最小化最大完工时间与等待时间的岸桥作业调度双目标优化及其遗传算法

doi:U691

系统管理学报 ›› 2013, Vol. 22 ›› Issue (1): 120-127.DOI: U691

最小化最大完工时间与等待时间的岸桥作业调度双目标优化及其遗传算法

范志强^{1, 2}，乐美龙¹

1. 上海海事大学物流研究中心，上海 200135；2. 河南理工大学经济管理学院，河南焦作 454000

收稿日期:2011-07-12 修回日期:2011-12-05 出版日期:2013-01-28 发布日期:2013-01-28
作者简介:范志强（1981-），男，博士生。研究方向为集装箱码头作业系统调度优化。 E-mail: fzq19810322@163.com
基金资助:
国家自然科学基金资助项目（71101088，71171129）；上海市自然科学基金创新行动计划项目（10190502500）；上海海事大学博士生创新基金资助项目（yc2011055）

A Genetic Algorithm to Minimize the Makespan and Waiting Time for the Bi-Objective Quay Crane Scheduling Problem

FAN Zhi-qiang^{1, 2}, LE Mei-long¹

1. Logistics Research Center, Shanghai Maritime University, Shanghai 200135, China; 2. School of Economic & Management, Henan polytechnic University, Jiaozuo 454000, Henan, China

Received:2011-07-12 Revised:2011-12-05 Online:2013-01-28 Published:2013-01-28

摘要/Abstract

摘要： 【摘要】分析了岸桥支援对船舶装卸作业效率的影响，指出减少岸桥等待时间，有利于加强岸桥支援，并能提高码头整体运作效率。考虑岸桥作业不可相互穿越与安全距离等特有约束，建立了岸桥作业调度双目标混合整数规划模型，其优化目标是最小化最大完工时间与岸桥等待时间。针对该问题的NP-hard特性，设计了一种遗传算法，对算法搜索空间进行了讨论，并推导了问题的一个下界。数据实验表明，所建立的模型能够在最小化最大完工时间的同时，有效地减少岸桥等待现象的发生，其算法在允许的运算时间内能获得稳定的满意解。

范志强，乐美龙. 最小化最大完工时间与等待时间的岸桥作业调度双目标优化及其遗传算法[J]. 系统管理学报,2013,22(1):120-127.

关键词: 岸桥作业调度, 岸桥等待时间, 混合整数规划, 遗传算法

Abstract: Abstract: This paper analyzes the influence of quay crane movements among several vessels on the efficiency of loading and unloading operations, and suggests that the waiting time of quay crane should be shortened to enhance the productivity of quay crane. Given the non-crossing and safety constraints, we establish a mixed integer programming model for quay crane scheduling problem, with the bi-objective to minimize the makespan of a vessel and the waiting time of the quay crane. Because of its NP-hard nature, a genetic algorithm is designed to obtain the near optimal solutions. A lower-bound is established to facilitate the effectiveness searching of the proposed algorithm. Computational study shows that the MIP model can minimize the makespan of a vessel, while effectively reduce the quay crane’s waiting time, and the algorithm can find stable and satisfying solutions in a reasonable amount of CPU time.

Key words: quay crane scheduling, quay crane’s waiting time, mixed integer programming, genetic algorithm

范志强1, 2，乐美龙1. 最小化最大完工时间与等待时间的岸桥作业调度双目标优化及其遗传算法[J]. 系统管理学报, 2013, 22(1): 120-127.

FAN Zhi-qiang1, 2, LE Mei-long1. A Genetic Algorithm to Minimize the Makespan and Waiting Time for the Bi-Objective Quay Crane Scheduling Problem[J]. Journal of Systems & Management, 2013, 22(1): 120-127.

参考文献

[1] Steenken D, Voß S, Stahlbock R. Container terminal operation and operations research：A classification and literature review[J]. OR Spectrum, 2004, 26: 3-49.
[2] Lim A, Rodrigues B, Xiao F, et al. Crane scheduling with spatial constraints[J]. Naval Research Logistics, 2004, 51 (3): 386-406.
[3] 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.
[4] Lim A R, Rodrigues B, Xu Z. A m-parallel crane scheduling problem with a non-crossing Constraint[J]. Naval Research Logistics 2007, 54 (2): 115-127.
[5] Lee D H, Wang H Q, Miao L X. Quay crane scheduling with non-interference in port container terminals[J]. Transportation Research Part E, 2008, 44 (1): 124-135.
[6] Bierwirth C, Meisel F. A fast heuristic for quay crane scheduling with interference constraints[J]. Journal of Scheduling, 2009, 12: 345-360.
[7] 曾庆成，高宇. 集装箱码头装卸桥调度优化模型与算法[J]. 计算机工程与应用，2006，42（32）：217-219.
[8] 韩笑乐，梁亮，陆志强，等. 集装箱码头岸吊作业调度建模及调度策略研究[J]. 工业工程与管理，2009，14（5）：20-26.
[9] 李晨，陆志强，陈璐. 具有岸桥碰撞和甲板约束的岸桥混合装卸作业调度优化[J]. 上海交通大学学报，2010，44（8）：1159-1164.
[10] Whitley D. The GENITOR algorithm and selection pressure: why rank-based allocation of reroductive trials is best[C]//In: Proceedings of the Third International Conference on Genetic Algorithms, San Mateo, California, USA: Morgam Kaufmann Publishers, 1989: 116-112.
[11] Davis L. Applying adaptive algorithms to epistatic domains[C]//In: Proceedings of the 9th International Joint Conference on Artificial Intelligence, Los Angeles, California, USA: Morgan Kaufmann, 1985, 162-164.
[12] Manderick B, De Weger M, Spiessens P. The genetic algorithm and the structure of the fitness landscape[C]//In: Belew, Booker Ed. Proceedings of the fourth International Conference on Genetic Algorithms, San Mateo: Morgan Kaufmann, 1991, 143-150.

最小化最大完工时间与等待时间的岸桥作业调度双目标优化及其遗传算法

A Genetic Algorithm to Minimize the Makespan and Waiting Time for the Bi-Objective Quay Crane Scheduling Problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 12

编辑推荐

Metrics

[1]	刘畅, 姚建明. 基于供应商满意度与模糊能力的服务大规模定制供应链调度优化[J]. 系统管理学报, 2020, 29(2): 273-281.
[2]	范厚明, 吴嘉鑫, 耿静, 李阳. 模糊需求与时间窗的车辆路径问题及混合遗传算法求解[J]. 系统管理学报, 2020, 29(1): 107-118.
[3]	杨华龙, 赵亮, 靳莉哲, 王征. 基于汇集预测的随机客户需求配送车辆调度问题[J]. 系统管理学报, 2019, 28(5): 917-926.
[4]	张惠珍, 刘云, 倪静. 基于客户满意度的MOVRPFTW的单亲遗传混合蚁群算法[J]. 系统管理学报, 2019, 28(5): 927-933.
[5]	葛兴浪, 刘海龙. 基于动态权重的信用评级[J]. 系统管理学报, 2019, 28(2): 285-293.
[6]	张涛1, 黄颖雷2, 邵志芳1, 张玥杰3. 分散搜索算法求解基于小流向平衡的合同计划问题[J]. 系统管理学报, 2014, 23(4): 578-584.
[7]	刘明，张培勇. 求解多旅行商问题的新混合遗传算法[J]. 系统管理学报, 2014, 23(2): 247-254.
[8]	谢文明1,2,刘晓1,2,江志斌1,2 . 基于服务型制造的再制造批量计划问题[J]. 系统管理学报, 2014, 23(2): 271-276.
[9]	李雪岩，李学伟，李雪梅. 自适应元胞遗传算法与股票市场逐利行为[J]. 系统管理学报, 2013, 22(6): 777-781.
[10]	杨娟1，袁可红2，郭海湘1，诸克军1. 煤矿危险物资多趟配送车辆路径问题[J]. 系统管理学报, 2013, 22(5): 728-736.
[11]	牛鸿蕾1，2，江可申1. 中国产业结构调整碳排放效应的多目标遗传算法[J]. 系统管理学报, 2013, 22(4): 560-566.
[12]	霍良安1，黄培清2，方星2. 基于Stackelberg博弈模型的展会人员应急疏散问题[J]. 系统管理学报, 2013, 22(3): 425-430.