A constructive shift patterns approach with simulated annealing for nurse rostering problem

Nurse Rostering problem (NRP) is an NP-Hard problem, which is difficult to solve for its optimality. This work aims to ensure the availability of enough nurses, by giving them fair consideration during the rostering period. In order to achieve this, we proposed a greedy constructive heuristic algorithm based on the idea of generating the most required shift patterns first to solve the nurses´ rostering problem at Universiti Kebangsaan Malaysia Medical Centre (UKMMC), Malaysia. That is, this approach attempts to reduce the complexity of the solution search space by generating all the allowed two-day and three-day shift patterns to build up the roster. We then use simulated annealing algorithm to improve the quality of the roster. The resulting roster demonstrates that our proposed approach generates a good quality roster in a reasonable time for our case study.