No-wait scheduling for locks

We consider an operational planning problem in waterway transportation. Consider a single lock that consists of m parallel chambers. The chambers operate independently of each other and are each characterized by two numbers: their lockage time and their capacity. The term lockage time refers to the time needed to bring a ship from the downstream water level to the upstream water level, or vice versa. The capacity gives an upper bound on the number of ships that may simultaneously be present within a chamber. Ships arrive at the locks at given times. A ship can arrive either from the upstream side, or from the downstream side (this is called the position of a ship). Our interest is on the existence of so-called no-wait schedules; these are schedules in which no ship has to wait. A relevant special case is the setting with two distinct chambers, and all ships having the same position (the uni-directional case). We show how this problem is related to interval scheduling, we give necessary and sufficient conditions determining the existence of a no-wait schedule in the special case described above, and we show how to find such a schedule in linear time. We prove that the uni-directional case of the problem is NP-complete in case the number of chambers is part of the input.status: publishe