Abstract
Nurse rostering is a complex task of practical relevance. Over the last years, researchers have been able to solve increasingly larger and more complex problems. In this paper, we describe the full procedure of running the First International Nurse Rostering Competition. The aim of the competition was to develop further interest in the area and to stimulate new solution approaches by bringing together researchers from different areas.
We describe the competition’s spirit and its rules, the problem description and evaluation of solutions. We also explain the selection process and the final results. In addition, we give a brief description of the algorithmic approaches undertaken by the participants. Finally, we discuss the lessons learned from the competition and future activities to undertake.
Similar content being viewed by others
References
Burke, E., De Causmaecker, P., Petrovic, S., & Vanden Berghe, G. (2001). Fitness evaluation for nurse scheduling problems. In Proceedings of the congress on evolutionary computation (CEC2001) (pp. 1139–1146). New York: IEEE Press.
Burke, E., De Causmaecker, P., Vanden Berghe, G., & Van Landeghem, H. (2004). The state of the art of nurse rostering. Journal of Scheduling, 7(6), 441–499.
Ernst, A. T., Jiang, H., Krishnamoorthy, M., & Sier, D. (2004). Staff scheduling and rostering: a review of applications, methods and models. European Journal of Operational Research, 153(1), 3–27. Timetabling and Rostering.
First international nurse rostering competition website. (2010). URL: http://www.kuleuven-kortrijk.be/nrpcompetition.
Haspeslagh, S., De Causmaecker, P., Stølevik, M., & Schaerf, A. (2010). First international nurse rostering competition 2010. Tech. rep., KULeuven Campus Kortrijk. http://www.kuleuven-kortrijk.be/codes/.
Ingolfsson, A., Campello, F., Wu, X., & Cabral, E. (2010). Combining integer programming and the randomization method to schedule employees. European Journal of Operational Research, 202(1), 153–163.
Karp, R. (1972). Reducibility among combinatorial problems. In R. Miller & J. Thatcher (Eds.), Complexity of computer computations (pp. 85–103). New York: Plenum.
Li, Y., & Kozan, E. (2009). Rostering ambulance services. In Industrial engineering and management society (pp. 795–801).
Maenhout, B., & Vanhoucke, M. (2010). A hybrid scatter search heuristic for personalized crew rostering in the airline industry. European Journal of Operational Research, 206(1), 155–167.
McCollum, B., Schaerf, A., Paechter, B., McMullan, P., Lewis, R., Parkes, A. J., Di Gaspero, L., Qu, R., & Burke, E. K. (2009). Setting the research agenda in automated timetabling: the second international timetabling competition. INFORMS Journal on Computing. doi:10.1287/ijoc.1090.0320.
Osogami, T., & Imai, H. (2000). Classification of various neighborhood operations for the nurse scheduling problem. Tech. rep. 135, The Institute of Statistical Mathematics.
Schaerf, A., & Di Gaspero, L. (2006). Measurability and reproducibility in timetabling research: state-of-the-art and discussion. In Proc. of the 6th int. conf. on the practice and theory of automated timetabling (PATAT-2006) (pp. 53–62).
Zolfaghari, S., Quan, V., El-Bouri, A., & Khashayardoust, M. (2009). Application of a genetic algorithm to staff scheduling in retail sector. International Journal of Industrial and Systems Engineering, 5(28), 20–47.
Author information
Authors and Affiliations
Corresponding author
Appendices
Appendix A: Unwanted patterns
An unwanted pattern is a sequence of assignments that a nurse does not want to work. We distinguish between patterns that are unwanted on specific days (e.g. a nurse does not want to work a night shift before a free weekend, a nurse wants to work on Friday before a working weekend, …) and patterns that are unwanted throughout the entire planning period (e.g. a nurse does not want to work a late shift before an early shift, …).
A pattern consists of a number of pattern entries X: [X]1…n . A pattern entry X can be one of the following:
-
ST: a specific shift type
-
W: any shift type on a day
-
F: free (no shift type) on a day
A pattern entry X can occur on any day in the scheduling period or on a specific day. For patterns on fixed days, one numbering is sufficient. The other patterns need multiple numberings (see Appendix C).
We introduce the following pattern types:
-
1.
{W,ST}−[F]2…n : Before a series of free days, it is prohibited to work either during the entire day or to work a specific shift type. E.g. an employee may not work a night shift before a free weekend.
-
2.
F−[W,ST]2…n : No free day can occur before working any of a number of consecutive days or shift types. E.g. if an employee works a shift in a weekend, the employee should also work on Friday.
-
3.
[ST]2…n : Unwanted shift type successions. E.g. Late-Early-Late, Night-Early, …
Appendix B: Formal description of constraints
In Table 13, we give a sample numbering for each constraint introduced in Sect. 4.1. More formal definitions of the numberings can be found in the technical report describing the competition (Haspeslagh et al. 2010). We consider a planning horizon of two weeks. There are three shift types: an early (E), late (L) and night (N) shift type. A weekend consists of three days: Friday, Saturday and Sunday. Table 14 shows the mapping between a numbering and the constraints it can represent. Note that some constraints require multiple numberings (see Appendix C).
Appendix C: Constraints with multiple numberings
Some constraints cannot be expressed using only one numbering. Mostly constraints that do not occur on fixed days, need multiple numberings. The number of numberings needed is equal to the length of the pattern. For example consider the unwanted pattern, L-E-L, of length 3 and a scheduling period of 7 days. Since the pattern can start on any day, we need 3 numberings to achieve this. An example is shown in Table 15.
Rights and permissions
About this article
Cite this article
Haspeslagh, S., De Causmaecker, P., Schaerf, A. et al. The first international nurse rostering competition 2010. Ann Oper Res 218, 221–236 (2014). https://doi.org/10.1007/s10479-012-1062-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-012-1062-0