В настоящее время управление вычислительными ресурсами в современных системах распределенных вычислений является актуальной проблемой. Эволюция потенциала инфраструктуры привела к тому, что распределенные вычисления могут быть организованы в динамичных гетерогенных и географически распределенных вычислительных средах, примерами которых являются среды «туманные» и «краевые». Динамика как нагрузки, так и топологии подразумевает необходимость смены конфигурации системы, а именно закрепления пользовательских задач за вычислительными устройствами с выделением необходимых ресурсов. Последнее актуализирует вопрос повышения эффективности функционирования планировщика (брокера), обеспечивающего управление ресурсами сети в пределах выделенного фрагмента. Алгоритмическое и программное обеспечение планировщиков основано на моделях и методах теории расписаний и, исходя из постановки задачи, реализует либо простые эвристики, либо методы математического программирования, либо метаэвристики. Однако анализ представленных в открытом доступе постановок задач показал, что они, во-первых, являются частными случаями и реализуют определенные ситуации распределения вычислительных ресурсов, во-вторых, не отражают в полной мере свойств гетерогенности, географической распределенности и динамики вычислительных сред. В рамках данного исследования предложена общая модель задачи распределения вычислительных ресурсов с учетом перечисленных свойств и предложен ее метод решения с использованием предметной онтологии метаэвристических методов. Показана целесообразность построения и применения онтологии на примере анализа эффективности генетических алгоритмов в зависимости от значений параметров решаемой задачи распределения вычислительных ресурсов.
1. Pinedo M.L. Planning and Scheduling in Manufacturing and Services. 2nd ed. New York, NY: Springer; 2014. 536 p.
2. Han X., Iwama K., Ye D., Zhang G. Strip packing vs. Bin packing. В сборнике: Third International Conference on Algorithmic Aspects in Information and Management (AAIM’07), 6–8 July 2007, Portland, Oregon, USA. Heidelberg: Springer; 2007. p. 358–367.
3. Burcea M., Wong P.W.H., Yung F.C.C. Online Multi-dimensional Dynamic Bin Packing of Unit-Fraction Items. In: CIAC 2013: 8th International Conference on Algorithms and Complexity, 22–24 May 2013, Barcelona, Spain. Heidelberg: Springer; 2013. p. 85–96.
4. Топорков В.В. Модели распределенных вычислений. М.: ФИЗМАТЛИТ; 2004. 320 с.
5. Shaji George A., Hovan George A.S., Baskar T. Edge computing and the future of cloud computing: a survey of industry perspectives and predictions. Partners Universal International Research Journal (PUIRJ). 2023;2(2):19–44. DOI: 10.5281/zenodo.8020101.
6. Shaji George A., Hovan George A.S., Baskar T. Unshackled by servers: embracing the serverless revolution in modern computing. Partners Universal International Research Journal (PUIRJ). 2023;2(2):229–240. DOI: 10.5281/zenodo.8051052.
7. Brando V., Lovell J., King E., Boadle D., Scott R., Schroeder T. The potential of autonomous ship-borne hyperspectral radiometers for the validation of ocean color radiometry data. Remote Sensing. 2016;8(2). URL: https://www.mdpi.com/2072-4292/8/2/150. DOI: 10.3390/rs8020150 (дата обращения: 19.12.2023).
8. Liang Z., Zhong P., Zhang C., Yang W., Xiong W., Yang S., et al. A genetic algorithm-based approach for flexible job shop rescheduling problem with machine failure interference. Eksploatacja i Niezawodność – Maintenance and Reliability. 2023;25(4). URL: https://ein.org.pl/A-genetic-algorithm-based-approach-for-flexible-job-shop-rescheduling-problem-with,171784,0,2.html. DOI: 10.17531/ein/171784 (дата обращения: 19.12.2023).
9. Espinaco F., Henning G.P. Industrial rescheduling approaches: where are we and what is missing? In: ICPR Americas 2022: International Conference on Production Research – Americas 2022, 23–25 November 2022, Curitiba, Brazil. Cham: Springer; 2023. p. 461–467.
10. 1Nair B., Bhanu S.M.S. A reinforcement learning algorithm for rescheduling preempted tasks in fog nodes. Journal of Scheduling. 2022;25(5):547–565. DOI: 10.1007/s10951-022-00725-x.
11. Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. М.: Наука; 1975. 359 с.
12. Khan A., Lonkar A., Maiti A., Sharma A., Wiese A. Tight approximation algorithms for two dimensional Guillotine strip packing. arXiv. 2022.
13. Henrik I.C., Arindam K., Pokutta S., Tetali P. Approximation and online algorithms for multidimensional bin packing: A survey. Computer Science Review. 2017;24:63–79. DOI: 10.1016/j.cosrev.2016.12.001.
14. Seiden S.S., Woeginger G.J. The two-dimensional cutting stock problem revisited. Mathematical Programming. 2005;102(3):519–530. DOI: 10.1007/s10107-004-0548-1.
15. Dow E.M. Decomposed multi-objective bin-packing for virtual machine consolidation. PeerJ Computer Science. 2016;2(e47):e47. DOI: 10.7717/peerj-cs.47.
16. Telenyk S., Zharikov E., Rolik O. Consolidation of virtual machines using stochastic local search. In: CSIT 2017: The International Conference on Computer Science and Information Technologies, 5–8 September 2017. Cham: Springer; 2018. p. 523–537.
17. Augustine J., Banerjee S., Irani S. Strip packing with precedence constraints and strip packing with release times. Theoretical Computer Science. 2009;410(38–40):3792–3803. DOI: 10.1016/j.tcs.2009.05.024.
18. Deppert M.A., Jansen K., Khan A., Rau M., Tutas M. Peak demand minimization via sliced strip packing. Algorithmica. 2023;85(12):3649–3679. DOI: 10.1007/s00453-023-01152-w.
19. Bódis A., Csirik J. The variable-width strip packing problem. Central European Journal of Operations Research. 2022;30(4):1337–1351. DOI: 10.1007/s10100-021-00772-3.
20. Барский А.Б. Параллельные информационные технологии. М.: БИНОМ. Лаборатория знаний; 2007. 502 с.
21. Singh R.M., Awasthi L.K., Sikka G. Techniques for task scheduling in cloud and fog environment: A survey. In: Second International Conference on Futuristic Trends in Networks and Computing Technologies (FTNCT-2019), 22–23 November 2019, Chandigarh, India. Singapore: Springer; 2020. p. 673–685.
22. Nguyen B.M., Binh H.T.T., Anh T.T., Son D.B. Evolutionary algorithms to optimize task scheduling problem for the IoT based bag-of-tasks application in cloud–fog computing Environment. Applied Sciences. 2019;9(9). URL: https://www.mdpi.com/2076-3417/9/9/1730. DOI: 10.3390/app9091730 (дата обращения: 19.12.2023).
23. Natesan G., Chokkalingam A. Task scheduling in heterogeneous cloud environment using mean grey wolf optimization algorithm. ICT Express. 2019;5(2):110–114. DOI: 10.1016/j.icte.2018.07.002.
24. Narendrababu Reddy G., Phani Kumar S. Modified ant colony optimization algorithm for task scheduling in cloud computing systems. In: SCI2018: 2nd International Conference on Smart Computing and Informatics, 27–28 January 2018, Vijayawada, India. Singapore: Springer; 2019. p. 357–365.
