Skip to main content
Log in

A scatter search methodology for the nurse rostering problem

  • Theoretical Paper
  • Published:
Journal of the Operational Research Society

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Figure 1
Figure 2
Figure 3
Figure 4
Figure 5
Figure 6
Figure 7
Figure 8
Figure 9

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.

    Article  Google Scholar 

  • Aickelin U and Dowsland KA (2000). Exploiting problem structure in a genetic algorithm approach to a nurse rostering problem. J Sched 3: 139–153.

    Article  Google Scholar 

  • Aickelin U and Dowsland KA (2003). An indirect genetic algorithm for a nurse scheduling problem. Comput Oper Res 31: 761–778.

    Article  Google Scholar 

  • Bard JF and Purnomo HW (2005). Preference scheduling for nurses using column generation. Eur J Opl Res 164: 510–534.

    Article  Google Scholar 

  • Bard JF and Purnomo HW (2007). Cyclic preference scheduling of nurses using a Lagrangian-based heuristic. J Sched 10: 5–23.

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Google Scholar 

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

    Article  Google Scholar 

  • Burke EK, Kendall G and Soubeiga E (2003). A tabu-search hyperheuristic for timetabling and rostering . J Heuristics 9: 451–470.

    Article  Google Scholar 

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

    Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Google Scholar 

  • Dias TM, Ferber DF, deSouza CC and Moura AV (2003). Constructing nurse schedules at large hospitals. Int Trans Opl Res 10: 245–265.

    Article  Google Scholar 

  • Dowsland KA and Thompson JM (2000). Solving a nurse scheduling problem with knapsacks, networks and tabu search. J Opl Res Soc 51: 825–833.

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Google Scholar 

  • Glover F, Laguna M and Martí R (2000a). Fundamentals of scatter search and path relinking. Control Cybern 29: 653–684.

    Google Scholar 

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

    Chapter  Google Scholar 

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

    Chapter  Google Scholar 

  • Greistorfer P (2003). A tabu scatter search metaheuristic for the arc routing problem. Comp Ind Eng 44: 249–266.

    Article  Google Scholar 

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

    Google Scholar 

  • Jaszkiewicz A (1997). A metaheuristic approach to multiple objective nurse scheduling. Found Comput Decis Sci 22: 169–183.

    Google Scholar 

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

    Article  Google Scholar 

  • Laguna M and Martí R (2003). Scatter Search. Methodology and Implementation in C. Kluwer Academic Publishers: Norwell, MA, USA.

    Book  Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

  • Meisels A and Schaerf A (2003). Modelling and solving employee timetabling problems. Ann Math Artif Intel 39: 41–59.

    Article  Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

Download references

Acknowledgements

This work was supported by EPSRC grant GR/S31150/01.

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to T Curtois.

Rights and permissions

Reprints 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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jors.2009.118

Keywords

Navigation