  In this paper, we study the nurse rostering problem that considers multiple
units and many soft time-related constraints. An efficient branch and price
solution approach that relies on a fast algorithm to solve the pricing
subproblem of the column generation process is presented. For the nurse
rostering problem, its pricing subproblem can be formulated as a shortest path
problem with resource constraints, which has been the backbone of several
solutions for several classical problems like vehicle routing problems.
However, approaches that perform well on these problems cannot be used since
most constraints in the nurse rostering problem are soft. Based on ideas
borrowed from global constraints in constraint programming to model rostering
problems, an efficient dynamic programming algorithm with novel label
definitions and dominating rules specific to soft time-related constraints is
proposed. In addition, several acceleration strategies are employed to improve
the branch and price algorithm. Computational results on instances of different
sizes indicate that the proposed algorithm is a promising solution for the
nurse rostering problem with multiple units.
