🧩 Constraint Solving POTD:Problem of the Day: Nurse Rostering — Staff Scheduling Under Constraints

[github-actions[bot]]

Problem Statement

Nurse Rostering is the problem of assigning nurses to shifts over a planning horizon while satisfying complex constraints on coverage, fairness, and regulations.

Concrete Instance

Consider a small hospital unit with:

• 5 nurses: N1, N2, N3, N4, N5
• 7 days in the planning horizon
• 3 shift types: Morning (M, 8am–4pm), Evening (E, 4pm–midnight), Night (N, midnight–8am)
• Each shift requires at least 2 nurses assigned

Constraints:

• Each nurse works at most 5 shifts per week
• No nurse works more than 2 consecutive night shifts
• Each nurse has at least 2 days off per week
• Certain nurses cannot work certain shifts (e.g., N1 unavailable on days 3–4)

Goal: Find a feasible assignment, or if multiple solutions exist, optimize for fairness (equal shift distribution).

---

Why It Matters

Healthcare scheduling: Hospitals must staff emergency departments, ICUs, and wards 24/7 while respecting union contracts and nurse preferences.

Retail and service industries: Large retailers use rostering to manage customer-facing staff across multiple locations, times, and skill levels.

Emergency services: Fire, police, and paramedic units must maintain coverage while adapting to variable demand and complex rest rules.

Call centers: Large operations schedule agents across shifts, languages, and skill specializations to meet service-level agreements.

---

Modeling Approaches

Approach 1: Constraint Programming (CP)

Decision variables:

• assignment[n, d, s] ∈ {0, 1} for each nurse n, day d, shift s
  • 1 if nurse n works shift s on day d, else 0

Key constraints:

• Coverage: ∑_n assignment[n, d, s] ≥ 2 (at least 2 nurses per shift)
• Work limit: ∑_{d,s} assignment[n, d, s] ≤ 5 (max 5 shifts per nurse per week)
• Consecutive nights: using a reified constraint, ensure no nurse has assignment[n, d, Night] = 1 for more than 2 consecutive days
• Unavailability: assignment[N1, 3, *] = 0 and assignment[N1, 4, *] = 0

Objective: Minimize max deviation in shift counts per nurse

Strengths: Native support for global constraints (e.g., cumulative, automaton for consecutive patterns), automatic propagation.
Trade-offs: Less flexible for dynamic pricing or objective refinement; typically slower on very large instances without good search heuristics.

---

Approach 2: Mixed-Integer Programming (MIP)

Decision variables:

• x[n, d, s] ∈ {0, 1} for each nurse n, day d, shift s (same as above)
• y[n] ≥ 0 for fairness slack (deviation from average shifts per nurse)

Key constraints:

• Coverage: ∑_n x[n, d, s] ≥ 2
• Work limit: ∑_{d,s} x[n, d, s] ≤ 5
• Consecutive nights (linearized): Introduce auxiliary binary variables z[n, d] and enforce

  z[n, d] ≥ x[n, d, Night] + x[n, d+1, Night] + x[n, d+2, Night] - 2
  ∑_d z[n, d] = 0
  

• Fairness: ∑_d x[n, d, *] ≤ avg_shifts + y[n] and ∑_d x[n, d, *] ≥ avg_shifts - y[n]

Objective: Minimize ∑_n y[n] (total slack) or max_n y[n] (largest deviation)

Strengths: Efficient solvers (CPLEX, Gurobi) can handle large instances; easy to add cost-based objectives.
Trade-offs: Linearizing complex constraints (consecutive patterns, disjunctive scheduling) requires auxiliary variables and big-M bounds, which can weaken LP relaxations.

---

Example Model (Pseudo-code: CP-based)

input: nurses, days, shifts, min_coverage[shift]
       work_limit, max_consecutive_nights, min_days_off

variables:
  x[n, d, s] ∈ {0, 1} for n in nurses, d in days, s in shifts

constraints:
  // Coverage
  forall d, s: sum(n) x[n, d, s] >= min_coverage[s]
  
  // Individual work limit
  forall n: sum(d, s) x[n, d, s] <= work_limit
  
  // Consecutive nights (global constraint or decomposition)
  forall n, d in 1..days-2:
    x[n, d, Night] + x[n, d+1, Night] + x[n, d+2, Night] <= 2
  
  // Minimum days off
  forall n: sum(d) (1 - sum(s) x[n, d, s]) >= min_days_off
  
  // Unavailability
  forall n, d, s where unavailable[n, d]:
    x[n, d, s] = 0

objective:
  minimize max_deviation_shifts(x)

solve with:
  - Variable heuristic: First Fail (choose most constrained variable)
  - Value ordering: Try 1 before 0 (prefer assigning shifts)
  - Backtracking + constraint propagation

---

Key Techniques

1. Global Constraints for Temporal Patterns

Nurse rostering involves forbidden patterns (e.g., 3+ consecutive nights). The automaton constraint encodes these patterns as a finite state machine, enabling efficient propagation. Alternatively, cumulative constraints enforce capacity limits across overlapping time windows.

2. Symmetry Breaking and Heuristics

Nurse identities are often interchangeable (symmetry). Heuristics like least-flexible-first (assign nurses with fewer available slots first) and largest-weighted-degree reduce the search space by identifying critical decisions early. Breaking symmetry with constraints like "N1 always works at least as many shifts as N2" prunes equivalent branches.

3. Column Generation and Relaxation

Large rostering instances use set-covering formulations: each column represents a feasible individual nurse schedule, and the master problem selects a subset to cover all shifts. The subproblem (pricing problem) identifies new columns via dynamic programming or CP.

---

Challenge Corner

Question for you: In the basic model above, fairness is measured by deviation in total shifts. But in practice, nurses prefer specific shifts (some prefer nights, others prefer mornings). How would you modify the model to encode individual preferences? Can you introduce soft constraints that reduce preference violations without making the problem infeasible?

---

References

1. Rossi, F., van Beek, P., Walsh, T. (2006). Handbook of Constraint Programming, Ch. 22 (Scheduling). Elsevier. A comprehensive reference for CSP modeling of scheduling problems.

2. Gendreau, M., Potvin, J.-Y. (2010). "Handbook of Metaheuristics", Ch. Nurse Scheduling. Springer. Covers local search and tabu/genetic approaches to rostering.

3. Cheang, B., Lim, A., Rodrigues, B. (2003). "Nurse Rostering Problems — Complexity and Potential Solutions in the Era of the Internet." Journal of Scheduling, 6(4), 327–337. A definitive problem characterization.

4. Gurobi.com/rostering: (www.gurobi.com/redacted) — Practical solver documentation and benchmarks for MIP formulations.

Generated by 🧩 Constraint Solving — Problem of the Day · haiku45 · 10.3 AIC · ⌖ 4.97 AIC · ⊞ 5.9K · ◷

• expires on Aug 12, 2026, 4:09 AM UTC-08:00