Workforce Assignment
Linear Assignment Problem
A 30-bed medical-surgical ward must assign 8 nurses to 8 patients each shift, matching competency to acuity while minimizing pod-distance travel. This is the Linear Assignment Problem (LAP) — solvable optimally in O(n³) time via the Hungarian algorithm. Research shows optimal assignment reduces adverse events by 10–20% and nurse burnout by 15–25%.
The Problem
Phase 2 · Staff Planning — Workforce Assignment
On a medical-surgical ward, each shift begins with a critical decision: which nurse cares for which patient? The charge nurse must balance patient acuity (severity levels 1–5), nurse competency, certification match, and physical proximity across pods. The American Nurses Association recommends a maximum of 4–6 patients per nurse on med-surg units; here we model the 1:1 assignment for the highest-acuity subset.
The cost of assigning nurse i to patient j captures the acuity-competency mismatch (squared, penalizing large gaps) plus a pod-distance penalty minus a certification discount when a nurse holds relevant credentials (CCRN, PCCN).
| OR Concept | Healthcare Mapping |
|---|
subject to
Σj xij = 1 // each nurse assigned to exactly one patient
Σi xij = 1 // each patient assigned to exactly one nurse
xij ∈ {0, 1} // binary assignment decision
Where cij
is the cost of assigning nurse i to patient j, computed as:
cij = (acuityj − competencyi)² × 20 + distance(podi, podj) × 15 − certDiscount
Pod distances: same pod = 0, adjacent = 1, far = 2. Certification discount: 10 points when the nurse holds CCRN or PCCN relevant to the patient condition.
See full Assignment Problem theoryTry It Yourself
Assign nurses to patients and compare algorithms
Nurse-Patient Assignment Optimizer
8 Nurses · 8 PatientsReady. Select a scenario and click Solve.
| Algorithm | Total Cost | Max Single | Time |
|---|
The Algorithms
From greedy heuristics to provably optimal solutions
Hungarian Algorithm (Kuhn–Munkres)
O(n³) | Guarantee: globally optimalThe Hungarian algorithm works by iteratively reducing the cost matrix through row and column subtractions, then finding a maximum matching of zero-cost entries. When a complete matching cannot be found, it adjusts the matrix using the minimum uncovered value. The result is a provably optimal one-to-one assignment that minimizes total cost across all nurse-patient pairs simultaneously.
Named after the Hungarian mathematicians König and Egerváry, and formalized by Harold Kuhn in 1955 and James Munkres in 1957. For an n×n cost matrix, the algorithm performs at most n iterations of O(n²) work.
Greedy Assignment
O(n²) | No optimality guaranteeSort all n² nurse-patient pairs by cost (ascending). Iterate through the sorted list: assign the pair if neither the nurse nor the patient has been assigned yet. This is fast and intuitive — it always picks the locally cheapest available pair — but it ignores the global structure of the cost matrix. A cheap early assignment can block a much better overall solution.
In practice, greedy often performs within 5–15% of optimal for well-structured cost matrices, but can be arbitrarily bad in adversarial cases. For safety-critical domains like healthcare staffing, the optimality gap matters.
Auction Algorithm
O(n² log n) typical | Guarantee: ε-optimalBertsekas' Auction Algorithm (1979) models the assignment as an auction: patients are “objects” and nurses are “bidders.” Each nurse bids on their most profitable patient, raising the patient’s price. The process repeats until all nurses are assigned. It is naturally parallelizable and converges to within ε of the optimal cost, where ε is a tunable parameter.
Real-World Complexity
Why nurse-patient assignment goes beyond a simple cost matrix
Beyond the Assignment Matrix
- Continuity of care — Patients benefit from seeing the same nurse across consecutive shifts; reassignment disrupts therapeutic rapport and increases handoff errors
- Skill mix requirements — Some patients need nurses with specific certifications (CCRN for cardiac, PCCN for progressive care); a competency gap can delay critical interventions
- Workload balancing — Total acuity points per nurse should be equitable; overloading one nurse while underloading another leads to burnout and errors
- Geographic clustering — Nurses assigned to patients in distant pods spend more time walking and less time at the bedside, reducing response times
- Dynamic reassignment — Patient acuity can change mid-shift (deterioration, new admissions, discharges); the assignment must be re-optimized in real time
Key References
Foundational works in nurse-patient assignment optimization
- (2002). “Assigning patients to nurses in neonatal intensive care.” Journal of the Operational Research Society, 53(1), 25–35. DOI: 10.1057/palgrave.jors.2601248
- (2010). “A data-integrated simulation-based optimization for assigning nurses.” Health Care Management Science, 13(3), 210–221. DOI: 10.1007/s10729-009-9125-2
- (2015). “Rescheduling nursing shifts.” Journal of Nursing Management, 23(4), 411–420. DOI: 10.1111/jonm.12158
Need to optimize your healthcare staffing?
From nurse-patient assignment to operating room scheduling and resource allocation, mathematical modeling can transform clinical operations. Let’s discuss how Operations Research can work for your organization.