Optimization of Surgery Scheduling in Multiple Operating Rooms with Post Anesthesia Care Unit Capacity Constraints

Abstract Surgery schedules are subject to disruptions due to duration uncertainty in surgical activities, patient punctuality, surgery cancellation and surgical emergencies. Unavailable recovery resources, such as post-anesthesia care unit (PACU) beds may also cause deviations from the surgical schedule. Such disruptions may result in inefficient utilization of medical resources, suboptimal patient care and patient and staff dissatisfaction. To alleviate these adverse effects, we study three open challenges in the field of surgery scheduling. The case we study is in a surgical suite with multiple operating rooms (ORs) and a shared PACU. The overall objective is to minimize the expected cost incurred from patient waiting time, OR idle time, OR blocking time, OR overtime and PACU overtime.In the first part of this work, we study surgery scheduling with PACU capacity constraints. With surgery sequences predetermined in each OR, a discrete event dynamic system (DEDS) and a DEDS-based stochastic optimization model are devised for the problem. A sample-gradient-based algorithm is proposed for the sample average approximation of our formulation. Numerical experiments suggest that the proposed method identifies near-optimal solutions and outperforms previous methods. It is also shown that considerable cost savings (11.8% on average) are possible in hospitals where PACU beds are a constraint.In the second part, we propose a two-stage solution method for stochastic surgery sequencing and scheduling with PACU capacity constraints. In the first stage, we propose a mixed-integer programming model with a surrogate objective that is much easier to solve than the original problem. The Lagrangian relaxation of the surrogate model can be decomposed by patients into network-structured subproblems which can be efficiently solved by dynamic programming. The first-stage model is solved by the subgradient method to determine the surgery sequence in each OR. Given the surgery sequence, scheduled start times are determined in the second stage using the sample-gradient descent algorithm. Our solution method outperforms benchmark methods that are proposed in the literature by 11% to 43% in numerical experiments. Our sequencing method contributes 45% to 80% of the overall improvement. We also illustrate the improvement on PACU utilization after using our scheduling strategy. In the third part, we propose a proactive and reactive surgery scheduling method for surgery scheduling under surgical disruptions. A surgical schedule considering possible disruptions is constructed prior to the day of surgery, and is then adjusted dynamically in response to disruptions on the day of surgery. The proposed method is based on stochastic optimization and a sample-gradient descent algorithm, which is the first non-metaheuristic approach proposed for this problem. In addition, the "to-follow" scheduling policy, which is widely used in practice, is considered in this study. This differs from previous surgical scheduling studies which assume no surgery can start before its scheduled start time. The proposed method finds near-optimal solutions and outperforms the scheduling method commonly used in practice.