Loading…
Thumbnail Image

Scheduling rail mounted cranes

Algorithms and complexity

Gellert, Torsten J.

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.
Parallelization is an important ingredient to solve modern logistic problems as fast as possible. Many industrial applications such as the loading of containers or the handling of intermediate products in the steel production deal with transportation tasks requiring items to be picked up at a certain position and dropped off at another one. Multiple rail-mounted vehicles can be used simultaneously in order to minimize the execution time, but they need to maintain their initial sequence. This restriction hinders the transports to be executed fully parallel and calls for sophisticated scheduling. The thesis Scheduling Rail-mounted Cranes provides a model to cope with collision-free movements of multiple cranes to process all transportation tasks. An analysis of its complexity distinguishes polynomially solvable special cases from hard ones. On the practical side, approximation algorithms as well as exact algorithms are developed. A computational study using the presented heuristics on a series of instances with typical properties augments the theoretical results by practical solution procedures.