Гибридный алгоритм JAYA для планирования рабочих процессов в облаке

Планирование рабочих процессов и предоставление ресурсов — две наиболее важные проблемы облачных вычислений. Разработка оптимальной стратегии планирования рабочих процессов в гетерогенной облачной среде чрезвычайно сложна из-за ее NP-полной природы. При планировании рабочего процесса используются различные алгоритмы оптимизации для получения пользователями качественного обслуживания (Quality of Service, QoS) от поставщиков облачных услуг. При этом поставщики услуг должны получать максимальную выгоду. Сегодня не существует такой модели, которая могла бы одновременно минимизировать время и стоимость выполнения работ при балансировке нагрузки между виртуальными машинами в гетерогенной среде с использованием подхода JAYA. В работе предложен гибридный алгоритм JAYA для минимизирования стоимости вычислений и времени выполнения работ при планировании рабочего процесса. Рассмотрена гетерогенная среда облачных вычислений, позволяющая равномерно распределять нагрузку между виртуальными машинами. Для достижения этих целей использованы эвристические подходы Task Duplication Heterogeneous Earliest Finish Time (HEFT-TD) и Predict Earliest Finish Time (PEFT). Длительность выполнения работ значительно сокращается благодаря HEFT-TD, основанному на таблице оптимистичных затрат (Optimistic Cost Table). Для распределения рабочей нагрузки между виртуальными машинами в гетерогенной среде использован жадный алгоритм. Жадный алгоритм назначает предстоящую задачу виртуальной машине с наименьшей нагрузкой. Рассмотрено изменение производительности, задержки завершения и время загрузки виртуальных машин. С целью проверки предложенной концепции для экспериментального анализа представленной модели использованы наборы данных Montage, LIGO, Cybershake и Epigenomics. Выполненные эксперименты показали, что рассмотренный гибридный подход превосходит более ранние алгоритмы по минимизации стоимости и времени его выполнения, такие как Cost Effective Genetic Algorithm (CEGA), Cost-effective Load-balanced Genetic Algorithm (CLGA), Cost effective Hybrid Genetic Algorithm (CHGA) и Artificial Bee Colony Algorithm (ABC).

1. Yu J., Buyya R. A taxonomy of scientific workflow systems for grid computing // ACM SIGMOD Record. 2005. V. 34. N 3. P. 44–49. https://doi.org/10.1145/1084805.1084814

2. Singhal S., Grover J. Hybrid biogeography algorithm for reducing power consumption in cloud computing // Proc. of the 2017 International Conference on Advances in Computing, Communications and Informatics (ICACCI). 2017. P. 121–124. https://doi.org/10.1109/ICACCI.2017.8125827

3. Bothra S.K., Singhal S. Nature-inspired metaheuristic scheduling algorithms in cloud: A systematic review // Научно-технический вестник информационных технологий, механики и оптики. 2021. V. 21. N 4. P. 463–472. https://doi.org/10.17586/2226-1494-2021-21-4-463-472

4. Bhatt C., Singhal S. Anatomy of virtual machine placement techniques in cloud // Lecture Notes in Networks and Systems. 2022. V. 373. P. 609–626. https://doi.org/10.1007/978-981-16-8721-1_59

5. Singhal S., Patel J. Load balancing scheduling algorithm for concurrent workflow // Computing and Informatics. 2018. V. 37. N 2. P. 311–326. https://doi.org/10.4149/cai_2018_2_311

6. NoorianTalouki R., Hosseini Shirvani M., Motameni H. A heuristic-based task scheduling algorithm for scientific workflows in heterogeneous cloud computing platforms // Journal of King Saud University Computer and Information Sciences. 2022. V. 34. N 8. P. 4902–4913. https://doi.org/10.1016/j.jksuci.2021.05.011

7. Arabnejad H., Barbosa J.G. List scheduling algorithm for heterogeneous systems by an optimistic cost table // IEEE Transactions on Parallel and Distributed Systems. 2014. V. 25. N 3. P. 682–694. https://doi.org/10.1109/tpds.2013.57

8. Shubham, Gupta R., Gajera V., Jana P.K. An effective multi-objective workflow scheduling in cloud computing: a pso based approach // Proc. of the 2016 Ninth International Conference on Contemporary Computing (IC3). 2016. P. 1–6. https://doi.org/10.1109/ic3.2016.7880196

9. Lal A., Krishna C.R. Critical path-based ant colony optimization for scientific workflow scheduling in cloud computing under deadline constraint // Advances in Intelligent Systems and Computing. 2018. V. 696. P. 447–461. https://doi.org/10.1007/978-981-10-7386-1_39

10. Xu R., Wang Y., Cheng Y., Zhu Y., Xie Y., Sani A.S., Yuan D. Improved particle swarm optimization based workflow scheduling in cloud-fog environment // Lecture Notes in Business Information Processing. 2019. V. 342. P. 337–347. https://doi.org/10.1007/978-3-030-11641-5_27

11. Meshkati J., Safi-Esfahani F. Energy-aware resource utilization based on particle swarm optimization and artificial bee colony algorithms in cloud computing // The Journal of Supercomputing. 2019. V. 75. N 5. P. 2455–2496. https://doi.org/10.1007/s11227-018-2626-9

12. Mohanty S., Patra P.K., Ray M., Mohapatra S. An approach for load balancing in cloud computing using JAYA algorithm // International Journal of Information Technology and Web Engineering. 2019. V. 14. N 1. P. 27–41. https://doi.org/10.4018/IJITWE.2019010102

13. Nayak S.C., Parida S., Tripathy C., Pattnaik P.K. Dynamic backfilling algorithm to increase resource utilization in cloud computing // International Journal of Information Technology and Web Engineering. 2019. V. 14. N 1. P. 1–26. https://doi.org/10.4018/IJITWE.2019010101

14. Masadeh R.M.T., Sharieh A.-A.A., Mahafzah B.A. Humpback whale optimization algorithm based on vocal behavior for task scheduling in cloud computing // International Journal of Advanced Science and Technology. 2019. V. 13. N 3. P. 121–140.

15. Sanaj M.S., Prathap P.J. An efficient approach to the map-reduce framework and genetic algorithm based whale optimization algorithm for task scheduling in cloud computing environment // Materials Today: Proceedings. 2021. V. 37. P. 3199–3208. https://doi.org/10.1016/j.matpr.2020.09.064

16. Gu Y., Budati C. Energy-aware workflow scheduling and optimization in clouds using bat algorithm // Future Generation Computer Systems. 2020. V. 113. P. 106–112. https://doi.org/10.1016/j.future.2020.06.031

17. Ullah A., Nawi N.M., Khan M.H. BAT algorithm used for load balancing purpose in cloud computing: an overview // International Journal of High Performance Computing and Networking. 2020. V. 16. N 1. P. 43. https://doi.org/10.1504/ijhpcn.2020.110258

18. Aziza H., Krichen S. A hybrid genetic algorithm for scientific workflow scheduling in cloud environment // Neural Computing and Applications. 2020. V. 32. N 18. P. 15263–15278. https://doi.org/10.1007/s00521-020-04878-8

19. Sardaraz M., Tahir M. A parallel multi-objective genetic algorithm for scheduling scientific workflows in cloud computing // International Journal of Distributed Sensor Networks. 2020. V. 16. N 8. https://doi.org/10.1177/1550147720949142

20. Gupta S., Agarwal I., Singh R.S. Workflow scheduling using Jaya algorithm in cloud // Concurrency and Computation: Practice and Experience. 2019. V. 31. N 17. P. e5251. https://doi.org/10.1002/cpe.5251

21. Rao R.V. Jaya: A simple and new optimization algorithm for solving constrained and unconstrained optimization problems // International Journal of Industrial Engineering Computations. 2016. V. 7. N 1. P. 19–34. https://doi.org/10.5267/j.ijiec.2015.8.004

22. Bothra S.K., Singhal S., Goyal H. Deadline-constrained cost-effective load-balanced improved genetic algorithm for workflow scheduling // International Journal of Information Technology and Web Engineering. 2021. V. 16. N 4. P. 1–34. https://doi.org/10.4018/IJITWE.2021100101

23. Bothra S.K., Singhal S., Goyal H. Cost effective hybrid genetic algorithm for workflow scheduling in cloud // System Research and Information Technologies. 2022. V. 3. P. 121–138. https://doi.org/10.20535/srit.2308-8893.2022.3.08

24. Голосов П.Е., Гостев И.М. Имитационная модель облачных вычислений со спорадическим механизмом управления параллельным решением задач // Научно-технический вестник информационных технологий, механики и оптики. 2022. Т. 22. № 2. С. 269–278. https://doi.org/10.17586/2226-1494-2022-22-2-269-278

25. Архипов И.В. Применение генетического алгоритма для многокритериальной задачи календарного планирования // Научно-технический вестник информационных технологий, механики и оптики. 2015. Т. 15. № 3. С. 525–531. https://doi.org/10.17586/2226-1494-2015-15-3-525-531

26. Беккер М.Я., Гатчин Ю.А., Кармановский Н.С., Терентьев А.О., Федоров Д.Ю. Информационная безопасность при облачных вычислениях: проблемы и перспективы // Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики. 2011. Т. 11. № 1. С.97–102.