兩臺(tái)不同速碼頭起重機(jī)調(diào)度問(wèn)題的改進(jìn)分析

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

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

?

兩臺(tái)不同速碼頭起重機(jī)調(diào)度問(wèn)題的改進(jìn)分析

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

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

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

0 引 言

1 符號(hào)說(shuō)明及近似算法

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

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

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

方案二：從船頭到船尾將船艙分為兩部分使得左側(cè)部分船艙總耗時(shí)為T(mén)/(s+1)，右側(cè)部分船艙總耗時(shí)為T(mén)s/(s+1)：

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

(1)

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

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

2 最壞情況分析

對(duì)算法A，文獻(xiàn)[4]給出如下結(jié)論：

以下給出算法A的改進(jìn)分析.

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

x+pi+y=T.

(2)

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

(3)

當(dāng)hi分配給QC2時(shí)，有：

(4)

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

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

x≤y/s.

(5)

x>y/s.

(6)

圖2 算法界的比較

3 結(jié)束語(yǔ)

[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]張文帥，張安，陳光亭，等.一類無(wú)干涉作業(yè)的碼頭起重機(jī)調(diào)度問(wèn)題的近似算法研究[J].高校應(yīng)用數(shù)學(xué)學(xué)報(bào)，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

國(guó)家自然科學(xué)基金資助項(xiàng)目(11571252，11401149)；浙江省自然科學(xué)基金資助項(xiàng)目(LY16A010015)

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

O221.7

A

1001-9146(2016)06-0092-04