American Institute of Mathematical Sciences

Advanced
doi: 10.3934/jimo.2020058

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

Mohammed Abdelghany 1,, , Amr B. Eltawil 1, , Zakaria Yahia 2, and  Kazuhide Nakata 3,

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

Received  December 2018 Revised  December 2019 Published  March 2020

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: Variable neighbourhood search, heuristics, dynamic programming, nurse rostering, timetabling.
Mathematics Subject Classification: Primary: 90B35; Secondary: 90C59, 90C39.
Citation: Mohammed Abdelghany, Amr B. Eltawil, Zakaria Yahia, Kazuhide Nakata. A hybrid variable neighbourhood search and dynamic programming approach for the nurse rostering problem. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2020058
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. Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[23]

Z. Lü and J.-K. Hao, Adaptive neighborhood search for nurse rostering, European Journal of Operational Research, 218 (2012), 865-876.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[37]

, Instances & Results – Nurse Rostering Competition, (Accessed: April 25, 2019), https://www.kuleuven-kulak.be/nrpcompetition/instances-results. Google Scholar

show all references

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. Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[23]

Z. Lü and J.-K. Hao, Adaptive neighborhood search for nurse rostering, European Journal of Operational Research, 218 (2012), 865-876.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[37]

, Instances & Results – Nurse Rostering Competition, (Accessed: April 25, 2019), https://www.kuleuven-kulak.be/nrpcompetition/instances-results. Google Scholar

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

Download full-size image

Download as PowerPoint slide

Figure 2.  Pseudo code for VNS algorithm
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  Example for HWCF.1 structure
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.  Example for HWCF.2 structure
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5.  Examples of vertical swaps
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 6.  Examples of horizontal swaps
Figure Options

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as 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
Table Options

Download as excel

# 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
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
Table Options

Download as excel

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
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
Table Options

Download as excel

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
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
Table Options

Download as excel

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
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
Table Options

Download as excel

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
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%
Table Options

Download as excel

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

Ryan Loxton, Qun Lin. Optimal fleet composition via dynamic programming and golden section search. Journal of Industrial & Management Optimization, 2011, 7 (4) : 875-890. doi: 10.3934/jimo.2011.7.875
[2]

Andrzej Nowakowski, Jan Sokolowski. On dual dynamic programming in shape control. Communications on Pure & Applied Analysis, 2012, 11 (6) : 2473-2485. doi: 10.3934/cpaa.2012.11.2473
[3]

Jérôme Renault. General limit value in dynamic programming. Journal of Dynamics & Games, 2014, 1 (3) : 471-484. doi: 10.3934/jdg.2014.1.471
[4]

Nur Aidya Hanum Aizam, Louis Caccetta. Computational models for timetabling problem. Numerical Algebra, Control & Optimization, 2014, 4 (3) : 269-285. doi: 10.3934/naco.2014.4.269
[5]

Oliver Junge, Alex Schreiber. Dynamic programming using radial basis functions. Discrete & Continuous Dynamical Systems - A, 2015, 35 (9) : 4439-4453. doi: 10.3934/dcds.2015.35.4439
[6]

Eduardo Espinosa-Avila, Pablo Padilla Longoria, Francisco Hernández-Quiroz. Game theory and dynamic programming in alternate games. Journal of Dynamics & Games, 2017, 4 (3) : 205-216. doi: 10.3934/jdg.2017013
[7]

Rein Luus. Optimal control of oscillatory systems by iterative dynamic programming. Journal of Industrial & Management Optimization, 2008, 4 (1) : 1-15. doi: 10.3934/jimo.2008.4.1
[8]

Qing Liu, Armin Schikorra. General existence of solutions to dynamic programming equations. Communications on Pure & Applied Analysis, 2015, 14 (1) : 167-184. doi: 10.3934/cpaa.2015.14.167
[9]

Peng Guo, Wenming Cheng, Yi Wang. A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1071-1090. doi: 10.3934/jimo.2014.10.1071
[10]

Abdel-Rahman Hedar, Alaa Fahim. Filter-based genetic algorithm for mixed variable programming. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 99-116. doi: 10.3934/naco.2011.1.99
[11]

Behrad Erfani, Sadoullah Ebrahimnejad, Amirhossein Moosavi. An integrated dynamic facility layout and job shop scheduling problem: A hybrid NSGA-II and local search algorithm. Journal of Industrial & Management Optimization, 2020, 16 (4) : 1801-1834. doi: 10.3934/jimo.2019030
[12]

Tengfei Yan, Qunying Liu, Bowen Dou, Qing Li, Bowen Li. An adaptive dynamic programming method for torque ripple minimization of PMSM. Journal of Industrial & Management Optimization, 2019  doi: 10.3934/jimo.2019136
[13]

Haiying Liu, Wenjie Bi, Kok Lay Teo, Naxing Liu. Dynamic optimal decision making for manufacturers with limited attention based on sparse dynamic programming. Journal of Industrial & Management Optimization, 2019, 15 (2) : 445-464. doi: 10.3934/jimo.2018050
[14]

Min Sha. Heuristics of the Cocks-Pinch method. Advances in Mathematics of Communications, 2014, 8 (1) : 103-118. doi: 10.3934/amc.2014.8.103
[15]

Matthew H. Henry, Yacov Y. Haimes. Robust multiobjective dynamic programming: Minimax envelopes for efficient decisionmaking under scenario uncertainty. Journal of Industrial & Management Optimization, 2009, 5 (4) : 791-824. doi: 10.3934/jimo.2009.5.791
[16]

Haibo Jin, Long Hai, Xiaoliang Tang. An optimal maintenance strategy for multi-state systems based on a system linear integral equation and dynamic programming. Journal of Industrial & Management Optimization, 2020, 16 (2) : 965-990. doi: 10.3934/jimo.2018188
[17]

Jeongmin Han. Local Lipschitz regularity for functions satisfying a time-dependent dynamic programming principle. Communications on Pure & Applied Analysis, 2020, 19 (5) : 2617-2640. doi: 10.3934/cpaa.2020114
[18]

Martino Bardi, Shigeaki Koike, Pierpaolo Soravia. Pursuit-evasion games with state constraints: dynamic programming and discrete-time approximations. Discrete & Continuous Dynamical Systems - A, 2000, 6 (2) : 361-380. doi: 10.3934/dcds.2000.6.361
[19]

Silvia Faggian. Boundary control problems with convex cost and dynamic programming in infinite dimension part II: Existence for HJB. Discrete & Continuous Dynamical Systems - A, 2005, 12 (2) : 323-346. doi: 10.3934/dcds.2005.12.323
[20]

Guy Barles, Ariela Briani, Emmanuel Trélat. Value function for regional control problems via dynamic programming and Pontryagin maximum principle. Mathematical Control & Related Fields, 2018, 8 (3&4) : 509-533. doi: 10.3934/mcrf.2018021

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (56)
  • HTML views (279)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences