Bed Management
Bin Packing + Knapsack
Healthcare · Inpatient · TacticalA 120-bed hospital must assign incoming ED patients to wards of fixed capacity while maximizing throughput. Occupancy above 85% increases mortality and ED boarding (Bain et al., 2010). This combines Bin Packing for ward allocation with 0-1 Knapsack for cardiac triage prioritization.
The Problem
Phase 3 · Patient Flow — Bed Management
Consider a 120-bed hospital with four specialty wards: Medical (35 beds), Surgical (30 beds), Cardiac (25 beds), and General (30 beds). Each shift, the Emergency Department admits patients who require specific ward types. Some patients (isolation cases) consume two bed-equivalents due to private-room requirements.
The bin packing component assigns ED patients to ward “bins” of limited capacity. When beds are scarce, a secondary knapsack component selects which waitlisted patients to admit, maximizing total clinical priority within available bed-days. Optimizing bed allocation can improve throughput by 10–20% without adding physical capacity (Hulshof et al., 2012).
| Real World | Mathematical Model |
|---|---|
| Hospital ward | Bin (fixed capacity) |
| Patient | Item (bed-equivalents = size) |
| Ward bed count | Bin capacity C |
| Specialty requirement | Bin-type constraint |
| Clinical priority | Item value (knapsack) |
| Length of stay | Item weight (knapsack) |
subject to
Σj xij = 1 // each patient assigned to exactly one ward
Σi bi · xij ≤ Cj // ward capacity not exceeded
xij ∈ {0, 1} // binary assignment
subject to
Σi di · xi ≤ W // total bed-days ≤ available capacity
xi ∈ {0, 1} // admit or not
Where bi is the bed-equivalent demand of patient i, Cj is the ward capacity, pi is clinical priority (1–10), and di is expected length of stay in days.
See full Packing & Knapsack theoryTry It Yourself
Assign patients to hospital wards
Bed Management Optimizer
20 Patients · 4 Wards| # | Patient / Diagnosis | Beds | Specialty |
|---|
Select a scenario and click Solve.
| Algorithm | Wards | Utilization | Time |
|---|---|---|---|
| Select a scenario to begin | |||
The Algorithms
Heuristic and exact approaches
First Fit (FF)
O(n²)Process patients in arrival order. For each patient, scan wards left to right and place the patient in the first ward of the correct specialty with enough remaining beds. If no ward fits, an overflow ward is opened. Simple but sensitive to arrival order.
First Fit Decreasing (FFD)
O(n log n) | Guarantee: ≤ 11/9 · OPT + 6/9Sort patients by bed-equivalents in descending order, then apply First Fit. Isolation patients (2 beds) are placed first, creating a foundation that single-bed patients fill efficiently. Provable worst-case guarantee established for general bin packing.
Best Fit Decreasing (BFD)
O(n log n)Sort patients by bed-equivalents descending. For each patient, place in the ward with the least remaining capacity that can still accommodate them. Produces tightly packed wards, maximizing utilization and reducing overflow. Often matches or outperforms FFD in practice (Demeester et al., 2010).
Dynamic Programming (Knapsack)
O(n · W) | Pseudo-polynomialFor the cardiac triage scenario, DP finds the optimal subset of waitlisted patients to admit given limited bed-days. Builds a table of subproblems bottom-up, guaranteeing maximum total clinical priority. Used when the capacity W is bounded (10 bed-days in our scenario).
Real-World Complexity
Why hospital bed management goes beyond the 1D model
Beyond Bin Packing
- Infection control — MRSA, C. diff, and TB patients require negative-pressure isolation rooms; cohorting rules prevent mixing infection types
- Acuity matching — ICU, step-down, and general beds have different monitoring capabilities; patient acuity must match bed type
- Gender segregation — Many wards require same-gender room assignments, adding parity constraints
- Stochastic arrivals — ED admission rates are uncertain and bursty; robust models must handle demand spikes
- Discharge uncertainty — Length-of-stay is probabilistic; early or late discharges shift available capacity dynamically
From bin packing to stochastic assignment
The 1-D packing framing on this page compresses the problem into a tractable offline snapshot: given a known demand list and given bed capacities, how do we pack optimally? Real hospital bed management operates one step richer:
- The canonical academic benchmark is the Patient Admission Scheduling (PAS) problem of Demeester et al. (2010) and Ceschia & Schaerf (2011) — an ILP/CSP with gender-mixing, equipment, transfer, and length-of-stay-horizon constraints. This page’s bin-packing is a simplification of the PAS backbone.
- On top, real bed managers face stochastic arrivals and discharges. Thompson et al. (2009) model dynamic reallocation as an MDP; Bekker & Koeleman (2011) smooth admission schedules against variance; Helm & Van Oyen (2014) jointly optimize elective admissions and bed pools.
- The full problem therefore spans Inpatient × Tactical (this page’s cell in the Hulshof 2012 taxonomy) and Inpatient × Online-operational (live transfer / surge management). Treat the packing model as the floor plan; the MDP literature handles day-to-day fluctuation.
Key References
Foundational works in healthcare bed management
- (2010). Applied “Myths of ideal hospital occupancy.” Medical Journal of Australia, 192(1), 42–43. doi:10.5694/j.1326-5377.2010.tb03401.x
- (2010). Seminal “A hybrid tabu search algorithm for automatically assigning patients to beds.” Artificial Intelligence in Medicine, 48(1), 61–70. doi:10.1016/j.artmed.2009.09.001 — introduces the Patient Admission Scheduling (PAS) benchmark on which much of the bed-assignment literature stands.
- (2011). Applied “Local search and lower bounds for the patient admission scheduling problem.” Computers & Operations Research, 38(10), 1452–1463. doi:10.1016/j.cor.2010.12.004
- (2011). Applied “Scheduling admissions and reducing variability in bed demand.” Health Care Management Science, 14(3), 237–249. doi:10.1007/s10729-011-9163-x — stochastic formulation of the same decision this page models deterministically.
- (2009). Seminal “Efficient short-term allocation and reallocation of patients to floors of a hospital during demand surges.” Operations Research, 57(2), 261–273. doi:10.1287/opre.1080.0584 — MDP-based dynamic bed allocation; the canonical stochastic counterpart to this page’s bin-packing model.
- (2014). Applied “Design and optimization methods for elective hospital admissions.” Operations Research, 62(6), 1265–1282. doi:10.1287/opre.2014.1317
- (1969). Seminal “The set-partitioning problem: Set covering with equality constraints.” Operations Research, 17(5), 848–856. doi:10.1287/opre.17.5.848 — the bin-packing / set-partitioning foundation.
- (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 × Tactical.
Need to optimize patient flow?
From bed management to operating room scheduling and staff rostering, mathematical modeling can transform hospital operations. Let’s discuss how Operations Research can work for your healthcare system.