Single Track Train Scheduling

In this work we consider the Single Track Train Scheduling Problem. The problem consists in scheduling a set of trains from opposite sides along a single track. The track passes intermediate stations and the trains are only allowed to pass each other at those stations. This problem has a close relation to minimizing the makespan in a job shop scheduling problem with two counter routes and no preemption. We develop a lower bound on the objective value of the train scheduling problem which provides us with an easy solution method in some special cases. The contrast in complexity to the analogous job shop scheduling problem is highlighted. Additionally, we prove the pseudo-polynomial solvability for a more general setting of the train scheduling problem.