From Metaheuristics to Exact Methods: A CP-SAT Approach for Multi-Objective Healthcare Workforce Scheduling
2026-08-31 • Artificial Intelligence
Artificial Intelligence
AI summaryⓘ
The authors tackled the complex problem of scheduling healthcare workers, which involves many rules and preferences. They created a new method called CP-SAT that follows strict rules perfectly and balances many goals, like fair workload and break times. Their approach works with detailed shift times, multiple skills, and overnight shifts, and it performed well on various real and test datasets. The method scaled efficiently and improved service quality compared to previous solutions. Overall, the authors showed a more accurate and flexible way to schedule healthcare staff without breaking regulations.
Healthcare workforce schedulingConstraint ProgrammingNP-hard optimizationMulti-skill schedulingShift schedulingAcuity-weighted workloadBreak schedulingInter-week stabilityCross-midnight shiftsCP-SAT solver
Authors
Vipul Patel, Anirudh Deodhar, Dagnachew Birru
Abstract
Healthcare workforce scheduling is an NP-hard optimization problem requiring simultaneous satisfaction of labor regulations, coverage requirements, employee preferences and cost objectives. Existing approaches (genetic algorithms, integer programming, constraint programming) model 6-12 constraints at shift-level granularity and cannot guarantee regulatory compliance. They also lack support for multi-role, multi-skill heterogeneity, mandatory break scheduling with midpoint control, acuity-weighted workload equity, sub-shift granularity, inter-week stability, and cross-midnight shifts. This paper presents CP-SAT: a Constraint Programming formulation for multi-role, multi-skill healthcare scheduling. CP-SAT enforces 14 hard constraints guaranteeing zero regulatory violations, while optimizing 15 soft objectives via a unified weighted penalty function. Contributions include a shift-window decomposition enabling break scheduling with centrality control, acuity-weighted workload equity, multi-granularity resolution from 15 minutes to 1 day, inter-week stability, and grid-offset preprocessing mapping cross-midnight shifts into a single scheduling day without solver changes. CP-SAT is evaluated on 18 instances: five synthetic hospital units (10-33 nurses), 10 INRC-II benchmarks (5-80 nurses, up to 8-week horizons) and 3 NRP-23 compatible instances (10-25 nurses) with cross-midnight Night shifts. Results: zero hard-constraint violations across all 18 instances by construction; proven optimality on INRC-II n005w4 (objective 118, gap 0.0%, 104s); feasible schedules scaling to 179,800 variables and 351,425 constraints (80 nurses); service quality improved 50-67% over MOGA; and model size scaling near-linearly at approximately 4,400 variables per employee. The formulation enforces 29 total constraints (14 hard, 15 soft), nearly three times the industry average.