Balancing Soft Constraints and Efficiency: The Role of Integer Linear Programming in Constraint-Based Employee Scheduling

Sammanfattning

Employee scheduling is a complex optimization problem that involves satisfying both ,hard constraints (e.g., legal regulations, shift coverage) and soft constraints (e.g., employee preferences, overtime limits). This thesis explores two approaches to solving this problem: a pure Constraint Programming (CP) model and a hybrid model combining CP with Integer Linear Programming (ILP). The models were evaluated using real-world data from a workforce management company and a synthetically generated test dataset designed to introduce higher complexity. Results show that while both methods achieved full shift coverage in the real-world scenario, the hybrid model produced schedules with lower total penalties by more effectively optimizing soft constraints. However, the hybrid method failed in overly constrained test cases where CP alone still generated partial solutions. The study highlights the strengths of ILP for fine-tuned optimization, the robustness of CP under constraint heavy conditions, and the importance of exploring open-source alternatives to commercial solvers like Gurobi.