An Integer Multicommodity Flow Model Applied to the Rerostering of Nurse Schedules

Authors: Moz M.¹; Pato M.V.²

Source: Annals of Operations Research, Volume 119, Numbers 1-4, March 2003 , pp. 285-301(17)

Publisher: Springer

Abstract:

The problem of rerostering service schedules is very common in organizations that work shifts around the clock every day of the year with a set number of employees. Whenever one or more workers announce that they will not be able to attend to tasks previously assigned in their schedule, those tasks must be performed at the expense of alterations in the schedules of other workers. These changes should not conflict with the rules laid down by the administration and employment contracts and should affect the previous schedules as little as possible. This is a difficult real problem calling for a computational tool to cope with it easily. In the paper the issue is described in detail in the context of nurse scheduling and formulated as an integer multicommodity flow problem with additional constraints, in a multi-level acyclical network. A heuristic was implemented as a first approach to solving the problem. Subsequently the integer linear programming formulation of the multicommodity flow model and two linear relaxations were tested using CPLEX [2] optimizers. The computational results reported regard real instances from a Lisbon state hospital. Satisfactory rosters were obtained within acceptable computational times in all instances tested, either with the integer optimizer, or with the heuristic. This being so, refinements will be undertaken to embed these methodologies in a decision support system that may assist the head nurse in her daily rerostering activities.

Keywords: employee scheduling; rerostering; integer linear programming; integer multicommodity flow problems

Language: English

Document Type: Research article

Affiliations: 1: Department of Mathematics, Institute of Economics and Business Administration, Technical University of Lisbon, Rua do Quelhas, 6, 1200-781 Lisboa, Portugal, and Center of Operational Research, Faculty of Science, University of Lisbon, Portugal mm 2: Department of Mathematics, Institute of Economics and Business Administration, Technical University of Lisbon, Rua do Quelhas, 6, 1200-781 Lisboa, Portugal, and Center of Operational Research, Faculty of Science, University of Lisbon, Portugal mp

Publication date: 2003-03-01

• In this: publication
• By this: publisher
• In this Subject: Materials & Manufacturing ,  Mathematics and Statistics ,  Industrial Engineering
• By this author: Moz M. ;  Pato M.V.

Website © Publishing Technology. Article copyright remains with the publisher, society or author(s) as specified within the article.

• Terms and conditions
• Privacy policy
• Information for advertisers