1 Department of Mathematics, Science and Technology, Aarhus University2 Department of Mathematics, Science and Technology, Aarhus University
This paper considers a nurse rostering problem from a ward at a Danish hospital. The problem is highly constrained and comprises a large set of different constraints. A branch-and-price method for solving the problem exactly is proposed. The master problem is to assign schedules to the nurses, and its linear relaxation is solved by means of column generation. The pricing sub-problem is to generate feasible schedules for the nurses and -- as a couple of different constraints including several special Danish regulations have to be observed -- is solved by constraint programming. A number of specific algorithms for handling these constraints are proposed. The method is very flexible regarding the rules a schedule should comply with, which is a key concern when creating solution methods for nurse rostering problems. Computational tests show that optimal solutions can be found for instances with a two weeks planning period in a reasonable amount of computing time.
Annals of Operations Research, 2014, Vol 222, Issue 1, p. 107-123