Operating room scheduling with uncertain surgery durations

In this thesis, we consider the day-to-day scheduling problem of a single hospital operating room (OR). We assume that the number and the characteristics of the surgeries to be scheduled for the next day are known in advance, but they have uncertain durations with di erent means and variances. Our aim is to determine the sequence and sched-uled starting times of the surgeries in such a way that a cost function, which is de ned as the weighted sum of expected patient waiting times, idle times of the OR, and the end-of-day overtime, is minimized. For the sequencing part of the problem, based on ana-lytical observations of smaller scale problems, we propose ordering surgeries with respect to stochastically increasing durations (roughly corresponding to a smallest variance rst sequencing rule). For the determination of the scheduled starting times, we consider three heuristics, each motivated by analytical solutions of approximate models: an expected value based heuristic, a heuristic based on decomposition of surgeries (Myopic heuris-tic), and a heuristic based on the assumption that the OR is never kept idle (Veteran's heuristic). We test these heuristics by comparing them with the optimal solution found by exhaustive enumeration. Our results reveal that the sequencing rule proposed coupled with the Veteran's heuristic yield the most satisfactory outcome.