Optimally solving the generalized serial-lock scheduling problem from a graph-theory-based multi-commodity network perspective

In this study, we propose a general model for the generalized serial-lock scheduling problem (GSLSP), innovatively from a multi-commodity network (MCN) perspective. The MCN-based approach allows the formulation of a mixed integer linear programming (MILP) model, which is capable of finding the optimal solution to the GSLSP. In order to verify the effectiveness of the proposed method, a large number of instances with various lock configurations are tested, which corroborates that the proposed MCN-based GSLSP approach attests optimality for single-lock problems with less computational burden than the conventional exact methods. It can also solve multiple series-connected lock problems to optimality within reasonable computational time. Thereafter, we also investigate the impact of a serial-lock system’s symmetry on the performance of the proposed MCN-based method when used for transferring ships.