Modeling and solving rich quay crane scheduling problems

The quay crane scheduling problem is a core task of managing maritime container terminals. In this planning problem, discharge and load operations of containers of a ship are scheduled on a set of deployed quay cranes. In this paper, we provide a rich model for quay crane scheduling that covers important issues of practical relevance like crane-individual service rates, ready times and due dates for cranes, safety requirements, and precedence relations among container groups. Focus is put on the incorporation of so-called unidirectional schedules into the model, by which cranes move along the same direction, either from bow to stern or from stern to bow, when serving the vessel. For solving the problem, we employ a branch-and-bound scheme that is known to be the best available solution method for a class of less rich quay crane scheduling problems. This scheme is extended by revising and extending the contained lower bounds and branching criteria. Moreover, a novel Timed Petri Net approach is developed and incorporated into the scheme for determining the starting times of the discharge and load operations in a schedule. Numerical experiments are carried out on both, sets of benchmark instances taken from the literature and real instances from the port of Gioia Tauro, Italy. The experiments confirm that the new method provides high quality solutions within short runtimes. It delivers new best solutions for some of the benchmark problems from the literature. It also shows capable of coping with rich real world problem instances where it outperforms the planning approach applied by practitioners. (C) 2011 Elsevier Ltd. All rights reserved.