Complexity, bounds and dynamic programming algorithms for single track train scheduling

J Harbering, A Ranade, Marie Schmidt, O Sinnen

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)

Abstract

In this work we consider the single track train scheduling problem. The problem consists of scheduling a set of trains from opposite sides along a single track. The track has intermediate stations and the trains are only allowed to pass each other at those stations. Traversal times of the trains on the blocks between the stations only depend on the block lengths but not on the train. This problem is a special case of minimizing the makespan in job shop scheduling with two counter routes and no preemption. We develop a lower bound on the makespan of the train scheduling problem which provides us with an easy solution method in some special cases. Additionally, we prove that for a fixed number of blocks the problem can be solved in pseudo-polynomial time.
Original languageEnglish
Pages (from-to)479-500
JournalAnnals of Operations Research
Volume273
Issue number1-2
DOIs
Publication statusPublished - 10 Oct 2017

Fingerprint

Dive into the research topics of 'Complexity, bounds and dynamic programming algorithms for single track train scheduling'. Together they form a unique fingerprint.

Cite this