DuEPublico 2

Dies ist unser neues Repositorium, derzeit für E-Dissertationen und ausgewählte weitere Publikationen. Weitere Informationen...

Hybrid Flow-Shop Scheduling mit verschiedenen Restriktionen : Heuristische Lösung und LP-basierte untere Schranken

Gondek, Verena

Während der Herstellung von Stahl ist es erforderlich, kontinuierlich dessen Qualität zu überwachen. Aus diesem Grund werden an verschiedenen Positionen in einem Stahlwerk fortlaufend Produktproben entnommen und analysiert. Ein großer deutscher Stahlerzeuger betreibt zu diesem Zweck ein vollautomatisiertes Labor. Die Proben werden per Rohrpost in dieses Labor gesendet und dort mit Hilfe verschiedener Maschinen untersucht. Notwendige Transporte zwischen diesen Maschinen werden unter Verwendung mehrerer Roboter durchgeführt. Die Belegungsplanung der Maschinen sowie das entsprechende Routing der Roboter bilden ein komplexes Scheduling-Problem. Dabei soll eine möglichst geringe Aufenthaltsdauer der Proben im Labor realisiert werden. Insgesamt kann diese Aufgabe als dynamisches Hybrid Flow-Shop-Problem mit Transporten und Minimierung der gewichteten Gesamtfertigstellungszeit (resp. gewichtete Gesamtflusszeit) klassifiziert werden, da die Ankunftszeit der Proben a priori nicht bekannt ist. Weil die Analyse einer Probe im Labor zudem maximal wenige Minuten dauern darf, steht nur eine sehr geringe Rechenzeit zur Lösung dieses Scheduling-Problems zur Verfügung. Die Entwicklung eines neuen Entscheidungssystems zur Optimierung der Arbeitsabläufe in einem solchen Labor ist ein Bestandteil der vorliegenden Dissertation. Dazu wird ein mehrstufiges heuristisches Lösungsverfahren entwickelt, welches auf einem Dekompositionsansatz, (engpass-orientierten) Prioritätsregeln und einer job-orientierten List Scheduling Strategie basiert. Die Arbeitsweise des Verfahrens für das Labor wird im Rahmen einer Fallstudie simuliert und die erzielten Lösungen mit dem Ist-Zustand des Labors verglichen. In der entsprechenden Analyse kann ein enormes Verbesserungspotential gegenüber dem derzeit verwendeten Planungstool nachgewiesen werden. Neben diesem anwendungsorientierten Teil der Arbeit wird die Performance des vorgestellten Verfahrens auch für allgemeinere Situationen empirisch untersucht. Zur Auswertung der erzielten Lösungen für verschiedene zufällig generierte Datensätze (insgesamt 1500 Probleminstanzen), werden zwei LP-basierte untere Schranken verwendet, welche auf einer zeit-indizierten gemischt-ganzzahligen Modellierung des Problems beruhen. Darüber hinaus werden diese Schranken auch auf theoretischer Ebene analysiert und mit weiteren in der Literatur gebräuchlichen Schranken verglichen.

During the manufacture of steel, its quality has to be monitored continuously. Therefore, samples are taken at several stages of the production process and their chemical composition is analyzed. A big German steel producer uses an automatic laboratory to perform this task. The samples are sent to this laboratory under usage of a pneumatic post system and afterwards they are processed by different machines. Arising transportation tasks between those operations are managed by a fleet of robots. The imetabling of the several machines as well as the related routing of the robots is a complex scheduling problem. Therein the flow time of the samples should be minimized. Altogether, this task can be classified as a dynamic hybrid flow-shop scheduling problem with transportation and total weighted completion time or total weighted flow time objective, because the arrival times of the samples are not known in advance. Because the analysis of one sample should at most last a few minutes, the available computational time to perform the required real-time optimization is strictly limited. The development of a decision support system to optimize the workflow in such a laboratory is one part of this dissertation. Therefore, a multi-stage heuristic algorithm is designed, which is based on a decomposition approach, (bottleneck related) dispatching rules as well as a job-oriented list scheduling strategy. The performance of this method in case of the laboratory is simulated and compared to the current control system. It can be shown that the new approach is able to reduce the total weighted flow time significantly. Beneath this application part of the thesis, the performance of the method is further evaluated in a more theoretical fashion. Therefore, an extensive empirical analysis is performed, where lower bounds are used to benchmark the heuristic solutions to 1500 random problem instances under consideration. These bounds are based on the lp relaxation of two time-indexed mixed-integer formulations of the problem. Furthermore, they are also compared to different other bounds introduced in literature.

Vorschau

Teilen und Zitieren

Zitierform:

Gondek, Verena: Hybrid Flow-Shop Scheduling mit verschiedenen Restriktionen. Heuristische Lösung und LP-basierte untere Schranken. 2011.

Rechte

Nutzung und Vervielfältigung:
Alle Rechte vorbehalten

Export