In this talk we present an exact algorithm for the Lock Scheduling Problem (LSP) based on a Combinatorial Benders’ decomposition.

LSP consists of three strongly interconnected sub problems: scheduling lockages, assigning ships to chambers, and positioning the ships inside the chambers.
These should be interpreted respectively as a scheduling, an assignment, and a packing problem. By combining the first two problems into a master problem and using the packing problem as a sub problem, a decomposition is achieved that can be solved efficiently using a Combinatorial Benders’ approach.

1. First the master problem is solved, thereby sequencing the ships into a number of lockages.
2. Next, for each lockage, a packing sub problem is checked for feasibility, possibly returning a number of combinatorial inequalities (cuts) to the master problem. Experiments are conducted on generated real world instances.

The results indicate that the decomposition approach significantly outperforms other exact approaches previously presented in literature, in terms of solution quality and computation time.