Kirsten Albrecht
Zentrum für Angewandte Informatik Köln
Universität zu Köln

Wo bleibt der Aufzug?

Die Ablaufplanung für Aufzüge soll mit Hilfe des folgenden Online Transportproblems bearbeitet werden: Personen sollen zwischen Knoten eines Graphen transportiert werden. Hierbei treten die Anfragen online auf, in denen die zu transportierenden Personen, sowie ihr Quell- und ihr Zielknoten bestimmt werden.
Ein Server, der seine Arbeit an einem bestimmten Anfangsknoten aufnimmt, arbeitet diese Anfragen ab und kehrt am Ende zu seinem Anfangsknoten zurück. Es soll ein Fahrplan entwickelt werden, dessen Gesamtlaufzeit minimal ist. Hierzu wird definiert, wann ein Online Algorithmus c-wettbewerbsfähig ist (mit einer Konstanten c). Diese Konstante wird im folgenden für verschiedene Strategien des Servers bestimmt.