Combining Heuristics and Machine Learning for Hybrid Flow Shop Scheduling Problems
This dissertation presents a new generic scheduling approach to makespan and flowtime minimization in hybrid flow shops with unrelated machines. In addition, possibilities of utilizing machine learning tools in job scheduling are explored.
The proposed scheduling approach is twofold. First, a new heuristic
based on the divide et impera strategy is introduced, that can be optionally
enhanced by different local search improvement schemes. Moreover, several
parameters are provided that enable a trade-off between solution quality and
computation time.
Then, a new hybrid variant of the heuristic is presented,
that drastically reduces computation times through the application of machine
learning techniques.
Initially, the formal problem definition is given in form of a mixed integer linear programming formulation, and, based on an extensive literature review,
the research gap is outlined.
To evaluate the performance of the new approach, a testbed representing various production settings is introduced. Due to the 102, NP-hardness of the problem, optimal solutions cannot be determined for all instances.
Therefore, several lower bounds are proposed for makespan minimization. Additionally, the
well-known heuristic of Nawaz et al. (1983) is considered as benchmark for
makespan and flowtime, as well as solutions of the mathematical optimization
model determined in a specified time limit.
A t-test for paired, dependent samples is conducted to statistically validate the results of the new approach. Furthermore, stability aspects of the results are evaluated and a study on computation times is included. Lastly, possible scope for future work is highlighted.
Die vorgelegte Dissertation stellt einen neuen generischen Planungsansatz zur Minimierung von Makespan und Flowtime in hybriden Flowshops mit nichtidentischen Maschinen vor. Darüber hinaus werden Möglichkeiten des Einsatzes von Methoden des maschinellen Lernens in der Maschinenbelegungsplanung untersucht.
Der vorgeschlagene Planungsansatz ist zweigeteilt. Zunächst
wird eine neue Heuristik auf Basis der Divide-et-Impera-Strategie eingeführt,
die optional durch verschiedene lokale Suchheuristiken ergänzt werden kann.
Zusätzlich verfügt die Heuristik über Parameter, die eine Steuerung des Kompromisses zwischen Lösungsqualität und Rechenzeit ermöglichen. Im zweiten
Teil wird eine neue hybride Variante des heuristischen Lösungsansatzes vorgestellt, bei der durch den Einsatz von maschinellen Lerntechniken die Rechenzeiten drastisch reduziert werden kann.
Zunächst wird die formale Problembeschreibung in Form eines gemischt ganzzahligen linearen Optimierungsproblems dargestellt und, auf der Grundlage
einer umfangreichen Literaturrecherche, die Forschungslücke skizziert.
Zur Bewertung des neuen Ansatzes wird ein repräsentatives Testbed eingeführt, welches verschiedene Produktionsumgebungen modelliert. Aufgrund der NP-Vollständigkeit des Problems können nicht für alle Instanzen optimale Lösungen gefunden werden. Daher werden verschiedene untere Schranken für die Makespan-Minimierung entwickelt. Darüber hinaus wird die etablierte Heuristik von Nawaz et. al. (1983) als Benchmark für Makespan und Flowtime verwendet. Zudem werden die Lösungen des mathematischen Optimierungsmodells mit vorgegebener Rechenzeit als Vergleichsgrößen herangezogen.
Zur statistischen Validierung der Ergebnisse des neuen Ansatzes wird ein t-Test für abhängige Stichproben durchgeführt. Weiterhin werden Stabilitätsaspekte der Ergebnisse evaluiert und eine Studie über die Rechenzeiten durchgeführt. Schließlich wird auf mögliche Forschungsfragen für zukünftige Arbeiten hingewiesen.