🧩 Constraint Solving POTD:🩺 Problem of the Day — Nurse Rostering (Scheduling)

[github-actions[bot]]

🩺 Problem of the Day: Nurse Rostering

Assign nursing staff to shifts over a planning horizon such that all shifts are covered, labor regulations are respected, and nurse preferences are honored as much as possible.

---

Problem Statement

You manage a hospital ward with 5 nurses over a 7-day planning horizon. Each day has three shifts: Morning (M), Afternoon (A), and Night (N). Each shift requires at least one nurse, and each nurse works at most one shift per day.

Hard constraints:

• Every shift every day must be covered by at least one nurse.
• No nurse works more than 5 shifts in the week.
• No nurse works a Night shift immediately followed by a Morning shift the next day (night-before-morning fatigue rule).

Soft constraints (minimize violations):

• Nurses have stated day-off preferences; respect them where possible.

Input/Output:

• Input: n nurses, d days, shift requirements, fatigue rules, preferences.
• Output: Assignment x[nurse, day, shift] ∈ {0,1} — 1 if that nurse works that shift.

A valid assignment for the small instance might look like:

Nurse	Mon	Tue	Wed	Thu	Fri	Sat	Sun
Alice	M	—	A	—	N	—	M
Bob	—	N	—	M	—	A	—
...	...	...	...	...	...	...	...

---

Why It Matters

• Healthcare operations: Hospitals worldwide spend significant effort — and budget — on manual scheduling. Automated rostering directly improves staff satisfaction and patient safety.
• Labor law compliance: Regulations like the EU Working Time Directive impose hard limits (max weekly hours, minimum rest periods) that are difficult to enforce manually at scale.
• Generalizes broadly: The same structure appears in airline crew scheduling, call-center staffing, and transit driver rostering.

---

Modeling Approaches

Approach 1: Constraint Programming (CP)

Decision variables:

x[i, d, s] ∈ {0, 1}   for nurse i, day d, shift s ∈ {M, A, N}

Key constraints:

// Each shift covered
∀d, s: sum_i x[i,d,s] ≥ requirement[d,s]

// At most one shift per day per nurse
∀i, d: sum_s x[i,d,s] ≤ 1

// Weekly workload cap
∀i: sum_{d,s} x[i,d,s] ≤ max_shifts

// Fatigue: no Night→Morning transition
∀i, d: x[i,d,N] + x[i,d+1,M] ≤ 1

Objective: minimize sum_{i,d} penalty[i,d] * (1 - day_off[i,d]) (preference violations).

Trade-offs: CP handles the combinatorial structure naturally, and global constraints like sum and alldifferent enable strong propagation. Branching on shift assignments prunes quickly once infeasibility is detected. However, large instances (100+ nurses, 28-day horizons) can be slow without good search heuristics.

---

Approach 2: Mixed-Integer Programming (MIP)

Use the same binary variables, but encode everything as linear constraints in a MIP solver (CPLEX, Gurobi, HiGHS).

Key additions over CP model:

• The fatigue constraint becomes a linear inequality: x[i,d,N] + x[i,d+1,M] ≤ 1 (already linear — no change needed).
• Preference penalties enter the objective directly.
• LP relaxation provides a lower bound; branch-and-bound closes the gap.

Trade-offs: MIP solvers excel at proving optimality via LP bounds and can handle large instances with a good formulation. However, complex temporal patterns (e.g., "no more than 3 consecutive night shifts") require auxiliary variables and may weaken the LP relaxation if modeled naively.

---

Approach 3: Local Search / Large Neighborhood Search (LNS)

Start from a feasible (possibly poor) assignment, then repeatedly:

1. Destroy: randomly unassign shifts for a subset of nurses.
2. Repair: use a CP or greedy sub-solver to reassign only those nurses.

Trade-offs: LNS scales to industrial instances (hundreds of nurses, months of horizon) where exact methods struggle. It sacrifices optimality guarantees but delivers high-quality solutions quickly. Widely used in commercial rostering products.

---

Example Model — MiniZinc (CP)

int: N = 5;   % nurses
int: D = 7;   % days
int: S = 3;   % shifts: 1=Morning, 2=Afternoon, 3=Night

array[1..N, 1..D, 1..S] of var 0..1: x;

% Each shift covered (require 1 nurse per shift for simplicity)
constraint forall(d in 1..D, s in 1..S)(
  sum(i in 1..N)(x[i,d,s]) >= 1
);

% At most one shift per nurse per day
constraint forall(i in 1..N, d in 1..D)(
  sum(s in 1..S)(x[i,d,s]) <= 1
);

% Max 5 shifts per week
constraint forall(i in 1..N)(
  sum(d in 1..D, s in 1..S)(x[i,d,s]) <= 5
);

% No Night (s=3) on day d followed by Morning (s=1) on day d+1
constraint forall(i in 1..N, d in 1..D-1)(
  x[i,d,3] + x[i,d+1,1] <= 1
);

solve satisfy;

---

Key Techniques

1. Global Cardinality Constraint (GCC)

The coverage requirement — "shift s on day d needs between lb and ub nurses" — is a perfect fit for GCC. CP solvers propagate GCC in polynomial time using network-flow algorithms (Régin 1994), achieving arc consistency far more efficiently than decomposing into individual sum constraints.

2. Pattern-Based Variable Modeling

Instead of individual shift variables, model each nurse's week as a work pattern (a sequence like M–A–_–N–_–M–_). Pre-generate all feasible patterns (respecting fatigue rules), then use a set variable or covering constraint to select one pattern per nurse. This dramatically shrinks the search space and integrates complex temporal rules directly into the variable domain.

3. Column Generation (for large MIP)

Formulate as a set-covering MIP: each column is a feasible weekly schedule for one nurse, and you select schedules to cover all shifts. Since the number of columns is exponential, generate them on-the-fly by solving a pricing sub-problem (a shortest-path or DP over the week) during branch-and-price. This is the approach used in industrial rostering software.

---

Challenge Corner

Extension: Suppose nurses can be swapped after the schedule is published — a nurse may trade a shift with a colleague, provided the result still satisfies all hard constraints.

Can you model the set of all valid pairwise swaps as a constraint problem? What data structure would you pre-compute to make swap-checking efficient at runtime?

Hint: think about which constraints are local to a single nurse's pattern versus global across the roster.

---

References

1. Ernst, A.T. et al. (2004). Staff scheduling and rostering: A review of applications, methods and models. European Journal of Operational Research, 153(1), 3–27. — The definitive survey.
2. Van den Bergh, J. et al. (2013). Personnel scheduling: A literature review. European Journal of Operational Research, 226(3), 367–385.
3. Musliu, N. (2006). Applying machine learning for search control in constraint solving for nurse rostering. — Early CP/ML hybrid approach.
4. MiniZinc Nurse Rostering Benchmark: [(www.minizinc.org/redacted)(www.minizinc.org/redacted) — includes nurse rostering models in the standard benchmark suite.

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

• expires on May 12, 2026, 11:53 AM 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 #30608.