An Efficient Task Scheduling Based on Seagull Optimization Algorithm for Heterogeneous Cloud Computing Platforms

Document Type : Original Article

Authors

Department of Computer Science, Shahid Bahonar University of Kerman, Kerman, Iran

Abstract

Cloud computing provides computing resources like software and hardware as a service by the network for several users. Task scheduling is one of the main problems to attain cost-effective execution. The main purpose of task scheduling is to allocate tasks to resources so that it can optimize one or more criteria. Since the problem of task scheduling is one of the Nondeterministic Polynomial-time (NP)-hard problems, meta-heuristic algorithms have been widely employed for solving task scheduling problems. One of the new bio-inspired meta-algorithms is Seagull Optimization Algorithm (SOA). In this paper, we proposed an energy-aware and cost-efficient SOA-based Task Scheduling (SOATS) algorithm. The aims of proposed algorithm to make a trade-off between five objectives (i.e., energy consumption, makespan, cost, waiting time, and load balancing) using a fewer number of iterations. The experiment results by comparing with several meta-heuristic algorithms (i.e., Genetic Algorithm (GA), Particle Swarm Optimization (PSO), Ant Colony Optimization (ACO), and Whale Optimization Algorithm (WOA)) prove that the proposed technique performs better in solving task scheduling problem. Moreover, we compared the proposed algorithm with well-known scheduling methods: Cost-based Job Scheduling (CJS), Moth Search Algorithm based Differential Evolution (MSDE), and Fuzzy-GA (FUGE). In the heavily loaded environment, the SOATS algorithm improved energy consumption and cost saving by 10 and 25%, respectively.

Keywords

Main Subjects


  1. Mohammad Hasani Zade. B, Mansouri. N, and Javidi. M. M, “Multi-objective scheduling technique based on hybrid hitchcock bird algorithm and fuzzy signature in cloud computing”, Engineering Applications of Artificial Intelligence, Vol. 104, (2021), DOI: 10.1016/j.engappai.2021.104372.
  2. Kumar. M, Sharma. S. C, Goel. A, and Singh. S. P, “A comprehensive survey for scheduling techniques in cloud computing”, Journal of Network and Computer Applications, Vol. 143, (2019), 1-33, DOI: 10.1016/j.jnca.2019.06.006.
  3. Dhiman. G, and Kumar. V, “Seagull optimization algorithm: Theory and its applications for large-scale industrial engineering problems”, Knowledge-Based Systems, Vol. 165, (2019), 169-196, DOI: 10.1016/j.knosys.2018.11.024.
  4. Mansouri. N, Mohammad Hasani Zade. B, Javidi. M. M, ”SAEA: A security-aware and energy-aware task scheduling strategy by Parallel Squirrel Search Algorithm in cloud environment”, Expert Systems with Applications, Vol. 176, (2021), DOI: 10.1016/j.eswa.2021.114915.
  5. Pradhan. A, Bisoy. S. K, and Das. A, “A survey on PSO based meta-heuristic scheduling mechanism in cloud computing environment”, Journal of King Saud University - Computer and Information Sciences, (2021), DOI: 10.1016/j.jksuci.2021.01.003.
  6. Shafiq. D. A, Jhanjhi. N. Z, and Abdullah. A, “Load balancing techniques in cloud computing environment: A review”, Journal of King Saud University - Computer and Information Sciences, (2021), DOI: 10.1016/j.jksuci.2021.02.007.
  7. Velliangiri. S, Karthikeyan. P, Arul Xavier. V. M, and Baswaraj. D, “Hybrid electro search with genetic algorithm for task scheduling in cloud computing”, Ain Shams Engineering Journal, Vol. 12, No. 1, (2021), 631-639, DOI: 10.1016/j.asej.2020.07.003.
  8. WilczyÅ„ski. A, and KoÅ‚odziej. J, “Modelling and simulation of security-aware task scheduling in cloud computing based on Blockchain technology”, Simulation Modelling Practice and Theory, Vol. 99, (2020), DOI: 10.1016/j.simpat.2019.102038.
  9. NoorianTalouki. R, Hosseini Shirvani. M, and 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, (2021), DOI: 10.1016/j.jksuci.2021.05.011.
  10. Alsaidy. S. A, Abbood. A. D, and Sahib. M. A, “Heuristic initialization of PSO task scheduling algorithm in cloud computing”, Journal of King Saud University - Computer and Information Sciences, (2020), DOI: 10.1016/j.jksuci.2020.11.002.
  11. Pradhan. A, and Bisoy. S. K, “A novel load balancing technique for cloud computing platform based on PSO”, Journal of King Saud University-Computer and Information Sciences, (2020), DOI: 10.1016/j.jksuci.2020.10.016.
  12. Kaur. R, Laxmi. V, and Balkrishan, “Performance evaluation of task scheduling algorithms in virtual cloud environment to minimize makespan”, International Journal of Information Technology, (2021), DOI: 10.1007/s41870-021-00753-4.
  13. Sreenivasulu. G, and Paramasivam. I, “Hybrid optimization algorithm for task scheduling and virtual machine allocation in cloud computing”, Evolutionary Intelligence, Vol. 14, No. 2, (2021), 1015-1022, DOI: 10.1007/s12065-020-00517-2.
  14. Zandvakili. A, Mansouri. N, and Javidi. M. M, “Energy-aware task scheduling in cloud compting based on discrete pathfinder algorithm”, International Journal of Engineering, Transactions C: Aspects, Vol. 34, No. 9, (2021), 2124-2136, doi: 10.5829/ije.2021.34.09c.10.
  15. Uchechukwu. A, Li. K, and Shen. Y, “Energy consumption in cloud computing data centers”, International Journal of Cloud Computing and Services Science, Vol. 3, No. 3, (2014), 31-48, doi: 10.11591/closer.v3i3.6346.
  16. Barroso. L. A, Clidaras. J, and Hölzle. U, “The datacenter as a computer: An introduction to the design of warehouse-scale machines”, Synthesis Lectures on Computer Architecture, Vol. 8, No. 3, (2013), 1-154, DOI: 10.2200/S00193ED1V01Y200905CAC006.
  17. Sharma. M, and Garg. R, “HIGA: Harmony-inspired genetic algorithm for rack-aware energy-efficient task scheduling in cloud data centers”, Engineering Science and Technology, an International Journal, Vol. 23, No. 1, (2020), 211-224, DOI: 10.1016/j.jestch.2019.03.009.
  18. Hussain. M, Wei. L.-F, Lakhan. A, Wali. S, Ali. S, and Hussain. A, “Energy and performance-efficient task scheduling in heterogeneous virtualized cloud computing”, Sustainable Computing: Informatics and Systems, Vol. 30, (2021), DOI: 10.1016/j.suscom.2021.100517.
  19. Dong. M, Fan. L, and Jing. C, “ECOS: An efficient task-clustering based cost-effective aware scheduling algorithm for scientific workflows execution on heterogeneous cloud systems”, Journal of Systems and Software, Vol. 158, (2019), DOI: 10.1016/j.jss.2019.110405.
  20. Singh. H, Tyagi. S, Kumar. P, Gill. S. S, and Buyya. R, “Metaheuristics for scheduling of heterogeneous tasks in cloud computing environments: Analysis, performance evaluation, and future directions”, Simulation Modelling Practice and Theory, Vol. 111, (2021), DOI: 10.1016/j.simpat.2021.102353.
  21. Meshkati. J, and Safi-Esfahani. F, “Energy-aware resource utilization based on particle swarm optimization and artificial bee colony algorithms in cloud computing”, The Journal of Supercomputing, Vol. 75, No. 5, (2019), 2455-2496, DOI: 10.1007/s11227-018-2626-9.
  22. Sanaj. M. S, and Joe Prathap. P. M, “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, Vol. 37, (2021), 3199-3208, DOI: 10.1016/j.matpr.2020.09.064.
  23. Alboaneen. D, Tianfield. H, Zhang. Y, and Pranggono. B, “A metaheuristic method for joint task scheduling and virtual machine placement in cloud data centers”, Future Generation Computer Systems, Vol. 115, (2021), 201-212, DOI: 10.1016/j.future.2020.08.036.
  24. Houssein. E. H, Gad. A. G, Wazery. Y. M, and Suganthan. P. N, “Task Scheduling in Cloud Computing based on Meta-heuristics: Review, Taxonomy, Open Challenges, and Future Trends”, Swarm and Evolutionary Computation, Vol. 62, (2021), DOI: 10.1016/j.swevo.2021.100841.
  25. Rai. D, and Tyagi. K, “Bio-inspired optimization techniques: a critical comparative study”, ACM SIGSOFT Software Engineering Notes, Vol. 38, No. 4, (2013), 1-7, DOI: 10.1145/2492248.2492271.
  26. Beni. G, and Wang. J, “Swarm intelligence in cellular robotic systems”, Robots and Biological Systems: Towards a New Bionics?, Springer, (1993), 703-712, DOI: 10.1007/978-3-642-58069-7_38.
  27. Shaheen. A. M, Spea. S. R, Farrag. S. M, and Abido. M. A, “A review of meta-heuristic algorithms for reactive power planning problem”, Ain Shams Engineering Journal, Vol. 9, No. 2, (2018), 215-231, DOI: 10.1016/j.asej.2015.12.003.
  28. Kennedy. J, and Eberhart. R, “Particle swarm optimization”, IEEE Proceedings of ICNN’95-International Conference on Neural Networks, Perth, WA, Australia, (1995), DOI: 10.1109/ICNN.1995.488968.
  29. Dorigo. M, Maniezzo. V, and Colorni. A, “Ant system: optimization by a colony of cooperating agents”, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), (1996), 1996, DOI: 10.1109/3477.484436.
  30. Sreenu. K, and Sreelatha. M, “W-Scheduler: whale optimization for task scheduling in cloud computing”, Cluster Computing, Vol. 22, (2019), 1087-1098, DOI: 10.1007/s10586-017-1055-5.
  31. Mirjalili. S, and Lewis. A, “The whale optimization algorithm”, Advances in Engineering Software, Vol. 95, (2016), 51-67, DOI: 10.1016/j.advengsoft.2016.01.008.
  32. Zuo. L, Shu. L, Dong. S, Zhu. C, and Hara. T, “A multi-objective optimization scheduling method based on the ant colony algorithm in cloud computing”, IEEE Access, Vol. 3, (2015), 2687-2699, DOI: 10.1109/ACCESS.2015.2508940.
  33. Zuo. X, Zhang. G, and Tan. W, “Self-adaptive learning PSO-based deadline constrained task scheduling for hybrid IaaS cloud”, IEEE Transactions on Automation Science and Engineering, Vol. 11, No. 2, (2013), 564-573, DOI: 10.1109/TASE.2013.2272758.
  34. Sreenivasulu. G, and Paramasivam. I, “Hybrid optimization algorithm for task scheduling and virtual machine allocation in cloud computing”, Evolutionary Intelligence, Vol. 14, (2021), DOI: 10.1007/s12065-020-00517-2.
  35. Lin. W, Liang. C, Wang. J. Z, and Buyya. R, “Bandwidth-aware divisible task scheduling for cloud computing”, Software: Practice and Experience, Vol. 44, No. 2, (2014), 163-174, DOI: 10.1002/spe.2163.
  36. Del Acebo. E, and de-la Rosa. J. L, “Introducing bar systems: a class of swarm intelligence optimization algorithms”, In AISB 2008 Convention Communication, Interaction and Social Intelligence, Vol. 1, (2008), 1-18.
  37. Mansouri. N, and Javidi. M. M, “Cost-based job scheduling strategy in cloud computing environments”, Distributed and Parallel Databases, Vol. 38, No. 2, (2020), 365-400, DOI: 10.1007/s10619-019-07273-y.
  38. Calheiros. R. N, Ranjan. R, Beloglazov. A, De Rose. C. A. F, and Buyya. R, “CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms”, Software: Practice and Experience, Vol. 41, No. 1, (2011), 23-50, DOI: 10.1002/spe.995.
  39. Shojafar. M, Javanmardi. S, Abolfazli. S, and Cordeschi. N, “FUGE: A joint meta-heuristic approach to cloud job scheduling algorithm using fuzzy theory and a genetic method”, Cluster Computing, Vol. 18, No. 2, (2015), 829-844, DOI: 10.1007/s10586-014-0420-x.
  40. Xu. B, Zhao. C, Hu. E, and Hu. B, “Job scheduling algorithm based on Berger model in cloud environment”, Advances in Engineering Software, Vol. 42, (2011), No. 7, 419-425, DOI: 10.1016/j.advengsoft.2011.03.007.
  41. Karthick. A. V, Ramaraj. E, and Subramanian. R. G, “An efficient multi queue job scheduling for cloud computing”, 2014 World Congress on Computing and Communication Technologies, Trichirappalli, India, (2014), DOI: 10.1109/WCCCT.2014.8.
  42. Babu. G, and Krishnasamy. K, “Task scheduling algorithm based on Hybrid Particle Swarm Optimization in cloud computing environment”, Journal of Theoretical and Applied Information Technology, Vol. 55, (2013), 33-38.
  43. Kumar. S, and Kalra. M. A, “ Hybrid Approach for Energy-Efficient Task Scheduling in Cloud ”, Proceedings of 2nd International Conference on Communication, Computing and Networking, Singapore, (2018), DOI: 10.1007/978-981-13-1217-5_99.
  44. Holland. J. H, “Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence”, MIT press, (1992).
  45. Karaboga. D, “ An idea based on honey bee swarm for numerical optimization ” Technical report-tr06, Erciyes university, Engineering faculty, Computer engineering department, (2005).
  46. Cotes-Ruiz. I. T, Prado. R. P, García-Galán. S, Muñoz-Expósito. J. E, and Ruiz-Reyes. N, “Dynamic voltage frequency scaling simulator for real workflows energy-aware management in green cloud computing”, PloS One, Vol. 12, No. 1, (2017), DOI: 10.1371/journal.pone.0169803.
  47. Singh. S, and Kalra. M, “Scheduling of independent tasks in cloud computing using modified genetic algorithm”, 2014 International Conference on Computational Intelligence and Communication Networks, Bhopal, India, (2014), DOI: 10.1109/CICN.2014.128.
  48. Prem Jacob. T, and Pradeep. K, “A Multi-objective Optimal Task Scheduling in Cloud Environment Using Cuckoo Particle Swarm Optimization”, Wireless Personal Communications, Vol. 109, No. 1, (2019), 315-331, DOI: 10.1007/s11277-019-06566-w.
  49. Yang. X.-S, and Deb. S, “Cuckoo search via Lévy flights”, World Congress on Nature & Biologically Inspired Computing (NaBIC), Coimbatore, India, (2009), doi: 10.1109/NABIC.2009.5393690.
  50. Wu. D, “Cloud computing task scheduling policy based on improved particle swarm optimization”, Proceedings - 2018 International Conference on Virtual Reality and Intelligent Systems, ICVRIS 2018, Hunan, China, (2018), DOI: 10.1109/ICVRIS.2018.00032.
  51. Elaziz. M. A, Xiong. S, Jayasena. K. P. N, and Li. L, “Task scheduling in cloud computing based on hybrid moth search algorithm and differential evolution”, Knowledge-Based Systems, Vol. 169, (2019), 39-52, DOI: 10.1016/j.knosys.2019.01.023.
  52. Wang. G.-G, “Moth search algorithm: a bio-inspired metaheuristic algorithm for global optimization problems”, Memetic Computing, Vol. 10, (2018), No. 2, 151-164, DOI: 10.1007/s12293-016-0212-3.
  53. Storn. R, and Price. K, “Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces”, Journal of Global Optimization, Vol. 11, No. 4, (1997), 341-359, DOI: 10.1023/A:1008202821328.
  54. Guo. X, “Multi-objective task scheduling optimization in cloud computing based on fuzzy self-defense algorithm”, Alexandria Engineering Journal, Vol. 60, No. 6, (2021), 5603-5609, DOI: 10.1016/j.aej.2021.04.051.
  55. Sharma. M, and Garg. R, “An artificial neural network based approach for energy efficient task scheduling in cloud data centers”, Sustainable Computing: Informatics and Systems, Vol. 26, (2020), DOI: 10.1016/j.suscom.2020.100373.
  56. Paknejad. P, Khorsand. R, and Ramezanpour. M, “Chaotic improved PICEA-g-based multi-objective optimization for workflow scheduling in cloud environment”, Future Generation Computer Systems, Vol. 117, (2021), 12-28, DOI: 10.1016/j.future.2020.11.002.
  57. Wei. X, “Task scheduling optimization strategy using improved ant colony optimization algorithm in cloud computing”, Journal of Ambient Intelligence and Humanized Computing, (2020), DOI: 10.1007/s12652-020-02614-7.
  58. Chen. X, Cheng. L, Liu. C, Liu. Q, Liu. J, Mao. Y, and Murphy. J, “A WOA-based optimization approach for task scheduling in cloud computing systems”, IEEE Systems Journal, Vol. 14, No. 3, (2020), 3117-3128, DOI: 10.1109/JSYST.2019.2960088.
  59. Tubishat. M, Abushariah. M. A. M, Idris. N, and Aljarah. I, “Improved whale optimization algorithm for feature selection in Arabic sentiment analysis”, Applied Intelligence, Vol. 49, No. 5, (2019), 1688-1707, DOI: 10.1007/s10489-018-1334-8.
  60. Tos. U, Mokadem. R, Hameurlain. A, Ayav. T, and Bora. S, “A performance and profit oriented data replication strategy for cloud systems”, 2016 Intl IEEE Conferences on Ubiquitous Intelligence & Computing, Advanced and Trusted Computing, Scalable Computing and Communications, Cloud and Big Data Computing, Internet of People, and Smart World Congress (UIC/ATC/ScalCom/CBDCom/IoP/SmartWorld), Toulouse, France, (2016), DOI: 10.1109/UIC-ATC-ScalCom-CBDCom-IoP-SmartWorld.2016.0125.