×

zbMATH — the first resource for mathematics

A tabu search heuristic for the quay crane scheduling problem. (English) Zbl 1168.90468
Summary: This paper proposes a tabu search heuristic for the Quay Crane Scheduling Problem (QCSP), the problem of scheduling a fixed number of quay cranes in order to load and unload containers into and from a ship. The optimality criterion considered is the minimum completion time. Precedence and non-simultaneity constraints between tasks are taken into account. The former originate from the different kind of operations that each crane has to perform; the latter are needed in order to avoid interferences between the cranes. The QCSP is decomposed into a routing problem and a scheduling problem. The routing problem is solved by a tabu search heuristic, while a local search technique is used to generate the solution of the scheduling problem. This is done by minimizing the longest path length in a disjunctive graph. The effectiveness of our algorithm is assessed by comparing it to a branch-and-cut algorithm and to a Greedy Randomized Adaptive Search Procedure (GRASP).

MSC:
90B35 Deterministic scheduling theory in operations research
90B40 Search theory
90C59 Approximation methods and heuristics in mathematical programming
Software:
Tabu search
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network flows–theory, algorithms and applications. Englewood Cliffs: Prentice Hall. · Zbl 1201.90001
[2] Cordeau, J.-F., Gendreau, M., & Laporte, G. (1997). A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks, 30, 105–119. · Zbl 0885.90037
[3] Daganzo, C. F. (1989). The crane scheduling problem. Transportation Research B, 23, 159–175.
[4] Daganzo, C. F., & Peterkofsky, R. I. (1990). A branch and bound solution method for the crane scheduling problem. Transportation Research B, 24, 159–172.
[5] Gendreau, M., & Potvin, J.-Y. (2005). Tabu search. In E. K. Burke & G. Kendall (Eds.), Search methodologies: introductory tutorials in optimization and decision support techniques. Berlin: Springer.
[6] Glover, F., & Laguna, M. (1993). Tabu search. In C. R. Reeves (Ed.), Modern heuristics techniques for combinatorial problems. Oxford: Blackwell. · Zbl 0774.90033
[7] Glover, F., & Laguna, M. (1998). Tabu search. Boston: Kluwer. · Zbl 0930.90083
[8] Kim, K. H., & Park, Y. M. (2004). A crane scheduling method for port container terminals. European Journal of Operational Research, 156, 752–768. · Zbl 1062.90027
[9] Lim, A., Rodrigues, B., Xiao, F., & Zhu, Y. (2004). Crane scheduling with spatial constraints. Naval Research Logistics, 51, 386–406. · Zbl 1054.90036
[10] 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, 45–59. · Zbl 1112.90033
[11] Nowicki, E., & Smutnicki, C. (1996). A fast taboo search algorithm for the job shop problem. Management Science, 42, 797–813. · Zbl 0880.90079
[12] Pinedo, M. (1995). Scheduling–theory, algorithms and systems. Englewood Cliffs: Prentice Hall. · Zbl 1145.90393
[13] Pinedo, M., & Singer, M. (1999). A shifting bottleneck heuristic for minimizing the total weighted tardiness in a job shop. Naval Research Logistics, 46, 1–17. · Zbl 0922.90088
[14] Roy, B., & Soussmann, B. (1964). Les problèmes d’ordonnancement avec constraintes disjonctives. Note D.S. 9 bis, SEMA, Paris.
[15] Steenken, D., Voss, S., & Stahlbock, R. (2004). Container terminal operation and operations research–a classification and literature review. Operations Research Spectrum, 26, 3–49. · Zbl 1160.90322
[16] Van Laarhoven, P. J. M., Aarts, E. H. L., & Lenstra, J. K. (1992). Job shop scheduling by simulated annealing. Operations Research, 40, 113–125. · Zbl 0751.90039
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.