A Generic Solution Approach to Nurse Rostering | Anders Dohn, Andrew Mason, David Ryan
| | Abstract | In this report, we present a solution approach to the nurse
rostering problem. The problem is defined by a generic model that
is able to capture close to all of the problem characteristics
that we have seen in the literature and in the realistic problems
at hand. The model is used directly in the solution algorithm
which gives a very versatile solution method. The method at the
same time is constructed to exploit a number of problem specific
features and thereby we have a both versatile and efficient
solution method. The approach presented uses a set partitioning
model of the rostering problem, which is solved in a
branch-and-price framework. Columns of the set partitioning
problem are generated dynamically and branch-and-bound is used to
enforce integrality. The column generating subproblem is modeled
in three stages that utilize the inherent structure of
roster-lines. Some important features of the implementation are
described. The implementation builds on the generic model and
hence the program can be setup for any problem that fits the
model. The adaption to a new problem is simple, as it requires
only the input of a new problem definition. The solution method is
internally adjusted according to the new definition. In this
report, we present two different practical problems along with
corresponding solutions. The approach captures all features of
each problem and is efficient enough to provide optimal solutions.
The solution time is still too large for the method to be
immediately applicable in practice, but we suggest a number of
ways to improve the method further. | | Keywords | generalized rostering problem, nurse rostering, nurse scheduling, column generation, branch-and-price, set partitioning problem, set covering problem, integer programming, linear programming, shortest path problem with resource constraints, dynamic progr | | Type | Technical report | | Journal/Book/Conference | DTU Management Engineering, Technical University of Denmark | | Year | 2010 | | Electronic version(s) | [pdf] | | BibTeX data | [bibtex] | | IMM Group(s) | Operations Research |
|