Operating Room Scheduling
Job Shop Scheduling
The Problem
From hospital corridors to optimization theory
In a modern hospital, each patient requires a specific sequence of procedures across different rooms and resources: pre-operative preparation, the operating room itself, and post-operative recovery. Critically, different patients may require these resources in different orders. An emergency trauma patient might go directly to the OR before any pre-op, while a routine surgical patient follows the standard pre-op, OR, recovery pathway.
This is precisely the structure of a Job Shop Scheduling problem. Each patient is a job, each room or resource is a machine, and each procedure is an operation with a specific processing time on a specific machine. The goal is to minimize the makespan — the total time from the start of the first procedure to the completion of the last, effectively minimizing the length of the surgical day.
| Hospital Domain | Job Shop Model | |
|---|---|---|
| Patient | Job | |
| Room / Resource | Machine | |
| Procedure | Operation | |
| Procedure duration | Processing time | |
| Patient pathway | Job routing (machine order) | |
| End of surgical day | Makespan (Cmax) |
Try It Yourself
Edit patient data, add or remove patients, then solve with all dispatching rules
Configuration
4 Patients · 3 Rooms · Click any cell to edit| Patient | Step 1 Room | Step 1 (min) | Step 2 Room | Step 2 (min) | Step 3 Room | Step 3 (min) |
|---|
The Algorithm
Giffler-Thompson active schedule generation
Giffler-Thompson Procedure
The Giffler-Thompson algorithm (1960) generates active schedules — schedules where no operation can be started earlier without delaying another. All optimal schedules are active, so this search space contains the optimum. The algorithm uses a priority rule to break ties and select among competing operations.
Identify Schedulable Operations
Build the set of all operations whose predecessors within the same job have already been scheduled. Initially, this is the first operation of every patient.
Find Earliest Completion
For each schedulable operation, compute its earliest possible completion time (EFT) based on when the machine becomes free and when the job's previous operation finishes. Let EFT* be the minimum across all schedulable operations, and let m* be the machine where this minimum occurs.
Build Conflict Set
Among all schedulable operations assigned to machine m*, select those that could start before EFT*. These operations conflict with the earliest-finishing operation — if we don't schedule them now, they might be delayed.
Apply Priority Rule
From the conflict set, select one operation using the dispatching rule:
- SPT (Shortest Processing Time): choose the operation with the smallest processing time, favoring quick procedures
- LPT (Longest Processing Time): choose the operation with the largest processing time, prioritizing lengthy surgeries
- MWR (Most Work Remaining): choose the operation belonging to the patient with the most total processing time still remaining
Schedule and Repeat
Schedule the selected operation at its earliest feasible start time on machine m*. Remove it from the schedulable set, update machine and job availability times, and return to Step 1. Repeat until all operations are scheduled.
Real-World Complexity
Why hospital scheduling goes beyond the basic model
Surgeon Availability
Surgeons have limited hours, specialty constraints, and may operate across multiple hospitals. This adds resource calendars and eligibility constraints.
Equipment Sterilization
Sequence-dependent setup times between surgeries for cleaning, sterilization, and room preparation. Extends the model to SDST Job Shop.
Emergency Surgeries
Unplanned arrivals disrupt the schedule, requiring robust or stochastic models with reserved capacity for urgent cases.
Patient Priority
Medical urgency, waiting list position, and case severity introduce weighted objectives beyond simple makespan.
Staff Shifts
Nurses, anesthesiologists, and support staff work in shifts, creating time-window constraints on when operations can be performed.
Recovery Room Capacity
Unlike the basic model, recovery rooms can often serve multiple patients simultaneously, introducing parallel machine constraints on select resources.
References
Key literature on job shop scheduling and OR applications