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

[github-actions[bot]]

🗓️ Problem of the Day — Nurse Rostering

Problem Statement

Nurse Rostering (also called nurse scheduling or staff rostering) asks: given a set of nurses and a planning horizon (e.g., one week), assign each nurse to shifts so that all coverage requirements are met and personnel constraints are respected.

Concrete Instance

Consider 5 nurses over 3 days, with three shift types per day:

Shift	Time	Required nurses
Morning (M)	07:00–15:00	2
Evening (E)	15:00–23:00	2
Night (N)	23:00–07:00	1

Constraints:

• Each nurse works at most one shift per day.
• A nurse on a Night shift cannot work a Morning shift the next day (rest requirement).
• Each nurse works at least 2 and at most 5 shifts over the 3-day horizon.
• Some nurses have day-off requests (soft constraint: violate only if necessary).

Output: An assignment shift[n, d] ∈ {M, E, N, Off} for each nurse n and day d satisfying all hard constraints and minimising soft constraint violations.

---

Why It Matters

• Healthcare operations: Hospitals worldwide solve rostering problems every scheduling cycle. Understaffing risks patient safety; overstaffing wastes budget. Automated solvers can cut planning time from days to minutes.
• Labour law compliance: Regulations on maximum consecutive working hours, mandatory rest periods, and weekend equity are naturally expressed as constraints — making CP an ideal fit.
• Generalisation: The same model structure applies to airline crew scheduling, call-centre staffing, and factory shift planning.

---

Modeling Approaches

Approach 1 — Constraint Programming (CP)

Decision variables:
shift[n, d] ∈ {M, E, N, Off} for each nurse n ∈ 1..N, day d ∈ 1..D

Key constraints:

// Coverage
forall d, s: sum(n) [shift[n,d] = s] = required[s]

// No Night→Morning transition
forall n, d: shift[n,d] = N → shift[n,d+1] ≠ M

// Workload bounds
forall n: min_shifts ≤ sum(d) [shift[n,d] ≠ Off] ≤ max_shifts

Objective (soft constraints as penalties):

minimize sum(n,d) penalty[n,d] * [shift[n,d] ≠ preferred[n,d]]

Trade-offs: CP handles complex combinatorial constraints naturally. Global constraints like global_cardinality enforce coverage in one propagation step. Scales to ~50–100 nurses with good search strategies; larger instances need decomposition or hybrid methods.

---

Approach 2 — Integer Programming (MIP/ILP)

Decision variables:
Binary x[n, d, s] ∈ {0, 1} — 1 if nurse n works shift s on day d

Key constraints:

// At most one shift per day
forall n, d: sum(s) x[n,d,s] ≤ 1

// Coverage
forall d, s: sum(n) x[n,d,s] = required[s]

// Night→Morning rest
forall n, d: x[n,d,N] + x[n,d+1,M] ≤ 1

// Workload
forall n: min_shifts ≤ sum(d,s) x[n,d,s] ≤ max_shifts

Trade-offs: MIP solvers (Gurobi, CPLEX, HiGHS) excel at optimising the objective via LP relaxation bounds and branch-and-bound. Large, well-structured instances often solve faster than CP. However, complex non-numeric constraints (e.g., pattern-based rules) require many auxiliary binary variables and become unwieldy.

---

Example Model (MiniZinc — CP approach)

int: N = 5;  % nurses
int: D = 3;  % days
int: Off = 0; int: M = 1; int: E = 2; int: Night = 3;
array[1..N, 1..D] of var 0..3: shift;

% Coverage requirements
array[1..3] of int: required = [2, 2, 1];
constraint forall(d in 1..D, s in 1..3)(
  sum(n in 1..N)(shift[n,d] = s) = required[s]
);

% No Night -> Morning
constraint forall(n in 1..N, d in 1..D-1)(
  shift[n,d] = Night -> shift[n,d+1] != M
);

% Workload bounds
constraint forall(n in 1..N)(
  let { var int: worked = sum(d in 1..D)(shift[n,d] != Off) }
  in worked >= 2 /\ worked <= 5
);

solve satisfy;

---

Key Techniques

1. Global Cardinality Constraint (GCC)

The global_cardinality constraint enforces that values appear a specified number of times in an array — perfectly modelling coverage requirements. It enables arc-consistency propagation that prunes infeasible assignments far more aggressively than decomposing into individual sum constraints.

2. Variable and Value Ordering Heuristics

• Fail-First (smallest domain first): Assign shifts to nurses with the fewest valid options first, detecting infeasibility early.
• Most-constrained day first: Prioritise days where coverage is tightest.
• Nurse-preference guided value selection: Try preferred shifts before non-preferred to find good solutions quickly for the soft objective.

3. Symmetry Breaking

If nurses are interchangeable (same skills, same contract), many solutions are symmetric permutations. Adding lexicographic ordering constraints between identical nurses can reduce the search space by k! for k equivalent nurses. Be cautious: over-constraining with symmetry breaks can hurt optimisation (optima may lie in broken regions).

---

Challenge Corner

Extension: Suppose nurses have different skill levels (junior vs. senior) and each shift requires at least one senior nurse. How would you modify the CP model to enforce this?

Harder: Consider a rolling horizon of 28 days with fairness objectives (equal distribution of Night shifts across nurses over time). What decomposition strategy would keep the model tractable? Can you exploit the problem's natural week-by-week structure?

Open question: Nurse rostering with preferences is typically NP-hard. For practical hospital sizes (30–200 nurses), what is the empirical boundary where exact CP/MIP methods become impractical, and how do metaheuristics (tabu search, simulated annealing) compare on solution quality?

---

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. — Comprehensive survey of the field.

2. Musliu, N. (2006). Heuristic methods for automatic staff scheduling. PhD Thesis, TU Wien. — Covers CP and local search for nurse rostering in depth.

3. Rossi, F., van Beek, P., & Walsh, T. (eds.) (2006). Handbook of Constraint Programming. Elsevier. — Chapter 10 covers scheduling constraints; Chapter 7 covers global constraints including GCC.

4. The Nurse Rostering Competition (INRC-II): (www.inrcii.eu/redacted) — Benchmark instances and results from the International Nurse Rostering Competition, a great resource for testing solvers.

Generated by Constraint Solving — Problem of the Day · ● 1.7M · ◷

• expires on May 13, 2026, 12:06 PM UTC

[github-actions[bot]]

This discussion was automatically closed because it expired on 2026-05-13T12:06:40.788Z.

Closed by Workflow