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.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
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)
Aickelin, U., Dowsland, K.: An indirect genetic algorithm for a nurse scheduling problem. J. Oper. Res. Soc. 31(5), 761–778 (2003)
Aickelin, U., Li, J.: An estimation of distribution algorithm for nurse scheduling. Ann. Oper. Res. 155(1), 289–309 (2007)
Bard, J., Purnomo, H.W.: Preference scheduling for nurses using column generation. Eur. J. Oper. Res. 164, 510–534 (2005)
Bard, J., Purnomo, H.W.: Cyclic preference scheduling of nurses using a Lagrangian-based heuristic. J. Sched. 10(1), 5–23 (2007)
Beaumont, N.: Scheduling staff using mixed integer programming. Eur. J. Oper. Res. 98, 473–484 (1997)
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)
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)
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)
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)
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)
Burke, E.K., Kendall, G., Soubeiga, E.: A tabu-search hyperheuristic for timetabling and rostering. J. Heur. 9(6), 451–470 (2003b)
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
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
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)
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)
Chen, J.G., Yeung, T.: Hybrid expert system approach to nurse scheduling. Comput. Nursing 11(4), 183–192 (1993)
Dowsland, K.: Nurse scheduling with tabu search and strategic oscillation. Eur. J. Oper. Res. 106, 393–407 (1998)
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)
Ikegami, A., Niwa, A.: A subproblem-centric model and approach to the nurse scheduling problem. Math. Program. 97(3), 517–541 (2003)
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)
Jaumard, B., Semet, F., Vovor, T.: A generalized linear programming model for nurse scheduling. Eur. J. Oper. Res. 107, 1–8 (1998)
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)
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)
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)
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)
Pierskalla, W., Rath, G.: Nurse scheduling using mathematical programming. Oper. Res. 24(5), 857–870 (1976)
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)
Sitompul, D., Randhawa, S.: Nurse rostering models: a state-of-the-art review. J. Soc. Health Syst. 2(1), 62–72 (1990)
Valouxis, C., Housos, E.: Hybrid optimisation techniques for the workshift and rest assignment of nursing personnel. Artif. Intell. Med. 20, 155–175 (2000)
Warner, M., Keller, B., Martel, S.: Automated nurse scheduling. J. Soc. Health Syst. 2(2), 66–80 (1990)
Author information
Authors and Affiliations
Corresponding author
Rights 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
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10732-008-9099-6