A hybrid variable neighbourhood search and dynamic programming approach for the nurse rostering problem

Mohammed Abdelghany; Amr B. Eltawil; Zakaria Yahia; Kazuhide Nakata

doi:10.3934/jimo.2020058

Article Contents

2021, Volume 17, Issue 4: 2051-2072. Doi: 10.3934/jimo.2020058

This issue Previous Article Selecting the supply chain financing mode under price-sensitive demand: Confirmed warehouse financing vs. trade credit Next Article Multiobjective mathematical models and solution approaches for heterogeneous fixed fleet vehicle routing problems

A hybrid variable neighbourhood search and dynamic programming approach for the nurse rostering problem

1.
Industrial Engineering and Systems Management, Egypt-Japan University of Science and Technology, New Borg Elarab City, Alexandria 21934, Egypt
2.
Mechanical Engineering Department, Faculty of Engineering, Fayoum University, Fayoum, Egypt
3.
Industrial Engineering and Economics, School of Engineering, Tokyo Institute of Technology, Tokyo, Japan

^* Corresponding author: Mohammed Abdelghany
^* Corresponding author: Mohammed Abdelghany

Received: November 30, 2018

Revised: November 30, 2019

Early access: March 2020

Published: July 2021

Abstract Full Text(HTML) Figure(8) / Table(6) Related Papers Cited by

Abstract

Nurse Rostering is the activity of assigning nurses to daily shifts in order to satisfy the cover requirements, taking into account the operational requirements and nurses' preferences. The problem is usually modeled as sets of hard and soft constraints with an objective function to minimize violations of soft constraints. The nurse rostering problem is known to be NP-hard. Many metaheuristics were used to tackle this problem. One of the frequently used heuristics is the Variable Neighbourhood Search (VNS). The VNS is usually used as a standalone method or in integration with another exact or heuristic method. In this paper, a new hybrid VNS and Dynamic Programming based heuristic approach is proposed to handle the nurse rostering problem. In the proposed approach, two perturbation mechanisms are adopted simultaneously. The proposed approach is tested on two different benchmark data sets. A comparison with state-of-the-art methods from literature revealed the competitive performance of the proposed approach.

Keywords:

Mathematics Subject Classification: Primary: 90B35; Secondary: 90C59, 90C39.

Citation:

Full Text(HTML)

Figure 1. Pseudo code for the hybrid VNS-DP approach

Download: Full-size image PowerPoint slide

Figure 2. Pseudo code for VNS algorithm

Download: Full-size image PowerPoint slide

Figure 3. Example for HWCF.1 structure

Download: Full-size image PowerPoint slide

Figure 4. Example for HWCF.2 structure

Download: Full-size image PowerPoint slide

Figure 5. Examples of vertical swaps

Download: Full-size image PowerPoint slide

Figure 6. Examples of horizontal swaps

Download: Full-size image PowerPoint slide

Figure 7. A dynamic programming structure for the nurse rostering problem

Download: Full-size image PowerPoint slide

Figure 8. Pseudo code for the proposed Dynamic Programming based heuristic algorithm

Download: Full-size image PowerPoint slide

Table 1. Benchmark instances main characteristics

#	Days	Nurses	Shift types	Days-off	Shifts on/off
01	14	8	1	8	26
02	14	14	2	14	62
03	14	20	3	20	64
04	28	10	2	20	71
05	28	16	2	32	106
06	28	18	3	36	135
07	28	20	3	40	168
08	28	30	4	60	225
09	28	36	4	72	232
10	28	40	5	80	284
11	28	50	6	100	336
12	28	60	10	120	422
13	28	120	18	240	841
14	42	32	4	128	359
15	42	45	6	180	490
16	56	20	3	120	280
17	56	30	4	160	480
18	84	22	3	176	414
19	84	40	5	320	834
20	182	50	6	900	2318
21	182	100	8	1800	4702
22	364	50	10	1800	4638
23	364	100	16	3600	9410
24	364	150	32	5400	13809

| Show Table

DownLoad: CSV

Table 2. Comparison for the performance of the VNS algorithm using classical and destroy-and-recreate perturbation mechanisms

Instance	Classical mechanism	Destroy-and-recreate mechanism
01	607	607
02	828	922
03	1001	1002
04	1721	1717
05	1249	1330
06	2053	2147
07	1077	1073
08	1425	1741
09	449	446
10	4679	4320
11	3458	3513
12	4217	4327
13	2423	2396
14	1377	1584
15	4996	5017
16	3550	3556
17	6391	6506
18	5177	5601
19	4789	5177
20	9097	7689
21	29486	27071
22	61690	58226
23	62195	53694
24	402313	248016

| Show Table

DownLoad: CSV

Table 3. Comparison between the proposed VNS–DP approach and other methods in literature

Instance	VNS–DP	Ejection chain	Gurobi	Branch & price	CP–ILS
01	607	607	607	607	607
02	828	837	828	828	828
03	1001	1003	1001	1001	1001
04	1716	1718	1716	1716	1716
05	1237	1358	1143	1160	1147
06	2141	2258	1950	1952	2050
07	1080	1269	1056	1058	1084
08	1452	2260	1306	1308	1464
09	446	463	439	439	454
10	4656	4797	4631	4631	4667
11	3512	3661	3443	3443	3457
12	4119	5211	4040	4046	4308
13	2120	2663	3109	–	2961
14	1344	1847	1278	–	1432
15	4637	5935	4843	–	4570
16	3458	4048	3225	3323	3748
17	6190	7835	5749	–	6609
18	5095	6404	4760	–	5416
19	4281	5531	5078	–	4364
20	7274	9750	3591	–	6654
21	26263	36688	132445	–	22549
22	56091	516686	265504	–	48382
23	51699	54384	–	–	38337
24	226490	156858	–	–	177037

| Show Table

DownLoad: CSV

Table 4. Comparison between the proposed VNS-DP approach and IP-VNS approach

Instance	VNS–DP	IP–VNS
01	607	607
02	828	828
03	1001	1001
04	1716	1716
05	1237	1143
06	2141	1950
07	1080	1056
08	1452	1344
09	446	439
10	4656	4631
11	3512	3443
12	4119	4040
13	2120	1905
14	1344	1279
15	4637	3928
16	3458	3225
17	6190	5750
18	5095	4662
19	4281	3224
20	7274	4913
21	26263	23191
22	56091	32126
23	51699	3794
24	226490	2281440

| Show Table

DownLoad: CSV

Table 5. Comparison between results of the proposed VNS-DP approach and other state-of-the-art approaches tested on the competition instances

Instance	BKS	VNS–DP	ANS	VDS	RVNS	HHSA
Sprint_early01	56	56	56	56	56	56
Sprint_early02	58	58	58	58	58	58
Sprint_early03	51	51	51	51	51	51
Sprint_early04	59	59	59	59	59	59
Sprint_early05	58	58	58	58	58	58
Sprint_early06	54	54	54	54	54	54
Sprint_early07	56	56	56	56	56	56
Sprint_early08	56	56	56	56	56	56
Sprint_early09	55	55	55	55	55	55
Sprint_early10	52	52	52	52	52	52
Sprint_late01	37	37	37	37	37	37
Sprint_late02	42	42	42	42	42	42
Sprint_late03	48	48	48	48	48	48
Sprint_late04	73	73	73	75	73	73
Sprint_late05	44	45	44	44	44	44
Sprint_late06	42	43	42	42	42	42
Sprint_late07	42	47	42	42	43	43
Sprint_late08	17	17	17	17	17	17
Sprint_late09	17	17	17	17	17	17
Sprint_late10	43	44	43	43	43	43
Sprint_hidden01	32	34	32	–	32	32
Sprint_hidden02	32	32	32	–	32	32
Sprint_hidden03	62	62	62	–	62	62
Sprint_hidden04	66	67	66	–	66	66
Sprint_hidden05	59	59	59	–	59	59
Sprint_hidden06	130	141	130	–	–	130
Sprint_hidden07	153	153	153	–	–	153
Sprint_hidden08	204	204	204	–	–	204
Sprint_hidden09	338	338	338	–	–	338
Sprint_hidden10	306	306	306	–	–	306
Medium_early01	240	243	240	244	240	243
Medium_early02	240	241	240	241	240	242
Medium_early03	236	238	236	238	236	238
Medium_early04	237	240	237	240	237	240
Medium_early05	303	303	303	308	303	305
Medium_late01	157	157	164	187	158	169
Medium_late02	18	31	20	22	20	26
Medium_late03	29	29	30	46	30	34
Medium_late04	35	35	36	49	35	42
Medium_late05	107	140	117	161	111	131
Medium_hidden01	111	111	122	–	117	143
Medium_hidden02	219	219	224	–	225	248
Medium_hidden03	34	34	35	–	34	49
Medium_hidden04	78	78	80	–	79	87
Medium_hidden05	118	118	120	–	122	169
Long_early01	197	197	197	198	197	197
Long_early02	219	221	222	223	219	226
Long_early03	240	240	240	242	240	240
Long_early04	303	303	303	305	303	303
Long_early05	284	284	284	286	284	284
Long_late01	235	240	237	286	235	253
Long_late02	229	229	229	290	229	256
Long_late03	220	220	222	290	221	256
Long_late04	221	221	227	280	224	263
Long_late05	83	89	83	110	83	98
Long_hidden01	346	346	346	–	349	380
Long_hidden02	89	89	89	–	89	110
Long_hidden03	38	38	38	–	38	44
Long_hidden04	22	22	22	–	22	27
Long_hidden05	41	41	45	–	41	53

| Show Table

DownLoad: CSV

Table 6. Comparison for number of best known solutions achieved by each approach

Competition track	VNS–DP	ANS	HHSA
Sprint (30 instances)	77%	100%	97%
Medium (15 instances)	60%	33%	0%
Long (15 instances)	80%	67%	27%

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	M. Abdelgalil, Z. Yahia and A. B. Eltawil, A proposed new dynamic programming formulation for the nurse rostering problem, in Proceedings of 47th International Conference on Computers and Industrial Engineering, 2017, 1–8.
[2]	H. Akita and A. Ikegami, A network representation of feasible solution space for a subproblem of nurse scheduling, Proceedings of the Institute of Statistical Mathematics, 61 (2013), 79-95.
[3]	G. Alpan, R. Larbi and B. Penz, A bounded dynamic programming approach to schedule operations in a cross docking platform, Computers and Industrial Engineering, 60 (2011), 385-396. doi: 10.1016/j.cie.2010.08.012.
[4]	M. A. Awadallah, M. A. Al-Betar, A. T. Khader, A. L. Bolaji and M. Alkoffash, Hybridization of harmony search with hill climbing for highly constrained nurse rostering problem, Neural Computing and Applications, 28 (2017), 463-482. doi: 10.1007/s00521-015-2076-8.
[5]	J. Bautista and J. Pereira, A dynamic programming based heuristic for the assembly line balancing problem, European Journal of Operational Research, 194 (2009), 787-794. doi: 10.1016/j.ejor.2008.01.016.
[6]	F. Bellanti, G. Carello, F. Della Croce and R. Tadei, A greedy-based neighborhood search approach to a nurse rostering problem, European Journal of Operational Research, 153 (2004), 28-40. doi: 10.1016/S0377-2217(03)00096-1.
[7]	S. Bouajaja and N. Dridi, A survey on human resource allocation problem and its applications, Operational Research, 17 (2017), 339-369. doi: 10.1007/s12351-016-0247-8.
[8]	J. D. Bunton, A. T. Ernst and M. Krishnamoorthy, An integer programming based ant colony optimisation method for nurse rostering, Proceedings of the 2017 Federated Conference on Computer Science and Information Systems, 11 (2017), 407-414. doi: 10.15439/2017F237.
[9]	E. Burke, P. De Causmaecker, S. Petrovic and G. V. Berghe, Variable neighborhood search for nurse rostering problems, in Metaheuristics: Computer Decision-Making, Springer, Boston, MA, 2003,153–172. doi: 10.1007/978-1-4757-4137-7_7.
[10]	E. K. Burke, T. Curtois, G. Post, R. Qu and B. Veltman, A hybrid heuristic ordering and variable neighbourhood search for the nurse rostering problem, European Journal of Operational Research, 188 (2008), 330-341. doi: 10.1016/j.ejor.2007.04.030.
[11]	E. K. Burke and T. Curtois, New approaches to nurse rostering benchmark instances, European Journal of Operational Research, 237 (2014), 71-81. doi: 10.1016/j.ejor.2014.01.039.
[12]	E. K. Burke, J. Li and R. Qu, A hybrid model of integer programming and variable neighbourhood search for highly-constrained nurse rostering problems, European Journal of Operational Research, 203 (2010), 484-493. doi: 10.1016/j.ejor.2009.07.036.
[13]	E. K. Burke, T. Curtois, L. F. van Draat, J. Van Ommeren and G. Post, Progress control in iterated local search for nurse rostering, Journal of the Operational Research Society, 62 (2011), 360-367. doi: 10.1057/jors.2010.86.
[14]	S. Ceschia, N. Dang, P. De Causmaecker, S. Haspeslagh and A. Schaerf, Second international nurse rostering competition, Annals of Operations Research, 274 (2019), 171–186, arXiv: 1501.04177. doi: 10.1007/s10479-018-2816-0.
[15]	T. Curtois and R. Qu, Technical Report: Computational Results on New Staff Scheduling Benchmark Instances, ASAP Research Group, School of Computer Science, University of Nottingham, UK, 2014.
[16]	F. Della Croce and F. Salassa, A variable neighborhood search based matheuristic for nurse rostering problems, Annals of Operations Research, 218 (2014), 185-199. doi: 10.1007/s10479-012-1235-x.
[17]	J. Van den Bergh, J. Beliën, P. De Bruecker, E. Demeulemeester and L. De Boeck, Personnel scheduling: A literature review, European Journal of Operational Research, 226 (2013), 367-385. doi: 10.1016/j.ejor.2012.11.029.
[18]	S. C. Gao and C. W. Lin, Particle swarm optimization based nurses' shift scheduling, in Proceedings of the Institute of Industrial Engineers Asian Conference 2013, 2013,775–782. doi: 10.1007/978-981-4451-98-7_93.
[19]	R. A. M. Gomes, T. A. M. Toffolo and H. G. Santos, Variable neighborhood search accelerated column generation for the nurse rostering problem, Electronic Notes in Discrete Mathematics, 58 (2017), 31-38. doi: 10.1016/j.endm.2017.03.005.
[20]	M. Hadwan, M. Ayob, N. R. Sabar and R. Qu, A harmony search algorithm for nurse rostering problems, Information Sciences, 233 (2013), 126-140. doi: 10.1016/j.ins.2012.12.025.
[21]	S. Haspeslagh, P. De Causmaecker, A. Schaerf and M. Stølevik, The first international nurse rostering competition 2010, Annals of Operations Research, 218 (2014), 221-236. doi: 10.1007/s10479-012-1062-0.
[22]	F. Knust and L. Xie, Simulated annealing approach to nurse rostering benchmark and real-world instances, Annals of Operations Research, 272 (2019), 187-216. doi: 10.1007/s10479-017-2546-8.
[23]	Z. Lü and J.-K. Hao, Adaptive neighborhood search for nurse rostering, European Journal of Operational Research, 218 (2012), 865-876.
[24]	R. M'Hallah and A. Alkhabbaz, Scheduling of nurses: A case study of a Kuwaiti health care unit, Operations Research for Health Care, 2 (2013), 1-19. doi: 10.1016/j.orhc.2013.03.003.
[25]	N. Musliu and F. Winter, A hybrid approach for the sudoku problem: Using constraint programming in iterated local search, IEEE Intelligent Systems, 32 (2017), 52-62. doi: 10.1109/MIS.2017.29.
[26]	F. Mischek and N. Musliu, Integer programming model extensions for a multi-stage nurse rostering problem, Annals of Operations Research, 275 (2019), 123-143. doi: 10.1007/s10479-017-2623-z.
[27]	E. Rahimian, K. Akartunali and J. Levine, A hybrid integer programming and variable neighbourhood search algorithm to solve nurse rostering problems, European Journal of Operational Research, 258 (2017), 411-423. doi: 10.1016/j.ejor.2016.09.030.
[28]	E. Rahimian, K. Akartunali and J. Levine, A hybrid integer and constraint programming approach to solve nurse rostering problems, Computers and Operations Research, 82 (2017), 83-94. doi: 10.1016/j.cor.2017.01.016.
[29]	H. G. Santos, T. A. M. Toffolo, R. A. M. Gomes and S. Ribas, Integer programming techniques for the nurse rostering problem, Annals of Operations Research, 239 (2016), 225-251. doi: 10.1007/s10479-014-1594-6.
[30]	A. M. Shahidin, M. S. M. Said, N. H. M. Said and N. I. A. Sazali, Developing optimal nurses work schedule using integer programming, AIP Conference Proceedings, 1870 (2017), 040031. doi: 10.1063/1.4995863.
[31]	P. Smet, P. Brucker, P. D. Causmaecker and G. V. Berghe, Polynomially solvable personnel rostering problems, European Journal of Operational Research, 249 (2016), 67-75. doi: 10.1016/j.ejor.2015.08.025.
[32]	I. P. Solos, I. X. Tassopoulos and G. N. Beligiannis, A generic two-phase stochastic variable neighborhood approach for effectively solving the nurse rostering problem, Algorithms, 6 (2013), 278-308. doi: 10.3390/a6020278.
[33]	I. X. Tassopoulos, I. P. Solos and G. N. Beligiannis, A two-phase adaptive variable neighborhood approach for nurse rostering, Computers and Operations Research, 60 (2015), 150-169. doi: 10.1016/j.cor.2015.02.009.
[34]	T.-H. Wu, J.-Y. Yeh and Y.-M. Lee, A particle swarm optimization approach with refinement procedure for nurse rostering problem, Computers and Operations Research, 54 (2015), 52-63. doi: 10.1016/j.cor.2014.08.016.
[35]	Z. Zheng and X. Gong, Chemical reaction optimization for nurse rostering problem,, in Frontier and Future Development of Information Technology in Medicine and Education, Springer, Dordrecht, 2014, 3275–3279. doi: 10.1007/978-94-007-7618-0_422.
[36]	Z. Zheng, X. Liu and X. Gong, A simple randomized variable neighbourhood search for nurse rostering, Computers and Industrial Engineering, 110 (2017), 165-174. doi: 10.1016/j.cie.2017.05.027.
[37]	, Instances & Results – Nurse Rostering Competition, (Accessed: April 25, 2019), https://www.kuleuven-kulak.be/nrpcompetition/instances-results.