A hyper-heuristic approach based upon a hidden Markov model for the multi-stage nurse rostering problem

Abstract

The importance of the nurse rostering problem in complex healthcare environments should not be understated. The nurses in a hospital should be assigned to the most appropriate shifts and days so as to meet the demands of the hospital as well as to satisfy the requirements and requests of the nurses as much as possible. Nurse rostering represents a challenging and demanding combinatorial optimisation problem. To address it, general and efficient methodologies, such as selection hyper-heuristics, have emerged. In this paper, we will consider the multi-stage nurse rostering formulation, posed by the second international nurse rostering competition’s problem. We introduce a sequence-based selection hyper-heuristic that utilises a statistical Markov model. The proposed methodology incorporates a dedicated algorithm for building feasible initial solutions and a series of low-level heuristics with different dynamics that respect the characteristics of the competition’s problem formulation. Empirical results and analysis suggest that the proposed approach has significant potential for difficult problem instances.