A mixed integer linear programming approach to

schedule the operating room

F Maaroufi, H Camus, O. Korbaa

To cite this version:

F Maaroufi, H Camus, O. Korbaa. A mixed integer linear programming approach to schedule the
operating room. IEEE International Conference on Systems, Man, and Cybernetics (SMC 2016), Oct
2016, Budapest, Hungary. ฀10.1109/SMC.2016.7844840฀. ฀hal-01715076฀

HAL Id: hal-01715076

https://hal.archives-ouvertes.fr/hal-01715076
Submitted on 22 Feb 2018

HAL is a multi-disciplinary open access L’archive ouverte pluridisciplinaire HAL, est

archive for the deposit and dissemination of sci- destinée au dépôt et à la diffusion de documents
entific research documents, whether they are pub- scientifiques de niveau recherche, publiés ou non,
lished or not. The documents may come from émanant des établissements d’enseignement et de
teaching and research institutions in France or recherche français ou étrangers, des laboratoires
abroad, or from public or private research centers. publics ou privés.
 A mixed integer linear programming approach to
schedule the operating room
F. MAAROUFI H. CAMUS O. KORBAA

MARS équipe OSS LAGIS équipe OSL MARS équipe OSS

ENSI Manouba Ecole Centrale de Lille ISITCom Hamam Sousse
Manouba, Tunisia Villeneuve d’Ascq, France Sousse, Tunisia
fetenmaaroufi@yahoo.fr herve.camus@ec-lille.fr Ouajdi.Korbaa@Centraliens-Lille.org

Abstract— the problem studied in this paper is to allocate and the MILP model is more efficient than the CP model in terms
to sequence the elective operation on operating rooms (ORs). We of computational times.
develop a mixed integer linear programming (MILP) model to
solve this problem. Decisions in this model include the allocation This paper is organized as follows. In the next section, we
of operations to material resources and human resources, the propose a literature review of the OR scheduling and we
starting time of them and the starting time for each surgeon. To identify our contribution. A MILP model and a CP model are
show the efficiency of this model, we decide to compare it with a proposed in section 3. Section 4 compares the computational
constraints programming (CP) approach. The performance of performance of the two proposed models. Finally, the paper
these models is tested using a benchmark of the literature. The ends with concluding remarks and future research prospects in
results indicate the efficiency of the MILP model compared with section 5.
the CP model in terms of computational time.

Keywords—health care; operating rooms; mixed integer linear

II. LITERATURE REVIEW
programming; constraint programming The OR daily scheduling problem studied in this paper
consists of allocation elective operations on human and
I. INTRODUCTION material resources and sequencing them within each material
resource within a day planning horizon. Due to the high
Operating room is the most critical resources in hospitals. It complexity of these two components, there are many papers
is the most precious and costly resources. ORs account for ([1], [6], [9], [10] and [12]) decompose the problem in two sub
approximately 40 % of hospital’s total expenses [3]. In problems: assignment operations and sequencing operations. In
addition, ORs contribute the largest amount of revenues to this paper, we address the studies which directly focus on
most hospitals [2]. However, ORs draw their importance from deterministic programming approach and combining the
their potential revenues and prohibitive costs for the society, allocation and sequencing phases in the same problem.
patients and health care service.
Mathematical programming models, especially integer and
ORs center in hospital always face problems in scheduling mixed integer programming, are the most approaches used in
elective operations. In fact, these problems are among the the literature to solve the OR scheduling problem. [7] Propose
complex encountered by healthcare organization, indeed they an integer linear programming (ILP) model to schedule a real
have to take many constraints into account, in particular those case of elective operations from the waiting list on a weekly
related to the availability of staff, materials and financial time horizon with the objective of maximizing the use of the
resources. In addition, demand for operation very often surgical suite. The aim of the purposed model is to employ
overwhelms supply therefore causing long waiting times for more efficiently the resources installed in the surgical suite of
patients and reducing their quality of life. Therefore, OR the hospital. [2] Investigate the deterministic daily scheduling
manager are interested in finding new approaches to improve of surgical case problem. A new MIP is presented with the
their surgical suite, which has encouraged the development of objective of minimizing the total idle times of ORs and the
research in this domain. Makespan. With the MIP model, the authors determine the
This paper describes the problem of scheduling a known set allocation of resources and the sequence of operations within
of elective operations to OR. The scheduling decisions include OR and the start time of them. [5] Develop a mathematical
two aspects: (1) assignment of surgery to induction beds, OR, programming approach to solve the surgical operations
recovery beds and surgeon, and (2) the surgery sequence scheduling problem. They propose a MILP model to minimize
within each material resource. A MILP model and a CP model the number of unscheduled surgical operation. The proposed
are built to find a daily schedule that minimizes the Makespan model takes into account the constraints of human (surgeons)
which represents the completion time of the last patient’s and material (ORs) resources. There are others papers propose
operation. This objective is studied in the literature of OT a mathematical programming approaches and compare their
scheduling by [4] and [2]. The performance of these two performance with heuristics approaches, for instance [12] Use
models is tested using a series of computational experiments a RCPSP (Resource Constraint Project Scheduling Problem) to
based on benchmark of the literature and the results show that generate scheduling and planning of the surgical operations
while focusing as much attention on human resources
(surgeons) as on economic factors. They develop a MIP model
including the planning and scheduling problem. They compare pbo Duration of recovery of operation o
the results of MIP with a heuristic solution procedure based on tr OR turnover time between two consecutive operations
genetic algorithm. [4] Investigate the deterministic daily ts Surgeon turnover time between two consecutive operations
Pretp,r Operation of type tp is operated in the room r
scheduling operating rooms problem for elective patient. They
propose a constraint programming model to solve their A. a MILP model
problem taking into account some constraints on human
This section describes the MILP model for determining the
(surgeons) and material (OR and recovery bed) resources and
daily surgical scheduling of electives patients. Let [As, Bs]
they compare the CP model with a MILP model.
represents the interval surgeons availability. Each surgeon s
Although these papers study the allocation and sequencing expresses her/his availability which can operate on day; such as
phases and resolve with mathematical programming approach, Bs – As = RATSs. A solution to the schedule problem is given
we cannot use those approaches because all of these assume by means of integer and binary variables.
that the human resources (surgeons) are already known in
advance (i.e. the allocation of the human resources to operation TABLE II. DECISION VARIABLES OF MILP MODEL
is known) to reduce the complexity of the problem and in our
approaches the allocation of the human resources (surgeons) Integer variables
are unknown. In addition, in this paper the operating theatre SOo Starting time of operation o
SIo Starting time of induction of operation o
(OT) composes of induction beds, ORs and recovery beds;
SBo Starting time of recovery of operation o
while these previous papers focus on the OR or\and the Δo Duration of recovery of operation o in OR
recovery beds. The new structure of the OT is studied in [6] but Ss Starting time of surgeon s
the authors resolve the allocation problem with heuristic Binary variables
approach and propose a MILP model to sequence the zo,p,Ib 1 if operation o starts before operation p in the induction
operations into material resources. bed Ib
Θo,p,r 1 if operation o starts before operation p in the OR r
The contributions made in this study are follows: we model α o,p,b 1 if operation o starts before operation p in the recovery bed
the deterministic OT scheduling problem, integrating allocation b
and sequencing decisions in the same model; we consider yo,p,s 1 if operation o starts before operation p in the operation list
surgeons, nurses, induction beds, ORs as well as recovery beds, of surgeon s
IBo,Ib 1 if the operation o assigned to the induction bed Ib
as resources and we provide a more realistic model of the RBo,b 1 if the operation o assigned to the recovery bed b
surgery process by explicitly considering the induction, the ORo,r 1 if the operation o assigned to the OR r
operations and the recovery tasks. NURo,nr 1 if the operation o assigned to the nurse nr
SURo,s 1 if the operation o assigned to the surgeon s
III. PROBLEM DEFINITION wnr,r 1 if the nurse nr is assigned to OR r

Many paper focus on the ORs and recovery room when A MILP model is then formulated as follows:
discussing OT scheduling problem. Furthermore, induction
task is always performed in the OR. The contribution of the
paper is to separate the induction and the operation task to obj = min (max (SBo+pbo-Δo)) (1.1)
improve the use of the ORs. With the new structure of the OT,
the goal is to perform the induction task in induction room
while the OR is prepared for another operation. ∑Oo=1 po×ORo,r≤ RATr  r ϵ {1..R} (1.2)
A MILP model is proposed to minimize the Makespan of
the OT. To show the efficiency of the MILP model, we
develop a CP model and we compare the results of the MILP ∑o=1Os po×SURo,s≤ RATSs  s ϵ {1..S} (1.3)
with the CP model. Here are the notations used for the two
proposed models.
∑r=1R OR o,r = 1  o ϵ {1..O} (1.4)
TABLE I. NOTATIONS

O The total number of operation

∑Ib=1IBIBo, Ib ≤1 o ϵ {1..O} (1.5)
R The total number of ORs
IB The total number of induction beds
B The total number of recovery beds
S The total number of surgeons ∑b=1B RBo, b ≤1 o ϵ {1..O} (1.6)
NM The number of nurses available for an operation in OR
NR The total number of nurses nr
Rs The set of rooms preferred by the surgeon s
Os The set of operation preferred by the surgeon s ∑nr=1NR NURo,nr ≥ NM  o ϵ {1..O} (1.7)
RATr Regular Available Time for OR r
RATSs Regular Available Time for Surgeon s
pIbo Duration of induction of operation o
∑r=1R wnr,r ≤ 1  nr ϵ {1..NR} (1.8)
po Duration of operation o
pIo Induction time of operation o in the OR
 wnr,r ≥ 1 – M × (2- ORo,r – NURo,nr) o ϵ {1..O}, nr ϵ SIp ≥ SIo + pIo - M× (3- zo,p,Ib- IBo,Ib – IBp,Ib) o,p ϵ {1..O},
{1..NR} (1.9) o≠p, Ibϵ {1..IB} (1.25)

∑o=1O∑tp=1Type∑r=1R ORo,r × pretp,r =O (1.10) SOp≥ SOo + pIro + po + tr +Δo – M × (3- θo,p,r –ORo,r –
ORp,r) o,p ϵ {1..O}, o≠p, rϵ {1..R} (1.26)

θo,p,r+ θp,o,r ≤ ORo,r o,p ϵ {1..O}, o<p, r ϵ {1..R} (1.11)

SBp≥ SBo + pbo - Δo – M × (3- αo,p,r –RBo,b – RBp,b) o,p ϵ
{1..O}, o≠p, bϵ {1..B} (1.27)
θo,p,r+ θp,o,r ≤ ORp,r o,p ϵ {1..O}, o<p, r ϵ {1..R} (1.12)

SOp≥ SOo + pIro + po + tr +Δo – M × (3- θo,p,r –NURon,r –

θo,p,r+ θp,o,r ≥ ORo,r + ORp,r -1 o,p ϵ {1..O}, o<p, r ϵ {1..R} NURpn,r) o,p ϵ {1..O}, o≠p, nrϵ {1..NR} (1.28)
(1.13)

SOo ≥ Ss – M × (1- SURo,s) o ϵ {1..O}, s ϵ {1..S}(1.29)

zo,p,Ib + zp,o,Ib ≤ IBo,Ib o,p ϵ {1..O}, o<p, Ib ϵ {1..IB}
(1.14)
SOp + pIrp ≥ SOo + pIro + po + ts – M × (3- yo,p,s – SURo,s –
SURp,s) o,p ϵ Os, o≠p, s ϵ {1..S} (1.30)
zo,p,Ib + zp,o,Ib ≤ IBp,Ib o,p ϵ {1..O}, o<p, Ib ϵ {1..IB}
(1.15)
SOo + pIro+ po – M× (1-SURo,s) ≤ Bs o ϵ Os, s ϵ {1..S}
(1.31)
zo,p,Ib + zp,o,Ib ≥ IBo,Ib + IBp,Ib -1o,p ϵ {1..O}, o<p, Ib ϵ
{1..IB} (1.16)
SOo + pIro ≥ As × SURo,s o ϵ Os, s ϵ {1..S} (1.32)

αo,p,b + αp,o,b ≤ RBo,b o,p ϵ {1..O}, o<p, b ϵ {1..B} (1.17)

wnr,r, ORo,r, IBo,Ib, RBo,b, NURo,nr, SURo,s ϵ {0,1}o ϵ
{1..O}, s ϵ {1..S}, r ϵ {1..R}, nr ϵ {1..NR}, Ib ϵ {1..IB}, b ϵ
αo,p,b + αp,o,b ≤ RBp,b o,p ϵ {1..O}, o<p, b ϵ {1..B}(1.18) {1..B} (1.33)

αo,p,b + αp,o,b ≥ RBo,b + RBp,b -1 o,p ϵ {1..O}, o<p, b ϵ SOo, SIo, SBo, Ss ≥ 0 o ϵ {1..O}, s ϵ {1..S} (34)
{1..B} (1.19)
The criterion obj to optimize is the maximum completion
time for operation in the OT. In order to obtain the most
yo,p,s + yp,o,s ≤ SURo,s o,p ϵ {1..O}, o<p, s ϵ {1..S} balanced operation schedule with smaller amount of opening
(1.20) hours in the OT on the day, we employ the Makespan of the
OT. Constraints (1.4) ensure that an operation can be assigned
to an OR only if it is opened and each operation is assigned to
exactly one OR, respectively. Constraints sets (1.2) - (1.3)
yo,p,s + yp,o,s ≤ SURo,s o,p ϵ {1..O}, o<p, s ϵ {1..S} impose a daily operating time limit on each OR and surgeon.
(1.21) Constraints (1.5) – (1.6) ensure that each operation should be
assigned to at most one induction bed and one recovery bed.
Constraints (1.7) impose the minimal number of nurses who
yo,p,s + yp,o,s ≥ SURo,s + SURp,s -1 o,p ϵ {1..O}, o<p, s ϵ can participate in one operation. Constraints (1.8) and (1.9)
{1..S} (1.22) ensure that a nurse does not overlap between operating rooms
during the day. Constraints (1.10) are related to OR
accessibility and verify that the operations happen in an
SIo + pIo = SOo  oϵ {1..O} (1.23) appropriate OR.
A precedence relation exists between two operations if and
only if they are assigned to the same OR (resp. induction beds,
SOo+ pIro+ po + Δo = SBo o ϵ {1..O} (1.24) recovery beds, surgeons). This is enforced by constraints (1.11)
- (1.22). The set of the constraints (1.23) and (1.24) define the
precedence constraints. Constraints (1.25) and (1.27) ensure ∑o=1O∑τ=tmin(t+ po+ pIro+ Δo+ tr -1, T) ORo,r,τ ≤ 1r ϵ {1..R}, t ϵ
that an induction bed and a recovery bed cannot be occupied by {1..T} (2.4)
more than one patient in the same time. The constraints (1.26)
imply that an OR cannot be occupied by more than one patient.
Constraints (1.28) verify that a nurse cannot participate in more ∑o=1Os∑τ=tmin(t+ po+ ts -1, T) SURo,s,τ ≤ 1s ϵ {1..S}, t ϵ {1..T}
than one operation at the same time. Constraints (1.30) ensure (2.5)
that a surgeon cannot operate more than one patient at the same
time. Constraints (1.25) – (1.30) make sure that two operations
do not overlap in time if their assigned resource (OR or
surgeon or nurse) is the same. Observe that the constraints ∑o=1O∑τ=tmin(t+ pIo -1, T) IBo,Ib,τ ≤ 1Ib ϵ {1..IB}, t ϵ {1..T}
(1.26) are inutile if the operating room r is not assigned to o (2.6)
and p, respectively, since then θo,p,r + ORo,r + ORp,r ≤ 1 and
hence M (3 - θo,p,r –ORo,r – ORp) is greater than the left-hand
side because of a very large value of M. If the operating room r ∑o=1O∑τ=tmin(t+ pbo- Δ -1, T)
o RBo,b,τ ≤ 1b ϵ {1..B}, t ϵ {1..T}
is assigned to o and p then the constraints (1.15) are necessary, (2.7)
depending on whether θo,p,r =1 or θo,p,r =0. For instance θo,p,r =1,
constraints (1.15) say that the operation p starts after the
completion time of operation o with a minimum time tr ∑r=1R∑t=1T ORo,r,t = 1  o ϵ {1..O} (2.8)
(cleaning time of OR). The M parameter used is an upper
bound on the surgery completion time, this value is sufficient
to keep the constraints (1.25) - (1.31) inutile when necessary. ∑Ib=1IB∑t=1T IBo,Ib,t ≤ 1  o ϵ {1..O} (2.9)
Constraints (1.29) ensure that operation of a surgeon cannot be
started before his or her arrival to the surgical suite. Constraints
(1.19) ensure that the starting time of each operation cannot be
more than the daily regular availability. Constraints (1.31) and ∑b=1B∑t=1T RBo,b,t ≤ 1  o ϵ {1..O} (2.10)
(1.32) ensure that each surgeon operates during the interval of
time in which he/she is available. Finally, the constraints (1.33)
and (1.34) express the variables’ domain. ∑nr=1NR∑t=1T NURo,nr,t ≥ NM  o ϵ {1..O} (2.11)

B. a CP model
This section presents the CP model we build for solving the ∑t=1min(t+ pIo-1, T) ∑Ib=1IB (t+ pIo) × IBo,Ib,t ≤ ∑t=1T∑r=1R t ×
elective scheduling problem. In this model, time has a discrete ORo,r,t  o ϵ {1..O} (2.12)
representation as a set of time periods available for scheduling,
{1…T}. This representation of time is used in the literature
such as [4] and [12] when they solve the scheduling problem ∑t=1min(t+ po+ pIro+ Δo -1, T) ∑r=1R (t+ po+ pIro+ Δo) × ORo,r,t ≤
with the CP mechanism. Let SA(s,t,r) represents the matrix ∑t=1T∑b=1B t × RBo,b,t  o ϵ {1..O} (2.13)
surgeons availability. Each surgeon s expresses her/ his
availability in time slot t in preference room r ϵ Rs; which
represents the set of preference room of surgeons. Before ∑o=1Os∑τ=tmin(t+ p -1, T)
o ORo,r,τ ≤ SA(s,t,r) s ϵ {1..S}, t ϵ
formulating the problem, we define the set of binary variables: {1..T}, r ϵ Rs (2.14)

TABLE III. DECISION VARIABLES OF CP MODEL

ORo,r,t 1 if operation o starts in the OR r at

∑o=1Os∑τ=tmin(t+ po -1, T) ORo,r,τ = ∑o=1Os∑τ=tmin(t+ po -1, T) SURo,s,τ
time slots t s ϵ {1..S}, t ϵ {1..T}, r ϵ Rs (2.15)
IBo,Ib,t 1 if operation o starts in the
induction bed Ib at time slots t
RBo,b,t 1 if operation o starts in the recovery
bed b at time slots t
SURo,s,t = 0  o ϵ {1..O}\Os, sϵ {1..S}, t ϵ {1..T} (2.16)
SURo,s,t 1 if operation o is performed by
surgeon s at time slots t
NURo,nr,t 1 if operation o is assigned to nurse ∑t=1T ORo,r,t ≤ prer,tp  o ϵ {1..O}, r ϵ {1..R}, tp ϵ
nr at time slots t
{1..TYPE} (2.17)
The CP model is then formulated as follows:

∑o=1O∑t=1T po× ORo,r,t ≤ RATr r ϵ {1..R} (2.2) ∑o=1O∑t=1T (t+ pbo ) × RBo,b,t≤ T  bϵ {1..B} (2.18)

∑o=1 Os ∑t=1T po× SURo,s,t ≤ RATSs s ϵ {1..S} (2.3)

 ORo,r,t, IBo,Ib,t, RBo,b,t, NURo,nr,t, SURo,s,t ϵ {0,1}  o ϵ Inst.7 15 6 9 9 9
{1..O}, r ϵ {1..R}, s ϵ {1..S}, bϵ {1..B}, Ibϵ {1..IB}, t ϵ {1..T} The setup time for OR and surgeons is tr = ts= 15 min. For
(2.19) all ORs and all surgeons the regular operating time
RAT=RATS= 480 min. For the CP model, the duration of the
Here, constraints sets (2.2) and (2.3) impose a daily time slot is set to 15 min, thus creating 32 daily time periods in
operating time limit on each OR and surgeon. Constraints (2.4) regular working time, whilst overtime is not provided for
(resp. (2.6) and (2.7)) prevent the assignment of several planning.
overlapping operations in the same room (resp. the same
induction bed and the same recovery bed). These constraints A. The comparaison of the two models
also present tr empty periods for room cleaning at the end of Table V summarizes the computational performance of the
each operation. The set of constraints (2.5) guarantees that a two models. The first column lists the number of the instances.
surgeon is assigned to at most one operation at any time. The The columns Variables and Constraints represent respectively,
surgeons may exchange operating rooms. This exchange the number of variables and constraints in the two models. The
allows surgeons to work in another OR during hygiene periods Obj column shows the optimal objective value found when the
in the previous room (about 15 min idle). This is also the program is terminate; and the CPU column is the
reason why the cleaning time is not incorporated in the computational time (in seconds) when the optimal solution is
operations’ duration. Constraints (2.8) ensure that an operation obtained. The performance of the two models is compared
begins once and only once. Constraints (2.11) express that from four aspects. The results are shown in Table V. As we can
there are at least NM nurses in per operation. The constraints see, the MILP model is efficient to solve the operation
(2.9) (resp. 2.10) ensure that only one operation can stay in the scheduling problem. Both the number of variables and
induction bed (resp. recovery bed) at time slots t. The constraints of the MILP model are smaller than the CP model.
precedence constraints are described in the set of constraints Partially due to the smaller number of constraints and
((2.12) – (2.13)). In constraints (2.14) every surgeon expresses variables, the MILP model is solved faster and can make the
her/his preference and the availabilities for certain time slots, optimal solution compared with the CP model. For all instance,
the availability is presented by the matrix SA (s, t, r). the MILP model is able to find the optimal solution in a
Constraints (2.15) verify that the surgeon cannot be in two ORs reasonable time for this problem; in average the CPLEX solver
by the same time. Constraints (2.16) ensure that the surgeons take 700 seconds (11 minutes) to find the optimal solution.
perform the preference operations. Constraints (2.17) are
related to OR accessibility and verify that the operations We show that the optimal solutions found by the CP model
happen in an appropriate ORs. The set of constraints (2.18) are the same with the ones obtained by the MILP model.
bound the limited capacity for OT in number of available Nevertheless, if we look at the CPU time to obtain the optimal
hours. Constraints (2.19) express the variables’ domains. solution, we notice that the CP proves more computational
times than the MILP model. We also notice that the more the
instance has a large number of constraints, the more the values
IV. EXPERIMENTAL RESULTS of the time computing is increase, which is normal. This shows
This section presents a comparison between both proposed us that the CP, when there is a large number of constraints,
models described in section 3. These two models are takes advantage of the parceling of the search space.
implemented under Windows 8 with an Intel® Celeron® 1.4
GHz processor and 4.0 GB RAM. The MILP model is solved In this section, we compare an exact method (MILP) by an
using IBM-ILOG-CPLEX 12.2. The CP model is based on the approximate method (CP). We push the CP model to find the
constraint programming method. It is solved by the solver optimal solution to compare with the MILP model in terms of
included in the Java library CHOCO 3.0.0 using JDK 1.8. computational times. We notice that The CP model uses more
CHOCO is a library for constraint satisfaction problems (CSP) time to find an optimal solution unlike the MILP model which
and CP and is based on a mechanism of propagation of finds the optimal solution in a reasonable time. Therefore, to
instantiation with structures which use a “backtracking” our problem, The MILP approach is sufficiently efficient to
algorithm. This solver is used by [4] and [8] for solving OR propose optimal solutions in a very short time and an
scheduling problem using a CP mechanism. These two models approximately approach is not necessary.
are evaluated by solving several problem instances described in
Table IV where O denotes the number of operations and R, S, B. The impact of the new structure of OT
IB and B represent respectively the number of OR, surgeons, In this section we compare two scheduling strategies: in the
induction beds and recovery beds. first, we assume that the induction of operation is performed in
the OR. In the second strategy, the induction of operation is
TABLE IV. CHARACTERISTICS OF PROBLEM INSTANCES
performed in the induction bed.

Instances O R S IB B To test the two strategies, we use the problem instance n°3
N° where there are four ORs, six induction beds, six recovery beds
Inst.1 9 4 6 6 6 and four nurses. The problem instance includes 13 operations
Inst.2 11 4 6 6 6 performed by six surgeons over single day. In strategy 1, the
Inst.3 13 4 6 6 6 Makespan is 525 minutes and in the second the Makespan is
Inst.4 15 4 6 6 6 450 minutes. We notice that in the first strategy we have 45
Inst.5 11 6 9 9 9
minutes overtime and with the new structure the Makespan is
Inst.6 13 6 9 9 9
reduced and all operations are scheduled in a regular time of number of planned operations in the planning day and
OT. maximize the occupancy rate of the ORs.
Fig. 1. Charge of ORs in these two strategies In this paper, we study the daily scheduling problem in a
deterministic context. In the future work, it is necessary to take
into accounts the urgent operations and to evaluate the
robustness of the MILP model. Other suggestion for future
research is to extend the proposed models by including other
human resources such as the porters and the anesthetists.

REFERENCES
[1] V. Augusto, X. Xie and V. Perdomo, Operating theatre scheduling with
patient recovery in both rooms and recovery beds, Computer &
Industrial Engineering., vol. 58, pp.231-238, 2010.
[2] H. Ghazalbash, M.M. Sepehri, P. Shadpour and A. Atighehchian,
Operating room scheduling in teaching hospitals, Advances in Operation
Research, vol. 2012, 2012.
[3] A. Jebali, A. Hadj Alouane and P. Ladet, Operating rooms scheduling,
International Journal of Production Economics, vol. 99, N°1-2, pp. 52–
62, 2006.
We can see in fig.1, when the induction is performed in the [4] A. Hanset, N. Meskens and D. Duvivier, Using constraint programming
induction bed, the occupancy of the ORs is reduced. In this to schedule an operating theatre, Health Care Management (WHCM),
IEEE Workshop, pp.1- 6, 2010.
case we can add other operations in the daily planning and we
can maximize the occupancy rate of ORs. Therefore the [5] E. Koksalmis, K.O. Hancerliogullari and G. Hancerliogullari, How to
schedule surgical operations into operating rooms? An application in
economic profit of OR can increase. Turkey, Industrial and systems Engeneering Research Conference
Montréal Canada, pp. 1139-1148, 2014.
V. CONCLUSION [6] F. Maaroufi, H. Camus and O. Korbaa, A VSCP approach for solving
the operating theater scheduling problem, the first international
In this study, we present a MILP model for OR scheduling conference on Reasoning and Optimization in Information Systems
problem. This model takes into account the material (induction (ROIS’2013) Hamam Sousse Tunisia, DOI: 10.13140/2.1.4864.3363,
beds, ORs and recovery beds) and human (surgeons and pp.57-64, 2013.
nurses) resources. The main contribution of the paper is to [7] I. Marques, M.E. Captivo and M. Vaz Pato, An interger programming
solve the allocation and sequenced phases in the same problem approach to elective surgery scheduling, OR Spectrum, vol. 34, pp. 407-
427, 2012.
and to perform the induction of operation in the induction bed.
[8] N. Meskens, D. Duvivier and A. Hanset, Multi-objective operating room
To prove the efficiency of MILP model to solve the scheduling considering desiderata of the surgical team, Decision Support
scheduling problem, we develop a CP model. These two Systems, vol. 55, pp. 650-659, 2013.
models are evaluated using several problem instances and we [9] D.N. Pham and A. Klinkert, Surgical case scheduling as a generalized
job shop scheduling problem, European Journal of Operational
push the CP model to find the optimal solution. The results Research, vol. 185, pp. 1011–1025, 2008.
show that the MILP model is more efficient than the CP model [10] A. Roberto, L.Paolo, S.Patrick, T.Elena, T. Angela, A two level
in terms of computational times. Thus, for this problem, the metaheuristic for the operatig room scheduling and assignement
exact method is sufficiently efficient to find optimal solutions problem, Computers& Operation Research, vol. 54, pp.21-34, 2015.
in a reasonable time. [11] B. Roland, C.D. Martinelly, F. Riane and Y. Pochet, Scheduling an
operating theatre under human resource constraints, Computer &
To analyze the impact of the new structure of the OT, we Industrial Engineering journal, vol. 58, pp. 212-220 ,2010.
compare two strategies scheduling: induction of operation is [12] Z. Zaho and X. Li, Scheduling elective surgeries with sequence-
performed in the ORs or in the induction bed. According to the dependent setup times to multiple operating rooms using constraint
results, we show that with the new structure of the OT, the programming., Operations Research for health care, vol. 3, pp. 160 –
occupancy of the ORs is reduced which we can increase the 167, 2014

TABLE V. THE COMPUTATIONAL PERFORMANCE OF THE TWO MODELS

MILP model CP model

Instances variables constraints Obi CPU (s) variables constraints Obi CPU (s)
N° (min) (time
slots)
Inst.1 1935 4436 315 4.93 7488 12160 21 3202.15
Inst.2 2854 6626 375 125.74 9152 14230 25 7355.21
Inst.3 3953 9256 450 1378.28 10816 16280 30 11058.7
Inst.4 5232 12318 480 975.32 12480 18340 32 14961.51
Inst.5 4232 9982 315 23.51 13728 22833 21 16541.22
Inst.6 5863 13935 330 960.33 16224 25917 22 22547.1
Inst.7 7762 18548 375 1391.25 18720 29001 25 31047.85