Bed Management

Bin Packing + Knapsack

Strategic Staff Planning Patient Flow Supply Chain

A 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)

Bin Packing Formulation (Ward Assignment) minimize Σ_j y_j // wards opened (overflow)
subject to
  Σ_j x_ij = 1    // each patient assigned to exactly one ward
  Σ_i b_i · x_ij ≤ C_j    // ward capacity not exceeded
  x_ij ∈ {0, 1} // binary assignment

Knapsack Formulation (Cardiac Triage) maximize Σ_i p_i · x_i // total clinical priority
subject to
Σ_i d_i · x_i ≤ W // total bed-days ≤ available capacity
x_i ∈ {0, 1} // admit or not

Where b_i is the bed-equivalent demand of patient i, C_j is the ward capacity, p_i is clinical priority (1–10), and d_i is expected length of stay in days.

See full Packing & Knapsack theory

Try It Yourself

Assign patients to hospital wards

Bed Management Optimizer

20 Patients · 4 Wards

Scenario

Patients to Assign

#	Patient / Diagnosis	Beds	Specialty

Ward Visualization

Select a scenario and click Solve.

Algorithm Comparison

Algorithm	Wards	Utilization	Time
Select a scenario to begin

Assignment Details

Ward assignments will appear here after solving.

The Algorithms

Heuristic and exact approaches

Heuristic

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.

Heuristic

First Fit Decreasing (FFD)

O(n log n) | Guarantee: ≤ 11/9 · OPT + 6/9

Sort 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.

Heuristic

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).

Exact

Dynamic Programming (Knapsack)

O(n · W) | Pseudo-polynomial

For 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

Key References

Foundational works in healthcare bed management

Bain, C.A. et al. (2010). “Myths of ideal hospital occupancy.” MJA, 192(1), 42–43. DOI: 10.5694/j.1326-5377.2010.tb03401.x
Demeester, P. et al. (2010). “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
Hulshof, P.J.H. et al. (2012). “Taxonomic classification of planning decisions in health care.” Health Systems, 1(2), 129–175. DOI: 10.1057/hs.2012.18

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.

Connect on LinkedIn

Disclaimer

Data shown is illustrative. Patient names, diagnoses, and hospital configurations are representative scenarios for educational purposes and do not reflect any specific hospital operation or real patient data.