🧩 Constraint Solving POTD:Problem of the Day: Workforce Scheduling with Shift Constraints

[github-actions[bot]]

Problem Statement

In Workforce Scheduling, you must assign workers to shifts over a planning horizon (e.g., one week) while respecting various constraints. The goal is typically to minimize labor costs or unmet demand while satisfying staffing requirements and labor regulations.

Concrete Instance

Suppose you run a 24-hour call center with:

• 7 days of planning (Mon–Sun)
• 3 shifts per day (Morning 8–12, Afternoon 12–20, Night 20–8)
• 10 workers, each with maximum 5 shifts/week
• Minimum staffing: 3 workers per shift
• Constraints:
  • No worker may work more than 2 consecutive night shifts
  • Each worker gets ≥2 consecutive days off per week
  • Worker A prefers morning shifts; Worker B is unavailable Wed–Fri

Find: A shift assignment that covers all demand, respects all constraints, and minimizes total cost (wages vary by shift).

Input/Output

• Input: Worker availability, shift coverage demands, work-rest regulations, cost coefficients
• Output: Assignment matrix x[w,d,s] ∈ {0,1} (worker w assigned to shift s on day d), and total cost

---

Why It Matters

Healthcare: Hospitals use workforce scheduling daily to staff nurses, doctors, and support staff across ICU, ER, and general wards, balancing patient safety (minimum staffing) with union contracts and fairness.

Retail & Food Service: Supermarkets, restaurants, and cafés must schedule hundreds of workers across overlapping shifts while respecting part-time availability and skill requirements.

Emergency Services: Fire departments, police, and ambulance services plan 24/7 crews with strict fatigue rules and statutory rest mandates.

Transportation: Airlines schedule cabin crew and ground staff to ensure every flight has qualified personnel while meeting duty-time limits and layover regulations.

Workforce scheduling accounts for billions in labor costs annually, making even 2–3% improvements highly valuable.

---

Modeling Approaches

Approach 1: Integer Linear Programming (ILP)

Paradigm: Mathematical optimization via linear inequalities over binary variables.

Decision Variables:

• x[w,d,s] ∈ {0,1}: Worker w works shift s on day d
• y[w,d] ∈ {0,1}: Worker w is "active" (works at least one shift) on day d

Key Constraints:

# Staffing requirement
For each shift (d,s): Σ_w x[w,d,s] ≥ min_staff[d,s]

# Max shifts per worker per week
For each worker w: Σ_{d,s} x[w,d,s] ≤ max_shifts[w]

# No more than k consecutive night shifts
For each worker w, day d:
  Σ_{d'=d..d+k-1} x[w,d',night] ≤ k - 1

# Minimum consecutive days off
For each worker w: (1 - y[w,d]) + (1 - y[w,d+1]) ≥ 1  (for all d)

Objective: Minimize Σ_{w,d,s} cost[w,s] × x[w,d,s]

Trade-offs:

• ✓ Exact solutions; well-studied
• ✓ Highly scalable (thousands of workers)
• ✗ Some practical constraints (e.g., fairness, learning curves) hard to express linearly
• ✗ Non-convex integer relaxations can be weak

Approach 2: Constraint Programming (CP)

Paradigm: Declarative constraints + intelligent search with propagation.

Decision Variables:

• assignment[w,d] ∈ {0..s_max}: Shift assigned to worker w on day d (0 = off)
• consecutive_nights[w,d] ∈ {0..k}: Running count of night shifts for worker w ending on day d

Key Constraints:

# Staffing (global cardinality or count constraint)
For each shift (d,s): count(assignment[*,d] = s) ≥ min_staff[d,s]

# Work-rest pattern (element + table/automaton)
Use an automaton to enforce: work ≤ 2 nights, then ≥ 2 consecutive days off

# Availability (domain restriction)
If worker w unavailable on day d: domain(assignment[w,d]) = {0}

# Symmetry breaking
Assign worker IDs in order; use lex_lesseq(...) to break symmetries

Objective: Minimize cost via branch-and-bound

Trade-offs:

• ✓ Natural expression of logical & cardinality constraints
• ✓ Strong propagation (e.g., arc consistency) prunes search early
• ✗ May require careful tuning of variable/value ordering
• ✓ Excellent for small–medium instances (≤50 workers, 1–4 weeks)

---

Modeling Example (MiniZinc)

int: num_workers;
int: num_days;
int: num_shifts;
int: min_staff;
array[1..num_workers, 1..num_days, 1..num_shifts] of int: cost;

% Decision variable: 0 = off, 1..num_shifts = assigned shift
array[1..num_workers, 1..num_days] of var 0..num_shifts: assignment;

% Constraint: minimum staffing per shift
constraint forall(d in 1..num_days, s in 1..num_shifts) (
  sum(w in 1..num_workers) (assignment[w,d] == s) >= min_staff
);

% Constraint: max 5 shifts per worker per week
constraint forall(w in 1..num_workers) (
  sum(d in 1..num_days) (assignment[w,d] > 0) <= 5
);

% Constraint: no more than 2 consecutive night shifts (shift 3)
constraint forall(w in 1..num_workers, d in 1..num_days-2) (
  (assignment[w,d] == 3) + (assignment[w,d+1] == 3) + 
  (assignment[w,d+2] == 3) <= 2
);

% Objective: minimize total cost
solve minimize sum(w in 1..num_workers, d in 1..num_days) (
  cost[w, d, assignment[w,d]]
);

output ["Worker ", show(w), " day ", show(d), " shift ", 
        show(assignment[w,d]), "\n" | 
        w in 1..num_workers, d in 1..num_days];

---

Key Techniques

1. Global Constraints

• cumulative(...): Enforce that workers' total shifts don't exceed capacity over sliding windows
• automaton(...): Model complex state machines (e.g., "Night → Rest → Day" patterns)
• global_cardinality(...): Ensure balanced allocation across shifts

2. Variable Ordering Heuristics

• First-Fail: Assign the worker/day with smallest domain (most constrained variables first)
• Impact-Based: Prioritize decisions that eliminate the most future options
• Domain-Driven: Assign workers with tight availability windows early

3. Symmetry Breaking

• Workers are largely interchangeable; post constraints like cost[w] ≥ cost[w+1] to reduce search
• Use implied constraints (e.g., "If all shifts identical, worker IDs are ordered")

4. Relaxation & Bounds

• LP Relaxation: Solve ILP with x[w,d,s] ∈ [0,1]; often gives tight lower bounds
• Lagrangian: Relax hard constraints; optimize the dual to guide feasibility search
• Greedy Heuristic: Quickly find a feasible solution; branch-and-bound improves from there

---

Challenge Corner

Question 1: How would you add fairness to ensure no worker is repeatedly assigned undesirable shifts (e.g., night shifts, weekends)? Can you do this without explicit historical data?

Question 2: Suppose you also want to minimize worker fatigue (measured as cumulative work hours and shift changes). How does this change the model? Is CP or ILP more expressive?

Question 3: In large call centers (1000+ agents), the ILP becomes intractable. Propose a decomposition strategy (e.g., cluster workers, solve per cluster, then integrate) and discuss what information you'd need to ensure solutions are still feasible globally.

---

References

1. Rossi, F., van Beek, P., & Walsh, T. (2006). Handbook of Constraint Programming. Elsevier. Chapter 26 covers scheduling.

2. Maenhout, B. & Vanhoucke, M. (2010). "An Evolutionary Approach to the Nurse Scheduling Problem." Journal of Heuristics, 16(6), 761–779.

3. Ernst, A. T., Jiang, H., Krishnamoorthy, M., & Sier, D. (2004). "Staff Scheduling and Rostering: A Review of Applications, Methods and Models." European Journal of Operational Research, 153(1), 3–27.

4. Google OR-Tools Documentation: (developers.google.com/redacted) — practical examples in Python/C++.

---

What constraint solving techniques would you use for workforce scheduling at your organization? Share your approach in the comments!

Warning

Firewall blocked 1 domain

The following domain was blocked by the firewall during workflow execution:

• awmgmcpg

To allow these domains, add them to the network.allowed list in your workflow frontmatter:

network:
  allowed:
    - defaults
    - "awmgmcpg"

See Network Configuration for more information.

Generated by 🧩 Constraint Solving — Problem of the Day · 9.64 AIC · ⌖ 23.9 AIC · ⊞ 5.2K · ◷

• expires on Jul 8, 2026, 4:26 AM UTC-08:00

[github-actions[bot]]

This discussion has been marked as outdated by Constraint Solving — Problem of the Day.

A newer discussion is available at Discussion #42947.