Биоинспирированные метаэвристические алгоритмы построения расписаний в облаке: систематический обзор

Применение сложных крупномасштабных научных приложений упрощается в случае их обработки в облачной среде. Дальнейшее развитие облачных технологий связано с решением ряда новых проблем. Центральной темой парадигмы облачных вычислений является планирование рабочих процессов с использованием биоинспирированных метаэвристических алгоритмов. NP-полная задача (NP-completeness) привлекает исследователей к поиску оптимального решения с использованием роевого интеллекта. В работе представлены систематизированный анализ и оценка метаэвристических алгоритмов, таких как генетический (Genetic Algorithms, GA), китовый (Whale Search Algorithm, WSA), муравьиный (Ant Colony Optimization, ACO), летучих мышей (Bat Algorithm, BA), пчелиный (Artificial Bee Colony, ABC), кукушкин поиск (Cuckoo Algorithm, CA), светлячковый (Firefly Algorithm, FA), оптимизация роем частиц (Particle Swarm Optimization, PSO). Представлены параметры алгоритмов, дана их классификация, приведено подробное сравнение. Уделено внимание нерешенным проблемам, таким как потребление энергии, надежность и безопасность. Представленные результаты позволят исследователям выбрать подходящие решения возможных новых проблем в облачных вычислениях.

1. Ibrahim S., He B., Jin H. Towards pay-as-you-consume cloud computing // Proc. of the IEEE International Conference on Services Computing (SCC). 2011. P. 370–377. https://doi.org/10.1109/scc.2011.38
2. Kumar P., Kumar R. Issues and challenges of load balancing techniques in cloud computing: A survey // ACM Computing Surveys. 2019. V. 51. N 6. P. 120. https://doi.org/10.1145/3281010
3. Aljoumah E., Al-Mousawi F., Ahmad I., Al-Shammri M., Al-Jady Z. SLA in cloud computing architectures: A comprehensive study // International Journal of Grid and Distributed Computing. 2015. V. 8. N 5. P. 7–32. https://doi.org/10.14257/ijgdc.2015.8.5.02
4. Weinman J. Cloud computing is NP-complete // Proc. Tech. Symp. ITU Telecom World. 2011. P. 75–81.
5. Fister Jr, I., Yang X.S., Fister I., Brest J., Fister D. A brief review of nature-inspired algorithms for optimization // Elektrotehniski Vestnik. 2013. V. 80. N 3. P. 116–122.
6. Osman I.H., Kelly J.P. Meta-heuristics: an overview // Meta-Heuristics. Springer, 1996. pp. 1–21. https://doi.org/10.1007/978-1-4613-1361-8_1
7. Laporte G., Osman I.H. Routing problems: A bibliography // Annals of Operations Research. 1995. V. 61. N 1. P. 227–262. https://doi.org/10.1007/bf02098290
8. 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. 2018. V. 342. P. 337–347. https://doi.org/10.1007/978-3-030-11641-5_27
9. Shubham, Gupta R., Gajera V., Jana P.K. An effective multi-objective workflow scheduling in cloud computing: A PSO based approach // Proc. 9^th International Conference on Contemporary Computing (IC3 2016). 2016. P. 7880196. https://doi.org/10.1109/ic3.2016.7880196
10. Zhan S., Huo H. Improved PSO-based task scheduling algorithm in cloud computing // Journal of Information & Computational Science. 2012. V. 9. N 13. P. 3821–3829.
11. Chen Z., Zhan Z., Lin Y., Gong Y., Gu T., Zhao F., Yuan H., Chen X., Li Q., Zhang J. Multiobjective cloud workflow scheduling: A multiple populations ant colony system approach // IEEE Transactions on Cybernetics. 2019. V. 49. N 8. P. 2912–2926. https://doi.org/10.1109/tcyb.2018.2832640
12. 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
13. Sharma S., Jain R. EACO: an enhanced ant colony optimization algorithm for task scheduling in cloud computing // International Journal of Security and Its Applications. 2019. V. 13. N 4. P. 91–100. https://doi.org/10.33832/ijsia.2019.13.4.09
14. Meshkati J., Safi-Esfahani F. Energy-aware resource utilization based on particle swarm optimization and artificial bee colony algorithms in cloud computing // Journal of Supercomputing. 2019. V. 75. N 5. P. 2455–2496. https://doi.org/10.1007/s11227-018-2626-9
15. Thanka M.R., Maheswari P.U., Edwin E.B. An improved efficient: Artificial Bee Colony algorithm for security and QoS aware scheduling in cloud computing environment // Cluster Computing. 2019. V 22. N 5. P. 10905–10913. https://doi.org/10.1007/s10586-017-1223-7
16. Yang X.S. Multiobjective firefly algorithm for continuous optimization // Engineering with Computers. 2013. V. 29. N 2. P. 175–184. https://doi.org/10.1007/s00366-012-0254-1
17. Chakravarthi K.K., Shyamala L., Vaidehi V. Cost-effective workflow scheduling approach on cloud under deadline constraint using firefly algorithm // Applied Intelligence. 2021. V. 51. N 3. P. 1629–1644. https://doi.org/10.1007/s10489-020-01875-1
18. Pradeep K., Jacob T.P. A hybrid approach for task scheduling using the cuckoo and harmony search in cloud computing environment // Wireless Personal Communications. 2018. V. 101. N 4. P. 2287–2311. https://doi.org/10.1007/s11277-018-5816-0
19. Ghasemi S., Hanani A. A cuckoo-based workflow scheduling algorithm to reduce cost and increase load balance in the cloud environment // International Journal on Informatics Visualization. 2019. V. 3. N 1. P. 79–85. https://doi.org/10.30630/joiv.3.1.220
20. Masadeh R., Sharieh A., Mahafzah B. 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.
21. Thennarasu S.R., Selvam M., Srihari K. A new whale optimizer for workflow scheduling in cloud computing environment // Journal of Ambient Intelligence and Humanized Computing. 2021. V. 12. N 3. P. 3807–3814. https://doi.org/10.1007/s12652-020-01678-9
22. Hemasian-Etefagh F., Safi-Esfahani F. Dynamic scheduling applying new population grouping of whales meta-heuristic in cloud computing // Journal of Supercomputing. 2019. V. 75. N 10. P. 6386–6450. https://doi.org/10.1007/s11227-019-02832-7
23. Kaur N., Singh S. A budget-constrained time and reliability optimization bat algorithm for scheduling workflow applications in clouds // Procedia Computer Science. 2016. V. 98. P. 199–204. https://doi.org/10.1016/j.procs.2016.09.032
24. 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
25. 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–54. https://doi.org/10.1504/ijhpcn.2020.110258
26. Abdel-Basset M., Abdel-Fatah L., Sangaiah A.K. Metaheuristic algorithms: A comprehensive review // Computational Intelligence for Multimedia Big Data on The Cloud with Engineering Applications. 2018. P. 185–231. https://doi.org/10.1016/b978-0-12-813314-9.00010-4
27. Yang X.S. Nature-Inspired Metaheuristic Algorithms. Luniver press, 2010. 148 p.
28. Iranmanesh A., Naji H.R. DCHG-TS: a deadline-constrained and cost-effective hybrid genetic algorithm for scientific workflow scheduling in cloud computing // Cluster Computing. 2021. V. 24. N 2. P. 667–681. https://doi.org/10.1007/s10586-020-03145-8
29. Zhou Z., Li F., Zhu H., Xie H., Abawajy J.H., Chowdhury M.U. An improved genetic algorithm using greedy strategy toward task scheduling optimization in cloud environments // Neural Computing and Applications. 2020. V. 32. N 6. P. 1531–1541. https://doi.org/10.1007/s00521-019-04119-7
30. 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
31. 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
32. Pang S., Li W., He H., Shan Z., Wang X. An EDA-GA hybrid algorithm for multi-objective task scheduling in cloud computing // IEEE Access. 2019. V. 7. P. 146379–146389. https://doi.org/10.1109/access.2019.2946216
33. Wangsom P., Lavangnananda K., Bouvry P. Multi-objective scientific-workflow scheduling with data movement awareness in cloud // IEEE Access. 2019. V. 7. P. 177063–177081. https://doi.org/10.1109/access.2019.2957998
34. Hammed S.S., Arunkumar B. Efficient workflow scheduling in cloud computing for security maintenance of sensitive data // International Journal of Communication Systems. 2019. P. e4240. https://doi.org/10.1002/dac.4240
35. Gupta I., Gupta S., Choudhary A., Jana P.K. A hybrid meta-heuristic approach for load balanced workflow scheduling in IaaS cloud // Lecture Notes in Computer Science. 2019. V. 11319. P. 73–89. https://doi.org/10.1007/978-3-030-05366-6_6
36. Rehman A., Hussain S.S., ur Rehman Z., Zia S., Shamshirband S. Multi-objective approach of energy efficient workflow scheduling in cloud environments // Concurrency and Computation: Practice and Experience. 2019. V. 31. N 8. P. e4949. https://doi.org/10.1002/cpe.4949
37. Ashouraei M., Khezr S.N., Benlamri R., Navimipour N.J. A new SLA-aware load balancing method in the cloud using an improved parallel task scheduling algorithm // Proc. 6^th International Conference on Future Internet of Things and Cloud (FiCloud). 2018. P. 71–76. https://doi.org/10.1109/ficloud.2018.00018
38. Jana B., Poray J. A hybrid task scheduling approach based on genetic algorithm and particle swarm optimization technique in cloud environment // Advances in Intelligent Systems and Computing. 2018. V. 695. P. 607–614. https://doi.org/10.1007/978-981-10-7566-7_61
39. Shishido H.Y., Estrella J.C., Toledo C.F.M., Arantes M.S. Genetic-based algorithms applied to a workflow scheduling algorithm with security and deadline constraints in clouds // Computers & Electrical Engineering. 2018. V. 69. P. 378–394. https://doi.org/10.1016/j.compeleceng.2017.12.004
40. Kaur G., Kalra M. Deadline constrained scheduling of scientific workflows on cloud using hybrid genetic algorithm // Proc. 7^th International Conference on Cloud Computing, Data Science and Engineering, Confluence. 2017. P. 276–280. https://doi.org/10.1109/confluence.2017.7943162
41. Wangsom P., Lavangnananda K., Bouvry P. The application of nondominated sorting genetic algorithm (NSGA-III) for scientific-workflow scheduling on cloud // Proc. 8^th Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA 2017). 2017. P. 269–287.
42. Meena J., Kumar M., Vardhan M. Cost effective genetic algorithm for workflow scheduling in cloud under deadline constraint // IEEE Access. 2016. V. 4. P. 5065–5082. https://doi.org/10.1109/access.2016.2593903
43. Liu L., Zhang M., Buyya R., Fan Q. Deadline‐constrained coevolutionary genetic algorithm for scientific workflow scheduling in cloud computing // Concurrency and Computation: Practice and Experience. 2017. V. 29. N 5. P. e3942. https://doi.org/10.1002/cpe.3942
44. Chen Z.G., Du K.J., Zhan Z.H., Zhang J. Deadline constrained cloud computing resources scheduling for cost optimization based on dynamic objective genetic algorithm // Proc. 2015 IEEE Congress on Evolutionary Computation (CEC). 2015. P. 708–714. https://doi.org/10.1109/cec.2015.7256960
45. Xu Y., Li K., Hu J., Li K. A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues // Information Sciences. 2014. V. 270. P. 255–287. https://doi.org/10.1016/j.ins.2014.02.122
46. Delavar A.G., Aryan Y. HSGA: a hybrid heuristic algorithm for workflow scheduling in cloud systems // Cluster Computing. 2014. V. 17. N 1. P. 129–137. https://doi.org/10.1007/s10586-013-0275-6
47. Wang T., Liu Z., Chen Y., Xu Y., Dai X. Load balancing task scheduling based on genetic algorithm in cloud computing // Proc. 12^th International Conference on Dependable, Autonomic and Secure Computing (DASC). 2014. P. 146–152. https://doi.org/10.1109/DASC.2014.35
48. Dasgupta K., Mandal B., Dutta P., Mandal J.K., Dam S. A genetic algorithm (GA) based load balancing strategy for cloud computing // Procedia Technology. 2013. V. 10. P. 340–347. https://doi.org/10.1016/j.protcy.2013.12.369
49. Ying C.-T., Yu J. Energy-aware genetic algorithms for task scheduling in cloud computing // Proc. 7^th ChinaGrid Annual Conference (ChinaGrid 2012). 2012. P. 43–48. https://doi.org/10.1109/chinagrid.2012.15
50. Zhao E.-D., Qi Y.-Q., Xiang X.-X., Chen Y. A data placement strategy based on genetic algorithm for scientific workflows // Proc. 8^th International Conference on Computational Intelligence and Security (CIS 2012). 2012. P. 146–149. https://doi.org/10.1109/cis.2012.40
51. Barrett E., Howley E., Duggan J. A learning architecture for scheduling workflow applications in the cloud // Proc. 9^th European Conference on Web Services (ECOWS 2011). 2011. P. 83–90. https://doi.org/10.1109/ecows.2011.27
52. Kessaci Y., Melab N., Talbi E.-G. A pareto-based GA for scheduling HPC applications on distributed cloud infrastructures // Proc. of the International Conference on High Performance Computing and Simulation (HPCS 2011). 2011. P. 456–462. https://doi.org/10.1109/hpcsim.2011.5999860
53. 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
54. Bansal S., Hota C. Efficient Algorithm on heterogeneous computing system // Proc. of the International Conference on Recent Trends in Information Systems (ReTIS 2011). 2011. P. 57–61. https://doi.org/10.1109/retis.2011.6146840
55. Хоружников С.Э., Шевель А.Е. Система управления масштабируемым географически распределенным центром обработки данных // Научно-технический вестник информационных технологий, механики и оптики. 2019. Т. 19. № 5. С. 931–938. https://doi.org/10.17586/2226-1494-2019-19-5-931-938
56. Беккер М.Я., Гатчин Ю.А., Кармановский Н.С., Терентьев А.О., Федоров Д.Ю. Информационная безопасность при облачных вычислениях: проблемы и перспективы // Научно-технический вестник Cанкт-петербургского государственного университета информационных технологий, механики и оптики. 2011. № 1(71). С. 97–102.
57. Хан Д.В., Разгуляев К.А., Тягунов Д.М. Разработка порталов для управления облачными сервисами в составе центра обработки и хранения данных // Научно-технический вестник информационных технологий, механики и оптики. 2019. Т. 19. № 6. С. 1169–1171. https://doi.org/10.17586/2226-1494-2019-19-6-1169-1171

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License