The Lockmaster's Problem
- 30 September 2011
- preprint
- Published by Elsevier BV in SSRN Electronic Journal
Abstract
Inland waterways form a natural network that is an existing, congestion free infrastructure with capacity for more traffic. Transportation of goods by ship is widely promoted as it is a reliable, efficient and environmental friendly way of transport. A bottleneck for transportation over water are the locks that manage the water level. The lockmaster's problem concerns the optimal strategy for operating such a lock. In the lockmaster's problem we are given a lock, a set of ships coming from downstream that want to go upstream, and another set of ships coming from upstream that want to go downstream. We are given the arrival times of the ships and a constant lockage time; the goal is to minimize total waiting time of the ships. In this paper a dynamic programming algorithm (DP) is proposed that solves the lockmaster's problem in polynomial time. We extend this DP to different generalizations that consider weights, water usage, capacity, and (a fixed number of) multiple chambers. Finally, we prove that the problem becomes strongly NP-hard when the number of chambers is part of the input.This publication has 15 references indexed in Scilit:
- Parallel batch scheduling of equal-length jobs with release and due datesJournal of Scheduling, 2010
- Optimal sequencing in the presence of setup times for tow/barge traffic through a river lockEuropean Journal of Operational Research, 2008
- Batch processing with interval graph compatibilities between tasksDiscrete Applied Mathematics, 2008
- Scheduling a batch-processing machine subject to precedence constraints, release dates and identical processing timesComputers & Operations Research, 2005
- Scheduling a batch processing machine with bipartite compatibility graphsMathematical Methods of Operations Research, 2003
- On the single machine serial batching scheduling problem to minimize total completion time with precedence constraints, release dates and identical processing timesOperations Research Letters, 2003
- Batching identical jobsMathematical Methods of Operations Research, 2000
- Scheduling a batching machineJournal of Scheduling, 1998
- Efficient Algorithms for Scheduling Semiconductor Burn-In OperationsOperations Research, 1992
- Scheduling Unit–Time Tasks with Arbitrary Release Times and DeadlinesSIAM Journal on Computing, 1981