自動(dòng)化外文文獻(xiàn)翻譯-在帶貨盤替代通道的自動(dòng)化倉(cāng)庫(kù)中安排整車運(yùn)作【中文8400字】 【PDF+中文WORD】

自動(dòng)化外文文獻(xiàn)翻譯-在帶貨盤替代通道的自動(dòng)化倉(cāng)庫(kù)中安排整車運(yùn)作【中文8400字】 【PDF+中文WORD】,中文8400字,PDF+中文WORD,自動(dòng)化外文文獻(xiàn)翻譯-在帶貨盤替代通道的自動(dòng)化倉(cāng)庫(kù)中安排整車運(yùn)作【中文8400字】,【PDF+中文WORD】,自動(dòng)化,外文,文獻(xiàn),翻譯,帶貨盤,替代,通道,倉(cāng)庫(kù),安排 【中文8400字】 在帶貨盤替代通道的自動(dòng)化倉(cāng)庫(kù)中安排整車運(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)中卡車裝載操作的調(diào)度。旨在于以前的出現(xiàn)問(wèn)題的擴(kuò)展，例如托盤可以從一組替代通道中取出。它被模擬為靈活的作業(yè)車間調(diào)度問(wèn)題，其中負(fù)載被視為工作，負(fù)載的托盤被視為操作，并且用于將檢索物品移除到卡車上的叉車被視為機(jī)器。最大限度縮短裝載時(shí)間是為了盡量減少訂單的吞吐時(shí)間，并最大限度地提高倉(cāng)庫(kù)的效率。提出了基于優(yōu)先級(jí)的遺傳算法來(lái)對(duì)檢索托盤進(jìn)行排序。置換編碼被用于編碼，并且生成用于靈活作業(yè)車間調(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è)備在分銷和生產(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不需要操作托盤[2]。當(dāng)收到一件物品的訂單時(shí)，堆垛起重機(jī)將托盤從其存放位置取回，并將其運(yùn)送到重力滾筒輸送機(jī)通道頂部的收集器。在滾筒輸送機(jī)的末端，使用叉車拾取所輸送的貨盤。 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ā)生的卡車裝載操作的調(diào)度。通過(guò)將負(fù)載視為作業(yè)的作業(yè)和托盤作為其操作，該問(wèn)題被模擬為靈活的作業(yè)車間調(diào)度問(wèn)題（FJSP）。用于從收集器到卡車運(yùn)輸托盤的叉車被視為機(jī)器。本文的主要貢獻(xiàn)有兩個(gè)：（1）卡車裝載作業(yè)的調(diào)度被模擬為靈活的作業(yè)車間調(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ù)中托盤的檢索操作。 本文的結(jié)構(gòu)如下，第2節(jié)對(duì)調(diào)查的自動(dòng)化存儲(chǔ)系統(tǒng)進(jìn)行了簡(jiǎn)要說(shuō)明。在第3節(jié)中，給出了關(guān)于卡車裝載作業(yè)調(diào)度的文獻(xiàn)回顧。第4節(jié)表示AS / RS中的整車運(yùn)行調(diào)度問(wèn)題的混合整數(shù)規(guī)劃（MIP）公式，并討論將該問(wèn)題建模為靈活的作業(yè)車間調(diào)度問(wèn)題。第5節(jié)介紹了專門的方法。第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ǔ)存并裝載到卡車上以滿足客戶的需求。預(yù)先知道的卡車路線是根據(jù)客戶訂單的交付截止日期確定的。倉(cāng)庫(kù)由11個(gè)過(guò)道組成，托盤架可容納40,000個(gè)托盤。自動(dòng)堆垛起重機(jī)或S / R機(jī)器在每個(gè)過(guò)道中工作，以將托盤從其各自的機(jī)架移動(dòng)到過(guò)道開(kāi)始時(shí)的收集器。叉車將貨盤運(yùn)送至卡車。倉(cāng)庫(kù)有13個(gè)?？亢逞b載卡車。圖1顯示了該倉(cāng)庫(kù)的裝貨流程。 倉(cāng)庫(kù)計(jì)劃系統(tǒng)（WPS）和倉(cāng)庫(kù)管理系統(tǒng)（WMS）用于操作倉(cāng)庫(kù)。每輛卡車的每日裝載計(jì)劃由WPS執(zhí)行。 WMS確定回收托盤和S / R機(jī)器和叉車的運(yùn)動(dòng)順序。一輛卡車每天可以檢索大約一百個(gè)貨物。每輛卡車都有自己的交貨時(shí)間，這是由WPS考慮的，并且裝載不得延遲。在為WPS定義的策略中，整套負(fù)載被分成稱為批次的子集。同時(shí)處理一批中的加載。在完成前一批次的加載之前，無(wú)法啟動(dòng)加載批次。批量的大小是根據(jù)交貨期限和?？亢车臄?shù)量來(lái)確定的。標(biāo)準(zhǔn)的每日計(jì)劃包括15-20批次，每批6-13批次。 客戶的訂單包括一個(gè)或多個(gè)托盤上交付的產(chǎn)品或一組產(chǎn)品。訂單的產(chǎn)品組是預(yù)先知道的，并且在倉(cāng)庫(kù)中可用?？ㄜ囏?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è)通道工作。叉車從自己的過(guò)道收到托盤后，可將托盤運(yùn)送到任何卡車。出于安全原因，不允許多臺(tái)叉車同時(shí)將貨盤放在卡車上。所以，一個(gè)負(fù)載應(yīng)該在特定時(shí)間收到一個(gè)托盤。托盤裝入卡車后，叉車返回到其通道并與WMS通信，以便它可用于新的運(yùn)輸。然后為相同的負(fù)載編程下一個(gè)托盤。叉車在每次運(yùn)輸時(shí)只能接收一個(gè)托盤。有關(guān)分析的AS / RS倉(cāng)庫(kù)的詳細(xì)信息可以從[5]中獲得。 由S / R機(jī)器檢索的批次中不同的托盤序列會(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è)托盤組成，這4個(gè)托盤預(yù)先具有優(yōu)先關(guān)系，代表該批次中將檢索的總共12個(gè)托盤。每個(gè)過(guò)道有一個(gè)叉車將托盤從過(guò)道搬運(yùn)到相應(yīng)的過(guò)道， 雖然托盤可以從幾個(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í)從第三通道中取回。為方便起見(jiàn)，托盤從1到12連續(xù)編號(hào)。 表1真正問(wèn)題的一個(gè)說(shuō)明性例子 圖2.用于檢索托盤的兩種不同時(shí)間表 圖2顯示了兩個(gè)不同的檢索托盤序列。矩形內(nèi)的數(shù)字標(biāo)識(shí)托盤。對(duì)于每個(gè)序列，圖2顯示了該組通道（左側(cè)）的甘特圖和該組負(fù)荷（右側(cè)）的甘特圖，其表示更好的處理時(shí)間。取回托盤的順序僅在走道3處不同，托盤11在托盤3和7（圖2（a））之后或托盤3和7（圖2（b））之前收集。決定何時(shí)檢索托盤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)，并具有基于類的產(chǎn)品存儲(chǔ)分配。他們調(diào)查了影響倉(cāng)儲(chǔ)系統(tǒng)性能的因素。 Yin和Rau [18]將動(dòng)態(tài)選擇排序規(guī)則的模擬和遺傳算法結(jié)合起來(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ù)中的卡車裝載作業(yè)模擬為帶再循環(huán)的作業(yè)車間調(diào)度問(wèn)題（JSP）[5]。奧利維拉[5]假定運(yùn)輸托盤的處理時(shí)間相同，而不依賴于過(guò)道和卡車的位置。 Figueiredo等人[6]通過(guò)考慮不同的處理時(shí)間來(lái)擴(kuò)展該問(wèn)題，并通過(guò)具有隨機(jī)密鑰表示的遺傳算法來(lái)解決該問(wèn)題。 Oliveira [5]和Figueiredo等人[ [6]認(rèn)為托盤可以從以前由WMS決定的一個(gè)通道檢索，考慮到靠近?？繛场Ｔ谶@項(xiàng)研究中，這個(gè)假設(shè)通過(guò)考慮托盤的替代通道來(lái)擴(kuò)展?？ㄜ囇b載調(diào)度同時(shí)確定托盤取回過(guò)道的選擇。因此，問(wèn)題包括選擇通道來(lái)檢索托盤（目前由WMS執(zhí)行），以及托盤從收集器到卡車的運(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é)中，介紹了用于整車運(yùn)行調(diào)度問(wèn)題的MIP公式。我們不考慮交叉對(duì)接或訂單揀選生產(chǎn)托盤。本研究考慮的假設(shè)如下： ?訂單僅由存儲(chǔ)在倉(cāng)庫(kù)中的（完整）托盤產(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)輸開(kāi)始和結(jié)束時(shí)間為零。如果在叉車k上分配，則約束條件（4）保證該托盤的運(yùn)輸完成時(shí)間不能小于其起始時(shí)間和運(yùn)輸時(shí)間之和。約束條件（5）和（6）滿足叉車在將當(dāng)前托盤運(yùn)送到相應(yīng)的叉車之前不能開(kāi)始運(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è)問(wèn)題可以被歸類為FJSP，其中貨物被認(rèn)為是工作，貨物的貨盤被認(rèn)為是工作的操作，并且用于將檢索物品移除到貨車的叉車被視為機(jī)器。最小化完工時(shí)間（運(yùn)輸時(shí)間）是目標(biāo)，因?yàn)檫@樣可以最大限度地減少訂單的吞吐時(shí)間并最大化倉(cāng)庫(kù)效率。 在FJSP中，不能同時(shí)在機(jī)器上處理多個(gè)操作。此外，對(duì)于滿足托盤優(yōu)先關(guān)系的所有工作，都存在技術(shù)限制。在倉(cāng)庫(kù)中，叉車只能像FJSP中的機(jī)器一樣在一定時(shí)間只運(yùn)載一個(gè)托盤。同樣，對(duì)于每個(gè)應(yīng)該保證的負(fù)載，都有一個(gè)接收訂單托盤。在前一個(gè)之前沒(méi)有裝載palletcan。換句話說(shuō)，不允許重疊相同載荷的貨盤的運(yùn)輸。每個(gè)負(fù)載的托盤順序可以作為技術(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)在有些托盤可以從兩個(gè)通道中取出，而前一個(gè)托盤和一個(gè)處理時(shí)間更長(zhǎng)的新替代物。每個(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í)間更長(zhǎng)。此分配的最佳時(shí)間表如圖3（b）所示。盡管將兩個(gè)托盤分配到較大的處理時(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]用于解決整車運(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è)托盤的優(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ī)則和輪盤賭被用作選擇操作員的方法。應(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ī)器（貨架/叉車）上的操作（貨盤）而開(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ī)則選擇，并由輪盤選擇。交叉操作符用于生成后代。如果選擇兩個(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中卡車負(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ò)為一些貨物托盤添加替代通道。 表6 Figueiredo等人使用的操作分布[6] 卡車的裝載（作業(yè)）由35個(gè)托盤（作業(yè)）組成，這些托盤來(lái)自靠近停靠站的5個(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í)間。通過(guò)這種方式，研究了將檢索序列建模為FJSP的好處。 每個(gè)實(shí)例都有兩種不同的人口規(guī)模：20人中的小人口和100人中的大一人。突變和交叉概率都被確定為0.5。計(jì)算結(jié)果在表7中給出。第一列至第四列代表實(shí)例名稱，人口規(guī)模（彈出大?。?，裝載/作業(yè)數(shù)量（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)的卡車裝載操作的調(diào)度被模擬為FJSP?；趦?yōu)先級(jí)的GA應(yīng)用于真正的AS / RS倉(cāng)庫(kù)，以對(duì)檢索到的托盤進(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)檢索托盤。使用額外的過(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)檢索托盤，這些收益會(huì)更大。 提高吞吐率，在更短的時(shí)間內(nèi)為客戶服務(wù)，并減少卡車和司機(jī)裝貨的等待時(shí)間，這些結(jié)果是其他管理方面的好處。如今，為了增加倉(cāng)庫(kù)的吞吐量，倉(cāng)庫(kù)建立了更多的過(guò)道，在卡車到達(dá)之前準(zhǔn)備了多個(gè)緩沖區(qū)以準(zhǔn)備貨物，在通道開(kāi)始時(shí)有多達(dá)3個(gè)收集器以及更多數(shù)量的托盤，從而導(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)研究中，通道和卡車之間的運(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ù)中的托盤。 致謝 這項(xiàng)研究得到了LATNA實(shí)驗(yàn)室，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