First-order linear programming in a column generation-based heuristic approach to the nurse rostering problem. (English) Zbl 1458.90358
Summary: A heuristic method based on column generation is presented for the nurse rostering problem. The method differs significantly from an exact column generation approach or a branch and price algorithm because it performs an incomplete search which quickly produces good solutions but does not provide valid lower bounds. It is effective on large instances for which it has produced best known solutions on benchmark data instances. Several innovations were required to produce solutions for the largest instances within acceptable computation times. These include using a fast first-order linear programming solver based on the work of Chambolle and Pock to approximately solve the restricted master problem. A low-accuracy but fast, first-order linear programming method is shown to be an effective option for this master problem. The pricing problem is modelled as a resource constrained shortest path problem with a two-phase dynamic programming method. The model requires only two resources. This enables it to be solved efficiently. A commercial integer programming solver is also tested on the instances. The commercial solver was unable to produce solutions on the largest instances whereas the heuristic method was able to. It is also compared against the state-of-the-art, previously published methods on these instances. Analysis of the branching strategy developed is presented to provide further insights. All the source code for the algorithms presented has been made available on-line for reproducibility of results and to assist other researchers.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | Asta, S.; Özcan, E.; Curtois, T., A tensor based hyper-heuristic for nurse rostering, Knowl. Based Syst., 98, 185-199 (2016) |
| [2] | Barnhart, C.; Hane, C. A.; Vance, P. H., Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems, Oper Res., 48, 2, 318-326 (2000) |
| [3] | Beddoe, G.; Petrovic, S., Enhancing case-based reasoning for personnel rostering with selected tabu search concepts, J. Oper. Res. Soc., 58, 12, 1586-1598 (2007) |
| [4] | Beddoe, G.; Petrovic, S.; Li, J., A hybrid metaheuristic case-based reasoning system for nurse rostering, J. Schedul., 12, 2, 99 (2009) · Zbl 1180.90147 |
| [5] | Beddoe, G. R.; Petrovic, S., Selecting and weighting features using a genetic algorithm in a case-based reasoning approach to personnel rostering, Eur. J. Oper. Res., 175, 2, 649-671 (2006) · Zbl 1142.90393 |
| [6] | Bell, P.; Hay, G.; Liang, Y., A visual interactive decision support system for workforce (nurse) scheduling, INFOR, 24, 2, 134-145 (1986) |
| [7] | Bilgin, B.; De Causmaecker, P.; Rossie, B.; Vanden Berghe, G., Local search neighbourhoods for dealing with a novel nurse rostering model, Ann. Oper. Res., 194, 1, 33-57 (2012) · Zbl 1251.90116 |
| [8] | Brucker, P.; Burke, E. K.; Curtois, T.; Qu, R.; Vanden Berghe, G., A shift sequence based approach for nurse scheduling and a new benchmark dataset, J. Heurist., 16, 4, 559-573 (2010) · Zbl 1230.90121 |
| [9] | Burke, E. K.; Cowling, P.; De Causmaecker, P.; Vanden Berghe, G., A memetic approach to the nurse rostering problem, Applied intelligence, 15, 3, 199-214 (2001) · Zbl 0993.90506 |
| [10] | Burke, E. K.; Curtois, T., New approaches to nurse rostering benchmark instances, Eur. J. Oper. Res., 237, 1, 71-81 (2014) · Zbl 1304.90088 |
| [11] | 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., 188, 2, 330-341 (2008) · Zbl 1149.90346 |
| [12] | Burke, E. K.; Curtois, T.; Qu, R.; Berghe, G. V., A scatter search methodology for the nurse rostering problem, Journal of the Operational Research Society, 61, 11, 1667-1679 (2010) |
| [13] | Burke, E. K.; Curtois, T.; Qu, R.; Vanden Berghe, G., A time predefined variable depth search for nurse rostering, INFORMS J. Comput., 25, 3, 411-419 (2013) |
| [14] | Burke, E. K.; De Causmaecker, P.; Vanden Berghe, G.; Van Landeghem, H., The state of the art of nurse rostering, J. Schedul., 7, 6, 441-499 (2004) · Zbl 1154.90422 |
| [15] | Cai, X.; Li, K., A genetic algorithm for scheduling staff of mixed skills under multi-criteria, Eur. J. Oper. Res., 125, 2, 359-369 (2000) · Zbl 0952.90007 |
| [16] | Ceschia, S.; Dang, N.; De Causmaecker, P.; Haspeslagh, S.; Schaerf, A., The second international nurse rostering competition, Ann. Oper. Res., 274, 1-2, 171-186 (2019) · Zbl 1434.90077 |
| [17] | Chambolle, A.; Pock, T., A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math Imaging Vi.s, 40, 1, 120-145 (2011) · Zbl 1255.68217 |
| [18] | Chen, J.; Yeung, T. W., Hybrid expert-system approach to nurse scheduling., Comput. Nurs., 11, 4, 183-190 (1993) |
| [19] | Condat, L., A direct algorithm for 1-d total variation denoising, IEEE Signal Process. Lett., 20, 11, 1054-1057 (2013) |
| [20] | Darmoni, S. J.; Fajner, A.; Mahe, N.; Leforestier, A.; Vondracek, M.; Stelian, O.; Baldenweck, M., Horoplan: computer-assisted nurse scheduling using constraint-based programming., J. Soc Health Syst., 5, 1, 41-54 (1995) |
| [21] | Della Croce, F.; Salassa, F., A variable neighborhood search based matheuristic for nurse rostering problems, Ann. Oper. Res., 218, 1, 185-199 (2014) · Zbl 1301.90055 |
| [22] | Desaulniers, G.; Desrosiers, J.; Solomon, M. M., Column Generation, 5 (2006), Springer Science & Business Media |
| [23] | Dowsland, K. A., Nurse scheduling with tabu search and strategic oscillation, Eur. J. Oper. Res., 106, 2-3, 393-407 (1998) · Zbl 0991.90055 |
| [24] | Eveborn, P.; Rönnqvist, M., Scheduler-a system for staff planning, Ann. Oper. Res., 128, 1-4, 21-45 (2004) · Zbl 1056.90060 |
| [25] | Guennebaud, G., Jacob, B., et al., 2010. Eigen v3. http://eigen.tuxfamily.org. |
| [26] | Gurobi Optimization, L., Gurobi Optimizer Reference Manual (2018) |
| [27] | Hadwan, M.; Ayob, M.; Sabar, N. R.; Qu, R., A harmony search algorithm for nurse rostering problems, Inf. Sci., 233, 126-140 (2013) |
| [28] | Häne, C.; Heng, L.; Lee, G. H.; Fraundorfer, F.; Furgale, P.; Sattler, T.; Pollefeys, M., 3D visual perception for self-driving cars using a multi-camera system: calibration, mapping, localization, and obstacle detection, Image Vis Comput, 68, 14-27 (2017) |
| [29] | 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 |
| [30] | 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 |
| [31] | IBM, Cplex Optimizer Reference Manual (2018) |
| [32] | Ikegami, A.; Niwa, A., A subproblem-centric model and approach to the nurse scheduling problem, Math. Program, 97, 3, 517-541 (2003) · Zbl 1035.90029 |
| [33] | Inafune, J.; Watanabe, S.; Okudera, M., New approach combining branch and price with metaheuristics to solve nurse scheduling problem., JACIII, 21, 7, 1251-1261 (2017) |
| [34] | 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 |
| [35] | Liu, Z.; Liu, Z.; Zhu, Z.; Shen, Y.; Dong, J., Simulated annealing for a multi-level nurse rostering problem in hemodialysis service, Appl. Soft. Comput., 64, 148-160 (2018) |
| [36] | Lougee-Heimer, R., The common optimization interface for operations research: promoting open-source software in the operations research community, IBM J. Res. Dev., 47, 1, 57-66 (2003) |
| [37] | Lü, Z.; Hao, J.-K., Adaptive neighborhood search for nurse rostering, Eur J. Oper. Res., 218, 3, 865-876 (2012) |
| [38] | Lübbecke, M. E.; Desrosiers, J., Selected topics in column generation, Oper Res, 53, 6, 1007-1023 (2005) · Zbl 1165.90578 |
| [39] | Maenhout, B.; Vanhoucke, M., Branching strategies in a branch-and-price approach for a multiple objective nurse scheduling problem, J. Schedul., 13, 1, 77-93 (2010) · Zbl 1185.90085 |
| [40] | Mason, A. J.; Smith, M. C., A nested column generator for solving rostering problems with integer programming, International Conference on Optimisation: Techniques and Applications, 827-834 (1998), Curtin University of Technology Perth, Australia |
| [41] | Meisels, A.; Gudes, E.; Solotorevsky, G., Employee timetabling, constraint networks and knowledge-based rules: A mixed approach, International Conference on the Practice and Theory of Automated Timetabling, 91-105 (1995), Springer |
| [42] | Meisels, A.; Schaerf, A., Modelling and solving employee timetabling problems, Ann. Math. Artif. Intell., 39, 1-2, 41-59 (2003) · Zbl 1045.68124 |
| [43] | Millar, H. H.; Kiragu, M., Cyclic and non-cyclic scheduling of 12 h shift nurses by network programming, Eur. J. Oper. Res., 104, 3, 582-592 (1998) · Zbl 0955.90027 |
| [44] | Miller, H. E.; Pierskalla, W. P.; Rath, G. J., Nurse scheduling using mathematical programming, Oper. Res., 24, 5, 857-870 (1976) · Zbl 0337.90034 |
| [45] | Ochs, P.; Malik, J.; Brox, T., Segmentation of moving objects by long term video analysis, IEEE Trans. Pattern Anal. Mach. Intell., 36, 6, 1187-1200 (2014) |
| [46] | Petrovic, S.; Vanden Berghe, G., A comparison of two approaches to nurse rostering problems, Ann. Oper. Res., 194, 1, 365-384 (2012) · Zbl 1251.90176 |
| [47] | Pock, T.; Chambolle, A., Diagonal preconditioning for first order primal-dual algorithms in convex optimization, Computer Vision (ICCV), 2011 IEEE International Conference on, 1762-1769 (2011), IEEE |
| [48] | Qu, Yi; Curtois, Timothy, Solving the Multi-activity Shift Scheduling Problem using Variable Neighbourhood Search, Proceedings of the 9th International Conference on Operations Research and Enterprise Systems, 1, 227-232 (2020) |
| [49] | Rahimian, E.; Akartunalı, K.; Levine, J., A hybrid integer and constraint programming approach to solve nurse rostering problems, Comput. Oper. Res., 82, 83-94 (2017) · Zbl 1391.90362 |
| [50] | Rahimian, E.; Akartunalı, K.; Levine, J., A hybrid integer programming and variable neighbourhood search algorithm to solve nurse rostering problems, Eur J Oper Res, 258, 2, 411-423 (2017) · Zbl 1394.90300 |
| [51] | Ryan, D. M.; Foster, B. A., An integer programming approach to scheduling, Computer Scheduling of Public Transport Urban Passenger Vehicle and Crew Scheduling, 269-280 (1981), North-Holland |
| [52] | Santos, H. G.; Toffolo, T. A.; Gomes, R. A.; Ribas, S., Integer programming techniques for the nurse rostering problem, Ann. Oper. Res., 239, 1, 225-251 (2016) · Zbl 1336.90063 |
| [53] | Smet, P., Constraint reformulation for nurse rostering problems, PATAT 2018 Twelfth International Conference on the Practice and Theory of Automated Timetabling, Vienna, August, 69-80 (2018) |
| [54] | Smet, P.; Bilgin, B.; De Causmaecker, P.; Vanden Berghe, G., Modelling and evaluation issues in nurse rostering, Ann. Oper. Res., 218, 1, 303-326 (2014) · Zbl 1301.90042 |
| [55] | Smet, P.; De Causmaecker, P.; Bilgin, B.; Vanden Berghe, G., Nurse Rostering: A Complex Example of Personnel Scheduling with Perspectives, Automated Scheduling and Planning, 129-153 (2013), Springer |
| [56] | Smith, L. D.; Wiggins, A., A computer-based nurse scheduling system, Comput. Oper. Res., 4, 3, 195-212 (1977) |
| [57] | Thompson, G. M., A simulated-annealing heuristic for shift scheduling using non-continuously available employees, Comput. Oper. Res., 23, 3, 275-288 (1996) · Zbl 0855.90073 |
| [58] | Valouxis, C.; Gogos, C.; Goulas, G.; Alefragis, P.; Housos, E., A systematic two phase approach for the nurse rostering problem, Eur. J. Oper. Res., 219, 2, 425-433 (2012) · Zbl 1244.90104 |
| [59] | Vanhoucke, M.; Maenhout, B., On the characterization and generation of nurse scheduling problem instances, Eur. J. Oper. Res., 196, 2, 457-467 (2009) · Zbl 1163.90514 |
| [60] | Václavık, R.; Novák, A.; Šøucha, P.; Hanzálek, Z., Accelerating the branch-and-price algorithm using machine learning, Eur. J. Oper. Res., 271, 3, 1055-1069 (2018) · Zbl 1403.90372 |
| [61] | Warner, D. M., Scheduling nursing personnel according to nursing preference: a mathematical programming approach, Oper. Res., 24, 5, 842-856 (1976) · Zbl 0337.90033 |
| [62] | Warner, D. M.; Prawda, J., A mathematical programming model for scheduling nursing personnel in a hospital, Manage Sci., 19, 4-NaN-1, 411-422 (1972) · Zbl 0246.90022 |
| [63] | Weil, G.; Heus, K.; Francois, P.; Poujade, M., Constraint programming for nurse scheduling, IEEE Eng. Med. Biol. Mag., 14, 4, 417-422 (1995) |
| [64] | Wu, T.-H.; Yeh, J.-Y.; Lee, Y.-M., A particle swarm optimization approach with refinement procedure for nurse rostering problem, Comput. Oper. Res., 54, 52-63 (2015) · Zbl 1348.90659 |
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.
