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.
LU Shuxiang, Lü Changhong, QIN Tao
. An algorithm based on makespan lower bound for quay crane schedule problem in container terminals[J]. Operations Research Transactions, 2020
, 24(3)
: 67
-76
.
DOI: 10.15960/j.cnki.issn.1007-6093.2020.03.005
[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.
