The quay crane scheduling problem with nonzero crane repositioning time and vessel stability constraints

• Present a novel formulation to the QCSP.
• We consider vessel’s stability that nobody before has considered.
• We develop an efficient GA to solve the problem.
• GA compared with lower bounds derived using dynamic programming.

The continuous growth in worldwide container terminals’ traffic resulted in an increasing interest for the Quay Crane Scheduling Problem (QCSP) in research and practice. This problem consists of scheduling the discharge and load operations of the containers of a vessel by a set of quay cranes; the objective is to minimize the completion time in an attempt to increase container terminal throughput. In the literature, most of the proposed studies focus on improving model formulation and solution methods with a trend, in most recent papers, to incorporate more realistic features of the problem. Despite the importance given by practitioners to vessel stability in scheduling discharge and load operations, there is little research that considers this constraint. This paper presents a novel MIP formulation of the QCSP that takes into account vessel stability constraints. Furthermore, the proposed model is very flexible in handling various settings of the QCSP, such as those related to crane traveling time, task preemption and unidirectional quay crane operating mode. In order to tackle problem complexity, a Genetic Algorithm (GA) is proposed. Computational results validate the MIP formulation on small-sized problems and highlight the performance of the proposed GA.