Modeling and solving rich quay crane scheduling problems

AbstractThe Quay Crane Scheduling Problem is a core task of managing maritime container terminals. In thisplanning problem, discharge and load operations of containers of a ship are scheduled on a set of deployedquay cranes. In this paper, we provide a rich model for quay crane scheduling that covers importantissues of practical relevance like crane-individual service rates, ready times and due dates for cranes, safetyrequirements, and precedence relations among container groups. Focus is put on the incorporation of socalledunidirectional schedules into the model, by which cranes move into the same direction, either frombow to stern or from stern to bow, when serving the vessel. For solving the problem, we employ a Branchand-Bound scheme that is known to be the best available solution method for a class of less rich quay cranescheduling problems. This scheme is extended by revising and extending the contained lower bounds andbranching criteria. Moreover, a novel Timed Petri Net approach is developed and incorporated into thescheme for determining the starting times of the discharge and load operations in a schedule. Numericalexperiments are carried out on both, sets of benchmark instances taken from the literature and real instancesfrom the port of Gioia Tauro, Italy. The experiments confirm that the new method provides high qualitysolutions within short runtimes. It delivers new best solutions for some of the benchmark problems fromthe literature. It also shows capable of coping with rich real world problem instances where it outperformsthe planning approach applied by practitioners.