Метод снижения временных затрат при решении NP-сложных задач оптимизации в распределенных вычислительных средах
https://doi.org/10.17586/0021-3454-2024-67-11-935-942
Аннотация
Обсуждаются вопросы решения целочисленных, смешанно-целочисленных многокритериальных задач оптимизации с нелинейными ограничениями. Цель исследования — снижение временных затрат на решение таких задач с применением метаэвристических алгоритмов в распределенной гетерогенной вычислительной среде, предоставляющей вычислительные ресурсы. Новизна предлагаемого метода заключается в выборе способа параллельного выполнения метаэвристических алгоритмов, формирования блоков вычислительной нагрузки, реализующих метаэвристики, и назначении блоков на вычислительные ресурсы в гетерогенной распределенной вычислительной среде с использованием репозитория эффективных алгоритмов. Приведены результаты экспериментального исследования, демонстрирующие эффективность разработанного метода.
Об авторах
Р. В. Мещеряков
Институт проблем управления им. В. А. Трапезникова Российской академии наук
Россия
Россия
Роман Валерьевич Мещеряков — д-р техн. наук, профессор РАН; лаборатория киберфизических систем; гл. научный сотрудник
А. Б. Клименко
Российский государственный гуманитарный университет
Россия
Россия
Анна Борисовна Клименко — канд. техн. наук; Институт информационных наук и технологий безопасности, кафедра фундаментальной и прикладной математики; доцент
Список литературы
1. Klimenko A., Barinov A. Multicriteria task distribution problem for resource-saving data processing//Lecture Notes in Computer Science. 2023. P. 166–176. DOI: 10.1007/978-3-031-41673-6_13.
2. Hameed T. et al. Efficient resource scheduling in fog: A multi-objective optimization approach // Proc. of the Pakistan Academy of Sciences: A. Physical and Computational Sciences. 2024. N 61 (1). DOI: 10.53560/ppasa(60-1)674.
3. Li S. et al.: Non-convex optimization of resource allocation in fog computing using successive approximation // Journal Syst. Sci. Complex. 2024. N 37 (2). P. 805–840. DOI: 10.1007/s11424-024-2038-2.
4. Singh K. D., Singh P. D. Machine Learning in Robotics with Fog/Cloud Computing and IoT// EAI Endorsed Trans AI Robotics. 2023. N 2.
5. Alqam S. et al. Reinforcement learning-driven decision-making for live virtual machine migration in fog computing // Journal Eng. Res. 2024. N 20 (2). P. 113–122. DOI: 10.53540/tjer.vol20iss2pp113-122.
6. Panahi F. H. et al. An intelligent path planning mechanism for firefighting in wireless sensor and actor networks // IEEE Internet Things Journal. 2023. N 10 (1). P. 9646–9661. DOI: 10.1109/jiot.2023.3235998.
7. Choudhary A., Rajak R. A novel strategy for deterministic workflow scheduling with load balancing using modified min-min heuristic in cloud computing environment // Cluster Computing. 2024. DOI: 10.1007/s10586-024-04307-8.
8. Uddin F. et al. An improvement to the 2-Opt heuristic algorithm for approximation of optimal TSP tour // Appl. Sci. 2023. N 13 (12). P. 7339. DOI: 10.3390/app13127339.
9. Donoso Y., Fabregat R. Multi-objective optimization in computer networks using metaheuristics. Boca Raton, Fl.: Auerbach Publications, 2016.
10. Xiao J. et al. A metaheuristic-based modularity optimization algorithm driven by edge directionality for directed networks // IEEE Trans. Netw. Sci. Eng. 2023. N 1–14. DOI: 10.1109/tnse.2023.3274173.
11. Cho W. K. T., Liu Y. Y. Parallel hybrid metaheuristics with distributed intensification and diversification for large-scale optimization in big data statistical analysis // IEEE. 2019.
12. Yang H. et al. An improved spherical evolution with enhanced exploration capabilities to address wind farm layout optimization problem // Eng. Appl. Artif. Intell. 2023. N 123. P. 106198. DOI: 10.1016/j.engappai.2023.106198.
13. Algin R. et al. Enhanced migrating birds optimization algorithm for optimization problems in different domains // Annual. Oper. Res. 2024. DOI: 10.1007/s10479-024-05992-9.
14. Zhang H. et al. Leader federated learning optimization using deep reinforcement learning for distributed satellite edge intelligence // IEEE Trans. Serv. Comput. 2024. N 1–14. DOI: 10.1109/tsc.2024.3376256.
15. He Y. et al. Distributed bilevel optimization with communication compression // arXiv [math.OC]. 2024.
16. Oszust M., Wysocki M. A distributed immune algorithm for solving optimization problems // Studies in Computational Intelligence. Berlin / Heidelberg: Springer-Verlag, 2008. Vol. 162. P. 147–155.
17. Abdelhafez A. et al. Systematic literature review on parallel trajectory-based metaheuristics// Swarm Evol. Comput. 2023. N 55.
18. Coelho P., Silva C. Parallel Metaheuristics for Shop Scheduling: enabling Industry 4.0 // Procedia Comput. Sci. 2021. N 180. P. 778–786. DOI: 10.1016/j.procs.2021.01.328.
19. Parallel GPU-accelerated metaheuristics // Designing Scientific Applications on GPUs. Chapman and Hall/CRC, 2013. P. 205–236.
20. Testa A. et al. A tutorial on distributed optimization for cooperative robotics: From setups and algorithms to toolboxes and research directions // arxiv.org/abs/2309.04257. 2023.
21. Testa A., Notarstefano G. Generalized assignment for multi-robot systems via distributed branch-and-price // IEEE Trans. Robot. 2022. N 38 (3). P. 1990–2001. DOI: 10.1109/tro.2021.3120046.
22. Mosteo A. R. et al. Optimal role and position assignment in multi-robot freely reachable formations // Automatica. 2017. N 81. P. 305–313. DOI: 10.1016/j.automatica.2017.03.040.
23. Bai X. et al.: Efficient routing for precedence-constrained package delivery for heterogeneous vehicles // IEEE Trans. Autom. Sci. Eng. 2020. N 17 (1). P. 248–260. DOI: 10.1109/tase.2019.2914113.
24. Hartuv E. et al. Scheduling spare drones for persistent task performance under energy constraints // Intern. Conf. on Autonomous Agents and MultiAgent Systems. 2018. P. 532–540.
25. Gopinath S., Natesh T. C. Development of interdependent resource management system for construction project using genetic algorithm // Lecture Notes in Civil Engineering. Singapore, 2024. P. 541–550.
26. Mijuskovic A. et al. Resource management techniques for cloud/fog and edge computing: An evaluation framework and classification // Sensors. 2021. N 21 (5). P. 1832. DOI: 10.3390/s21051832.
Рецензия
Для цитирования:
Мещеряков Р.В., Клименко А.Б. Метод снижения временных затрат при решении NP-сложных задач оптимизации в распределенных вычислительных средах. Известия высших учебных заведений. Приборостроение. 2024;67(11):935-942. https://doi.org/10.17586/0021-3454-2024-67-11-935-942
For citation:
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
Просмотров:
33
Послать статью по эл. почте 