Investigating Explanations of Infeasibility for Test Laboratory Scheduling Problems

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.