The crane scheduling problem: models and solution approaches

In this paper, we study the crane scheduling problem for a vessel after the vessel is moored on a terminal and develop both exact and heuristic solution approaches for the problem. For small‐sized instances, we develop a time‐space network flow formulation with non‐crossing constraints for the problem and apply an exact solution approach to obtain an optimal solution. For medium‐sized instances, we develop a Lagrangian relaxation approach that allows us to obtain tight lower bounds and near‐optimal solutions. For large‐sized instances, we develop two heuristics and show that the error bounds of our heuristics are no more than 100%. Finally, we perform computational studies to show the effectiveness of our proposed solution approaches.