The nurse rostering problem refers to the assignment of nurses to daily shifts according to the required demand of each shift and day, with consideration for the operational requirements and nurses’ preferences. This problem is known to be an NP-hard problem, difficult to be solved using the known exact solution methods especially for large size instances. Mostly, this problem is modeled with soft and hard constraint, and the objective is set to minimize the violations for the soft constraints. In this paper, a new two-stage variable neighborhood search algorithm is proposed for solving the nurse rostering problem. The first stage aims at minimizing the violations of the soft constraints with the higher penalty weights in the objective function. While the second stage considers minimizing the total solution penalty taking into account all the soft constraint. The proposed algorithm was tested on the 24 benchmark instances of Curtois and Qu (Technical Report, ASAP Research Group, School of Computer Science, University of Nottingham (2014)). The test results revealed that the proposed algorithm is able to compete with the results of a recent heuristic approach from literature for most of the tested instances.
Keywords: Nurse rostering, nurse scheduling, staff scheduling, variable neighborhood search, heuristics, timetabling
@article{RO_2021__55_2_673_0,
author = {Abdelghany, Mohammed and Yahia, Zakaria and Eltawil, Amr B.},
title = {A new two-stage variable neighborhood search algorithm for the nurse rostering problem},
journal = {RAIRO. Operations Research},
pages = {673--687},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
number = {2},
doi = {10.1051/ro/2021027},
mrnumber = {4238788},
zbl = {1472.90153},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2021027/}
}
TY - JOUR AU - Abdelghany, Mohammed AU - Yahia, Zakaria AU - Eltawil, Amr B. TI - A new two-stage variable neighborhood search algorithm for the nurse rostering problem JO - RAIRO. Operations Research PY - 2021 SP - 673 EP - 687 VL - 55 IS - 2 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2021027/ DO - 10.1051/ro/2021027 LA - en ID - RO_2021__55_2_673_0 ER -
%0 Journal Article %A Abdelghany, Mohammed %A Yahia, Zakaria %A Eltawil, Amr B. %T A new two-stage variable neighborhood search algorithm for the nurse rostering problem %J RAIRO. Operations Research %D 2021 %P 673-687 %V 55 %N 2 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2021027/ %R 10.1051/ro/2021027 %G en %F RO_2021__55_2_673_0
Abdelghany, Mohammed; Yahia, Zakaria; Eltawil, Amr B. A new two-stage variable neighborhood search algorithm for the nurse rostering problem. RAIRO. Operations Research, Tome 55 (2021) no. 2, pp. 673-687. doi: 10.1051/ro/2021027
[1] , and , A proposed new dynamic programming formulation for the nurse rostering problem. In: Proceedings of 47th International Conference on Computers and Industrial Engineering (2017).
[2] , , and , Global best harmony search with a new pitch adjustment designed for nurse rostering. J. King Saud Univ. Comput. Inf. Sci. 25 (2013) 145–162.
[3] , and , A hybrid artificial bee colony for a nurse rostering problem. Appl. Soft Comput. 35 (2015) 726–739. | DOI
[4] and , New approaches to nurse rostering benchmark instances. Eur. J. Oper. Res. 237 (2014) 71–81. | MR | Zbl | DOI
[5] , , and , A time predefined variable depth search for nurse rostering. Informs J. Comput. 25 (2013) 411–419. | DOI
[6] , and , A hybrid model of integer programming and variable neighbourhood search for highly-constrained nurse rostering problems. Eur. J. Oper. Res. 203 (2010) 484–493. | MR | Zbl | DOI
[7] , , , and , Second International Nurse Rostering Competition (INRC-II) – Problem description and rules. Preprint (2015). | arXiv | MR | Zbl
[8] and , Computational results on new staff scheduling benchmark instances. Technical report, ASAP Research Group, School of Computer Science, University of Nottingham (2014). http://schedulingbenchmarks.org/papers/computational_results_on_new_staff_scheduling_benchmark_instances.pdf.
[9] and , Particle swarm optimization based nurses shift scheduling. In: Proceedings of the Institute of Industrial Engineers Asian Conference (2013) 775–782. | DOI
[10] and , The nurse rostering problem: a critical appraisal of the problem structure. Eur. J. Oper. Res. 202 (2010) 379–389. | Zbl | DOI
[11] , , and , A harmony search algorithm for nurse rostering problems. Inf. Sci. 233 (2013) 126–140. | MR | DOI
[12] , , and , The first international nurse rostering competition 2010. Ann. Oper. Res. 218 (2014) 221–236. | MR | Zbl | DOI
[13] , , , and , Cooperative search for fair nurse rosters. Expert Syst. App. 40 (2013) 6674–6683. | DOI
[14] and , Scheduling of nurses: a case study of a Kuwaiti health care unit. Oper. Res. Health Care 2 (2013) 1–19. | DOI
[15] , and , Automatic scheduling of nurses: What does it take in practice? In: Systems Analysis Tools for Better Health Care Delivery (2013) 151–178. | DOI
[16] , and , A two-phase adaptive variable neighborhood approach for nurse rostering. Comput. Oper. Res. 60 (2015) 150–169. | MR | Zbl | DOI
[17] , , , and , A systematic two phase approach for the nurse rostering problem. Eur. J. Oper. Res. 219 (2012) 425–433. | MR | Zbl | DOI
[18] , and , A two-stage heuristic approach for nurse scheduling problem: a case study in an emergency department. Comput. Oper. Res. 51 (2014) 99–110. | MR | Zbl | DOI
[19] World Health Organization, Nursing and midwifery. http://www.who.int/mediacentre/factsheets/nursing-midwifery/en/ (2018).
[20] , and , A particle swarm optimization approach with refinement procedure for nurse rostering problem. Comput. Oper. Res. 54 (2015) 52–63. | MR | Zbl | DOI
[21] and , Chemical reaction optimization for nurse rostering problem. In: Frontier and Future Development of Information Technology in Medicine and Education (2014) 3275–3279.
[22] and , Adaptive neighborhood search for nurse rostering. Eur. J. Oper. Res. 218 (2012) 865–876. | DOI
Cité par Sources :
