doi: 10.17586/2226-1494-2021-21-4-463-472


УДК 004.75

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

Ботра С., Сингхал С.


Читать статью полностью 
Язык статьи - английский

Ссылка для цитирования:
Ботра Сандип Кумар, Сингхал Сунита. Биоинспирированные метаэвристические алгоритмы построения расписаний в облаке: систематический обзор // Научно-технический вестник информационных технологий, механики и оптики. 2021. Т. 21, № 4. С. 463–472 (на англ. яз.). doi: 10.17586/2226-1494-2021-21-4-463-472


Аннотация

Применение сложных крупномасштабных научных приложений упрощается в случае их обработки в облачной среде. Дальнейшее развитие облачных технологий связано с решением ряда новых проблем. Центральной темой парадигмы облачных вычислений является планирование рабочих процессов с использованием биоинспирированных метаэвристических алгоритмов. 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. 9th 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. 6th 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. 7th 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. 8th 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. 12th 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. 7th 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. 8th 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. 9th 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


Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License
Информация 2001-2021 ©
Научно-технический вестник информационных технологий, механики и оптики.
Все права защищены.

Яндекс.Метрика