Crane scheduling in a shipbuilding environment

This paper describes exact and heuristic approaches for scheduling multiple cranes that service a shipyard that produces multiple ships concurrently. Cranes transport a variety of materials over a shared network of tracks; therefore, inter-crane interference is a major factor affecting makespan and crane utilization. The exact approach models the problem as a multi-commodity flow problem with side constraints on a network. The corresponding integer programming formulation is solved using CPLEX. The heuristics proposed decompose the problem in two sub-problems: a scheduling problem that determines the order in which jobs should be performed, and an assignment problem that assigns cranes to jobs. Computational results show that using the Priority/ACO (ant colony optimization) heuristic gives high quality solutions.