自動(dòng)化外文文獻(xiàn)翻譯-在帶貨盤(pán)替代通道的自動(dòng)化倉(cāng)庫(kù)中安排整車(chē)運(yùn)作【中文8400字】 【PDF+中文WORD】,中文8400字,PDF+中文WORD,自動(dòng)化外文文獻(xiàn)翻譯-在帶貨盤(pán)替代通道的自動(dòng)化倉(cāng)庫(kù)中安排整車(chē)運(yùn)作【中文8400字】,【PDF+中文WORD】,自動(dòng)化,外文,文獻(xiàn),翻譯,帶貨盤(pán),替代,通道,倉(cāng)庫(kù),安排 【中文8400字】 在帶貨盤(pán)替代通道的自動(dòng)化倉(cāng)庫(kù)中安排整車(chē)運(yùn)作 Didem Cinar，JoséAntónioOliveira，Y. Ilker Topcu，Panos M. Pardalos 土耳其伊斯坦布爾伊斯坦布爾技術(shù)大學(xué)工業(yè)工程系管理學(xué)院 美國(guó)蓋恩斯維爾佛羅里達(dá)大學(xué)工程與系統(tǒng)工程系 葡萄牙布拉加Minho大學(xué)ALGORITMI研究中心 在這項(xiàng)研究中，調(diào)查了自動(dòng)化存儲(chǔ)和檢索系統(tǒng)中卡車(chē)裝載操作的調(diào)度。旨在于以前的出現(xiàn)問(wèn)題的擴(kuò)展，例如托盤(pán)可以從一組替代通道中取出。它被模擬為靈活的作業(yè)車(chē)間調(diào)度問(wèn)題，其中負(fù)載被視為工作，負(fù)載的托盤(pán)被視為操作，并且用于將檢索物品移除到卡車(chē)上的叉車(chē)被視為機(jī)器。最大限度縮短裝載時(shí)間是為了盡量減少訂單的吞吐時(shí)間，并最大限度地提高倉(cāng)庫(kù)的效率。提出了基于優(yōu)先級(jí)的遺傳算法來(lái)對(duì)檢索托盤(pán)進(jìn)行排序。置換編碼被用于編碼，并且生成用于靈活作業(yè)車(chē)間調(diào)度問(wèn)題的構(gòu)造性算法生成活動(dòng)調(diào)度被應(yīng)用于解碼。所提出的方法適用于由自動(dòng)化材料處理和存儲(chǔ)系統(tǒng)的領(lǐng)先供應(yīng)商安裝的倉(cāng)庫(kù)中出現(xiàn)的實(shí)際問(wèn)題。 1.簡(jiǎn)介 自動(dòng)化存儲(chǔ)和檢索系統(tǒng)（AS / RS）是一種倉(cāng)儲(chǔ)系統(tǒng)，它使用機(jī)械設(shè)備在分銷(xiāo)和生產(chǎn)環(huán)境中存儲(chǔ)和檢索產(chǎn)品[1,2]。自動(dòng)起重機(jī)通過(guò)機(jī)架之間的過(guò)道移動(dòng)，將物品放在機(jī)架上，并將這些物品從存儲(chǔ)器取回到收集器，以完成客戶訂單。 AS / RS是完全自動(dòng)化的，因?yàn)椴僮魅藛T不需要操作托盤(pán)[2]。當(dāng)收到一件物品的訂單時(shí)，堆垛起重機(jī)將托盤(pán)從其存放位置取回，并將其運(yùn)送到重力滾筒輸送機(jī)通道頂部的收集器。在滾筒輸送機(jī)的末端，使用叉車(chē)拾取所輸送的貨盤(pán)。 AS / RS [3]的一些優(yōu)點(diǎn)是空間利用率高，材料流量得到改善，庫(kù)存控制得到改善。通過(guò)系統(tǒng)的優(yōu)化設(shè)計(jì)和優(yōu)化調(diào)度，這種系統(tǒng)的最佳利用率可以成功。 倉(cāng)庫(kù)調(diào)度優(yōu)化是一個(gè)組合優(yōu)化問(wèn)題，在高維實(shí)例的合理計(jì)算時(shí)間內(nèi)無(wú)法用精確的算法求解。由于問(wèn)題的復(fù)雜性高，模擬和metaheuristics已被廣泛應(yīng)用于倉(cāng)庫(kù)調(diào)度優(yōu)化[4]。第3節(jié)給出了關(guān)于為AS / RS設(shè)計(jì)和調(diào)度開(kāi)發(fā)的方法的詳細(xì)文獻(xiàn)綜述。 在這項(xiàng)研究中，調(diào)查了在AS / RS中發(fā)生的卡車(chē)裝載操作的調(diào)度。通過(guò)將負(fù)載視為作業(yè)的作業(yè)和托盤(pán)作為其操作，該問(wèn)題被模擬為靈活的作業(yè)車(chē)間調(diào)度問(wèn)題（FJSP）。用于從收集器到卡車(chē)運(yùn)輸托盤(pán)的叉車(chē)被視為機(jī)器。本文的主要貢獻(xiàn)有兩個(gè)：（1）卡車(chē)裝載作業(yè)的調(diào)度被模擬為靈活的作業(yè)車(chē)間調(diào)度問(wèn)題;（2）由領(lǐng)先的自動(dòng)化物料處理供應(yīng)商安裝的AS / RS倉(cāng)庫(kù)中出現(xiàn)的真正問(wèn)題;存儲(chǔ)系統(tǒng)通過(guò)使用基于優(yōu)先級(jí)的遺傳算法來(lái)解決，并且通道選擇靈活性的影響被調(diào)查。就作者所知，這項(xiàng)工作是FSJP第一次用于模擬AS / RS倉(cāng)庫(kù)中托盤(pán)的檢索操作。 本文的結(jié)構(gòu)如下，第2節(jié)對(duì)調(diào)查的自動(dòng)化存儲(chǔ)系統(tǒng)進(jìn)行了簡(jiǎn)要說(shuō)明。在第3節(jié)中，給出了關(guān)于卡車(chē)裝載作業(yè)調(diào)度的文獻(xiàn)回顧。第4節(jié)表示AS / RS中的整車(chē)運(yùn)行調(diào)度問(wèn)題的混合整數(shù)規(guī)劃（MIP）公式，并討論將該問(wèn)題建模為靈活的作業(yè)車(chē)間調(diào)度問(wèn)題。第5節(jié)介紹了專(zhuān)門(mén)的方法。第6節(jié)給出了現(xiàn)實(shí)AS / RS倉(cāng)庫(kù)問(wèn)題的計(jì)算結(jié)果。最后，第7節(jié)給出了結(jié)論。 圖1.倉(cāng)庫(kù)的模式 2.存儲(chǔ)系統(tǒng) 本研究中提出的方法適用于作為配送中心的意大利AS / RS倉(cāng)庫(kù)。產(chǎn)品由倉(cāng)庫(kù)儲(chǔ)存并裝載到卡車(chē)上以滿足客戶的需求。預(yù)先知道的卡車(chē)路線是根據(jù)客戶訂單的交付截止日期確定的。倉(cāng)庫(kù)由11個(gè)過(guò)道組成，托盤(pán)架可容納40,000個(gè)托盤(pán)。自動(dòng)堆垛起重機(jī)或S / R機(jī)器在每個(gè)過(guò)道中工作，以將托盤(pán)從其各自的機(jī)架移動(dòng)到過(guò)道開(kāi)始時(shí)的收集器。叉車(chē)將貨盤(pán)運(yùn)送至卡車(chē)。倉(cāng)庫(kù)有13個(gè)?？亢逞b載卡車(chē)。圖1顯示了該倉(cāng)庫(kù)的裝貨流程。 倉(cāng)庫(kù)計(jì)劃系統(tǒng)（WPS）和倉(cāng)庫(kù)管理系統(tǒng)（WMS）用于操作倉(cāng)庫(kù)。每輛卡車(chē)的每日裝載計(jì)劃由WPS執(zhí)行。 WMS確定回收托盤(pán)和S / R機(jī)器和叉車(chē)的運(yùn)動(dòng)順序。一輛卡車(chē)每天可以檢索大約一百個(gè)貨物。每輛卡車(chē)都有自己的交貨時(shí)間，這是由WPS考慮的，并且裝載不得延遲。在為WPS定義的策略中，整套負(fù)載被分成稱(chēng)為批次的子集。同時(shí)處理一批中的加載。在完成前一批次的加載之前，無(wú)法啟動(dòng)加載批次。批量的大小是根據(jù)交貨期限和?？亢车臄?shù)量來(lái)確定的。標(biāo)準(zhǔn)的每日計(jì)劃包括15-20批次，每批6-13批次。 客戶的訂單包括一個(gè)或多個(gè)托盤(pán)上交付的產(chǎn)品或一組產(chǎn)品。訂單的產(chǎn)品組是預(yù)先知道的，并且在倉(cāng)庫(kù)中可用?？ㄜ?chē)負(fù)載由一組托盤(pán)運(yùn)送給一個(gè)或多個(gè)客戶。 WMS使用LIFO（后進(jìn)先出）規(guī)則確定卡車(chē)上裝載貨盤(pán)的順序。由于負(fù)載中的托盤(pán)序列是預(yù)先確定的并且不能改變，因此負(fù)載的托盤(pán)之間存在優(yōu)先關(guān)系。 貨物的托盤(pán)可以從任何通道中取出。為了便于將卡車(chē)分配到?？亢?，幾個(gè)托盤(pán)放置在不同的通道中，以減少準(zhǔn)備工作的時(shí)間，允許在接近卡車(chē)的通道中選擇托盤(pán)并尊重FEFO（First -Expired-First-Out）規(guī)則。 S / R機(jī)器編程為從相應(yīng)通道取回托盤(pán)。 我們假設(shè)每臺(tái)叉車(chē)只能為一個(gè)通道工作。叉車(chē)從自己的過(guò)道收到托盤(pán)后，可將托盤(pán)運(yùn)送到任何卡車(chē)。出于安全原因，不允許多臺(tái)叉車(chē)同時(shí)將貨盤(pán)放在卡車(chē)上。所以，一個(gè)負(fù)載應(yīng)該在特定時(shí)間收到一個(gè)托盤(pán)。托盤(pán)裝入卡車(chē)后，叉車(chē)返回到其通道并與WMS通信，以便它可用于新的運(yùn)輸。然后為相同的負(fù)載編程下一個(gè)托盤(pán)。叉車(chē)在每次運(yùn)輸時(shí)只能接收一個(gè)托盤(pán)。有關(guān)分析的AS / RS倉(cāng)庫(kù)的詳細(xì)信息可以從[5]中獲得。 由S / R機(jī)器檢索的批次中不同的托盤(pán)序列會(huì)導(dǎo)致不同的處理時(shí)間。一個(gè)說(shuō)明性的例子如下。假設(shè)A1，A2，...表示倉(cāng)庫(kù)中有5個(gè)過(guò)道。 。 A5。問(wèn)題在于規(guī)劃包含3個(gè)負(fù)載的批次的檢索順序。每個(gè)負(fù)載由4個(gè)托盤(pán)組成，這4個(gè)托盤(pán)預(yù)先具有優(yōu)先關(guān)系，代表該批次中將檢索的總共12個(gè)托盤(pán)。每個(gè)過(guò)道有一個(gè)叉車(chē)將托盤(pán)從過(guò)道搬運(yùn)到相應(yīng)的過(guò)道， 雖然托盤(pán)可以從幾個(gè)通道上取回，但在之前的研究中[5,6]，人們認(rèn)為這是WMS以前選擇的托盤(pán)，考慮到準(zhǔn)備裝載貨物的通道的距離。表1給出了每個(gè)托盤(pán)的通道和處理時(shí)間。 通道存放托盤(pán)j和相關(guān)通道與卡車(chē)之間的運(yùn)輸時(shí)間表示為（Ak，t），其中Ak表示第k通道，t是從通道Ak到卡車(chē)的運(yùn)輸時(shí)間。例如，第二個(gè)貨物的第一個(gè)托盤(pán)必須在時(shí)間1時(shí)從第三通道中取回。為方便起見(jiàn)，托盤(pán)從1到12連續(xù)編號(hào)。 表1真正問(wèn)題的一個(gè)說(shuō)明性例子 圖2.用于檢索托盤(pán)的兩種不同時(shí)間表 圖2顯示了兩個(gè)不同的檢索托盤(pán)序列。矩形內(nèi)的數(shù)字標(biāo)識(shí)托盤(pán)。對(duì)于每個(gè)序列，圖2顯示了該組通道（左側(cè)）的甘特圖和該組負(fù)荷（右側(cè)）的甘特圖，其表示更好的處理時(shí)間。取回托盤(pán)的順序僅在走道3處不同，托盤(pán)11在托盤(pán)3和7（圖2（a））之后或托盤(pán)3和7（圖2（b））之前收集。決定何時(shí)檢索托盤(pán)11會(huì)對(duì)整批貨物產(chǎn)生明顯不同的處理時(shí)間。圖2（a）給出了這個(gè)小例子的最優(yōu)解。 3.文獻(xiàn)回顧 在AS / RS中，計(jì)劃和執(zhí)行準(zhǔn)確的裝載流程對(duì)于在適當(dāng)?shù)臅r(shí)間滿足客戶訂單非常重要[5]。在以前的研究中，面向分析的構(gòu)成了文獻(xiàn)的大部分，而不是那些用于倉(cāng)庫(kù)設(shè)計(jì)的開(kāi)發(fā)模型和技術(shù)[7]。簡(jiǎn)單的啟發(fā)式和模擬技術(shù)被用于自動(dòng)化倉(cāng)儲(chǔ)系統(tǒng)中的存儲(chǔ)和檢索問(wèn)題。 Bozer和White [8]提出了具有單指令和雙指令模式的自動(dòng)化S / R機(jī)器的行程時(shí)間模型。 Han等人[9]提出了一種最近鄰啟發(fā)式方法用于在AS / RS中進(jìn)行雙重命令周期的檢索測(cè)序，并使用Monte Carlo仿真進(jìn)行評(píng)估。Eben-Chaime [10]也使用最近鄰居啟發(fā)式對(duì)檢索進(jìn)行排序。豪斯曼等人[3]比較了幾種存儲(chǔ)分配規(guī)則來(lái)確定最優(yōu)的存儲(chǔ)分配策略。施瓦茨等人。 [11]分析存儲(chǔ)分配和交錯(cuò)規(guī)則與模擬模型。 Lee和Schaefer [12]提出了這個(gè)問(wèn)題，這也是由Han等人處理的。 [9]，作為一個(gè)分配問(wèn)題。他們提出了一種將匈牙利方法和分配問(wèn)題的排序算法與巡回檢查和巡回演算算法相結(jié)合的方法。 在過(guò)去的幾年里，除了數(shù)學(xué)建模和模擬方法之外，metaheuristics已經(jīng)用于這些領(lǐng)域。倉(cāng)庫(kù)設(shè)計(jì)和控制的綜合評(píng)論可以在de Koster等人的文章中找到。 [13]，顧等人。 [14]和貝克和卡內(nèi)薩[15]。此外，Roodbergen和Vis [2]和Vasili等人提供了AS / RS設(shè)計(jì)中現(xiàn)有技術(shù)狀況的詳細(xì)解釋。 [16]。曼齊尼等人。 [17]開(kāi)發(fā)了一個(gè)多參數(shù)動(dòng)態(tài)模型，用于產(chǎn)品到采摘器的存儲(chǔ)系統(tǒng)，并具有基于類(lèi)的產(chǎn)品存儲(chǔ)分配。他們調(diào)查了影響倉(cāng)儲(chǔ)系統(tǒng)性能的因素。 Yin和Rau [18]將動(dòng)態(tài)選擇排序規(guī)則的模擬和遺傳算法結(jié)合起來(lái)，用于基于類(lèi)別的單位負(fù)載AS / RS。 Chang等人[19]提出了一個(gè)多目標(biāo)數(shù)學(xué)規(guī)劃模型和堆垛起重機(jī)訂單揀選的遺傳算法。 Kung等人[20]開(kāi)發(fā)了一種基于動(dòng)態(tài)規(guī)劃的訂單調(diào)度方法，用于在共軌上使用多臺(tái)堆垛起重機(jī)的AS / RS。問(wèn)題包括為每臺(tái)起重機(jī)分配訂單以及在沒(méi)有碰撞的情況下安排起重機(jī)。 Brezovnik等人[21]采用多目標(biāo)蟻群優(yōu)化方法處理AS / RS中的存儲(chǔ)分配問(wèn)題。根據(jù)從家電設(shè)備倉(cāng)庫(kù)獲得的計(jì)算結(jié)果，顯示當(dāng)重量和身高較低的產(chǎn)品存儲(chǔ)在較高級(jí)別時(shí)，可以實(shí)現(xiàn)最佳空間利用率。楊等人。 [22]推斷S / R機(jī)器的速度曲線對(duì)多深度AS / RS的最佳存儲(chǔ)機(jī)架有重要影響。 Atmaca和Ozturk [4]提出了一種用于存儲(chǔ)分配和存儲(chǔ)分配問(wèn)題的數(shù)學(xué)規(guī)劃模型和模擬退火方法，以最大限度地降低存儲(chǔ)成本。通過(guò)提出的數(shù)學(xué)模型獲得了最多103種材料問(wèn)題的最優(yōu)解。 Dooly和Lee [23]將雙梭AS / RS的基于移位的測(cè)序問(wèn)題建模為最小成本完美匹配問(wèn)題，并提出了多項(xiàng)式時(shí)間精確算法。 Oliveira [5]和Figueiredo等人。[6]將AS / RS倉(cāng)庫(kù)中的卡車(chē)裝載作業(yè)模擬為帶再循環(huán)的作業(yè)車(chē)間調(diào)度問(wèn)題（JSP）[5]。奧利維拉[5]假定運(yùn)輸托盤(pán)的處理時(shí)間相同，而不依賴(lài)于過(guò)道和卡車(chē)的位置。 Figueiredo等人[6]通過(guò)考慮不同的處理時(shí)間來(lái)擴(kuò)展該問(wèn)題，并通過(guò)具有隨機(jī)密鑰表示的遺傳算法來(lái)解決該問(wèn)題。 Oliveira [5]和Figueiredo等人[ [6]認(rèn)為托盤(pán)可以從以前由WMS決定的一個(gè)通道檢索，考慮到靠近停靠灣。在這項(xiàng)研究中，這個(gè)假設(shè)通過(guò)考慮托盤(pán)的替代通道來(lái)擴(kuò)展?？ㄜ?chē)裝載調(diào)度同時(shí)確定托盤(pán)取回過(guò)道的選擇。因此，問(wèn)題包括選擇通道來(lái)檢索托盤(pán)（目前由WMS執(zhí)行），以及托盤(pán)從收集器到卡車(chē)的運(yùn)輸安排。通過(guò)這種方式，結(jié)合這兩種操作的好處被調(diào)查。在本研究的范圍內(nèi)沒(méi)有發(fā)現(xiàn)將這個(gè)問(wèn)題作為FJSP的研究。 4.將AS / RS倉(cāng)庫(kù)建模為FJSP 在本節(jié)中，介紹了用于整車(chē)運(yùn)行調(diào)度問(wèn)題的MIP公式。我們不考慮交叉對(duì)接或訂單揀選生產(chǎn)托盤(pán)。本研究考慮的假設(shè)如下： ?訂單僅由存儲(chǔ)在倉(cāng)庫(kù)中的（完整）托盤(pán)產(chǎn)品組成。 ?S / R機(jī)器比叉車(chē)更快地將托盤(pán)放在收集器上，以卸下托盤(pán)并且S / R機(jī)器在叉車(chē)之前運(yùn)行， ?收集器作為一個(gè)緩沖器，可以處理多個(gè)托盤(pán)， ?收集器（重力滾筒輸送機(jī)）中托盤(pán)的流量遵循FIFO規(guī)則， ?S / R機(jī)器需要零時(shí)間將托盤(pán)放入收集器中。 表2給出了后面使用的表示法。整車(chē)運(yùn)行調(diào)度的MIP公式如下： 表2 MIP的表示法 （1） 0中給出了目標(biāo)函數(shù)，以使批次的總加載時(shí)間最小化。約束條件（2）保證每個(gè)托盤(pán)僅由一臺(tái)叉車(chē)運(yùn)輸。約束條件（3）確保如果托盤(pán)未分配給叉車(chē)，則該叉車(chē)托盤(pán)的運(yùn)輸開(kāi)始和結(jié)束時(shí)間為零。如果在叉車(chē)k上分配，則約束條件（4）保證該托盤(pán)的運(yùn)輸完成時(shí)間不能小于其起始時(shí)間和運(yùn)輸時(shí)間之和。約束條件（5）和（6）滿足叉車(chē)在將當(dāng)前托盤(pán)運(yùn)送到相應(yīng)的叉車(chē)之前不能開(kāi)始運(yùn)送下一個(gè)托盤(pán)。在（7）中給出了每個(gè)載荷的優(yōu)先約束，這確保了在相同載荷的前一個(gè)托盤(pán)的運(yùn)輸完成之前不能運(yùn)載載荷的托盤(pán)。約束條件（8）和（9）分別給出了每個(gè)負(fù)載和批次的完成時(shí)間。約束（10） - （14）表示決策變量的二元約束和符號(hào)限制。 由（1） - （14）給出的模型是?zgüven等人提出的模型的調(diào)整版本。 [24] FJSP。這個(gè)問(wèn)題可以被歸類(lèi)為FJSP，其中貨物被認(rèn)為是工作，貨物的貨盤(pán)被認(rèn)為是工作的操作，并且用于將檢索物品移除到貨車(chē)的叉車(chē)被視為機(jī)器。最小化完工時(shí)間（運(yùn)輸時(shí)間）是目標(biāo)，因?yàn)檫@樣可以最大限度地減少訂單的吞吐時(shí)間并最大化倉(cāng)庫(kù)效率。 在FJSP中，不能同時(shí)在機(jī)器上處理多個(gè)操作。此外，對(duì)于滿足托盤(pán)優(yōu)先關(guān)系的所有工作，都存在技術(shù)限制。在倉(cāng)庫(kù)中，叉車(chē)只能像FJSP中的機(jī)器一樣在一定時(shí)間只運(yùn)載一個(gè)托盤(pán)。同樣，對(duì)于每個(gè)應(yīng)該保證的負(fù)載，都有一個(gè)接收訂單托盤(pán)。在前一個(gè)之前沒(méi)有裝載palletcan。換句話說(shuō)，不允許重疊相同載荷的貨盤(pán)的運(yùn)輸。每個(gè)負(fù)載的托盤(pán)順序可以作為技術(shù)限制來(lái)考慮。 在倉(cāng)庫(kù)中，裝載可以同時(shí)實(shí)現(xiàn)，并應(yīng)在由WPS確定的時(shí)間窗內(nèi)結(jié)束。所有負(fù)荷應(yīng)盡快結(jié)束以方便裝入下列批次。在加載當(dāng)前批次的所有裝載之前，無(wú)法啟動(dòng)新批次的準(zhǔn)備。盡快終止批量加載并減少碼頭占用是通過(guò)縮短完工時(shí)間來(lái)實(shí)現(xiàn)的。 表3一個(gè)真正問(wèn)題的例子 下面的例子是以前的例子的擴(kuò)展?，F(xiàn)在有些托盤(pán)可以從兩個(gè)通道中取出，而前一個(gè)托盤(pán)和一個(gè)處理時(shí)間更長(zhǎng)的新替代物。每個(gè)托盤(pán)的替代通道和處理時(shí)間在表3中給出。例如，第二個(gè)負(fù)載的第一個(gè)托盤(pán)可以從處理時(shí)間2的第二個(gè)通道或第一個(gè)時(shí)間的第三個(gè)通道中獲取。 當(dāng)所有托盤(pán)從處理時(shí)間最短的通道中取出時(shí)，可獲得一個(gè)可行的時(shí)間表，如圖3（a）所示，即圖2（a）所示的相同解決方案。讓我們分配走道2，即使它的處理時(shí)間比負(fù)載2的第三個(gè)托盤(pán)的走道3和負(fù)載2的第四個(gè)托盤(pán)的走道1的處理時(shí)間更長(zhǎng)。此分配的最佳時(shí)間表如圖3（b）所示。盡管將兩個(gè)托盤(pán)分配到較大的處理時(shí)間，但是就批次的完成時(shí)間而言獲得了更好的時(shí)間表。 5.方法 FJSP是一個(gè)NP難題，因?yàn)楦?jiǎn)單的問(wèn)題是JSP，在強(qiáng)烈意義上是NP難的問(wèn)題[25]。因此，在合理的時(shí)間內(nèi)不可能用精確的解決方案獲得最佳的解決方案。已經(jīng)開(kāi)發(fā)了各種近似算法來(lái)獲得大尺寸調(diào)度實(shí)例的良好結(jié)果[26]。遺傳算法（GAs）[27-33]，粒子群優(yōu)化算法[34,35]，蟻群算法[36,37]，模擬退火算法[38]，變鄰域搜索算法[39,40]和禁忌搜索算法[ 42]已被用于最小化文獻(xiàn)中FJSP的完工時(shí)間。在這項(xiàng)研究中，Cinar等人為FJSP開(kāi)發(fā)了一個(gè)基于優(yōu)先級(jí)的GA。 [27]用于解決整車(chē)運(yùn)行調(diào)度問(wèn)題。 5.1 表象 染色體的每個(gè)基因代表用于解碼的構(gòu)造性算法的操作的優(yōu)先級(jí)。置換代碼被選擇來(lái)引用優(yōu)先值。在這項(xiàng)研究中，每個(gè)染色體中的基因數(shù)量等于相應(yīng)替代機(jī)器處理的可能操作數(shù)量。圖4說(shuō)明了圖3（b）給出的時(shí)間表的樣本染色體。較高的優(yōu)先值意味著在施工過(guò)程中安排較高的優(yōu)先級(jí)，這將在下一小節(jié)中解釋。例如，負(fù)載1的第一個(gè)托盤(pán)的優(yōu)先級(jí)在A1上是18，在A3上是14。如果在建構(gòu)性算法的迭代中在這些替代方案之間進(jìn)行選擇是必要的，則將選擇A1，因?yàn)樗哂懈叩膬?yōu)先級(jí)。 5.2 解碼 解決方案由Chang和Sullivan [43]開(kāi)發(fā)的構(gòu)造算法進(jìn)行解碼，該算法可以為FJSP生成所有有效的時(shí)間表[27]?；顒?dòng)時(shí)間表構(gòu)成可行時(shí)間表的一個(gè)子集，包括最佳時(shí)間表。 構(gòu)造性算法僅根據(jù)染色體上的信息生成時(shí)間表。通過(guò)這種方式，可以保證最佳的解決方案包含在搜索空間中，不可能生成不可行或不可行的解決方案。另一方面，編碼和解空間之間發(fā)生n對(duì)1的關(guān)系。換句話說(shuō)，多于一個(gè)染色體可以代表相同的時(shí)間表[27]。 圖3.說(shuō)明性示例的示例時(shí)間表 圖4.說(shuō)明性例子的樣本染色體。 5.3.Genetic操作符 精英規(guī)則和輪盤(pán)賭被用作選擇操作員的方法。應(yīng)用兩個(gè)交叉操作符：循環(huán)交叉（CX）和基于作業(yè)的交換（JOX）。 CX是用于排列編碼問(wèn)題的通用算子。絕對(duì)基因位置是從父母遺傳到后代。 JOX是由[44]開(kāi)發(fā)的基于問(wèn)題的交叉操作符，用于JSP以滿足幾代人繼承工作順序的需求?；趦?yōu)先級(jí)的置換編碼可以輕松實(shí)現(xiàn)JOX，并且不需要任何修復(fù)機(jī)制。 應(yīng)用機(jī)器變異和序列變異來(lái)重新分配操作，移植變異用于全局搜索。機(jī)器突變是為了替代機(jī)器（貨架/叉車(chē)）上的操作（貨盤(pán)）而開(kāi)發(fā)的。它使用基于關(guān)鍵路徑的鄰域結(jié)構(gòu)。由于不屬于關(guān)鍵路徑的操作的重新分配不會(huì)改變完工時(shí)間，因此從關(guān)鍵路徑中隨機(jī)地選擇操作以進(jìn)行重新分配。從替代機(jī)器中隨機(jī)選擇一臺(tái)機(jī)器，并將操作安排到隨機(jī)位置。 為了增強(qiáng)鄰域搜索，開(kāi)發(fā)了一種基于塊結(jié)構(gòu)的序列變異來(lái)重定位當(dāng)前機(jī)器上的操作。從關(guān)鍵路徑中隨機(jī)選擇一項(xiàng)操作。它在相應(yīng)塊的所有操作之前或之后重新安排。 遷移是一種全局搜索的變異算子，通過(guò)在每一代中隨機(jī)產(chǎn)生一個(gè)染色體來(lái)替代至少一個(gè)染色體，從而增強(qiáng)基因庫(kù)中的多樣性。在遺傳算法的每次迭代中，確定具有相同財(cái)富價(jià)值的個(gè)體，并將移民程序應(yīng)用于他們。通過(guò)這種方式，減少了n對(duì)1映射的限制。 5.4 基于優(yōu)先級(jí)的遺傳算法 最初的人口是隨機(jī)產(chǎn)生的。建構(gòu)性算法用于評(píng)估個(gè)體。在每次迭代開(kāi)始時(shí)，執(zhí)行移民程序以減少當(dāng)前人群中具有相同財(cái)富價(jià)值的人數(shù)。包括父母在內(nèi)的交配池由選擇構(gòu)建。交配池的2％由精英規(guī)則選擇，并由輪盤(pán)選擇。交叉操作符用于生成后代。如果選擇兩個(gè)父母進(jìn)行交叉，則每個(gè)交叉運(yùn)算符（CX，JOX）有50％的機(jī)會(huì)被應(yīng)用。在交叉過(guò)程終止后，將變換運(yùn)算符應(yīng)用于生成的個(gè)體。就像在交叉過(guò)程中一樣，如果個(gè)體會(huì)發(fā)生變異，每個(gè)突變算子（機(jī)器，序列）有50％的概率。在遺傳算法的每個(gè)重現(xiàn)過(guò)程結(jié)束時(shí)，迭代局部搜索（ILS）被應(yīng)用于群體中具有最佳適應(yīng)度值的小量染色體。 ILS用于搜索更好的解決方案。由于計(jì)算量很大，因此只適用于少數(shù)人。下一代通過(guò)成對(duì)比較來(lái)確定，其中每個(gè)種群中的一個(gè)個(gè)體（當(dāng)前和由遺傳操作者產(chǎn)生的）在適應(yīng)值方面進(jìn)行比較。更好的一個(gè)被轉(zhuǎn)移到下一代。 GA的迭代一直持續(xù)到達(dá)到最大代數(shù)。基于優(yōu)先級(jí)的GA的流程圖在圖5中給出。 表4從BC數(shù)據(jù)集avRD獲得的平均相對(duì)偏差 6.計(jì)算結(jié)果 Cinar等人[27]將基于優(yōu)先級(jí)的遺傳算法與文獻(xiàn)中為FJSP開(kāi)發(fā)的其他算法進(jìn)行了比較。基于優(yōu)先級(jí)的遺傳算法得到的結(jié)果與文獻(xiàn)中的算法和給出基于優(yōu)先級(jí)的遺傳算法獲得的改進(jìn)百分比的相對(duì)偏差進(jìn)行了比較。 Cinar等人獲得的結(jié)果。 [27]總結(jié)在表4和表5中。表4和5包括Chambers和Barnes [45]（BC數(shù)據(jù)集）和Hurink等人生成的實(shí)例的平均相對(duì)偏差（avRD）。 （HU數(shù)據(jù)集）。表格的第一列和第二列表示每個(gè)實(shí)例的作業(yè)數(shù)量和機(jī)器數(shù)量。第三列給出了相應(yīng)數(shù)據(jù)集中具有指定大小的實(shí)例的數(shù)量。例如，在BC數(shù)據(jù)集中有兩個(gè)實(shí)例有10個(gè)作業(yè)和11個(gè)機(jī)器（表4）?；趦?yōu)先級(jí)的GA與Mastrolilli和Gambardella [47]和Gao等人的結(jié)果進(jìn)行了比較。對(duì)于BC實(shí)例，以avRD（表4的最后兩列）以及Behnke和Geiger [49]對(duì)于HU實(shí)例（表5的最后一列）來(lái)表示。根據(jù)這些結(jié)果，基于優(yōu)先級(jí)的遺傳算法是一種有效的算法，相對(duì)于平均遺傳算法為FJSP獲得接近最優(yōu)的結(jié)果[27]。因此，在本研究范圍內(nèi)，選擇基于優(yōu)先級(jí)的遺傳算法來(lái)解決AS / RS中卡車(chē)負(fù)荷運(yùn)行的調(diào)度問(wèn)題。 表5從HU數(shù)據(jù)集中獲得的平均相對(duì)偏差。 圖5.基于優(yōu)先級(jí)的GA。 Oliveira [5]使用代表性的相關(guān)AS / RS問(wèn)題實(shí)例和JPS文獻(xiàn)中的測(cè)試實(shí)例進(jìn)行計(jì)算機(jī)實(shí)驗(yàn)。真正問(wèn)題的代表性實(shí)例是隨機(jī)生成的，代表一個(gè)JSP進(jìn)行再循環(huán)。這些實(shí)例的維度與實(shí)際問(wèn)題的定義的最大維度相同。 Figueiredo等人[6]為相同的真實(shí)問(wèn)題生成隨機(jī)實(shí)例。我們使用Figueiredo等人提出的實(shí)際問(wèn)題的相同代表性實(shí)例。 [6]通過(guò)為一些貨物托盤(pán)添加替代通道。 表6 Figueiredo等人使用的操作分布[6] 卡車(chē)的裝載（作業(yè)）由35個(gè)托盤(pán)（作業(yè)）組成，這些托盤(pán)來(lái)自靠近停靠站的5個(gè)走道（機(jī)器）。 Figueiredo等人[6]根據(jù)表6中定義的分布確定了存放35個(gè)托盤(pán)的一個(gè)貨物的通道。例如，貨物5以相等的概率存儲(chǔ)在5個(gè)通道（通道2-6）之一中，即20/100 = 0.5。在這項(xiàng)研究中，一個(gè)程序可以將JSP的實(shí)例轉(zhuǎn)換為Figueiredo等人生成的再循環(huán)。 [6] FJSP實(shí)例和基于優(yōu)先級(jí)的GA在Microsoft Visual C ++ V7.0中編碼。為每個(gè)貨物隨機(jī)選擇的托盤(pán)添加一個(gè)替代通道。替代通道和相應(yīng)卡車(chē)之間的處理時(shí)間大于JSP數(shù)據(jù)和卡車(chē)中確定的通道之間的時(shí)間。通過(guò)這種方式，研究了將檢索序列建模為FJSP的好處。 每個(gè)實(shí)例都有兩種不同的人口規(guī)模：20人中的小人口和100人中的大一人。突變和交叉概率都被確定為0.5。計(jì)算結(jié)果在表7中給出。第一列至第四列代表實(shí)例名稱(chēng)，人口規(guī)模（彈出大?。b載/作業(yè)數(shù)量（n）以及托盤(pán)/操作總數(shù)（操作）。第五和第六列表示菲格雷多等人15次獲得的最佳平均完工時(shí)間。 [6]。第七和第八列表示通過(guò)基于優(yōu)先級(jí)的GA獲得的15次運(yùn)行的最佳平均完工時(shí)間。第九列給出了獲得最小值的實(shí)驗(yàn)數(shù)量，而第十列表示15次運(yùn)行中的有價(jià)值的標(biāo)準(zhǔn)偏差。第十一列代表平均CPU時(shí)間。對(duì)每個(gè)實(shí)驗(yàn)執(zhí)行500次迭代。 根據(jù)計(jì)算結(jié)果，包括靈活性會(huì)給出更好的結(jié)果，特別是對(duì)于那些有大量工作的實(shí)例。擬議的GA發(fā)現(xiàn)FJSP數(shù)據(jù)集的結(jié)果比JSP數(shù)據(jù)的結(jié)果更好或相同。因此可以得出結(jié)論，檢索排序問(wèn)題可以更好地模擬為FJSP。 圖6顯示了人口規(guī)模為20和100的最大實(shí)例（jr 13 2）在整個(gè)迭代過(guò)程中的最佳適應(yīng)值。雖然大型實(shí)例需要額外的CPU時(shí)間，但更大的群體規(guī)?？梢垣@得更好的解決方案。人口規(guī)模為100和32.7秒需要164.8秒，實(shí)例“jr 13 2”的人口規(guī)模為20。該算法還可以在更大的人口規(guī)模下更加穩(wěn)健地執(zhí)行 表7計(jì)算結(jié)果 圖6.適合度評(píng)估 7.總結(jié) 在這項(xiàng)研究中，在AS / RS中出現(xiàn)的卡車(chē)裝載操作的調(diào)度被模擬為FJSP。基于優(yōu)先級(jí)的GA應(yīng)用于真正的AS / RS倉(cāng)庫(kù)，以對(duì)檢索到的托盤(pán)進(jìn)行排序。 Figueiredo等人生成的數(shù)據(jù)集[6]對(duì)于同一個(gè)倉(cāng)庫(kù)，通過(guò)為某些操作添加替代機(jī)器進(jìn)行擴(kuò)展。通過(guò)這種方式，研究了通道選擇靈活性的影響。生成的數(shù)據(jù)集的維度與真正的問(wèn)題相同。在倉(cāng)庫(kù)每日問(wèn)題的便利計(jì)算時(shí)間內(nèi)找到合理的解決方案。證明了所提出的基于優(yōu)先級(jí)的遺傳算法可以用來(lái)解決倉(cāng)庫(kù)中現(xiàn)實(shí)生活中的檢索排序問(wèn)題。在用來(lái)說(shuō)明FJSP優(yōu)勢(shì)的一組實(shí)例中，我們只考慮一個(gè)額外的過(guò)道來(lái)檢索托盤(pán)。使用額外的過(guò)道具有更長(zhǎng)的處理時(shí)間，這是我們做出的一個(gè)保守的選擇，并且在真正的問(wèn)題中，它可能具有相同的甚至更低的處理時(shí)間。盡管如此，如果方便的話，使用更長(zhǎng)的處理時(shí)間會(huì)導(dǎo)致更低的完工時(shí)間，從而提高處理速度 倉(cāng)庫(kù)的有效性。對(duì)于具有相似實(shí)際問(wèn)題大小的實(shí)例集，F(xiàn)JSP模型平均可以獲得高達(dá)11％的增益和7％左右的增益。很明顯，如果我們考慮使用不止一個(gè)替代通道來(lái)檢索托盤(pán)，這些收益會(huì)更大。 提高吞吐率，在更短的時(shí)間內(nèi)為客戶服務(wù)，并減少卡車(chē)和司機(jī)裝貨的等待時(shí)間，這些結(jié)果是其他管理方面的好處。如今，為了增加倉(cāng)庫(kù)的吞吐量，倉(cāng)庫(kù)建立了更多的過(guò)道，在卡車(chē)到達(dá)之前準(zhǔn)備了多個(gè)緩沖區(qū)以準(zhǔn)備貨物，在通道開(kāi)始時(shí)有多達(dá)3個(gè)收集器以及更多數(shù)量的托盤(pán)，從而導(dǎo)致更多昂貴的項(xiàng)目。從JSP運(yùn)營(yíng)模式向FSJP運(yùn)營(yíng)模式的轉(zhuǎn)變只需要WMS升級(jí)，短期內(nèi)將全面回放，避免大量投資增加倉(cāng)儲(chǔ)容量。 在這項(xiàng)研究中，通道和卡車(chē)之間的運(yùn)輸時(shí)間假定在整個(gè)裝載過(guò)程中固定。在進(jìn)一步的研究中，這個(gè)假設(shè)可以擴(kuò)展到使問(wèn)題更加真實(shí)。此外，產(chǎn)品的惡化會(huì)對(duì)生產(chǎn)過(guò)程產(chǎn)生負(fù)面影響[50,51]，因此可以考慮安排倉(cāng)庫(kù)中的托盤(pán)。 致謝 這項(xiàng)研究得到了LATNA實(shí)驗(yàn)室，NRU HSE，RF政府資助，ag的部分支持。 11.G34.31.0057。