Elective Surgery Sequencing and Scheduling under Uncertainty

We consider a surgery sequencing and scheduling problem with uncertain surgical durations in the context of an operating theatre. From real data collected from a hospital, we observe the common practice, namely 'to follow', in which surgeries are conducted sequentially and immediately, one after another, according to a specific schedule. Based on this practice, we propose a mathematical framework to balance the delay risk and the idle risk with a Punctuality Index, which takes into account both the probability and intensity of delay and idle time. We develop a computationally efficient solution procedure based on Benders Decomposition, offering exact solutions for the problem. When the sequence is given, the scheduling problem is solvable in polynomial time. The framework can also accommodate a robust setting when the underlying probability distribution is not fully available. For practical use, we propose two effective heuristics for sequencing decisions by approximating the model. One sorts surgeries in ascending order of the variance of the surgical durations. The second one is based on the forward and backward deviations, which capture the right and left tail of the uncertain surgical durations, respectively. Finally, we carry out numerical studies with real data to demonstrate the benefits of the model and the heuristics