The lockmaster's problem

S. Coene, F.C.R. Spieksma

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Citations (Scopus)

Abstract

Inland waterways form a natural network that is an existing, congestion free infrastructure with capacity for more traffic. The European commission promotes the transportation of goods by ship 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.

Original languageEnglish
Title of host publication11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2011
Place of PublicationDagstuhl
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages27-37
Number of pages11
Volume20
ISBN (Print)978-3-939897-33-0
DOIs
Publication statusPublished - 2011
Externally publishedYes
Event11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2011) - Saarbrucken, Germany
Duration: 8 Sep 20118 Sep 2011
Conference number: 11
http://atmos2011.mpi-inf.mpg.de/

Publication series

NameOpenAccess Series in Informatics (OASIcs)
Volume20

Conference

Conference11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2011)
Abbreviated titleATMOS 2011
CountryGermany
CitySaarbrucken
Period8/09/118/09/11
Internet address

Keywords

  • Batch scheduling
  • Complexity
  • Dynamic programming
  • Lock scheduling

Fingerprint Dive into the research topics of 'The lockmaster's problem'. Together they form a unique fingerprint.

Cite this