An Exact Approach to the Generalized Serial-lock Scheduling Problem from a Flexible Job-shop Scheduling Perspective

Abstract In this paper, the general serial-lock scheduling problem (SLSP) is studied from a new methodological angle, aiming at optimizing the process of ships passing a series of consecutive locks. For the first time in this research topic, we propose a widely applicable model for the SLSP from a flexible job-shop scheduling (FJS) perspective, integrated with a two-dimensional bin-packing problem. The FJS-based perspective allows the formulation of a mixed integer linear programming model, which is capable of solving the SLSP to optimality. Wide-ranging instances with various lock configurations and traffic scenarios are performed to test the applicability and efficiency of the proposed FJS model, which demonstrates that the FJS can optimally solve most of the instances with up to four multi-chamber locks and 20 ships. The results obtained respectively with and without the first-come-first-served restriction show that imposing this restriction can accelerate the solution process for most instances. Meanwhile, experimental results also confirm the advantage of the FJS for solving single-lock scheduling problems, compared with other existing methods. Additionally, although the experiments on the simplified SLSP without multi-type chambers nor two-dimensional ship placement demonstrate a comparable performance between the FJS-based approach and other exact methods, the majority of experimental results infer that the FJS is a more suitable candidate model for dealing with the scenarios with high-density water traffic.