Solving Nurse Rostering Problems with Lagrangian Relaxation and Column Generation

In this thesis we try to ll the gap between the current nurse rostering research and the very complex real world. In reality, very complex and elaborate regulations hold. Therefore, methodology is proposed that is very exible and robust to a variety of constraints. The nurse rostering problem is solved by applying a column generation approach that involves solving the Lagrangian dual problem with a subgradient algorithm. The algorithm is considered very robust to varying and dicult constraints, since the pricing problem is solved heuristically. This heuristic creates many patterns of shifts for every employee, which are evaluated on feasibility and solution value. In the restricted master problem, one of these patterns is selected for each employee, yielding an overall schedule. For validation of our methods, we use benchmark instances of which the optimal solution is known. Next to that, we compare the results of our algorithm with a dierent algorithm currently used by ORTEC. Although the ORTEC algorithm has a dierent objective function, the optimal solutions to the benchmark instances is the same and therefore the two algorithms can be compared. It is shown that for both algorithms it is very hard to nd good quality schedules within a short amount of time. When exact methodology is incorporated in the algorithm described in this paper, it is shown for the smaller instances that the new algorithm is outperforming the algorithm of ORTEC. For the larger instances it is hard to conclude which algorithm performs best, due to the slight dierence in objective functions. It is concluded, that it is of interest to investigate whether it is necessary to be able to comply to all exceptions to the rules or that it is sufficient to comply to more strict constraints to obtain good solutions in limited time.