Investigating Explanations of Infeasibility for Test Laboratory Scheduling Problems

Abstract

Infeasibility in automated scheduling systems poses a significant challenge in many real-world applications, as conflicting constraints often prevent the generation of a feasible schedule. This thesis focuses on the infeasibility of instances of Test Laboratory Scheduling Problem (TLSP), an extension of the Resource-Constrained Project Scheduling Problem (RCPSP). Specifically, it addresses challenges faced by industrial test laboratories where a large number of tests have to be performed by qualified personnel using specialized equipment, while respecting strict temporal requirements, complex task dependencies and various other constraints. To address this challenge, we propose an infeasibility explainer that integrates two complementary approaches. The first approach is based on conflict detection: by identifying minimal unsatisfiable subsets and maximal satisfiable subsets, the explainer pinpoints the precise groups of constraints that cause infeasibility. Feasibility can then be restored by computing minimal correction subsets. The second approach employs counterfactual explanations, which offer minimal modifications to the scheduling constraints that are necessary to restore feasibility. This method leverages a multi-point relaxation space, allowing for simultaneous adjustments across multiple constraints, thereby providing a more flexible and nuanced resolution. Our methodology builds on established techniques from Constraint Satisfaction Problem (CSP) literature and extends them specifically to the TLSP domain. The infeasibility explainer is implemented using a TLSP-specific constraint programming model in OR-Tools, designed for explainability. This model is enhanced by a configurable user interface that enables users to adjust explainer settings and execute multiple configurations in parallel, thereby significantly reducing reliance on manual trial-and-error methods. Experimental evaluations, carried out on both industrial and benchmark instances, demonstrate that our approach substantially reduces the time and effort required to identify and resolve scheduling conflicts. Although the solution performs effectively on moderately-sized instances, scalability remains a challenge for very large and complex instances, suggesting a need for further optimization. The infeasibility explainer described in this thesis is already deployed in an industrial setting, where it effectively aids in resolving real-world scheduling infeasibilities.

Die mathematische Unerfüllbarkeit von Planungsaufgaben stellt in vielen realen An-wendungsgebieten eine erhebliche Herausforderung für automatisierte Planungssysteme dar, da einander widersprechende Anforderungen häufig die Erstellung eines zulässigen Zeitplans verhindern. Diese Arbeit konzentriert sich auf die Unerfüllbarkeit von Instanzen des Test Laboratory Scheduling Problems (TLSP), einer Erweiterung des Resource-Constrained Project Scheduling Problems (RCPSP). Im Speziellen behandelt sie die Herausforderungen, denen industrielle Prüflabore gegenüberstehen, in denen eine große Anzahl von Tests durch qualifiziertes Personal mit spezialisierter Ausrüstung unter Einhaltung strikter zeitlicher Vorgaben, komplexer Abhängigkeiten zwischen Aufgaben und weiterer Nebenbedingungen durchgeführt werden muss. In diesem Kontext beeinträchtigen unerfüllbare Konflikte zwischen den Anforderungen bereits in der Planungsphase die operative Effizienz und erschweren fundierte Entscheidungen in industriellen Umgebungen. Um diese Herausforderung zu bewältigen, stellen wir in dieser Arbeit ein Erklärungswerkzeug für mathematische Unerfüllbarkeiten vor, das zwei komplementäre Ansätze kombiniert. Der erste Ansatz basiert auf der Konflikterkennung: Durch Identifikation minimaler unerfüllbarer Teilmengen (Minimal Unsatisfiable Subsets) und maximaler erfüll-barer Teilmengen (Maximal Satisfiable Subsets) werden genau die Constraint-Gruppenaufgedeckt, die Unerfüllbarkeit verursachen. Die Wiederherstellung der Erfüllbarkeit erfolgt anschließend über die Berechnung minimaler Korrekturmengen (Minimal Correc-tion Subsets). Der zweite Ansatz verwendet kontrafaktische Erklärungen, die minimale Modifikationen der Anforderungen aufzeigen, die notwendig sind, um Erfüllbarkeit wiederherzustellen. Hierfür nutzen wir einen mehrstufigen Relaxationsraum, der gleichzeitige Anpassungen mehrerer Anforderungen erlaubt und so eine flexiblere und differenziertere Problemlösung ermöglicht. Unsere Methodik baut auf etablierten Verfahren aus der Constraint-Satisfaction-Problem(CSP)-Literatur auf und erweitert sie gezielt für den TLSP-Bereich. Der Unerfüllbarkeitserklärer ist mittels eines TLSP-spezifischen Constraint-Programming-Modells inOR-Tools implementiert, das auf Erklärbarkeit ausgelegt ist. Dieses Modell wird durch eine konfigurierbare Benutzeroberfläche ergänzt, die es den Anwendern ermöglicht, die Einstellungen des Erklärers anzupassen und mehrere Konfigurationen parallel auszuführen, wodurch die Abhängigkeit von manuellen Trial-and-Error-Methoden deutlichverringert wird. ixExperimentelle Auswertungen an realen und synthetischen Benchmark-Instanzen zeigen, dass unser Ansatz den Zeit- und Arbeitsaufwand zur Identifikation und Behebung von Planungskonflikten erheblich reduziert. Obwohl die Lösung für mittelgroße Instanzeneffektiv ist, bleibt die Skalierbarkeit bei sehr großen und komplexen Problemen eine Herausforderung und deutet auf weiteren Optimierungsbedarf hin.Der in dieser Arbeit vorgestellte Unerfüllbarkeitserklärer ist bereits in einem industriellen Umfeld im Einsatz und unterstützt dort wirkungsvoll bei der Behebung realer Planungsunerfüllbarkeiten.