Stochastic Models for the Operating Room Scheduling Problem under Uncertainty

Surgical procedures are complex tasks requiring a variety of specialized and expensive resources. They are recognized amongst the most crucial activities in hospitals from social, medical and economic points of view. Accordingly, operating room (OR) management has gained significant attention within the past decade. Specifically, efficient planning and scheduling of operating rooms has become a priority for both practitioners and researchers. Planning problems deal with assigning surgical patients to certain days over a given planning horizon (e.g., a week) considering limited resources (e.g., PACU bed). Scheduling problems address the allocation of patients to the OR and the calculation of surgery start times on a daily basis. One of the major problems associated with the development of accurate OR planning and scheduling strategies is the uncertainty inherent to surgical procedures. Among many sources of uncertainty mentioned in the literature, high variability of surgery durations is identified as the biggest challenge towards developing practical OR schedules. Uncertain surgery durations can cause a large deviation from the expected completion time of all surgery cases scheduled for each day. Larger than average surgery durations cause an extended overtime for surgical teams and waiting time for patients. On the other hand, shorter than expected durations result in unnecessary resource idle time and lost revenue. The goal of the proposed research is to address surgery duration uncertainty and make a trade-off between optimizing average performance and reducing variability of the performance measures via developing risk-based models and solution methods. A risk averse solution method using Conditional Value-at-Risk (CVaR) is proposed to reduce variability on overtime and its associated costs in a daily OR scheduling problem. CVaR is a risk measure that is shown to be effective in simultaneously reducing the expected value and the variance of a performance measure. The OR scheduling problem is formulated as a stochastic mixed-integer linear programming model, where a surgery duration follows a known probability distribution function. Numerical results from real-life instances show that our approach not only outperforms the widely used expected value (EV) approach in reducing variability on overtimes, but it also shows acceptable performance in minimizing the expected value of overtimes and idle times. We also show that the proposed method performs well under distributional uncertainty of the random data. As compared to the EV in terms of the total cost, the CVaR reduced the variance, interquartile range and median absolute deviation by 37%, 25% and 24%, respectively, with a slight increase (4%) in the expected value. The proposed method does not explicitly optimize the average performance but focuses on a rather small portion of scenarios. Our next work tries to tackle this limitation using chance-constrained programming. This work proposes a two-stage chance-constrained model to solve the OR scheduling problem under uncertainty. The goal is to minimize the costs associated with OR opening and overtimes and patient waiting times. The risk of OR overtime is controlled using individual chance constraints. A deterministic equivalent formulation of the model is proposed. Numerical experiments on several test problems show that the proposed model provides a better trade-off between minimizing costs and reducing solution variability compared to two existing models in the literature. We used several criteria such as OR utilization, amount of OR overtime, patient waiting time and the ratio of overtime scenarios to compare the three models. We exploit the structure of the model in order to propose a decomposition algorithm that solves large test instances of the OR scheduling problem, that of which is known to be NP-hard. Strong valid inequalities are derived in order to accelerate the convergence speed. It is shown that the proposed algorithm will achieve global optimality. Moreover, the proposed algorithm outperforms a commercial solver and a basic decomposition algorithm by solving instances of up to double size to optimality within one hour. Specifically, this algorithm solves instances with up to 74 surgeries and 20 ORs to optimality. The next chapter aims to develop more powerful solution techniques to solve even larger instances of the stochastic OR scheduling problem. Lower- and upper-bounds are derived for the two-stage model using Lagrangian relaxation and CVaR. An augmented decomposition algorithm is proposed that is able to find high quality initial feasible solutions in reasonable solution times. Numerical experiments show that the proposed bounds enhance the computational efficiency of the decomposition algorithm significantly. The augmented algorithm is able to solve instances with up to 207 surgeries and 40 ORs to optimality within one hour. As the probability threshold for OR overtime increases, the proposed algorithm provides stronger bounds on the optimal objective value.