INTRODUCTION
The operating theatre involves two sectors: Operating Rooms (ORs) and PostAnesthesia
Care Unit (PACU) or revival beds. The operating process procedure is divided
into three phases:
• 
The preoperative step during which the patient undergoes
surgical and anesthetics consultations. It extends from the admission of
the patient until the eve of the intervention 
• 
The peroperative step which ranges from the patient mental preparation
before surgery intervention, until he wakes up and leaves the PACU. This
phase takes place the day of the intervention. In cases where the patient's
condition is considered critical, it will rather lead to Intensive Cares
Unit (ICU) (Hammami et al., 2007) 
• 
The postoperative phase after his revival 
The operating theatre program refers to two sequential subproblems: Advanced
scheduling which plans the surgeries a week before and the allocation scheduling
which determines the order of surgical interventions passages in one day and
their assignments in the operating theatre.
In this study, we limited our study to the peroperative (during surgery) steps of the operating procedure.
OPERATING THEATRE SCHEDULING PROBLEM
Problematic and contribution: Many solutions for the surgeries scheduling
problem can be found in the literature. Some approaches are based on the simulation
(Dexter et al., 1999). Jebali
et al. (2006) introduced a twostep approach for operating room
scheduling, where operations are assigned to ORs in the first step and then
these operations are sequenced in the second step. The reader may also refer
by Guinet and Chaabane (2003), Hsu
et al. (2003), Van Oostrum et al. (2008)
and Cardoen et al. (2009b). A summary of recent
approaches can be found by Cardoen et al. (2010).
The criteria of scheduling surgical interventions depend on the strategy adopted
at the Advanced Scheduling. We can find: Overuse and underuse of the operating
rooms (Fei et al., 2010), Makespan (Kharraja
and Marcon, 2003) operating rooms efficiency (Dexter
et al., 2002) patients waiting and total interventions cost (Cardoen
et al., 2009b).
Scheduling seeks to balance needs expressed by patients, surgeons with clearly
defined policies and supplies. The presence of a large number of constraints
is a difficulty in constructing this schedule. In the field of manufacturing
systems, many works were interested by developing of assignment and scheduling
algorithms under constraints (Espinouse et al., 1999;
Baptiste et al., 2001; AlemTabriz
et al., 2009). In the area of operating programming, constraints
studied had economic nature so they were limited to time’s constraints
and such as: Opening hours of the operating rooms (Kharraja
and Marcon, 2003), time available for each time slot, average waiting time
(Dexter et al., 2002) deterioration of the noidle
constraint. To our knowledge, only the study of Sier
et al. (1997) and Jebali et al. (2006)
considered patients satisfiablility or surgeries quality by taking into account
number of constraints such as priority by age, assignment laws and respect of
rooms’ specialization and recently Cardoen et al.
(2009a) solved a case sequencing problem in which they propose to minimize
the date of surgeries of children and prioritized patients. In this last study,
authors ignore assignments to beds. They took into account a good sized PACUs
with identical beds and without intensive care beds. Present study is to adapt
some manufacturing systems constraints of sequencing and assignment to operating
theatre scheduling problem. Thus, we undertake to propose constraints of quality
and of service feasibility not present in the literature of surgeries scheduling
as they are present in the literature of manufacturing systems scheduling. We
got these constraints after a view of the set of constraints known in manufacturing
systems literature and a deep study with experts at different operating theaters
especially in the academic and hospitable establishment of Oran (EHUO: Etablissement
Hospitaliers et Universitaire d’Oran).
Analogy with the manufacturing system scheduling problem: On the one
hand, the difference between manufacturing system and the operating theatre
lies in their products. Compared to the manufacturing system where the processes
are deterministic, in the Operating theatre system services are offered to patients
whom health vary and preferences vary. In addition, there are more frequent
emergencies in the hospital than in the manufacturing systems. On the other
hand, unlike the Manufacturing System where a machine is normally occupied by
a technician, surgical teams are composed of members from different specialties
(surgeons, nurses, anesthetists etc.) So, it needs to coordinate activities.
In Table 1 we consider the surgical as tasks, the operating
units as service centers and we can deduce that the operating theatre is composed
of two stages where the first are the parallel operating rooms and the second
are beds in PACU.
Table 1: 
Comparison between manufacturing system scheduling and operating
theatre scheduling. 

This system is literally classified as a hybrid flow shop.
HYBRID FLOW SHOP PROBLEM
Presentation of hybrid flow shop: A Hybrid Flow Shop (HFS) also called
flexible flow shop, is a system composed of a set of stages, where each stage
is composed of one or more parallel machines. The different jobs visit the stages
in the same order. On each stage, a job is treated by one machine only. Between
each stage, the jobs can wait or not in limited or unlimited buffers (Vignier
et al., 1999).
Scheduling in the HFS consists to find a adequate sequence of the jobs in entry and an assignment of the jobs on the various machines at the various stages. The objective is Optimization of a criterion of performance among the criteria one can quote the makespan or C_{max}, F_{max}, etc.
Number of tasks scheduled is N. The assignment of a task i to the jth machine in the stage k is noted v_{i,k}=j. l_{k} is the number of machines in stage k.
Figure 1 is an example of a hybrid flow shop with 2 stages
and 3 machines on the first stage and 2 machines on the second one. A buffer
of infinite capacity is incorporated between stages of the system. Moreover,
all jobs are assumed to be available at the system entrance with release date
with value 0 (Belkadi et al., 2006; Sahraoui
et al., 2003).
If we take as criterion the C_{max }(the completion time of the last
job on the last stage)and using the notation of (Vignier
et al., 1999), the system can be defined by FH2 (M(3),M(2))C_{max}.
Survey of the twostage HFS scheduling: The flow shop scheduling problem has been shown to be NPHard.

Fig. 1: 
HFS,M(l_{1}=3),M(l_{2}=2)C_{max} 
General HFS studies are found by Baker (1974) and Carlier
(1993). Shen and Chen (1972) were the first to tackle
a twostage HFS with l_{1}>2;l_{2}>2. They
proposed a permutation heuristic to solve the Makespan Minimization Problem
(MMP) when preemption is not allowed. Buten and Shen (1973)
have studied the same problem but with jobs having precedence constraints, which
they solved with a modified version of Johnson (1954)
algorithm. Gupta (1988) has studied the MMP in a twostage
HFS with l_{1}>=2 and l_{2}=1. He states that
the MMP in a twostage HFS is NPhard when max (l_{1}, l_{2})>1.
This result is very important because it shows that any MMP in a Kstage HFS
is NPhard, since the Kstage HFS can always be reduced to a twostage HFS.
He proposed a heuristic and lower bounds for the MMP case.
Sriskandarajah and Sethi (1989) focused on the two
stages HFS with single machine on the first stage and parallel identical machines
on the second stage to minimize the makespan.
CONSTRAINTS ADAPTED TO OPERATING THEATRE
A notation adapted to the operating theatre scheduling problem are presented. We submit from the 3rd subtitle, this problem to many constraints.
Problem notation: We consider the problem as a twostage hybrid flow shop with without buffer or with Blocking, where the first stage represents noidentical ORsand the second, beds in the PACU (Fig. 2).
The Input Parameters are:
K 
= 
2 number of stage 
N 
= 
No. of patients 
l_{1} 
= 
No. of ORs in stage 1 
l_{2} 
= 
No. of beds in stage 2 

Fig. 2: 
Organization of the operating theatre 
The Indices used are:
k 
= 
Stage where, k = 1..2 
j 
= 
Processor in stage, where, j =1… li 
i,i’ 
= 
Patient where i,i’=1..N 
t_{ik} 
= 
Processing times of a patient i in the stage k 
Decision variables are:
d_{i,k} 
= 
Begining time of the patient i at stage k 
f_{i,k} 
= 
Departure time of patient i from stage k 
C_{max} 
= 
Makespan. It is calculated by the Eq. 1: 
We obtain HFS2 (M(l1),M(l2)block  C_{max} according to Vignier notation(Vignier
et al., 1999).
For the solution notation , we consider:
p_{i} 
= 
1..N is the patient of the order i 
o_{pi} 
= 
1..l_{1} is the OR assigned to the patient p_{i} 
b_{pi} 
= 
1..l_{2} is the bed assigned to the patient p_{i} 
A solution is a combination of the three vectors (pob).
Example: A solution for 4 patients in a HFS2(M3,M5) t,d,f,block C_{max} can be notated as below:
(4,3,2,11,1,3,21,2,5,3)  
Where:
p_{1} 
= 
4: The patient number 4 passes in 1st order 
o_{4} 
= 
1: The OR assigned to patient 4 is the 1st one 
b_{4} 
= 
1: The bed assigned to patient 4 is the 1st one 
Time and block constraints: Hwan and Pinedo (1986),
Espinouse et al. (1999), Abadi
et al. (2000) and Kalczynski and Kamburowski,
(2005) blocking flow shop problem as follows: The flow shop has no intermediate
buffer therefore a job cannot leave a machine until the next machine downstream
is free. If that is not the case, the job (and the machine as well) is said
to be blocked. Detailed survey of the application and research on the problem
is given by Hall and Sriskandarajah (1996).
We can deduce Eq. 2 about the date of leaving the OR and
Eq. 3 about the relation between two patients assigned to
the same bed in PACU.
In addition to the particularity of blocking constraint, the time of execution
on the second stage decreases if the patient began to wake up in the OR. We
calculate the real time which must be spent in the PACU, noted tr_{i,2}
as Eq. 4:
Order constraints: Here, we present the constraints that affect on the
sequence of the patients. We quote:
• 
Connective precedence 
• 
Unitary precedence 
• 
Sequencing relation 
• 
Temporal localization 
Connective precedence: This constraint was discussed by BottaGenoulaz
(2000). We can say that we have a connective precedence where, a patient
i must be scheduled above all others by priority (5). Let note p^{1}
the order or the inverse function of p.
We note: prio_{i }as an integer and a default value is 0.
Some data as the age of patients, operating and revival times or having already
a canceled surgery, allow deciding priorities for the sequence of surgeries.
Unitary precedence: Many definitions were given to this constraint (Buten
and Shen, 1973; Rinnoy, 1976; Kurisu,
1976; Espinouse et al., 1999) as a relation
between only two tasks when one must be schedule above another in the same stage
or when they use the same machine. We define the unitary precedence where a
patient p_{i} must be scheduled above another p_{i’}. Eq.
6 and 7.
We note: prec_{pi,pi’ } as a Boolean and a default value is 0:
If p_{i }must be scheduled directly above p_{i’}, we talk
about strict precedence Eq. 8 and 9.
We note: pres_{pi,pi’} as a Boolean and a default value is 0.
An example of the use of this last restriction is the case of transplantation.
Those two constraints can be transformed in priorities.
Sequencing relation: The Sequencing Relation was defined by Esquirol
et al. (2001) for projects scheduling. In our case it prohibits for
a given pair of patients (p_{i},p_{i’}) any scheduling
where, p_{i} is directly above p_{i’} or p_{i’}
is directly above p_{i}. Eq. 10 and 11.
We note: nonseq_{pi,pi’ }as a Boolean and a default value is 0.
We consider this constraint when the surgeries of p_{i’} and p_{i
}require a special effort from the surgical team or a special supply from
the pharmacy.
Temporal localization: A temporal localization gives earliest Eq.
13 and latest Eq. 12 dates (Giard,
1991) for the start of a surgery.
We note: dmax_{i} or dmin_{i} as float and default values are
1;
This constraint can be defined where the fasting duration is paramount.
Assignment constraints: Here, we present the constraints that affect
on the assignment of the patients to ORs and beds. We quote:
• 
Dedication constraint 
• 
Technology dependence 
Dedication constraint: The constraint of dedicated machine for a type
of task was used for the HSF by Riane et al. (2001),
Hung and Ching, (2003), Longmin
et al. (2007) and Dekhici and Belkadi (2008)
for the clothing workshop where it dedicates a special sewing machine to an
appointed task.
In present cases it assigns a patient to a special operating room (Eq. 14) or a special bed (Eq. 15) when the state is considered critical.
We note: dedi,k as integer and a default value 1.
For example if a patient p_{i} which is a biologic danger must be assigned
to bed y in stage 2 we note: ded_{pi}, 2 = y and if a patient pi must
be assigned to an efficient operating room z in stage 1, we note: ded_{pi},1
= z.
Technology dependence: The technology dependence constraint was defined
by Vignier et al. (1999) for the HFS with k stages
and a same number of machine l in each stage HFSK,M(l),M(l)….M(l)C_{max
}as follow:
For all job i, if j is the machine assigned to the job i in the stage k (v_{i,k
}according to Vignier Notation), then the machine assigned to i in the
stage k+1 must be the jth machine in this stage.
This definition was modified in (Dekhici and Belkadi, 2008).
We define the technology dependence for some OR only. If a patient goes to the
operating room j, he must go to the bed j’ (Eq. 17).
We note: Tec_{j}= j’ as integer and a default value is 1.
As example let propose that every patient who goes to the cardiac OR must go
to an intensive care bed.
New notation: After submitting the habituel problem to constraints, we get a new problem: HFS2,M(l1), M(l2)t,tr,d,f,dmax,dmin;block,prec,prio,tec,ded, noseq C_{max}.
Possible conflict: In manufacturing systems, assignment constraints
may contradict (Dekhici and Belkadi, 2008). An expert
confirms that in Hospital Systems, they are complementary and that only order
constraints can disrupt planning.
Example: ded_{pi},1 = x and ded_{pi}, 2 = y and Tec_{x} = z. So, both of the assignment of the room x and the bed y and the assignment of the room x and the bed z are refused.
RESOLUTION
We have presented earlier the notation of operating theatre scheduling under constraint. And we can identify that there are two problems: How to give a which satisfies constraint and how to minimize the C_{max} of operating procedure in one day. We propose two essential algorithms (Fig. 3).

Fig. 3: 
Notation and Methods used in the problem resolution 
The first one solves a Maximal Constraint Satisfaction problem (MCS) in order
to give a feasible schedule and the second one solves a scheduling problem to
give an optimal schedule.
Constraint satisfaction in the initial schedule: For the dependence technology and the dedication constraints, a simple check is sufficient given priority to dedication one, if ever a bad manipulation has led a conflict.
To find an initial feasible order, we implement an algorithm for Maximal Constraints Satisfaction (MCS) with a local search or minconflicts. One of the advantage of the minconflicts is that its runtime is roughly independent of the problem size.
The MCS problems consist either of the optimization of the constraints violated number or the optimization of the inconsistency cost. After a discussion with experts at EHUO, we admit that constraints have not the same importances in the planning. So, we choose the second criterion.
To evaluate the inconsistency cost, we first sort order constraints per importance
and we give a coefficient for each one according to our study:
• 
Temporal localization, coeff. = 4 
• 
Unitary precedence, coeff. = 3 
• 
No sequencing constraint, coeff. = 2 
• 
Priorities, coeff. = 1 
Our MCS can be formulated as a triple (X,D,C), where X is a set of variables
which are the patients pi, D is a domain of values which is the schedule and
C is a set of constraints. Every constraint is in turn a pair (T,R) where, T
is a tuple of variables and R is a set of relations.
X 
= 
{p_{i}/i=1..N} scheduling of patients. 
Di 
= 
[1…N], i=1..N. 
C 
= 
(T,R):the set of the order constraints. It contains the relations of priorities(X,Prio(p_{i1},p_{i2},p_{i3},….))
, of unitary precedence ((i1,i2),prec(i1,i2)), of no sequencing ((i1,i2),noseq(i1,i2))
, of temporal localization (i,dmax(i))and no equality of the variables (Eq.
18): 
With this last constraint, we can deduce that we cannot talk about a reselection
of a new value for a variable from X without talking about a permutation between
two values.
We admit that priorities can be erased by other order constraints as the no
sequencing constraint. All the constraints are soft. Present algorithm (algorithm
1) uses local search to check for conflicts and to select assignments that minimize
conflict with other variables.
Algorithm 1: 

Where Cost (P,csp) is a function that calculates the number of constraints violated multiplied by theirs coefficients in an assignment P.
The generation of a feasible schedule is in algorithm 2 and follows the steps
below:
• 
Generate a feasible sequence of the patients with min conflict 
• 
Generate a feasible assignment to either ORs or Beds with totally respect
of dedication and technology dependence constraints 
Algorithm 2: 

Optimization schedule: In order to provide an efficient schedule within
a very reasonable time, we use a Tabu Search (TS) method (Glover
and Laguna, 1997). The performance of the Tabu Search algorithm for the
HFS2C_{max} was analyzed from the computational point of view. It
gave good results with the size of the Tabu list fixed to 7, the candidate list
to 500 and iterations number to 1000 (Belkadi et al.,
2006; Sahraoui et al., 2003).
The algorithm 3 shows the adaptation of this search to our case. Details can
be found by Belkadi et al. (2006).
Algorithm 3: 

We study on 6 types of neighbor as the permutation of order, of assignment,
the insertion etc. A restricted neighborhood system (Baptiste
et al., 2001) must satisfy all constraints. An example of a neighbor
is given in algorithm 4.
Algorithm 4: 

Where choice_neighborhood( ) is a function for reselection a of another type of neighborhood.
RESULTS AND DISCUSSION
Data used in Experimentations are extracted from an implemented database. We supply the database from the history of the multidisciplinary Operating theatre of the EHUO. This center opens at 8 am and the operating theatre comprises 3 ORs and 9 beds in PACU and 2 beds in ICU dedicated to critical cases. The daily number of surgeries performed is less than 10.
First, we decrease number of beds to only 4 to give a simple example of a bad sized operating theatre under constraint.
Input data: N = 5 Patients noted A,B,…E. L_{1}=3 ORs (the first ordinary, the second dedicated to cardiac state and the third has high strelity). L_{2}=4 Beds in PACU(the latest is for Intensive Care).The Execution times are shown in Table 2.
Constraints:
Ded_{D,1} 
= 
2 (patient D must go to the cardiac OR) 
Ded_{D,2} 
= 
4 (patient D must go to the Intensive Care bed) 
Noseq_{D,E} 
= 
1 
Feasible schedule: A run without optimization give the solution below:
abdce, 12212 and 12441. Assignment to OR, to PACU and dates of beginning and
ending of process in both OR and PACU are shown in Table 3.
Table 2: 
Operating and reweaking times 

Table 3: 
Allocation schedule of the example 


Fig. 4: 
Gantt diagram of the feasible solution of the example 
As an example , Patient D has the third order. He is assigned to the second
OR and the fourth bed in PACU. His surgery begins at 8.5 a clock, finishes at
11.5 a clock. He lives the PACU at 16.5 a clock. The makespan is calculated
with the max of f_{pi,2 }date of departure from PACU and the min of
d_{pi,1 } date of beginning to OR. C_{max} =21.508=13.5 (h).
We validate result with a Gantt diagram (Fig. 4) which highlights the resources occupation and demonstrates the feasibility of scheduling.
An optimization give a better schedule (bdcae,12311,24312) with a C_{max} = 11,5 h and the Gantt diagram of Fig. 5.
Some results of experimentation done on the existing database are in Table 4.
The aim was to define constraints of surgeries scheduling. We have submitted
an operating theatre scheduler to many constraints that we had token from reality.
For resolution we proposed for C_{max} scheduling a Tabu search which
is already known well in this area and local search for constraints satisfaction
problem. Results of many Fictive examples of bad sized operating theaters and
real examples from the multidisciplinary surgeries or constraints increase,
shown the capacity of algorithms to give a good rates of criteria amelioration.
Table 4: 
Examples of Amelioration rates for (N=4..10, l_{1}=2..3,
l_{2}=2..9, constraints number =0..6) 


Fig. 5: 
Gantt diagram of the optimal solution of the example 
In its practical aspect, the advantage of our algorithms is that they could
give computerized feasible optimal schedule of 10 surgeries in less than 14.3
seconds where a simple feasible handmade could take 5 days.
CONCLUSION
We presented manufacturing constraints accustomed to the Operating theatre scheduling. The aim was to present the problem of surgeries scheduling differently in its real image, by adding these constraints. In order to give a satisfactory schedule, we implemente a local search for Maximal Constraints Satisfaction. Tabu Search was used to optimize the Cmax. We envision the use of several other meta heuristics and parallel versions of these metaheuristics in order to choose the best method.