Exact and heuristic approaches for unrelated parallel machine scheduling

Abstract

Parallel-Machine-Scheduling-Probleme wurden vielfach in der wissenschaftlichen Literatur untersucht und sind häufig in der Industrie anwendbar. Diese Diplomarbeit beschäftigt sich mit einem praktisch auftretendem Problem, welches als Unrelated Parallel-Machine- Scheduling-Problem mit sequenzabhängigen Umrüstzeiten, Fälligkeitsterminen und Einschränkungen für die Verwendung der Maschinen beschreiben lässt. Das Ziel ist die Minimierung der gesamten Verspätung und Produktionsdauer. Da bereits existierende mathematische Formulierungen nicht direkt auf unser Problem anwendbar sind, erweitern wir verschiedene bestehende Formulierungen für verwandte Probleme und passen sie auf unser Problem an. Des weiteren stellen wir mehrere Varianten von Simulated Annealing vor, welche wir zum Lösen sehr großer Problem-Instanzen verwenden. Als Teil dieser Algorithmen verwenden wir verschiedene Suchnachbarschaften und untersuchen die Verwendung zusätzlicher innovativer Heuristiken zur Auswahl benachbarter Lösungen. Wir verwenden die neu generierten Probleminstanzen zusammen mit bestehenden Instan- zen aus der Literatur, um die vorgestellten mathematischen Modelle und metaheuristi- schen Algorithmen auszuwerten. Die praktischen Resultate zeigen, dass unsere gewählten Methoden in der Lage sind, die Resultate der bisher besten Methoden zu verbessern.

Parallel Machine Scheduling problems have been subject of intensive research and have many applications in the manufacturing industry. In this thesis, we study a real-life scheduling problem that can be formulated as an Unrelated Parallel Machine Scheduling Problem with Sequence-Dependent Setup Times, Due Dates, and Machine Eligibility Constraints. The aim is to minimise total tardiness and makespan. As existing formulations from the literature cannot be directly applied to our problem, we extend and adapt different mathematical models for related problems to approach the problem. Furthermore, we propose several variants of Simulated Annealing to solve very large-scale problem instances as they appear in practice. In these algorithms, we utilise several different search neighbourhoods and additionally investigate the use of innovative heuristic neighbourhood move selection strategies. Further, we provide a set of real-life problem instances as well as a random instance generator that we use to generate a large number of instances. Using the novel datasets together with existing instances from the literature, we perform a thorough evaluation of the mathematical models and meta-heuristic algorithms that are studied in this thesis. Experimental results show that our methods are able to improve the results produced with state-of-the-art approaches for a large number of instances.