Quay crane scheduling in container terminals
- 1 September 2006
- journal article
- research article
- Published by Taylor & Francis Ltd in Engineering Optimization
- Vol. 38 (6), 723-737
- https://doi.org/10.1080/03052150600691038
Abstract
The problem of scheduling identical quay cranes moving along a common linear rail to handle containers for a ship is studied. The ship has a number of container-stacking compartments called bays, and only one quay crane can work on a bay at the same time. The objective of the scheduling problem is to find the work schedule for each quay crane which minimizes the ship’s stay time in port. Finding the optimal solution of the scheduling problem is computationally intractable and a heuristic is proposed to solve it. The heuristic first decomposes the difficult multi-crane scheduling problem into easier subproblems by partitioning the ship into a set of non-overlapping zones. The resulting subproblems for each possible partition are solved optimally by a simple rule. An effective algorithm for finding tight lower bounds is developed by modifying and enhancing an effective lower-bounding procedure proposed in the literature. Computational experiments were carried out to evaluate the performance of the heuristic on a set of test problems randomly generated based on typical terminal operations data. The computational results show that the heuristic can indeed find effective solutions for the scheduling problem, with the heuristic solutions on average 4.8% above their lower bounds.Keywords
This publication has 12 references indexed in Scilit:
- Dispatching vehicles in a mega container terminalOR Spectrum, 2005
- Crane scheduling in container yards with inter-crane interferenceEuropean Journal of Operational Research, 2005
- Yard crane scheduling in port container terminalsApplied Mathematical Modelling, 2005
- Analysis of a new vehicle scheduling and location problemNaval Research Logistics (NRL), 2001
- Deriving decision rules to locate export containers in container yardsEuropean Journal of Operational Research, 2000
- A routing algorithm for a single straddle carrier to load export containers onto a containershipInternational Journal of Production Economics, 1999
- An Optimal Routing Algorithm for a Transfer Crane in Port Container TerminalsTransportation Science, 1999
- A general lower bound for the makespan problemEuropean Journal of Operational Research, 1996
- A branch and bound solution method for the crane scheduling problemTransportation Research Part B: Methodological, 1990
- The crane scheduling problemTransportation Research Part B: Methodological, 1989