Workforce Assignment
Linear Assignment Problem
Healthcare · Inpatient · Offline-opA 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
From single-shift LAP to multi-period ILP
The solver on this page is the classical Linear Assignment Problem (LAP) of Kuhn (1955), solved to optimality in $O(n^3)$ for a single shift on a single ward. Production nurse-staffing systems extend this in two directions:
- Multi-period ILP — decisions span a week or month, with shift patterns, rest constraints, and preference balancing tied together (Punnakitikashem et al., 2013). This is the integrated staffing + assignment formulation; the generic personnel-scheduling survey is Van den Bergh et al. (2013).
- Stochastic extensions — patient acuity (and therefore the cost matrix) is revealed progressively; Markov-policy and scenario-based SP models assign under uncertainty.
- Dynamic re-assignment — mid-shift perturbations (new admissions, deterioration) trigger a new LAP solve. Clark et al. (2015) survey the re-scheduling variant.
The page occupies Inpatient × Offline-operational in the Hulshof (2012) taxonomy. The companion nurse-rostering page (one cell wider in time) solves the multi-period ILP that this page’s single-shift LAP is a slice of.
Key References
Foundational works in nurse-patient assignment optimization
- (1955). Seminal “The Hungarian method for the assignment problem.” Naval Research Logistics Quarterly, 2(1–2), 83–97. doi:10.1002/nav.3800020109 — the Hungarian algorithm used by the solver on this page.
- (1957). Seminal “Algorithms for the assignment and transportation problems.” Journal of the Society for Industrial and Applied Mathematics, 5(1), 32–38. doi:10.1137/0105003 — polynomial-time correctness proof of Kuhn’s method.
- (2002). Seminal “Assigning patients to nurses in neonatal intensive care.” Journal of the Operational Research Society, 53(1), 25–35. doi:10.1057/palgrave.jors.2601248 — the canonical healthcare application of the Hungarian method.
- (2010). Applied “A data-integrated simulation-based optimization for assigning nurses to inpatient rotations.” Health Care Management Science, 13(3), 210–221. doi:10.1007/s10729-009-9125-2
- (2013). Applied “A stochastic programming approach for integrated nurse staffing and assignment.” IIE Transactions, 45(10), 1059–1076. doi:10.1080/0740817X.2012.763002 — the multi-period stochastic ILP that generalizes the single-shift Hungarian assignment on this page.
- (2013). Survey “Personnel scheduling: A literature review.” European Journal of Operational Research, 226(3), 367–385. doi:10.1016/j.ejor.2012.11.029
- (2004). Survey “Staff scheduling and rostering: A review of applications, methods and models.” European Journal of Operational Research, 153(1), 3–27. doi:10.1016/S0377-2217(03)00095-X
- (2015). Applied “Rescheduling nursing shifts: Scoping the challenge and examining the potential of mathematical model-based approaches.” Journal of Nursing Management, 23(4), 411–420. doi:10.1111/jonm.12158
- (2012). Taxonomy “Taxonomic classification of planning decisions in health care: A structured review of the state of the art in OR/MS.” Health Systems, 1(2), 129–175. doi:10.1057/hs.2012.18 — positions this page at Inpatient × Offline-operational.
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.