On the complexity of scheduling locks in sequence

We discuss a problem inspired by the practical setting of scheduling a series of locks arranged in a sequence: a setting that occurs along many inland waterways. This problem can be considered as the scheduling of a series of batching machines where each job belongs to one of two job families. In our problem setting, ships traverse a waterway from a known arrival position to a known destination position. The ships arrive at a specified moment in time and travel at a known and fixed speed. Each of the locks is characterized by a lockage duration (i.e. processing time) and a capacity (i.e. maximum batch size). We investigate the computational complexity of a number of problem variants. In particular, we show that minimizing the total waiting time for ships travelling through these locks is strongly NP-hard. This holds even when (i) there are only two locks, (ii) both locks have identical lockage duration and capacity, and (iii) all ships traverse the waterway in the same direction. We further show that, when all ships travel at a fixed and identical speed, the problem remains strongly NP-hard when ships travel the canal in two directions. To show that two-directional travel contributes fundamentally to the hardness of our problem in this setting, we also provide a polynomial-time procedure for the setting where all ships travel in the same direction.status: publishe