
-
Previous Article
Second-Order characterizations for set-valued equilibrium problems with variable ordering structures
- JIMO Home
- This Issue
-
Next Article
Impact of cap-and-trade regulation on coordinating perishable products supply chain with cost learning
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 |
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.
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.
|
[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. 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. |
[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. 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. |
[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. 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.
|
[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. 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. |
[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. 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. |
[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. Google Scholar |








# | 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 |
# | 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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
Competition track | VNS–DP | ANS | HHSA |
Sprint (30 instances) | 77% | 100% | 97% |
Medium (15 instances) | 60% | 33% | 0% |
Long (15 instances) | 80% | 67% | 27% |
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] |
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, 2021, 17 (2) : 827-839. doi: 10.3934/jimo.2019136 |
[2] |
Mahdi Karimi, Seyed Jafar Sadjadi. Optimization of a Multi-Item Inventory model for deteriorating items with capacity constraint using dynamic programming. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2021013 |
[3] |
Tomáš Smejkal, Jiří Mikyška, Jaromír Kukal. Comparison of modern heuristics on solving the phase stability testing problem. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1161-1180. doi: 10.3934/dcdss.2020227 |
[4] |
Jong Yoon Hyun, Boran Kim, Minwon Na. Construction of minimal linear codes from multi-variable functions. Advances in Mathematics of Communications, 2021, 15 (2) : 227-240. doi: 10.3934/amc.2020055 |
[5] |
Elvio Accinelli, Humberto Muñiz. A dynamic for production economies with multiple equilibria. Journal of Dynamics & Games, 2021 doi: 10.3934/jdg.2021002 |
[6] |
M. S. Lee, H. G. Harno, B. S. Goh, K. H. Lim. On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 45-61. doi: 10.3934/naco.2020014 |
[7] |
Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020 doi: 10.3934/naco.2020054 |
[8] |
Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102 |
[9] |
Pablo Neme, Jorge Oviedo. A note on the lattice structure for matching markets via linear programming. Journal of Dynamics & Games, 2020 doi: 10.3934/jdg.2021001 |
[10] |
Ke Su, Yumeng Lin, Chun Xu. A new adaptive method to nonlinear semi-infinite programming. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2021012 |
[11] |
Editorial Office. Retraction: Jinling Wei, Jinming Zhang, Meishuang Dong, Fan Zhang, Yunmo Chen, Sha Jin and Zhike Han, Applications of mathematics to maritime search. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 957-957. doi: 10.3934/dcdss.2019064 |
[12] |
Chao Xing, Zhigang Pan, Quan Wang. Stabilities and dynamic transitions of the Fitzhugh-Nagumo system. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 775-794. doi: 10.3934/dcdsb.2020134 |
[13] |
P. K. Jha, R. Lipton. Finite element approximation of nonlocal dynamic fracture models. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1675-1710. doi: 10.3934/dcdsb.2020178 |
[14] |
Marcos C. Mota, Regilene D. S. Oliveira. Dynamic aspects of Sprott BC chaotic system. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1653-1673. doi: 10.3934/dcdsb.2020177 |
[15] |
Shasha Hu, Yihong Xu, Yuhan Zhang. Second-Order characterizations for set-valued equilibrium problems with variable ordering structures. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2020164 |
[16] |
Kengo Nakai, Yoshitaka Saiki. Machine-learning construction of a model for a macroscopic fluid variable using the delay-coordinate of a scalar observable. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1079-1092. doi: 10.3934/dcdss.2020352 |
[17] |
Sergey E. Mikhailov, Carlos F. Portillo. Boundary-domain integral equations equivalent to an exterior mixed bvp for the variable-viscosity compressible stokes pdes. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021009 |
[18] |
Ali Mahmoodirad, Harish Garg, Sadegh Niroomand. Solving fuzzy linear fractional set covering problem by a goal programming based solution approach. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2020162 |
[19] |
Bahaaeldin Abdalla, Thabet Abdeljawad. Oscillation criteria for kernel function dependent fractional dynamic equations. Discrete & Continuous Dynamical Systems - S, 2020 doi: 10.3934/dcdss.2020443 |
[20] |
Kevin Li. Dynamic transitions of the Swift-Hohenberg equation with third-order dispersion. Discrete & Continuous Dynamical Systems - B, 2020 doi: 10.3934/dcdsb.2021003 |
2019 Impact Factor: 1.366
Tools
Metrics
Other articles
by authors
[Back to Top]