Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-4435
Main Title: Scheduling rail mounted cranes
Subtitle: Algorithms and complexity
Translated Title: Steuerung von schienengebundenen Kränen
Translated Subtitle: Algorithmen und Komplexität
Author(s): Gellert, Torsten J.
Advisor(s): Möhring, Rolf H.
Referee(s): Lübbecke, Marco
Granting Institution: Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften
Type: Doctoral Thesis
Language: English
Language Code: en
Abstract: 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.
URI: urn:nbn:de:kobv:83-opus4-65674
http://depositonce.tu-berlin.de/handle/11303/4732
http://dx.doi.org/10.14279/depositonce-4435
Exam Date: 20-Feb-2015
Issue Date: 11-May-2015
Date Available: 11-May-2015
DDC Class: 510 Mathematik
Subject(s): Transportplanung
Kollisionsvermeidung
Kransteuerung
Algorithmen
Komplexität
Vehicle scheduling
collision avoidance
crane scheduling
algorithms
complexity
Creative Commons License: https://creativecommons.org/licenses/by-sa/3.0/de/
ISBN: 978-3-7375-4251-7
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 2 Mathematik und Naturwissenschaften » Institut für Mathematik » Publications

Files in This Item:
File Description SizeFormat 
gellert_torsten.pdf28.71 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.