Scheduling trams in the morning

Ulrich Blasum, Michael R. Bussieck, Winfried Hochstättler, Christoph Moll, Hans-Helmut Scheel and Thomas Winter

Mathematical Methods of Operations Research, 1999, vol. 49, issue 1, 137-148

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. Copyright Springer-Verlag Berlin Heidelberg 1999

Keywords: Key words: Combinatorial optimization; complexity; ℳ?-completeness; scheduling; assignment; stack (search for similar items in EconPapers)
Date: 1999
References: Add references at CitEc
Citations: View citations in EconPapers (11)

Downloads: (external link)
http://hdl.handle.net/10.1007/PL00020912 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:mathme:v:49:y:1999:i:1:p:137-148

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/00186

DOI: 10.1007/PL00020912

Access Statistics for this article

Mathematical Methods of Operations Research is currently edited by Oliver Stein

More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().