A hyper-heuristic approach based upon a hidden Markov model for the multi-stage nurse rostering problem. (June 2021)

• Record Type: Journal Article
• Authors: Kheiri, Ahmed; Gretsista, Angeliki; Keedwell, Ed; Lulli, Guglielmo; Epitropakis, Michael G.; Burke, Edmund K.
• Is Part Of: Computers & operations research. Volume 130(2021)
• Publication Date: 2021-06
• Subjects: Hyper-heuristic -- Optimisation -- Healthcare -- Scheduling; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2021.105221
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: The paper describes a hyper-heuristic to solve nurse rostering. The paper addresses the multi-stage nurse rostering formulation posed by INRC-II. Results show that the proposed method is performing better than many other methods. 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.