Operating room scheduling with sequence - dependent & stochastic surgery durations

Abstract

Operating rooms are the most costly part of hospitals. In order to increase their efficiencies, hospitals should first increase the efficiency of their operating rooms. In this thesis, we consider the next-day operating room scheduling problem both for single op erating room and multiple operating rooms. It is assumed that surgeries have uncertain durations and distributions of surgery durations are dependent on the sequence of the surgeries within an operating room. In this problem, sequence-dependency comes from the location of surgeries within an operating room instead of the relationship between two successive surgeries. It is aimed to sequence and schedule sequence-dependent surgeries by minimizing the weighted sum of expected waiting time of patients, idle time of operating rooms, and overtime of the hospital staff. In order to find solutions to the problem, Sample Average Approximation(SAA) method is used. Then, the effect of different parameters on penalty of ignoring sequence-dependent surgery durations is analyzed. Furthermore, L-Shaped method and five different heuristics are introduced to decrease the computation time further. We test the performance of these heuris tics by comparing them with the solutions found by using SAA. According to results, Modified Myopic Heuristic performs better than other heuristics for single operating room problem. For multiple operating rooms, giving more weight to overtime increases the cost occurred by ignoring the sequence-dependent surgeries. It is also observed that SVF Heuristic is an important way to decrease the computation time of complex scheduling problems.