Scheduling Rail-mounted Cranes - Algorithms and Complexity

Die Parallelisierung von Teilschritten gehört zu den wichtigsten Gliedern einer funktionierenden Logistikkette bei der Bewältigung von Aufgaben in kürzest möglicher Zeit. Viele Anwendungen in der Industrie, wie zum Beispiel die Verladung von Containern oder das Stapeln von Zwischenprodukten in der Stahlverarbeitung, beinhalten Transporte, bei denen Güter an einer bestimmten Stelle aufgehoben und an einer anderen abgelegt werden. Um die Abwicklungszeit zu minimieren, kommen mehrere an Schienen montierte Kräne simultan zum Einsatz. Dabei können die Kräne ihre initialen Reihenfolge nicht verändern. Eine vollständig parallele Ausführung der Transporte ist durch diese Einschränkung oft unmöglich und anspruchsvolle Planung wird unabdingbar. Die Arbeit Scheduling Rail-mounted Cranes beschreibt ein Modell, das mit kollisionsfreien Bewegungen von mehreren Kränen bei der Bearbeitung aller Aufträge umgehen kann. Eine Analyse der Komplexität differenziert die leichten von den schweren Spezialfällen des Problems. Für die eingeführte Fragestellung werden approximative sowie exakte Algorithmen entwickelt. In einer experimentellen Rechenanalyse werden die vorgeschlagenen Heuristiken auf eine Reihe von typischen Instanzen angewendet, um die theoretischen Resultate mit praktischen Herangehensweisen zu ergänzen.