zbMATH — the first resource for mathematics

A generalized linear programming model for nurse scheduling. (English) Zbl 0943.90032
Summary: This paper presents a 0-1 column generation model with a resource constrained shortest path auxiliary problem for nurse scheduling. The master problem finds a configuration of individual schedules to satisfy the demand coverage constraints while minimizing salary costs and maximizing both employee preferences and team balance. A feasible solution of the auxiliary problem is an acceptable schedule for a given nurse, with respect to collective agreement requirements such as seniority, workload, rotations and days off. We define a new resource structure in the auxiliary problem in order to take into account the complex collective agreement rules specific to the nurse scheduling problem. This model generalizes further the previous formulations discussed in the literature and can be viewed as a general scheme for complex personnel scheduling problems, especially in the context of organizations which operate around the clock. Solution methods and preliminary test results are discussed.

90B35 Deterministic scheduling theory in operations research
90C90 Applications of mathematical programming
90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
Full Text: DOI
[1] Convention collective intervenue entre le comité patronal de négociation du secteur de la santé et des services sociaux, le souscomité patronal de négociation des centres hospitaliers publics et la Fédération des affaires sociales (CSN), C.H.P., (1991), Québec, Canada
[2] Dagenais, C., Automated staff scheduling: description of current system, definition of requirements, cost estimates, ()
[3] Hung, R., Hospital nurse scheduling, Journal of nursing administration, 25, 7/8, 21-23, (1995)
[4] Smith, L.D.; Wiggins, A., A computer based nurse scheduling system, Computers and operations research, 4, 195-212, (1977)
[5] Anzai, M.; Miura, Y., Computer program for quick work scheduling of nursing staff, Medical information, 12, 1, 43-52, (1987)
[6] Okada, M.; Okada, M., Prolog-based system for nursing staff scheduling implemented on a personal computer, Computers and biomedical research, 21, 53-63, (1988)
[7] Baker, K., Scheduling a full-time workforce to meet cyclic staffing requirements, Management science, 20, 12, 1561-1568, (1974) · Zbl 0304.90056
[8] Burns, R.N., Manpower scheduling with variable demands and alternate weekends off, Infor, 16, 2, 101-111, (1978) · Zbl 0384.90056
[9] Burns, R.N.; Koop, G.J., A modular approach to optimal multiple-shift manpower scheduling, Operations research, 35, 1, 100-110, (1987) · Zbl 0614.90069
[10] Warner, D.M., Scheduling nursing personnel according to nursing preference: A mathematical programming approach, Operations research, 24, 5, 842-856, (1976) · Zbl 0337.90033
[11] Miller, H.E.; Pierskalla, W.P.; Rath, G.J., Nurse scheduling using mathematical programming, Operations research, 24, 5, 857-871, (1976) · Zbl 0337.90034
[12] Ozkarahan, I.; Bailey, J., Goal programming model subsystem of a flexible nurse scheduling support system, IIE transactions, 306-316, (1988)
[13] Berrada, I., Planification d’horaires du personnel infirmier dans un établissement hospitalier, ()
[14] Dantzig, G.B.; Wolfe, P., Decomposition principle for linear programs, Operations research, 8, 101-111, (1960) · Zbl 0093.32806
[15] Gilmore, P.C.; Gomory, R.E., A linear programming approach to the cutting stock problem, Operations research, 9, 849-859, (1961) · Zbl 0096.35501
[16] Gilmore, P.C.; Gomory, R.E., A linear programming approach to the cutting stock problem: part II, Operations research, 11, 863-888, (1963) · Zbl 0124.36307
[17] Desrosiers, J.; Dumas, Y.; Solomon, M.M.; Soumis, F., Time constrained routing and scheduling, (), 35-139 · Zbl 0861.90052
[18] Hansen, P.; Jaumard, B.; de Aragão, M.P., Un algorithme primal de programmation linéaire généralisée pour LES programmes mixtes, Comptes-rendus de l’académie des sciences de Paris, 313, 1, 557-560, (1991) · Zbl 0737.90045
[19] Vanderbeck, F.; Wolsey, L.A., An exact algorithm for IP column generation, () · Zbl 0873.90074
[20] 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, () · Zbl 0979.90092
[21] Jaumard, B.; Semet, F.; Vovor, T., A two-phase resource constrained shortest path algorithm for acyclic graphs, ()
[22] Beasley, J.E.; Christofides, N., An algorithm for the resource constrained shortest path problem, Networks, 19, 379-394, (1989) · Zbl 0673.90085
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.