Instance Space Analysis and Constraint Programming Models for Unrelated Parallel Machine Scheduling Problems

Abstract

Terminplanung spielt eine wichtige Rolle für viele Firmen und Institutionen, zum Beispiel zur Verbesserung der Effizienz komplexer Produktionssysteme. Es gibt verschiedene Möglichkeiten, um problemspezifische Zeitpläne zu erstellen und zu optimieren. Die Wahl eines passenden Algorithmus für eine konkrete Probleminstanz ist dabei entscheidend, da die Qualität des resultierenden Zeitplans stark variieren kann. Diese Diplomarbeit fokussiert sich auf das Unrelated Parallel Machine Scheduling Problem, ein bekanntes Optimierungsproblem mit vielen verschiedenen Varianten. Für ein tieferes Verständnis des Instanzraums dieses Problems wurde jedoch bisher wenig unternommen. Das ist aber wichtig, da existierende Instanzen aus früheren Studien einen Bias aufweisen könnten und so zu falschen Schlüssen über die Performance von Algorithmen führen. In dieser Diplomarbeit wird der Instanzraum des Unrelated Parallel Machine Scheduling Problems analysiert, um tiefere Einblicke in die Struktur des Optimierungsproblems zu gewinnen. Instanz-Eigenschaften, die unter anderem auf Graphen basieren, werden eingeführt, um die Probleminstanzen beschreiben und klassifizieren zu können. Sie ermöglichen auch die Visualisierung des Instanzraums. Es wird festgestellt, dass die generierten Instanzen aus bekannten Datensätzen sehr unterschiedliche Eigenschaften im Vergleich zu realen Instanzen aufweisen. Daher werden zusätzliche Instanzen mithilfe eines neuen Instanzengenerators erzeugt, die ähnlicher zu den realen Instanzen sind. Auf dieser erweiterten Menge an Instanzen werden vier exakte Methoden sowie vier heuristische Ansätze zur optimierung ausgewertet. Dabei wird festgestellt, dass die Anzahl an zugelassenen Maschinen pro Job einen großen Einfluss auf die Performance der untersuchten Methoden hat. Mit den gewonnenen Erkenntnissen aus diesen Experimenten können Klassifikationsmodelle trainiert werden, die versuchen, den am besten geeigneten Algorithmus für eine konkrete Instanz automatisiert auswählen. Die besten Modelle sind in der Lage, die optimale Lösung öfter zu finden als jeder einzelne Algorithmus separat betrachtet. Zusätzlich wird eine zweite Variante dieses Optimisierungsproblems betrachtet. Basierend auf den Ergebnissen der vorherigen Analyse wird ein Constraint Programming Modell, das Intervallvariablen verwendet, formuliert. Die Implementierung dieses Modells ist in der Lage, die Optimalität von Lösungen zu kleinen Instanzen in signifikant kürzerer Zeit zu beweisen als bisher bekannte exakte Lösungsmethoden. Auf größeren Instanzen kann diese Methode sogar einen heuristischen Ansatz auf einigen Instanzen übertreffen.

Scheduling plays a crucial role for many companies and institutions across various sectors. The efficiency of complex production systems can be increased, or personnel utilization can be optimized. There exist many approaches to generate and optimize such schedules. The choice of the correct algorithm for a specific problem is very important, as the quality of the schedule can vary a lot, which might have a direct impact on the expenses. This thesis focuses on the Unrelated Parallel Machine Scheduling Problem, which is a well-known problem with many variants utilizing different constraints. However, very little work has been done in the past to analyze the instance space of this problem. Existing instances used in past studies might be biased, which may lead to wrong conclusions about the performance of algorithms. This thesis analyzes the instance space to gain deeper insights into the underlying structures of the Unrelated Parallel Machine Scheduling Problem. Instance features, including graph-based and probing features, are introduced to describe and classify problem instances. These features also allow a visualization of the instance space. It is found that the existing, randomly generated instances have very different characteristics compared to the available real-life instances. Therefore, an extension to an existing instance generator is proposed to create a novel set of instances resembling real-life ones. On the combined set of instances, four exact methods and four heuristic approaches are evaluated and analyzed. It is discovered that the number of eligible machines per job greatly influences the performance of the exact methods. A comparison of the heuristics shows a similar influence of machine eligibility. Simple classification models are trained on the gathered data for automated algorithm selection. The final models are able to find the best solution more often than each algorithm or solver on its own. Additionally, another problem with an extended set of constraints is investigated. Based on the insights of the prior analysis, a Constraint Programming formulation utilizing interval variables is proposed. An implementation of this model is able to prove optimality for instances of small size significantly faster than existing exact models. Also, it finds new best solutions for larger problem instances, by outperforming a Simulated Annealing approach for some instances.