Abstract
The problem of rerostering nurse schedules arises in hospitals when at least one nurse informs that she will be unable to perform the shifts assigned to her on one or more future work days. As a result, the current roster must be rebuilt in accordance with labour contract rules and institutional requirements. All such restraints are regarded as hard constraints. However, major alterations in the previously assigned nurse schedules must be avoided. This paper is based on a case study of a public hospital in Portugal. It presents two new integer multicommodity flow formulations for the rerostering problem, besides a computational experiment performed using real data. The first model is based on a directed multilevel acyclic network. The aggregation of nodes in this network led to the second model. The results obtained show that the second integer multicommodity flow formulation outperforms the first, both in terms of solution quality, as well as in computational time.
Similar content being viewed by others
References
Aykin, T. (2000). “A Comparative Evaluation of Modeling Approaches to the Labor Shift Scheduling Problem.” European Journal of Operational Research 125, 381–397.
Baker, K.R. (1976). “Workforce Allocation in Cyclic Scheduling Problems: A Survey.” Operational Research Quarterly 27(1)ii, 155–167.
Barnhart, C., E. Johnson, G. Nemhauser, M. Savelsbergh, and P. Vance. (1998). “Branch-and-Price: Column Generation for Solving Integer Programs.” Operations Research 46(3), 316–329.
Barnhart, C., C. Hane, G. Nemhauser, and P. Vance. (2000). “Using Branch-and-Price-and-Cut to Solve Origin-Destination Integer Multicommodity Flow Problems.” Operations Research 48(2), 318–326.
Bechtold, S.E. (1988). “Implicit Optimal and Heuristic Labor Staffing in a Multiobjective Multilocation Environment.” Decision Sciences 19(2), 353–372.
Caprara, A., M. Fischetti, and P. Toth. (2000). “Algorithms for the Set Covering Problem.” Annals of Operations Research 98, 353–371.
Caprara, A., M. Fischetti, P. Toth, D. Vigo, and P. Guida. (1997). “Algorithms for Railway Crew Management.” Mathematical Programming 79, 125–141.
Carraresi, P. and G. Gallo. (1984). “A Multi-Level Bottleneck Assignment Approach to the Bus Drivers' Restoring Problem.” European Journal of Operational Research 16, 163–173.
Ceria, S., P. Nobili, and A. Sassano. (1998). “A Lagrangean-Based Heuristic for Set Covering Problems.” Mathematical Programming 81, 215–228.
CPLEX. (2000). Using the CPLEXR Callable Library and CPLEXR Mixed Integer Library, CPLEX Manual (Version 7.0). Incline Village, NV: CPLEXR Division, ILOG, Inc.
Feo, T.A. and J.F. Bard. (1989), “Flight Scheduling and Maintenance Base Planning.” Management Science 35(12), 1415–1432.
Hall, N. and D. Hochbaum. (1992). “The Multicovering Problem.” European Journal of Operational Research 62, 323–339.
Moz, M. (1993). “Um Sistema para o Planeamento e Gestão das Escalas do Pessoal de Enfermagem de uma Unidade Hospitalar.” MSc. Dissertation, Institute Superior de Economia e Gestão, Universidade Técnica de Lisboa.
Moz, M. and M.T. Almeida. (1997). “Nurse Scheduling-A Mathematical Programming Based Approach.” Working paper 3/97, Centre of Operational Research, Faculdade de Ciências, Universidade de Lisboa.
Moz, M. and M. Pato. (2003). “An Integer Multicommodity Flow Model Applied to the Rerostering of Nurse Schedules.” Annals of Operations Research 119, 285–301.
Paias, A. and J. Paixão. (1993). “State Space Relaxations for Set Covering Problems Related to Bus Driver Scheduling.” European Journal of Operational Research 71, 303–316.
Paixão, J. and M. Pato. (1989). “A Structural Lagrangean Relaxation for Two-Duty Period Bus Driver Scheduling Problems.” European Journal of Operational Research 39, 213–222.
Siferd, S.P. and W.C. Benton. (1992). “Workforce Staffing and Scheduling: Hospital Nursing Specific Models.” European Journal of Operational Research 60, 233–246.
Tien, J.M. and A. Kamiyama. (1982). “On Manpower Scheduling Algorithms.” SIAM Review 24(3), 275–287.
Warner, D.M. (1976). “Scheduling Nursing Personnel According to Nursing Preference: A Mathematical Programming Approach.” Operations Research 24(5), 842–856.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Moz, M., Pato, M.V. Solving the Problem of Rerostering Nurse Schedules with Hard Constraints: New Multicommodity Flow Models. Annals of Operations Research 128, 179–197 (2004). https://doi.org/10.1023/B:ANOR.0000019104.39239.ed
Issue Date:
DOI: https://doi.org/10.1023/B:ANOR.0000019104.39239.ed