SpringerLink
Log in

PSO+LOA: hybrid constrained optimization for scheduling scientific workflows in the cloud

  • Published:
The Journal of Supercomputing Aims and scope Submit manuscript

Abstract

Cloud computing provides a cost-effective deploying environment for hosting and executing workflows as its elasticity, scalability and pay-per-use model. Scientific applications are normally compute- or resource-intensive, and how to run them in the cloud while both meeting QoS of users and guaranteeing the benefits of cloud service providers (CSPs) is still a challenge and depends mainly on workflow scheduling. In this article, we propose a hybrid optimization approach, PSO+LOA, i.e., a combination of particle swarm optimization (PSO) and lion optimization algorithm (LOA) for scheduling workflows in the cloud to minimize the total execution time under budget constraints. The main contributions of our work are: (1) A Euclidean distance (ED) aware particle reposition strategy is defined for two close particles, so as to separate them away from each other, hence enhancing the capability of esca** from local optima. (2) To improve the search and convergence efficiency of original PSO, we modify the velocity update equation by introducing adaptive parameters. (3) Inspired by the multiple-swarm co-evolutionary mechanism of LOA, we integrate PSO with LOA to make a good balance between exploration and exploitation during the whole optimization process. Extensive experiments are conducted over well-known scientific workflows with different sizes and types through WorkflowSim. The experimental results demonstrate that in most cases, PSO+LOA outperforms the existing algorithms in the extent of budget constraint satisfiability, solution quality, i.e., it can generate much better solutions which meet the needs of different budget constraints, especially for large-scale applications, such as the average relative deviation index for PSO+LOA and genetic algorithm (GA) are 0.03% and 0.20%, respectively.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price includes VAT (Canada)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

References

  1. Buyya R, Yeo CS, Venugopal S, Broberg J, Brandic I (2009) Cloud computing and emerging it platforms: Vision, hype, and reality for delivering computing as the 5th utility. Future Gener Comput Syst 25(6):599–616

    Article  Google Scholar 

  2. Aziza H, Krichen S (2020) A hybrid genetic algorithm for scientific workflow scheduling in cloud environment. Neural Comput Appl 32(18):1433–3058

    Article  Google Scholar 

  3. Chen Z, Zhan Z, Lin Y, Gong Y, Gu T, Zhao F, Yuan H, Chen X, Li Q, Zhang J (2019) Multiobjective cloud workflow scheduling: a multiple populations ant colony system approach. IEEE Trans Cybern 49(8):2912–2926

    Article  Google Scholar 

  4. Rodriguez MA, Buyya R (2014) Deadline based resource provisioning and scheduling algorithm for scientific workflows on clouds. IEEE Trans Cloud Comput 2(2):222–235

    Article  Google Scholar 

  5. Yazdani M, Jolai F (2016) Lion optimization algorithm (loa): a nature-inspired metaheuristic algorithm. J Comput Design Eng 3(1):24–36

    Article  Google Scholar 

  6. Ilavarasan E, Thambidurai P (2007) Low complexity performance effective task scheduling algorithm for heterogeneous computing environments. J Comput Sci 3(2):94–103

    Article  Google Scholar 

  7. Kwok YK, Ahmad I (1996) Dynamic critical-path scheduling: an effective technique for allocating task graphs to multiprocessors. IEEE Trans Parallel Distrib Syst 7(5):506–521

    Article  Google Scholar 

  8. Sakellariou R, Zhao H, Tsiakkouri E, Dikaiakos MD (1970) Scheduling workflows with budget constraints. In: Integrated Research in GRID Computing, Springer, pp 189–202. https://doi.org/10.1007/978-0-387-47658-2_14

  9. Abrishami S, Naghibzadeh M, Epema DH (2011) Cost-driven scheduling of grid workflows using partial critical paths. IEEE Trans Parallel Distrib Syst 23(8):1400–1414

    Article  Google Scholar 

  10. Abrishami S, Naghibzadeh M, Epema DH (2013) Deadline-constrained workflow scheduling algorithms for infrastructure as a service clouds. Future Gener Comput Syst 29(1):158–169

    Article  Google Scholar 

  11. Arabnejad H, Barbosa JG, Prodan R (2016) Low-time complexity budget-deadline constrained workflow scheduling on heterogeneous resources. Future Gener Comput Syst 55:29–40

    Article  Google Scholar 

  12. Arabnejad V, Bubendorfer K, Ng B (2019) Budget and deadline aware e-science workflow scheduling in clouds. IEEE Trans Parallel Distrib Syst 30(1):29–44

    Article  Google Scholar 

  13. Rizvi N, Ramesh D (2019) Design of a scheduling approach for budget-deadline constrained applications in heterogeneous clouds. Distrib Comput Int Technol. https://doi.org/10.1007/978-3-030-36987-3_12

    Article  Google Scholar 

  14. Kalyan Chakravarthi SLVVK (2020) Budget aware scheduling algorithm for workflow applications in iaas clouds. Clust Comput 23(4):3405–3419

    Article  Google Scholar 

  15. Jain R (2020) Eaco: an enhanced ant colony optimization algorithm for task scheduling in cloud computing. Int J Sec Appl 13:91–100 (10.33832/ijsia.2019.13.4.09)

    Google Scholar 

  16. Li F, Zhang L, Liao TW, Liu Y (2019) Multi-objective optimisation of multi-task scheduling in cloud manufacturing. Int J Prod Res 57(11–12):3847–3863

    Article  Google Scholar 

  17. Net**da N, Sirinaovakul B, Achalakul T (2014) Cost optimal scheduling in iaas for dependent workload with particle swarm optimization. J Supercomput 68(3):1579–1603

    Article  Google Scholar 

  18. Ambursa FU, Latip R, Abdullah A, Subramaniam S (2017) A particle swarm optimization and min-max-based workflow scheduling algorithm with qos satisfaction for service-oriented grids. J Supercomput 73(5):2018–2051

    Article  Google Scholar 

  19. Wang P, Lei Y, Agbedanu PR, Zhang Z (2020) Makespan-driven workflow scheduling in clouds using immune-based pso algorithm. IEEE Access 8:1

    Article  Google Scholar 

  20. Verma A, Kaushal S (2014) Bi-criteria priority based particle swarm optimization workflow scheduling algorithm for cloud. In: 2014 Recent Advances in Engineering and Computational Sciences (RAECS), IEEE, pp 1–6. https://doi.org/10.1109/RAECS.2014.6799614

  21. Chitra S, Madhusudhanan B, Sakthidharan G, Saravanan P (2014) Local minima jump pso for workflow scheduling in cloud computing environments. In: Advances in Computer Science and its Applications, Springer, pp 1225–1234. https://doi.org/10.1007/978-3-642-41674-3_170

  22. Ramadhan M, Latip R, Hussin M, Asilawati N (2020) A survey on qos requirements based on particle swarm optimization scheduling techniques for workflow scheduling in cloud computing. Symmetry 12:551

    Article  Google Scholar 

  23. Hosseinzadeh M, Ghafour MY, Hama HK, Vo B, Khoshnevis A (2020) Multi-objective task and workflow scheduling approaches in cloud computing: a comprehensive review. J Grid Comput 18(3):327–356

    Article  Google Scholar 

  24. Almezeini N, Hafez A (2017) Task scheduling in cloud computing using lion optimization algorithm. Int J Adv Comput Sci Appl 8(11):77–83

    Google Scholar 

  25. Manikandan N, Pravin A (2019) Lgsa: hybrid task scheduling in multi objective functionality in cloud computing environment. 3D Res 10(2):12

    Article  Google Scholar 

  26. Wu F, Wu Q, Tan Y (2015) Workflow scheduling in cloud: a survey. J Supercomput 71(9):3373–3418

    Article  Google Scholar 

  27. Kennedy J, Eberhart R (2002) Particle swarm optimization. In: Icnn95-international Conference on neural networks. https://doi.org/10.1109/ICNN.1995.488968

  28. Chen K, Zhou F, Yin L, Wang S, Wang Y, Wan F (2018) A hybrid particle swarm optimizer with sine cosine acceleration coefficients. Inform Sci 422:218–241

    Article  MathSciNet  Google Scholar 

  29. Chen W, Deelman E (2012) Workflowsim: A toolkit for simulating scientific workflows in distributed environments. In: 2012 IEEE 8th International Conference on E-Science, IEEE, pp 1–8. https://doi.org/10.1109/eScience.2012.6404430

  30. Juve G, Chervenak A, Deelman E, Bharathi S, Mehta G, Vahi K (2013) Characterizing and profiling scientific workflows. Future Gener Comput Syst 29(3):682–692

    Article  Google Scholar 

  31. Ostermann S, Iosup A, Yigitbasi N, Prodan R, Fahringer T, Epema D (2009) A performance analysis of ec2 cloud computing services for scientific computing. In: International Conference on cloud computing, Springer, pp 115–131. https://doi.org/10.1109/ICNN.1995.488968

  32. Li X, Cai Z (2015) Elastic resource provisioning for cloud workflow applications. IEEE Trans Autom Sci Eng 14(2):1195–1210

    Article  Google Scholar 

Download references

Acknowledgements

The work is supported in part by the National Key Research and Development Program of China under Grant No. 2018YFB1003700 and in part by the National Natural Science Foundation of China under Grant No. 61836001.

Author information

Authors and Affiliations

  1. School of Automation, Bei**g Institute of Technology, Bei**g, China

    Huifang Li, Dan**g Wang, Julio Ruben Cañizares Abreu & Orlando Bonilla Pineda

  2. Faculty of Information Technology, Bei**g University of Technology, Bei**g, China

    Qing Zhao

Authors
  1. Huifang Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Dan**g Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Julio Ruben Cañizares Abreu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Qing Zhao
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Orlando Bonilla Pineda
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Huifang Li or Qing Zhao.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Li, H., Wang, D., Cañizares Abreu, J.R. et al. PSO+LOA: hybrid constrained optimization for scheduling scientific workflows in the cloud. J Supercomput 77, 13139–13165 (2021). https://doi.org/10.1007/s11227-021-03755-y

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11227-021-03755-y

Keywords

Search

Navigation