Column generation approach to operating theater planning with elective and emergency patients.

1. Introduction

A hospital operating theater generally admits two categories of patients: elective patients, who can be planned in advance and emergency patients, who arrive randomly during the day and must be served urgently. One of the major problems facing the operating theater manager is how to allocate the capacity of the Operating Rooms (ORs) among these two competing groups of patients. Emergency surgery demand arises randomly almost every day and must be met on the same day because of the critical condition of emergency patients. Devoting a large amount of the capacity to emergency surgery will increase OR idle times and the waiting list for elective surgery. However, if the capacity reserved for emergency surgeries is insufficient, this may result in excessive overtime usage and cancellation or postponement of already planned elective patients; which can significantly degrade the quality of service, and generate additional costs and a bad image for the hospital.

This paper addresses the problem of elective surgery planning under uncertain demand for emergency surgery. The problem consists in determining a plan that specifies the set of elective patients that would be operated on in each OR in each period over a planning horizon. The surgery plan should minimize costs related to performing elective surgeries and the expected utilization costs of the ORs, i.e., expected overutilization and underutilization costs.

ORs are among the most critical and expensive resources at most hospitals. For this reason, the planning and scheduling of ORs has been widely addressed in the healthcare literature. Belien and Demeulemeester (2007) developed analytical models and solution heuristics for building cyclic master surgery schedules to minimize the expected total bed shortage. Vissers et al. (2005) studied the problem of creating a master surgery schedule while considering multiple resources; they formulated the problem as a mixed-integer program and solved it heuristically. Marcon et al. (2003) proposed a tool to assist the planning negotiation between the different actors of the surgical suite by estimating the risk of non-realization of tentative surgery plans. A two-step approach was proposed by Guinet and Chaabane (2003) and Jebali et al. (2006) for the operating theater scheduling problem. First, elective patients are assigned to ORs. Patients assigned to each OR are then scheduled on a daily basis in order to satisfy material and personnel-related constraints. Integer programming models were developed for the patient assignment problem. Fei et al. (2008) used a branch-and-price algorithm to solve the elective surgery planning while minimizing OR overutilization and underutilization. Hans et al. (2008) considered the problem of assigning elective surgeries and planned capacity slack to OR days. The planned slack aims at minimizing overtime by absorbing the variability in the duration of surgical operations. Various heuristic rules were used to solve this problem. Several other approaches to OR planning have been proposed in the literature (Magerlein and Martin, 1978; Dexter, Macario, Traub, Hopwood, and Lubarsky, 1999; Ozkarahan, 2000).

Most existing approaches for OR planning assume that the OR capacity is devoted to a single class of patients: elective patients. Gerchak et al. (1996) addressed the problem of reservation planning for elective patients when the capacity is used to satisfy elective and emergency surgery demands. The focus of their work is on the characterization of the optimal policy that determines, at the beginning of each day, how many additional requests for elective surgery to assign for that day. Though similar to our problem, their model is mono-period with aggregated capacity and does not specify the intervention date and the OR for each elective case.

This work addresses the planning of elective patients at a hospital operating theater over a planning horizon. The operating theater is composed of several ORs and provides service to elective and emergency patients. Elective patients can be planned in advance with a patient-related cost that depends on the OR and on the date of surgery. A random amount of each OR's capacity is used to serve emergency patients. The planning problem consists in assigning elective patients to ORs with the best trade-off between patient-related costs and the expected utilization costs of the ORs.

The planning problem is first modeled as a stochastic integer program. A column-oriented formulation in which each column represents a possible assignment of elective patients to a particular OR in a particular time period is then derived. The linear relaxation of the latter formulation is then solved via column generation, where the pricing problem, a stochastic knapsack problem, is solved by a dynamic programming method. A feasible plan is derived from the solution of the relaxed problem by a heuristic, and improved by using local optimization heuristics.

This work is an extension of our earlier work (Lamiri et al., 2008) in which a stochastic programming model and a Monte Carlo optimization approach were proposed for elective patient planning under uncertain demand for emergency surgery. In this earlier work, only the total operating theater capacity is taken into account and the assignment of patients to ORs is not considered. As a result, the resulting planning might not be feasible. Furthermore, the Monte Carlo optimization approach relies on mixed-integer programming and hence cannot be used to solve problems of realistic size.

The new contributions of this paper can be summarized as follows: (i) a stochastic model for operating theater planning taking into account the random emergency surgery demand, assignment of patients to ORs, more realistic cost structure of OR capacity utilization; and (ii) an efficient column generation approach able to solve realistic size problems with a very small optimality gap.

The remainder of the paper is organized as follows. Section 2 gives a stochastic integer programming formulation of the planning problem. Section 3 presents the column generation approach, the pricing problem solution method, and the construction and improvement of a feasible plan. Numerical results are presented and discussed in Section 4. Section 5 concludes the paper and discusses possible extensions of this work.

2. Problem statement

This paper considers the planning of elective surgery at a hospital operating theater over a finite horizon of H periods (days). The operating theater is composed of S ORs and provides service to two groups of patients: elective patients, that can be planned in advance; and emergency patients, that must be served on the day of arrival.

At the beginning of the horizon, there are a set of N requests for elective surgery. The planning problem consists in determining the set of elective patients to be operated on in each OR and in each time period over the planning horizon. The starting times and sequence of surgical cases for a given OR can be determined at a later stage on a period-to-period basis (Weiss, 1990; Liu and Liu, 1998; Denton and Gupta, 2003). In the rest of the paper, we call an OR s [member of] {1,...., S} in a given period (day) t [member of] {1,..., H} an "OR-day" (s, t). The following notations are used throughout the paper:

H = planning horizon;

t [member](1,...,H) = time period index;

S = number of ORs;

s[member of](l,...,S) = operating room index;

N = number of elective cases;

i [member of](1,....,N) = elective case index;

[d.sub.i] = time needed to perform elective case i;

[e.sub.i] = earliest period to perform elective case i;

[a.sub.its] = cost of performing elective case i in OR-day (s,t);

[W.sub.ts] = random variable representing the capacity used by emergency cases in OR-day (s, t);

[g.sub.ts] (*) = operating room utilization cost.

In the following, the notations defining the operating theater planning problem and the underlying assumptions are explained and discussed in detail.

2.1. Operating time

Each elective case i has an operating time [d.sub.i], which includes surgery duration, pre-surgery set up time and post-surgery OR cleaning time. Operating times can be efficiently estimated by using historical information and/or surgeons' and operating theater managers' expertise (Shukla et al., 1990; Wright et al., 1996; Dexter, Traub and Qian, 1999).

Existing statistical studies (Zhou and Dexter, 1998; Strum et al., 2000) show that surgery duration is in general log-normally distributed. Uncertainty related to surgery duration may have a significant impact on the quality of a surgery plan. Explicit modeling of random surgery duration for operating theater planning is an important issue but it is beyond the scope of this paper.

Assumption 1: Operating times [d.sub.i] are given constants and multiples of some basic time period [theta] (e.g., [theta]=5 minutes). Furthermore, the operating times are assumed to be independent of the OR-days to which elective cases are assigned.

Remark 1: In practice, the operating time of a surgery may depend on the OR to use, since the pre-surgery set up time varies according to the availability of specialist medical equipment. The column generation approach of this paper applies to the case of OR-dependent operating times. However, due to lack of realistic estimation of operating times for different ORs and the relative minor difference in operating times for different ORs in general, we limit ourselves to OR-independent operating times.

2.2. Patient assignment costs