Explainability Results for the Rotating Workforce Scheduling Problem

Abstract

Scheduling is a highly relevant aspect of industrial work. From assigning jobs to machines to creating shift plans for employees; schedules must be created to ensure efficiency, cover requirements and adhere to working regulations. As creating schedules while keeping track of all constraints is often a notoriously difficult job, automated methods can be employed. However, sometimes no solution can be found due to conflicting problem specifications. In this case, it is important to explain which constraints contribute to infeasibility and how the problem can be relaxed. We study the Rotating Workforce Scheduling Problem, for which we develop a framework that generates explanations for instances with incompatible constraints. We show how Minimal Correction Sets can be used to provide detailed explanations for infeasible problems, caused by hard constraint violations or by conflicting optimisation goals. We perform a case study and experiments on (real-life) instances that reveal that explanations can be efficiently generated.