Online-Optimierung von Aufzugsystemen

Die effiziente Steuerung von Aufzugsystemen ist ein Problem, welches in natürlicher Weise Online-Charakter besitzt: Bei Personenbeföorderung ist zum Zeitpunkt einer Transportanfrage im allgemeinen unklar, wann die nächste Anfrage erfolgt und welchen Transportauftrag sie enthält. Auch bei Lastaufzügen in Palettenfördertürmen können in der Praxis zukünftige Aufträge in der Regel nicht vorhergesagt werden.

Ein Kennzeichen bei der Steuerung von Aufzugsystemen ist der Echtzeit-Aspekt. Bei Auftreten einer neuen Anfrage steht nur eine sehr beschränkte Rechenzeit für die Bestimmung einer neuen Lösung zur Verfügung, und eine Reaktion des Systems auf die neue Situation muß schnell erfordern, um den Durchsatz im System nicht zu bremsen.

Im allgemeinen Fall ist jedoch bereits die Offline-Version des Fahrstuhlsteuerungsproblems NP-schwer. Spezialfälle konnten hingegen als polynomial lösbar nachgewiesen werden. Durch die Komplexität des allgemeinen Fahrstuhlsteuerungsproblems ergeben sich neben der Online-Problematik weitere Schwierigkeiten für die Erstellung von effizient arbeitenden Algorithmen.

Ziel ist es, effiziente Online-Algorithmen zu entwickeln, die sowohl gute theoretische Eigenschaften (beweisbare Güte) besitzen als auch praktischen Anforderungen (insbesondere dem Echtzeit-Aspekt) genügen. Schnelle Offline-Verfahren (auch Approximations-Algorithmen) spielen hier eine nicht zu unterschätzende Rolle, da viele Online-Algorithmen Offline-Lösungen zur Reoptimierung verwenden und dafür ständig neue Instanzen eines verwandten Offline-Problems lösen müssen.

Aufbauend auf dem Simulationspaket AMSEL wurde für die Aufzugssysteme ein Simulationssystem entwickelt, das es ermöglicht, das Verhalten der Algorithmen in praktischen Situationen zu evaluieren.