A multiple-crane-constrained scheduling problem in a container terminal

We consider a container terminal loading and unloading containers to and from a set of ships, and storing the containers in the terminal yard. Each ship is served by multiple quay cranes, which load and unload containers to and from ships. Containers are moved between the ships and the yard using a fleet of vehicles, each with unit capacity. The problem is (i) to determine a storage location for each unloaded container, (ii) to dispatch vehicles to containers, and (iii) to schedule the loading and unloading operations on the cranes, so as to minimize the maximum time it takes to serve a given set of ships. This problem is NP-hard, and therefore we develop a heuristic algorithm based on formulating the problem as a transshipment problem. The effectiveness of the heuristic is analyzed from both worst-case and computational points of view. (C) 2002 Elsevier Science B.V. All rights reserved.