A simple randomized variable neighbourhood search for nurse rostering

摘要

Nurse rostering is a complex and hard discrete optimization problem as well as a very common personnel scheduling task which occurs in each hospital ward. To solve the highly constrained nurse rostering problem, various approaches have been developed including some effective variable neighbourhood search methods. In this paper, a randomized variable neighbourhood search algorithm, which is much simpler than existing methods of the similar type, is proposed. The algorithm uses random combined group operators to iteratively search better solutions and a cycle shift operator to diversify the search space when stagnating in local optima. Computational experiments are carried out with fifty-five instances from the First International Nurse Rostering Competition. Under the time limit of the competition, results achieved show that the proposed algorithm is very competitive with the state-of-the-art methods. Comparison of results with respect to the average performance with other algorithms indicates that our approach is more stable. Analysis and discussion based on extensive experiments are also presented to investigate critical features of our algorithm.