Hybrid flow shop scheduling mit verschiedenen Restriktionen : heuristische Lösung und LP-basierte untere Schranken

Duisburg, Essen (2011), VII, 183 S.
Dissertation / Fach: Mathematik
Fakultät für Mathematik
Törner, Günter (Doktorvater, Betreuerin)
Leisten, Rainer (GutachterIn)
Duisburg, Essen, Univ., Diss., 2011
Abstract:
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.