×

A fast heuristic for quay crane scheduling with interference constraints. (English) Zbl 1185.90140

Summary: This paper considers the problem of scheduling quay cranes which are used at sea port container terminals to load and unload containers. This problem is studied intensively in a recent stream of research but still lacks a correct treatment of crane interference constraints. We present a revised optimization model for the scheduling of quay cranes and propose a heuristic solution procedure. At its core a branch-and-bound algorithm is applied for searching a subset of above average quality schedules. The heuristic takes advantage from efficient criteria for branching and bounding the search with respect to the impact of crane interference. Although the used techniques are quite standard, the new heuristic produces much better solutions in considerably shorter run times than all algorithms known from the literature.

MSC:

90B90 Case-oriented studies in operations research
90B35 Deterministic scheduling theory in operations research
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bierwirth, C., & Meisel, F. (2009). A survey of berth allocation and quay crane scheduling problems in container terminals (Working paper). Martin-Luther-University Halle-Wittenberg, submitted for publication. · Zbl 1176.90373
[2] Daganzo, C. F. (1989). The crane scheduling problem. Transportation Research Part B, 23(3), 159–175. · doi:10.1016/0191-2615(89)90001-5
[3] Kim, K. H., & Park, Y. M. (2004). A crane scheduling method for port container terminals. European Journal of Operational Research, 156(3), 752–768. · Zbl 1062.90027 · doi:10.1016/S0377-2217(03)00133-4
[4] Lim, A., Rodrigues, B., Xiao, F., & Zhu, Y. (2004). Crane scheduling with spatial constraints. Naval Research Logistics, 51(3), 386–406. · Zbl 1054.90036 · doi:10.1002/nav.10123
[5] Lim, A., Rodrigues, B., & Xu, Z. (2007). A m-parallel crane scheduling problem with a non-crossing constraint. Naval Research Logistics, 54(2), 115–127. · Zbl 1126.90025 · doi:10.1002/nav.20189
[6] Liu, J., Wan, Y.-W., & Wang, L. (2006). Quay crane scheduling at container terminals to minimize the maximum relative tardiness of vessel departures. Naval Research Logistics, 53(1), 60–74. · Zbl 1112.90031 · doi:10.1002/nav.20108
[7] Meersmans, P. J. M., & Dekker, R. (2001). Operations research supports container handling (Econometric Institute Report 234). Erasmus University Rotterdam.
[8] Moccia, L., Cordeau, J.-F., Gaudioso, M., & Laporte, G. (2006). A branch-and-cut algorithm for the quay crane scheduling problem in a container terminal. Naval Research Logistics, 53(1), 45–59. · Zbl 1112.90033 · doi:10.1002/nav.20121
[9] Peterkofsky, R. I., & Daganzo, C. F. (1990). A branch and bound solution method for the crane scheduling problem. Transportation Research Part B, 24(3), 159–172. · doi:10.1016/0191-2615(90)90014-P
[10] Pinedo, M. (2002). Scheduling–theory, algorithms, and systems (2nd ed.). Englewood Cliffs: Prentice Hall. · Zbl 1145.90394
[11] Sammarra, M., Cordeau, J.-F., Laporte, G., & Monaco, M. F. (2007). A tabu search heuristic for the quay crane scheduling problem. Journal of Scheduling, 10(4–5), 327–336. · Zbl 1168.90468 · doi:10.1007/s10951-007-0029-5
[12] Stahlbock, R., & Voß, S. (2008). Operations research at container terminals: a literature update. OR Spectrum, 30(1), 1–52. · Zbl 1133.90313 · doi:10.1007/s00291-007-0100-9
[13] Steenken, D., Winter, T., & Zimmermann, U. T. (2001). Stowage and transport optimization in ship planning. In M. Grötschel, S. Krumke, & J. Rambau (Eds.), Online optimization of large scale systems (pp. 731–745). Berlin: Springer. · Zbl 1004.90008
[14] Vis, I. F. A., & de Koster, R. (2003). Transshipment of containers at a container terminal: an overview. European Journal of Operational Research, 147(1), 1–16. · Zbl 1011.90005 · doi:10.1016/S0377-2217(02)00293-X
[15] Winter, T. (1999). Online and real-time dispatching problems. PhD thesis, Technical University Braunschweig.
[16] Zhu, Y., & Lim, A. (2006). Crane scheduling with non-crossing constraint. Journal of the Operational Research Society, 57(12), 1464–1471. · Zbl 1123.90042 · doi:10.1057/palgrave.jors.2602110
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.