謝 謝, 李彥平

(沈陽大學 裝備制造綜合自動化重點實驗室, 遼寧 沈陽 110044)

本文研究了在鋼鐵企業(yè)鋼卷倉庫中出現(xiàn)的一個問題,如圖1所示.一些成品或半成品板卷已經(jīng)被存放在倉庫中等待被客戶或下道工序選擇.根據(jù)實際存儲的需求,每個板卷已經(jīng)被放在了預(yù)先指定的按兩層擺放的位置上.如果一個需求板卷在上層或無板卷阻礙的下層,它可以被直接運輸?shù)街付ㄎ恢?如果一個需求板卷在下層并且由上層的一個或兩個板卷阻礙,直到阻礙板卷需要被運到另外的位置后,它才能被運輸?shù)街付ㄎ恢?為了便于描述問題,前一種情況稱為運輸操作,后一種情況稱為倒垛操作.這兩種操作都由貴重的設(shè)備即上方移動的許多吊機實施.目的就是確定一個聯(lián)合運輸和倒垛操作的多吊機調(diào)度,使得所有的需求板卷盡快被運輸?shù)街付ㄎ恢?同時確定每個阻礙板卷需要倒垛的位置.這個問題經(jīng)常出現(xiàn)于存儲成品或半成品板卷的鋼鐵企業(yè)倉庫中,如熱軋后庫、熱鍍鋅原料庫、酸洗原料庫和酸軋后庫.另外,在集裝箱終端的垛場和造船廠原料庫也存在該問題.然而,現(xiàn)有的文獻幾乎沒有研究該問題的.

圖1 鋼鐵企業(yè)生產(chǎn)物流圖Fig.1 Production and logistics flow chart in iron and steel enterprises

該問題通常如下描述. 給定一些位于倉庫某區(qū)中的候選板卷.一旦收到來自客戶和生產(chǎn)線的需求板卷列表,這些板卷由處于上方的覆蓋該區(qū)的雙向跨上的一些吊機實施操作,如圖2所示.為了方便描述,定義一個板卷為一個工件.每個吊機從一個地方移動到另一個地方意味著它的提起設(shè)備(吊鉤)隨著吊機不僅沿著平行的跨移動,而且在跨之間移動,兩方向的移動是同時進行的.本文中,將吊鉤看作吊機.本文研究在避免吊機碰撞的約束下,決策聯(lián)合運輸操作和倒垛操作以最小化最后一個需求板卷被運輸?shù)街付ㄎ恢玫耐瓿蓵r間(makespan).

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

有關(guān)吊機調(diào)度的文獻通常僅考慮吊機的一種操作[如集裝箱碼頭的岸吊(QC)或場吊(YC)調(diào)度和電鍍生產(chǎn)線中的吊機(HS)調(diào)度],并沒有考慮多吊機的運輸與倒垛的集成操作.一些研究致力于和其他設(shè)備的集成研究以調(diào)度吊機[1-5]. 一些研究僅致力于研究兩臺或多吊機調(diào)度問題.Lei和Wang[6]提出了兩臺吊機周期調(diào)度的一個算法.他們通過劃分兩個區(qū)域?qū)⒚颗_吊機分配給專門的區(qū)域進行研究,然而連續(xù)的相鄰兩區(qū)不能保證吊機之間不碰撞.Armstrong等[7]提出了一個貪婪搜索算法以確定吊機的最小數(shù)目.Liu和Jiang[8]研究了工件具有固定加工時間和移動時間的兩臺吊機調(diào)度問題,提出了一個多項式時間最優(yōu)算法.Zhou和Liu[9]提出了解決具有重疊區(qū)域的兩臺吊機周期調(diào)度問題的一個啟發(fā)式算法.對于多吊機調(diào)度問題,Varnier 等[10]使用約束邏輯規(guī)劃的方法確定當給定吊機分配時的最優(yōu)調(diào)度.Jiang和Liu[11]提出了具有固定加工時間和移動時間的多吊機問題的多項式時間最優(yōu)算法.

然而,之前提及的這些問題或者是本文考慮問題的特殊情況,或者與本文研究的問題不同.研究目的就是減少存儲時間,但并沒有同時考慮到吊機的運輸?shù)苟饧烧{(diào)度.盡管有一些研究主要考慮倒垛,但在這些問題中,工件按照每個工件上僅有一個工件阻礙的方式堆放,比起上述研究的問題簡單得多.此外,大部分的研究主要考慮單吊機調(diào)度,多吊機調(diào)度問題研究得相對較少.大多數(shù)研究主要考慮智能計算以獲得近優(yōu)解,很少有研究對吊機調(diào)度問題進行理論分析.因此,大部分文獻不能直接應(yīng)用于解決上述問題.該問題有如下兩個特點:吊機操作集成了運輸和倒垛兩道工序;協(xié)調(diào)調(diào)度吊機,避免相鄰吊機之間碰撞.這需要在考慮問題特點和約束的基礎(chǔ)上提出新的算法.

1 問題的符號和分析

2 問題模型

為了更清晰地描述上面描述的問題,在這部分中,提出了一個混合整線性規(guī)劃模型(MILP).

2.1 問題參數(shù)

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

μ對應(yīng)于吊機上提和下放一個工件的時間.

v1,v2和λ1,λ2對應(yīng)于吊機帶著工件和不帶工件沿著兩個方向移動的速度 ,為了表達方便,本文中,令λ=min{λ1,λ2},v=min{v1,v2}.不失一般性,假設(shè)λ≥v≥1.

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

決策變量如下:

xmij=1,如果工件Ji被吊機m倒到工件Jj的位置(Ji,Jj∈Ω0,m∈M);否則,xmij=0.

zij=1,如果工件Jj的一道工序(倒垛或運輸)在工件Ji的一道工序(倒垛或運輸)結(jié)束后開始(Ji,Jj∈Ω0);否則,zij=0.

smi,吊機m(m∈M)從工件Ji的位置移動的開始時間(Ji∈Ω或Ji∈Ω0).根據(jù)吊機的移動可知,如果吊機帶著工件開始移動,這是裝載移動的開始時間;否則,是空移動的開始時間.

emi,吊機m(m∈M)將工件Ji(Ji∈Ω0)倒垛后的結(jié)束時間.

Cmax,最后一個工件被運到指定位置的完成時間.

2.2 數(shù)學模型

問題的數(shù)學模型表示如下:

minCmax=max{Ci|Ji∈Ω}.

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

(?Ji,Jj∈Ω0,?m∈M);

(8)

(?Ji∈Ω0,Jj∈Ω,?m∈M);

(9)

(?Ji∈Ω,Jj∈Ω0,?m∈M);

(10)

(?Ji,Jj∈Ω0,?m∈M);

(11)

(?Ji,Jj∈Ω,?m∈M);

(12)

(?Ji,Jj∈Ω0,?m1,m2∈M);

(13)

(?Ji,Jj∈Ω0,?m1,m2∈M);

(14)

(?Ji,Jj∈Ω0,?m1,m2∈M);

(15)

(?Ji,Jj∈Ω0,?m1,m2∈M);

(16)

(?Ji,Jj∈Ω0,?m1,m2∈M);

(17)

(?Ji,Jj∈Ω0,?m1,m2∈M);

(18)

(?Ji,Jj∈Ω0,?m1,m2∈M);

(19)

(?Ji,Jj∈Ω0,?m1,m2∈M);

(20)

(?Ji,Jj∈Ω0,?m1,m2∈M);

(21)

(?Ji,Jj∈Ω0,?m1,m2∈M);

(22)

(?Ji,Jj∈Ω0,?m1,m2∈M);

(23)

(?Ji,Jj∈Ω0,?m1,m2∈M);

(24)

xmij∈{0, 1} (?Ji,Jj∈Ω0,?m∈M);

(25)

(26)

(27)

(28)

(29)

zij∈{0, 1} (?Ji,Jj∈Ω0,?m∈M).

(30)

由于文獻[12]中研究的單吊機調(diào)度問題已經(jīng)證明為強NP難的,因此,本文考慮的多吊機調(diào)度問題也是強NP難問題.這使得最優(yōu)算法不能解決實際中的大規(guī)模問題,啟發(fā)式算法能夠有效地解決上述問題.在下面的部分中,提出了問題的一些最優(yōu)性質(zhì),這些性質(zhì)將應(yīng)用在后面的啟發(fā)式算法及其性能分析中.

3 啟發(fā)式算法及其最壞性能分析

3.1 啟發(fā)式算法

第3步 吊機的操作原則:一旦吊機空閑,如果存在沒有被阻礙的需求工件,則吊機對該工件進行運輸操作;否則,吊機進行倒垛操作.

第3.1步 對于運輸操作,如果存在多需求工件,吊機選擇權(quán)最大的工件進行操作.

第3.2步 對于倒垛操作,吊機選擇距離當前位置最近的阻礙工件,將其倒到最近的下層空位置,如果不存在這樣的空位,則選擇上層中不阻礙需求板卷的位置;否則,吊機選擇距離當前位置次最近的阻礙工件進行操作.如果一個需求工件被運輸?shù)街付ㄎ恢?則從列表中刪除.

第4步 當兩臺或多臺吊機同時可利用時,根據(jù)第5步分配吊機.根據(jù)第3步執(zhí)行每臺吊機的操作.一旦發(fā)生吊機沖突,轉(zhuǎn)第6步.

第5步 檢驗吊機操作的可行性.

第5.1步 檢驗分配的吊機號是否在可行范圍內(nèi),如果可行,則構(gòu)建一個吊機啟發(fā)式;否則,轉(zhuǎn)第6步.

第5.2步 為避免吊機碰撞,分別檢驗在相鄰兩行或同一行中的各種可能的情況.如果可行,則構(gòu)建一個吊機啟發(fā)式;否則,轉(zhuǎn)第6步.

第6步 避免吊機碰撞的原則:

第6.1步 交換彼此的操作;

第6.2步 一臺吊機等待直到另一臺吊機完成當前的操作.

性質(zhì)1 啟發(fā)式的計算復(fù)雜度為o(n2N2×|M|2).

證明 在第2步中,需要時間o(|M|×NlogN).第3步和第4步中,吊機運行時間分別為o(nN)和o(nN|M|).第5步中,檢驗吊機操作的可行性時間為o(nN|M|).因此,算法的復(fù)雜度為o(n2N2|M|2).

3.2 最壞性能分析

為了分析算法的最壞性能比,根據(jù)三種不同的情況得到了三個下界.由于幾個下界之間互相補充,沒有一個能代替另一個,因此,進一步采用復(fù)合下界的策略,使得得到的問題的下界可以更接近最優(yōu)值.基于這個界,分析了問題啟發(fā)式的最壞性能.

自然的,可以把多吊機對工件的操作看作平行機.一個下界為

當所有的需求工件位于上層或無阻礙板卷壓迫的下層時,這個界的值更緊.等式右邊第一項的值需要決策,第二項的值為常數(shù).注意,這個下界忽略了吊機的空移動時間.因此,不采用它作為問題的下界.

從吊機運輸操作的角度看,一個可行調(diào)度的最大完工時間不能小于運輸一個工件的時間.因此,得到的下界為

從吊機倒垛操作的角度看,一個可行調(diào)度的最大完工時間不能小于一個工件在|R|-|M|+1相鄰行內(nèi)由一臺吊機進行倒垛操作的時間.顯然,得到的另一個下界為

由上面的討論可以直接得到以下結(jié)論.

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

性質(zhì)2 問題的下界LB可由下面兩個下界獲得:LB=max{LB2,LB3}.

定理由啟發(fā)式得到調(diào)度σH的最壞性能比為

證明 不失一般性,考慮一種最差的情況,即一臺吊機m∈M對所有需求工件在|R|-|M|+1相鄰行中進行操作.顯然,在這種情況下,不需要考慮吊機間的彼此碰撞.如果沒有阻礙工件,問題可以在多項式時間內(nèi)求得最優(yōu)解.因此,一個可行調(diào)度的最大完工時間或許依賴于阻礙工件:阻礙工件的個數(shù)越少,可以更容易地得到一個調(diào)度.根據(jù)阻礙工件的個數(shù),算法的最壞性能可以根據(jù)阻礙工件的個數(shù)從下面3種情況中得到.

在這種情況下,算法可以得到最優(yōu)調(diào)度,有Cmax(σH)=Cmax(σ*).

在這種情況下,可以為阻礙工件提供足夠的倒垛位置而不會使需求工件再次被阻礙.根據(jù)第3步,在運輸所有需求板卷之前,首先將所有阻礙板卷倒垛.調(diào)度σH的目標函數(shù)值不能超過需要倒垛的所有阻礙板卷的最長時間(兩項的和)與需要運輸?shù)乃行枨蟀寰淼淖疃虝r間(后三項的和).

(a)

(b)

在這種情況下,由于阻礙工件沒有足夠的倒垛位置,因此,阻礙工件或許被倒到已經(jīng)運走的需求工件的位置.也就是,一些需求工件被運輸?shù)酶?為了盡可能地減少倒垛時間,吊機或許將對工件進行倒垛和運輸操作.因此,最大完工時間Cmax(σH)總是滿足下式:

式中,右邊第一項為吊機從初始位置到一個工件的最大空移動時間,后3項的和為最大的倒垛與運輸時間的和.

因此,最壞性能為max{(a),(b),(c),(d)}.

4 結(jié) 語

本文不同于之前的相關(guān)文獻,對這個實際問題通過理論分析的方式進行了研究.問題被描述為一個混合整規(guī)劃模型,由于問題是強NP難的,提出了一個有效的啟發(fā)式算法,這個算法的性能與問題的參數(shù)有關(guān),這個算法為改進吊機的運行效率、及時地為下道工序運輸工件、提高鋼鐵企業(yè)的產(chǎn)能提供了一個依據(jù).

上述問題適用于在鋼鐵企業(yè)倉庫中解決避免吊機碰撞的約束下,運輸需求板卷多吊機協(xié)調(diào)調(diào)度問題.除了鋼卷倉庫中的問題可以應(yīng)用,這個研究在考慮具體的實施細節(jié)時也可以擴展到類似的板坯倉庫和集裝箱碼頭的倒垛、重倒垛問題.

協(xié)調(diào)調(diào)度吊機與其他物流和運輸設(shè)備,如鋼鐵企業(yè)的臺車和卡車、集裝箱碼頭的船只和場吊,都是將來進一步研究的問題.

參考文獻:

[ 1 ]Guan Y, Cheung R K. The Berth Allocation Problem: Models and Solution Methods[J]. OR Spectrum, 2004,26(1):75-92.

[ 2 ]Imai A, Sun X, Nishimura E, et al. Berth Allocation in a Container Port: Using a Continuous Location Space Approach[J]. Transportation Research Part B: Methodological, 2005,39(3):199-221.

[ 3 ]Park Y M, Kim K H. A Scheduling Method for Berth and Quay Cranes[J]. OR Spectrum, 2003,25(1):1-23.

[ 4 ]Kim K H, Moon K C. Berth Scheduling by Simulated Annealing[J]. Transportation Research Part B: Methodological, 2003,37(6):541-560.

[ 5 ]Neumann K, Zimmermann J. Procedures for Resource Leveling and Net Present Value Problems in Project Scheduling with General Temporal and Resource Constraints[J]. European Journal of Operational Research, 2000,127(2):425-443.

[ 6 ]Lei L, Wang T J. The Minimum Common-Cycle Algorithm for Cyclic Scheduling of Two Material Handling Hoists with Time Window Constraints[J]. Management Science, 1991,37(12):1629-1639.

[ 7 ]Armstrong R, Gu S, Lei L. A Greedy Algorithm to Determine the Number of Transporters in a Cyclic Electroplating Process[J]. IIE Transactions, 1996,28(5):347-355.

[ 8 ]Liu J Y, Jiang Y. An Efficient Optimal Solution to the Two-hoist No-wait Cyclic Scheduling Problem[J]. Operations Research, 2005,53(2):313-327.

[ 9 ]Zhou Z L, Liu J Y. A Heuristic Algorithm for the Two-hoist Cyclic Scheduling Problem with Overlapping Hoist Coverage Ranges[J]. IIE Transactions, 2008,40(8):782-794.

[10]Varnier C, Bachelu A, Baptiste P. Resolution of the Cyclic Multi-hoists Scheduling Problem with Overlapping Partitions[J]. INFOR, 1997,35(4):309-324.

[11]Jiang Y, Liu J Y. Multihoist Cyclic Scheduling with Fixed Processing and Transfer Times[J]. IEEE Transactions on Automation Science and Engineering, 2007,4(3):435-450.

[12]謝謝,李彥平. 鋼卷倉庫中的吊機調(diào)度問題[J]. 沈陽大學學報:自然科學版, 2014,26(2):159-165.

(Xie Xie, Li Yanping. Crane Scheduling in Warehouse of Coil[J]. Journal of Shenyang University: Natural Science, 2014,26(2):159-165.)