Volume 12, Number 18, October 2022

The NP-Completeness of Quay Crane Scheduling Problem

  Authors

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

  Abstract

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.

  Keywords

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