Nurse Rostering
Parallel Machine Scheduling
Healthcare · Inpatient · Offline-opAssigning weekly shifts to nursing staff, modeled as Pm||Cmax. Nurses are parallel machines, shifts are jobs, and the objective is to minimize the maximum workload across all nurses — ensuring balanced, fair rosters.
Where This Decision Fits
Healthcare sector decision chain
The Problem
Mapping nurse rostering to parallel machine scheduling
A hospital ward must assign a set of shifts across a 7-day week to a pool of nurses. Each shift has an acuity load (effective hours weighted by patient complexity). The goal is to minimize the maximum total workload (Cmax) across all nurses, ensuring no single nurse is overloaded while others remain underutilized. Additional constraints limit maximum shifts per nurse and prohibit back-to-back shifts.
| Healthcare Domain | Scheduling Element | Example | |
|---|---|---|---|
| Nurse | Machine (parallel) | Nurse Alvarez, Senior ICU | |
| Shift | Job | Day 3 Night Shift (10h) | |
| Acuity hours | Processing time (pj) | Night = 12h weighted load | |
| Max shifts / nurse | Machine capacity constraint | ≤ 5 shifts per 7-day cycle | |
| Balanced workload | Objective: min Cmax | Most-loaded nurse’s total |
This slice of the problem is NP-hard (strongly for $m \geq 3$ machines; reduces from PARTITION). LPT is a $\tfrac{4}{3} - \tfrac{1}{3m}$-approximation (Graham, 1969). For theory, see the Scheduling family.
But: Pm Cmax is a simplification. It captures workload balance across nurses but ignores the structure that defines real nurse rostering — shift types (morning / evening / night), skill matching, legal rest, coverage by time-of-day, weekend patterns, and preferences. The full problem is the Nurse Rostering Problem (NRP), an ILP/CSP surveyed by Burke et al. (2004), Ernst et al. (2004), and Van den Bergh et al. (2013). See the next section.
The Canonical NRP Formulation
What the healthcare-OR literature actually solves
The Nurse Rostering Problem (NRP) is a Mixed-Integer Linear Program over a planning horizon (typically 4–6 weeks). Shift types, skill classes, legal rest, coverage requirements, and preference/fairness objectives all appear explicitly.
Sets & indices
| Symbol | Meaning |
|---|---|
| $i \in N$ | Nurse, with skill class $c(i) \in C$ |
| $d \in D$ | Day in the planning horizon |
| $s \in S$ | Shift type (e.g., morning, evening, night) |
| $w \in W$ | Weekend index (Sat–Sun pair) |
Parameters
| Symbol | Meaning |
|---|---|
| $r_{d,s,c}$ | Required nurses of skill class $c$ on day $d$, shift $s$ (coverage target) |
| $q_{i,s}$ | $1$ if nurse $i$ is qualified to work shift $s$, else $0$ |
| $M_i$ | Maximum shifts nurse $i$ can work over the horizon |
| $L_i$ | Minimum shifts (contractual floor) |
| $\pi_{i,d,s}$ | Preference weight — $+1$ wants, $-1$ avoids, $0$ neutral |
| $h_{s,s'}$ | $1$ if shift $s$ on day $d$ followed by $s'$ on $d{+}1$ violates rest, else $0$ |
Decision variables
Objective
Hard constraints
Soft constraints (linked to objective slacks)
The resulting ILP is NP-hard (Burke et al., 2004) and typically solved with commercial MIP solvers for small wards, or with hybrid metaheuristics (tabu search, VNS, ILP + LNS) for large hospitals. Real deployments additionally model: weekend-block patterns, forbidden shift sequences, employment-contract personalization, and inter-ward sharing.
Emergency-Department staff rostering with service leveling
A frontier extension relevant to ED operations: replace the deterministic coverage target $r_{d,s,c}$ with a service-level constraint tied to time-varying patient arrival intensity $\lambda(t)$. The staffing profile is sized so that the probability of a patient waiting more than some threshold $\tau$ is bounded below a target (e.g., 90% within 30 min). This couples rostering with queueing theory / simulation. See Erhard et al. (2018) for the physician-scheduling analogue and Brunner & Bard (2013) for the stochastic physician case.
Interactive Solver
Choose a scenario, review data, then solve and compare algorithms
Roster Builder
Phase 2 · Staff PlanningSolution Algorithms
Three approaches from scheduling theory
Key Insight
LPT (Longest Processing Time first) assigns the longest remaining shift to the least-loaded nurse. This single sorting step — processing shifts in descending order of acuity — dramatically improves workload balance compared to arbitrary assignment. Graham (1969) proved LPT achieves a 4/3 − 1/(3m) approximation ratio for Pm||Cmax.
LPT — Longest Processing Time
4/3-approximation · O(n log n) · Greedy
Sort Shifts Descending
Order all shifts by acuity load from highest to lowest. Night shifts (12h) come first, then morning (10h), then evening (9h).
Assign to Least-Loaded Nurse
For each shift in sorted order, assign it to the nurse with the smallest current total workload. If tied, assign to the nurse with fewer shifts.
Enforce Constraints
Skip any nurse who has reached max shifts or would create a back-to-back violation. Move to next least-loaded eligible nurse.
MULTIFIT — Binary Search + FFD
1.22-approximation · O(n log n · log(psum)) · Bin-Packing Reduction
Set Bounds
Lower bound L = ⌈total_acuity / m⌉. Upper bound U = max acuity shift + L. These bracket the optimal Cmax.
Binary Search on Target
Try mid = (L + U) / 2 as the target maximum load. Use First Fit Decreasing (FFD): sort shifts descending, assign each to the first nurse whose load + shift ≤ target.
Converge
If FFD fits all shifts into m nurses within target, tighten U = mid. Otherwise, loosen L = mid. Repeat until U − L < 0.5.
List Scheduling — Baseline
2 − 1/m approximation · O(n log m) · Greedy
Process in Given Order
Take shifts in their natural order (Day 1 Morning, Day 1 Evening, Day 1 Night, Day 2 Morning, …) without sorting.
Assign to Least-Loaded Nurse
Each shift goes to the nurse with the smallest current load (same greedy step as LPT, but input order differs).
No Pre-Processing
The lack of sorting means large shifts may appear late, causing imbalance. This baseline demonstrates why LPT’s sort step matters.
Real-World Complexity
Why hospital rostering goes far beyond Pm||Cmax
Labor Law Compliance
Working time directives mandate maximum weekly hours, minimum rest between shifts (e.g., 11h in the EU), and overtime caps. Violations incur legal penalties and endanger patient safety.
Skill & Certification Constraints
ICU, cardiac, pediatric, and general wards require specific certifications. A feasible roster must match skill supply to unit demand, not just balance hours.
Nurse Preferences
Preferred days off, shift-type preferences (no nights), seniority-based priority, and part-time contracts add soft constraints that affect retention and morale.
Fatigue & Safety
Consecutive night shifts increase error rates. Circadian disruption models penalize rapid rotation patterns. Research links fatigue to medication errors and patient falls.
Continuity of Care
Patients benefit from seeing the same nurse across shifts. Continuity constraints assign nurses to consistent patient groups, adding assignment dependencies across days.
References
Nurse rostering canon · Pm Cmax scheduling theory · physician / ED extensions