Solving Three-Stage Operating Room Scheduling Problems with Uncertain Surgery Durations

Operating room (OR) scheduling problems are often addressed using deterministic models that assume surgery durations are known in advance. However, such assumptions fail to reflect the uncertainty that often occurs in real surgical environments, especially during the surgery and recovery stages. This study focuses on a robust scheduling problem involving a three-stage surgical process that includes pre-surgery, surgery, and post-surgery stages. The scheduling needs to coordinate multiple resources—pre-operative holding unit (PHU) beds, ORs, and post-anesthesia care unit (PACU) beds—while following a strict no-wait rule to keep patient flow continuous without delays between stages. The main goal is to minimize the makespan and improve schedule robustness when surgery and post-surgery durations are uncertain. To solve this problem, we propose a Genetic Algorithm for Robust Scheduling (GARS), which evaluates solutions using a scenario-based robustness criterion derived from multiple sampled instances. GARS is compared with four other algorithms: a deterministic GA (GAD), a random search (BRS), a greedy randomized insertion and swap heuristic (GRIS), and an improved version of GARS with simulated annealing (GARS_SA). The results from different problem sizes and uncertainty levels show that GARS and GARS_SA consistently perform better than the other algorithms. In large-scale tests with moderate uncertainty (30 surgeries, α = 0.5), GARS achieves an average makespan of 633.85, a standard deviation of 40.81, and a worst-case performance ratio (WPR) of 1.00, while GAD reaches 673.75, 54.21, and 1.11, respectively. GARS can achieve robust performance without using any extra techniques to strengthen the search process. Its structure remains simple and easy to use, making it a practical and effective approach for creating reliable and efficient surgical schedules under uncertainty.