In den nächsten 2 Wochen werden bei mir im Institut beide(!) Fahrstühle repariert. Auch wenn ich nur im 5. Stock sitze und nicht wie einige Kollegen im 8.: Da bleib ich doch lieber zuhause und beschäftige mich mit mathematischer Fahrstuhl-Theorie.
Einen mathematischen Beweis dafür, daß man besser nicht beide Fahrstühle gleichzeitig reparieren sollte, hat wohl noch niemand gefunden.
Über das Thema ‘Optimerung von Fahrstuhlsteuerungen’ gibt es aber tatsächlich mathematische Forschungsarbeiten.
Das hat zwar nichts mit meinem aktuellen Problem zu tun, ist aber jedenfalls auch interessant. Das Thema Echtzeitsteuerung von Aufzugsystemen ist 1995-2001 von einer Arbeitsgruppe am Berliner Zuse-Institut bearbeitet worden.
Der allgemein-verständliche Artikel “Wo bleibt der Aufzug?” faßt einige der Ergebnisse zusammen, ebenso wie die beiden unten abgebildeten Poster. (Siehe auch die Webseite von Jörg Rambau.)
Bei der Fahrstuhlsteuerung handelt es sich um ein sogenanntes Online-Problem, d.h. bei Beginn des Berechnungsvorgangs sind nicht alle Eingabedaten verfügbar (weil ja in Echtzeit ständig neue Anfragen dazukommen). Eine wichtige Frage ist natürlich, wie man die verschiedenen Möglichkeiten bewertet, also wie man bestimmt, ob eine Route besser ist als eine andere.
Das theoretische Verfahren zur Analyse der Online-Algorithmen heißt kompetitive Analyse: man vergleicht den Zielfunktionswert (die Zufriedenheit der Fahrgäste) einer vom Online-Algorithmus generierten Lösung bei Eingabe einer Anfrage-Sequenz mit dem Wert einer optimalen Offline-Lösung.
Ascheuer, Krumke und Rambau haben 1998 einen 2-kompetitiven Algorithmus für die Fahrstuhlsteuerung entwickelt, d.h. die vom Algorithmus vorgeschlagene Online-Lösung ist immer höchstens um einen Faktor 2 schlechter als die jeweilige Offline-Lösung.
Aus dem Artikel “Wo bleibt der Aufzug?”:
Die theoretischen Resultate sind teilweise so schwach, daß sie für die Praxis kaum Entscheidungshilfen liefern. Häufig ist der einzige Ausweg Validierung und Evaluierung durch Simulation.
Grundlage fur eine aussagekräftige Simulation ist Zugang zu realistischen Daten. Für verschiedene Aufzugsysteme wurde aufbauend auf AMSEL ein Simulationssystem entwickelt, mit dem das Verhalten der Algorithmen in praktischen Situationen evaluiert werden kann. Einige der für die Zielfunktion Makespan kompetitiven Algorithmen zeigten dabei auch gutes praktisches Verhalten für andere Zielfunktionen, die für die Praxis interessanter sind.
[…]
Während kompetitive Analyse alleine oftmals zuwenig Information uber die Leistungsfähigkeit von Algorithmen liefert, gewinnt man doch Einsicht in die Problemstruktur. Die Kombination aus theoretischer Analyse und Simulation führt dann häufig auch zu praktikablen Algorithmen, deren Lösungen (durch Simulation empirisch bewertet) erheblich besser sind als man theoretisch garantieren kann.
Unser Fahrstuhlproblem vom Anfang kann man in der Praxis also durchaus zufriedenstellend bewältigen, wenn man anhand repräsentativer Datensatze anwendungsspezische Online-Heuristiken entwirft. Gegen unerwartet massiven Andrang, z.B. direkt vor Arbeitsbeginn, oder bewußt böswillige Datensätze ist jedoch auch der beste Algorithmus machtlos.”
Quelle: Zuse-Institut
Quelle: Zuse-Institut
Kommentare (15)