Patient Flow Routing
Job Shop Scheduling
The average US ED patient spends 4.4 hours from arrival to disposition. Every shift, emergency physicians must decide which patients move to which department next. The Job Shop Scheduling Problem (Jm||Cmax) — strongly NP-hard — models this multi-department patient routing challenge.
Where This Decision Fits
Healthcare operations chain — the highlighted step is what this page optimizes
Problem Definition
Mapping the real-world ED patient flow problem to a Job Shop formulation
| Real-World Element | JSP Abstraction | Description |
|---|---|---|
| Patient | Job | Each patient follows a unique route through departments |
| Department | Machine | 5 departments: Triage, Lab, Imaging, Consult, Treatment |
| Processing Time | Duration | Minutes each patient spends at each department |
| ESI Level | Priority | Emergency Severity Index (1=critical, 5=non-urgent) |
| Makespan | Total ED Time | Time from first patient triage to last patient disposition |
subject to
Sij + pij ≤ Si,j+1 /* precedence: patient i finishes dept j before starting j+1 */
Sij + pij ≤ Skj ∨ Skj + pkj ≤ Sij /* disjunctive: no two patients use same dept at once */
Sij ≥ 0 /* non-negative start times */
Cmax ≥ Sij + pij /* makespan definition */
Interactive Solver
Select a scenario, choose algorithms, and optimize patient flow
Patient Flow Scheduler
| Patient | ESI | Route | Total (min) |
|---|
| Algorithm | Makespan (min) | Avg Wait (min) | Time (ms) |
|---|
Solution Algorithms
Three approaches from dispatching rules to decomposition heuristics
Key Insight
Shifting Bottleneck decomposes the m-machine job shop into a sequence of single-machine subproblems. At each iteration it identifies the department with the largest single-machine makespan (the bottleneck), fixes its optimal schedule via 1|rj|Lmax, then re-computes release dates for remaining departments. This yields near-optimal solutions in polynomial time for practical ED sizes.
Shortest Processing Time (SPT)
Priority Dispatching RuleAt each department, whenever the machine becomes free, select the patient with the shortest processing time at that department. SPT minimizes average flow time on a single machine and serves as a fast baseline for job shops.
- Initialize all patients at their first department in route
- Advance simulation clock to next department availability
- Among waiting patients, select the one with shortest processing time
- Schedule patient, update completion and release to next department
- Repeat until all patients complete all departments
Most Work Remaining (MWR)
Priority Dispatching RuleAt each department, when the machine becomes free, select the patient with the most total processing time remaining across all unfinished departments. MWR prioritizes complex patients to prevent them from becoming late bottlenecks.
- Compute total remaining work for each patient across unvisited departments
- At each scheduling decision point, pick patient with highest remaining work
- Break ties by ESI level (lower ESI = higher priority)
- Schedule patient, update remaining work and release times
Shifting Bottleneck
Decomposition HeuristicAdams, Balas & Zawack (1988). Iteratively identifies the bottleneck department (the one whose optimal single-machine schedule yields the largest makespan), fixes its schedule, then re-computes release dates and deadlines for remaining departments. Produces high-quality schedules by focusing optimization effort where it matters most.
- Compute release dates from precedence constraints (longest path)
- For each unscheduled department, solve 1|rj|Lmax optimally
- Identify the department with the largest Lmax (bottleneck)
- Fix the bottleneck schedule; add disjunctive arcs to the graph
- Re-compute release dates; repeat until all departments scheduled
Real-World Complexity
Factors that extend the textbook Job Shop model in emergency departments
Acuity-Based Preemption
ESI-1 patients (cardiac arrest, stroke) may preempt lower-acuity patients already being processed. This transforms the non-preemptive JSP into a preemptive variant with priority classes — significantly harder to optimize and requiring real-time rescheduling.
Department Capacity
Real departments have multiple parallel resources (e.g., 3 imaging rooms, 2 lab stations). This extends JSP to a Flexible Job Shop (FJSP) where each operation can be processed on any of several identical machines within a department.
Stochastic Arrivals
Patients arrive continuously and unpredictably. The static JSP assumes all jobs are known at time zero; real EDs face a dynamic, online scheduling problem where the job set changes every few minutes and processing times are uncertain.
Staff Availability
Department capacity varies by shift, break schedules, and specialization. A CT scanner requires a radiology technician; specialist consults depend on on-call availability. Machine availability windows add another layer of constraints to the scheduling model.
Readmission Loops
Some patients require return visits to departments (e.g., post-treatment imaging to verify reduction). This creates recirculation — a patient may visit Imaging twice — violating the classical JSP assumption that each job visits each machine at most once.
Academic References
- (2015). "Operations research/management contributions to emergency department patient flow optimization." IIE Transactions on Healthcare Systems Engineering, 5(2), 101–123. DOI: 10.1080/19488300.2015.1017676
- (2010). "Discrete event simulation for performance modelling in health care: a review of the literature." Journal of Simulation, 4(1), 42–51. DOI: 10.1057/jos.2009.25
- (2011). "Review of modeling approaches for emergency department patient flow and crowding research." Academic Emergency Medicine, 18(12), 1371–1379. DOI: 10.1111/j.1553-2712.2011.01135.x
Explore More Applications
This patient flow scheduling demo is part of a comprehensive library of optimization models across healthcare, agriculture, manufacturing, and logistics.