自動化外文文獻(xiàn)翻譯-在帶貨盤替代通道的自動化倉庫中安排整車運(yùn)作【中文8400字】 【PDF+中文WORD】,中文8400字,PDF+中文WORD,自動化外文文獻(xiàn)翻譯-在帶貨盤替代通道的自動化倉庫中安排整車運(yùn)作【中文8400字】,【PDF+中文WORD】,自動化,外文,文獻(xiàn),翻譯,帶貨盤,替代,通道,倉庫,安排 【中文8400字】 在帶貨盤替代通道的自動化倉庫中安排整車運(yùn)作 Didem Cinar，JoséAntónioOliveira，Y. Ilker Topcu，Panos M. Pardalos 土耳其伊斯坦布爾伊斯坦布爾技術(shù)大學(xué)工業(yè)工程系管理學(xué)院 美國蓋恩斯維爾佛羅里達(dá)大學(xué)工程與系統(tǒng)工程系 葡萄牙布拉加Minho大學(xué)ALGORITMI研究中心 在這項研究中，調(diào)查了自動化存儲和檢索系統(tǒng)中卡車裝載操作的調(diào)度。旨在于以前的出現(xiàn)問題的擴(kuò)展，例如托盤可以從一組替代通道中取出。它被模擬為靈活的作業(yè)車間調(diào)度問題，其中負(fù)載被視為工作，負(fù)載的托盤被視為操作，并且用于將檢索物品移除到卡車上的叉車被視為機(jī)器。最大限度縮短裝載時間是為了盡量減少訂單的吞吐時間，并最大限度地提高倉庫的效率。提出了基于優(yōu)先級的遺傳算法來對檢索托盤進(jìn)行排序。置換編碼被用于編碼，并且生成用于靈活作業(yè)車間調(diào)度問題的構(gòu)造性算法生成活動調(diào)度被應(yīng)用于解碼。所提出的方法適用于由自動化材料處理和存儲系統(tǒng)的領(lǐng)先供應(yīng)商安裝的倉庫中出現(xiàn)的實際問題。 1.簡介 自動化存儲和檢索系統(tǒng)（AS / RS）是一種倉儲系統(tǒng)，它使用機(jī)械設(shè)備在分銷和生產(chǎn)環(huán)境中存儲和檢索產(chǎn)品[1,2]。自動起重機(jī)通過機(jī)架之間的過道移動，將物品放在機(jī)架上，并將這些物品從存儲器取回到收集器，以完成客戶訂單。 AS / RS是完全自動化的，因為操作人員不需要操作托盤[2]。當(dāng)收到一件物品的訂單時，堆垛起重機(jī)將托盤從其存放位置取回，并將其運(yùn)送到重力滾筒輸送機(jī)通道頂部的收集器。在滾筒輸送機(jī)的末端，使用叉車拾取所輸送的貨盤。 AS / RS [3]的一些優(yōu)點是空間利用率高，材料流量得到改善，庫存控制得到改善。通過系統(tǒng)的優(yōu)化設(shè)計和優(yōu)化調(diào)度，這種系統(tǒng)的最佳利用率可以成功。 倉庫調(diào)度優(yōu)化是一個組合優(yōu)化問題，在高維實例的合理計算時間內(nèi)無法用精確的算法求解。由于問題的復(fù)雜性高，模擬和metaheuristics已被廣泛應(yīng)用于倉庫調(diào)度優(yōu)化[4]。第3節(jié)給出了關(guān)于為AS / RS設(shè)計和調(diào)度開發(fā)的方法的詳細(xì)文獻(xiàn)綜述。 在這項研究中，調(diào)查了在AS / RS中發(fā)生的卡車裝載操作的調(diào)度。通過將負(fù)載視為作業(yè)的作業(yè)和托盤作為其操作，該問題被模擬為靈活的作業(yè)車間調(diào)度問題（FJSP）。用于從收集器到卡車運(yùn)輸托盤的叉車被視為機(jī)器。本文的主要貢獻(xiàn)有兩個：（1）卡車裝載作業(yè)的調(diào)度被模擬為靈活的作業(yè)車間調(diào)度問題;（2）由領(lǐng)先的自動化物料處理供應(yīng)商安裝的AS / RS倉庫中出現(xiàn)的真正問題;存儲系統(tǒng)通過使用基于優(yōu)先級的遺傳算法來解決，并且通道選擇靈活性的影響被調(diào)查。就作者所知，這項工作是FSJP第一次用于模擬AS / RS倉庫中托盤的檢索操作。 本文的結(jié)構(gòu)如下，第2節(jié)對調(diào)查的自動化存儲系統(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)實AS / RS倉庫問題的計算結(jié)果。最后，第7節(jié)給出了結(jié)論。 圖1.倉庫的模式 2.存儲系統(tǒng) 本研究中提出的方法適用于作為配送中心的意大利AS / RS倉庫。產(chǎn)品由倉庫儲存并裝載到卡車上以滿足客戶的需求。預(yù)先知道的卡車路線是根據(jù)客戶訂單的交付截止日期確定的。倉庫由11個過道組成，托盤架可容納40,000個托盤。自動堆垛起重機(jī)或S / R機(jī)器在每個過道中工作，以將托盤從其各自的機(jī)架移動到過道開始時的收集器。叉車將貨盤運(yùn)送至卡車。倉庫有13個?？亢逞b載卡車。圖1顯示了該倉庫的裝貨流程。 倉庫計劃系統(tǒng)（WPS）和倉庫管理系統(tǒng)（WMS）用于操作倉庫。每輛卡車的每日裝載計劃由WPS執(zhí)行。 WMS確定回收托盤和S / R機(jī)器和叉車的運(yùn)動順序。一輛卡車每天可以檢索大約一百個貨物。每輛卡車都有自己的交貨時間，這是由WPS考慮的，并且裝載不得延遲。在為WPS定義的策略中，整套負(fù)載被分成稱為批次的子集。同時處理一批中的加載。在完成前一批次的加載之前，無法啟動加載批次。批量的大小是根據(jù)交貨期限和停靠海灣的數(shù)量來確定的。標(biāo)準(zhǔn)的每日計劃包括15-20批次，每批6-13批次。 客戶的訂單包括一個或多個托盤上交付的產(chǎn)品或一組產(chǎn)品。訂單的產(chǎn)品組是預(yù)先知道的，并且在倉庫中可用?？ㄜ囏?fù)載由一組托盤運(yùn)送給一個或多個客戶。 WMS使用LIFO（后進(jìn)先出）規(guī)則確定卡車上裝載貨盤的順序。由于負(fù)載中的托盤序列是預(yù)先確定的并且不能改變，因此負(fù)載的托盤之間存在優(yōu)先關(guān)系。 貨物的托盤可以從任何通道中取出。為了便于將卡車分配到?？亢常瑤讉€托盤放置在不同的通道中，以減少準(zhǔn)備工作的時間，允許在接近卡車的通道中選擇托盤并尊重FEFO（First -Expired-First-Out）規(guī)則。 S / R機(jī)器編程為從相應(yīng)通道取回托盤。 我們假設(shè)每臺叉車只能為一個通道工作。叉車從自己的過道收到托盤后，可將托盤運(yùn)送到任何卡車。出于安全原因，不允許多臺叉車同時將貨盤放在卡車上。所以，一個負(fù)載應(yīng)該在特定時間收到一個托盤。托盤裝入卡車后，叉車返回到其通道并與WMS通信，以便它可用于新的運(yùn)輸。然后為相同的負(fù)載編程下一個托盤。叉車在每次運(yùn)輸時只能接收一個托盤。有關(guān)分析的AS / RS倉庫的詳細(xì)信息可以從[5]中獲得。 由S / R機(jī)器檢索的批次中不同的托盤序列會導(dǎo)致不同的處理時間。一個說明性的例子如下。假設(shè)A1，A2，...表示倉庫中有5個過道。 。 A5。問題在于規(guī)劃包含3個負(fù)載的批次的檢索順序。每個負(fù)載由4個托盤組成，這4個托盤預(yù)先具有優(yōu)先關(guān)系，代表該批次中將檢索的總共12個托盤。每個過道有一個叉車將托盤從過道搬運(yùn)到相應(yīng)的過道， 雖然托盤可以從幾個通道上取回，但在之前的研究中[5,6]，人們認(rèn)為這是WMS以前選擇的托盤，考慮到準(zhǔn)備裝載貨物的通道的距離。表1給出了每個托盤的通道和處理時間。 通道存放托盤j和相關(guān)通道與卡車之間的運(yùn)輸時間表示為（Ak，t），其中Ak表示第k通道，t是從通道Ak到卡車的運(yùn)輸時間。例如，第二個貨物的第一個托盤必須在時間1時從第三通道中取回。為方便起見，托盤從1到12連續(xù)編號。 表1真正問題的一個說明性例子 圖2.用于檢索托盤的兩種不同時間表 圖2顯示了兩個不同的檢索托盤序列。矩形內(nèi)的數(shù)字標(biāo)識托盤。對于每個序列，圖2顯示了該組通道（左側(cè)）的甘特圖和該組負(fù)荷（右側(cè)）的甘特圖，其表示更好的處理時間。取回托盤的順序僅在走道3處不同，托盤11在托盤3和7（圖2（a））之后或托盤3和7（圖2（b））之前收集。決定何時檢索托盤11會對整批貨物產(chǎn)生明顯不同的處理時間。圖2（a）給出了這個小例子的最優(yōu)解。 3.文獻(xiàn)回顧 在AS / RS中，計劃和執(zhí)行準(zhǔn)確的裝載流程對于在適當(dāng)?shù)臅r間滿足客戶訂單非常重要[5]。在以前的研究中，面向分析的構(gòu)成了文獻(xiàn)的大部分，而不是那些用于倉庫設(shè)計的開發(fā)模型和技術(shù)[7]。簡單的啟發(fā)式和模擬技術(shù)被用于自動化倉儲系統(tǒng)中的存儲和檢索問題。 Bozer和White [8]提出了具有單指令和雙指令模式的自動化S / R機(jī)器的行程時間模型。 Han等人[9]提出了一種最近鄰啟發(fā)式方法用于在AS / RS中進(jìn)行雙重命令周期的檢索測序，并使用Monte Carlo仿真進(jìn)行評估。Eben-Chaime [10]也使用最近鄰居啟發(fā)式對檢索進(jìn)行排序。豪斯曼等人[3]比較了幾種存儲分配規(guī)則來確定最優(yōu)的存儲分配策略。施瓦茨等人。 [11]分析存儲分配和交錯規(guī)則與模擬模型。 Lee和Schaefer [12]提出了這個問題，這也是由Han等人處理的。 [9]，作為一個分配問題。他們提出了一種將匈牙利方法和分配問題的排序算法與巡回檢查和巡回演算算法相結(jié)合的方法。 在過去的幾年里，除了數(shù)學(xué)建模和模擬方法之外，metaheuristics已經(jīng)用于這些領(lǐng)域。倉庫設(shè)計和控制的綜合評論可以在de Koster等人的文章中找到。 [13]，顧等人。 [14]和貝克和卡內(nèi)薩[15]。此外，Roodbergen和Vis [2]和Vasili等人提供了AS / RS設(shè)計中現(xiàn)有技術(shù)狀況的詳細(xì)解釋。 [16]。曼齊尼等人。 [17]開發(fā)了一個多參數(shù)動態(tài)模型，用于產(chǎn)品到采摘器的存儲系統(tǒng)，并具有基于類的產(chǎn)品存儲分配。他們調(diào)查了影響倉儲系統(tǒng)性能的因素。 Yin和Rau [18]將動態(tài)選擇排序規(guī)則的模擬和遺傳算法結(jié)合起來，用于基于類別的單位負(fù)載AS / RS。 Chang等人[19]提出了一個多目標(biāo)數(shù)學(xué)規(guī)劃模型和堆垛起重機(jī)訂單揀選的遺傳算法。 Kung等人[20]開發(fā)了一種基于動態(tài)規(guī)劃的訂單調(diào)度方法，用于在共軌上使用多臺堆垛起重機(jī)的AS / RS。問題包括為每臺起重機(jī)分配訂單以及在沒有碰撞的情況下安排起重機(jī)。 Brezovnik等人[21]采用多目標(biāo)蟻群優(yōu)化方法處理AS / RS中的存儲分配問題。根據(jù)從家電設(shè)備倉庫獲得的計算結(jié)果，顯示當(dāng)重量和身高較低的產(chǎn)品存儲在較高級別時，可以實現(xiàn)最佳空間利用率。楊等人。 [22]推斷S / R機(jī)器的速度曲線對多深度AS / RS的最佳存儲機(jī)架有重要影響。 Atmaca和Ozturk [4]提出了一種用于存儲分配和存儲分配問題的數(shù)學(xué)規(guī)劃模型和模擬退火方法，以最大限度地降低存儲成本。通過提出的數(shù)學(xué)模型獲得了最多103種材料問題的最優(yōu)解。 Dooly和Lee [23]將雙梭AS / RS的基于移位的測序問題建模為最小成本完美匹配問題，并提出了多項式時間精確算法。 Oliveira [5]和Figueiredo等人。[6]將AS / RS倉庫中的卡車裝載作業(yè)模擬為帶再循環(huán)的作業(yè)車間調(diào)度問題（JSP）[5]。奧利維拉[5]假定運(yùn)輸托盤的處理時間相同，而不依賴于過道和卡車的位置。 Figueiredo等人[6]通過考慮不同的處理時間來擴(kuò)展該問題，并通過具有隨機(jī)密鑰表示的遺傳算法來解決該問題。 Oliveira [5]和Figueiredo等人[ [6]認(rèn)為托盤可以從以前由WMS決定的一個通道檢索，考慮到靠近?？繛场Ｔ谶@項研究中，這個假設(shè)通過考慮托盤的替代通道來擴(kuò)展。卡車裝載調(diào)度同時確定托盤取回過道的選擇。因此，問題包括選擇通道來檢索托盤（目前由WMS執(zhí)行），以及托盤從收集器到卡車的運(yùn)輸安排。通過這種方式，結(jié)合這兩種操作的好處被調(diào)查。在本研究的范圍內(nèi)沒有發(fā)現(xiàn)將這個問題作為FJSP的研究。 4.將AS / RS倉庫建模為FJSP 在本節(jié)中，介紹了用于整車運(yùn)行調(diào)度問題的MIP公式。我們不考慮交叉對接或訂單揀選生產(chǎn)托盤。本研究考慮的假設(shè)如下： ?訂單僅由存儲在倉庫中的（完整）托盤產(chǎn)品組成。 ?S / R機(jī)器比叉車更快地將托盤放在收集器上，以卸下托盤并且S / R機(jī)器在叉車之前運(yùn)行， ?收集器作為一個緩沖器，可以處理多個托盤， ?收集器（重力滾筒輸送機(jī)）中托盤的流量遵循FIFO規(guī)則， ?S / R機(jī)器需要零時間將托盤放入收集器中。 表2給出了后面使用的表示法。整車運(yùn)行調(diào)度的MIP公式如下： 表2 MIP的表示法 （1） 0中給出了目標(biāo)函數(shù)，以使批次的總加載時間最小化。約束條件（2）保證每個托盤僅由一臺叉車運(yùn)輸。約束條件（3）確保如果托盤未分配給叉車，則該叉車托盤的運(yùn)輸開始和結(jié)束時間為零。如果在叉車k上分配，則約束條件（4）保證該托盤的運(yùn)輸完成時間不能小于其起始時間和運(yùn)輸時間之和。約束條件（5）和（6）滿足叉車在將當(dāng)前托盤運(yùn)送到相應(yīng)的叉車之前不能開始運(yùn)送下一個托盤。在（7）中給出了每個載荷的優(yōu)先約束，這確保了在相同載荷的前一個托盤的運(yùn)輸完成之前不能運(yùn)載載荷的托盤。約束條件（8）和（9）分別給出了每個負(fù)載和批次的完成時間。約束（10） - （14）表示決策變量的二元約束和符號限制。 由（1） - （14）給出的模型是?zgüven等人提出的模型的調(diào)整版本。 [24] FJSP。這個問題可以被歸類為FJSP，其中貨物被認(rèn)為是工作，貨物的貨盤被認(rèn)為是工作的操作，并且用于將檢索物品移除到貨車的叉車被視為機(jī)器。最小化完工時間（運(yùn)輸時間）是目標(biāo)，因為這樣可以最大限度地減少訂單的吞吐時間并最大化倉庫效率。 在FJSP中，不能同時在機(jī)器上處理多個操作。此外，對于滿足托盤優(yōu)先關(guān)系的所有工作，都存在技術(shù)限制。在倉庫中，叉車只能像FJSP中的機(jī)器一樣在一定時間只運(yùn)載一個托盤。同樣，對于每個應(yīng)該保證的負(fù)載，都有一個接收訂單托盤。在前一個之前沒有裝載palletcan。換句話說，不允許重疊相同載荷的貨盤的運(yùn)輸。每個負(fù)載的托盤順序可以作為技術(shù)限制來考慮。 在倉庫中，裝載可以同時實現(xiàn)，并應(yīng)在由WPS確定的時間窗內(nèi)結(jié)束。所有負(fù)荷應(yīng)盡快結(jié)束以方便裝入下列批次。在加載當(dāng)前批次的所有裝載之前，無法啟動新批次的準(zhǔn)備。盡快終止批量加載并減少碼頭占用是通過縮短完工時間來實現(xiàn)的。 表3一個真正問題的例子 下面的例子是以前的例子的擴(kuò)展?，F(xiàn)在有些托盤可以從兩個通道中取出，而前一個托盤和一個處理時間更長的新替代物。每個托盤的替代通道和處理時間在表3中給出。例如，第二個負(fù)載的第一個托盤可以從處理時間2的第二個通道或第一個時間的第三個通道中獲取。 當(dāng)所有托盤從處理時間最短的通道中取出時，可獲得一個可行的時間表，如圖3（a）所示，即圖2（a）所示的相同解決方案。讓我們分配走道2，即使它的處理時間比負(fù)載2的第三個托盤的走道3和負(fù)載2的第四個托盤的走道1的處理時間更長。此分配的最佳時間表如圖3（b）所示。盡管將兩個托盤分配到較大的處理時間，但是就批次的完成時間而言獲得了更好的時間表。 5.方法 FJSP是一個NP難題，因為更簡單的問題是JSP，在強(qiáng)烈意義上是NP難的問題[25]。因此，在合理的時間內(nèi)不可能用精確的解決方案獲得最佳的解決方案。已經(jīng)開發(fā)了各種近似算法來獲得大尺寸調(diào)度實例的良好結(jié)果[26]。遺傳算法（GAs）[27-33]，粒子群優(yōu)化算法[34,35]，蟻群算法[36,37]，模擬退火算法[38]，變鄰域搜索算法[39,40]和禁忌搜索算法[ 42]已被用于最小化文獻(xiàn)中FJSP的完工時間。在這項研究中，Cinar等人為FJSP開發(fā)了一個基于優(yōu)先級的GA。 [27]用于解決整車運(yùn)行調(diào)度問題。 5.1 表象 染色體的每個基因代表用于解碼的構(gòu)造性算法的操作的優(yōu)先級。置換代碼被選擇來引用優(yōu)先值。在這項研究中，每個染色體中的基因數(shù)量等于相應(yīng)替代機(jī)器處理的可能操作數(shù)量。圖4說明了圖3（b）給出的時間表的樣本染色體。較高的優(yōu)先值意味著在施工過程中安排較高的優(yōu)先級，這將在下一小節(jié)中解釋。例如，負(fù)載1的第一個托盤的優(yōu)先級在A1上是18，在A3上是14。如果在建構(gòu)性算法的迭代中在這些替代方案之間進(jìn)行選擇是必要的，則將選擇A1，因為它具有更高的優(yōu)先級。 5.2 解碼 解決方案由Chang和Sullivan [43]開發(fā)的構(gòu)造算法進(jìn)行解碼，該算法可以為FJSP生成所有有效的時間表[27]?；顒訒r間表構(gòu)成可行時間表的一個子集，包括最佳時間表。 構(gòu)造性算法僅根據(jù)染色體上的信息生成時間表。通過這種方式，可以保證最佳的解決方案包含在搜索空間中，不可能生成不可行或不可行的解決方案。另一方面，編碼和解空間之間發(fā)生n對1的關(guān)系。換句話說，多于一個染色體可以代表相同的時間表[27]。 圖3.說明性示例的示例時間表 圖4.說明性例子的樣本染色體。 5.3.Genetic操作符 精英規(guī)則和輪盤賭被用作選擇操作員的方法。應(yīng)用兩個交叉操作符：循環(huán)交叉（CX）和基于作業(yè)的交換（JOX）。 CX是用于排列編碼問題的通用算子。絕對基因位置是從父母遺傳到后代。 JOX是由[44]開發(fā)的基于問題的交叉操作符，用于JSP以滿足幾代人繼承工作順序的需求。基于優(yōu)先級的置換編碼可以輕松實現(xiàn)JOX，并且不需要任何修復(fù)機(jī)制。 應(yīng)用機(jī)器變異和序列變異來重新分配操作，移植變異用于全局搜索。機(jī)器突變是為了替代機(jī)器（貨架/叉車）上的操作（貨盤）而開發(fā)的。它使用基于關(guān)鍵路徑的鄰域結(jié)構(gòu)。由于不屬于關(guān)鍵路徑的操作的重新分配不會改變完工時間，因此從關(guān)鍵路徑中隨機(jī)地選擇操作以進(jìn)行重新分配。從替代機(jī)器中隨機(jī)選擇一臺機(jī)器，并將操作安排到隨機(jī)位置。 為了增強(qiáng)鄰域搜索，開發(fā)了一種基于塊結(jié)構(gòu)的序列變異來重定位當(dāng)前機(jī)器上的操作。從關(guān)鍵路徑中隨機(jī)選擇一項操作。它在相應(yīng)塊的所有操作之前或之后重新安排。 遷移是一種全局搜索的變異算子，通過在每一代中隨機(jī)產(chǎn)生一個染色體來替代至少一個染色體，從而增強(qiáng)基因庫中的多樣性。在遺傳算法的每次迭代中，確定具有相同財富價值的個體，并將移民程序應(yīng)用于他們。通過這種方式，減少了n對1映射的限制。 5.4 基于優(yōu)先級的遺傳算法 最初的人口是隨機(jī)產(chǎn)生的。建構(gòu)性算法用于評估個體。在每次迭代開始時，執(zhí)行移民程序以減少當(dāng)前人群中具有相同財富價值的人數(shù)。包括父母在內(nèi)的交配池由選擇構(gòu)建。交配池的2％由精英規(guī)則選擇，并由輪盤選擇。交叉操作符用于生成后代。如果選擇兩個父母進(jìn)行交叉，則每個交叉運(yùn)算符（CX，JOX）有50％的機(jī)會被應(yīng)用。在交叉過程終止后，將變換運(yùn)算符應(yīng)用于生成的個體。就像在交叉過程中一樣，如果個體會發(fā)生變異，每個突變算子（機(jī)器，序列）有50％的概率。在遺傳算法的每個重現(xiàn)過程結(jié)束時，迭代局部搜索（ILS）被應(yīng)用于群體中具有最佳適應(yīng)度值的小量染色體。 ILS用于搜索更好的解決方案。由于計算量很大，因此只適用于少數(shù)人。下一代通過成對比較來確定，其中每個種群中的一個個體（當(dāng)前和由遺傳操作者產(chǎn)生的）在適應(yīng)值方面進(jìn)行比較。更好的一個被轉(zhuǎn)移到下一代。 GA的迭代一直持續(xù)到達(dá)到最大代數(shù)?；趦?yōu)先級的GA的流程圖在圖5中給出。 表4從BC數(shù)據(jù)集avRD獲得的平均相對偏差 6.計算結(jié)果 Cinar等人[27]將基于優(yōu)先級的遺傳算法與文獻(xiàn)中為FJSP開發(fā)的其他算法進(jìn)行了比較?；趦?yōu)先級的遺傳算法得到的結(jié)果與文獻(xiàn)中的算法和給出基于優(yōu)先級的遺傳算法獲得的改進(jìn)百分比的相對偏差進(jìn)行了比較。 Cinar等人獲得的結(jié)果。 [27]總結(jié)在表4和表5中。表4和5包括Chambers和Barnes [45]（BC數(shù)據(jù)集）和Hurink等人生成的實例的平均相對偏差（avRD）。 （HU數(shù)據(jù)集）。表格的第一列和第二列表示每個實例的作業(yè)數(shù)量和機(jī)器數(shù)量。第三列給出了相應(yīng)數(shù)據(jù)集中具有指定大小的實例的數(shù)量。例如，在BC數(shù)據(jù)集中有兩個實例有10個作業(yè)和11個機(jī)器（表4）?；趦?yōu)先級的GA與Mastrolilli和Gambardella [47]和Gao等人的結(jié)果進(jìn)行了比較。對于BC實例，以avRD（表4的最后兩列）以及Behnke和Geiger [49]對于HU實例（表5的最后一列）來表示。根據(jù)這些結(jié)果，基于優(yōu)先級的遺傳算法是一種有效的算法，相對于平均遺傳算法為FJSP獲得接近最優(yōu)的結(jié)果[27]。因此，在本研究范圍內(nèi)，選擇基于優(yōu)先級的遺傳算法來解決AS / RS中卡車負(fù)荷運(yùn)行的調(diào)度問題。 表5從HU數(shù)據(jù)集中獲得的平均相對偏差。 圖5.基于優(yōu)先級的GA。 Oliveira [5]使用代表性的相關(guān)AS / RS問題實例和JPS文獻(xiàn)中的測試實例進(jìn)行計算機(jī)實驗。真正問題的代表性實例是隨機(jī)生成的，代表一個JSP進(jìn)行再循環(huán)。這些實例的維度與實際問題的定義的最大維度相同。 Figueiredo等人[6]為相同的真實問題生成隨機(jī)實例。我們使用Figueiredo等人提出的實際問題的相同代表性實例。 [6]通過為一些貨物托盤添加替代通道。 表6 Figueiredo等人使用的操作分布[6] 卡車的裝載（作業(yè)）由35個托盤（作業(yè)）組成，這些托盤來自靠近?？空镜?個走道（機(jī)器）。 Figueiredo等人[6]根據(jù)表6中定義的分布確定了存放35個托盤的一個貨物的通道。例如，貨物5以相等的概率存儲在5個通道（通道2-6）之一中，即20/100 = 0.5。在這項研究中，一個程序可以將JSP的實例轉(zhuǎn)換為Figueiredo等人生成的再循環(huán)。 [6] FJSP實例和基于優(yōu)先級的GA在Microsoft Visual C ++ V7.0中編碼。為每個貨物隨機(jī)選擇的托盤添加一個替代通道。替代通道和相應(yīng)卡車之間的處理時間大于JSP數(shù)據(jù)和卡車中確定的通道之間的時間。通過這種方式，研究了將檢索序列建模為FJSP的好處。 每個實例都有兩種不同的人口規(guī)模：20人中的小人口和100人中的大一人。突變和交叉概率都被確定為0.5。計算結(jié)果在表7中給出。第一列至第四列代表實例名稱，人口規(guī)模（彈出大小），裝載/作業(yè)數(shù)量（n）以及托盤/操作總數(shù)（操作）。第五和第六列表示菲格雷多等人15次獲得的最佳平均完工時間。 [6]。第七和第八列表示通過基于優(yōu)先級的GA獲得的15次運(yùn)行的最佳平均完工時間。第九列給出了獲得最小值的實驗數(shù)量，而第十列表示15次運(yùn)行中的有價值的標(biāo)準(zhǔn)偏差。第十一列代表平均CPU時間。對每個實驗執(zhí)行500次迭代。 根據(jù)計算結(jié)果，包括靈活性會給出更好的結(jié)果，特別是對于那些有大量工作的實例。擬議的GA發(fā)現(xiàn)FJSP數(shù)據(jù)集的結(jié)果比JSP數(shù)據(jù)的結(jié)果更好或相同。因此可以得出結(jié)論，檢索排序問題可以更好地模擬為FJSP。 圖6顯示了人口規(guī)模為20和100的最大實例（jr 13 2）在整個迭代過程中的最佳適應(yīng)值。雖然大型實例需要額外的CPU時間，但更大的群體規(guī)?？梢垣@得更好的解決方案。人口規(guī)模為100和32.7秒需要164.8秒，實例“jr 13 2”的人口規(guī)模為20。該算法還可以在更大的人口規(guī)模下更加穩(wěn)健地執(zhí)行 表7計算結(jié)果 圖6.適合度評估 7.總結(jié) 在這項研究中，在AS / RS中出現(xiàn)的卡車裝載操作的調(diào)度被模擬為FJSP?；趦?yōu)先級的GA應(yīng)用于真正的AS / RS倉庫，以對檢索到的托盤進(jìn)行排序。 Figueiredo等人生成的數(shù)據(jù)集[6]對于同一個倉庫，通過為某些操作添加替代機(jī)器進(jìn)行擴(kuò)展。通過這種方式，研究了通道選擇靈活性的影響。生成的數(shù)據(jù)集的維度與真正的問題相同。在倉庫每日問題的便利計算時間內(nèi)找到合理的解決方案。證明了所提出的基于優(yōu)先級的遺傳算法可以用來解決倉庫中現(xiàn)實生活中的檢索排序問題。在用來說明FJSP優(yōu)勢的一組實例中，我們只考慮一個額外的過道來檢索托盤。使用額外的過道具有更長的處理時間，這是我們做出的一個保守的選擇，并且在真正的問題中，它可能具有相同的甚至更低的處理時間。盡管如此，如果方便的話，使用更長的處理時間會導(dǎo)致更低的完工時間，從而提高處理速度 倉庫的有效性。對于具有相似實際問題大小的實例集，F(xiàn)JSP模型平均可以獲得高達(dá)11％的增益和7％左右的增益。很明顯，如果我們考慮使用不止一個替代通道來檢索托盤，這些收益會更大。 提高吞吐率，在更短的時間內(nèi)為客戶服務(wù)，并減少卡車和司機(jī)裝貨的等待時間，這些結(jié)果是其他管理方面的好處。如今，為了增加倉庫的吞吐量，倉庫建立了更多的過道，在卡車到達(dá)之前準(zhǔn)備了多個緩沖區(qū)以準(zhǔn)備貨物，在通道開始時有多達(dá)3個收集器以及更多數(shù)量的托盤，從而導(dǎo)致更多昂貴的項目。從JSP運(yùn)營模式向FSJP運(yùn)營模式的轉(zhuǎn)變只需要WMS升級，短期內(nèi)將全面回放，避免大量投資增加倉儲容量。 在這項研究中，通道和卡車之間的運(yùn)輸時間假定在整個裝載過程中固定。在進(jìn)一步的研究中，這個假設(shè)可以擴(kuò)展到使問題更加真實。此外，產(chǎn)品的惡化會對生產(chǎn)過程產(chǎn)生負(fù)面影響[50,51]，因此可以考慮安排倉庫中的托盤。 致謝 這項研究得到了LATNA實驗室，NRU HSE，RF政府資助，ag的部分支持。 11.G34.31.0057。 Contents lists available at ScienceDirect Applied Soft Computing j ournal homepage: www.elsevier.com/locate/asoc Applied Soft Computing 52 (2017) 566–574 Scheduling the truckload operations in automated warehouses with alternative aisles for pallets Didem Cinara,b,?, José António Oliveirac, Y. Ilker Topcua, Panos M. Pardalosb a Department of Industrial Engineering, Faculty of Management, Istanbul Technical University, Istanbul, Turkey b Department of Industrial and Systems Engineering, Faculty of Engineering, University of Florida, Gainesville, United States c ALGORITMI Research Centre, University of Minho, Braga, Portugal a r t i c l e i n f o a b s t r a c t Article history: Received 5 June 2015 Received in revised form 27 June 2016 Accepted 13 October 2016 Available online 19 October 2016 Keywords: Automated storage and retrieval systems Truckload operations scheduling Flexible job shop scheduling Genetic algorithms In this study, the scheduling of truck load operations in automated storage and retrieval systems is investigated. The problem is an extension of previous ones such that a pallet can be retrieved from a set of alternative aisles. It is modelled as a ?exible job shop scheduling problem where the loads are considered as jobs, the pallets of a load are regarded as the operations, and the forklifts used to remove the retrieving items to the trucks are seen as machines. Minimization of maximum loading time is used as the objective to minimize the throughput time of orders and maximize the ef?ciency of the warehouse. A priority based genetic algorithm is presented to sequence the retrieving pallets. Permutation coding is used for encoding and a constructive algorithm generating active schedules for ?exible job shop scheduling problem is applied for decoding. The proposed methodology is applied to a real problem arising in a warehouse installed by a leading supplier of automated materials handling and storage systems. ? 2016 Elsevier B.V. All rights reserved. 1. Introduction Automated storage and retrieval system (AS/RS) is a warehous- ing system that uses mechanic devices for the storage and retrieval of products in both distribution and production environments [1,2]. Automatic cranes move through aisles between racks to put the items on the racks and retrieve those items from storage to the col- lector for ful?lling the customer orders. AS/RS is fully automated, because no intervention of an operator is needed for handling the pallets [2]. When an order is received for an item, a stacker crane retrieves the pallet from its storage location and carries it to the col- lector at the top of the aisle that is a gravity roller conveyor. At the end of the roller conveyor, the conveyed pallet is picked up using a forklift truck. High space utilization, improved material ?ow, and improved inventory control are some of the advantages of AS/RS [3]. The best utilization from such a system can be succeed by optimal design and optimal scheduling of the system. Warehouse scheduling optimization is a combinatorial opti- mization problem which cannot be solved with exact algorithms in reasonable computational time for high dimensional instances. ? Corresponding author at: Department of Industrial Engineering, Faculty of Man- agement, Istanbul Technical University, Istanbul, Turkey. E-mail addresses: cinard@itu.edu.tr (D. Cinar), zan@dps.uminho.pt (J.A. Oliveira), topcuil@itu.edu.tr (Y. Ilker Topcu), pardalos@u?.edu (P.M. Pardalos).  Because of the high complexity of the problem, simulation and metaheuristics have been widely used in warehouse scheduling optimization [4]. A detailed literature review about the method- ologies developed for AS/RS design and scheduling is given in Section 3. In this study, the scheduling of truck load operations arising in AS/RS is investigated. The problem is modelled as a ?exible job shop scheduling problem (FJSP) by considering the loads as jobs and pallets of a load as its operations. The forklifts which are used for transportation of pallets from collectors to trucks are considered as machines. The main contributions of this paper are twofold: (1) scheduling of truck load operations is modelled as a ?exible job shop scheduling problem, (2) a real problem arising in an AS/RS warehouse installed by a leading supplier of automated materials handling and storage systems is solved by using a priority based genetic algorithm and the effect of aisle selection ?exibility is inves- tigated. To the best of the authors’ knowledge, this work is the ?rst time that the FSJP is used to model the retrieving operation of pallets in an AS/RS warehouse. The paper is organized as follows. Section 2 provides a brief explanation on investigated automated storage system. In Sec- tion 3, a literature review on scheduling of truck load operations is given. Section 4 represents a mixed integer programming (MIP) formulation for a truckload operations scheduling problem in AS/RS and discusses the modelling of the problem as a ?exible job shop scheduling problem. Section 5 presents the devoted methodology. http://dx.doi.org/10.1016/j.asoc.2016.10.013 1568-4946/? 2016 Elsevier B.V. All rights reserved. D. Cinar et al. / Applied Soft Computing 52 (2017) 566–574 567 Fig. 1. Schema of the warehouse. Section 6 gives the computational results for a real life AS/RS ware- house problem. Finally, Section 7 presents the conclusion. 2. Storage system The methodology proposed in this study is applied to an AS/RS warehouse in Italy which works as a distribution center. Products are stored by the warehouse and loaded to the trucks to ful?ll the orders of customers. Routes of the trucks, which are known in advance, are determined considering the delivery deadline of cus- tomer orders. The warehouse consists of eleven aisles constituted by pallet racks with the capacity of 40,000 pallets. An automatic stacker crane or S/R machine works in each aisle to move the pallets from their respective rack to the collector at the beginning of the aisle. Forklifts transport the pallets to the trucks. The warehouse has 13 docking bays to load the trucks. A scheme of the loading process in this warehouse is shown in Fig. 1. Warehouse Planning System (WPS) and Warehouse Manage- ment System (WMS) are used to operate the warehouse. Daily planning of loadings for each truck is executed by WPS. The sequence of retrieving pallets and the movement of S/R machines and forklifts are determined by WMS. Approximately one hun- dred loads are retrieved per day by a truck. Each truck has its own delivery time which is considered by WPS and loading must not be delayed. In the strategy de?ned for the WPS, the whole set of loads are divided into subsets called batches. Loads in a batch are processed simultaneously. Loading of a batch cannot be started before the loads of previous batch are ?nished. The size of a batch is determined with respect to delivery deadlines and the number of docking bays. A standard daily plan includes 15–20 batches with 6–13 loads for each one. An order of a customer consists a product or a set of products that are delivered on one or more pallets. The set of products for an order is known in advance, and it is available in the warehouse. A truck load consists of a set of pallets transported for one or more clients. The sequence of loading pallets on the truck is determined by WMS with LIFO (Last In First Out) rule. Since the sequence of pallets in a load is predetermined and cannot be changed, precedence relations exist between pallets of a load. The pallets of a load can be retrieved from any aisle. To facilitate the assignment of the trucks to the docking bays, several pallets are placed in different aisles to reduce the time of load prepara- tion, allowing a pallet to be selected in an aisle that is close to the truck and respecting the FEFO (First-Expired-First-Out) rule. The S/R machine is programmed to retrieve the pallets from the corresponding aisle. We assume that each forklift can work for only one aisle. After a forklift receives a pallet from its own aisle, it can carry the pallet to any truck. For safety reasons, more than one forklift cannot be allowed to place pallets in a truck at the same time. So, one load should receive one pallet at a certain time. After a pallet is loaded to the truck, the forklift returns to its aisle and communicates to WMS that it is available for a new transportation. Then the next pallet for the same load is programmed. A forklift can receive only one pallet at each transportation. Detailed information about the analysed AS/RS warehouse can be obtained from [5]. Different sequences of pallets in a batch retrieved by S/R machines result in different processing times. An illustrative exam- ple is the following. Assume that there are 5 aisles in the warehouse represented by A1, A2, . . ., A5. The problem is planning the retriev- ing sequence of a batch including 3 loads. Each load consists of 4 pallets, which have precedence relations in advance, representing a total of 12 pallets to be retrieved in the batch. There is one forklift for each aisle to carry the pallets from the aisle to the correspond- ing truck. Although a pallet can be retrieved from several aisles, in previous studies [5,6] it was assumed that it is the WMS that previ- ously selects the pallets considering the distance to the aisle where the load is prepared. The aisle for each pallet and the processing times are given in Table 1. The aisle storing pallet j and the transportation time between related aisle and truck are shown as (Ak, t) where Ak refers the kth aisle and t is the transportation time from aisle Ak to truck. For example, the ?rst pallet of the second load must be retrieved Table 1 An illustrative example for real problem. jth pallet Load i 1 2 3 4 1 (A1 ,1) (A2 ,2) (A3 ,3) (A4 ,4) 2 (A3 ,1) (A1 ,3) (A3 ,1) (A4 ,2) 3 (A4 ,2) (A4 ,2) (A3 ,3) (A5 ,1) 568 D. Cinar et al. / Applied Soft Computing 52 (2017) 566–574 Fig. 2. Two different schedules for retrieving the pallets. from the third aisle with time 1. For convenience, the pallets were consecutively numbered from 1 to 12. Fig. 2 shows two different sequences of retrieving pallets. The numbers inside the rectangles identify the pallets. For each sequence, Fig. 2 presents the Gantt chart for the set of aisles (left side) and the Gantt chart for the set of loads (right side), which represents better the processing time of the batch. The sequences for retrieving pallets only differ at Aisle 3, where the pallet 11 is collected either after pallets 3 and 7 (Fig. 2(a)), or before pallets 3 and 7 (Fig. 2(b)). The decision when to retrieve pallet 11 produces signi?cantly different processing times for the entire batch of loads. Fig. 2(a) presents the optimal solution for this small example. 3. Literature review In an AS/RS, planning and performing of accurate loading pro- cesses are very important to meet the customer orders at the proper time [5]. Among previous studies, analysis oriented ones constituted the majority of the literature rather than those devel- oping models and techniques for warehouse design [7]. Simple heuristics and simulation techniques were used for storage and retrieval problems in automated warehousing systems. Bozer and White [8] proposed travel time models for automated S/R machines with single and dual command mode. Han et al. [9] proposed a nearest neighbour heuristic for retrieval sequencing in AS/RS with dual command cycles and used Monte Carlo simulation for eval- uation. Eben-Chaime [10] also used a nearest neighbour heuristic to sequence the retrievals. Hausman et al. [3] compared several storage assignment rules to determine the optimal storage assign- ment policy. Schwarz et al. [11] analysed both storage assignment and interleaving rules with a simulation model. Lee and Schae- fer [12] formulated the problem, which is also handled by Han et al. [9], as an assignment problem. They proposed a methodology combining the Hungarian method and the ranking algorithm for the assignment problem with the tour-checking and tour-breaking algorithms. In the last few years, besides the mathematical modeling and simulation approaches, metaheuristics have been used in these areas. Comprehensive reviews of warehouse design and control can be found in de Koster et al. [13], Gu et al. [14] and Baker and Canessa [15]. Moreover, detailed explanations of the current state of the art in AS/RS design are provided by Roodbergen and Vis [2] and Vasili et al. [16]. Manzini et al. [17] developed a multi-parametric dynamic model for a product-to-picker storage system with class- based storage allocation of products. They investigated the factors affecting the warehousing system performance. Yin and Rau [18] combined simulation and genetic algorithms for the dynamic selec- tion of sequencing rules for a class-based unit-load AS/RS. Chang et al. [19] proposed a multi-objective mathematical programming model and a genetic algorithm for the order picking of stacker cranes. Kung et al. [20] developed a dynamic programming based order scheduling methodology for the AS/RS with multiple stacker cranes on a common rail. The problem includes both assignment of orders to each crane and scheduling of cranes without collision. Brezovnik et al. [21] used a multi-objective ant colony optimization method for the storage allocation problem in an AS/RS. Based on the computational results obtained from a home appliance devices warehouse, it was shown that optimal space utilization can be achieved when the products with lower weight and height are stored at higher levels. Yang et al. [22] inferred that the speed pro?le of an S/R machine has an important effect on the optimal stor- age rack for a multi-deep AS/RS. Atmaca and Ozturk [4] proposed a mathematical programming model and a simulated annealing approach for the storage allocation and storage assignment prob- lems to minimize storage costs. Optimal solution was obtained by the proposed mathematical model for problems having up to 103 materials. Dooly and Lee [23] modelled a shift-based sequencing problem for twin-shuttle AS/RS as a minimum-cost perfect match- ing problem and presented a polynomial-time exact algorithm. Oliveira [5] and Figueiredo et al. [6] modelled the truck load operations on an AS/RS warehouse as a job shop scheduling prob- lem (JSP) with recirculation [5]. Oliveira [5] assumed identical processing times to transport pallets independently of the location D. Cinar et al. / Applied Soft Computing 52 (2017) 566–574 569 of the aisle and the truck. Figueiredo et al. [6] extended the problem by considering different processing times and solved it by genetic algorithms with random keys representation. Both Oliveira [5] and Figueiredo et al. [6] assumed that a pallet can be retrieved from one aisle previously decided by WMS, considering the proximity to the docking bay. In this study, this assumption is extended by consid- ering alternative aisles for pallets. The selection of the aisle where the pallets are retrieved is determined with truck load scheduling simultaneously. So the problem consists of both selection of an aisle to retrieve the pallet, which is currently performed by WMS, and the scheduling of pallets’ transportation from collector to truck. In this way, the bene?t of combining these two operations is inves- tigated. No study which addresses this problem as a FJSP has been encountered in the scope of this study. 4. Modelling AS/RS warehouses as FJSP In this section, a MIP formulation for the truckload operation scheduling problem is presented. We do not consider cross-docking or order picking to produce a pallet. The assumptions considered in this study are given as follows: ? an order is formed by only (complete) pallets of products that are stored in the warehouse. ? an S/R machine is faster to put a pallet on the collector than a forklift to remove a pallet and an S/R machine operates in advance of the forklift, ? a collector works as a buffer with capacity for several pallets, ? the ?ow of pallets in the collector (gravity roller conveyor) follows the FIFO rule, ? an S/R machine takes zero units of time to put a pallet in the collector. The notation used hereafter is given in Table 2. The MIP formu- lation for truckload operations scheduling is given as follows: min Cb (1) subject to 「Xijk = 1 ?i ∈ L, ?j ∈ Pi (2) k ∈ Fij Sijk + Cijk ≤ MXijk ?i ∈ L, ?j ∈ Pi, ?k ∈ Fij (3) Cijk ≥ Sijk + tijk ? M(1 ? Xijk) ?i ∈ L, ?j ∈ Pi, ?k ∈ Fij (4) Sijk ≥ Ci1 j1 k ? MYiji1 j1 k ?i < i1 , ?j ∈ Pi, ?j1 ∈ Pi1 , ?k ∈ Fij ∩ Fi1 j1 (5) Si1 j1 k ≥ Cijk ? M （1 ? Yiji1 j1 k） ?i < i1 , ?j ∈ Pi, ?j1 ∈ Pi1 , ?k ∈ Fij ∩ Fi1 j1 (6)  Table 2 Notation for MIP. Indices: i loads (i, i1 ∈ L) j pallets (j, j1 ∈ P) k forklifts (k ∈ F ) Sets: L set of loads P set of pallets F set of forklifts Pi ordered set of pallets of load i (Pi ? P) Pil(i) the last pallet of Pi Fij set of alternative forklifts on which pallet Pij can be transported （Fij ? F ） Decision variables: Binary variables Xijk 1 if forklift k is selected for pallet Pij , 0 otherwise Yiji1 j1 k 1 if pallet Pij is transported (not necessarily immediately) before pallet Pi1 j1 on forklift k, 0 otherwise Continuous variables Sijk starting time of the transportation of pallet Pij on forklift k Cijk completion time of the transportation of pallet Pij on forklift k Ci completion time of load i Cb completion time of whole batch Parameters: tijk transportation time of pallet Pij on forklift k M a large number Objective function is given in (1) as minimizing the total load- ing time of the batch. Constraints (2) guarantee that each pallet is transported by only one forklift. Constraints (3) ensure that if a pallet is not assigned to a forklift, then the starting and completion time of the transportation for the pallet on that forklift is zero. If it is assigned on forklift k, constraints (4) guarantee that the completion time of the transportation for that pallet cannot be smaller than the sum of its starting time and transportation time. Constraints (5) and (6) satisfy that a forklift cannot start to carry the next pal- let until it delivers its current pallet to the corresponding forklift. Precedence constraints for each load are given in (7) which ensure that a pallet of a load cannot be carried before the transportation of the preceding pallet of the same load is ?nished. Constraints (8) and (9) give the completion time for each load and batch, respec- tively. Constraints (10)–(14) represent the binary constraints and sign restrictions for decision variables. The model given by (1)–(14) is an adjusted version of the one proposed by ?zgüven et al. [24] for FJSP. This problem can be mod- elled as a FJSP in which the loads are considered as jobs, the pallets of a load are regarded as the operations of jobs, and the forklifts used to remove the retrieving items to the trucks are seen as machines. 「 Si,j 1,k ≥ 「Ci,j,k ?i ∈ L, ?j ∈ P ? {P 1 (7) k ∈ Fi,j+1 + Ci ≥ 「Ci,P ,k k ∈ Fij ?i ∈ L (8) Cb ≥ Ci ?i ∈ L (9) Xijk ∈ {0, 11 ? i ∈ L, ?j ∈ Pi, ?k ∈ Fij (10) il(i)  k ∈ Fij i il(i) Minimization of the makespan (transportation time) is the objec- tive, as this allows minimization of the throughput time of orders and maximization of the ef?ciency of the warehouse. In FJSP, more than one operations cannot be processed on a machine at the same time. Moreover, there are technological con- straints for all jobs which satisfy the precedence relations bet