自動化外文文獻翻譯-在帶貨盤替代通道的自動化倉庫中安排整車運作【中文8400字】 【PDF+中文WORD】

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