 Open Access
 Total Downloads : 247
 Authors : Lahbib Zeroual, Mohammed Essaid Riffi, Belaid Ahiod
 Paper ID : IJERTV3IS20830
 Volume & Issue : Volume 03, Issue 02 (February 2014)
 Published (First Online): 26032014
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Adaptation of the Bee Colony Optimization to the Nurse Scheduling Problem
Lahbib Zeroual
Mathematics & Computer Science Dept LABOMATIC, faculty of sciences ChouaÃ¯bDoukkali El Jadida University Morocco
Mohammed Essaid Riffi Mathematics & Computer Science Dept LABOMATIC, faculty of sciences
ChouaÃ¯bDoukkali El Jadida University Morocco
BelaÃ¯d Ahiod
Computer Science Dept LRIT, URAC29 faculty of sciences
Mohammed V Agdal University Morocco
Abstract –In this paper, we applied a metaheuristic based on the adaptation of the Bee Colony Optimization (BCO) to the Nurse Scheduling Problem (NSP). The BCO algorithm is motivated by the strategy used by the honey bee in search food. BCO was successfully applied to different combinatorial problem optimization. That motivate to use BCO on real data to solve the NSP and to propose a good schedule taking in account the special demand of nurse. Performance was evaluated on real data from two main units of the hospital Hotel Dieu from Montreal.

INTRODUCTION
In the present work, we consider the Nurse Scheduling problem, abbreviated NSP (Burke et al. 2004b,Cheang et al. 2003). The problem NSP is known as a combinatorial optimization problem which attract many researchers to develop exact and metaheuristics methodes (M.Vanhoucke and B. Maenhout 2009). The NSP is to improve a schedule in satisfy multiple constraints that are sometimes contradictory, we can classify the constraints of rigid and soft. Rigid constraints must be met and not violated for a feasible schedule. Soft constraints must be satisfied to the extent possible (Z.Zhang and al. 2011). NSP is NPhard combinatorial optimization problem (Osogami and Imai, 2000). Therefore, the exact methods are passively efficient in terms of complexity. This requires meta heuristics to solve the NSP .In this paper we use real data from two main units of the hospital Hotel Dieu from Montreal, and for the mathematical model has arising from the nonlinear multiobjective mathematical programming proposed by Berrada in (Berrada and al. 1994, 1996).
In this work, we use Bee Colony optimization (BCO); Lucic and Teodorovic have recently presented BCO for solving combinatorial problems of transport (P. Lucic and D. Teodovic 2001, 2002, 2003). BCO was been applied to a variety of optimization problems and performed well and produced satisfactory results (S. C. Chin and al.2006, G. Markovic and al. 2007, D.
Teodorovic and M. Orco 2008, D. Pham and al. 2007, D. Pham and al. 2006, D. Karaboga and al. 2007, D. Karaboga and B. Basturk 2008).
The BCO uses the behavior of bees in search of food as an optimization algorithm for solving combinatorial optimization problems, the idea is to create artificial bee able to explore the search space to find a feasible solution. Bees share information solutions explored during the research process as a collaborative effort between swarm to find an optimal solution.
This paper is organized as follows: section two present nurse scheduling problem. Section 3 describes BCO algorithm. In section 4, we present an adaptation of the BCO to NSP. In section 5, we will prove the performance of the used approach on real instances. Finally, we conclude and give some perspectives of research.

THE NURSE SCHEDULING PROBLEM The NSP is to specify the working and leave days for
each nurse for each unit. The general objective of the schedule is to minimize costs violation of constraints, and maximize satisfaction special requests personal (Jaumard et al 1998. Berrada et al 1996. ). There are two types of schedules: cyclic, where each nurse chooses his or her weekly schedule from a set of predefined schedules (Rosenbloom and Goertzen 1987), and noncyclical where each nurse is assigned to a schedule that meets its intrinsic constraints. To satisfy the desires of nurses and to ensure more flexibility noncyclic schedules (Cheang et al. 2003) are used.
Nurse
Mon
Tue
wed
Thu
Fri
Sat
Sun
A
N
N
L
E
E
L
L
B
D
D
D
L
N
L
L
C
L
E
E
D
D
L
L
TABLE 1: NON CYCLICAL SCHEDULE EXAMPLE
D: Day, E: Evening, N: Night, L: Leave When shifts longer than 12 hours and the total number
of hours worked by nurses plan more than 40 hours per week, the percentage of errors made by the latter increases the stress and fatigue encountered during the program (Rogers and al . 2004). To ensure good working conditions noncyclical schedules are proposed, three shifts of eight hours is considered in this work falls within the day ( 8:00

to 4:00 p.m. ) , falls in the evening ( 4:00 p.m. to 0:00 ) and night shift ( 0:00 – 8:00 ) (B.Ahiod and al.1998).
The BCO algorithm can be described by the following:
Algorithm 1 : BCO algorithm
[1]. Initialisation: a blank solution is assigned to each bee. [2]. For each bee:
(step) k = 1

Evaluate all possible step

Choose a step

k = k +1 if (k N) then goto b

research with its own solution and become a recruiting bee or choose a solution among the best solutions.
[6]. For each follower, choose a new solution from recruiting. [7]. If the solutions are not complete, goto (2). [8]. Evaluate all options and find the best [9]. If stopping criterion is not satisfied, goto (2) [10]. See the best solution foundPropose a good schedule must satisfy a set of constraints
problem, rigid and soft constraints (Berrada et al. 1996). Rigid constraints are administrative requirements for weeks of work, weekly number of working days of nurses, thebalanceddistribution on
lackorsurpluspersonnelthroughout the weekand holidays. Soft constraints are wishes nursing regarding consecutive working days, daily request and holidays.


BCO ALGORITHM
Bee colony optimization proposed by Teodorovic and Lucic (2001, 2002, and 2003) is a metaheuristic algorithm to solve a variety of combinatorial optimization problems. The BCO is inspired by nature in search of food sources. The algorithm belongs to the group of metaheuristics swarm intelligence. It consists of two alternating phases: the step forward and backwards (Lucic and Teodorovic 2003;

ADAPTATION OF BCO TO NSP
To solve the NSP we propose an approach to build the solution in two steps. The first step is to distribute uniformly the lack or surplus on the weekend satisfy the daily demands of personnel, the choice of the nurse is random, the process stops when the workdays of each nurse is exhausted. The second step is an adaptation of the BCO algorithm to minimize violation of objective and satisfy special requests in the measurement do not violate the hard constraints, which brings us to achieve better quality solutions.
The hive consists of several bees. Each bee generates a feasible solution to the problem according to the proces of finding food. The bee begin to choose randomly a nurse follows it begins to affect his workdays following the formula of transition following:
Teodorovic and al 2006). In the step forward, bee explores all possible way forward from the current solution, different
, =
,
criteria are used to select the next step: logical reasoning (Teodorovic and Orco 2008) and the logit stochastic model (Markovic and al.2007), or according to a probability. In the
,
Equation 1
step backward, bee go back to the hive and begins the new phase of iteration. During this phase, all bees share the value of the objective function of the solution generated. Each bee
The parameters et determine the size of the arc fitness compared to the heuristic information ij, with ij equal :
decides following a probability he shares his solution or not. Bee with the best solution has more chance to share his solution. Each bee decide whether to continue the search
= 1
with its own solution or it will start the search with selected solutions.
Equation 2
Where NEj is the total number of employees who have worked on the day during the solution found in the previous iteration.
ij,n : Indicates the arc fitness associated with planning a day of work j of an employee i.
, , , , > 1
In the case of NSP that we are interested, we chose a
= , , ,
,
> 1
binary matrix representation in two dimensions. Is a matrix
ij ,n
, ,
,
,
= ( )with:
1 , , = 1
Equation 3
The parameter represents the probability of selecting a workday from untreated employee i in the day j.
represents preferably working days of the nurse i during the cycle.
, is a set that contains the days that the bee prefers to assign the nurse i to the transition n, as recommended by
, : Set of the days untreated for nurse in transition
Algorithm 2 : Adaptation of the BCO algorithm to NSP
[1]. Initialyse the parametres(,,) for all bees= 1;
= 5;
= 0 ;
, ;
: ; : ; :
[2]. for t=1 to tmax for k=1 to NB do
for i=1 to NE do
> 0 = 1,8
initializes (Bee)
Bee k the day of work j to nurse i with the probability.
= 1 1 , 1 14 0
Where,  denotes the cardinality of the set I of nurses in a given shift.
The actual data used in our tests are from the intensive care unit and the emergency unit of the HotelDieu Hospital in Montreal described in (B.Ahiod and al.1998). We are interested in the development of hourly nurses each shift in both units for a period of two weeks. We identify six categories of test problem corresponds to the above mentioned period we denote by 1 6 . Each category represents a shift (Day, Evening and Night) of the two units for the six periods. It follows 36 scheduling problems to develop. To facilitate interpretation of the results, we will use the classification described in (B.Ahiod and al.1998), after we compare our results with those obtained by the application of genetic algorithm in (B.Ahiod and al.1998) and those obtained by MOACO in (Yassine and al. 2013). To facilitate the evaluation of the quality of our solutions we will present some measurement obtained in (B.Ahiodet al.1998; Yassine et al. 2013).
The objectives considered in our tests are defined as follows:
1 :The lack or surplus staff should be distributed evenly on each week.
2 : The number of consecutive days shall not exceed a fixed
() =
number
3 : The number of consecutiveworking daysmust be at leastequal to
+ 6
= 1;
= 1
End if
2.
4 : The number of consecutive working days must be at least equal to two.
5 : The daily demand for personnel of the same substitution group must be satisfied.
End while End for.
End for.
for i=1 to NB do
Mark workday as discussed;
6 : Special requests for weekly holidays and / or days of work must be met
7 : The daily demand for staff every Monday and Friday should be satisfied.
The priority given to these objectives, selected for
Choose the best solution with the dance End for
for i=1 to NB do
update for the bee i End for.
End for.

NUMERICAL TESTS

CPUT :total execution time (in seconds) required by the algorithms.

Vmoy : Average violation of the given solution, described by :
= =1
testing is as follows:
1 > 6 > 7 > 4 > 2 > 3 > 5. It is important to note that except the goal should remain the first priority; all other objectives may even their priorities changed. This will cause other types of problems.
The performance of the adaptation of the algorithm BCO to NSP problem was evaluated according to certain criteria related to the quality of the solution (Berrada et al. 1994). Below some criteria:
p : number of selected target.
: Weight associated with the target with priority i.
: value of the objective with priority i.
: The ideal value of the objective of the priority i. obtained by minimizing this objective under rigid
constraints.
=1

% : Improvement percentage of the initial solution given by:

. (. )
% = .
In the following, we call any good solution with the lowest average violation (min Vmoy).


RESULTS
Recall that the effectiveness of the BCO algorithm is bound to choice of parameter values and which determine the extent of the arc of the fitness versus the heuristic information . This implies the best combination to choose from and are those that minimize the average violation of goals. So to choose the best value for and are fixed starts throwing multiple runs on the P1 problem of intensive care unit over the day.
Table 2 : VALUES OF THE PARAMETER
Execution
1
2
3
4
5
1
0.035
0.14
0.32
0.21
0.035
2
0.17
0.035
0.25
0.10
0.25
3
0.035
0.17
0.25
0.28
0.25
4
0.10
0.21
0.17
0.10
0.28
5
0.17
0.10
0.17
0.17
0.25
Average
0.10
0.13
0.23
0.17
0.21
Min(Av)
0.10
After analyze the result of table 1 we choose the value that minimize the average of violation that equal to 1.
Table 3 : NUMERIC VALUE OF THE PARAMETER
td>
0.035
Execution
1
2
3
4
5
1
0.035
0.035
0.10
0.25
0.10
2
0.17
0.035
0.10
0.035
3
0.035
0.21
0.10
0.42
0.035
4
0.10
0.10
0.25
0.035
0.10
5
0.17
0.035
0.035
0.17
0.035
Average
0.10
0.083
0.104
0.195
0.061
Min(Av)
0.061
After 5 executions we get the value 5 for like value that minimise the violation of the problem 4
Table 4 : RESULTS OF NIGHT SHIFT OF THE EMERGENCY UNIT
Category C1
Initial Solution
Final Solution
CPU
Vmoy
Vmoy
P1
0.57
0.10
48.12
P2
0.64
0.035
47.90
P3
0.78
0.035
51.63
P4
0.75
0.071
47.39
P5
0.78
0
53.32
P6
0.75
0
48.25
Average
0.71
0.040
49.43
Table 5 :RESULTS OF NIGHT SHIFT PROBLEM OF THE INTENSIVE CARE UNIT
Category C2
Initial Solution
Final Solution
CPU
Vmoy
Vmoy
P1
1.17
0.32
65
P2
1.07
0.17
67.90
P3
0.92
0.17
70
P4
1.32
0.5
67.39
P5
0.78
0.42
53.32
P6
1.03
0.25
58.25
Average
0.88
0.30
63.64
Table 6 : RESULTS OF EVENING SHIFT PROBLEM OF THE INTENSIVE CARE UNIT
Category C3
Initial Solution
Final Solution
CPU
Vmoy
Vmoy
P1
1.21
0.10
55
P2
1.03
0.10
66.86
P3
0.85
0.00
58.37
P4
0.89
0.13
61.33
P5
1
0.32
60.42
P6
0.92
0.39
52.63
Average
0.98
0.17
59.10
Table 7 : RESULTS OF DAY SHIFT PROBLEM OF THE INTENSIVE CARE UNIT
Category C4
Initial Solution
Final Solution
CPU
Vmoy
Vmoy
P1
1.14
0.035
59
P2
1.14
0.08
49.99
P3
0.64
0.02
52.13
P4
0.75
0.36
66.08
P5
1.07
0
47.82
P6
0.35
0
48.95
Average
0.84
0.082
53.99
Table 8 : RESULTS OF EVENING SHIFT PROBLEM OF THE EMERGENCY UNIT
Category C5
Initial Solution
Final Solution
CPU
Vmoy
Vmoy
P1
1.28
0.14
66.38
P2
0.85
0
62.74
P3
0.67
0
61.63
P4
0.21
0
62.77
P5
1
0
68.54
P6
0.42
0
64.89
Average
0.73
0.023
64.49
Table 9 : RESULTS OF DAY SHIFT PROBLEM OF THE EMERGENCY UNIT
Category C6
Initial Solution
Final Solution
CPU
Vmoy
Vmoy
P1
1.96
0.85
61.47
P2
1.17
0.17
63.17
P3
1.17
0.35
69.81
P4
1.57
0.53
69.71
P5
1.96
0.28
61.23
P6
1.39
0.42
65.46
Average
1.53
0.43
65.13
Table 10 : RESULTS OF BCO, MOAC AND GENETIC ALGORITHM
Cate gory
BCO
GA
MOACO
Initial. Sol
Final. Sol
%
Im
CPU
Initial. Sol
Final. Sol
%
Im
CPU
Initial. Sol
Final. Sol
%
Im
CP U
Vmoy
Vmoy
Vmoy
Vmoy
Vmoy
Vmoy
C1
0.71
0.040
94
49.43
1.53
0.07
96
49.81
0.25
0.011
96
48.7
4
C2
0.88
0.30
65
63.64
3.34
0.39
88
71.71
1.41
0.33
77
55.7
C3
0.98
0.17
82
59.10
3.31
0.32
90
87.26
1.68
0.31
82
60.0
7
C4
0.84
0.082
90
53.99
3.04
0.27
92
85.60
1.9
0.27
86
54.2
C5
0.73
0.023
96
64.49
3.17
0.34
90
98.8
2.43
0.33
86
66.1
3
C6
1.53
0.43
71
65.13
5.48
0.93
83
139.25
2.54
0.84
45
67
Fig 1: average violation of the initial solution
Figure one present the quality of the initial solution obtained by the BCO, GA and MOACO for the six categories. The figure prove that the BCO start with good quality solutions, that allow to generate solutions with best quality.
Fig 2: Average violation of the final solution
In this work, we present the first comparison of the BCO algorithm with Multi Objective Ant Colony Optimization (MOACO) and the Genetic Algorithm (GA) on the same data. The figure 1 and 2 present the solutions obtained by the three methods (BCO, MOACO and GA) and prove that the proposed method allows to generate solutions of good quality for instances of smaller sizes. However, it allows generating better quality solutions in less time than the other methods in largest instances. The quality of solutions obtained can be explained, by the diversification proposed in the algorithm, and the different concepts introduced in the algorithm. Every bee choose a solution of the one bee of the recruiting bees, and begins to explore the search space from the hive. Each step during the building of the solution is evaluated by the transition formula, which is based one side on the best solutions obtained in the previous iteration, and, in the other side is choose the step that improves the current.

CONCLUSION
In this paper, we propose an adaptation of BCO algorithm to the NSP problem. The parameters (Number of bees in colony, number of recruiters, number of followers, etc.) of the given algorithm are chosen experimentally. The algorithm benefit if the parameters are adjusted automatically. Apart from that, the algorithm performed well when compared with MOACO and GA. The quality of the solutions obtained in this paper encourage the further survey of the BCO algorithm on other combinatorial optimization problems.
REFERENCES

Burke, E.K., De Causmacker, P., Vanden Berghe, G., Van Landeghem, H.: The state of the art of nurse rostering. J. Sched. 7, 441499 (2004b)

Cheang, B.,H. Li,A. Lim and B. Rodrigues. Nurse rostering problems a bibliographic survey, Eur. J. Oper. Res. 151, 447460 (2003).

M. Vanhoucke, B. Maenhout, On the characterization and generation of nurse scheduling problem instances, European Journal of Operational Research 196, (2009).

Z.Zhang, Z.Hao, H.Huang : Hybrid SwarmBased Optimization Algorithm of GA&VNS for Nurse Scheduling Problem.Springer Verlag Berlin Heidelberg 2011.

Berrada,J.A.FerlandetP.Michelon, "A Multiob jective Approach for Nurse Scheduling with both Hard and Soft Constraints".SocioEcon. Plann. Sci., 30, p. 183193, (1996)

Berrada,J.A.FerlandetP.Michelon, "Multiobjective Models and Techniques for Nurse SchedulingProblem", Publication No. 907, UniversitÃ© de MontrÃ©al, MontrÃ©al, (1994).

Osogami, T., Imai, H., Classification of various neighbourhood operations for the nurse scheduling problem. Lecture Notes in Computer Science 1969, 7283 (2000).

P. Lucic and D. Teodorovic, Bee system: Modeling combinatorial optimization transportation engineering problems by swarm intelligence, in Proc. Preprints TRISTAN IV Triennial Symp. Transp. Anal., Sao Miguel, Azores Island, Portugal, 2001, pp. 441 445.

P. Lucic and D. Teodorovic, Transportation modeling: an artificial life approach. In Proceedings of the 14th IEEE International Conference on Tools with Artificial Intelligence. Washington, DC, 216223,2002

P. Lucic and D. Teodorovic, Computing with bees: Attacking complex transportation engineering problems, Int. J. Artif. Intell. Tools, vol. 12, pp. 375394, 2003.

S. C. Chin, H. L. Malcolm Yoke, I. S. Appa, and L. G. Kheng, A bee colony optimization algorithm to job shop scheduling, in Proc. 38thWSC, 2006, pp. 19541961.

D. Teodorovic and M. Orco, Mitigating traffic congestion: Solving the ridematching problem by bee colony optimization,Transp. Plan. Technol., vol. 31, no. 2, pp. 135152, 2008.

D. Pham, A. Afify, and E. Koc, Manufacturing cell formation using the bees algorithm, inProc. IPROMS, Cardiff, U.K., 2007.

D. Pham, A. Ghanbarzadeh, E. Ko, S. Otri, S. Rahim, and M. Zaidi,
The bees algorithmA novel tool for complex optimisation problems, in Proc. IPROMS Conf., 2006.

D. Karaboga, B. Akay, and C. Ozturk, Artificial bee colony (abc) optimization algorithm for training feedforward neural networks, inProc. 4th MDAI, Berlin, Germany, 2007, pp. 318329.

D. Karaboga and B. Basturk, On the performance of artificial bee colony (abc) algorithm,Appl. Soft Comput., vol. 8, no. 1, pp. 687 697, Jan. 2008.

Jaumard, B., Semet, F. and T. Vovor (1998). A generalized linear programming model for nurse scheduling, Eur. J. Oper. Res. 107, 1 18.

Rosenbloom, E.S. and N. F. Goertzen (1987).Cyclic nurse scheduling, Eur. J. Oper. Res., 31, 1923.

Rogers, A. E., Hwang, W.T., Scott, L. D., Aiken, L. H. and Dinges,
D. F. (2004). The working hours of hospital staff nurses and patient safety, Health Affairs 23: 202212.

G. Markovic, D. Teodorovic, and V. AcimovicRaspopovic, Rout ing and wavelength assignment in alloptical networks based on the bee colony optimization,AI Commun., vol. 20, no. 4, pp. 273285, 2007.

D. Bradley, J. Martin: Continuous Personnel Scheduling Algorithms: A Literature Review, Journal of the Society of Health Systems 2, 1990, 823.

S.P. Siferd, W.C. Benton: Workforce staffing and scheduling: Hospital nursing specific models, European Journal of Operational Research 60, 1992, 233246.

J. Tien, A. Kamiyama: On Manpower Scheduling Algorithms, Society for Industrial and Applied Mathematics, 1982, Vol 24, No 3, 275287.

M. Warner: Nurse Staffing, Scheduling, and Reallocation in the Hospital, Hospital & Health Services Administration, 1976, 7790.

D. Teodorovic, P. Lucic, G. Markovic, and M. Orco, Bee colony optimization: Principles and applications, inProc. 8th Sem. NEUREL, 2006, pp. 151156.

B. Ahiod, I. Berrada and I. Kassou, Deux MÃ©thodes de Recherche Locale pour RÃ©soudre un problÃ¨me dHoraire du Personnel Infirmier dans un Etablissement Hospitalier, InvestigacionOperativa 1998.

Y.Saji, M.EssaidRiffi and B.Ahiod, MultiObjective Ant Colony Optimization Algorithmto Solve a Nurse Scheduling Problem, International Journal of Advanced Research in Computer Science and Software Engineering, August – 2013, pp. 311320