Constraint Programming Models for the Shift-Design Personnel Task Scheduling Problem

This thesis addresses a personnel scheduling problem arising from a real industrial application developed by Optit. More specifically, the focus is on the Shift-Design Personnel Task Scheduling Problem (SDPTSP), a class of workforce scheduling problems in which employee shifts are not predefined but must be generated as part of the optimization process. The company currently relies on a Mixed-Integer Linear Programming (MILP) formulation to generate workforce schedules. While MILP represents one of the most established approaches for combinatorial optimization, recent advances in Constraint Programming (CP) have demonstrated the effectiveness of CP-based methods for a wide range of scheduling applications. In particular, modern CP solvers provide specialized scheduling constructs and propagation mechanisms that naturally capture many of the temporal and logical relationships arising in workforce scheduling problems. The objective of this thesis is to investigate the suitability of Constraint Programming for the SDPTSP and to assess its performance on realistic industrial instances. To this end, a CP model based on Google's CP-SAT solver is developed and compared with the existing MILP approach currently adopted by the company. Computational experiments show that the CP formulation is highly effective on feasibility-driven instances, while the MILP model remains competitive on optimization-intensive scenarios. The results provide insights into the strengths and limitations of the two paradigms and highlight the potential of Constraint Programming as an alternative approach for workforce scheduling problems.