European Journal of Operational Research 185 (2008) 1026–1037

www.elsevier.com/locate/ejor

A stochastic model for operating room planning

with elective and emergency demand for surgery
Mehdi Lamiri *, Xiaolan Xie, Alexandre Dolgui, Frédéric Grimaud
Ecole Nationale Supérieure des Mines de Saint Etienne, 158, Cours Fauriel, 42023 Saint Etienne cedex 2, France

Received 1 April 2005; accepted 1 February 2006

Available online 13 October 2006

Abstract

This paper describes a stochastic model for Operating Room (OR) planning with two types of demand for surgery: elec-
tive surgery and emergency surgery. Elective cases can be planned ahead and have a patient-related cost depending on the
surgery date. Emergency cases arrive randomly and have to be performed on the day of arrival. The planning problem
consists in assigning elective cases to different periods over a planning horizon in order to minimize the sum of elective
patient related costs and overtime costs of operating rooms. A new stochastic mathematical programming model is first
proposed. We then propose a Monte Carlo optimization method combining Monte Carlo simulation and Mixed Integer
Programming. The solution of this method is proved to converge to a real optimum as the computation budget increases.
Numerical results show that important gains can be realized by using a stochastic OR planning model.
 2006 Elsevier B.V. All rights reserved.

Keywords: Stochastic programming; Operating rooms; Surgery planning; Emergency patients; Monte Carlo optimisation

1. Introduction

Facing ever increasing health care demand, limited government support and increasing competition, hos-
pitals are more and more aware of the need to use their resources as efficiently as possible. Operating Rooms
(ORs) are among the most critical resources that generate highest costs for a hospital. For these reasons, plan-
ning and scheduling OR activities have become major priorities for hospitals.
In this paper, we focus on the planning of elective surgery when the OR capacity is shared between two
competing patient classes: emergency patients and elective patients. These two patients groups have different
characteristics. Emergency cases arrive randomly and must be served immediately on the same day. Electives
cases can be delayed and planned for future dates.
The planning of surgical activities in ORs has been extensively addressed over the past three decades. Mag-
erlein and Martin (1978) presented a review of surgical suite scheduling and discussed procedures for planning
patients in advance of their surgical dates and techniques for the assignment of patients to operating rooms at

*
Corresponding author. Tel.: +33 (0)4 77 42 66 45; fax: +33 (0)4 77 42 66 66.
E-mail addresses: Lamiri@emse.fr (M. Lamiri), Xie@emse.fr (X. Xie), Dolgui@emse.fr (A. Dolgui), Grimaud@emse.fr (F. Grimaud).

0377-2217/$ - see front matter  2006 Elsevier B.V. All rights reserved.
doi:10.1016/j.ejor.2006.02.057
 M. Lamiri et al. / European Journal of Operational Research 185 (2008) 1026–1037 1027

specific times of day. Dexter et al. (1999a,b) used on-line and off-line bin-packing techniques to plan elective
cases and evaluated their performances using simulation. Marcon et al. (2003) presented a tool to assist in the
planning negotiation between the different participants in the surgical suite. Linear programming models were
proposed for the planning and the scheduling of OR activities (Jebali et al., 2005; Guinet and Chaabane,
2003). A column generation approach was proposed in Fei et al. (2004) to plan elective surgeries in identical
ORs. Ozkarahan (2000) proposed a goal-programming model to allocate surgeries to ORs.
Though a substantial body of work on OR planning has appeared in the literature, most of these papers
assume that the total OR capacity is devoted to a single patient class. One exception is the work of Gerchak
et al. (1996), which addressed the problem of reservation planning for elective patients when the capacity is
shared between elective and emergency surgery. The focus of their work is on the characterization of the opti-
mal policy that determines at the start 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 and does not specify the intervention
date for each elective case.
The goal of this paper is to develop an optimization model and algorithms for elective surgery planning in ORs
with uncertain demand for emergency surgery. The problem consists of determining a plan that specifies the set of
elective cases that would be performed in each period over a planning horizon (one or two weeks). The surgery
plan should minimize costs related to the over-utilization of ORs and costs related to performing elective surgery.
Although numerous studies show the extreme importance of taking into account uncertainties such as emer-
gency demand in OR planning, existing OR planning approaches all use deterministic optimization models and
assume that the hospital use dedicated ORs to serve emergency patients, or devotes a fixed portion of OR
capacity to perform only the emergency surgeries. The main contributions of this paper include (i) an original
stochastic OR planning model that explicitly takes into account both elective and emergency patients, (ii) a
Monte Carlo optimization method for effective OR planning with explicit consideration of uncertainties related
to emergency demand. Numerical experiments further show importance of explicit modelling of uncertainties.
Compared with a deterministic OR planning model that only considers the average emergency demand but
neglects its uncertainty, our stochastic OR planning method yields about 4% reduction of overall cost.
The remainder of this paper is organized as follows: Section 2 presents the planning model, proposes a sto-
chastic programming model of the problem and investigates its complexity. Section 3 proposes a Monte Carlo
optimization method combining the Monte Carlo simulation and Mixed Integer Programming. Numerical
results of the optimization method are presented in Section 4. Section 5 concludes the paper and discusses pos-
sible extensions of this work.

2. Problem setting

2.1. A stochastic programming model

This work concerns the planning of elective surgery at a hospital surgical suite over a planning horizon H.
The surgical suite capacity is shared among two competing patient classes: elective cases, that are to be
planned in advance; and emergency cases, that must be served on the day of arrival.
At the beginning of the horizon, there are N requests for elective surgery. Each elective case i (i = 1..N) has
the following characteristics:
• pi, the time needed for performing elective case i , which we call operating time, and includes not only the
surgery time but also set-up time, cleaning, etc.;
• Bi, the release period.
Accurate estimates of operating times are necessary to have efficient OR planning. Shukla et al. (1990) recom-
mend using historical information to estimate the operating time of elective cases. Zhou and Dexter (1998)
advocate the use of log–normal distributions to approximate surgery durations. Surgeons and OR managers
can also provide good estimations of operating times. In this work, we assume that operating times of all elec-
tive cases are known and deterministic.
The release date Bi (i = 1..N) is the earliest perioid at which elective case i can be performed, it may repre-
sent hospitalization date, date of medical test delivery, etc.
1028 M. Lamiri et al. / European Journal of Operational Research 185 (2008) 1026–1037

For each elective case i we define a set of costs CEit (t = Bi, . . . , H, H + 1). The CEit represents the cost of
performing elective case i in period t. The period H + 1 is added to the planning horizon for cases that are
rejected from the current planning horizon and that will be considered in the next horizon. The cost structure
proposed in this paper is fairly general. It can represent hospitalization costs (Jebali et al., 2005; Guinet and
Chaabane, 2003), penalties for waiting to get on schedule (Gerchak et al., 1996), optimal surgery date,
patients’ or surgeons’ preferences, and eventual deadlines. For example, if case i must be performed before
period Li, this constraint can be taken in account by choosing large costs CEit for t > Li.
At the planning level, we are interested in determining a plan that specifies the set of elective cases to be per-
formed in each period over the planning horizon. The assignment to a specific OR and the starting time of each
case can be made at a later stage on a period-to-period basis (Weiss, 1990; Denton and Gupta, 2003). We
assumed that ORs are identically equipped, each surgical case can be assigned to any OR, and only the total
available capacity of all ORs is taken into account. However, the planning model and the optimization method
can be easily extended to plan different types of OR and to take into account OR assignment of surgical cases.
Let Tt be the total available regular OR capacity in period t. If planned elective cases and emergency cases
exceed this regular capacity, overtime costs are incurred. Let COt be the cost per unit of overtime in period t.
While under-utilization costs are not considered in this paper, the results can be easily extended to take into
account both costs; this extension is presented in the next section.
Emergency cases arrive randomly and must be served immediately on the day of their arrival. Equivalently,
emergency cases arriving in a given time period are performed in the same period whatever the available
capacity. Let Wt be the capacity, i.e., total OR time, needed for emergency cases arriving in period t. It is
assumed to be a random variable. Let fW t ðxÞ, be the density function of Wt.

2.1.1. Notation

H planning horizon
t = 1, 2, . . . , H time period index
N number of elective cases
i = 1, . . . , N elective case index
pi time needed for performing elective case i which is assumed to be a given constant
Bi earliest period for performing case i
CEit cost of performing elective case i in period t for t = Bi, Bi+1, . . . , BH+1
Tt total available regular capacity of all ORs in period t
COt cost per unit of overtime in period t
Wt capacity needed for emergency cases of period t
fW t ðxÞ the density function of Wt.

2.1.2. Decision variables

Xit 2 {0 ,1} with Xit = 1 if elective case i is performed in period t and 0 otherwise with the obvious conven-
tion that Xi,H+1 = 1 implies that elective case i is rejected in the current planning horizon.

2.1.3. Mathematical model

N X
X H þ1 X
H
ðPÞ J  ¼ Minimize J ðX Þ ¼ CEit X it þ COt Ot ð1Þ
i¼1 t¼Bi t¼1
" !þ #
X
N
Subject to: Ot ¼ EW t Wtþ pi X it  T t ; 8t ¼ 1; . . . ; H ; ð2Þ
i¼1
H þ1
X
X it ¼ 1; 8i ¼ 1; . . . ; N ; ð3Þ
t¼Bi

X it ¼ f0; 1g; 8i ¼ 1; . . . ; N ; 8t ¼ 1; . . . ; H þ 1; ð4Þ

+
where (x) = max{0, x}.
 M. Lamiri et al. / European Journal of Operational Research 185 (2008) 1026–1037 1029

The objective function (1) minimizes the expected overtime costs as well as elective cases related costs (wait-
ing time costs, hospitalization costs, etc.). Constraints (2) estimate the expected overtime Ot in each period.
Constraints (3) ensure that each elective case is assigned once and only once. Constraints (4) are the integrity
constraints.
Remark. As we have mentioned in the previous section, our planning model can easily be extended to take
into account both overtime costs and under-utilization costs. Let CUt be the cost per unit of under-utilization
in period t. To take into account both over-utilization and under-utilization costs, COtOt in the objective
function (1) is replaced by CORt, the OR utilization cost in period t, and we replace constraints (2) by the
following:
" !þ ! #
XN X
N
CORt ¼ EW t COt W t þ pi X it  T t þ CUt W t þ pi X it  T t ; 8t ¼ 1; ::; H ;
i¼1 i¼1

where (x) = max{0, x}. The solution method proposed in this paper could be easily adapted to take into
account this new cost structure.
The elective case planning model (1)–(4) is a stochastic combinatorial problem and its NP-hardness is estab-
lished by the following theorems, proved in Appendix 1.
Theorem 1. The stochastic planning problem is strongly NP-hard.

Theorem 2. The two-period stochastic planning problem, i.e., H = 2 is NP-hard.

To sum up, the stochastic planning problem is strongly NP-hard, and the NP-hardness remains true even
for the two-period problem.

2.2. Plan evaluation

This subsection addresses the evaluation of a given plan X, i.e., the computation of J(X). The computation
of J(X) can be carried outPanalytically or with simulation. Let TPt be the total planned time in period t for
elective cases, i.e., TP t ¼ Ni¼1 pi X it , and RTt = Tt  TPt the remaining regular capacity. To compute J(X),
we can use either of the following methods.
The first method is an analytical method and determines J(X) exactly. For each period t, the expected over-
time Ot is determined exactly based on the distribution of Wt with the following analytical expression:
Z 1
þ
Ot ¼ EW t ½ðW t  RTt Þ  ¼ ðw  RTt ÞfW t ðwÞ dw:
RTt

J(X) is computed using the expression (1) by replacing the Ots by their expectations.
Monte Carlo simulation is the second alternative that we use to compute the total cost J(X). This method is
implemented with the following algorithm.

Monte Carlo simulation algorithm for plan evaluation:

Step 1. Randomly generate
P L samples of emergency capacity requirement for period t: Wt1, Wt2, . . . , WtL.
L þ
b tL ¼ l¼1 ðW tl RTt Þ .
Step 2. Compute O L
b tL .
Step 3. Compute J(X) using (1) with Ot replaced by O

b tL converges with probability 1 to Ot as L increases.

Remark. By the law of large numbers, O

3. Monte Carlo simulation and mixed integer programming

In this section we present the Monte Carlo optimization method. The basic idea of this method is (i) to
generate K samples of emergency capacity requirement for each period, (ii) to estimate costs of plans similarly
1030 M. Lamiri et al. / European Journal of Operational Research 185 (2008) 1026–1037

as in Section 2.2 and (iii) to determine the plan having the minimum estimated cost. Thanks to the structure of
the problem, the determination of the optimal plan does not require explicit estimation of all plan costs.
Given emergency requirement samples, the related planning problem becomes the following mixed integer
program (P 0 ):
X H þ1
N X X
H
ðP0 Þ J W ;K ¼ Minimize J W ;K ðX Þ ¼ CEit X it þ COt Ot ð10 Þ
i¼1 t¼Bi t¼1

X
N
Subject to: Otk P W tk þ pi X it  T t ; 8t ¼ 1; ::; H ; 8k ¼ 1; . . . ; K; ð20 Þ
i¼1
PK
k¼1 Otk
Ot ¼ ; 8t ¼ 1; ::; H ; ð30 Þ
K
H þ1
X
X it ¼ 1; 8i ¼ 1; . . . ; N ; ð40 Þ
t¼Bi

ðBinary variablesÞ X it ¼ f0; 1g; 8i ¼ 1; . . . ; N ; 8t ¼ 1; . . . ; H þ 1; ð50 Þ

ðReal variablesÞ Otk P 0; 8t ¼ 1; ::; H ; 8k ¼ 1; . . . ; K; ð60 Þ

where Wt1, Wt2, . . . , Wtk are independent random samples of Wt.

The objective function (1 0 ) minimizes the sum of patient related costs and overtime costs using K samples of
Wt ("t = 1, . . . , H). Constraints (2 0 ) define the overtimes Otk related to each sample or scenario Wtk in each
period. Constraints (3 0 ) estimate the required overtime Ot in each period. Constraints (4 0 ) ensure that each
elective case is assigned exactly once. Constraints (5 0 ) and (6 0 ) are variables’ type related constraints.
P
Remark. By optimization, for any optimal solution of problem (P 0 ), Otk ¼ ðW tk þ Ni¼1 pi X it  T t Þþ and
Ot ¼ O b tK where O b tK was defined in Section 2.2. The variable Ot is exactly the overtime O b tK estimated by the
Monte Carlo simulation method of the previous section. Further, variables Ot can be easily removed from the
formulation by replacing it directly into criterion (1 0 ).
The Monte Carlo optimization method can be summarized as follows.

The Monte Carlo optimization algorithm:

Step 1. For each time period t generate K samples of Wt:Wt1,Wt2, . . . , WtK.
Step 2. Solve the mixed integer program (P 0 ) and let X W ;K be the resulting optimal solution.
Step 3. Evaluate the exact cost of the optimal solution J ðX W ;K Þ, using one of the methods presented in Section
2.2.

Note that JW,K(X) and X W ;K are both functions of K and W, i.e., the number of samples and the random
sequence of emergency capacity requirement. For simplicity, we will omit the W index in the rest of this paper,
and denote JW,K(X) (respectively X W ;K ) by JK(X) (respectively X K ).
Theorem 3. With probability 1, as K tends to infinity, J K ðX K Þ converges to J(X*) and the optimal solution X K of
problem (P 0 ) converges to an optimal solution X* of problem (P).

Proof. See Appendix 2. h

4. Computational experiments

This section presents numerical results of the Monte Carlo optimization method. For each K, the related
linear programming problem (P 0 ) was solved using the commercial software ‘‘ILOG CPLEX’’ version 8.0.
The different experiments were carried out on a PC with a 3.0 GHz Pentium IV processor.
 M. Lamiri et al. / European Journal of Operational Research 185 (2008) 1026–1037 1031

The performance of our optimization method was examined by solving a given problem for various values
of K i.e., number of samples. The different values of K are [2, 5, 10, 20, 50, 100, 200, 500, 700, 1000]. For each
K, we performed seven independent runs of the optimization method to provide seven Monte Carlo optimum
solutions X K . The ‘‘exact’’ cost J ðX K Þ of each resulting optimal solution X K was estimated using the ‘‘Monte
Carlo simulation algorithm’’, presented in Section 2.2, with a large number of samples (106 samples), i.e.,
J ðX K Þ ’ J L ðX K Þ with L = 106.

4.1. The test problem

The number of periods H was equal to 5 (one week). The regular OR capacities Tt (t = 1..H) were equal to
16 hours. Assuming that the regular capacity of an OR is 8 hours, this is equivalent to having two available
ORs. The overtime cost is 500 €/h. The daily capacity needed for emergency cases Wt (t = 1..H) is assumed to
be exponentially distributed with a mean of 3 hour.
The durations of elective surgery pi are randomly and uniformly generated from interval [0.5 hour, 3 hours].
For each case i we randomly selected its release period Bi from the set {1. . .H}. To take into account cases
with Bi = 1 that were postponed from the previous plan, we introduced a new variable B0i , the effective earliest
period of case i (or effective release period). B0i can take negative values. The earliest dates Bi were generated in
two steps as follows. First, we generated for each case i the effective earliest date B0i . The B0i s are integer num-
bers randomly selected from the set {2, . . . , 5}. Then, cases with zero or negative B0i will have Bi equal to 1,
while the others will have Bi equal to B0i (Bi = 1 if B0i < 1; Bi ¼ B0i otherwise).
The CEit are assumed to be increasing in t for every i:
CEit ¼ ðt  B0i Þ  c for t ¼ Bi . . . BH þ1 :

The constant c can be interpreted as a penalty per day of waiting to get on schedule, or as a hospitalization
cost per day if patient i was hospitalized in period B0i . The value of c is set equal to 100 €.
The number of elective cases was determined such that the OR workload was 100% of the regular capacity
of the entire planning horizon.

4.2. Computational results

This subsection presents the computational results from a test problem of 44 elective cases generated as
explained above. For each value of K, the resulting optimal solutions of seven independent runs of the Monte
Carlo optimization algorithm lead to seven Monte Carlo optima X K . The ‘‘exact’’ criterion values J ðX K Þ of
these Monte Carlo optimum solutions were evaluated with extremely long Monte Carlo simulations of 106
samples. For each K, we further derived: the minimal ‘‘exact’’ optimal cost, the average ‘‘exact’’ optimal cost,
the maximal ‘‘exact’’ optimal cost and the standard deviation. The computational results are presented
in Table 1. The detailed results of the Monte Carlo optimization problem (P 0 ) obtained with CPLEX are

Table 1
Exact optimal cost of Monte Carlo optimal solutions for seven independent runs
Number of samples Minimal optimal cost (€) Average optimal cost (€) Maximal optimal cost (€) Standard deviation
2 8203.49 8861.27 9542.76 476.07
5 7925.29 8154.68 8451.78 204.20
10 7921.76 8091.69 8346.12 146.48
20 7943.49 7986.52 8067.53 49.28
50 7888.69 7925.22 7972.52 27.88
100 7885.24 7891.41 7903.17 5.63
200 7883.87 7913.75 7952.46 26.92
500 7882.26 7890.93 7903.93 8.47
700 7885.83 7892.38 7915.87 10.46
1000 7883.10 7888.91 7904.24 7.27
1032 M. Lamiri et al. / European Journal of Operational Research 185 (2008) 1026–1037

Table 2
Computational results of the Monte Carlo optimization problem (P 0 ) with CPLEX
Number of Estimated costs (€) Computation time (seconds)
samples
Minimal Average Maximal Standard deviation Minimum Average Maximum
‘‘estimated’’ ‘‘estimated’’ ‘‘estimated’’ of ‘‘estimated’’
optimal cost optimal cost optimal cost optimal costs
2 6133.83 7145.68 8827.25 1031.33 21.00 3012.86 8956.00
5 6002.66 6897.07 7988.60 661.68 0.00 12.57 47.00
10 6005.55 7190.72 7870.92 613.48 1.00 68.57 342.00
20 7569.42 7797.23 8082.37 211.14 0.00 3.43 16.00
50 7468.89 7953.54 8770.72 446.11 0.00 2.29 10.00
100 7745.82 7943.03 8422.59 235.27 0.00 1.14 3.00
200 7697.00 7879.34 8120.84 161.70 0.00 10.57 34.00
500 7772.26 7909.08 8040.48 89.10 10.00 50.00 160.00
700 7739.33 7829.44 7963.80 79.26 38.00 97.57 194.00
1000 7829.51 7865.02 7901.29 26.09 36.00 176.86 593.00

in Table 2. The results include, for each value of K, the minimum, the average, the maximum, the standard
deviation of ‘‘estimated’’ optimal costs ðJ K ðX K ÞÞ of problem (P 0 ) and the computation time.
Two solutions are used to assess the quality of Monte Carlo optimal solutions and the benefit of stochastic
modelling. We consider first the deterministic version of the problem with Wt replaced by its expectation in
problem (P), i.e., with Wt = E[Wt] = 3 hours. This deterministic problem corresponds to the strategy of reserv-
ing a fixed amount of OR capacity for the exclusive use of emergency surgery and is a linear programming
problem. Let XDet be the resulting solution. The ‘‘exact’’ cost J(XDet) of the deterministic solution is evaluated
as €8213.
The second solution is the so-called default solution which plans elective cases for their earliest dates
(X iBi ¼ 1; 8i ¼ 1; . . . ; N ). It incurs a cost of €17,960 which implies that the default solution is very bad.
Comparing solutions of Monte Carlo optimization and the deterministic solution allows us to precisely
quantify the benefit of our stochastic Operating Rooms planning model and the explicit modelling of
randomness.
From the results presented in Table 1, the solutions provided by the Monte Carlo optimization method are
better than those of the deterministic method, even for small values of K (K = 20). Further, the proposed
method achieves a cost reduction of 4% with K = 1000.
To better illustrate the convergence of the Monte Carlo optimization method, Fig. 1 presents the minimal,
the average and the maximal ‘‘exact’’ costs of optimal solutions for each value of K. The results show that the
proposed method achieves a better performance than the deterministic one, for K greater than 20. Further, it is
also clear that the curves converge when the number K of samples is greater than 200, which confirms the con-
vergence property of Theorem 3.
Fig. 1 also shows that the Monte Carlo optimization method is fairly robust if a reasonable number of sam-
ples is used, for example with K > 20.
Let us now compare the convergence rate of the estimated cost and the exact cost of the Monte Carlo opti-
mal solution. To this purpose, we compare the standard deviations of ‘‘exact’’ and ‘‘estimated’’ optimal costs.
The results from Tables 1 and 2 show that both quantities decrease with increasing K, which confirm that the
Monte Carlo optimal solution converges to an optimal solution of problem (P). Standard deviations of the
‘‘estimated’’ optimal costs are always greater than those of the ‘‘exact’’ optimal costs. This can be explained
by the small number of samples (K) used to estimate the cost of the optimal solution J K ðX K Þ, the slow con-
vergence rate of the estimated cost function JK(X) and the quick exponential convergence rate of the Monte
Carlo optimal solution to the real optimal solution.
We now consider the evolution of the computation time with respect to K. Table 2 gives the minimum, the
average value and the maximum of the computation time for solving the Monte Carlo optimization problem
(P 0 ). Surprisingly, the computation time is very large and has large variation for small K; it is small for K
between 20 and 100. For K greater than 100 the computation time increases with K.
 M. Lamiri et al. / European Journal of Operational Research 185 (2008) 1026–1037 1033

9400

9200

9000

8800
Costs

8600

8400

8200

8000

7800
2 5 10 20 50 100 200 500 700 1000
Number of samples (K)

Cost of the deterministic solution Average optimal cost

Minimal optimal cost Maximal optimal cost

Fig. 1. Evolution of costs.

We have also tested the proposed solution method with other problem configurations. Computational
results confirm that our optimization method provides solutions that converge to optimal solutions of the
problems, as K increases, and considerable cost reductions can be achieved using the stochastic optimization
model.

5. Conclusion and discussion

In this paper we proposed a stochastic model for OR planning with two classes of patients: elective patients
and emergency patients. Elective cases can be planned in advance with a patient related cost depending on the
surgery date. Emergency cases arrive randomly and have to be performed on the day of arrival. The planning
problem consists of assigning elective cases to different periods over a planning horizon in order to minimize
the sum of elective patient related costs and overtime costs of operating rooms. The elective cases planning
problem has been formulated as a stochastic mathematical program. A solution method combining the Monte
Carlo simulation with Mixed Integer Programming has been proposed. We have successfully proved and
tested the performance of the solution method.
The performance of the Monte Carlo optimization method was tested by solving random instances of a
surgery planning problem. Experimental results show that costs can be significantly reduced by using a sto-
chastic model where uncertainty related to emergency surgery is explicitly considered. We are presently testing
the model with real hospital data and expect to report results in the near future.
To solve the problem of planning elective cases, we can also use a local search method. This solution
method solves the problem in two steps. First, a feasible plan is determined by solving a deterministic pro-
gram, which is obtained from the stochastic program by replacing the random variables (capacities needed
for emergency cases) by their expected values. Second, starting from the feasible plan, we try to iteratively
improve the plan by searching through its neighbourhood. The neighbourhood structure can be defined in sev-
eral ways. For example, we can use a neighbourhood structure by exchanging the intervention dates, modify-
ing the intervention date of an elective case, etc. At this step, other methods such as simulated annealing,
taboo search and genetic algorithms can be used. Further work will include the testing of these methods with
the elective cases planning problem.
The planning model proposed in this work is useful for hospitals using a ‘‘blocked’’ advance scheduling
system, which reserve blocks of OR time to surgical specialties. Each specialty serving elective and emergency
surgery demand can use the proposed model for the planning of electives cases. Costs related to elective
1034 M. Lamiri et al. / European Journal of Operational Research 185 (2008) 1026–1037

patients may represent, for example, hospitalization costs which increase with delays, and thus the model for-
mulates tradeoffs between overtime costs and delay costs. However, elective patients’ costs can represent sev-
eral other characteristics such as surgeons’ availabilities, patients’ preferences, deadlines, etc.
Various issues need to be further addressed for real-life application of our approach. The first issue is the
setting of costs related to elective patients in order to represent simultaneously hospitalization costs, surgeons’
preferences, and several other characteristics. Other issues include the improvement of the efficiency of the
optimization method for solving large-scale problems by taking into account the properties of the optimal
solutions, and the extension of the model. Another important issue is the sensitivity with respect to data such
as operating times, earliest dates, costs, and distribution of emergency capacity requirement that is often
neglected in the OR planning literature.
This work should be considered as a first step toward a project of robust OR planning. Further work is
needed to build more comprehensive OR planning models taking into account all relevant organizational
and technical constraints and with realistic modelling of various uncertainties. The stochastic model can be
extended in several ways to take into account various characteristics such as (i) constraints on overtime capac-
ity, (ii) assignment of patient to ORs, (iii) different types of OR, (iv) other criteria such as probability of can-
celling planned cases or emergency cases due to limited overtime capacity.

Appendix 1. Problem complexity and proofs

Proof of Theorem 1. The NP-hardness of problem (P) is proved using the 3-Partition decision problem. The 3-
Partition problem, known to be strongly NP-hard, Pcan be defined as follows (Garey and Johnson, 1979):
Given a set of 3z integers A = {ai}16i63z such that 3z i¼1 ai ¼ zB and ai > B/4, where z and B are
P integers, the
question is whether there exists a partition of the set A into z triplets A1, . . . , Az such that i2At ai ¼ B for
1 6 t 6 z. A positive answer to this question implies that the 3-Partition problem has a solution.
In order to prove the NP-hardness of the stochastic planning problem, we define a polynomial
transformation of the 3-Partition problem to the following decision problem: Is there a feasible plan X* for the
planning problem such that J(X*) = 0?
To each instance of the 3-Partition Problem, we associate the following instance (P1) of the planning
problem. The planning horizon H is set at value z, and the number of elective cases N is equal to jAj. For each
period t, the total available regular capacity, the capacity needed for emergency cases and the cost per unit of
overtime are given as follows:
T t ¼ B; W t ¼ 0 and COt ¼ 1; 8t 2 f1; . . . ; H g:
The cost structure of each elective case i (i = 1, . . . , jAj) is the following one:
CEit ¼ 0; 8t 2 f1; . . . ; H g and CEiðH þ1Þ ¼ 1:
The release period and the time needed for performing elective case i are respectively equal to Bi = 1 and
pi = ai, "i for i = 1, . . . , jAj.
We show that, for the planning problem (P1), a plan X* such that J(X*) = 0 exists if and only if the related
3-Partition problem has a solution.
P
Sufficiency: Assume that the 3-Partition problem has a solution A = [ 16t6zAt and i2At ai ¼ B for
1 6 t 6 z. Consider the following plan X *: cases in subset A are planned for period t, "t 2 {1, . . . z}. Since
P t
*
i2At ai ¼ Bð8t 2 f1; . . . zgÞ, it is obvious that the total cost of the plan is TC(X ) = 0. So we have a feasible
*
plan X which satisfies the constraint J(X ) = 0. *

Necessity: Assume that a feasible plan X* such that J(X*) = 0 exists. Let At the set of cases planned for
period t ("t 2 {1, . . . z}). Since *
Pai > B/4 for all i, each set At contains exactly three elements. Since J(X ) = 0,
we have A = [16t6zAt and i2At ai ¼ B for 1 6 t 6 z, which imply that the 3-Partition problem has a
solution. h
Having established the strong NP-hardness of the stochastic planning problem, we shall prove that the NP-
hardness remains true even for a fixed planning horizon H (H = 2). The 2-Partition decision problem is used
for this purpose.
 M. Lamiri et al. / European Journal of Operational Research 185 (2008) 1026–1037 1035

Proof of Theorem 2. The 2-Partition decision problem is used to establish the complexity of the case H = 2.
This problem is Known to bePNP-hard, and can be defined as follows (Garey and Johnson, 1979): Given a set
of integers {ai}i2A such that Pi2A ai ¼ 2B,
Pthe question is whether there exists a partition of the set A into two
subsets A1 and A2 such that i2A1 ai ¼ i2A2 ai ¼ B.
The proof is based on the polynomial transformation of the 2-Partition problem to the following problem
(P2) (instance of the planning problem (P) with a two-period horizon). The problem instance (P2) is the same
as the problem instance (P1) except that H = 2 and N = jAj. More precisely, (P2) can be derived from the set A
of the 2-Partition problem as (P1) was derived from the set A of the 3-Partition problem.
Instance (P2): Given H = 2, we set Tt = B, Wt = 0 and COt = 1, "t 2 {1, . . . H}. The number of elective
cases N is equal to jAj. For each elective case i(i = 1. . .N), the operating time and the release period are
respectively equal to pi = ai and Bi = 1. The related costs of performing elective case i(i = 1. . .N), are given as
follows:
CEit ¼ 0; 8t 2 f1; . . . H g and CEiðH þ1Þ ¼ 1:
Decision problem: Is there a plan X* for the planning problem (P2) such that J(X*) = 0?
We now prove that (P2) has a solution iff the 2-Partition problem has a solution. It is obvious that a plan
for which J(X*) = 0 exists for the proposed instance if and only if the 2-Partition problem has a solution.
These conditions can be proved using the same arguments as in the proof of Theorem 1. Hence the two-period
planning problem is NP-hard. h

Appendix 2. Convergence of Monte Carlo optimization algorithm

We now give the proof of Theorem 3. We need to prove that the optimal solution of problem (P 0 ) converges
to an optimal solution of problem (P), as K increases. For this purpose, we use an equivalent formulation (P00 )
of problem (P 0 ):
N X
X H þ1 X
H
ðP00 Þ J K ¼ Minimize J K ðX Þ ¼ CEit X it þ COt Ot;K ð100 Þ
i¼1 t¼Bi t¼1
 þ
PK P
N
k¼1 W tk þ p X
i it  T t
i¼1
Subject to: Ot;K ¼ ; 8t ¼ 1; ::; H ; ð200 Þ
K
H þ1
X
X it ¼ 1; 8i ¼ 1; . . . ; N ; ð300 Þ
t¼Bi

ðBinary variablesÞ X it ¼ f0; 1g; 8i ¼ 1; . . . ; N ; 8t ¼ 1; . . . ; H þ 1; ð400 Þ

where Wt1, Wt2, . . ., Wtk are independent random samples of Wt.
It can be easily proved that problem (P00 ) is exactly equivalent to (P 0 ). We are now ready to prove the con-
vergence of (P 0 ) related optimal solution to an optimal solution of problem (P).
Let variables Ot(X) and Ot,K(X) be respectively the actual and the estimated overtime incurred in period t if
solution X is chosen. Then we have
" !þ # PK  PN
þ 
X N
k¼1 W tk þ i¼1 pi X it  T t
Ot ðX Þ ¼ EW t W t þ pi X it  T t and Ot;K ðX Þ ¼
i¼1
K
PN P
Since ðW tk þ i¼1 pi X it  T t Þþ are i.i.d. samples of random variable ðW t þ Ni¼1 pi X it  T t Þþ , by law of large
numbers, Ot,K(X) converges with probability 1 to Ot(X) as K increases. As a result, for any e P 0, there exists
an integer K t;X > 0 such that
jOt;K ðX Þ  Ot ðX Þj < e; 8K P K t;X :
1036 M. Lamiri et al. / European Journal of Operational Research 185 (2008) 1026–1037

Let K ¼ maxt;X K t;X . From (100 ) and (200 ),

X
H
jJ K ðX Þ  J ðX Þj 6 COt e; 8K P K: ð5Þ
t¼1

For every solution X, the estimated cost converges with probability 1 to the expected (exact) cost as K in-
creases. Hence,
X
H
jJ K ðX K Þ  J ðX K Þj 6 COt e; 8K P K:
t¼1

Further, for every K > K,

jJ K ðX K Þ  J K ðX  Þj ¼ J K ðX  Þ  J K ðX K Þ ðFrom the definition of X K Þ
6 J K ðX  Þ  J K ðX K Þ þ J ðX K Þ  J ðX  Þ ðFrom the definition of X Þ
X
H
6 j  J K ðX K Þ þ J ðX K Þj þ jJ K ðX  Þ  J ðX  Þj 6 2 COt e: ð6Þ
t¼1

As a result,
jJ K ðX K Þ  J ðX  Þj ¼ jJ K ðX K Þ  J K ðX  Þ þ J K ðX  Þ  J ðX  Þj 6 jJ K ðX K Þ  J K ðX  Þj þ jJ K ðX  Þ  J ðX  Þj
X
H
63 COt e ðFrom ð5Þ and ð6ÞÞ:
t¼1

Further,
jJ ðX K Þ  J ðX  Þj ¼ J ðX K Þ  J ðX  Þ ðFrom the definition of X  Þ
6 J ðX K Þ  J ðX  Þ  J K ðX K Þ þ J K ðX  Þ ðFrom the definition of X K Þ
X
H
6 jJ ðX K Þ  J K ðX K Þj þ j  J ðX  Þ þ J K ðX  Þj 6 2 COt e ðFrom ð5ÞÞ:
t¼1

To summarize, for all e > 0, there exist a finite integer K such that for every K > K,
X
H
jJ K ðX K Þ  J ðX  Þj 6 3 COt e; ð7Þ
t¼1
X
H
jJ ðX K Þ  J ðX  Þj 6 2 COt e: ð8Þ
t¼1

Inequality (7) implies that as K increases, the estimated cost J K ðX K Þ of the resulting optimal solution con-
verges with probability 1 to the exact optimal cost J(X*). While inequality (8) implies that the exact cost of
the resulting optimal solution converges with probability 1 to the exact optimal cost, as K increases. Hence
X K converges to an optimal solution X* of problem (P).

References

Denton, B., Gupta, D., 2003. A sequential bounding approach for optimal appointment scheduling. IIE Transactions 35, 1003–1016.
Dexter, F., Macario, A., Traub, RD., 1999a. Which algorithm for scheduling add-on elective cases to maximizes operating room
utilization? Use of bin packing algorithms and fuzzy constraints in operating room management. Anesthesiology 91, 1491–1500.
Dexter, F., Macario, A., Traub, R.D., Hopwood, M., Lubarsky, D.A., 1999b. An operating room scheduling strategy to maximize the use
of operating room block time: Computer simulation of patient scheduling and survey of patients preferences for surgical waiting time.
Anesthesia and Analgesia 89 (1), 7–20.
Fei, H., Chu, C., Artiba, A., Meskens, N., 2004. Planification des salles opératoires: Résolution par la génération de colonnes et la
programmation dynamique. In: 2ème Conférence Francophone en Gestion et Ingénierie des Systèmes Hospitaliers, GISEH, 9–11
Septembre, Mons, Belgique.
 M. Lamiri et al. / European Journal of Operational Research 185 (2008) 1026–1037 1037

Garey, M.R., Johnson, M.R., 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco.
Gerchak, Y., Gupta, D., Henig, M., 1996. Reservation planning for elective surgery under uncertain demand for emergency surgery.
Management Science 42 (3), 321–334.
Guinet, A., Chaabane, S., 2003. Operating theatre planning. International Journal of Production Economics 85 (1), 69–81.
Jebali, A., Hadjalouane, A.B., Ladet, P., 2005. Operating rooms scheduling. International Journal of Production Economics 99, 52–62.
Magerlein, J.M., Martin, J.B., 1978. Surgical demand scheduling: A review. Health Service Research 13 (4), 418–433.
Marcon, E., Kharraja, S., Simmonet, G., 2003. The operating theatre scheduling: An approach centered on the follow-up of the risk of no
realization of the planning. International Journal of Production Economics 85 (1), 83–90.
Ozkarahan, I., 2000. Allocation of surgeries to operating rooms by goal programming. Journal of Medical Systems 24 (6), 339–378.
Shukla, R.K., Ketcham, J.S., Ozcan, Y.A., 1990. Comparison of subjective versus data base approaches for improving efficiency of
operating room scheduling. Health Services Management Research 3, 74–81.
Weiss, E.N., 1990. Models for determining estimated start times and case orderings in hospital operating rooms. IIE Transactions 22 (2),
143–150.
Zhou, J., Dexter, F., 1998. Method to assist in the scheduling of add-on surgical cases, Upper prediction bounds for surgical case
durations based on the log–normal distribution. Anesthesiology 89 (5), 1228–1232.