Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-2349
Main Title: Sorting with Objectives - Graph-Theoretic Concepts in Industrial Optimization
Translated Title: Sortieren mit Zielfunktionen - Graphentheoretische Konzepte in industrieller Optimierung
Author(s): König, Felix G.
Advisor(s): Möhring, Rolf H.
Granting Institution: Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften
Type: Doctoral Thesis
Language: English
Language Code: en
Abstract: Nach einem einführenden Überblickskapitel gliedert sich die Dissertation in zwei Teile. Der erste Teil beschäftigt sich mit dem Sortieren durch Netzwerke von Stapeln. Zunächst wird eine motivierende Anwendung aus der integrierten Stahlproduktion beschrieben, die auch Gegenstand einer Industriekooperation war. Dort werden Brammen, Stahlbarren von bis zu zwölf Metern Länge und zwanzig Tonnen Gewicht, zwischen verschiedenen Produktions\-schritten auf Stapeln gelagert. Jede Bramme ist einzigartig in ihren Eigenschaften und einem festen Kundenauftrag zugeordnet. Da vor- und nachgelagerte Produktionsschritte die Brammen in unterschiedlichen Reihenfolgen verarbeiten, müssen sie im Zwischenlager sortiert werden. Die Anzahl der hierfür notwendigen Kranbewegungen ist zu minimieren, eine erste Zielfunktion für das Sortieren. Nach der mathematischen Beschreibung dieser Optimierungsaufgabe wird ein schlankeres abstraktes Modell des Problems definiert, um es theoretisch zu analysieren und so die Kernherausforderungen beim Sortieren mit Stapeln zu identifizieren. Über eine Verbindung zu verallgemeinerten Färbungsproblemen in Kreissehnenschnittgraphen werden starke Komplexitätsresultate für verschiedene Varianten des Problems bewiesen und Approximationsalgorithmen entwickelt. Schließlich wird das im Rahmen der Industriekooperation entwickelte praxistaugliche heuristische Verfahren beschrieben. Um die Güte der erzielten Lösungen zu beweisen, wird ein ge\-mischt ganzzahliges Programm für ein relaxiertes Problem aufgestellt und gelöst. Auf Praxisdaten basierende Rechenergebnisse belegen, dass die Werte der erzielten Lösungen innerhalb von $4/5$ des Optimums liegen. Im zweiten Teil der Dissertation wird ein Scheduling-Problem betrachtet, dessen Instanzen durch die Reihenfolge gegeben sind, in denen eine Menge Werkstücke bearbeitet wird. Der Wert seiner Optimallösungen ist also in einem gewissen Sinne eine weitere Zielfunktion für das Sortieren. Die motivierende Anwendung kommt wieder aus der Stahlproduktion. So genannte Coils, Rollen von Stahlblech mit einer Länge von bis zu $1500$ Metern, werden in mehreren Schichten mit einigen von hunderten verschiedenen Materialien beschichtet. Jede Schicht wird von einer eigenen Maschine aufgebracht, wobei in einigen Maschinen zwei Beschichtungsstoffe parallel vorgehalten werden können. Das Austauschen der Beschichtungsstoffe in den Maschinen, wie auch das regelmäßige Erneuern ihrer Farbwalzen, verursacht erhebliche Nebenzeiten. Das Optimierungsziel ist, durch geschicktes Vorhalten paralleler Beschichtungsstoffe und eine passende Planung der Rüstvorgänge die anfallende Nebenzeit zu minimieren. Für die Optimierungsaufgabe wird ein graphentheoretisches Modell entwickelt, so dass optimale Lösungen als maximal gewichtete unabhängige Knotenmengen in speziellen Multi-In\-ter\-vall\-gra\-phen dargestellt werden können. Im Folgenden wird die Literatur zu verwandten Problemen analysiert und um eigene Resultate ergänzt. Für die in der Anwendung vorkommenden Fälle wird eine spezielle Teilklasse dieser Graphen definiert, und sowohl Komplexitätsresultate als auch Algorithmen hergeleitet. Schließlich wird für das Anwendungsproblem auch hier ein praxistauglicher heuristischer Algorithmus entwickelt, und die Güte der erzielten Lösungen über Optimallösungen einer Relaxation bewiesen, die mit Hilfe eines Branch-and-Price Verfahrens berechnet werden. Das implementierte Softwaremodul wird gegenwärtig beim Projektpartner in der täglichen Produktionsplanung eingesetzt.
After an opening overview chapter, the thesis comprises two major parts. The first part is concerned with sorting by networks of stacks. First, a motivating application from integrated steel production is described, which was also the subject of an industry cooperation: Slabs, bars of steel of up to twelve meters length and twenty tons weight, are stored on stacks in between different steps of the production process. Every slab is unique in its characteristics and assigned to a fixed customer order. Due to different production sequences in subsequent production steps, slabs need to be sorted while in storage. The number of crane movements to achieve this is to be minimized, forming a first objective of sorting. After a concise mathematical description of the optimization task at hand, a leaner more abstract model of the problem is defined, enabling a thorough theoretical analysis and the identification of the core challenges in sorting with stacks. By means of a generalized coloring problem in the intersection graphs of chords of circles, strong hardness results for different variants of the problem are proven and approximation algorithms are developed. Finally, the practical heuristic optimization scheme developed within the industry cooperation is described. In order to prove optimality gaps for the solutions computed, a mixed integer program for a relaxed version of the problem is stated and solved. Computational results based on real-world data demonstrate that the objective values obtained lie within $4/5$ of optimality. In the second part of the thesis, a scheduling problem is considered, whose instances ensue from the order in which work pieces are processed. In a sense, the optimal objective value of these instances forms another objective of sorting. The motivating application comes again from integrated steel production. So-called coils of sheet metal with a length of up to $1500$ meters are coated with several layers out of hundreds of different coating materials. Each layer is applied by a certain coater, where some coaters can hold two coating materials simultaneously. Changing a coating material in a coater, as well as the frequent replacement of the rollers applying the coating, account for significant setup times. Goal of the optimization task is their minimization by a good choice of parallel coating materials and optimal scheduling of the ensuing setup tasks. A graph-theoretic model for this planning task is developed, where optimal solutions correspond to maximum weight independent sets in special multi-interval graphs. The literature for related graph problems is surveyed and complemented by some new results. A special graph class for the case of the application is identified, and complexity results as well as algorithms for it are devised. Finally, a practical heuristic algorithm is developed for this application as well, and the quality of its solutions is verified by optimally solving a combinatorial relaxation of the problem via branch-and-price. The implemented software module is currently being employed by the project partner for day-to-day production planning.
URI: urn:nbn:de:kobv:83-opus-25284
http://depositonce.tu-berlin.de/handle/11303/2646
http://dx.doi.org/10.14279/depositonce-2349
Exam Date: 26-Nov-2009
Issue Date: 18-Jan-2010
Date Available: 18-Jan-2010
DDC Class: 510 Mathematik
Subject(s): Graphentheorie
Optimierung
Sortieren
Stahl
Stapel
Graph Theory
Optimization
Sorting
Stacks
Steel
Usage rights: Terms of German Copyright Law
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 
Dokument_8.pdf9,05 MBAdobe PDFThumbnail
View/Open


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