A constraint programming based column generation approach to nurse rostering problems. (English) Zbl 1349.90351
Summary: This paper presents our investigations on a hybrid constraint programming based column generation (CP-CG) approach to nurse rostering problems. We present a complete model to formulate all the complex real-world constraints in several benchmark nurse rostering problems. The hybrid CP-CG approach is featured with not only the effective relaxation and optimality reasoning of linear programming but also the powerful expressiveness of constraint programming in modeling the complex logical constraints in nurse rostering problems. In solving the CP pricing subproblem, we propose two strategies to generate promising columns which contribute to the efficiency of the CG procedure. A Depth Bounded Discrepancy Search is employed to obtain diverse columns. A cost threshold is adaptively tightened based on the information collected during the search to generate columns of good quality. Computational experiments on a set of benchmark nurse rostering problems demonstrate a faster convergence by the two strategies and justify the effectiveness and efficiency of the hybrid CP-CG approach.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
column generation; constraint programming; heuristics; nurse rostering problems; schedulingReferences:
| [1] | Zurn P, Dolea C, Stilwell B. Nurse retention and recruitment: developing a motivated workforce. Global Nursing Review Initiative 2005;4: 1-31.; Zurn P, Dolea C, Stilwell B. Nurse retention and recruitment: developing a motivated workforce. Global Nursing Review Initiative 2005;4: 1-31. |
| [2] | Burke, E. K.; De Causmaecker, P.; Vanden Berghe, G.; Van Landeghem, H., The state of the art of nurse rostering, Journal of Scheduling, 7, 6, 441-499 (2004) · Zbl 1154.90422 |
| [3] | Brucker, P.; Qu, R.; Burke, E. K., Personnel scheduling: models and complexity, European Journal of Operational Research, 210, 3, 467-473 (2011) · Zbl 1213.90151 |
| [4] | Morris, J. G.; Showalter, M. J., Simple approaches to shift, days-off, and tour scheduling programs, Management Science, 29, 942-950 (1983) |
| [5] | Billionnet, A., Integer programming to schedule a hierarchical workforce with variable demands, European Journal of Operational Research, 114, 1, 105-114 (1999) · Zbl 0945.90019 |
| [6] | Beaumont, N., Scheduling staff using mixed integer programming, European Journal of Operational Research, 98, 3, 473-484 (1997) · Zbl 0930.90045 |
| [7] | Puchinger J, Raidl GR. Combining metaheuristics and exact algorithms in combinatorial optimization: a survey and classification. In: Mira J, Álvarez JR (eds.) Artificial intelligence and knowledge engineering applications: a bioinspired approach; Lecture Notes in Computer Science, vol. 3562, 2005. p. 113-124.; Puchinger J, Raidl GR. Combining metaheuristics and exact algorithms in combinatorial optimization: a survey and classification. In: Mira J, Álvarez JR (eds.) Artificial intelligence and knowledge engineering applications: a bioinspired approach; Lecture Notes in Computer Science, vol. 3562, 2005. p. 113-124. |
| [8] | Jaumard, B.; Semet, F.; Vovor, T., A generalized linear programming model for nurse scheduling, European Journal of Operational Research, 107, 1-18 (1998) · Zbl 0943.90032 |
| [9] | Bard, J. F.; Purnomo, H. W., Preference scheduling for nurses using column generation, European Journal of Operational Research, 164, 2, 510-534 (2005) · Zbl 1068.90053 |
| [10] | Beliën, J.; Demeulemeester, E., A branch-and-price approach for integrating nurse and surgery scheduling, European Journal of Operational Research, 189, 652-668 (2008) · Zbl 1146.90404 |
| [11] | Maenhout, B.; Vanhoucke, M., Branching strategies in a branch-and-price approach for a multiple objective nurse scheduling problem, Journal of Scheduling, 13, 1, 77-93 (2010) · Zbl 1185.90085 |
| [12] | Cheng, B. M.W.; Lee, J. H.M.; Wu, J. A.C. K., A nurse rostering system using constraint programming and redundant modelling, IEEE Transactions on Information Technology in Biomedicine, 1, 1, 44-54 (1997) |
| [13] | Wonga, G. Y.C.; Chun, A. H.W., Constraint-based rostering using meta-level reasoning and probability-based ordering, Engineering Applications of Artificial Intelligence, 17, 599-610 (2004) |
| [14] | Junker UE, Karisch S, Kohl N, Vaaben B, Fahle T, Sellmann M. A framework for constraint programming based column generation. In: Jaffar J (ed), Principles and practice of constraint programming; 1999. p. 261-275.; Junker UE, Karisch S, Kohl N, Vaaben B, Fahle T, Sellmann M. A framework for constraint programming based column generation. In: Jaffar J (ed), Principles and practice of constraint programming; 1999. p. 261-275. · Zbl 0983.90059 |
| [15] | Yunes TH, Moura AV, de Souza CC. Solving very large crew scheduling problems to optimality. In: Proceedings of the ACM symposium on applied computing; 2000. p. 446-451.; Yunes TH, Moura AV, de Souza CC. Solving very large crew scheduling problems to optimality. In: Proceedings of the ACM symposium on applied computing; 2000. p. 446-451. |
| [16] | Fahle, T.; Junker, U.; Karisch, S.; Kohl, N.; Sellmann, M.; Vaaben, B., Constraint programming based column generation for crew assignment, Journal of Heuristics, 8, 59-81 (2002) · Zbl 1073.90542 |
| [17] | Rousseau, L. M.; Gendreau, M.; Pesant, G.; Focacci, F., Solving VRPTWs with constraint programming based column generation, Annals of Operations Research, 13, 1, 199-216 (2004) · Zbl 1062.90007 |
| [18] | Pisinger, D.; Sigurd, M., Using decomposition techniques and constraint programming for solving the two-dimensional bin-packing problem, INFORMS Journals on Computing, 19, 1, 36-51 (2007) · Zbl 1241.90118 |
| [19] | Demassey, S.; Pesant, G.; Rousseau, L.-M., A cost-regular based hybrid column generation approach, Constraints, 11, 4, 315-333 (2006) · Zbl 1117.90066 |
| [20] | Gendron B, Lebbah H, Pesant G. Improving the cooperation between the master problem and the subproblem in constraint programming based column generation. In: Barták R, Milano M (eds.) Integration of AI and OR techniques in constraint programming for combinatorial optimization problems; 2005. p. 217-227.; Gendron B, Lebbah H, Pesant G. Improving the cooperation between the master problem and the subproblem in constraint programming based column generation. In: Barták R, Milano M (eds.) Integration of AI and OR techniques in constraint programming for combinatorial optimization problems; 2005. p. 217-227. · Zbl 1133.68429 |
| [21] | Barnhart, C.; Johnson, E. L.; Nemhauser, G. L.; Savelsbergh, M. W.P.; Vance, P. H., Branch-and-price: column generation for solving huge integer programs, Operations Research, 46, 316-329 (1998) · Zbl 0979.90092 |
| [22] | Lubbecke, M. E.; Desrosiers, J., Selected topics in column generation, Operations Research, 53, 1007-1023 (2002) · Zbl 1165.90578 |
| [23] | Dantzig, G. B.; Wolfe, P., Decomposition principle for linear programs, Operations Research, 8, 101-111 (1960) · Zbl 0093.32806 |
| [24] | Gilmore, P. C.; Gomory, R. E., A linear programming approach to the cutting-stock problem, Operations Research, 9, 849-859 (1961) · Zbl 0096.35501 |
| [25] | Qu R, He F. A hybrid constraint programming approach for nurse rostering problems. In: Allen T, Ellis R, Petridis M (eds.) Applications and Innovations in Intelligent Systems XVI; 2008. p. 211-224.; Qu R, He F. A hybrid constraint programming approach for nurse rostering problems. In: Allen T, Ellis R, Petridis M (eds.) Applications and Innovations in Intelligent Systems XVI; 2008. p. 211-224. |
| [26] | van Hoeve, W. J.; Katriel, I., Global constraints, (Rossi, F.; Beek, P.; van; Walsh, T., Handbook of constraint programming (2006), Elsevier B.V.), 169-208 · Zbl 1175.90011 |
| [27] | Hooker, J. N., Integrated methods for optimization (2007), Springer · Zbl 1214.90084 |
| [28] | van Hoeve, W. J.; Pesant, G.; Rousseau, L. M., On global warming: flow-based soft global constraints, Journal of Heuristics, 12, 347-373 (2006) · Zbl 1100.68623 |
| [29] | Walsh T. Depth-bounded discrepancy search. In: Proceedings of IJCAI-97; 1997. p. 1388-1393.; Walsh T. Depth-bounded discrepancy search. In: Proceedings of IJCAI-97; 1997. p. 1388-1393. |
| [30] | Focacci F, Lodi A, Milano M. Cost-based domain filtering. In: Jaffar J (ed), Principles and practice of constraint programming 1999. p. 189-203.; Focacci F, Lodi A, Milano M. Cost-based domain filtering. In: Jaffar J (ed), Principles and practice of constraint programming 1999. p. 189-203. |
| [31] | Apt, K. R., Principles of constraint programming (2003), Cambridge University Press · Zbl 1187.68132 |
| [32] | Sellmann, M.; Zervoudakis, K.; Stamatopoulos, P.; Fahle, T., Crew assignment via constraint programming: integrating column generation and heuristic tree search, Annals of Operations Research, 115, 1, 207-225 (2002) · Zbl 1013.90091 |
| [33] | Harvey WD, Ginsberg ML. Limited discrepancy search. In: Proceedings of the fourteenth international joint conference on artificial intelligence; 1995. p. 607-13.; Harvey WD, Ginsberg ML. Limited discrepancy search. In: Proceedings of the fourteenth international joint conference on artificial intelligence; 1995. p. 607-13. |
| [34] | Rousseau L-M. Stabilization issues for constraint programming based column generation. In: Régin J-C, Rueher M (eds.) Integration of AI and OR techniques in constraint programming for combinatorial optimization problems; 2004. p. 402-408.; Rousseau L-M. Stabilization issues for constraint programming based column generation. In: Régin J-C, Rueher M (eds.) Integration of AI and OR techniques in constraint programming for combinatorial optimization problems; 2004. p. 402-408. · Zbl 1094.68655 |
| [35] | Vanderbeck, F.; Wolsey, L. A., An exact algorithm for IP column generation, Operations Research Letters, 19, 4, 151-159 (1996) · Zbl 0873.90074 |
| [36] | Sol M, Savelsbergh MWP. Column generation techniques for pickup and delivery problems; 1994.; Sol M, Savelsbergh MWP. Column generation techniques for pickup and delivery problems; 1994. · Zbl 0833.90037 |
| [37] | Focacci, F.; Lodi, A.; Milano, M., Optimization-oriented global constraints, Constraints, 7, 3, 351-365 (2002) · Zbl 1028.68024 |
| [38] | Petit T, Régin J-C, Bessière C. Specific filtering algorithms for over-constrained problems. In: Walsh T (ed) Principles and practice of constraint programming; 2001. p. 451-463.; Petit T, Régin J-C, Bessière C. Specific filtering algorithms for over-constrained problems. In: Walsh T (ed) Principles and practice of constraint programming; 2001. p. 451-463. · Zbl 1067.68663 |
| [39] | Fijn van Draat, L., Harmonious personnel scheduling, Medium Econometrische Toepassingen, 14, 4-7 (2006) |
| [40] | Burke, E. K.; Curtois, T.; Post, G.; Qu, R.; Veltman, B., A hybrid heuristic ordering and variable neighbourhood search for the nurse rostering problem, European Journal of Operational Research, 330-341 (2008) · Zbl 1149.90346 |
| [41] | Burke, E. K.; Li, J.; Qu, R., A hybrid model of integer programming and variable neighbourhood search for highly-constrained rostering problems, European Journal of Operational Research, 203, 2, 484-493 (2009) · Zbl 1177.90356 |
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.
