鋼卷倉庫中的吊機調(diào)度問題

謝 謝，李彥平

（沈陽大學 裝備制造綜合自動化重點實驗室，遼寧 沈陽 110044）

本文的研究來源于鋼鐵企業(yè)冷軋原料庫，所有存儲在原料庫的板卷等待被運走進行進一步的冷軋加工.由于存儲技術(shù)的要求，這些板卷每個區(qū)域中每行必須按照兩層堆放，下層的板卷數(shù)至少比上層多一個（如圖1所示，圖中以四行的區(qū)域為例）.當下游生產(chǎn)或客戶需求板卷時，存儲在下層且沒有被上層阻礙的需求板卷可以直接被吊機提起運輸走；否則，在下層板卷被運走前，阻礙板卷首先被倒垛到該區(qū)域的其他空位置.所有需求板卷的運輸和阻礙板卷的倒垛都由上方的移動吊機進行.實際中，一個倉庫通?？梢詣澐譃樵S多相同的區(qū)域，每個區(qū)域上方有一臺吊機，見圖1.吊機從一個地方移動到另一個地方意味著它的提起設(shè)備（吊鉤）隨著吊機不僅沿著平行的跨移動而且在跨之間移動，兩方向的移動是同時進行的.本文將吊鉤看作吊機.

圖1 鋼卷倉庫一個區(qū)域的板卷存儲Fig.1 Coil storage in a block of steel coil warehouse

如果需求板卷被吊機直接運輸?shù)街付ㄎ恢茫瑢⑦@個過程命名為吊機的運輸；如果阻礙板卷被運輸?shù)皆搮^(qū)域的其他位置，將這個過程命名為吊機的倒垛.本文主要提出并分析了吊機調(diào)度問題，同時將運輸和倒垛結(jié)合起來考慮，以盡快確定全部需求板卷的運輸順序以及每個阻礙板卷的倒垛位置.該問題存在于實際中大多數(shù)倉庫運輸和生產(chǎn)系統(tǒng)（如鋼鐵企業(yè)中熱軋后庫、熱鍍鋅原料庫、酸洗原料庫和酸軋后庫，集裝箱終端的垛場，造船廠的原料庫），然而很少有這方面的相關(guān)研究，一個可能的原因是很難同時將吊機的運輸和倒垛集成考慮.有效地將運輸和倒垛集成可以增加吊機的利用率，減少這種貴重設(shè)備不必要的等待時間.

本文研究的問題為發(fā)生在倉庫中的物質(zhì)處理設(shè)備（吊機）的活動：盡快地接收、排序和轉(zhuǎn)移（確定板卷的順序），這種活動屬于由van den Berg和Zijm［1］所定義的倉庫管理活動.盡管 Z?pfel和Wasner［2］考慮了倉庫內(nèi)關(guān)于實際順序、調(diào)度和移動的路線，他們將存儲位置和吊機作為機器，并把問題描述成一個一般性的車間調(diào)度問題，但并沒有給出倉庫活動中吊機運輸和倒垛的細節(jié).此外，他們主要提出了一個啟發(fā)式，并沒有從計算復雜度的角度對其進行評價并給出理論分析.

在自動存／取倉庫環(huán)境中，相關(guān)文獻主要考慮了生產(chǎn)布局設(shè)計問題，其中，Burkard等［3］考慮了自動倉庫中車輛操作系統(tǒng)的設(shè)計.倉庫的布局和車輛的數(shù)目及屬性已經(jīng)給定.除了van den Berg［4］給出的關(guān)于倉庫問題的綜述，van den Berg和Zijm［1］討論了倉庫系統(tǒng)并提出了倉庫管理系統(tǒng)的一個分類.van den Berg［4－5］研究了在庫存控制決策和生產(chǎn)分配分發(fā)關(guān)系的模型.Bertazzi和Speranza［6］為極小化總庫存和運輸費用而考慮了庫存和運輸費用的關(guān)系.

包含倒垛操作的文獻較多地出現(xiàn)在集裝箱終端和鋼鐵企業(yè)的堆垛問題中.由于每垛中一個板坯放在另一個板坯的頂端，因此，每個需求板坯僅被一個板坯阻礙，因此，這類問題比本文研究的問題要簡單.在集裝箱取出順序給定的情況下，Kim和Hong［7］提出了一個分支定界過程和一個啟發(fā)式算法決策集裝箱的存儲位置以最小化倒垛數(shù)目.為求解集裝箱的動態(tài)存取問題，Wan等［8］提出了一個線性整規(guī)劃模型和啟發(fā)式.在集裝箱的取出順序給定的前提下，Lee等［9］提出了一個三階段啟發(fā)式以最小化加權(quán)總移動次數(shù)和吊機的工作時間之和.Lee和Hsu［10］提出了一個線性整規(guī)劃模型以最小化倒垛次數(shù).Lee和Chao［11］通過鄰域搜索的啟發(fā)式求解了該問題更大規(guī)模的實例.Steenken等［12］給出了關(guān)于堆垛問題理論和實際的綜述.

本文的問題不同于上面提到的設(shè)計倉庫形狀、設(shè)計存取設(shè)備的路線等問題，以上問題并沒有考慮吊機上提下放的細節(jié)操作.盡管一些學者關(guān)于吊機調(diào)度研究了吊機的倒垛或重倒垛活動，但對于板卷的倒垛研究得很少.盡管謝和李［13］研究了鋼鐵企業(yè)中的吊機調(diào)度問題，但他們并沒有同時考慮吊機的運輸和倒垛.因此，有必要研究這種將運輸和倒垛集成考慮的吊機調(diào)度.

1 問題描述和符號

圖2 鋼卷倉庫一個區(qū)域的俯視圖Fig.2 Top view of a block in steel coil warehouse

定義吊機的位置等于它的吊鉤向工作區(qū)內(nèi)投影與之距離最近的板卷位置.令w0為吊機的初始位置.定義全部板卷指定的位置為wT.因此，吊機最初的位置與板卷Ji的距離可以表示為＝｜w0－wi｜，板卷Ji與指定位置的距離可以表示為di＝｜wi－wT｜.類似的，兩板卷Ji和Jj之間的距離可以表示為dij＝｜wi－wj｜.

定義吊機上提、下放板卷的時間為μ（很容易擴展到上提下放的時間是不同的情況）.吊機帶著板卷沿著平行跨和支撐橋之間移動的速度分別為v1和v2，類似的，兩個方向空吊機移動的速度為λ1（λ1≥v1）和λ2（λ2≥v2）.由于給定了可計算的移動距離和吊機的速度，因此，吊機的每一個裝載移動時間和空移動時間分別由下面兩式計算出來：

2 問題模型

為了更清楚地描述問題，本文提出了問題的一個混合整線性規(guī)劃模型（MILP）.

2.1 問題參數(shù)

輸入數(shù)據(jù)如下：

wi，w0和wT分別對應(yīng)板卷的位置、吊機的初始位置和指定位置，一旦給定N 個需求的板卷，它們的位置已知；

μ對應(yīng)于吊機上提和下放一個板卷；

v1，v2和λ1，λ2對應(yīng)于吊機帶著板卷和不帶板卷移動沿著兩個方向移動的速度，為了表達方便，本文中，令λ＝min｛λ1，λ2｝，v＝min｛v1，v2｝，不失一般性，假設(shè)λ≥v≥1；

M是一個很大的正整數(shù).

決策變量如下：

xij＝1，如果板卷Ji被吊機倒到板卷Jj的位置（Ji，Jj∈Ω0）；否則，xij＝0；

si，吊機從板卷Ji的位置移動的開始時間（Ji∈Ω 或Ji∈Ω0）；

ei，吊機將板卷Ji（Ji∈Ω0）倒垛后的結(jié)束時間；

Cmax，最后一個板卷運到指定位置的完成時間.

2.2 數(shù)學模型

問題的模型可以表示為

3 復雜性及問題的性質(zhì)

根據(jù)前述可知，該問題的復雜性仍然未知.因此，通過與一個已證明為強NP難的問題相歸結(jié)，證明該問題也是強NP難的.

3.1 復雜性

定理1 考慮運輸每個需求板卷的時間趨近于0，將這個時間近似地認為0，即使是這種簡單情況，問題也是強NP難的.

證明 當這種情況存在時，只需要考慮所有的阻礙板卷.給定任意一個旅行商問題的例子，將旅行商看作一臺吊機，將城市看作阻礙板卷的位置.這臺吊機從初始位置開始，必須通過每個阻礙板卷的位置將它們運走.由于兩個板卷之間的距離和速度都是預(yù)先已知的，因此，這個問題等價于已經(jīng)證明為強NP難的旅行商問題.這種情況可解當且僅當旅行商問題可解.

推論 本文研究的問題是強NP難的.

證明 在倒垛和運輸同時考慮的情況下，可知本文研究的問題是強NP難的.

復雜性的結(jié)果表明，除非P＝NP，否則問題不存在多項式時間內(nèi)可解的算法.在下一部分中，首先證明了滿足最優(yōu)解的一些性質(zhì).

3.2 問題的性質(zhì)

圖3描繪了一行的側(cè)視圖，其中，深色圈代表需求的板卷.

圖3 板卷倉庫中一行的側(cè)視圖Fig.3 Side view of a row in steel coil warehouse

根據(jù)板卷的位置，將需求板卷集Ω分成如下四類.

第1類 位于上層的板卷（見圖3中板卷2和14），令Ω1表示這類板卷的集合.

第2類 板卷位于下層，被需求板卷阻礙（包含在Ω1中的板卷阻礙）或無其他阻礙板卷（見圖3中板卷5和15），令Ω2表示這類板卷的集合.

第3類 板卷位于下層且被一個板卷阻礙（見圖3中板卷7被板卷8阻礙，板卷17被板卷18阻礙，板卷21被板卷20阻礙），令Ω3表示這類板卷的集合3表示阻礙板卷的集合.

第4類 板卷位于下層，且被不包含在Ω1中的兩個板卷阻礙（見圖3中板卷11被板卷10和12阻礙，板卷19被板卷18和20阻礙），令Ω4表示這類板卷的集合4表示阻礙板卷的集合.

因此，根據(jù)定義，有Ω＝Ω1∪Ω2∪Ω3∪Ω4.注意一些阻礙板卷或許同時阻礙兩個需求板卷，如板卷J18和J20，每一個屬于阻礙板卷集3或4，即3∩4≠?.根據(jù)分類表示，Ω1和Ω2中的板卷可以直接運輸.為了運輸Ω3和Ω4中的板卷，阻礙板卷必須先被倒垛到一個位置，這個位置或者是下層的空位，或者是上層空位在它的下層已有兩個板卷占著位.

性質(zhì)1 最優(yōu)調(diào)度中，最大完工時間不少于需求板卷與指定位置之間的總移動時間.

證明 由于一個調(diào)度開始并終于這個單吊機操作，調(diào)度值等于吊機總倒垛與總移動時間總和，因此，性質(zhì)顯然成立.

證明 根據(jù)板卷的分類，至少有｜Ω3｜≤｜Ω3｜＋2｜Ω4｜個板卷需要倒垛.如果｜Ω3｜≤｜Ω1｜＋｜Ω2｜，那么每個｜Ω3｜中的板卷可以僅倒一次到｜Ω1｜＋｜Ω2｜的位置.總倒垛次數(shù)為｜Ω3｜.否則，至少一個板卷需要倒兩次.因此，為了運輸所有的需求板卷，總倒垛次數(shù)至少為｜Ω3｜.類似的，最多（｜Ω3｜＋2｜Ω4｜）個板卷需要倒垛.如果（｜Ω3｜＋2｜Ω4｜）中的板卷每個僅倒一次，則需要（｜Ω3｜＋2｜Ω4｜）次；否則，一個板卷最多需要倒n次.因此，最多的倒垛次數(shù)為n（｜Ω3｜＋2｜Ω4｜）.

3.3 特殊情況

在這部分中，首先分析吊機之間可以將所有需求板卷運走的情況.這種情況發(fā)生在需求板卷在倉庫中上層和沒有阻礙板卷的下層.

性質(zhì)3 如果所有需求板卷均在Ω1和Ω2中，最優(yōu)調(diào)度可以在o（N）內(nèi)，通過選擇（－di）最小的板卷為第一個板卷，剩余的N－1個板卷順序任意排列而得到.

證明 令σ＝［J1，J2，…，JN］為板卷按任意順序的標號.在這個調(diào)度中，吊機從它的初始位置空移動到J1，放下吊鉤后將它提起立即運到指定位置.一旦吊機到達指定位置，將這個板卷放下，從這個位置空移動到板卷J2的位置.放下吊鉤后將J2提起立刻移動到指定位置當下，立刻空移動到板卷J3，運輸J3.重復這個過程，直到JN被吊機運輸?shù)街付ㄎ恢?吊機移動的完工時間可以用下式表示：

由于上式最后兩項是常數(shù)，最小化Cmax（σ）等價于選擇（－di）的值最小的板卷.

4 一般情況的啟發(fā)式算法及其性能分析

由于本文研究的問題是強NP難的，線性規(guī)劃模型求解問題的缺陷就是獲得解的時間隨著問題規(guī)模的增大快速增加.相比之下，啟發(fā)式算法在計算時間和解的質(zhì)量上給出了合理的折中.

4.1 啟發(fā)式算法

第1步 運輸所有屬于Ω1和Ω2中的板卷，根據(jù)性質(zhì)3，選擇具有最?。璬i）的板卷作為第一個板卷，剩余的｜Ω1｜＋｜Ω2｜－1板卷調(diào)度順序任意.轉(zhuǎn)第2步.

第3步：

②吊機從當前位置到集合Ω中的板卷距離與該板卷到指定位置距離之和.

比較由①和②得到的距離，選擇最小的進行吊機操作.如果這兩個距離相等，則選擇Ω1∪Ω2中的板卷優(yōu)先于3∪4.如果對于集合3∪4中的任意一個板卷沒有可倒垛的位置，轉(zhuǎn)第1步，運輸當前在集合Ω1∪Ω2中的板卷.一旦集合Ω中的板卷都被運輸?shù)街付ㄎ恢?，停?

根據(jù)啟發(fā)式，由第1步，吊機運輸板卷的時間為o（NlogN）.由第2步，吊機首先將阻礙板卷倒走再運輸所有的板卷.由于總倒垛板卷為（｜Ω3｜＋2｜Ω4｜）≤3 N，倒垛位置為｜Ω0｜＝n，因此，總倒垛時間為o（Nn（logN）（logn））.由第3步，吊機倒垛和運輸操作或許交替進行.因此，由啟發(fā)式算法獲得調(diào)度的時間為o（Nn（logN）（logn））.

4.2 性能分析

令啟發(fā)式算法獲得的調(diào)度為σH.

性質(zhì)4 問題的下界LB可以從如下兩個界中獲得：

其中，LB＝max｛LB1，LB2｝.

如果所有的需求板卷都在集合Ω1和Ω2中，根據(jù)性質(zhì)3，LB1為最優(yōu)目標值.LB2為總倒垛與運輸時間的最小值.

由于單吊機必須運輸所有的需求板卷并為所有的阻礙板卷倒垛，因此，最大完工時間依賴于吊機的操作順序.啟發(fā)式的目的就是盡可能減小吊機運輸和倒垛操作的距離.由于啟發(fā)式包括所有可能的情況，因此，按照如下三種情況分析最壞性能.

情況1 Ω＝Ω1∪Ω2.

在這種情況下，所有需求板卷屬于集合Ω1和Ω2，應(yīng)用啟發(fā)式第1步可以得到最優(yōu)調(diào)度σ＊，調(diào)度值為Cmax（σ＊）.因此

式中，右邊前兩項為最長倒垛時間總和，后三項為運輸所有需求板卷最短的時間總和.

式中，右邊第一項是吊機從初始位置空移動的最大時間，第二、第三項是吊機倒垛操作和運輸操作的最大時間，第四項為吊機總的上提和下放的時間.

根據(jù)情況2和Cmax（σ＊）≥LB≥LB2，同時結(jié)合｜Ω3｜≤N、｜Ω4｜≤2 N 和λ≥v≥1，可以得到如下最壞情況比：

根據(jù)情況3和Cmax（σ＊）≥LB≥LB2，同時結(jié)合｜Ω3｜≤N、｜Ω4｜≤2 N 和λ≥v≥1，可以得到如下最壞性能比：因此，max｛（a），（b）｝為最壞性能的比值.

定理2 對于由啟發(fā)式得到的問題的任意一個調(diào)度σH，最壞性能保證為

這個比值是潛在的最壞情況，與距離參數(shù)有關(guān).

5 結(jié) 語

本文重點考慮了吊機調(diào)度問題以將所有下游階段生產(chǎn)或客戶需要進一步加工的需求板卷運輸?shù)街付ㄎ恢玫淖畲笸旯r間最小化.這個問題源于實際工業(yè)中的倉庫管理問題，而且實際中經(jīng)常發(fā)生.研究這種吊機調(diào)度問題的文獻很少.本文主要提出了算法并從理論性能的角度對這個問題進行了分析，可以用于企業(yè)倉庫管理和大型設(shè)備使用以獲得更有效的利用率.

未來的研究方向包括解決如下問題：其他的目標函數(shù)如平均完工時間、總延遲時間和延遲板卷的個數(shù)；板卷具有可替換約束和板卷間的優(yōu)先約束.關(guān)于多吊機調(diào)度問題，是未來的另一個研究方向.

［1］ van den Berg J P，Zijm W H M.Models for Warehouse Management： Classification and Examples ［J］.International Journal of Production Economics，1999，59（1／2／3）：519－528.

［2］ Z?pfel G，Wasner M.Warehouse Sequencing in the Steel Supply Chain as a Generalized Job Shop Model［J］.International Journal of Production Economics，2006，104（2）：482－501.

［3］ Burkard R E，F(xiàn)ruhwirth B，Rote G.Vehicle Routing in an Automated Warehouse：Analysis and Optimization［J］.Annals of Operations Research，1995，57（1）：29－44.

［4］ van den Berg J P.Planning and Control of Warehousing Systems［D］.Enschede：University of Twente，1996.

［5］ van den Berg J P.A Literature Survey on Planning and Control of Warehousing Systems［J］.IIE Transactions，1999，31（8）：751－762.

［6］ Bertazzi L，Speranza M G.Minimizing Logistic Costs in Multistage Supply Chains［J］.Naval Research Logistics，1999，46（4）：399－417.

［7］ Kim K H，Hong G P.A Heuristic Rule for Relocating Blocks［J］.Computers ＆ Operations Research，2006，33（4）：940－954.

［8］ Wan Y W，Liu Jiyin，Tsai P C.The Assignment of Storage Locations to Containers for a Container Stack［J］.Naval Research Logistics，2009，56（8）：699－713.

［9］ Lee Yusin，Lee Y J. A Heuristic for Retrieving Containers from a Yard［J］.Computers ＆ Operations Research，2010，37（6）：1139－1147.

［10］ Lee Yusin，Hsu N Y.An Optimization Model for the Container Pre－marshalling Problem［J］.Computers ＆Operations Research，2007，34（1）：3295－3313.

［11］ Lee Yusin，Chao S L.A Neighborhood Search Heuristic for Pre－marshalling Export Containers［J］.European Journal of Operational Research，2009，196（2）：468－475.

［12］ Steenken D，Vo?S，Stahlbock R.Container Terminal Operation and Operations Research：A Classification and Literature Review［J］.OR Spectrum，2004，26（1）：3－49.

［13］ 謝謝，李彥平.罩式退火過程中的多吊機調(diào)度問題［J］.沈陽大學學報：自然科學版，2012，24（1）：12－19.

（Xie Xie，Li Yanping.Multi－Crane Scheduling in Batch Annealing Process［J］.Journal of Shenyang University：Natural Science，2012，24（1）：12－19.）