Surgery sequencing to minimize the expected maximum waiting time of emergent patients

This paper investigates the problem of surgery sequencing under uncertain surgery durations, with the objective of minimizing the expected maximum waiting time that emergent patients may endure before an operating room becomes available. Given the sets of surgeries assigned to each operating room as well as the distribution of each surgery’s duration, we aim to find the room sequences that minimize the expected largest interval between consecutive completion times. To solve the resulting stochastic optimization problem called the Stochastic Break-In Moment problem (SBIM), we implement a new MILP based on Sample Average Approximation. An algorithm that more intelligently segments the search further improves performance. We also create a variance-based heuristic and adapt a variety of local search methods to the SBIM case. Numerical experiments based on a surgery scheduling benchmark set show that stochastic solution methods outperform their deterministic counterparts, and highlight the value of the stochastic solution.