Ali Skaf, Samir Dawaliby, and Arezki Aberkane, Caplogy R&D, France

This paper discusses the computational complexity of the quay crane scheduling problem (QCSP) in a maritime port. To prove that a problem is NP-complete, there should be no polynomial time algorithm for the exact solution, and only heuristic approaches are used to obtain near-optimal solutions but in reasonable time complexity. To address this, first we formulate the QCSP as a mixed integer linear programming to solve it to optimal, and next we theoretically prove that the examined problem is NP-complete.

Quay crane, Container, Scheduling, Optimization, MILP, NP-complete.