Why is there no (better) solution? : explainability results for the multi-objective rotating workforce scheduling problem

Abstract

Scheduling ist ein wichtiger Aspekt in der industriellen Arbeit. Von der Zuweisung von Aufträgen an verschiedene Maschinen bis hin zu Schichtplänen für Mitarbeitern müssen effiziente Pläne erstellt werden, um Anforderungen abzudecken und Arbeitsvorschriften einzuhalten. Für kleine Unternehmen können solche Pläne zwar noch händisch erstellt werden, es ist jedoch schwierig, dabei den Überblick über alle Anforderungen nicht zu verlieren. Daher gibt es verschiedene Methoden, wie beispielsweise Constraint Programming und heuristische Suche, die diesen Prozess automatisieren können. Obwohl sie (optimale) Pläne erzeugen können, die den Problemspezifikationen entsprechen, kann es passieren, dass Interessenvertreter inkompatible Spezifikationen vorgeben oder dass sie mit dem resultierenden Plan nicht zufrieden sind und eine bessere Lösung verlangen. Sollte ein Programm keine Lösung finden, ist es wichtig die Gründe dafür anzugeben. Dadurch werden die Spezifikationen, die zur Unlösbarkeit beitragen, identifiziert und Lockerungen der Anforderungen vorgeschlagen, durch die das Problem lösbar wird. Auch wenn ein passender Plan für ein Problem gefunden wird, ist nicht garantiert, dass er den Vorstellungen der Interessenvertreter entspricht. Daher ist es wünschenswert, mehrere Pläne zu produzieren, die Vorteile für unterschiedliche Aspekte bieten. Dadurch ist es möglich, verschiedene Lösungen zu vergleichen und zu analysieren, welche Kompromisse gemacht werden müssen, um eine Lösung in einem bestimmten Aspekt zu verbessern.\\ In dieser Arbeit untersuchen wir das Rotating Workforce Scheduling Problem, für das wir zwei Ziele verfolgen: (1.) Die Entwicklung eines Frameworks, das Erklärungen für Instanzen mit inkompatiblen Spezifikationen generiert, und (2.) die Nutzung von heuristischen Methoden, um viele verschiedene Lösungen zu generieren und zu analysieren. Dadurch erhalten wir Einblicke in Synergien und nötige Kompromisse zwischen Spezifikationen. Wir implementieren beide Frameworks und evaluieren diese auf Benchmarks des Rotating Workforce Scheduling Problems. Wir zeigen wie Minimal Correction Sets verwendet werden können um Erklärungen für unlösbare Problem-Instanzen und Konfigurationen zu erzeugen. Zu diesem Zweck führen wir eine Fallstudie und Experimente durch die zeigen, dass Erklärungen effizient generiert werden können. Ausserdem untersuchen wir grosse Mengen an Lösungen, die wir mit unserem zweiten Ansatz generieren. Wir zeigen, dass diese Lösungsmengen effizient generiert und wie diese dargestellt werden können. Mittels der Lösungen können wir die Beziehungen zwischen Anforderungen unterschiedlicher Instanzen analysieren. Zuletzt evaluieren wir verschiedene Modifikationen des base-line Ansatzes und vergleichen diese mit dem aktuellen State-of-the-art.

Scheduling is a highly relevant aspect of industrial work. From assigning jobs to machines in a time-saving manner to creating shift plans for employees in different fields of work; schedules have to be created to ensure efficiency, cover requirements and adhere to working regulations. While schedules for smaller-scale companies can still be designed manually, keeping track of all constraints and preferences is often a notoriously difficult job. Therefore, different methods that automatise this process, such as Constraint Programming and Heuristic Search, can be employed. However, while they are able to produce (optimal) plans in terms of the problem specification, stakeholders might demand incompatible specifications or not be content with a resulting plan, wanting a ”better solution”. If no solution can be found, it is important to explain which specifications contribute to infeasibility and how the problem can be relaxed to provide a solution. If a feasible plan can be provided, it is not necessarily accepted by all the stakeholders. Therefore, it can be advantageous to provide multiple solutions with qualities in different aspects. This allows us to compare different solutions and to analyse which compromises have to be made in order to further improve a solution in a certain aspect. In this thesis we study the Rotating Workforce Scheduling Problem, for which our aim is two-fold: (1.) to develop a framework that generates explanations for instances with incompatible constraints and (2.) to use heuristic methods to provide and analyse multiple different solutions at once. This allows us to gain insights into conflicting constraints, synergies and necessary trade-offs between constraints. We implement frameworks for both aims and perform computational studies of their performances on RWS benchmarks. We show how Minimal Correction Sets can be used to provide explanations for infeasible instances and problem configurations. To do so, we perform a case study as well as experiments on (real-life) instances that reveal that explanations can be efficiently generated. Additionally, we study large sets of solutions generated by our second approach. We show that these sets of solutions can be generated efficiently and how they can be displayed. Using our resulting solutions we analyse the relationships between constraints for different instances of the problem. Lastly, we also compare and contrast modifications of the base-line approach and compare them to the current state of the art.