Adaptation of the Bee Colony Optimization to the Nurse Scheduling Problem

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, URAC-29 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.

1. 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 NP-hard 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 non-linear multi-objective 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.

2. 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 non-cyclical 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 non-cyclical schedules are proposed, three shifts of eight hours is considered in this work falls within the day ( 8:00

   1. 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:

      1. (step) k = 1

      2. Evaluate all possible step

      3. Choose a step

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

   [3]. Return all the bees in the hive, (not back)
   [4]. Evaluate the value of the objective function for each bee. [5]. Each bee decides according to a probability is to continue

   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 found

   Propose 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.

3. 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 meta-heuristics swarm intelligence. It consists of two alternating phases: the step forward and backwards (Lucic and Teodorovic 2003;

4. 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 Hotel-Dieu 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.

5. 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).

6. 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.

7. 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

1. 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)

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

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

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

5. Berrada,J.A.FerlandetP.Michelon, "A Multi-ob jective Approach for Nurse Scheduling with both Hard and Soft Constraints".Socio-Econ. Plann. Sci., 30, p. 183-193, (1996)

6. Berrada,J.A.FerlandetP.Michelon, "Multi-objective Models and Techniques for Nurse SchedulingProblem", Publication No. 907, Université de Montréal, Montréal, (1994).

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

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

9. 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

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

11. 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.

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

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

14. 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.

15. D. Karaboga, B. Akay, and C. Ozturk, Artificial bee colony (abc) opti-mization algorithm for training feed-forward neural networks, inProc. 4th MDAI, Berlin, Germany, 2007, pp. 318329.

16. 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.

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

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

19. 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.

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

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

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

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

24. M. Warner: Nurse Staffing, Scheduling, and Reallocation in the Hospital, Hospital & Health Services Administra-tion, 1976, 77-90.

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

26. 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.

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