CP-WSP: A Declarative CP-SAT Framework for Configurable Multi-Constraint Workforce Scheduling Vipul Patel1 , Anirudh Deodhar1 , Dagnachew Birru1 1 Phi Labs, Quantiphi {vipul.patel, anirudh.deodhar, dagnachew.birru}@quantiphi.com
arXiv:2607.05177v1 [cs.AI] 6 Jul 2026
Abstract
and shift limits; operations require staffing floors and management coverage; employee contracts restrict availability; quality objectives include fairness and schedule stability. A schedule that violates a minimum rest requirement is not merely a “slightly suboptimal” solution - it is a regulatory violation with direct safety and legal implications, motivating the use of exact methods with formal feasibility guarantees. Existing approaches - metaheuristics (Burke et al. 2006), integer programming (Vossen et al. 2015) and constraint programming (van Hoeve et al. 2006) - typically model 6-12 constraints at shift-level granularity (Table 1). No reviewed system simultaneously supports mandatory break scheduling with midpoint control, acuity-weighted workload equity, inter-week schedule stability, cross-midnight shifts (e.g., 22:00-07:00) and configurable multi-granularity temporal resolution. Moreover, metaheuristic methods encode regulations as penalty terms rather than hard constraints, so generated schedules may violate rest or unavailability requirements. Adding a new labor regulation requires modifying solver code - a high-friction process needing CP expertise rarely available in operations teams. Constraint acquisition (Bessière et al. 2011; Tsouros, Stergiou, and Bessière 2013) addresses this but has not been applied to large-scale workforce scheduling. CP-WSP contributes four things to the CASPeR community: (1) Declarative constraint configuration: All 29 constraints (14H+15S) are independently activatable and weight-configurable via a plain JSON file, requiring no solver code changes. (2) Shift-window variable decomposition: A three-variable (x, w, b) model replaces the single binary variable, enabling mandatory breaks with duration control (H11), break centrality (S11), concurrent break limits (H12) and shift contiguity (H10) - constructs inexpressible with a single binary indicator. (3) Hard/soft constraint separation: 14 hard constraints are structurally enforced as mathematically inviolable requirements (zero violations by construction); 15 soft terms enter a weighted COP objective, eliminating the feasibility-optimality tension of penalty methods. (4) Comprehensive benchmark evaluation: Evaluated on 10 INRC-II instances (5-80 nurses), 3 NRP-23 cross-midnight instances and a 36-configuration synthetic benchmark, CP-WSP achieves proven optimality on n005w4 (objective 118, gap 0.0%, 104 s), scales to 179,800 variables (80 nurses) and delivers a 37% ablation
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; acuityweighted 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 (x = w − b) 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, CP-WSP achieves: zero hard-constraint violations across all instances by construction; proven optimality on INRC-II n005w4 (objective 118, gap 0.0%, 104 s); feasible solutions for 30-employee instances within 120 seconds; and model sizes scaling linearly at ∼4,400 variables per employee. The formulation enforces 29 total constraints (14 hard + 15 soft) - nearly three times the 6-12 constraint industry average. A constraint ablation study shows the full model achieves a 37% objective improvement over baseline, with workload equity delivering 66% fairness improvement at negligible coverage cost.
1
Introduction
Workforce scheduling assigns employees to time slots to meet demand subject to hard labor constraints and soft quality objectives. It is NP-hard (Garey and Johnson 1979; Blazewicz, Lenstra, and Rinnooy Kan 1983) and arises in healthcare, retail and logistics. In practice, constraint sets are heterogeneous and evolving: labor laws mandate rest Accepted at the CASP:ER Workshop, ICAPS 2026. This is the authors’ version of the work.
1
System
has ≈210080 binary assignments before constraint propagation. The model scales linearly at ≈4,400 decision variables and ≈9,400 constraints per employee, confirmed empirically across all benchmark instances.
Cons. Brk Eq. Cfg? Feas.
INRC-II (Ceschia et al. 2019) Schaus (2009) Burke (2006) Van Hoeve (2006) CP-WSP
11
×
×
×
15 10 12 29
✓ × ✓ ✓
× × × × × × ✓ JSON
✓ ✓ × ✓ ✓
Three-State Variable Decomposition Traditional models use xe,d,s ∈ {0, 1}, conflating break with off-duty time. CP-WSP introduces the shift-window decomposition:
Table 1: CP-WSP vs. related CP workforce scheduling systems. Cons.=total constraints; Brk=break scheduling; Eq.=workload equity; Cfg=user-configurable; Feas.=feasibility guaranteed. CP-WSP is the only system providing all five properties.
xe,d,s = we,d,s − be,d,s
(2)
where we,d,s =1 iff slot s is within e’s shift window on day d, and be,d,s =1 iff e is on a scheduled break. Three feasible states: off-duty (w=0, b=0, x=0), active (w=1, b=0, x=1), break (w=1, b=1, x=0). This enables break constraints as direct CP-SAT linear expressions (Appendix C, Table 13).
improvement from baseline to full model.
2
∀ e, d, s
Background and Related Work
Grid-Offset Preprocessing for Cross-Midnight Shifts
Workforce Scheduling as a Scheduling Problem Workforce scheduling is a temporal assignment problem: for each employee e and slot (d, s), decide xe,d,s ∈ {0, 1}. Its temporal structure connects it to scheduling; its resource dimension to resource allocation. INRC-I (Haspeslagh et al. 2014) and INRC-II (Ceschia et al. 2019) established community benchmarks. Most competitive solvers use CP (Vossen et al. 2015) or IP (Beddoe and Petrovic 2006).
Day-indexed models traditionally cannot represent shifts spanning midnight (e.g., 22:00-07:00). CP-WSP introduces a zero-cost grid-offset preprocessing technique: before model construction, the time grid is shifted by ∆ hours such that all shift types start and end within a single calendar day. Formally, for grid offset ∆, slot s maps to wall-clock time (s · δ + ∆) mod 24. The offset is chosen as: ∆∗ = arg min max end(t, ∆) − start(t, ∆) (3) ∆
Constraint Acquisition
t∈T
CONACQ (Bessière et al. 2011), QuAcq (Tsouros, Stergiou, and Bessière 2013) and ORCA (Mears et al. 2014) learn constraint models from examples or interactive queries. A complementary approach is declarative specification (Freuder and Wallace 2011): experts specify constraints in a highlevel language. CP-WSP adopts this: all constraints and weights are declared in a JSON file, enabling rapid model evolution without solver expertise.
where T is the set of shift types. This transformation requires no structural model changes - all constraints, variables and objective terms remain identical. Post-solving, assignments are mapped back to wall-clock times. This technique is validated on INRC-II instances with Night shifts (22:00-07:00), confirming correct cross-midnight scheduling.
Shift Scheduling with CP
Six experiments are conducted on hardware: Intel Core i712700, 16-core, 32 GB RAM, Python 3.11, OR-Tools v9.12 (Perron and Furnon 2024). The constraint model (H1 - H14, S1 - S15) and solver configuration are described fully in Appendices D and A. Results are presented across: (1) INRC-II benchmark scaling at two granularities; (2) NRP-23 crossmidnight validation; (3) synthetic scalability; (4) granularity impact; (5) constraint ablation; and (6) weight sensitivity.
4
Schaus et al. (2009) introduced global constraints for rostering; van Hoeve et al. (2006) applied CP to nurse scheduling with soft constraints. All prior models use a single binary per (employee, day, slot), which cannot distinguish break time from off-duty time. Table 1 positions CP-WSP among related systems.
3
Problem Formulation
Evaluation
Temporal Resource Assignment
INRC-II Benchmark
Let E = {e1 , . . . , en }, days D = {0, . . . , 6}, slots S = {0, . . . , T −1} with T = ⌈24/δ⌉ for slot duration δ. The COP minimizes a weighted combination of |S|=15 soft objective terms (S1 - S15, detailed in Appendix D): P|S| Find X s.t. Hk (X)=0 ∀k, min Z = i=1 ai wi fi (X) (1) where S = {S1 , . . . , S15 } is the set of soft objectives, ai ∈ {0, 1} is an activation flag and wi ∈ R is a configurable weight. A 30-employee, 7-day, 30-MIN instance
CP-WSP is evaluated on all 10 standard INRC-II benchmark instances (Ceschia et al. 2019) at two granularity levels. Table 2 reports hourly results (1-HR, 24 slots/day, 600 s time limit): CP-WSP produces feasible, regulation-compliant schedules for all 10 instances (5-80 nurses), with models scaling to 179,800 variables and 351,425 constraints. The large optimality gaps (36-99%) are inherent to the hourly formulation: expanding shift-level decisions into individual hourly slots creates a weak LP relaxation. The key result is that feasibility - not optimality - is the primary requirement: 2
Inst. n005w4 n012w8 n021w4 n030w4 n035w4 n040w4 n050w4 n060w4 n070w4 n080w4
Emp.
Vars
Cons.
Obj. Gap (%) Status
5 11,725 22,458 1,151 12 27,412 53,331 2,584 21 47,581 92,820 4,071 30 67,750 132,234 5,842 35 78,955 154,162 10,469 40 90,160 176,084 28,704 50 112,570 219,897 33,053 60 134,980 263,791 41,473 70 157,390 307,580 56,480 80 179,800 351,425 171,268
Inst.
36.6 FEASIBLE 86.5 FEASIBLE 81.5 FEASIBLE 88.7 FEASIBLE 93.0 FEASIBLE 96.7 FEASIBLE 96.6 FEASIBLE 97.0 FEASIBLE 97.4 FEASIBLE 99.0 FEASIBLE
n005w4 n012w8 n021w4 n030w4 n040w4 n050w4 n060w4 n080w4
Emp. Gran. 5 12 21 30 40 50 60 80
118 242 462 231 423 256 324 437
Obj. Gap (%)
Status
157 1,358 210
- FEASIBLE 13.6 FEASIBLE - FEASIBLE
n010w1 1-HR n010w4 1-HR n025w1 1-HR
10 23,292 2,404 10 94,566 35,017 25 56,927 11,225
- FEASIBLE 77.2 FEASIBLE - FEASIBLE
All 36 instances achieve zero hard-constraint violations. OPTIMAL is certified for all ≤10-employee instances. This benchmark is released as a standardized community resource: all 36 configurations use fully specified JSON constraint schemas (Appendix B), enabling exact reproduction and fair comparison by future workforce scheduling systems.
Vars Obj. Bnd Gap (%) Status
8-HR 1,799 118 6-HR 5,632 316 6-HR 9,781 938 6-HR 13,930 2,855 6-HR 18,540 885 6-HR 23,150 3,341 6-HR 27,760 579 6-HR 36,980 729
Vars
10 3,867 10 15,606 25 9,467
Table 4: NRP-23 compatible instances with cross-midnight Night shifts (600 s limit). Shift-level objectives are 15-26× lower than hourly. n010w4 gap of 13.6% indicates nearoptimal scheduling.
Table 2: INRC-II at 1-HR granularity (600 s limit). All 10 instances (5-80 nurses) produce feasible, regulation-compliant schedules. Model size scales linearly at ∼2,250 vars/nurse. Zero hard violations. Inst.
Gran. Emp.
n010w1 8-HR n010w4 8-HR n025w1 8-HR
0.0 OPTIMAL 23.4 FEASIBLE 50.8 FEASIBLE 91.9 FEASIBLE 52.2 FEASIBLE 92.3 FEASIBLE 44.0 FEASIBLE 40.1 FEASIBLE
Granularity Impact Table 6 isolates the effect of temporal granularity on a fixed 20-employee, 7-day instance. Coarser granularity yields ≈10× speedup but fundamentally changes solution quality: the objective drops from 15,240 (30-MIN, 48 slots/day) to 9,820 (2-HR, 12 slots/day) because fewer decision variables reduce the penalty surface. This is not a quality improvement - it reflects reduced modeling fidelity. Practitioners should choose granularity based on operational requirements: 30MIN for fine-grained break and coverage control; shift-level for traditional rostering formulations.
Table 3: INRC-II at shift-level granularity (600 s limit). n005w4 solved to proven optimality. Model sizes are 4.56.5× smaller than 1-HR; objectives improve by up to 99%+ for large instances.
every returned schedule satisfies all 14 hard constraints by construction. Table 3 reports shift-level results (6-HR/8-HR, 3-4 slots/day). Model sizes shrink 4.5-6.5× vs. hourly and objectives improve dramatically: n060w4 drops from 41,473 (1-HR) to 579 (shift) - a >99% reduction. n005w4 achieves proven optimality (objective 118, gap 0.0%, 104 s).
Model Complexity Table 7 confirms linear scaling of model size with employee count across five deployment units at 30-MIN granularity. Variables and constraints scale at ≈4,400 and ≈9,400 per employee, respectively. CP-SAT’s presolve phase reduces effective model size by 60-70% before search.
NRP-23 Compatible Benchmark
Constraint Ablation Study
To validate cross-midnight shift support, CP-WSP is evaluated on three NRP-23 compatible instances using the standard D/E/N shift structure (8-HR each), where the Night shift N(23:00-07:00) spans midnight. Grid-offset preprocessing (∆=7) maps all shifts into a single day. Table 4 reports results at both shift-level and hourly granularity. All instances produce feasible schedules with correct crossmidnight assignments. The shift-level model for n010w4 achieves a gap of just 13.6%, indicating near-optimal scheduling. Hourly models produce objectives 15-26× larger than shift-level counterparts, confirming that granularity selection fundamentally affects solution quality.
CP-WSP is run with progressively richer constraint sets on a 20-employee, 7-day, 30-MIN instance, toggling JSON activation flags per run (Table 8). Break constraints (H10 H12, S11) reduce the objective by 3.9% while enabling valid break placement - impossible with a single binary variable. Workload equity (S15) reduces the equity standard deviation from 6.2 h to 2.1 h (66%) at only 0.8% objective cost.
Weight Sensitivity Analysis Table 9 shows how primary objective weights affect solution quality on the same instance. Coverage improves monotonically with understaffing weight; equity improves with equity weight at coverage cost. The JSON interface enables rapid stakeholder preference elicitation without recompiling the solver.
Synthetic Benchmark: Scalability Table 5 reports results across a 4×3×3 benchmark (4 team sizes × 3 horizons × 3 granularities = 36 configurations). 3
Team
Horizon
Granularity
Status
Solve (s)
5 10 20 30 5 10 20 30
7-day 7-day 7-day 7-day 14-day 14-day 14-day 14-day
30-MIN 30-MIN 30-MIN 30-MIN 30-MIN 30-MIN 30-MIN 30-MIN
OPTIMAL OPTIMAL FEASIBLE FEASIBLE OPTIMAL OPTIMAL FEASIBLE FEASIBLE
0.8 2.3 18.4 41.2 1.4 4.7 34.8 87.3
Gap (%)
Cov. (%)
0.0 0.0 2.1 4.1 0.0 0.0 3.2 5.8
98.4 96.8 93.2 88.4 97.9 95.3 91.8 86.1
Table 5: CP-WSP scalability benchmark (30-MIN granularity). Zero hard violations on all 36 configurations. OPTIMAL certified for all ≤10-employee instances across both 7-day and 14-day horizons.
Granularity Slots/Day Status 30-MIN 1-HR 2-HR
Solve (s)
48 FEASIBLE 18.4 24 FEASIBLE 4.2 12 FEASIBLE 1.8
model (Appendix E), reproducible JSON schemas and baseline results with certified optimality gaps. Future work can evaluate new solvers or decomposition strategies under controlled conditions.
Obj. 15,240 11,640 9,820
Limitations and Future Work
Table 6: Granularity impact (20 emp., 7-day). Coarser granularity yields ∼10× speedup but reduces modeling fidelity. Multi-granularity support enables practitioners to choose the appropriate fidelity level. Unit Unit 1 Unit 2 Unit 3 Unit 4 Unit 5
Emp.
Vars
Model size scales linearly (∼4,400 vars, ∼9,400 constraints per employee); presolve reduces effective size by 60-70%. The acuity-weighted equity objective (S15) uses composite Workload Points W P (e) combining role, skill and demandintensity credits, ensuring fairness accounts for workload difficulty, not merely duration. Scalability beyond 50 employees could be addressed via Benders decomposition or column generation. The static JSON interface could be extended with QuAcq-style (Tsouros, Stergiou, and Bessière 2013) interactive feedback loops or LLM-based naturallanguage constraint specification.
Cons. Time (s) Status
26 115,294 244,202 123.9 14 62,682 131,025 122.0 23 102,107 214,053 122.5 10 45,196 94,178 121.5 33 145,901 306,323 126.1
FEASIBLE FEASIBLE FEASIBLE FEASIBLE FEASIBLE
Table 7: Model complexity across five deployment units (30MIN, 7-day, 120 s limit). Linear scaling: ∼4,400 vars and ∼9,400 constraints per employee.
5
6
Conclusion
CP-WSP is a declarative CP-SAT framework for multiconstraint workforce scheduling with four contributions relevant to CASPeR: (1) Declarative JSON-based constraint configuration for a 29-constraint model (14H+15S) without solver code changes. (2) The shift-window decomposition (x = w−b) enabling mandatory breaks, break centrality and concurrent break limits - inexpressible with a single binary variable. (3) Hard/soft constraint separation guaranteeing zero hard violations while enabling quality trade-off through weighted objectives. (4) A reproducible 36-configuration benchmark suite with fully specified constraint schemas and baseline results for community comparison. The full constraint set achieves a 37% objective improvement over a baseline; workload equity delivers 66% equity improvement at negligible coverage cost. Grid-offset preprocessing extends the framework to cross-midnight shifts at zero computational cost.
Discussion
Constraint Acquisition and the Shift-Window Model The JSON interface separates constraint specification from solving: domain experts specify requirements; CP-SAT determines how to satisfy them. While this interface does not perform constraint acquisition in the formal sense of learning constraints from examples (Bessière et al. 2011), it provides a lightweight declarative specification mechanism (Freuder and Wallace 2011) that achieves a similar practical goal: enabling non-experts to modify the constraint model without solver expertise. Adding a constraint requires only a JSON key and a ∼20-line Python function. The x=w−b decomposition generalizes beyond workforce scheduling to any problem distinguishing “within-window-but-inactive” from “outside-window” states (e.g., machine maintenance windows, vehicle rest stops).
References Beddoe, G.; and Petrovic, S. 2006. Selecting and weighting features in a case-based reasoning approach to nurse rostering. European Journal of Operational Research, 175(2): 1027–1044. Bessière, C.; Coletta, R.; Freuder, E.; and O’Sullivan, B.
CP-WSP as a Benchmark The 36-configuration benchmark is proposed as a standardized community resource: a fully specified 29-constraint 4
Obj. Cov. (%) Equity σ (h) Breaks?
Config
Active Constraints
(A) Baseline (B) +Coverage (C) +Breaks (D) +Mgmt (E) +Stability (F) +Fairness (G) Full
H1 - H7 only (A)+H8,H9,S1 - S5 (B)+H10 - H12,S11 (C)+S8 - S10 (D)+S12,S13 (E)+S15,H14 All H1 - H14, S1 - S15
24,180 18,640 17,920 17,340 16,890 16,210 15,240
71.4 88.3 87.1 88.4 87.9 87.2 93.2
8.4 7.1 6.8 6.2 5.8 2.1 2.1
× × ✓ ✓ ✓ ✓ ✓
Table 8: Constraint ablation (20 emp., 7-day, 30-MIN, 120 s limit). Full model achieves 37% objective improvement over baseline; break validity requires the shift-window decomposition (H10 - H12). Config
wunder
weq
wstab wbrk
Default Coverage+ Equity+ Stability+ Balanced
1.0 5.0 1.0 1.0 3.0
1.0 1.0 10.0 1.0 3.0
1.0 1.0 1.0 5.0 3.0
10.0 10.0 10.0 10.0 10.0
Obj. Cov. (%) Eq. σ Stab. ∆ 15,240 13,680 16,440 16,890 14,920
93.2 97.1 90.1 88.6 94.8
2.1 h 3.8 h 0.8 h 2.3 h 1.4 h
0.41 0.52 0.43 0.18 0.29
Table 9: Weight sensitivity (20 emp., 7-day, 30-MIN). JSON weight changes require no solver recompilation. 2011. Constraint acquisition. Artificial Intelligence, 175(12– 13): 1786–1822. Blazewicz, J.; Lenstra, J. K.; and Rinnooy Kan, A. H. G. 1983. Scheduling subject to resource constraints: Classification and complexity. Discrete Applied Mathematics, 5(1): 11–24. Burke, E.; De Causmaecker, P.; Petrovic, S.; and Vanden Berghe, G. 2006. Metaheuristics for handling time interval coverage constraints in nurse scheduling. Applied Artificial Intelligence, 20(9): 743–766. Ceschia, S.; et al. 2019. The second international nurse rostering competition. Annals of Operations Research, 274: 171–186. Freuder, E. C.; and Wallace, R. J. 2011. Progressing toward the holy grail. Constraints, 16(2): 120–139. Garey, M. R.; and Johnson, D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. Haspeslagh, S.; De Causmaecker, P.; Schcausberger, A.; et al. 2014. The first international nurse rostering competition 2010. Annals of Operations Research, 218(1): 221–236. Mears, C.; et al. 2014. ORCA: a hybrid approach to constraint acquisition. In AAAI 2014 Workshop on Constraint Acquisition. Perron, L.; and Furnon, V. 2024. OR-Tools CP-SAT. Google, v9.12. https://developers.google.com/optimization. Schaus, P.; Deville, Y.; Dupont, P.; and Régin, J.-C. 2009. Solving nurse rostering problems using global constraints in CP. In Proceedings of CP 2009, 73–87. Springer. Tsouros, N.; Stergiou, K.; and Bessière, C. 2013. QuAcq: acquiring constraints from queries. In Proceedings of CP 2013, 784–792. Springer. van Hoeve, W. J.; et al. 2006. Soft global constraints in CP for nurse rostering. In Proceedings of CPAIOR 2006, 287– 302. Springer.
Vossen, B.; et al. 2015. Optimal scheduling of nurses using constraint programming. Technical report, Nurse Rostering Competition.
A
Solver Configuration and Anytime Behavior
CP-WSP uses OR-Tools CP-SAT v9.12 (Perron and Furnon 2024), which combines constraint propagation, SAT clause learning, LP relaxations and Large Neighborhood Search (LNS) in a portfolio of 16 parallel workers. This provides an anytime algorithm: feasible solutions appear within 515 s; subsequent iterations improve the incumbent. The dual bound provides a certified optimality gap - a key advantage over metaheuristics. Parameter
Value Justification
Workers
16
Symmetry level 3 Time limit
120 s
LNS workers
11
Presolve
Full
Portfolio diversity; all CPU cores Maximum symmetry breaking Practical; anytime feasible in <15 s RINS, RENS, graph, random strategies Reduces model size 6070%
Table 10: CP-SAT solver configuration in CP-WSP.
B
Full JSON Constraint Activation Schema
The complete mapping of JSON keys to constraints is shown in Table 11. Setting any key to false deactivates the corresponding constraint with no code changes required. 5
JSON Key
Constraint
Type
check empty on empty check unavailability check min 2 on floor check daily shift length check minimum turnaround check max consecutive days check weekly hours limits check utilise workforce check weekly understaffing hard check max 1 continuous shift check mandatory break check max break concurrency check weekend coverage rule check skill coverage check slot staff coverage check daily staff coverage check weekly staff coverage check daily hours target check weekly hours target check missing manager check manager overlap check mgr open close reward check break centrality check inter week stability check intra week stability check preferred hours reward check workload equity
H1 H2 H3 H4 H5 H6 H7 H8 H9
Hard Hard Hard Hard Hard Hard Hard Hard Hard
H10 H11 H12 H13 H14 S1 S3 S5 S6 S7 S8 S9 S10 S11 S12 S13 S14 S15
Hard Hard Hard Hard Hard Soft Soft Soft Soft Soft Soft Soft Soft Soft Soft Soft Soft Soft
{ "Constraint_Activation": { "check_mandatory_break": true, "check_workload_equity": true, "check_intra_week_stability": false }, "Constraint_Weights": { "slot_understaffing": 5.0, "break_centrality": 10.0, "preferred_hours_reward": -1.0 }, "Operational_Rules": { "Min_Work_window_for_Break": 4, "Break_duration_hours": 0.5 } }
Figure 1: JSON configuration excerpt for CP-WSP. Property
Soft (S1 - S15)
Enforcement Structural (CP-SAT Weighted penalty in Z Add/AddBoolOr) Violation Impossible in any fea- Allowed; penalized sible soln Semantics Labor law / safety Business quality pref. Config Activate flag (bool) Activate + weight (real) Example H11: Break ≥30 min if S11: Break near midshift ≥4 h point
Table 11: Complete JSON constraint activation schema for CP-WSP.
C
Hard (H1 - H14)
Table 12: Hard/soft constraint separation. Hard constraints are structural (violations impossible); soft objectives are weighted and traded off.
Declarative Constraint Architecture
JSON-Based Constraint Acquisition
teed to satisfy them. Constraint activation is controlled perinstance via the JSON configuration.
CP-WSP externalizes all constraint configuration to a JSON file with three sections: Constraint Activation (which constraints are active), Constraint Weights (objective term scaling) and Operational Rules (parameter values). An excerpt: This interface provides three key constraint acquisition properties: (1) Constraint selection: domain experts choose which constraints apply without modifying solver code; (2) Weight elicitation: priority among competing objectives is specified numerically; (3) Parameter specification: operational parameters are decoupled from model structure.
Soft Constraints / Objective Terms (S1 - S15)
E
Detailed Mathematical Formulation
This appendix provides the complete mathematical formulation of the CP-WSP model, including notation, linearization techniques and implementation details for all 29 constraints.
Notation Configurable parameters (set via JSON Operational Rules):
Hard/Soft Constraint Separation
Fundamental Relationship
A critical design decision is the explicit separation of constraints into two classes:
The three decision variable families are linked by the shiftwindow identity:
Shift-Window Decomposition in Detail
xe,d,s = we,d,s − be,d,s
The (x, w, b) triple enables four constraint classes that are inexpressible with a single binary variable x[e,d,s]:
D
∀ e ∈ E, d ∈ D, s ∈ S (4)
with the domain constraint be,d,s ≤ we,d,s ensuring that breaks can only occur within the shift window. This yields exactly three feasible states per (e, d, s) triple: State w b x Off-duty 0 0 0 Active work 1 0 1 Scheduled break 1 1 0
Constraint Model
Hard Constraints (H1 - H14) All 14 hard constraints are added to the CP-SAT model before solving. Any solution returned by the solver is guaran6
Constraint
H4: Daily Shift Length. Active work hours per day are bounded: X Lmin Lmax ye,d = 1 ⇒ ≤ xe,d,s ≤ ∀ e, d (11) δ δ
Expression
H10: Single we,d,s =1 ∀s ∈ [αe,d +1, βe,d −1]; shift w contiguous P P H11: Manda- ( s w ≥ Bthr ) ⇒ ( s b = Blen , tory break b contiguous) P H12: Break e be,d,s ≤ kbreak ∀d, s concurrency P S11: Break min e,d |mid(be,d,· ) − centrality mid(we,d,· )|
s∈S
Implementation: The implication isPlinearized using big-M: P s xe,d,s ≥ (Lmin /δ) · ye,d and s xe,d,s ≤ (Lmax /δ) · ye,d . H5: Minimum Inter-Shift Rest. Between consecutive working days, a minimum rest period is enforced:
Table 13: Constraint classes enabled by the shift-window decomposition. None can be expressed with a single binary work variable.
Hrest when ye,d = 1 ∧ ye,d+1 = 1 (12) δ Implementation: Using CP-SAT’s OnlyEnforceIf, this constraint is active only when both ye,d and ye,d+1 are true. αe,d+1 − βe,d ≥
The infeasible combination (w=0, b=1) is excluded by b ≤ w. This three-state model is the minimal extension of the binary model that supports break-aware scheduling: two binary variables are necessary and sufficient to represent three states and the (w, b) parameterization aligns with the natural semantics of shift windows and breaks.
H6: Maximum Consecutive Working Days. ployee works more than Cmax consecutive days: d+C max X
ye,j ≤ Cmax
No em-
∀ e, ∀ d ∈ {0, . . . , |D| − Cmax − 1}
j=d
(13)
Derived Variables
H7: Weekly Hour Limits. Total active work hours per week are bounded: XX Hmin Hmax ≤ xe,d,s ≤ ∀e ∈ E (14) δ δ
The daily work indicator and shift boundary variables are derived from the primary decision variables: hX i ye,d = 1 we,d,s ≥ 1 (5)
d∈D s∈S
H8: Utilize Workforce. Every employee must work at least one day per planning period: X ye,d ≥ 1 ∀ e ∈ E (15)
s∈S
αe,d = min{s ∈ S : we,d,s = 1} βe,d = max{s ∈ S : we,d,s = 1}
(6) (7)
In CP-SAT, ye,d is implemented via AddMaxEquality and αe,d , βe,d are computed using channeling constraints that link boolean indicators to integer shift-boundary variables.
d∈D
H9: Weekly Minimum Coverage. Total weekly staffing meets aggregate demand: XXX XX xe,d,s ≥ Dmin [d][s] (16)
Hard Constraint Formulations
e∈E d∈D s∈S
H10: Single Continuous Shift. Each employee’s shift window forms exactly one contiguous block per day:
H1: Empty-on-Empty. If no demand exists for a slot, no employee may be assigned: Dmin [d][s] = 0 ⇒ xe,d,s = 0
∀e ∈ E
we,d,s = 1
(8)
Employee availability is respected:
U [e, d, s] = 1 ⇒ we,d,s = 0
∀ e, d, s
∀ s ∈ [αe,d + 1, βe,d − 1]
(17)
Implementation: Enforced by constraining that if we,d,s1 = 1 and we,d,s2 = 1 with s1 < s2 , then we,d,s = 1 for all s1 ≤ s ≤ s2 . In CP-SAT, this is implemented via the “nogap” pattern: for each triple (s1 , s, s2 ) with s1 < s < s2 , add we,d,s1 + we,d,s2 − we,d,s ≤ 1.
Implementation: For each zero-demand slot, xe,d,s is fixed to 0 at model construction time (not as a constraint but as a variable domain restriction), eliminating these variables from the search space entirely. H2: Unavailability.
d∈D s∈S
H11: Mandatory Break. If a shift window exceeds a threshold, a contiguous break must be scheduled: ! X X Bthr Blen we,d,s ≥ ⇒ be,d,s = ∧(b contiguous) δ δ s s (18) Break contiguity is enforced analogously to H10: for the break variable be,d,· , if be,d,s1 = 1 and be,d,s2 = 1 with s1 < s2 , then be,d,s P = 1 for all s1 ≤ s ≤ s2 . The implicationPis linearized: s be,d,s ≥ (Blen /δ)·ze,d where ze,d = 1 iff s we,d,s ≥ Bthr /δ.
(9)
Note that this constrains w (not x), ensuring that unavailable slots cannot be part of the shift window at all - a stronger guarantee than merely preventing active work. H3: Minimum Floor Staffing. When demand exists, a minimum number of employees must be actively working: X Dmin [d][s] > 0 ⇒ xe,d,s ≥ kfloor ∀ d, s (10) e∈E
7
ID
Name
Type
Key Expression
H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 H12 H13
Empty-on-Empty Unavailability Min Floor Staffing Daily Shift Length Min Inter-Shift Rest Max Consecutive Days Weekly Hour Limits Utilize Workforce Weekly Min Coverage Single Continuous Shift Mandatory Break Break Concurrency Limit Weekend Management
Coverage Compliance Coverage Labor Law Labor Law Labor Law Labor Law Operations Coverage Structure Labor Law Operations Operations
xe,d,s =0 when Dmin [d][s]=0 w Pe,d,s =0 when U [e, d, s]=1 e xe,d,s ≥ Pkfloor if demand>0 Lmin /δ ≤ s x ≤ Lmax /δ α − βe,d ≥ Hrest /δ Pe,d+1 d+C y ≤ Cmax j=d e,j P H min /δ ≤ d,s x ≤ Hmax /δ P 1 at least once per week Pd ye,d ≥P d,s x ≥ d,s Dmin (weekly) w forms one contiguous block (new) e,d,· P P Ps w ≥ Bthr ⇒ s b = Blen (new) e be,d,s ≤ kbreak ∀d, s (new) Management ∈ Emgr present all weekend demand (new) Skill-demand met per slot (new)
H14 Skill Coverage
Operations
Table 14: 14 hard constraints. H1 - H9 are common to prior work; H10 - H14 (new) require the shift-window decomposition or are novel. ID S1 S2 S3 S4 S5 S6 S7 S8 S9 S10 S11 S12 S13 S14 S15
Name
Cat.
Formula P P Slot Understaffing Coverage Pd,s max(0, P Dmin [d][s] − e xe,d,s ) Slot Overstaffing Coverage Pd,s max(0,P e xe,d,s − PDideal [d][s]) Daily Understaffing Coverage Pd max(0, Ps Dmin − P e,s xe,d,s ) x − max(0, Daily Overstaffing Coverage e,d,s s Dideal ) e,s d P P D ) x − Weekly Overstaffing Coverage max(0, ideal d,s P e,d,s P daily x − H | |δ Daily Hours Target Hours e,d,s tgt Pe,d P s week | |δ d,s xe,d,s − Htgt Weekly Hours Target Hours P Pe − e∈M xe,d,s ]+ Missing Management Coverage Pd,s [1Dd,s >0 P Management Overlap Efficiency e∈Emgr xe,d,s − 1) d,s max(0, P Mgmt Open/Close Quality − d (mgr at sopen + mgr at sclose ) P mid(we,d,· )| Break Centrality Quality Pe,d |mid(be,d,· ) − prev |x Inter-Week Stability Stability e,d,s − xe,d,s | e,d,s P P ′ ′ Intra-Week Stability Stability e d<d′ (|αe,d − αe,d | + |βe,d − βe,d |) P Preferred Hours Quality − e,d,s P [e, d, s] · xe,d,s Workload Equity Fairness maxe |W P (e) − W Pbaseline (e)|
Table 15: 15 soft objective terms. S9 - S15 are novel quality dimensions not present in the INRC-II constraint set.
Soft Constraint Linearization
H12: Break Concurrency Limit. At most kbreak employees may be on break simultaneously: X be,d,s ≤ kbreak ∀ d ∈ D, s ∈ S (19)
All soft objectives are expressed as linear terms in the CPSAT objective function. Non-linear operations (max, |·|) are linearized using standard auxiliary variable techniques:
e∈E
Linearizing max(0, ·). For each term max(0, g(x)), introduce auxiliary variable v ≥ 0:
H13: Weekend Manager Coverage. At least one manager must be working during all weekend demand slots: X Dmin [d][s] > 0 ∧ d ∈ {5, 6} ⇒ xe,d,s ≥ 1 (20)
v ≥ g(x),
v≥0
(22)
and add v to the objective. Since the objective is minimized, the solver sets v = max(0, g(x)) at optimality.
e∈Emgr
H14: Skill Coverage. For each skill k and each slot with skill-specific demand Dk [d][s]: X xe,d,s ≥ Dk [d][s] ∀ k, d, s (21)
Linearizing |g(x)|. For absolute value terms, introduce v ≥ 0: v ≥ g(x), v ≥ −g(x) (23)
e∈Ek
In CP-SAT, this is implemented using AddAbsEquality for integer expressions.
where Ek ⊆ E is the set of employees possessing skill k. 8
Symbol
Definition
E = {e1 , . . . , en } Set of employees D = {0, . . . , |D| − 1} Set of planning days S = {0, . . . , T − 1} Set of time slots per day T = ⌈24/δ⌉ Number of slots per day δ Slot duration in hours (configurable) xe,d,s ∈ {0, 1} 1 iff employee e is actively working in slot s on day d we,d,s ∈ {0, 1} 1 iff slot s is within e’s shift window on day d be,d,s ∈ {0, 1} 1 iff e is on a scheduled break in slot s on day d ye,d ∈ {0, 1} 1 iff employee e works on day d (derived: ye,d = maxs xe,d,s ) αe,d Shift start slot for employee e on day d (derived) βe,d Shift end slot for employee e on day d (derived) Dmin [d][s] Minimum staffing demand for day d, slot s Dideal [d][s] Ideal (target) staffing level U [e, d, s] ∈ {0, 1} 1 iff employee e is unavailable at (d, s) P [e, d, s] ∈ R Preference score for employee e at (d, s) Emgr ⊆ E Set of employees with manager role ai ∈ {0, 1} Activation flag for constraint/objective i wi ∈ R Weight for soft objective i
S15: Workload Equity (Detailed). The Workload Points W P (e) for employee e are computed as: X W P (e) = xe,d,s · R(e) + K(e, d, s) + Dmin [d][s] | {z } | {z } | {z } role
skill
kbreak daily Htgt week Htgt
e∈E
Typical Value
Table 17: Configurable operational parameters.
(25)
where R + K + D is the average per-slot workload point value across all employees and slots. The minimax equity objective is: f15 (X) = max |W P (e) − W Pbaseline (e)|
Min/max daily shift length 4, 10 (hours) Min/max weekly hours 20, 48 Min inter-shift rest (hours) 11 Max consecutive working days 6 Shift length triggering break 4 (hours) Mandatory break duration 0.5 (hours) Min employees on floor if de- 2 mand > 0 Max simultaneous employees 2 on break Target daily hours 8 Target weekly hours 40
kfloor
demand
week Htgt ·R+K +D δ
Lmin , Lmax
Blen
(24) where R(e) is a role-based weight (e.g., R(manager) = 1.5, R(staff) = 1.0), K(e, d, s) ∈ {0, 0.5} is a skill bonus awarded when the slot requires a specialized skill that e possesses, and Dmin [d][s] captures demand intensity. The baseline is: W Pbaseline (e) =
Description
Hmin , Hmax Hrest Cmax Bthr
Table 16: Complete notation for the CP-WSP formulation.
d,s
Parameter
(26)
linearized via a single auxiliary variable veq with veq ≥ W P (e)−W Pbaseline (e) and veq ≥ W Pbaseline (e)−W P (e) for all e.
9