Analysis of three mathematical models of the staff rostering problem. (English) Zbl 1280.90081
Summary: Staff rostering is a major challenge in the service sector, where exploitation costs are essentially made up of staffing costs. Searching for an optimum has direct economic returns but the rosters must satisfy numerous legal constraints. This paper presents work on an exact approach using branch-and-price methods on a concrete situation. We develop three MILP models and extend them with valid inequalities to two cases. Their computation results on a set of 960 tests covering several scenarios will then be compared and analyzed.
MSC:
| 90B70 | Theory of organizations, manpower planning in operations research |
| 90C05 | Linear programming |
| 90B35 | Deterministic scheduling theory in operations research |
References:
| [1] | Aickelin, U., & Dowsland, K. A. (2000). Exploiting problem structure in a genetic algorithms approach to a nurse rostering problem. Journal of Scheduling, 31, 139–153. · Zbl 0965.90019 · doi:10.1002/(SICI)1099-1425(200005/06)3:3<139::AID-JOS41>3.0.CO;2-2 |
| [2] | Barnhart, C., Johnson, E., Nemhauser, G. L., Savelsbergh, M. W. P., & Vance, P. H. (1998). Branch-and-price: column generation for solving huge integer programs. Operations Research, 46, 316–329. · Zbl 0979.90092 · doi:10.1287/opre.46.3.316 |
| [3] | Beliën, J., & Demeulemeester, E. (2006). Scheduling trainees at a hospital department using a branch-and-price approach. European Journal of Operational Research, 175, 258–278. · Zbl 1137.90479 · doi:10.1016/j.ejor.2005.04.028 |
| [4] | Brusco, M. J., & Jacobs, L. W. (1993). A simulated annealing approach to the cyclic staff-scheduling problem. Naval Research Logistics, 40, 69–84. · Zbl 0769.90056 · doi:10.1002/1520-6750(199302)40:1<69::AID-NAV3220400105>3.0.CO;2-H |
| [5] | Burke, E. K., De Causmaecker, P., & Vanden Berghe, G. (1998). A hybrid tabu search algorithm for the nurse rostering problem. In Selected papers from the 2nd Asia pacific conference on simulated evolution and learning (pp. 187–194). |
| [6] | Burke, E. K., 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. · Zbl 1154.90422 · doi:10.1023/B:JOSH.0000046076.75950.0b |
| [7] | Ceria, S., Nobili, P., & Sassano, A. (1997). Set covering problem. In M. Dell’Amico, F. Maffoli, & S. Martello (Eds.), Annotated bibliographies in combinatorial optimization (pp. 415–428). New York: Wiley. · Zbl 1068.90506 |
| [8] | Dantzig, G. B., & Wolfe, P. (1960). Decomposition principle for linear programs. Operations Research, 8, 101–111. · Zbl 0093.32806 · doi:10.1287/opre.8.1.101 |
| [9] | Desrochers, M., & Soumis, F. (1988). A generalised permanent labelling algorithm for the shortest path problem with time windows. INFOR, 26(3), 191–212. · Zbl 0652.90097 |
| [10] | Dror, M. (1994). Note on the complexity of the shortest path models for column generation in VRPTW. Operations Research, 42, 977–978. Technical Note. · Zbl 0815.90064 · doi:10.1287/opre.42.5.977 |
| [11] | 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, 3–37. · Zbl 1053.90034 · doi:10.1016/S0377-2217(03)00095-X |
| [12] | Gamache, M., Soumis, F., Marquis, G., & Desrosiers, J. (1999). A column generation approach for large scale aircrew rostering problems. Operations Research, 47, 247–263. · Zbl 1041.90513 · doi:10.1287/opre.47.2.247 |
| [13] | Gilmore, P. C., & Gomory, R. E. (1960). A linear programming approach to the cutting stock problem. Operations Research, 9, 849–859. · Zbl 0096.35501 · doi:10.1287/opre.9.6.849 |
| [14] | Jaumard, B., Semet, F., & Vovor, T. (1998). A generalized linear programming model for nurse scheduling. European Journal of Operational Research, 107(1), 1–18. · Zbl 0943.90032 · doi:10.1016/S0377-2217(97)00330-5 |
| [15] | Mautor, T. Naudin, É. (2007). Arcs-states models for the vehicle routing problem with time windows and related problems. Computers and Operations Research, 34(4), 1061–1084. · Zbl 1102.90014 · doi:10.1016/j.cor.2005.05.024 |
| [16] | Naudin, É. (2003) Problèmes de tournées de véhicules avec contraintes de ressources: modélisation par arcs-états et techniques de résolution adaptées. PhD thesis, University Pierre et Marie Curie–Paris 6. |
| [17] | Warner, D. M. (1976). Scheduling nursing personnel according to nursing preference: A mathematical programming approach. Operations Research, 24(5), 842–856. · Zbl 0337.90033 · doi:10.1287/opre.24.5.842 |
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.
