Hansen, Anders Dohn2; Mason, Andrew3; Ryan, David3
1 Operations Research, Department of Management Engineering, Technical University of Denmark2 Department of Management Engineering, Technical University of Denmark3 University of Auckland
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.
label setting; set partitioning problem; set covering problem; column generation; shortest path problem with resource constraints; linear programming; integer programming; generalized rostering problem; nurse scheduling; nurse rostering; branch-and-price; dynamic programming