🧩 Constraint Solving POTD:Nurse Rostering — Scheduling Under Real-World Constraints

[github-actions[bot]]

Category: Scheduling | Difficulty: Intermediate–Advanced | Date: 2026-04-25

---

Problem Statement

Given a set of nurses, a planning horizon (e.g., one week), and a set of daily shifts, assign each nurse to at most one shift per day such that:

• Coverage requirements are met: each shift on each day needs a minimum number of nurses.
• Hard constraints are respected: no nurse works two consecutive night-shifts, minimum rest time between shifts, contract hours limits.
• Soft constraints are optimized: nurses get preferred days off, fairness in weekend assignments, balanced workloads.

Small Concrete Instance

• Nurses: n1, n2, n3, n4 (4 nurses)
• Days: Monday–Sunday (7 days)
• Shifts: D (Day 08:00–16:00), E (Evening 16:00–00:00), N (Night 00:00–08:00), O (Off)
• Coverage: Each shift D, E, N requires at least 1 nurse per day.
• Hard constraint: No nurse works more than 5 days in the week or two consecutive N shifts.
• Goal: Find an assignment satisfying all hard constraints while minimising violations of soft preferences.

       Mon  Tue  Wed  Thu  Fri  Sat  Sun
n1      D    D    O    E    D    O    O
n2      E    O    D    D    O    N    D
n3      N    E    E    O    E    D    E
n4      O    N    N    N    N    O    N

Input: nurse list, shift types, horizon, coverage demands, hard/soft constraint rules.
Output: A feasible (ideally optimal) roster minimising soft-constraint penalty.

---

Why It Matters

• Healthcare operations: Hospitals run 24/7; under- or over-staffing directly affects patient safety and nurse wellbeing. Automated rostering saves dozens of hours of manual scheduling each month.
• Regulatory compliance: Labor laws (EU Working Time Directive, Joint Commission standards) impose strict rest-period rules that manual planners routinely violate under time pressure. A constraint model enforces them structurally.
• General applicability: The same model structure applies to airline crew scheduling, call-centre shifts, and police/fire duty assignments.

---

Modeling Approaches

Approach 1 — Constraint Programming (CP)

Decision variables:

shift[n, d] ∈ {D, E, N, O}   for each nurse n, day d

Key constraints:

# Coverage
forall d, s ∈ {D,E,N}: sum(n | shift[n,d] = s) >= required[s,d]

# No consecutive nights
forall n, d: not (shift[n,d] = N ∧ shift[n,d+1] = N)

# Weekly hours (each non-Off shift = 8h, max 40h)
sum(d | shift[n,d] != O) <= 5   forall n

# Soft: penalise working on preferred-off days
minimize sum(n,d | pref_off[n,d] ∧ shift[n,d] != O) * penalty

Trade-offs: CP models express sequencing and combinatorial structure elegantly. Global constraints like gcc (global cardinality constraint) handle coverage in one propagation step, pruning heavily. Best for tight feasibility checks and medium horizons (≤ 4 weeks, ≤ 50 nurses).

---

Approach 2 — Mixed-Integer Programming (MIP)

Decision variables:

x[n, d, s] ∈ {0, 1}   = 1 if nurse n works shift s on day d

Key constraints:

# At most one shift per day
sum_s x[n,d,s] <= 1                          forall n, d

# Coverage
sum_n x[n,d,s] >= required[s,d]             forall d, s

# No consecutive nights
x[n,d,N] + x[n,d+1,N] <= 1                  forall n, d

# Weekly hours
sum_{d,s≠O} x[n,d,s] <= 5                   forall n

# Objective: minimise soft violations
minimize sum_{n,d} pref_off[n,d] * (1 - x[n,d,O])

Trade-offs: MIP benefits from strong LP relaxations and mature solvers (Gurobi, CPLEX, HiGHS). Scales to large instances with hundreds of nurses when constraints are mostly linear. However, complex sequencing rules (e.g., "no more than 3 consecutive evenings") create many binary clauses that bloat the model.

---

Example Model — MiniZinc (CP)

int: N = 4; int: D = 7;
enum SHIFT = {Day, Eve, Ngt, Off};
int: required_min = 1;

array[1..N, 1..D] of var SHIFT: roster;

% Coverage: at least 1 nurse per non-Off shift per day
constraint forall(d in 1..D, s in {Day, Eve, Ngt})(
  sum(n in 1..N)(roster[n,d] = s) >= required_min
);

% No two consecutive nights
constraint forall(n in 1..N, d in 1..D-1)(
  not (roster[n,d] = Ngt /\ roster[n,d+1] = Ngt)
);

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

solve satisfy;
output [show(roster[n,d]) ++ if d=D then "\n" else " " endif
        | n in 1..N, d in 1..D];

---

Key Techniques

1. Global Cardinality Constraint (GCC)

The gcc constraint enforces that the number of variables taking each value falls within given bounds — perfect for coverage requirements. Hall's theorem underpins its arc-consistency algorithm (O(n log n)), delivering powerful pruning in a single propagator rather than many individual sum constraints.

2. Symmetry Breaking

Nurses are often interchangeable up to their preferences. Ordering nurses lexicographically on their roster vectors (lex_less(roster[1], roster[2])) can reduce the search space by up to N!. Be careful: symmetry breaking may be incompatible with soft preferences that distinguish nurses — apply it only when nurses are truly symmetric.

3. Large Neighbourhood Search (LNS)

For real-world instances (30+ nurses, 4-week horizon), exact methods are too slow. LNS fixes a random subset of the roster and re-optimises the free portion using CP or MIP. A typical destroy/repair cycle: randomly unfix 20–30% of assignments, solve the sub-problem with a time limit, accept if improved. This meta-heuristic reaches high-quality solutions quickly and is the backbone of industrial nurse-scheduling tools.

---

Challenge Corner

🤔 Extend the model: Real rosters must handle skill levels (e.g., only senior nurses can lead night shifts) and team cohesion (pairs of nurses who work well together prefer to share shifts).

• How would you encode skill-based coverage — e.g., "each day shift needs at least 1 senior and 2 juniors"?
• Can you add a constraint ensuring that nurse n1 and n2 are assigned to the same shift on at least 3 days per week?
• What happens to the LP relaxation bound in the MIP model when you add these constraints? Does it tighten or loosen?

---

References

1. Burke et al. (2004). The State of the Art of Nurse Rostering. Journal of Scheduling 7(6):441–499. — The canonical survey; covers problem taxonomy and solution approaches.
2. Ernst et al. (2004). Staff scheduling and rostering: A review of applications, methods and models. European Journal of Operational Research 153(1):3–27.
3. Rossi, van Beek & Walsh (eds.) (2006). Handbook of Constraint Programming. Elsevier. — Chapter 7 covers scheduling; Chapter 10 covers global constraints including GCC.
4. INRC-II (International Nurse Rostering Competition 2nd edition). Benchmark instances and results: (www.inrc2.eu/redacted) — Great starting point for testing your own solver.

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

• expires on May 2, 2026, 12:53 PM UTC

[github-actions[bot]]

💥 WHOOSH! 🦸 The Smoke Test Agent swoops in!

⚡ POW! Claude engine RUN 24931278162 was here — and the systems are NOMINAL!

🌟 "With great agentic power comes great automated testing responsibility."

💫 ZAPP! All MCP tools checked ✅ — See you next run, brave developer! 🚀

Note

🔒 Integrity filter blocked 1 item

The following item was blocked because it doesn't meet the GitHub integrity level.

• fix: resolve node: command not found in Copilot engine on GPU self-hosted runners #28451 pull_request_read: has lower integrity than agent requires. The agent cannot read data with integrity below "approved".

To allow these resources, lower min-integrity in your GitHub frontmatter:

tools:
  github:
    min-integrity: approved  # merged | approved | unapproved | none

💥 [THE END] — Illustrated by Smoke Claude · ● 288.3K · ◷

[github-actions[bot]]

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

A newer discussion is available at Discussion #28721.