Method for Reducing Time Costs in Solving NP-Hard Optimization Problems in Distributed Computing Environments
https://doi.org/10.17586/0021-3454-2024-67-11-935-942
Abstract
The issues of solving integer, mixed-integer multicriterial optimization problems with nonlinear constraints are discussed. The aim of the study is to reduce the time costs for solving such problems using metaheuristic algorithms in a distributed heterogeneous computing environment that provides computing resources. The novelty of the proposed approach lies in the choice of a method for parallel execution of metaheuristic algorithms, the formation of computational load blocks that implement metaheuristics, and the assignment of blocks to computing resources in a heterogeneous distributed computing environment using a repository of effective algorithms. Results of an experimental study demonstrating the developed method effectiveness are presented.
About the Authors
R. V. Meshcheryakov
V. A. Trapeznikov Institute of Control Sciences of the RAS
Russian Federation
Russian Federation
Roman V. Meshcheryakov — Dr. Sci., Professor; Laboratory of Cyberphysical Systems; Chief Researcher
А. B. Klimenko
Russian State University for the Humanities
Russian Federation
Russian Federation
Anna B. Klimenko — PHD; Institute of IT and Security Technologies, Department of Fundamental and Applied Mathematics; Associate Professor
References
1. Klimenko A., Barinov A. Lecture Notes in Computer Science, Springer Nature Switzerland, Cham, 2023, pp. 166–176, https://doi.org/10.1007/978-3-031-41673-6_13.
2. Hameed T. et al. Proceedings of the Pakistan Academy of Sciences: A. Physical and Computational Sciences, 2024, no. 1(61), https://doi.org/10.53560/ppasa(60-1)674.
3. Li S. et al. J. Syst. Sci. Complex, 2024, no. 2(37), pp. 805–840, https://doi.org/10.1007/s11424-024-2038-2.
4. Singh K.D., Singh P.D. EAI Endorsed Trans AI Robotics, 2023, no. 2.
5. Alqam S. et al. J. Eng. Res., 2024, no. 2(20), pp. 113–122, https://doi.org/10.53540/tjer.vol20iss2pp113-122.
6. Panahi F.H. et al. IEEE Internet Things J., 2023, no. 11(10), pp. 9646–9661, https://doi.org/10.1109/jiot.2023.3235998.
7. Choudhary A., Rajak R. Cluster computing, 2024, https://doi.org/10.1007/s10586-024-04307-8.
8. Uddin F. et al. Appl. Sci. (Basel), 2023, no. 12(13), pp. 7339, https://doi.org/10.3390/app13127339.
9. Donoso Y., Fabregat R. Multi-objective optimization in computer networks using metaheuristics, Auerbach Publications, 2016, 468 p., DOI:10.1201/9781420013627.
10. Xiao J. et al. IEEE Trans. Netw. Sci. Eng., 2023, рр. 1–14, https://doi.org/10.1109/tnse.2023.3274173.
11. Cho W.K.T., Liu Y.Y. IEEE International Conference on Big Data (Big Data), 2019, DOI:10.1109/BigData47090.2019.9006045.
12. Yang H. et al. Eng. Appl. Artif. Intell., 2023, vol. 123, art. no. 106198, https://doi.org/10.1016/j.engappai.2023.106198.
13. Algin R. et al. Ann. Oper. Res., 2024, https://doi.org/10.1007/s10479-024-05992-9.
14. Zhang H. et al. IEEE Trans. Serv. Comput., 2024, рр. 1–14, https://doi.org/10.1109/tsc.2024.3376256.
15. He Y. et al. arXiv. https://arxiv.org/pdf/2405.18858, 2024.
16. Oszust M., Wysocki M. Studies in Computational Intelligence, Springer, Berlin Heidelberg, 2008, pp. 147–155.
17. Abdelhafez A. et al. Swarm Evol. Comput., 2023, vol. 55, art. no.100692.
18. Coelho P., Silva C. Procedia Comput. Sci., 2021, vol. 180, рр. 778–786, https://doi.org/10.1016/j.procs.2021.01.328.
19. Parallel GPU-accelerated metaheuristics, Designing Scientific Applications on GPUs, Chapman and Hall/CRC, 2013, pp. 205–236.
20. Testa A. et al., http://arxiv.org/abs/2309.04257, 2023.
21. Testa A., Notarstefano G. IEEE Trans. Robot., 2022, no. 3(38), pp. 1990–2001, https://doi.org/10.1109/tro.2021.3120046.
22. Mosteo A.R. et al. Automatica (Oxf.), 2017, vol. 81, рр. 305–313, https://doi.org/10.1016/j.automatica.2017.03.040.
23. Bai X. et al. IEEE Trans. Autom. Sci. Eng., 2020, no. 1(17), pp. 248–260, https://doi.org/10.1109/tase.2019.2914113.
24. Hartuv E. et al. Intern. Conf. on Autonomous Agents and MultiAgent Systems, 2018, pp. 532–540.
25. Gopinath S., Natesh T.C. Lecture Notes in Civil Engineering, Springer Nature, Singapore, 2024, pp. 541–550.
26. Mijuskovic A. et al. Sensors (Basel), 2021, no. 5(21), pp. 1832, https://doi.org/10.3390/s21051832.
27.
Review
For citations:
Meshcheryakov R.V., Klimenko А.B. Method for Reducing Time Costs in Solving NP-Hard Optimization Problems in Distributed Computing Environments. Journal of Instrument Engineering. 2024;67(11):935-942. (In Russ.) https://doi.org/10.17586/0021-3454-2024-67-11-935-942
Views:
34
Email this article 