Nurse Rostering
Parallel Machine Scheduling
Assigning 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 problem is NP-hard (strongly for m ≥ 3 machines). Approximation algorithms like LPT achieve a 4/3-approximation ratio. For theory details, see Scheduling Problem Family.
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
Foundational works in scheduling theory