关注单船桥机调度问题，指出了单船桥机的闲置会影响码头整体的运作效率。以单个集装箱为任务单位，考虑桥机移动时间、安全距离等约束，建立了最小化桥机完工时间和闲置时间的多目标规划模型。基于完工时间下界的两种不同情况：以重点贝位工作量确定和以平均工作量确定，分别设计了基于邻域搜索的启发式算法和基于贪心策略的“分割贝位”算法，并且证明了在以平均工作量确定下界的情况中该算法不会导致桥机闲置。不同规模、不同下界类型的算例表明：提出的模型与算法得到的桥机调度计划更适合实际生产作业，能够有效地逼近完工时间下界，算法运行速度较现有的研究有显著的提高。
This paper focuses on the quay crane scheduling on one vessel, and suggests that the idle of crane will affect the efficiency of the whole container terminal. We consider a single container as task unit and constrains such as quay crane's moving time and safe margin and establish a multi-objective programming model to minimize the vessel completion time and crane idle time. Noticing the lower bound of completion time, the problem will be divided into two situations:determined by the workload of key bays and determined by average workload. Respectively, we proposed the heuristic algorithm based on neighborhood search and "bay segmentation" algorithm based on the greedy strategy, and proved that in the case where the lower bound is determined by the average workload, our algorithm will not lead to idle of any cranes. The results of numerical experiments with different scales and lower bounds show that the quay crane schedule obtained by our model and algorithm are more suitable for actual production operation, and can effectively approach the lower bound of the completion time. The algorithm has a significant improvement in the speed of the algorithm with the existing research.
[1] 赖文光. 中国港口生产形势2017年回顾与2018年展望[J]. 中国港口, 2018, 308(02):13-19.
[2] Zhu Y, Lim A. Crane Scheduling with non-crossing constraint[J]. Journal of the Operational Research Society, 2006, 57(12):1464-1471.
[3] Lee D H, Qiu Wang H, Miao L. Quay crane scheduling with handling priority in port container terminals[J]. Engineering Optimization, 2008, 40(2):179-189.
[4] Daganzo C F. The crane scheduling problem[J]. Transportation Research Part B, 1989, 23(3):159-175.
[5] Liu J, Wan Y W, Wang L. Quay crane scheduling at container terminals to minimize the maximum relative tardiness of vessel departures[J]. Naval Research Logistics, 2010, 53(1):60-74.
[6] 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.
[7] Moccia L, Cordeau J F, Gaudioso M, et al. A branch-and-cut algorithm for the quay crane scheduling problem in a container terminal[J]. Naval Research Logistics, 2010, 53(1):45-59.
[8] Sammarra M, Cordeau J F, Laporte G, et al. A tabu search heuristic for the quay crane scheduling problem[J]. Journal of Scheduling, 2007, 10(4-5):327-336.
[9] Bierwirth C, Meisel F. A Fast Heuristic for Quay Crane Scheduling with Interference Constraints[M]. Dutch:Kluwer Academic Publishers, 2009, 345-360.
[10] Meisel F, Bierwirth C. A unified approach for the evaluation of quay crane scheduling models and algorithms[J]. Computers & Operations Research, 2011, 38(3):683-693.
