運(yùn)輸與倒垛集成的多吊機(jī)調(diào)度問題

謝 謝, 李彥平

(沈陽大學(xué) 裝備制造綜合自動(dòng)化重點(diǎn)實(shí)驗(yàn)室, 遼寧 沈陽 110044)

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

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

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

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

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

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

1 問題的符號(hào)和分析

2 問題模型

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

2.1 問題參數(shù)

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

μ對(duì)應(yīng)于吊機(jī)上提和下放一個(gè)工件的時(shí)間.

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

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

決策變量如下:

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

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

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

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

Cmax,最后一個(gè)工件被運(yùn)到指定位置的完成時(shí)間.

2.2 數(shù)學(xué)模型

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

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)

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

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

3.1 啟發(fā)式算法

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

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

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

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

第5步 檢驗(yàn)吊機(jī)操作的可行性.

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

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

第6步 避免吊機(jī)碰撞的原則:

第6.1步 交換彼此的操作;

第6.2步 一臺(tái)吊機(jī)等待直到另一臺(tái)吊機(jī)完成當(dāng)前的操作.

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

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

3.2 最壞性能分析

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

自然的,可以把多吊機(jī)對(duì)工件的操作看作平行機(jī).一個(gè)下界為

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

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

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

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

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

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

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

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

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

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

(a)

(b)

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

式中,右邊第一項(xiàng)為吊機(jī)從初始位置到一個(gè)工件的最大空移動(dòng)時(shí)間,后3項(xiàng)的和為最大的倒垛與運(yùn)輸時(shí)間的和.

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

4 結(jié) 語

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

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

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

參考文獻(xiàn):

[ 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]謝謝,李彥平. 鋼卷倉庫中的吊機(jī)調(diào)度問題[J]. 沈陽大學(xué)學(xué)報(bào):自然科學(xué)版, 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.)