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