Scheduling trams in the morning |
| |
Authors: | Ulrich Blasum Michael R Bussieck Winfried Hochstättler Christoph Moll Hans-Helmut Scheel Thomas Winter |
| |
Institution: | Zentrum für Paralleles Rechnen, Universit?t zu K?ln, Albertus-Magnus-Platz, D-50923 K?ln, Germany, DE Abteilung für Mathematische Optimierung, TU Braunschweig, Pockelsstra?e 14, D-38106 Braunschweig, Germany, DE Siemens AG, ZT SE 4, D-81730 München, Germany, DE
|
| |
Abstract: | In this note, we prove -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? In the particular case where the number of sidings is fixed, the problem is solvable in polynomial time. We derive a dynamic program and improve its performance by a state elimination scheme. We implemented three variants of the dynamic program and applied them to random data as well as to real-world data. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|