Skip to main content
Log in

A Memetic Approach to the Nurse Rostering Problem

  • Published:
Applied Intelligence Aims and scope Submit manuscript

Abstract

Constructing timetables of work for personnel in healthcare institutions is known to be a highly constrained and difficult problem to solve. In this paper, we discuss a commercial system, together with the model it uses, for this rostering problem. We show that tabu search heuristics can be made effective, particularly for obtaining reasonably good solutions quickly for smaller rostering problems. We discuss the robustness issues, which arise in practice, for tabu search heuristics. This paper introduces a range of new memetic approaches for the problem, which use a steepest descent improvement heuristic within a genetic algorithm framework. We provide empirical evidence to demonstrate the best features of a memetic algorithm for the rostering problem, particularly the nature of an effective recombination operator, and show that these memetic approaches can handle initialisation parameters and a range of instances more robustly than tabu search algorithms, at the expense of longer solution times. Having presented tabu search and memetic approaches (both with benefits and drawbacks) we finally present an algorithm that is a hybrid of both approaches. This technique produces better solutions than either of the earlier approaches and it is relatively unaffected by initialisation and parameter changes, combining some of the best features of each approach to create a hybrid which is greater than the sum of its component algorithms.

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

Similar content being viewed by others

References

  1. K. Dowsland, “Nurse scheduling with tabu search and strategic oscillation,” EJOR to appear.

  2. A. Meisels, E. Gudes, and G. Solotorevski, “Employee timetabling, constraint networks and knowledge-based rules: A mixed approach.” In Proc. Practice and Theory of Automated Timetabling, First International Conference Edinburgh, pp. 93-105, 1995.

  3. M. Okada, “Prolog-based system for nursing staff scheduling implemented on a personal computer,” Computers and Biomedical Research, vol. 21, pp. 53-63, 1988.

    Google Scholar 

  4. M. Okada, “An approach to the generalised nurse scheduling problem-Generation of a declarative program to represent institution-specific knowledge,” Computers and Biomedical Research, vol. 25, pp. 417-434, 1992.

    Google Scholar 

  5. H. Miller, W. Pierskalla, and G. Rath, “Nurse scheduling using mathematical programming,” Operations Research, vol. 24, pp. 857-870, 1976.

    Google Scholar 

  6. V.M. Trivedi and M.Warner, “A branch and bound algorithm for optimum allocation of float nurses,” Management Science, vol. 22, no. 9, pp. 972-981, 1976.

    Google Scholar 

  7. M.Warner, “Scheduling nursing personnel according to nursing preference: A mathematical programming approach,” Operations Research, vol. 24, pp. 842-856, 1976.

    Google Scholar 

  8. M.Warner and J. Prawda, “A mathematical programming model for scheduling nursing personnel in a hospital,” Management Science, vol. 19, pp. 411-422, 1972.

    Google Scholar 

  9. H. Meyer auf'm Hofe, “ConPlan/SIEDAplan, Personnel Assignment as a Problem of Hierarchical Constraint Satisfaction,” in Proc. PACT 97, pp. 257-271, 1997.

  10. E.K. Burke, P. De Causmaecker, and G. Vanden Berghe, “A hybrid tabu search algorithm for the nurse rostering problem,” in Proc. Second Asia-Pacific Conference on Simulated Evolution and Learning (SEAL'98) Springes Lecture Notes on AI, vol. 1585, pp. 186-194, 1998.

  11. P. Coppens, “Geautomatiseerde personeelsplanning bij het A.Z. Sint-Erasmus,” GET info, vol. 9, pp. 1-3, 1995.

    Google Scholar 

  12. E.K. Burke and J.P. Newall, “A multi-stage evolutionary algorithm for the timetable problem,” IEEE Transactions on Evolutionary Computation, vol. 3, no. 1, pp. 63-74, April 1999.

    Google Scholar 

  13. E.K. Burke and A.J. Smith, “Hybrid evolutionary techniques for the maintenance scheduling problem,” IEEE Transactions on Power Systems, vol. 15, no. 1, pp. 122-128, Feb. 2000.

    Google Scholar 

  14. E.K. Burke, J.P. Newall, and R.F. Weare, “Initialisation strategies and diversity in evolutionary timetabling,” Evolutionary Computation Journal (Special Issue on Scheduling), vol. 6, no. 1, pp. 81-103, 1998.

    Google Scholar 

  15. R.W. Cheng and M. Gen, “Parallel machine scheduling problems using memetic algorithms,” Computers & Industrial Engineering, vol. 33, no. 3-4, pp. 761-764, 1997.

    Google Scholar 

  16. P. Moscato and M.G. Norman, “A 'Memetic' appproach for the traveling salesman problem. Implementation of a computational ecology for combinatorial optimization on messagepassing systems,” in Parallel Computing and Transputer Applications, edited by M. Valero, E. Onate, M. Jane, J.L. Larriba, and B. Suarez, IOS Press: Amsterdam, pp. 187-194, 1992.

    Google Scholar 

  17. B. Paechter, A. Cumming, M.G. Norman, and H. Luchian, “Extensions to a memetic timetabling system,” in Practice and Theory of Automated Timetabling, edited by E.K. Burke and P. Ross, Springer Lecture Notes in Computer Science, vol. 1153, pp. 251-265, 1996.

  18. N.J. Radcliffe and P.D. Surry, “Formal memetic algorithms,” in Evolutionary Computing, edited by T. Fogarty, Springer Lecture Notes in Computer Science, vol. 865, pp. 250-263, 1994.

  19. W.J. Abernathy, N. Baloff, J.C. Hershey, and S. Wandel, “A three-stage manpower planning and scheduling model-A service-sector example,” Operations Research, vol. 22, pp. 693-711, 1973.

    Google Scholar 

  20. E.K. Burke, P. De Causmaecker, S. Petrovic, and G. Vanden Berghe, “Fitness evaluation for nurse scheduling problems,” in Proc. Congress on Evolutionary Computation 2001 (CEC 2001), IEEE Press, pp. 1139-1146, 2001. 214 Burke et al.

  21. R.D.T. Farmer and J. Emami, “Models for forecasting hospital bed requirements in the acute sector,” Journal of Epidemiology and Community Health, vol. 44, pp. 307-312, 1990.

    Google Scholar 

  22. P. Gemmel and P. Coppens, “Hospitalia, Tijdschrift verbond der Verzorgingsinstellingen (1996) in the acute sector,” Journal of Epidemiology and Community Health, vol. 44, pp. 307-312, 1990.

    Google Scholar 

  23. B. Paechter, A. Cumming, and H. Luchian, “The use of local search suggestion lists for improving the solution of timetable problems with evolutionary algorithms,” in Evolutionary Computation, edited by T. Fogarty, Springer Lecture Notes in Computer Science, vol. 993, pp. 86-93, 1995.

  24. A.P. Punnen, and Y.P. Aneja, “A tabu search algorithm for the resource-constrained assignment problem,” Journal of the Operational Research Society, vol. 44, pp. 214-220, 1995.

    Google Scholar 

  25. S. Vanderhaeghe, “Dienstroosters in de gezondheidszorg: ongezond?” Informatiedossier, Stichting Technologie Vlaanderen, 1998.

Download references

Author information

Authors and Affiliations

Authors

Rights and permissions

Reprints and permissions

About this article

Cite this article

Burke, E., Cowling, P., De Causmaecker, P. et al. A Memetic Approach to the Nurse Rostering Problem. Applied Intelligence 15, 199–214 (2001). https://doi.org/10.1023/A:1011291030731

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1011291030731

Navigation