A crane scheduling method for port container terminals. (English) Zbl 1062.90027

Summary: This paper discusses the problem of scheduling Quay Cranes (QCs), the most important equipment in port terminals. A mixed-integer programming model, which considers various constraints related to the operation of QCs, was formulated. This study proposes a branch and bound (B \(\and\) B) method to obtain the optimal solution of the QC scheduling problem and a heuristic search algorithm, called greedy randomized adaptive search procedure (GRASP), to overcome the computational difficulty of the B \(\and\) B method. The performance of GRASP is compared with that of the B \(\and\) B method.


90B35 Deterministic scheduling theory in operations research
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C27 Combinatorial optimization
Full Text: DOI


[1] Brown, G. G.; Lawphongpanich, S.; Thurman, K. P., Optimizing ship berthing, Naval Research Logistics, 41, 1-15 (1995) · Zbl 0800.90579
[2] Cheung, R. K.; Li, C.-L.; Lin, W., Interblock crane deployment in container terminals, Transportation Science, 36, 1, 79-93 (2002) · Zbl 1065.90514
[4] Cojeen, H. P.; Dyke, P. V., The automatic planning and sequencing of containers for containership loading and unloading, (Pitkin; Roche; Williams, Ship Operation Automation (1976), North-Holland Publishing Co)
[5] Daganzo, C. F., The crane scheduling problem, Transportation Research Part B, 23B, 3, 159-175 (1989)
[6] Feo, T. A.; Resende, M. G.C., Greedy randomized adaptive search procedures, Journal of Global Optimization, 6, 109-133 (1995) · Zbl 0822.90110
[8] Guinet, A., Scheduling sequence-dependent jobs on identical parallel machines to minimize completion time criteria, International Journal of Production Research, 31, 7, 1579-1594 (1993)
[9] Kim, K. H.; Kim, K. Y., An optimal routing algorithm for a transfer crane in port container terminals, Transportation Science, 33, 1, 17-33 (1999) · Zbl 1002.90508
[10] Lee, Y. H.; Pinedo, M., Scheduling jobs on parallel machines with sequence-dependent setup times, European Journal of Operational Research, 100, 3, 464-474 (1997) · Zbl 0917.90193
[11] Lim, A., The berth planning problem, Operations Research Letters, 22, 105-110 (1998) · Zbl 0911.90283
[12] Narasimhan, A.; Palekar, U. S., Analysis and algorithms for the transtainer routing problem in container port operations, Transportation Science, 36, 1, 63-78 (2002) · Zbl 1065.90511
[13] Peterkofsky, R. I.; Daganzo, C. F., A branch and bound solution method for the crane scheduling problem, Transportation Research Part B, 24, 3, 159-172 (1990)
[14] Zhang, C.; Wan, Y.-W.; Liu, J.; Linn, R. J., Dynamic crane deployment in container storage yards, Transportation Research Part B, 36, 537-555 (2002)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.