两台不同速码头起重机调度问题的改进分析

张文帅，张 安，陈光亭，陈 永

(杭州电子科技大学理学院，浙江 杭州 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的改进分析.

方案二：根据该方案的描述有如下公式成立：

x+pi+y=T.

(2)

注意到文献[4]在证明算法界时没有对最优解进行更详细的讨论.事实上，由于码头起重机之间在装载(卸载)时需要满足无交叉作业约束，所以，当hi分配给QC1时，有：

(3)

当hi分配给QC2时，有：

(4)

根据算法解以及上述最优解的不同取值分情况讨论如下：

情形1 L≥R/s，则将前i个船舱分配给QC1，其余分配给QC2.此时CA=x+pi.根据式(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]张文帅，张安，陈光亭，等.一类无干涉作业的码头起重机调度问题的近似算法研究[J].高校应用数学学报，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-)，男，河北沧州人，硕士研究生，组合优化.通信作者：陈光亭教授，E-mail：gtchen@hdu.edu.cn.

O221.7

A

1001-9146(2016)06-0092-04