PaperlayerView exact revision on arXiv

Source-linked AI summary

From Metaheuristics to Exact Methods: A CP-SAT Approach for Multi-Objective Healthcare Workforce Scheduling

Vipul Patel, Anirudh Deodhar, Dagnachew Birru

arXiv:2608.30419v1cs.AImath.OC

TL;DR

Healthcare workforce scheduling must satisfy NP-hard combinations of labor, coverage, skill, preference, and cost requirements, while existing approaches lack guaranteed compliance and richer scheduling features. This paper presents CP-SAT with structurally enforced hard constraints and weighted soft objectives, producing compliant schedules across 18 instances, including proven optimality on one benchmark and scaling to 80 nurses.

  • Problem

    Healthcare workforce scheduling is an NP-hard problem requiring simultaneous labor-law compliance, coverage, skill, preference, and cost satisfaction, while existing approaches lack feasibility guarantees and several richer scheduling capabilities.

  • Method

    CP-SAT encodes 14 requirements as hard constraints and optimizes soft objectives through weighted scalarization, with grid-offset preprocessing supporting cross-midnight shifts without solver changes.

  • Results

    CP-SAT produced zero regulatory violations across 18 instances, proved optimality on n005w4 at objective 118 with a 0.0% gap in 104 seconds, and scaled to 80 nurses with 179,800 variables and 351,425 constraints.

  • Takeaways & Limitations

    The evaluation supports regulation-compliant healthcare schedules with configurable granularity, while shift-level models provide tighter gaps and hourly models provide sub-shift control.

  • Takeaways & Limitations

    Existing exact formulations struggled with instances exceeding 30 nurses, and a single grid offset does not suffice for shifts spanning more than 24 hours.

Abstract

from arXiv · show

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.

1 Introduction

Healthcare workforce scheduling is an NP-hard operational problem requiring compliant assignments across regulations, coverage, skills, preferences, and costs. The paper addresses limitations in existing methods with a richer CP-SAT formulation and quantified contributions.

  • Motivation: Healthcare scheduling must satisfy labor law, coverage, skill, preference, and cost requirements across recurring hospital planning cycles.Violating a single labor regulation can constitute non-compliance and pose patient-safety risks.
  • Limitations: Existing scheduling systems typically model 6-12 shift-level constraints across metaheuristic, exact, and benchmark formulations.The paper identifies this as the prevailing constraint complexity in the literature.
  • Limitations: Existing approaches lack feasibility guarantees, richer constraint expressiveness, cross-midnight support, flexible granularity, and demonstrated scalability for rich exact models.The cited limitations include penalty-based regulation handling, omitted breaks and workload equity, day-independent shift modeling, and scalability concerns.
  • Contributions: CP-SAT addresses these gaps with 14 hard constraints, 15 soft objectives, and a 29-constraint model for heterogeneous healthcare scheduling.The contributions include mandatory break centrality, acuity-weighted workload equity, inter-week stability, and cross-midnight support.

2 Related Work

Prior nurse-scheduling research spans metaheuristics, exact optimization, and standardized benchmarks. These traditions provide different trade-offs in search, optimality certification, and evaluation structure, while public benchmarks expose cross-midnight scheduling challenges.

  • Metaheuristics: Metaheuristic research includes genetic algorithms, variable-neighborhood search, harmony search, and Pareto-front methods such as NSGA-II.These methods target violation reduction, local improvement, or trade-off analysis among competing objectives.
  • Exact methods: Exact approaches use integer programming and constraint programming, with early implementations limited by instance size and modern CP-SAT combining propagation, satisfiability, and LP relaxations.The related work describes parallelism, clause learning, and symmetry breaking as CP-SAT capabilities.
  • Benchmarks: INRC-II standardizes 11 constraints and XML instances ranging from 5 to 100 nurses across 1- to 8-week horizons.Its instances include shift types, contracts, and weekly requirements.
  • Benchmarks: INRC-II and NRP-23 both include cross-midnight Night shifts, motivating the paper’s grid-offset contribution.NRP-23 additionally uses Day, Evening, and Night patterns with full-time and part-time contracts.

3 Problem Formulation

The formulation separates regulatory feasibility from quality optimization through hard constraints, soft penalties, structured shift variables, and configurable temporal resolution. It also preprocesses cross-midnight shifts so they fit the day-indexed model.

  • 3.1 Problem Setting: The model assigns employees to discrete time slots over a seven-day horizon while satisfying hard feasibility conditions and minimizing weighted soft penalties.Soft penalties measure staffing quality, employee well-being, and schedule stability.
  • 3.1 Problem Setting: Regulatory compliance is represented by 14 inviolable hard constraints, while coverage quality and employee satisfaction are optimized through 15 soft objectives.This separates feasibility from preference ranking.
  • 3.1 Problem Setting: The formal model uses assignment variables x alongside shift-window w, break b, and day-activity y variables.The formal statement includes demand, skills, availability, preferences, roles, and labor parameters.
  • 3.2 Grid-Offset Preprocessing: Grid-offset preprocessing re-indexes the daily slot grid so cross-midnight shifts occupy one contiguous scheduling day without solver modifications.A Night shift spanning 22:00-07:00 otherwise crosses two independently modeled calendar days.
  • 3.3 Decision Variables: The shift-window identity x = w − b distinguishes off-shift, active-work, and break slots, enabling mandatory break scheduling without quadratic constraints.The day-active variable y is linked to the maximum assignment value across slots.
  • 3.4 Objective Function: CP-SAT aggregates 15 soft constraints into one weighted penalty function while encoding hard constraints directly in the model.Configurable weights can implement rewards through negative values.
  • 3.5 Multi-Granularity Temporal Resolution: The formulation supports 13 temporal granularities from 15 minutes to 1 day, with complexity O(|E| · |D| · T^2).Moving from 30-minute to 1-hour slots reduces variables by approximately four times.
  • 3.5 Multi-Granularity Temporal Resolution: The constraint model uniquely combines formal feasibility guarantees with break scheduling, workload equity, and cross-midnight support.This combination is identified as absent from prior systems in the cited comparison.

4 Experimental Setup

The evaluation combines synthetic scalability tests, comparisons on five hospital units, and public INRC-II and NRP-23-compatible benchmarks. It varies team size, horizon, shift structure, and temporal granularity across heterogeneous nurse datasets.

  • Evaluation Design: The evaluation uses synthetic scalability and granularity tests, baseline comparisons, and INRC-II and NRP-23 benchmark evaluations.Experiments ran with Python 3.11 and OR-Tools v9.12 on a 16-core, 32 GB RAM machine.
  • Synthetic Benchmark: The synthetic benchmark uses a 4 × 3 × 3 factorial design covering 36 team-size, horizon, and granularity configurations.This design systematically varies the three experimental factors.
  • Synthetic Hospital Units: Five synthetic hospital units contain 10-33 employees over seven days with heterogeneous roles, skills, employment types, and unavailability declarations.The standard units use 30-minute scheduling and daytime demand from 06:00-22:00.
  • Synthetic Hospital Units: An extended 10-employee unit adds 24-hour Day, Late, and Night demand with Grid_Start_Hour = 6 to test grid-offset preprocessing.This extension applies the cross-midnight test to the existing synthetic infrastructure.
  • INRC-II: INRC-II evaluation covers instances from 5 to 100 nurses across one- and four-week horizons, including cross-midnight Night shifts requiring grid offset g=7.The benchmark uses Early, Day, Late, and Night shift types.
  • INRC-II: The INRC-II setup uses 1-hour granularity with 24 slots per day for compact models, while larger instances require external benchmark downloads.n005w1 is the bundled sample and primary validated result.
  • NRP-23: NRP-23-compatible instances follow the published JSON structure with Day, Evening, and Night shifts, full-time and part-time contracts, and weekly coverage requirements.The constructed instances include weekend demand relaxation.

5 Results

Across synthetic, INRC-II, and NRP-23-compatible benchmarks, CP-SAT produced feasible schedules without hard-constraint violations while exposing trade-offs between granularity, solution quality, and model size. Shift-level formulations improved tractability and achieved proven optimality on one INRC-II instance, whereas hourly formulations supported finer control at substantially larger scale.

  • Feasibility: Zero hard-constraint violations were produced across all synthetic benchmark instances and all tested INRC-II and NRP-23-compatible instances.The reported evaluations include five synthetic units, 10 INRC-II instances, and three NRP-23-compatible instances.
  • Multi-objective comparison: CP-SAT achieved f3 = 0.0 in all five hospital units, while its higher total objective was attributed to increased staffing cost for fuller coverage.For example, Unit 1 had a total of 678 versus MOGA’s 255.8, with cost 593 versus 49.2.
  • Multi-objective comparison: CP-SAT achieved the lowest service-quality penalty in 4 of 5 hospital units, with reported penalties of 85.0, 105.0, 151.0, and 88.0.These values were compared with MOGA penalties of 169.0, 100.4, 151.2, and 263.8 for the corresponding units.
  • Model complexity: Variables and constraints scaled linearly with employee count at approximately 4,400 variables and 9,400 constraints per employee.Table 7 additionally reports that presolve reduced effective model size by 60-70%.
  • INRC-II scaling: Hourly INRC-II models produced feasible schedules through 80 nurses, reaching 179,800 variables and 351,425 constraints within a 600-second limit.The hourly expansion enabled sub-shift staffing control but produced large optimality gaps of 36-99%.
  • Shift-level results: Shift-level INRC-II scheduling solved n005w4 to proven optimality with objective 118 and gap 0.0% in 104 seconds.For n080w4, the shift-level model used 36,980 variables versus 179,800 at 1-hour granularity, a 4.9× reduction.
  • NRP-23 granularity: NRP-23 hourly models produced objectives 15-26× larger than shift-level models, while the n010w4 shift-level gap was 13.6% versus 77.2% hourly.The results identify granularity selection as a determinant of solution quality and model tractability when sub-shift control is unnecessary.

6 Discussion

The discussion frames CP-SAT’s feasibility guarantees and richer capabilities as operationally valuable, while showing that granularity and objective weights determine the cost–quality trade-off.

  • Operational trade-offs: CP-SAT structurally enforces 14 hard constraints, making every returned schedule regulation-compliant rather than merely penalizing violations.The paper links this guarantee to patient-safety and legal implications, while acknowledging higher staffing cost than MOGA in most units.
  • Granularity and optimality: Shift-level granularity produces tighter gaps and proven optimality, whereas hourly granularity supports sub-shift control but creates larger models and gaps.The paper recommends shift-level scheduling by default and hourly resolution when break placement or partial-hour coverage is genuinely required.
  • Cross-midnight scheduling: The grid-offset transformation represents cross-midnight shifts on one scheduling day without adding solver variables, constraints, or search changes.It applies to any dataset with cross-midnight shifts and composes with slot-indexed scheduling solvers; shifts longer than 24 hours exceed the stated limitation.
  • Capability comparison: CP-SAT uniquely combines break scheduling, workload equity, and feasibility guarantees across the compared benchmark standards.The comparison covers eight capability dimensions against INRC-II and NRP-23.
  • Objective trade-offs: The weighted objective scalarizes the multi-objective problem, with planner-selected weights determining which compliant schedule is preferred.Sweeping the weight vector traces the Pareto front, complementing metaheuristics that approximate the whole front.

7 Conclusion and Future Work

The paper concludes that CP-SAT provides exact feasibility, cross-midnight support, scalable compliant schedules, and granularity-dependent solution quality. Future work targets large slot-level optimality gaps and stronger multi-week evaluation.

  • Conclusion: Zero regulatory violations occurred across all 18 instances because CP-SAT enforces 14 hard constraints as model requirements.The conclusion also reports cross-midnight validation across INRC-II, NRP-23 compatible, and synthetic 24-hour data.
  • Conclusion: All 10 INRC-II instances and all 3 NRP-23 compatible instances returned regulation-compliant schedules within the 600-second budget.The evaluated INRC-II instances span 5–80 nurses, with models reaching 179,800 variables.
  • Conclusion: Shift-level granularity yields tight gaps and proven optimality on n005w4, while hourly granularity trades larger gaps for sub-shift control.This establishes granularity as a solution-quality and control choice rather than only a computational setting.
  • Future Work: Future work proposes Benders decomposition or column generation to tighten gaps on large slot-level instances and multi-week rolling-horizon evaluation.The proposed evaluation would capture inter-week coupling effects that increase problem difficulty.
  • Future Work: Additional directions include learned demand forecasting, data-fitted preference and fairness models, multi-site routing, and natural-language constraint re-specification.These extensions target demand planning, soft-objective refinement, cross-site scheduling, and interactive schedule editing.

A.1 Hard Constraints (Guaranteed Satisfaction)

The hard-constraint set is documented as a guaranteed-satisfaction component of CP-SAT, distinguishing inviolable requirements from optimized preferences.

  • A.1 Hard Constraints: Table 14 lists 14 hard constraints guaranteed in every CP-SAT feasible solution.H1–H7 correspond to MOGA’s f3 components but are enforced rather than penalized; H10–H14 are new constraints absent from MOGA.

A.2 Soft Constraints (Weighted Optimization)

The soft-constraint set defines the quality dimensions optimized after hard feasibility has been guaranteed.

  • A.2 Soft Constraints: Table 15 lists 15 soft constraints used for weighted optimization in CP-SAT.S1–S8 correspond to components of MOGA’s f1 and f2, while S9–S15 introduce new quality dimensions.

A.3 Workload Equity (Min-Max Fairness)

Workload equity is modeled as a soft constraint that compares acuity-weighted actual workload with an expected baseline and minimizes the worst employee deviation. Grid-offset preprocessing separately maps cross-midnight shifts into one scheduling day.

  • A.3 Workload Equity (Min-Max Fairness): Workload equity compares each employee’s acuity-weighted actual workload with an expected baseline based on slots worked.The workload score incorporates role, skill contribution and slot demand intensity.
  • A.3 Workload Equity (Min-Max Fairness): The min-max objective minimizes the largest workload deviation rather than averaging deviations across employees.This targets the worst-off employee’s workload imbalance.
  • A.4 Grid-Offset Preprocessing for Cross-Midnight Shift Support: Cross-midnight shifts adjust their end hour by 24 before slot mapping, keeping the shift contiguous in the scheduling representation.For example, a 07:00 end becomes hour 31 after adjustment.
  • A.4 Grid-Offset Preprocessing for Cross-Midnight Shift Support: The grid offset is selected from the earliest shift start and used to reorder inputs and restore wall-clock output times.With g=7, the Night shift maps cleanly to slots 15–23 within one scheduling day.

Appendix B: Complete Mathematical Formulation of the CP-SAT Model

Appendix B specifies the CP-SAT model’s sets, configurable parameters, shift-window variables, objective, hard constraints and workload-based soft penalties. It separates inviolable feasibility requirements from weighted quality objectives and documents solver configuration.

  • Appendix B: Complete Mathematical Formulation of the CP-SAT Model: The appendix gives the complete mathematical specification, extending MOGA with shift-window variables, hard/soft separation and seven new quality dimensions.The added dimensions are labeled S9–S15 and H10–H14.
  • B.1 Sets and Indices: The model defines its sets, indices and parameters through tables, with parameters configurable through the business configuration file.Configuration includes scheduling granularity and work-hour limits.
  • B.3 Decision Variables: The shift-window triple (x, w, b) replaces a single assignment variable and enables mandatory breaks and break-centrality optimization.The appendix identifies x, w and b as the shift-window triple, with α and β as derived boundaries.
  • B.4 Structural Identity and Shift-Window Model: The structural identity x[e, d, s] = w[e, d, s] − b[e, d, s] defines the feasible state relationship among the three binary variables.The resulting state space contains only three feasible states.
  • B.4 Structural Identity and Shift-Window Model: The shift-window model inserts mandatory breaks, optimizes break midpoint centrality and limits concurrent breaks.Shift start α and end β are derived from assigned work slots.
  • B.5 Objective Function: A weighted-sum objective combines 15 soft penalty components, each controlled by an activation flag and configurable weight.Positive weights represent penalties, while negative weights represent rewards.
  • B.6 Hard Constraints (H1–H14): Fourteen hard constraints are imposed as inviolable requirements, including empty-on-empty, unavailability and minimum floor staffing rules.Violations are structurally impossible for feasible CP-SAT solutions.
  • B.8 Workload Point Computation (for S15): Workload-point penalties combine role load, critical-skill bonuses and demand intensity to support min-max workload fairness.The objective minimizes maximum deviation from role-based workload baselines.
Loading 2608.30419v1…