Healthcare Operations
Scheduling · Routing · Assignment
Healthcare systems face the most consequential scheduling decisions in operations research: every assignment of surgeon to operating room, every placement of an ambulance station, every routing choice for an emergency vehicle directly determines patient outcomes. The OR problems that arise are structurally identical to classical combinatorial problems — but the cost of a suboptimal solution is measured not in money but in lives and suffering.
From ICU bed allocation modeled as bin packing, to surgical scheduling as job shop, to ambulance positioning as p-median facility location, the healthcare domain spans a full spectrum of NP-hard combinatorial problems. Operations research has been applied in hospital settings since the 1960s; today, deployed systems manage operating rooms in hospitals across North America, Europe, and Asia.
A hospital surgical day requires coordinating patients through a sequence of stages: pre-operative preparation, the operating room procedure itself, and post-operative recovery. Each patient follows a fixed pathway through these stages, each stage has a known duration, and each room or bay can handle only one patient at a time. This maps directly to the job shop scheduling problem: patients are jobs, rooms are machines, procedures are operations with fixed routing and processing times. The objective is to minimise makespan — the time at which the last patient completes recovery — which determines when the surgical day ends. The problem is NP-hard for two or more machines.
OR Mapping: Patient → Job, Room → Machine, Procedure → Operation, Duration → Processing time, Pathway → Routing, End of day → Makespan. This is the classical job shop scheduling formulation applied to surgical suites.
s.t. Sij + pij ≤ Si,j+1 ∀ i, j // precedence within patient pathway
// no two patients in same room at same time
Sij + pij ≤ Skj or Skj + pkj ≤ Sij // machine capacity
Cmax ≥ Sij + pij ∀ i, j // all ops complete
// NP-hard for m ≥ 2 machines
OR Scheduling Solver
- Cardoen, B., Demeulemeester, E., & Beliën, J. (2010). Operating room planning and scheduling: A literature review. European Journal of Operational Research, 201(3), 921–932. Published
- Dexter, F., Macario, A., & Traub, R.D. (1999). An operating room scheduling strategy to maximize the use of operating room block time. Anesthesiology, 91(5), 1436–1443. Operational
A city must locate k ambulance stations among a set of candidate sites to minimise the demand-weighted total response time to all neighbourhoods. Each neighbourhood has a known demand (call frequency) and a known travel time to each candidate station. This is the classical p-median facility location problem: select exactly p facilities from candidates to minimise total weighted distance. The problem is NP-hard in general, though greedy and local search heuristics yield strong practical results.
OR Mapping: Candidate site → Facility, Neighbourhood → Demand node, Response time → Distance, Number of stations → p, Coverage standard → Service constraint. This is the p-median facility location formulation.
s.t. Σj yj = p // open exactly p stations
xij ≤ yj ∀ i, j // assign only to open stations
Σj xij = 1 ∀ i // each neighbourhood assigned once
// NP-hard. y_j, x_ij binary.
Ambulance Placement Solver
- ReVelle, C. & Swain, R. (1970). Central facilities location. Geographical Analysis, 2(1), 30–42. Published
- Daskin, M.S. (1995). Network and Discrete Location: Models, Algorithms, and Applications. John Wiley & Sons. Published
- Schilling, D., Elzinga, D.J., Cohon, J., Church, R., & ReVelle, C. (1979). The FLEET model: A fleet management and allocation model for ambulance systems in Baltimore. Operational
An emergency vehicle must find the fastest route through a city road network from its dispatch point to the emergency location. The road network is modeled as a weighted directed graph where intersections are nodes and roads are edges with travel-time weights. This is the classical shortest path problem — one of the few fundamental OR problems that is polynomial-time solvable. Dijkstra's algorithm runs in O((V+E) log V) with a binary heap, making real-time routing feasible even on large urban networks.
OR Mapping: Intersection → Node, Road segment → Edge, Travel time → Weight, Dispatch point → Source, Emergency location → Target. Unlike the other two tabs, this problem is polynomial — solvable optimally in polynomial time.
s.t. Σj fsj - Σj fjs = 1 // flow out of source
Σj fjt - Σj ftj = 1 // flow into target
Σj fij = Σj fji ∀ i ≠ s,t // flow conservation
// Dijkstra: O((V+E) log V) with binary heap
Emergency Routing Solver
- Dijkstra, E.W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269–271. Published
- Toregas, C., Swain, R., ReVelle, C., & Bergman, L. (1971). The location of emergency service facilities. Operations Research, 19(6), 1363–1373. Operational
All Healthcare Applications
Browse the complete collection