Abstract
Workforce scheduling is an NP-hard combinatorial optimization problem that requires simultaneous satisfaction of labor regulations, coverage requirements, employee preferences, and operational objectives. Existing CP formulations typically model simplified instances with 6-12 constraints 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
- 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
- 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.
Blogger's Review: The CP-WSP framework shows significant advancements in tackling workforce scheduling challenges, especially in managing complex constraints and multi-objective optimization. Its configurability and no-code change feature make it highly flexible and practical for real-world applications, warranting further promotion and adoption.