| dc.description.abstract | This thesis proposes two mathematical stochastic optimisation models handling two different aspects of uncertainty in the daily problem of deciding start times for a set of surgeries in a single operating room. The uncertainty related to surgery durations are modelled by scenarios generated using moment-matching on a statistical basis of detailed data on almost 90~000 past surgeries at St. Olavs Hospital.
Both problems have the objective of minimising the expected cost of waiting time, idle time and overtime. The first is based on the hypothesis that, for some surgeries, the uncertainty in duration depends on the start time, a hypothesis that is tested using a two-sample Kolmogorov-Smirnov test of independence. The model formulated to solve this problem is a mixed integer program including decision-dependent uncertainty, something that complicates the problem considerably on a computational level. The second problem includes both stochastic surgery durations and stochastic arrival of emergency patients, a combination that, to the authors' best knowledge, has not yet been covered by existing literature.
The model formulations are tightened by the introduction of several valid inequalities, the most effective of which is a cut strengthening the link between two types of sequencing variables. On average this reduces execution time by roughly 40\%. To further overcome the computational challenges posed by decision-dependent uncertainty, and in order to investigate alternative solution methods, we test the heuristics most commonly used in surgery scheduling literature. These tests conclude that the best performance is by a heuristic sorting surgeries by increasing variance, while the popular Bailey-Welch heuristic shows poor performance.
Based on insights gained from our practical analysis, and with foundation in literature, we propose a decision rule stating that you should sequence the surgeries by ascending variance, and set start times with intervals equal to each surgery's mean duration. We proceed to show that this rule captures large parts of the total potential gain from solving the stochastic models using optimisation. Averaged over our problem instances, the model results signify that the case hospital can reduce waiting time, idle time and overtime by 160, 22, and 16 minutes per day, respectively. The contribution of this thesis is thus both on a practical and a theoretical level. | |
