Abstract
The benefits of automating the nurse scheduling process in hospitals include reducing the planning workload and associated costs and being able to create higher quality and more flexible schedules. This has become more important recently in order to retain nurses and to attract more people into the profession. Better quality rosters also reduce fatigue and stress due to overwork and poor scheduling and help to maximise the use of leisure time by satisfying more requests. A more contented workforce will lead to higher productivity, increased quality of patient service and a better level of healthcare. This paper presents a scatter search approach for the problem of automatically creating nurse rosters. Scatter search is an evolutionary algorithm, which has been successfully applied across a number of problem domains. To adapt and apply scatter search to nurse rostering, it was necessary to develop novel implementations of some of scatter search's subroutines. The algorithm was then tested on publicly available real-world benchmark instances and compared against previously published approaches. The results show the proposed algorithm is a robust and effective method on a wide variety of real-world instances.
Similar content being viewed by others
References
Aickelin U, Burke EK and Li J (2007). An estimation of distribution algorithm with intelligent local search for rule-based nurse rostering. J Opl Res Soc 58: 1574–1585.
Aickelin U and Dowsland KA (2000). Exploiting problem structure in a genetic algorithm approach to a nurse rostering problem. J Sched 3: 139–153.
Aickelin U and Dowsland KA (2003). An indirect genetic algorithm for a nurse scheduling problem. Comput Oper Res 31: 761–778.
Bard JF and Purnomo HW (2005). Preference scheduling for nurses using column generation. Eur J Opl Res 164: 510–534.
Bard JF and Purnomo HW (2007). Cyclic preference scheduling of nurses using a Lagrangian-based heuristic. J Sched 10: 5–23.
Beddoe GR and Petrovic S (2006). Selecting and weighting features using a genetic algorithm in a case-based reasoning approach to personnel rostering. Eur J Opl Res 175: 649–671.
Beddoe GR and Petrovic S (2007). Enhancing case-based reasoning for personnel rostering with selected tabu search concepts. J Opl Res Soc 58: 1586–1598.
Bellanti F, Carello G, Croce FD and Tadei R (2004). A greedy-based neighborhood search approach to a nurse rostering problem. Eur J Opl Res 153: 28–40.
Brucker P, Burke EK, Curtois T, Qu R and Vanden Berghe G (2009). A shift sequence based approach for nurse scheduling and a new benchmark dataset. J Heuristics, available online, doi:10.1007/s10732-008-9099-6.
Burke EK, De Causmaecker P and Vanden Berghe G (1999). A hybrid tabu search algorithm for the nurse rostering problem . In: McKay B, Yao X, Newton CS, Kim J and Furuhashi T (eds). Simulated Evolution and Learning Selected Papers from the 2nd Asia-Pacific Conference on Simulated Evolution and Learning, SEAL 98. Springer Lecture Notes in Artificial Intelligence Vol. 1585. Springer-Verlag: London, UK, pp. 187–194.
Burke EK, Cowling P, De Causmaecker P and Vanden Berghe G (2001). A memetic approach to the nurse rostering problem . Appl Intell 15: 199–214.
Burke EK, Kendall G and Soubeiga E (2003). A tabu-search hyperheuristic for timetabling and rostering . J Heuristics 9: 451–470.
Burke EK, De Causmaecker P, Petrovic S and Vanden Berghe G (2004a). Variable neighborhood search for nurse rostering problems . In: Resende MGC and de Sousa JP (eds). Metaheuristics: Computer Decision-Making. Kluwer: Norwell, MA, USA, pp. 153–172.
Burke EK, De Causmaecker P, Vanden Berghe G and Van Landeghem H (2004b). The state of the art of nurse rostering . J Sched 7: 441–499.
Burke EK, Curtois T, Qu R, Vanden Berghe G (2007). A time predefined variable depth search for nurse rostering. Technical Report. School of Computer Science and IT, University of Nottingham.
Burke EK, Li J and Qu R (2008a). A hybrid model of integer programming and variable neighbourhood search for highly-constrained nurses rostering problems. Eur J Opl Res, accepted for publication.
Burke EK, Curtois T, Post G, Qu R and Veltman B (2008b). A hybrid heuristic ordering and variable neighbourhood search for the nurse rostering problem . Eur J Opl Res 188: 330–341.
Burke EK, Curtois T, Qu R, Vanden Berghe G (2009). Problem model for nurse rostering benchmark instances, http://www.cs.nott.ac.uk/~tec/NRP/papers/ANROM.pdf.
Campos V, Glover F, Laguna M and Martí R (2001). An experimental evaluation of a scatter search for the linear ordering problem. J Global Optim 21: 397–414.
Cung V-D, Mautor T, Michelon P and Tavares A (1997). A scatter search based approach for the quadratic assignment problem. In: Back T, Michalewicz Z and Yao X (eds). Proceedings of IEEE International Conference on Evolutionary Computation. IEEE Press: Piscataway, NJ, USA, pp. 165–169.
Dias TM, Ferber DF, deSouza CC and Moura AV (2003). Constructing nurse schedules at large hospitals. Int Trans Opl Res 10: 245–265.
Dowsland KA and Thompson JM (2000). Solving a nurse scheduling problem with knapsacks, networks and tabu search. J Opl Res Soc 51: 825–833.
Ernst AT, Jiang H, Krishnamoorthy M, Owens B and Sier D (2004a). An annotated bibliography of personnel scheduling and rostering. Ann Oper Res 127: 21–144.
Ernst AT, Jiang H, Krishnamoorthy M and Sier D (2004b). Staff scheduling and rostering: a review of applications, methods and models. Eur J Opl Res 153: 3–27.
Glover F (1998). A template for scatter search and path relinking. In: Hao JK, Lutton E, Ronald E, Schoenauer M and Snyers D (eds). Lecture Notes in Computer Science Vol. 1363. Springer-Verlag: London, UK, pp. 13–54.
Glover F, Laguna M and Martí R (2000a). Fundamentals of scatter search and path relinking. Control Cybern 29: 653–684.
Glover F, Laguna M and Martí R (2003). Scatter search. In: Ghosh A and Tsutsui S (eds). Advances in Evolutionary Computing. Springer-Verlag: Berlin, Heidelberg, pp. 519–539.
Glover F, Løkketangen A and Woodruff DL (2000b). Scatter search to generate diverse MIP solutions. In: Laguna M and González-Velarde JL (eds). OR Computing Tools for Modeling, Optimization and Simulation: Interfaces in Computer Science and Operations Research. Kluwer: Norwell, MA, USA, pp. 299–317.
Greistorfer P (2003). A tabu scatter search metaheuristic for the arc routing problem. Comp Ind Eng 44: 249–266.
Jan A, Yamamoto M and Ohuchi A (2000). Evolutionary algorithms for nurse scheduling problem. In:Proceedings of the 2000 Congress on Evolutionary Computation. IEEE Press: Piscataway, NJ, USA, pp. 196–203.
Jaszkiewicz A (1997). A metaheuristic approach to multiple objective nurse scheduling. Found Comput Decis Sci 22: 169–183.
Jaumard B, Semet F and Vovor T (1998). A generalized linear programming model for nurse scheduling. Eur J Opl Res 107: 1–18.
Laguna M and Martí R (2003). Scatter Search. Methodology and Implementation in C. Kluwer Academic Publishers: Norwell, MA, USA.
Lourenço H, Laguna M and Martí R (2000). Assigning proctors to exams with scatter search. In: Laguna M and González-Velarde JL (eds). Computing Tools for Modeling, Optimization and Simulation. Kluwer: Norwell, MA, USA, pp. 215–228.
Maenhout B and Vanhoucke M (2006). New computational results for the nurse scheduling problem: a scatter search algorithm. In: Gottlieb J and Raidl GR (eds). Proceedings of the 6th European Conference on Evolutionary Computation in Combinatorial Optimization (EvoCOP 2006), Lecture Notes in Computer Science, Vol. 3906, Budapest, Hungary. Springer: Berlin, Heidelberg, pp. 159–170.
Meisels A and Schaerf A (2003). Modelling and solving employee timetabling problems. Ann Math Artif Intel 39: 41–59.
Meyer auf'm Hofe H (2000). Solving rostering tasks as constraint optimization. In: Burke EK and Erben W (eds). Selected papers from the Third International Conference on Practice and Theory of Automated Timetabling, Springer Lecture Notes in Computer Science Vol. 2079. Springer-Verlag: Berlin, Heidelberg, pp. 191–212.
Thornton J and Sattar A (1997). Nurse rostering and integer programming revisited. In: Verma B and Yao X (eds). International Conference on Computational Intelligence and Multimedia Applications. Griffith University: Gold Coast, Australia, pp. 49–58.
Acknowledgements
This work was supported by EPSRC grant GR/S31150/01.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Burke, E., Curtois, T., Qu, R. et al. A scatter search methodology for the nurse rostering problem. J Oper Res Soc 61, 1667–1679 (2010). https://doi.org/10.1057/jors.2009.118
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2009.118