CP-WSP: A Declarative CP-SAT Framework for Configurable Multi-Constraint Workforce Scheduling
2026-07-06 • Artificial Intelligence
Artificial Intelligence
AI summaryⓘ
The authors address the complex problem of workforce scheduling, which involves meeting multiple hard rules and preferences. They developed CP-WSP, a flexible framework that strictly follows 14 essential constraints and balances 15 goals using a customizable penalty system, all set up without coding changes. Their approach supports detailed scheduling features like controlled breaks, fair workloads considering task difficulty, stable weekly schedules, and shifts that cross midnight. They tested their method on standard benchmarks and various synthetic setups to demonstrate its adaptability.
workforce schedulingconstraint programming (CP)NP-hard optimizationbreak schedulingworkload equitymulti-granularity temporal resolutioninter-week stabilitycross-midnight shiftsCP-SAT solverbenchmarking
Authors
Vipul Patel, Anirudh Deodhar, Dagnachew Birru
Abstract
Workforce scheduling is an NP-hard combinatorial optimization problem requiring simultaneous satisfaction of labor regulations, coverage requirements, employee preferences and operational objectives. Existing CP formulations typically model simplified instances with 6-12 constraints at shift-level granularity and critically lack explicit support for: mandatory break scheduling with midpoint placement control; acuity weighted workload equity; sub-shift temporal granularity enabling demand-driven staffing; inter-week schedule stability; and cross-midnight shift patterns common in 24-hour operations. This paper presents CP-WSP: a declarative CP-SAT framework enforcing 14 hard constraints as mathematically inviolable requirements (zero regulatory violations by construction) while optimizing 15 soft objectives through a unified weighted penalty function -- all configurable via a JSON specification with no code changes required. Key contributions include: a shift-window variable decomposition enabling mandatory break scheduling with centrality control; acuity-weighted workload equity; multi-granularity temporal resolution from 30 minutes to 2 hours; inter-week schedule stability; a grid-offset preprocessing technique for cross-midnight shifts; and a reproducible 36-configuration benchmark suite for community comparison. Evaluated on INRC-II benchmarks at both hourly and shift-level granularity and on 36 synthetic configurations.