🧩 Constraint Solving POTD:Nurse Rostering — Scheduling Under Hard and Soft Constraints

[github-actions[bot]]

Problem Statement

A hospital needs to assign nurses to shifts over a planning horizon (typically one to four weeks) while satisfying both hard constraints (that must never be violated) and soft constraints (preferences that should be satisfied as much as possible).

Concrete instance — 5 nurses, 3 shifts/day, 7 days:

• Nurses: N1, N2, N3, N4, N5
• Shifts per day: Day (D), Evening (E), Night (N)
• Each shift requires at least 1 nurse
• No nurse works more than 5 days in a week
• No nurse works a Night shift followed immediately by a Day shift
• Soft preference: N3 prefers not to work weekends

Input: number of nurses, shift types, horizon length, coverage requirements, individual nurse constraints/preferences
Output: an assignment shift[n][d] ∈ {D, E, N, OFF} for each nurse n and day d that satisfies all hard constraints and minimises soft-constraint violations

---

Why It Matters

• Healthcare operations: Nurse scheduling is a critical daily task in hospitals worldwide. Poor schedules increase burnout and affect patient care quality.
• Generalisation: The same model structure applies to airline crew pairing, call-centre staffing, and factory shift planning — anywhere a workforce must be rotated across time slots with coverage and fatigue rules.

---

Modeling Approaches

Approach 1 — Constraint Programming (CP)

Decision variables:
shift[n][d] ∈ {Day, Evening, Night, Off} for nurse n ∈ 1..N, day d ∈ 1..H

Hard constraints:

∀d: |{n | shift[n][d] = Day}|   ≥ minDay[d]
∀d: |{n | shift[n][d] = Evening}| ≥ minEvening[d]
∀d: |{n | shift[n][d] = Night}|  ≥ minNight[d]

∀n: sum(d)(shift[n][d] ≠ Off) ≤ maxDaysPerWeek   // per week window

∀n, d: NOT (shift[n][d] = Night AND shift[n][d+1] = Day)  // forbidden sequence

Soft objective (penalty minimisation):

minimise Σ_{n,d} penalty(n, d, shift[n][d])

Trade-offs: CP handles the combinatorial structure naturally via global constraints (GCC for coverage, Regular/Sequence for pattern rules). Propagation is strong but the search space is exponential.

---

Approach 2 — Mixed-Integer Programming (MIP)

Introduce binary variables: x[n][d][s] ∈ {0,1} = 1 if nurse n works shift s on day d.

Key constraints:

∀n,d:  Σ_s x[n][d][s] ≤ 1                    // at most one shift per day

∀d,s:  Σ_n x[n][d][s] ≥ min_coverage[d][s]   // coverage

∀n,d:  x[n][d][Night] + x[n][d+1][Day] ≤ 1   // forbidden transition

∀n, week w:  Σ_{d in w, s} x[n][d][s] ≤ 5    // work-hours cap

Objective: minimise weighted sum of soft-constraint violations (add slack variables for preferences).

Trade-offs: MIP benefits from LP relaxation bounds and mature solvers (Gurobi, CPLEX, HiGHS). However, modelling complex consecutive-shift patterns requires auxiliary binary variables, making the formulation verbose.

---

Example Model (MiniZinc pseudo-code)

int: N = 5; int: H = 7;
enum Shift = {Day, Eve, Night, Off};

array[1..N, 1..H] of var Shift: roster;

% Coverage
constraint forall(d in 1..H)(
  count(n in 1..N)(roster[n,d] = Day)   >= 1 /\
  count(n in 1..N)(roster[n,d] = Eve)   >= 1 /\
  count(n in 1..N)(roster[n,d] = Night) >= 1
);

% No Night→Day sequence
constraint forall(n in 1..N, d in 1..H-1)(
  not (roster[n,d] = Night /\ roster[n,d+1] = Day)
);

% Max 5 working days per week
constraint forall(n in 1..N)(
  count(d in 1..7)(roster[n,d] != Off) <= 5
);

% Soft: penalise N3 weekend work
var int: penalty =
  bool2int(roster[3,6] != Off) + bool2int(roster[3,7] != Off);

solve minimize penalty;

---

Key Techniques

1. Global constraint Regular: Encodes allowed/forbidden shift-sequence patterns as a finite automaton. This is far more efficient than posting pairwise "forbidden successor" constraints, especially for complex work-pattern rules (e.g., "at most 3 consecutive nights, then at least 2 days off").

2. Variable ordering heuristics: Use first-fail on the most constrained nurse-day pairs, combined with impact-based search to quickly detect infeasible partial assignments. In practice, ordering by day before nurse often yields better propagation.

3. Large Neighbourhood Search (LNS): Because the full problem is NP-hard and instances can involve hundreds of nurses, pure tree search rarely scales. LNS iteratively destroys a random subset of the assignment (e.g., all shifts for 2 randomly chosen nurses) and re-solves the subproblem, accepting improvements. This is the dominant approach in competition-winning rostering solvers.

---

Challenge Corner

Extension: The International Nurse Rostering Competition (INRC) introduced multi-week planning where weeks are solved sequentially but decisions in week k affect feasibility in week k+1 (e.g., a nurse ending week k on Night cannot start week k+1 on Day). How would you propagate these boundary constraints between subproblems in a rolling-horizon approach? Can you bound the quality loss compared to solving all weeks jointly?

---

References

1. Burke et al. (2004) — "The State of the Art of Nurse Rostering", Journal of Scheduling 7(6). The definitive survey covering models, algorithms, and benchmarks.
2. Rossi, van Beek & Walsh (2006) — Handbook of Constraint Programming, Ch. 23 on scheduling. Covers CP modelling patterns directly applicable here.
3. Haspeslagh et al. (2014) — "The Nurse Rostering Problem: A Competition", Annals of Operations Research. Describes INRC benchmark instances and winning approaches.
4. OR-Tools CP-SAT documentation — [developers.google.com/optimization]((developers.google.com/redacted) — practical guide with nurse-scheduling worked examples.

Generated by Constraint Solving — Problem of the Day · ● 109.7K · ◷

• expires on May 1, 2026, 12:56 PM UTC

[github-actions[bot]]

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

A newer discussion is available at Discussion #28456.