Skip to main content
SpringerLink
Log in

A shift sequence based approach for nurse scheduling and a new benchmark dataset

  • Published:
Journal of Heuristics Aims and scope Submit manuscript

Abstract

This paper investigates an adaptive constructive method for solving nurse rostering problems. The constraints considered in the problems are categorised into three classes: those that are sequence related, those that are nurse schedule related and those that are roster related. We propose a decomposition approach (to construct solutions) that consists of two stages: (1) to construct high quality sequences for nurses by only considering the sequence constraints, and (2) to iteratively construct schedules for nurses and the overall rosters, based on the sequences built and considering the schedule and roster constraints. In the second stage of the schedule construction, nurses are ordered and selected adaptively according to the quality of the schedules they were assigned to in the last iteration. Greedy local search is carried out during and after the roster construction, in order to improve the (partial) rosters built. We show that the local search heuristic during the roster construction can further improve the constructed solutions for the benchmark problems tested.

In addition, we introduce new benchmark nurse rostering datasets which are based upon real world data. The data sets represent a variety of real world constraints. The publication of this problem data to the research community is aimed at closing the gap between theory and practice in nurse scheduling research. One of the main objectives is to encourage more research on these data sets.

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

Access this article

Log in via an institution

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

  • Adbennadher, S., Schlenker, H.: Nurse scheduling using constraint logic programming. In: Eleventh Annual Conference on Innovative Applications of Artificial Intelligence, IAAI-99, pp. 838–843, July 1999, Orlando, Florida, USA

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

    Article  MATH  MathSciNet  Google Scholar 

  • Aickelin, U., Dowsland, K.: An indirect genetic algorithm for a nurse scheduling problem. J. Oper. Res. Soc. 31(5), 761–778 (2003)

    Google Scholar 

  • Aickelin, U., Li, J.: An estimation of distribution algorithm for nurse scheduling. Ann. Oper. Res. 155(1), 289–309 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  • Bard, J., Purnomo, H.W.: Preference scheduling for nurses using column generation. Eur. J. Oper. Res. 164, 510–534 (2005)

    Article  MATH  Google Scholar 

  • Bard, J., Purnomo, H.W.: Cyclic preference scheduling of nurses using a Lagrangian-based heuristic. J. Sched. 10(1), 5–23 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  • Beaumont, N.: Scheduling staff using mixed integer programming. Eur. J. Oper. Res. 98, 473–484 (1997)

    Article  MATH  Google Scholar 

  • Beddoe, G., Petrovic, S.: Determining feature weights using a genetic algorithm in a case-based reasoning approach to personnel rostering. Eur. J. Oper. Res. 175, 649–671 (2006)

    Article  MATH  Google Scholar 

  • Brusco, M.J., Jacobs, L.W.: Cost analysis of alternative formulations for personnel scheduling in continuously operating organisations. Eur. J. Oper. Res. 86, 249–261 (1995)

    Article  MATH  Google Scholar 

  • Brucker, P., Qu, R., Burke, E.K., Post, G.: A decomposition, construction and post-processing approach for a specific nurse rostering problem. In: Kendall, G., Lei, L., Pinedo, M. (eds.) Proceeding of the 2nd Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA’05), pp. 397–406, New York, USA, July 2005

  • Burke, E.K., De Causmaecker, P., Vanden Berghe, G.: A hybrid tabu search algorithm for the nurse rostering problem. In: Selected Papers from the 2nd Asia Pacific Conference on Simulated Evolution and Learning (SEAL’98). Lecture Notes in Artificial Intelligence, vol. 1585, pp. 187–194. Springer, Berlin (1999)

    Google Scholar 

  • Burke, E.K., Cowling, P., De Causmaecker, P., Vanden Berghe, G.: A memetic approach to the nurse rostering problem. Appl. Intell. 15, 119–214 (2001)

    Article  Google Scholar 

  • Burke, E.K., Hart, E., Kendall, G., Newall, J., Ross, P., Schulenburg, S.: Hyperheuristics: an emerging direction in modern search technology. In: Glover, F., Kochenberger, G. (eds.) Handbook of Meta-heuristics, pp. 457–474. Kluwer, Dordrecht (2003a)

    Google Scholar 

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

    Article  Google Scholar 

  • Burke, E.K., De Causmaecker, P., Petrovic, S., Vanden Berghe, G.: Variable neighborhood search for nurse rostering problems. In: Resende, M.G.C., Pinho de Sousa, J.P. (eds.) Metaheuristics: Computer Decision-Making. Combinatorial Optimization Book Series, pp. 153–172. Kluwer, Dordrecht (2004a). Chapter 7

    Google Scholar 

  • Burke, E.K., De Causmaecker, P., Vanden Berghe, G.: Novel meta-heuristic approaches to nurse rostering problems in Belgian hospitals. In: Leung, J. (ed.) Handbook of Scheduling: Algorithms, Models and Performance Analysis, pp. 44.1–44.18. CRC Press, Boca Raton (2004b). Chapter 44

    Google Scholar 

  • Burke, E.K., De Causmaecker, P., Vanden Berghe, G., Van Landeghem, H.: The state of the art of nurse rostering. J. Sched. 7(6), 441–499 (2004c)

    Article  MATH  MathSciNet  Google Scholar 

  • Burke, E.K., Curtois, T., Post, G., Qu, R., Veltman, B.: A hybrid heuristic ordering and variable neighbourhood search for the nurse rostering problem. Eur. J. Oper. Res. 2, 330–341 (2008)

    Article  Google Scholar 

  • Chen, J.G., Yeung, T.: Hybrid expert system approach to nurse scheduling. Comput. Nursing 11(4), 183–192 (1993)

    Google Scholar 

  • Dowsland, K.: Nurse scheduling with tabu search and strategic oscillation. Eur. J. Oper. Res. 106, 393–407 (1998)

    Article  MATH  Google Scholar 

  • Ernst, A.T., Jiang, H., Krishnamoorthy, M., Sier, D.: Staff scheduling and rostering: a review of applications, methods and models. Eur. J. Oper. Res. 153, 3–27 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  • Ikegami, A., Niwa, A.: A subproblem-centric model and approach to the nurse scheduling problem. Math. Program. 97(3), 517–541 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  • Jan, A., Yamamoto, M., Ohuchi, A.: Evolutionary algorithms for nurse scheduling problem. In: Proceedings of the 2000 Congress on Evolutionary Computation (CEC’00), pp. 196–203, San Diego, USA, 2000

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

    MATH  Google Scholar 

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

    Article  MATH  Google Scholar 

  • Mason, A., Smith, M.: A nested column generator for solving rostering problems with integer programming. In: Caccetta, L., Teo, K.L., Siew, P.F., Leung, Y.H., Jennings, L.S., Rehbock, V. (eds.) Proceedings of the 4th International Conference on Optimisation: Techniques and Applications, pp. 827–834. July 1998, Perth, Australia

  • Meisels, A., Gudes, E., Solotorevsky, G.: Employee timetabling, constraint networks and knowledge-based rules: a mixed approach. In: Burke, E.K., Ross, P. (eds.) Selected Papers from the 1st International Conference on Practice and Theory of Automated Timetabling. Lecture Notes in Computer Science, vol. 1153, pp. 93–105. Springer, Berlin (1996)

    Google Scholar 

  • Meyer auf’m Hofe, H.: Solving rostering tasks as constraint optimisation. In: Burke, E.K., Erben, W. (eds.) Selected Papers from the 3rd International Conference on Practice and Theory of Automated Timetabling. Lecture Notes in Computer Science, vol. 2079, pp. 280–297. Springer, Berlin (2000)

    Google Scholar 

  • Millar, H.H., Kiragu, M.: Cyclic and non-cyclic scheduling of 12h shift nurses by network programming. Eur. J. Oper. Res. 104, 582–592 (1998)

    Article  MATH  Google Scholar 

  • Petrovic, S., Beddoe, G., Vanden Berghe, G.: Storing and adapting repair experiences in personnel rostering. In: Burke, E.K., De Causmaecker, P. (eds.) Selected Papers from the 4th International Conference on Practice and Theory of Automated Timetabling. Lecture Notes in Computer Science, vol. 2740, pp. 148–165. Springer, Berlin (2003)

    Google Scholar 

  • Pierskalla, W., Rath, G.: Nurse scheduling using mathematical programming. Oper. Res. 24(5), 857–870 (1976)

    Article  MATH  Google Scholar 

  • Post, G., Veltman, B., Harmonious personnel scheduling. In: Burke, E.K., Trick, M. (eds.) Proceedings of the 5th International Conference on the Practice and Automated Timetabling, pp. 557–559. August 2004, Pittsburgh, PA, USA

  • Scott, S., Simpson, R.M.: Case-based incorporating scheduling constraint dimensions: experiences in nurse rostering. In: Smyth, Cunningham (eds.) Advances in Case Based Reasoning. Lecture Notes in Artificial Intelligence, vol. 1488, pp. 392–401. Springer, Berlin (1998)

    Chapter  Google Scholar 

  • Sitompul, D., Randhawa, S.: Nurse rostering models: a state-of-the-art review. J. Soc. Health Syst. 2(1), 62–72 (1990)

    Google Scholar 

  • Valouxis, C., Housos, E.: Hybrid optimisation techniques for the workshift and rest assignment of nursing personnel. Artif. Intell. Med. 20, 155–175 (2000)

    Article  Google Scholar 

  • Warner, M., Keller, B., Martel, S.: Automated nurse scheduling. J. Soc. Health Syst. 2(2), 66–80 (1990)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Fachbereich Mathematik/Informatik, University of Osnabruck, Albrechtstr. 28, 49069, Osnabruck, Germany

    Peter Brucker

  2. Automated Scheduling, Optimisation and Planning (ASAP) Group, School of Computer Science, University of Nottingham, Nottingham, NG8 1BB, UK

    Edmund K. Burke, Tim Curtois & Rong Qu

  3. Information Technology, Engineering Department, KaHo St.-Lieven, 9000, Gent, Belgium

    Greet Vanden Berghe

  4. Department of Computer Science, K.U. Leuven campus Kortrijk, E. Sabbelaan 53, 8500, Kortrijk, Belgium

    Greet Vanden Berghe

Authors
  1. Peter Brucker
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Edmund K. Burke
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Tim Curtois
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Rong Qu
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Greet Vanden Berghe
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Rong Qu.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Brucker, P., Burke, E.K., Curtois, T. et al. A shift sequence based approach for nurse scheduling and a new benchmark dataset. J Heuristics 16, 559–573 (2010). https://doi.org/10.1007/s10732-008-9099-6

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10732-008-9099-6

Keywords

Search

Navigation