一類無干涉作業(yè)的碼頭起重機調(diào)度問題的近似算法研究

張文帥, 張 安, 陳光亭,2, 陳 永

(1.杭州電子科技大學理學院,浙江杭州310018;2.臺州學院數(shù)學與信息工程學院,浙江臺州317000)

一類無干涉作業(yè)的碼頭起重機調(diào)度問題的近似算法研究

張文帥1, 張 安1, 陳光亭1,2, 陳 永1

(1.杭州電子科技大學理學院,浙江杭州310018;2.臺州學院數(shù)學與信息工程學院,浙江臺州317000)

集裝箱港口上的大型貨輪通常是由從船頭到船尾縱向分布的集裝箱船艙構(gòu)成,而碼頭起重機主要負責裝載或卸載集裝箱.如何調(diào)度碼頭起重機在很大程度上影響著集裝箱貨輪的運輸效率.該文主要研究一類無干涉作業(yè)的起重機調(diào)度問題,目標是極小化裝(卸)載總耗時.對三臺,四臺起重機情形設(shè)計了新型調(diào)度算法,并給出了最壞情況分析,改進了文獻中的已有結(jié)果.

碼頭起重機;調(diào)度;近似算法;最壞情況分析

§1 引 言

在現(xiàn)代物流業(yè)中,海洋運輸已成為國際貿(mào)易的支柱和推動貿(mào)易全球化的關(guān)鍵動力.根據(jù)中國產(chǎn)業(yè)信息網(wǎng)消息,海運幾乎承擔了全球90%的國際貿(mào)易量,全球各大港口之間的競爭也越來越激烈.因而如何提高港口運行效率,尤其是如何減少碼頭起重機的裝載或卸載耗時,就顯得至關(guān)重.

集裝箱港口上的大型貨輪通常是由從船頭到船尾縱向分布的集裝箱船艙構(gòu)成,用于裝載不同目的地或不同客戶需求的集裝箱,而碼頭起重機主要負責裝載或卸載集裝箱,如何調(diào)度碼頭起重機在很大程度上影響著集裝箱貨輪的運輸效率.為減少裝卸錯漏,同一船艙內(nèi)的集裝箱只能由一臺起重機來處理.由于交叉作業(yè)會增加調(diào)度的復雜性并會產(chǎn)生較高的風險,所以在起重機調(diào)度過程中一般嚴禁兩臺起重機之間的交叉作業(yè).也就是說,當其中一臺起重機正在裝載(卸載)某個船艙時,該起重機右側(cè)的任何一臺起重機都不允許同時處理此船艙左側(cè)的其他船艙,同樣地,該起重機左側(cè)的任何一臺起重機也不允許同時處理此船艙右側(cè)的其他船艙,即所謂“無干涉作業(yè)”(non-interference-operation).

近年來,對于港口碼頭起重機的調(diào)度問題引得大家的廣泛關(guān)注.對于該問題,理論上,極小化裝載(卸載)總耗時的優(yōu)化問題是NP-困難的[1-2].Lee[3]等人分別設(shè)計了啟發(fā)式算法,遺傳算法,并通過數(shù)據(jù)實驗評估算法的實際性能.其他關(guān)于該問題的啟發(fā)式算法研究可參考Lee和Chen[4],Guan[5]等人.Lim[6]等人則設(shè)計了動態(tài)規(guī)劃算法,并給出了三個最壞情況界為2的近似算法以及一個完全多項式時間近似方案(FPTAS).Lee[2]等人給出了另一個最壞情況界為2的近似算法.Liu等人[7]則針對碼頭起重機的數(shù)量為2和3的情形分別設(shè)計近似算法,并證明其最壞情況界分別為4/3和5/3.Fu和Diabat[8]設(shè)計了利用拉格朗日松弛方法來求解的數(shù)學規(guī)劃模型.Goodchild和Daganzo[9-10]首次對簡單情形下的碼頭起重機的雙循環(huán)調(diào)度給出了最優(yōu)算法.Lee[11]等人則針對一般情形的碼頭起重機的雙循環(huán)調(diào)度給出了最優(yōu)算法,找到集裝箱的最優(yōu)排序.其他相關(guān)研究參看綜述文獻[12-13].

本文則對碼頭起重機數(shù)量為3和4的情形設(shè)計近似算法,并證明其最壞情況界分別為3/2和8/5.全文安排如下,§2給出本文的符號約定以及算法描述,§3為算法的最壞情況分析,§4給出主要結(jié)論.

§2 符號說明及調(diào)度算法

記船頭到船尾的船艙依次為h1,h2,···,hn,令T={h1,h2,···,hn},船艙hj可裝載(或需卸載)的集裝箱數(shù)量為pj(＞0).在不引起混淆的情況下,也用T表示各船艙中集裝箱數(shù)量的總和,對任意X?T,也用X表示其中的所包含的集裝箱總數(shù)目,即pmax為集裝箱數(shù)量最多的船艙中所包含的集裝箱數(shù)量,即pmax=mjax pj.m臺碼頭起重機依次記為QCi(i=1,2,···,m).CA為調(diào)度算法所需的裝載(卸載)總耗時,C?為最優(yōu)解所需的裝載(卸載)總耗時.為方便起見,假設(shè)每臺起重機在單位時間內(nèi)能夠裝載(卸載)一個集裝箱.

有以上的說明,不難得到最優(yōu)解的一般性質(zhì):

引理1

接下來給出調(diào)度算法,該算法首先尋找把整艘船的集裝箱數(shù)量二等分的分割船艙,并根據(jù)該分割船艙兩側(cè)集裝箱數(shù)量的具體情況給出各個船艙在碼頭起重機上的安排.“二分”調(diào)度算法A的具體描述如下(參看圖1):

“二分”調(diào)度算法A

從整艘船中找到把集裝箱數(shù)量二等分的船艙hm,為方便起見,

令L={h1,h2,···,hm?1},R={hm+1,···,hn}.

一 三臺碼頭起重機情形:

分別將L分配給起重機QC1,將hm分配給起重機QC2,將R分配給起重機QC3,終止.

二 四臺碼頭起重機情形:

1.若L∈[0,0.4T]且R∈[0,0.4T],則將L分配給起重機QC1,將hm分配給起重機QC2,將R分配給起重機QC3,終止.

2. 若L∈[0,0.4T](或R∈[0,0.4T]),則將L(R)分配給起重機QC1(QC4),將hm分配給起重機QC2(QC3),并執(zhí)行子算法B(R,QC3,QC4),(B(L,QC1,QC2)),終止.

3. 若L∈(0.4T,0.45T]且R∈(0.4T,0.45T].則分別執(zhí)行子算法B(L,QC1,QC2)和B(R∪{hm},QC3,QC4),終止.

4. 若L∈(0.45T,0.5T](或R∈(0.45T,0.5T]),則分別執(zhí)行子算法B(L,QC1,QC2)和B(R∪{hm},QC3,QC4),(B(R,QC3,QC4)和B(L∪{hm},QC1,QC2)),終止.

子算法B(S,QCi,QCj)(i＜ j):S={hx,···,hy}(x＜y≤n),找到把S中集裝箱數(shù)量二等分的船艙hs,令S1={hx,···,hs?1},S2={hs+1,···,hy},若S1≤ S2,則將S1∪ {hs}分配給起重機QCi,將S2分配給起重機QCj;否則,將S1分配給起重機QCi,將S2∪{hs}分配給起重機QCj,終止.

下面根據(jù)子算法B(S,QCi,QCj)的描述給出如下引理:

引理2對于子算法B(S,QCi,QCj)(i＜j),若S≤0.55T,則

證由子算法描述,若S1≤S2,則將S1∪{hs}分配給起重機QCi,將S2分配給起重機QCj;否則,將S1分配給起重機QCi,將S2∪{hs}分配給起重機QCj.可知S=S1+ps+S2≤0.55T,CB=min{S1,S2}+ps,若CB=min{S1,S2}+ps≤0.4T,則由引理1可得:若CB=min{S1,S2}+ps＞ 0.4T,即S1+ps＞ 0.4T,S2+ps＞ 0.4T成立.而S1+ps+S2≤ 0.55T,故有S1＜ 0.15T,S2＜ 0.15T,進而有ps＞ 0.25T.由引理1可得:

圖1 船艙與碼頭起重機的分布情況及分割船艙

§3 最壞情況分析

定理1對于三臺碼頭起重機,“二分”調(diào)度算法A的最壞情況界不超過3/2,且是緊的.

證根據(jù)算法A的三臺碼頭起重機情形的描述:分別將L分配給起重機QC1,將hm分配給起重機QC2,將R分配給起重機QC3,則有:CA=max{L,pm,R}.

情形1: 若CA=pm,由引理1可得:

情形2: 若CA=max{L,R},由引理1可得：

下面給出緊例:T=6,其中L=2,pm=1,R=3.L是有兩個含有相等數(shù)量集裝箱的船艙構(gòu)成,R是有三個含有相等數(shù)量集裝箱的船艙構(gòu)成.此例根據(jù)三臺碼頭起重機的算法描述,可知CA=3.最優(yōu)解中,三臺機首先共同裝(卸)載R,然后將L分配給QC1,QC2,將pm分配給QC3裝(卸)載,此時C?=2,因此

定理2對于四臺碼頭起重機,“二分”調(diào)度算法A的最壞情況界不超過8/5,且是緊的.

證 情形1:由算法描述可得:CA=max{L,pm,R}.

情形1.1:CA=pm,由引理1可得:

情形1.2:CA=max{L,R},由引理1可得：

情形2: 若L∈[0,0.4T],由算法描述可得：CA=max{L,pm,min{R1,R2}+pr}.

情形2.1:CA=L,由引理1可得:

情形2.2:CA=pm,由引理1可得:

情形2.3:CA=min{R1,R2}+pr,由于執(zhí)行子算法B(R,QC3,QC4),此時S=R≤0.5T＜0.55T,由引理2可得:

同理可證R∈[0,0.4T]的情形.

情形3:由算法描述可得:CA=max{min{L1,L2}+pl,min{R1,R2}+pr}.

情形3.2:CA=min{R1,R2}+pr,由算法A執(zhí)行子算法B(R∪{hm},QC3,QC4),此時0.55T＜S=R+pm＜0.6T,進一步分析:

情形3.2.1:CA=min{S1,S2}+ps≤0.4T.則由引理1可得：.

情形3.2.2:CA=min{S1,S2}+ps＞ 0.4T.即S1+ps＞ 0.4T,S2+ps＞ 0.4T成立.由(1),可得:S1＜0.2T,S2＜0.2T.進而有ps＞0.2T.故下式成立:

考慮問題最優(yōu)解:若hs分配給QC4,即當QC4正在裝(卸)載hs時,由于無干涉作業(yè),hs右側(cè)的所有船艙S2不能夠被其他三臺起重機處理,由四臺起重機同時處理S2時,至少耗時故

若hs分配給QC3,即當QC3正在裝(卸)載hs時,QC4裝(卸)載S2提前完工,由于無干涉作業(yè),QC4需要等待QC3裝(卸)載hs完成時才能繼續(xù)工作,故

若hs分配給QC2,即當QC2正在裝(卸)載hs時,QC3,QC4同時裝(卸)載S2提前完工,由于無干涉作業(yè),QC3,QC4需要等待QC2裝(卸)載hs完成時才能繼續(xù)工作,故

同理,若hs分配給QC1,則故有:.

下面考慮CA:

(5)可靠性原則。系統(tǒng)應滿足電網(wǎng)企業(yè)運營監(jiān)測業(yè)務應用24小時可靠運行的要求，系統(tǒng)關(guān)鍵環(huán)節(jié)軟硬件資源設(shè)計采用高可用方案，保證系統(tǒng)運行的高度可靠，避免出現(xiàn)數(shù)據(jù)不及時和信息失真等現(xiàn)象。

情形3.2.2.1: 若S1≤S2,則CA=S1+ps.

情形3.2.2.2: 若S1＞S2,則CA=S2+ps.

情形4: 若L∈(0.45T,0.5T],由算法描述可得:CA=max{min{L1,L2}+pl,min{R1,R2}+pr}.若CA=min{L1,L2}+pl,由執(zhí)行子算法B(L,QC1,QC2),此時S=L≤0.5T＜0.55T.故由引理2得：若CA=min{R1,R2}+pr,由執(zhí)行子算法B(R∪{hm},QC3,QC4),此時S=R+pm＜0.55T.故由引理2得:

同理可證R∈(0.45T,0.5T]的情形.

下面給出緊例:T=10,其中L1=L2=pm=R1=R2=2.L1是有四個含有相等數(shù)量集裝箱的船艙構(gòu)成.此例根據(jù)四臺碼頭起重機的算法描述在第1步終止,可知CA=4.最優(yōu)解中,四臺機首先共同裝(卸)載L1,然后將L2,pm,R1,R2分別分配給QC1,QC2,QC3,QC4裝(卸)載,此時C?=2.5,因此

§4 結(jié)論

本文研究了在港口碼頭無干涉作業(yè)的小數(shù)量碼頭起重機調(diào)度問題,主要針對三臺及四臺碼頭起重機的情況給出了最壞情況界分別為3/2和8/5的近似算法,并給出緊例,這是全新的結(jié)果.如何將上述調(diào)度算法的設(shè)計思想推廣到任意m臺碼頭起重機的情形,以及如何考慮具有不同速率的碼頭起重機調(diào)度問題,將是本文的進一步研究方向.

[1] Lim A,Rodrigues B,Xu Zhou.A m-parallel crane scheduling problem with a non-crossing constraint[J].Naval research logistics,2007,54(2):115-127.

[2] Lee D H,Wang Huiqiu,Miao Lixin.An approximation algorithm for quay crane scheduling with non-interference constraints in port container terminals[R].Technical Report,presented at Tristan VI,Phuket,June 10-15,2007.

[3] Lee D H,Wang Huiqiu,Miao Lixin.Quay crane scheduling with non-interference constraints in port container terminals[J].Transportation Research Part E:Logistics and Transportation Review,2008,44(1):124-135.

[4] Lee D H,Chen Jianghang.An improved approach for quay crane scheduling with noncrossing constraints[J].Engineering Optimization,2010,42(1):1-15.

[5] Guan Yongpei,Yang K H,Zhou Zhili.The crane scheduling problem:models and solution approaches[J].Annals of Operations Research,2013,203(1):119-139.

[6] Lim A,Rodrigues B,Xu Zhou.Approximation schemes for the crane scheduling problem[A].In:Hagerup T,Katajainen J,eds,9th Scandinavian workshop on algorithm theory(SWAT 2004)[C].Lecture notes in computer science,vol.3111,2004,323-335.

[7] Liu Ming,Zheng Feifeng,Li Jinfeng.Scheduling small number of quay cranes with noninterference constraint[J].Optimization Letters,2015,9(2):403-412.

[8] Fu Yimin,Diabat A.A Lagrangian relaxation approach for solving the integrated quay crane assignment and scheduling problem[J].Applied Mathematical Modelling,2015,39(3):1194-1201.

[9] Goodchild A V,Daganzo C F.Double-cycling strategies for container ships and their e ff ect on ship loading and unloading operations[J].Transportation Science,2006,40(4):473-483.

[10]Goodchild A V,Daganzo C F.Crane double cycling in container ports:planning methods and evaluation[J].Transportation Research Part B:Methodological,2007,41(8):875-891.

[11]Lee C Y,Liu Ming,Chu Chengbin.Optimal Algorithm for the General Quay Crane Double-Cycling Problem[J].Transportation Science,2014:1-11.

[12]Bierwirth C,Meisel F.A survey of berth allocation and quay crane scheduling problems in container terminals[J].European Journal of Operational Research,2010,202(3):615-627.

[13]Bierwirth C,Meisel F.A follow-up survey of berth allocation and quay crane scheduling problems in container terminals[J].European Journal of Operational Research,2015,244(3):675-689.

Approximation algorithms of quay crane scheduling with non-interference constraints

ZHANG Wen-shuai1,ZHANG An1,CHEN Guang-ting1,2,CHEN Yong1
(1.School of Science,Hangzhou Dianzi Univ.,Hangzhou 310018,China;2.School of Math.&Inform.Engine.,Taizhou Univ.,Taizhou 317000,China)

In port container terminals,a vessel is usually divided longitudinally between head and tail into many holds to store containers,which must be loaded or unloaded by several quay cranes.The scheduling of quay cranes signi fi cantly in fl uences the turn-around time of a container vessel.This paper studies a problem of scheduling small number of quay cranes with non-interference constraint.The objective is to minimize the overall time of loading or unloading the containers.New scheduling algorithms are designed and analyzed for three and four quay cranes,which improve previous results on this problem.

quay cranes;scheduling;approximation algorithm;worst-case analysis

90B35;68W25

O221.7

A

:1000-4424(2016)03-0351-06

2016-03-07

2016-05-06

國家自然科學基金(11571252;11201105;11401149);浙江省自然科學基金(LY16A010015)