Scheduling Trams in the Morning

Blasum, Ulrich and Bussieck, M. and Hochstättler, Winfried and Moll, Christoph and Scheel, Hans-Helmut and Winter, Thomas (1999) Scheduling Trams in the Morning.
Published in: Mathematical Methods of Operations Research Vol. 49 (1). pp. 137-148.


In this note, we prove NP-completeness of the following problem: Given a set of trams of different types, which are stacked on sidings in their depot and an order in which trams of specified types are supposed to leave. Is there an assignment of trams to departure times without any shunting movements? For the special case where the number of sidings is fixed the problem is solvable in polynomial time. We derive a brute force and a more sophisticated implementation of the associated algorithm. Furthermore, we compare the implementations on random and real word data.

Download: [img] Postscript - Preprinted Version
Download (234kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr96-232
Depositing User: Ulrich Blasum
Date Deposited: 02 Apr 2001 00:00
Last Modified: 16 Jan 2012 15:04