Dealing with uncertain surgery times in operating room scheduling

Highlights

• A general model for decision support for the operating room scheduling problem, using integer optimization.

• A novel approach to introduce case length uncertainty into the problem formulation.

• Use of chance constraints to control uncertainty, showing how these can be implemented in the integer optimization model.

• Experimental results, using historical instances, show that this approach improves schedule performance significantly.

• The analysis shows the improvement gained if it is possible to add flexibility to physicians' assignment to surgeries.

Abstract

The operating theater is one of the most expensive units in the hospital, representing up to 40% of the total expenses. Because of its importance, the operating room scheduling problem has been addressed from many different perspectives since the early 1960s. One of the main difficulties that has reduced the applicability of the current results is the high variability in surgery duration, making schedule recommendations hard to implement.

In this work, we propose a time-indexed scheduling formulation to solve the operational problem. Our main contribution is that we propose the use of chance constraints related to the surgery duration’s probability distribution for each surgeon to improve the scheduling performance. We show how to implement these chance constraints as linear ones in our time-indexed formulation, enhancing the performance of the resulting schedules significantly.

Through data analysis of real historical instances, we develop specific constraints that improve the schedule, reducing the need for overtime without affecting the utilization significantly. Furthermore, these constraints give the operating room manager the possibility of balancing overtime and utilization through a tuning parameter in our formulation. Finally, through simulations and the use of real instances, we report the performance for four different metrics, showing the importance of using historical data to get the right balance between the utilization and overtime.

Introduction

The operating theater is one of the most expensive units within a hospital, representing up to 40% of the total expenses (Denton, Viapiano, & Vogl, 2007). As a result, there is a vast literature addressing operating room (OR) management at the strategic, tactical, and operational levels (e.g., see Magerlein & Martin, 1978 and references therein). One of the most important trade-offs, usually highlighted when managing ORs, is the one between the cost of overtime when ORs are used after regular hours versus the opportunity cost for under utilization, when there are idle OR hours (Erdogan, Denton, & Fitts, 2010).

Although researchers have addressed several dimensions of this problem, only a few actual implementations have been described in the literature. One of the main reasons identified for the lack of real applications is that the resulting schedules are hard to operationalize by OR managers, in part due to the high variability of surgery duration (Guerriero & Guido, 2011).

Our work has been motivated by the scheduling problem faced by the Instituto de Neurocirugía Dr. Raúl Asenjo, in Santiago, Chile. This hospital is a specialty facility for patients with neurosurgical needs, from around the country. Thus, in contrast of what happens at a typical hospital, there are no competing specialties for the use of OR hours. We remark, however, that if this was not the case, then the master surgery scheduling, when OR block hours are assigned to different specialties, would be an input to consider at the daily scheduling process, and incorporated in the mathematical models when specifying the OR available hours. This study focuses at the operational level where the detailed daily scheduling takes place: date, time, OR, and, in the more general case, physician are assigned to each patient. The current practice for the scheduling process is as follows: on Thursdays, a medical team revises the waiting list and schedules patients for the following week, considering the patients’ waiting times and trying to maximize the use of the scarce OR operating hours. We notice that the majority of patients have already an assigned surgeon to perform the procedure. However, there are simpler surgeries, such as carpal tunnel syndrome, where a physician is assigned according to time availability. The scheduling process is manual and relies heavily on the personal experience of the scheduling team. The latter provides an opportunity not only to optimize the scheduling procedure in terms of performance measures but also to relief professional resources.

The medical center, which is one of the most important for neurosurgeries in the country, has four operating rooms plus one emergency OR, where more than 110 different types of surgeries are performed.The hospital has provided detailed historical data of their four ORs. These ORs are dedicated exclusively to elective surgeries, having a separate OR for emergency ones.

The data shared by the hospital, of all their elective surgical procedures from 2015 and 2016, corroborates what is shown in the literature: for a given diagnostic and procedure, surgeries may vary significantly in their duration (also known as case length). As an example, Fig. 1 shows the duration, in minutes, of the 20% most common procedures at the hospital, indicating that for the same surgery code (i.e., the same type of operation), surgeries can have a wide range of duration. The selected 23 surgeries account for more than 85% of the total procedures done in the Institute, and more than 88% of the time used in the operating rooms. The box plot in Fig. 1 highlights the median for each kind of surgery, with the box covering the upper and lower quartile. The notch in the box represents the confidence interval for the median estimation, whereas the whiskers show the whole range of the data for that specific type of surgery.

Although the high variability indicated in Fig. 1 could be explained by the difference in the performance of the different surgeons, Fig. 2 shows that this result also holds when considering surgery times for each physician separately. In this figure, we showcase the lengths of the operation for all the physicians that performed one specific surgery in the data time-frame: nucleus pulposus hernia. We continue to observe the high variability in surgery times for each physician ID. We remark that the source of this variability could be found on the physicians’ personal features such as experience or training in that specific procedure, as well as patients’ characteristics such as age or comorbidities. It is also important to note that a physician does not have the same performance across different types of surgeries. That is, one physician can be among the fastest for one specific type of procedure, whereas she can be far from that group for a different kind of surgery.

Our contributions

In this work, we present a novel approach on how to incorporate surgery time variability into the OR scheduling problem at the operational level. Our work presents several contributions to address the operating room scheduling problem.

First, we present a time-indexed formulation for the OR scheduling problem. Because of large differences in the duration of similar surgeries between the surgeons, our general model allows the decision-maker to select the surgeon for each procedure. Hence, in the more flexible version of the model, the recommendation given by our model will not only be at what time to schedule the operation for each patient and in which operating room, but also the physician that should perform the surgery.

The main methodological contribution of our work is how we improve the proposed model by including surgery variability. We do this by developing specific chance constraints using historical data to guide our development. These new constraints allow the decision-maker to control the probability of having overtime in each OR in the resulting schedule.

As an additional contribution, we do several experimental studies of our approach. Through simulations, we show the value added by including historical data into the scheduling problem: first by separating the performance of different physicians, and later by adding chance constraints that use this data to control the probability of having overtime in each OR. Our experiments show that our approach significantly improves the performance of the resulting schedules. We also validate our methodology on historical data provided by the hospital, showing that even when the physician cannot be selected (i.e., the surgeon is predetermined for each patient), using these chance constraints can reduce overtime without sacrificing OR utilization as much.

The rest of the paper is organized as follows. First, in Section 2, we present the literature review focused on how researchers have dealt with surgery duration variability. Then, Section 3 presents an initial, deterministic scheduling model, which we further improve in Section 4 to include the variability in surgery duration. In Section 5, we show experimental results, highlighting how the performance of the schedules improve when new data is added, and our methodology is used. Section 6 studies the model adding the flexibility of assigning physicians to patients at the scheduling stage. Finally, Section 7 describes our conclusions and future lines of research.