張文帥，張 安，陳光亭，陳 永

(杭州電子科技大學理學院，浙江 杭州 310018)

?

兩臺不同速碼頭起重機調度問題的改進分析

張文帥，張 安，陳光亭，陳 永

(杭州電子科技大學理學院，浙江 杭州 310018)

碼頭起重機；調度；近似算法；最壞情況分析

0 引 言

1 符號說明及近似算法

引理1[4]C*≥T/(s+1).

算法A[4]在以下兩個調度方案中選取較好的一個輸出并終止：

方案一：將全部船艙都分配給QC2處理.

方案二：從船頭到船尾將船艙分為兩部分使得左側部分船艙總耗時為T/(s+1)，右側部分船艙總耗時為Ts/(s+1)：

1)若不存在兩側公用的船艙(稱為交叉船艙)，則將左、右兩側的船艙分別分配給QC1和QC2處理.

(1)

此時若L≥R/s，則將前i個船艙分配給QC1，其余分配給QC2；否則將前i-1個船艙分配給QC1，其余分配給QC2.

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

2 最壞情況分析

對算法A，文獻[4]給出如下結論：

以下給出算法A的改進分析.

方案二：根據(jù)該方案的描述有如下公式成立：

x+pi+y=T.

(2)

注意到文獻[4]在證明算法界時沒有對最優(yōu)解進行更詳細的討論.事實上，由于碼頭起重機之間在裝載(卸載)時需要滿足無交叉作業(yè)約束，所以，當hi分配給QC1時，有：

(3)

當hi分配給QC2時，有：

(4)

根據(jù)算法解以及上述最優(yōu)解的不同取值分情況討論如下：

情形1 L≥R/s，則將前i個船艙分配給QC1，其余分配給QC2.此時CA=x+pi.根據(jù)式(1)、式(2)及L≥R/s，有：

x≤y/s.

(5)

x>y/s.

(6)

圖2 算法界的比較

3 結束語

[1]KIM K H, PARK Y M. A crane scheduling method for port container terminals[J]. European Journal of Operational Research, 2004, 156(3)：752-768.

[2]張文帥，張安，陳光亭，等.一類無干涉作業(yè)的碼頭起重機調度問題的近似算法研究[J].高校應用數(shù)學學報，2016，31(3)：351-356.

[3]LIM A，RODRIGUES B，XU Z.A m-parallel crane scheduling problem with a non-crossing constraint[J]. Naval Research Logistics，2007，54(2)：115-127.

[4]LIU M，ZHENG F，XU Y，et al. Approximation algorithm for uniform quay crane scheduling at container ports[J]. Discrete Mathematics Algorithms & Applications，2014. DOI：http://dx.doi.org/10.1142/S179383091650018X.

[5]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.

[6]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.

Better Analysis of Scheduling Two Uniform Quay Cranes with Non-interference Constraints

ZHANG Wenshuai, ZHANG An, CHEN Guangting, CHEN Yong

(SchoolofScience,HangzhouDianziUniversity,HangzhouZhejiang310018,China)

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

10.13954/j.cnki.hdu.2016.06.020

2016-04-18

國家自然科學基金資助項目(11571252，11401149)；浙江省自然科學基金資助項目(LY16A010015)

張文帥(1990-)，男，河北滄州人，碩士研究生，組合優(yōu)化.通信作者：陳光亭教授，E-mail：gtchen@hdu.edu.cn.

O221.7

A

1001-9146(2016)06-0092-04