priborИзвестия высших учебных заведений. ПриборостроениеJournal of Instrument Engineering0021-34542500-0381Национальный исследовательский университет ИТМО10.17586/0021-3454-2024-67-11-935-942pribor-311Research ArticleМЕТОДОЛОГИЧЕСКИЕ ОСНОВЫ И ТЕХНОЛОГИИ ПРОАКТИВНОГО УПРАВЛЕНИЯ СЛОЖНЫМИ ОБЪЕКТАМИMETHODOLOGICAL PRINCIPLES AND TECHNOLOGIES OF PROACTIVE CONTROL OF COMPLEX OBJECTSМетод снижения временных затрат при решении NP-сложных задач оптимизации в распределенных вычислительных средахMethod for Reducing Time Costs in Solving NP-Hard Optimization Problems in Distributed Computing EnvironmentsМещеряковР. В.MeshcheryakovR. V.

Роман Валерьевич Мещеряков — д-р техн. наук, профессор РАН; лаборатория киберфизических систем; гл. научный сотрудник

Roman V. Meshcheryakov — Dr. Sci., Professor; Laboratory of Cyberphysical Systems; Chief Researcher

mrv@ipu.ruКлименкоА. Б.KlimenkoА. B.

Анна Борисовна Клименко — канд. техн. наук; Институт информационных наук и технологий безопасности, кафедра фундаментальной и прикладной математики; доцент

Anna B. Klimenko — PHD; Institute of IT and Security Technologies, Department of Fundamental and Applied Mathematics; Associate Professor

anna_klimenko@mail.ruИнститут проблем управления им. В. А. Трапезникова Российской академии наукV. A. Trapeznikov Institute of Control Sciences of the RASРоссийский государственный гуманитарный университетRussian State University for the Humanities2024071220246711935942Copyright © Национальный исследовательский университет ИТМО, 20242024Национальный исследовательский университет ИТМОНациональный исследовательский университет ИТМОhttps://pribor.ifmo.ru/jour/about/submissions#copyrightNoticehttps://pribor.ifmo.ru/jour/article/view/311

Обсуждаются вопросы решения целочисленных, смешанно-целочисленных многокритериальных задач оптимизации с нелинейными ограничениями. Цель исследования — снижение временных затрат на решение таких задач с применением метаэвристических алгоритмов в распределенной гетерогенной вычислительной среде, предоставляющей вычислительные ресурсы. Новизна предлагаемого метода заключается в выборе способа параллельного выполнения метаэвристических алгоритмов, формирования блоков вычислительной нагрузки, реализующих метаэвристики, и назначении блоков на вычислительные ресурсы в гетерогенной распределенной вычислительной среде с использованием репозитория эффективных алгоритмов. Приведены результаты экспериментального исследования, демонстрирующие эффективность разработанного метода.

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.

метаэвристикираспределенные вычисленияпараллельные метаэвристикиоптимизацияраспределение вычислительной нагрузкиmetaheuristicsdistributed computingparallel metaheuristicsoptimizationworkload distributionReferencesKlimenko 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.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.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.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.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.Li S. et al. J. Syst. Sci. Complex, 2024, no. 2(37), pp. 805–840, https://doi.org/10.1007/s11424-024-2038-2.Singh K. D., Singh P. D. Machine Learning in Robotics with Fog/Cloud Computing and IoT// EAI Endorsed Trans AI Robotics. 2023. N 2.Singh K.D., Singh P.D. EAI Endorsed Trans AI Robotics, 2023, no. 2.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.Alqam S. et al. J. Eng. Res., 2024, no. 2(20), pp. 113–122, https://doi.org/10.53540/tjer.vol20iss2pp113-122.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.Panahi F.H. et al. IEEE Internet Things J., 2023, no. 11(10), pp. 9646–9661, https://doi.org/10.1109/jiot.2023.3235998.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.Choudhary A., Rajak R. Cluster computing, 2024, https://doi.org/10.1007/s10586-024-04307-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.Uddin F. et al. Appl. Sci. (Basel), 2023, no. 12(13), pp. 7339, https://doi.org/10.3390/app13127339.Donoso Y., Fabregat R. Multi-objective optimization in computer networks using metaheuristics. Boca Raton, Fl.: Auerbach Publications, 2016.Donoso Y., Fabregat R. Multi-objective optimization in computer networks using metaheuristics, Auerbach Publications, 2016, 468 p., DOI:10.1201/9781420013627.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.Xiao J. et al. IEEE Trans. Netw. Sci. Eng., 2023, рр. 1–14, https://doi.org/10.1109/tnse.2023.3274173.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.Cho W.K.T., Liu Y.Y. IEEE International Conference on Big Data (Big Data), 2019, DOI:10.1109/BigData47090.2019.9006045.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.Yang H. et al. Eng. Appl. Artif. Intell., 2023, vol. 123, art. no. 106198, https://doi.org/10.1016/j.engappai.2023.106198.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.Algin R. et al. Ann. Oper. Res., 2024, https://doi.org/10.1007/s10479-024-05992-9.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.Zhang H. et al. IEEE Trans. Serv. Comput., 2024, рр. 1–14, https://doi.org/10.1109/tsc.2024.3376256.He Y. et al. Distributed bilevel optimization with communication compression // arXiv [math.OC]. 2024.He Y. et al. arXiv. https://arxiv.org/pdf/2405.18858, 2024.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.Oszust M., Wysocki M. Studies in Computational Intelligence, Springer, Berlin Heidelberg, 2008, pp. 147–155.Abdelhafez A. et al. Systematic literature review on parallel trajectory-based metaheuristics// Swarm Evol. Comput. 2023. N 55.Abdelhafez A. et al. Swarm Evol. Comput., 2023, vol. 55, art. no.100692.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.Coelho P., Silva C. Procedia Comput. Sci., 2021, vol. 180, рр. 778–786, https://doi.org/10.1016/j.procs.2021.01.328.Parallel GPU-accelerated metaheuristics // Designing Scientific Applications on GPUs. Chapman and Hall/CRC, 2013. P. 205–236.Parallel GPU-accelerated metaheuristics, Designing Scientific Applications on GPUs, Chapman and Hall/CRC, 2013, pp. 205–236.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.Testa A. et al., http://arxiv.org/abs/2309.04257, 2023.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.Testa A., Notarstefano G. IEEE Trans. Robot., 2022, no. 3(38), pp. 1990–2001, https://doi.org/10.1109/tro.2021.3120046.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.Mosteo A.R. et al. Automatica (Oxf.), 2017, vol. 81, рр. 305–313, https://doi.org/10.1016/j.automatica.2017.03.040.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.Bai X. et al. IEEE Trans. Autom. Sci. Eng., 2020, no. 1(17), pp. 248–260, https://doi.org/10.1109/tase.2019.2914113.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.Hartuv E. et al. Intern. Conf. on Autonomous Agents and MultiAgent Systems, 2018, pp. 532–540.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.Gopinath S., Natesh T.C. Lecture Notes in Civil Engineering, Springer Nature, Singapore, 2024, pp. 541–550.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.Mijuskovic A. et al. Sensors (Basel), 2021, no. 5(21), pp. 1832, https://doi.org/10.3390/s21051832.

The authors declare that there are no conflicts of interest present.