Surgical Scheduling with Constrained Patient Waiting Times

We consider a surgical case scheduling problem with the objective of minimizing the expected time span of the schedule subject to a prespecified upper bound on the expected waiting time for each patient. The problem is challenging due to its combinatorial and nonlinear nature, and we focus on developing approximate methods to solve the problem. Specifically, we study two approximation methods. In the certainty equivalent method, we approximate the expected time span of the cases by assuming that the waiting time of each surgical case is a deterministic value. In the variance bounding method, we approximate the expected time span based on upper bounds on the variance of the surgical case waiting times. We show that the certainty equivalent method leads to a lower bound on the optimal expected time span, while the variance bounding method leads to an upper bound. Both methods suggest a simple sequencing rule, which is to sort the surgical cases in the ascending order of the surgical duration variability. Based on the upper and lower bounds, we derive a closed‐form, distribution‐free relative error bound for our sequencing rule, and show that it is uniformly bounded with respect to the number of cases. We also conduct a case study based on real‐life data on hernia repair procedures at the Jewish General Hospital in Montréal, to demonstrate our analytical models and their potential benefits for improving surgical scheduling. Finally, we conclude the paper by mentioning a few future research directions.