TY - JOUR

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

AU - Kheiri, Ahmed

AU - Gretsista, Angeliki

AU - Keedwell, Ed

AU - Lulli, Guglielmo

AU - Epitropakis, Michael

AU - Burke, Edmund

N1 - This is the author’s version of a work that was accepted for publication in Computers and Operations Research. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Computers and Operations Research, 130, 2021 DOI: 10.1016/j.cor.2021.105221

PY - 2021/6/1

Y1 - 2021/6/1

N2 - The nurse rostering problem is a very important problem to address. Due to the importance of nurses’ jobs, it is vital that all the nurses in a hospital are 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 is a computationally hard and challenging combinatorial optimisation problem. To solve it, general and efficient methodologies such as selection hyper-heuristics have emerged. To address the multi-stage nurse rostering formulation, posed by the second international nurse rostering competition’s problem, a sequence-based selection hyper-heuristic that utilises a statistical Markov model is developed. The proposed algorithm 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 a significant potential on difficult problem instances.

AB - The nurse rostering problem is a very important problem to address. Due to the importance of nurses’ jobs, it is vital that all the nurses in a hospital are 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 is a computationally hard and challenging combinatorial optimisation problem. To solve it, general and efficient methodologies such as selection hyper-heuristics have emerged. To address the multi-stage nurse rostering formulation, posed by the second international nurse rostering competition’s problem, a sequence-based selection hyper-heuristic that utilises a statistical Markov model is developed. The proposed algorithm 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 a significant potential on difficult problem instances.

KW - Hyper-heuristic

KW - Optimisation

KW - Healthcare

KW - Scheduling

U2 - 10.1016/j.cor.2021.105221

DO - 10.1016/j.cor.2021.105221

M3 - Journal article

VL - 130

JO - Computers and Operations Research

JF - Computers and Operations Research

SN - 0305-0548

M1 - 105221

ER -