×

A rotation-based branch-and-price approach for the nurse scheduling problem. (English) Zbl 1452.90223

Summary: In this paper, we describe an algorithm for the personalized nurse scheduling problem. We focus on the deterministic counterpart of the specific problem that has been described in the second international nurse rostering competition. One specificity of this version is that most constraints are soft, meaning that they can be violated at the price of a penalty. We model the problem as an integer program (IP) that we solve using a branch-and-price procedure. This model is, to the best of our knowledge, comparable to no other from the literature, since each column of the IP corresponds to a rotation, i.e., a sequence of consecutive worked days for a nurse. In contrast, classical models involve individual nurse schedules over the complete horizon. We tackle instances involving up to 120 nurses and 4 shifts over an 8-weeks horizon by embedding the branch-and-price in a large-neighborhood-search framework. Initial solutions of the large-neighborhood search are found by a rolling-horizon algorithm well-suited to the rotation model.

MSC:

90C10 Integer programming
49M27 Decomposition methods
90C90 Applications of mathematical programming
90C59 Approximation methods and heuristics in mathematical programming

Software:

NurseScheduler
PDFBibTeX XMLCite
Full Text: DOI HAL

References:

[1] Bard, JF; Purnomo, HW, Preference scheduling for nurses using column generation, Eur. J. Oper. Res., 164, 2, 510-534 (2005) · Zbl 1068.90053
[2] Barnhart, C.; Johnson, EL; Nemhauser, GL; Savelsbergh, MWP; Vance, PH, Branch-and-price: column generation for solving huge integer programs, Oper. Res., 46, 3, 316-329 (1998) · Zbl 0979.90092
[3] Beliën, J.; Demeulemeester, E., A branch-and-price approach for integrating nurse and surgery scheduling, Eur. J. Oper. Res., 189, 3, 652-668 (2008) · Zbl 1146.90404
[4] Boyer, V.; Gendron, B.; Rousseau, LM, A branch-and-price algorithm for the multi-activity multi-task shift scheduling problem, J. Sched., 17, 2, 185-197 (2014) · Zbl 1297.90032
[5] Braekers, K., Janssens, G.K.: Shortest route problem with soft time windows. In: Onggo, S., Kavicka, A. (eds.) The European Simulation and Modelling Conference, pp. 279-283 (2013)
[6] Burke, EK; Curtois, T., New approaches to nurse rostering benchmark instances, Eur. J. Oper. Res., 237, 1, 71-81 (2014) · Zbl 1304.90088
[7] Burke, EK; De Causmaecker, P.; Berghe, GV; Van Landeghem, H., The state of the art of nurse rostering, J. Sched., 7, 6, 441-499 (2004) · Zbl 1154.90422
[8] Ceschia, S.; Dang, N.; De Causmaecker, P.; Haspeslagh, S.; Schaerf, A., The second international nurse rostering competition, Ann. Oper. Res. (2018)
[9] Ceschia, S., Dang, N., De Causmaecker, P., Haspeslagh, S., Schaerf, A.: Solving the INRC-II nurse rostering problem by simulated annealing based on large-scale neighborhoods. In: Proceedings of the 12th International Conference on Practice and Theory of Automated Timetabling (PATAT-2018) (2018)
[10] Ceschia, S., Dang, N.T.T., De Causmaecker, P., Haspeslagh, S., Schaerf, A.: The second international nurse rostering competition. In: Proceedings of the 10th International Conference of the Practice and Theory of Automated Timetabling (PATAT-2014), pp. 554-556 (2014) · Zbl 1434.90077
[11] Cheang, B.; Li, H.; Lim, A.; Rodrigues, B., Nurse rostering problems—a bibliographic survey, Eur. J. Oper. Res., 151, 3, 447-460 (2003) · Zbl 1045.90027
[12] Desaulniers, G.; Desrosiers, J.; Solomon, MM, Column Generation (2006), Berlin: Springer, Berlin
[13] Dumas, Y.; Soumis, F.; Desrosiers, J., Optimizing the schedule for a fixed vehicle path with convex inconvenience costs, Transp. Sci., 24, 2, 145-152 (1990) · Zbl 0715.90066
[14] Frigge, M.; Hoaglin, DC; Iglewicz, B., Some implementations of the boxplot, Am. Stat., 43, 1, 50-54 (1989)
[15] Gamache, M.; Soumis, F.; Yu, G., A method for optimally solving the rostering problem, Operations Research in the Airline Industry, International Series in Operations Research and Management Science, Chapter 5, 124-157 (1998), New York: Springer, New York
[16] Gamache, M.; Soumis, F.; Marquis, G.; Desrosiers, J., A column generation approach for large-scale aircrew rostering problems, Oper. Res., 47, 2, 247-263 (1999) · Zbl 1041.90513
[17] Garcia, R.: Resource constrained shortest paths and extensions. Ph.D. Thesis, Georgia Institute of Technology, GA, USA (2009)
[18] Gérard, M.; Clautiaux, F.; Sadykov, R., Column generation based approaches for a tour scheduling problem with a multi-skill heterogeneous workforce, Eur. J. Oper. Res., 252, 3, 1019-1030 (2016) · Zbl 1346.90472
[19] Gomes, RA; Toffolo, TA; Santos, HG, Variable neighborhood search accelerated column generation for the nurse rostering problem, Electron. Notes Discret. Math., 58, 31-38 (2017) · Zbl 1390.90396
[20] Haspeslagh, S.; De Causmaecker, P.; Schaerf, A.; Stølevik, M., The first international nurse rostering competition 2010, Ann. Oper. Res., 218, 1, 221-236 (2014) · Zbl 1301.90036
[21] He, F.; Qu, R., A constraint programming based column generation approach to nurse rostering problems, Comput. Oper. Res., 39, 12, 3331-3343 (2012) · Zbl 1349.90351
[22] Irnich, S.; Desaulniers, G.; Desaulniers, G.; Desrosiers, J.; Solomon, MM, Shortest path problems with resource constraints, Column Generation, Chapter 2, 33-65 (2005), Boston: Springer, Boston · Zbl 1130.90315
[23] Jaumard, B.; Semet, F.; Vovor, T., A generalized linear programming model for nurse scheduling, Eur. J. Oper. Res., 107, 1, 1-18 (1998) · Zbl 0943.90032
[24] Kohl, N.; Karisch, SE, Airline crew rostering: problem types, modeling, and optimization, Ann. Oper. Res., 127, 1-4, 223-257 (2004) · Zbl 1087.90031
[25] Legrain, A., Rosat, S., Omer, J.: legraina/nursescheduler: static rostering (2019). 10.5281/zenodo.3460634
[26] Maenhout, B.; Vanhoucke, M., Branching strategies in a branch-and-price approach for a multiple objective nurse scheduling problem, J. Sched., 13, 1, 77-93 (2010) · Zbl 1185.90085
[27] Pisinger, D.; Ropke, S.; Gendreau, M.; Potvin, J-Y, Large neighborhood search, Handbook of Metaheuristics, 399-419 (2010), Boston: Springer, Boston
[28] Prescott-Gagnon, E.; Desaulniers, G.; Rousseau, LM, A branch-and-price-based large neighborhood search algorithm for the vehicle routing problem with time windows, Networks, 54, 4, 190-204 (2009) · Zbl 1206.90016
[29] Qurashi, AG; Taniguchi, E.; Yamada, T., Column generation-based heuristics for vehicle routing problem with soft time windows, J. East. Asia Soc. Trans. Stud., 8, 827-841 (2010)
[30] Qurashi, AG; Taniguchi, E.; Yamada, T., Exact solution for vehicle routing problem with soft time windows and dynamic travel time, Asian Trans. Stud., 2, 1, 48-63 (2012)
[31] Richalet, J.; Rault, A.; Testud, J.; Papon, J., Model predictive heuristic control: applications to industrial processes, Automatica, 14, 5, 413-428 (1978)
[32] Saddoune, M.; Desaulniers, G.; Soumis, F., Aircrew pairings with possible repetitions of the same flight number, Comput. Oper. Res., 40, 3, 805-814 (2013)
[33] Sadykov, R.; Vanderbeck, F.; Pessoa, A.; Tahiri, I.; Uchoa, E., Primal Heuristics for Branch-and-Price: the assets of diving methods, INFORMS J. Comput., 31, 251-267 (2018) · Zbl 07281710
[34] Santos, HG; Toffolo, TA; Gomes, RA; Ribas, S., Integer programming techniques for the nurse rostering problem, Ann. Oper. Res., 239, 1, 225-251 (2016) · Zbl 1336.90063
[35] Wickert, T.I., Santori, C.S., Buriol, L.S.: A fix-and-optimize VNS algorithm applied to the nurse rostering problem. In: Proceedings of the Sixth International Workshop on Model-based Metaheuristic (Matheuristics-2016), pp. 1-12 (2016)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.