×

A graph-based formulation for the shift rostering problem. (English) Zbl 1441.90081

Summary: This paper investigates a shift rostering problem – the assignment of staff to shifts over a planning horizon such that work rules are observed. Traditional integer-programming models are not able to solve shift rostering problems effectively for a large number of staff and feasible shift patterns. We formulate work rules in terms of newly-proposed prohibited meta-sequences and resource constraints. A graph-based formulation and a specialized graph construction algorithm are proposed where the set of feasible shift patterns is represented by paths of a graph. The formulation size depends on the structure of the work-rule constraints and is independent of the number of staff. This approach results in smaller networks allowing large-scale rostering problems with hard constraints to be solved efficiently using standard commercial solvers. Moreover, it allows finding multiple optimal solutions which are beneficial for managerial decision makers. Computational results show that the proposed approach can obtain new best-known solutions and identify proven optimal solutions for almost all NSPLIB instances at significantly lower CPU times.

MSC:

90B70 Theory of organizations, manpower planning in operations research
90B35 Deterministic scheduling theory in operations research
90C10 Integer programming
90C59 Approximation methods and heuristics in mathematical programming

Software:

NSPLib
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Andersen, A. R.; Nielsen, B. F.; Reinhardt, L. B.; Stidsen, T. R., Staff optimization for time-dependent acute patient flow, European Journal of Operational Research, 272, 1, 94-105 (2019) · Zbl 1403.90250
[2] Bard, J. F.; Binici, C.; deSilva, A. H., Staff scheduling at the United States Postal Service, Computers & Operations Research, 30, 5, 745-771 (2003) · Zbl 1026.90038
[3] 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
[4] Blöchliger, I., Modeling staff scheduling problems. a tutorial, European Journal of Operational Research, 158, 3, 533-542 (2004) · Zbl 1056.90056
[5] Brucker, P.; Qu, R.; Burke, E., Personnel scheduling: Models and complexity, European Journal of Operational Research, 210, 3, 467-473 (2011) · Zbl 1213.90151
[6] Bruecker, P. D.; Beliën, J.; Van den Bergh, J.; Demeulemeester, E., A three-stage mixed integer programming approach for optimizing the skill mix and training schedules for aircraft maintenance, European Journal of Operational Research, 267, 2, 439-452 (2018) · Zbl 1403.90316
[7] Brunner, J. O.; Bard, J. F.; Köhler, J. M., Bounded flexibility in days-on and days-off scheduling, Naval Research Logistics, 60, 8, 678-701 (2013) · Zbl 1410.90082
[8] Burke, E. K.; Curtois, T., New approaches to nurse rostering benchmark instances, European Journal of Operational Research, 237, 1, 71-81 (2014) · Zbl 1304.90088
[9] Cappanera, P.; Gallo, G., A multicommodity flow approach to the crew rostering problem, Operations Research, 52, 4, 583-596 (2004) · Zbl 1165.90343
[10] Cheang, B.; Li, H.; Lim, A.; Rodrigues, B., Nurse rostering problems — A bibliographic survey, European Journal of Operational Research, 151, 3, 447-460 (2003) · Zbl 1045.90027
[11] Côté, M.-C.; Gendron, B.; Rousseau, L.-M., Modeling the regular constraint with integer programming, (Van Hentenryck, P.; Wolsey, L., Integration of ai and or techniques in constraint programming for combinatorial optimization problems (2007), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 29-43 · Zbl 1214.90086
[12] Cuevas, R.; Ferrer, J.-C.; Klapp, M.; Muñoz, J.-C., A mixed integer programming approach to multi-skilled workforce scheduling, Journal of Scheduling, 19, 1, 91-106 (2016) · Zbl 1341.90040
[13] Dahmen, S.; Rekik, M., Solving multi-activity multi-day shift scheduling problems with a hybrid heuristic, Journal of Scheduling, 18, 2, 207-223 (2015) · Zbl 1312.90020
[14] Doi, T.; Nishi, T.; Voss, S., Two-level decomposition based matheuristic for airline crew rostering problems with fair working time, European Journal of Operational Research, 267, 2, 428-438 (2018) · Zbl 1403.90461
[15] Dolgui, A.; Kovalev, S.; Kovalyov, M. Y.; Malyutin, S.; Soukhal, A., Optimal workforce assignment to operations of a paced assembly line, European Journal of Operational Research, 264, 1, 200-211 (2018) · Zbl 1380.90150
[16] Ernst, A.; Jiang, H.; Krishnamoorthy, M.; Sier, D., Staff scheduling and rostering: A review of applications, methods and models, European Journal of Operational Research, 153, 1, 3-27 (2004) · Zbl 1053.90034
[17] Fügener, A.; Pahr, A.; Brunner, J. O., Mid-term nurse rostering considering cross-training effects, International Journal of Production Economics, 196, 176-187 (2018)
[18] Jarray, F., A 4-day or a 3-day workweeks scheduling problem with a given workforce size, Asia-Pacific Journal of Operational Research, 26, 5, 685-696 (2009) · Zbl 1178.90153
[19] Lau, H. C., On the complexity of manpower shift scheduling, Computers & Operations Research, 23, 1, 93-102 (1996) · Zbl 0838.90065
[20] Maenhout, B.; Vanhoucke, M., An exact algorithm for an integrated project staffing problem with a homogeneous workforce, Journal of Sscheduling, 19, 2, 107-133 (2016) · Zbl 1341.90053
[21] Margot, F., Symmetry in integer linear programming, 50 years of integer programming 1958-2008, 647-686 (2010), Springer · Zbl 1187.90200
[22] Musliu, N., Heuristic methods for automatic rotating workforce scheduling, International Journal of Computational Intelligence Research., 2, 4, 309-326 (2006)
[23] Örmeci, E. L.; Salman, F. S.; Yücel, E., Staff rostering in call centers providing employee transportation, Omega, 43, 41-53 (2014)
[24] Rahimian, E.; Akartunali, K.; Levine, J., A hybrid integer programming and variable neighbourhood search algorithm to solve nurse rostering problems, European Journal of Operational Research, 258, 2, 411-423 (2017) · Zbl 1394.90300
[25] Santos, H. G.; Toffolo, T. A.M.; Gomes, R. A.M.; Ribas, S., Integer programming techniques for the nurse rostering problem, Annals of Operations Research, 239, 1, 225-251 (2016) · Zbl 1336.90063
[26] Smet, P.; Brucker, P.; Causmaecker, P. D.; Vanden Berghe, G., Polynomially solvable personnel rostering problems, European Journal of Operational Research, 249, 1, 67-75 (2016) · Zbl 1346.90474
[27] Smet, P.; Ernst, A. T.; Berghe, G. V., Heuristic decomposition approaches for an integrated task scheduling and personnel rostering problem, Computers & Operations Research, 76, 60-72 (2016) · Zbl 1349.90398
[28] Taskiran, G. K.; Zhang, X., Mathematical models and solution approach for cross-training staff scheduling at call centers, Computers & Operations Research, 87, 258-269 (2017) · Zbl 1391.90280
[29] Van den Bergh, J.; Beliën; Bruecker, P. D.; Demeulemeester, E.; Boeck, L. D., Personnel scheduling: A literature review, European Journal of Operational Research, 226, 3, 367-385 (2013) · Zbl 1292.90001
[30] Van Den Eeckhout, M.; Maenhout, B.; Vanhoucke, M., A heuristic procedure to solve the project staffing problem with discrete time/resource trade-offs and personnel scheduling constraints, Computers & Operations Research, 101, 144-161 (2019) · Zbl 1458.90361
[31] Vanhoucke, M.; Maenhout, B., NSPLib — A nurse scheduling problem library: a tool to evaluate (meta-) heuristic procedures, Operational research for health policy: making better decisions, proceedings of the 31st annual meeting of the working group on operations research applied to health services, 151-165 (2007)
[32] Vanhoucke, M.; Maenhout, B., On the characterization and generation of nurse scheduling problem instances, European Journal of Operational Research, 196, 2, 457-467 (2009) · Zbl 1163.90514
[33] Vermuyten, H.; Rosa, J. N.; Marques, I.; Beliën, J.; Barbosa-Póvoa, A., Integrated staff scheduling at a medical emergency service: An optimisation approach, Expert Systems with Applications, 112, 62-76 (2018)
[34] Wong, T.; Xu, M.; Chin, K., A two-stage heuristic approach for nurse scheduling problem: A case study in an emergency department, Computers & Operations Research, 51, 99-110 (2014) · Zbl 1348.90325
[35] Zheng, Z.; Liu, X.; Gong, X., A simple randomized variable neighbourhood search for nurse rostering, Computers & Industrial Engineering, 110, 165-174 (2017)
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.