Abstract:

Nurse rostering problem is one of multiconstrained problems with many traps. Therefore neither traditional approaches nor heuristic methods can find the optimal solution for the problem. This paper studied and solved the nurse rostering problem by applying a hybrid method that combines genetic algorithm (GA) and variable neighborhood search (VNS). In this method, GA generates a new nurse roster by adding judgment rules and control policies. VNS algorithm operates on the steps of initialization, crossover and mutation with constraints, and separation of solution space. Finally, the experiment results of 20 nurse rostering problems indicate that, within the same runtime, the method of GA+VNS outperforms the method of IP+VNS which is internationally known as the newest approach.

Key words: nurse rostering problem;genetic algorithm;variable neighborhood search