Top

The Journal of Supercomputing

Published in:

26-07-2022

A hybrid bi-objective scheduling algorithm for execution of scientific workflows on cloud platforms with execution time and reliability approach

Authors: Yeganeh Asghari Alaie, Mirsaeid Hosseini Shirvani, Amir Masoud Rahmani

Published in: The Journal of Supercomputing | Issue 2/2023

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Heterogeneous cloud datacenters are well-suited and cost-efficient platforms for execution of scientific workflows requested from academics. Workflow scheduling algorithms have drastic impacts on the objectives that stakeholders in the system expect. This paper models the scientific workflow scheduling issue to a bi-objective optimization problem with makespan and reliability optimization approach because the users not only expect to have quick response, but also they need reliable executions. To address the issue, a new system framework and different concepts are introduced. A centralized log as a repository module is embedded in the system framework to register all kinds of system failures. In addition to, the new scheduling failure factor (SFF), which has reciprocal relation with system reliability, is defined. Therefore, the broker module quantifies the failure proneness of all resources and the most reliable ones are incorporated in scheduling model. The aforementioned scheduling model is then formulated to a bi-objective optimization problem with makespan and SFF minimization viewpoint which is an NP-Hard problem. To solve this combinatorial problem, a hybrid bi-objective discrete cuckoo search algorithm (HDCSA) is proposed. The proposed hybrid algorithm utilizes different novel Levy flight operators commensurate with discrete search space that makes good balance between exploration and exploitation in optimization process. The proposed HDCSA was validated in 12 extensive scenarios that were conducted on both symmetric and asymmetric scientific workflows in different conditions. The final results prove that the proposed bi-objective HDCSA scheduler has the amount of 22.11%, 12.97%, 11.81%, 12.18%, and 12.42% on average improvement against other state-of-the-arts in terms of makespan, SFF, speedup, efficiency, and SLR, respectively, which are prominent performance evaluation metrics is this scheduling domain.

previous article Generic and scalable DNA-based logic design methodology for massive parallel computation

next article Memory management optimization strategy in Spark framework based on less contention

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Hosseini Shirvani M, Rahmani AM, Sahafi A (2018) An iterative mathematical decision model for cloud migration: a cost and security risk approach. Softw Pract Exp 48(3):449–485. https://doi.org/10.1002/spe.2528CrossRef

Przybylski B (2021) Parallel-machine scheduling of jobs with mixed job-, machine- and position-dependent processing times. J Comb Optim. https://doi.org/10.1007/s10878-021-00821-2CrossRefMATH

Konjaang JK, Xu L (2021) Multi-objective workflow optimization strategy (MOWOS) for cloud computing. J Cloud Comput 10:11. https://doi.org/10.1186/s13677-020-00219-1CrossRef

Zhou X, Wang H, Ding B, Hu T, Shang S (2018) Balanced connected task allocations for multi-robot systems: an exact ßow-based integer program and an approximate tree-based genetic algorithm. Expert Syst Appl. https://doi.org/10.1016/j.eswa.2018.09.001CrossRef

Hosseini Shirvani M (2020) A hybrid meta-heuristic algorithm for scientific workflow scheduling in heterogeneous distributed computing systems. Eng Appl Artif Intell 90:103501. https://doi.org/10.1016/j.engappai.2020.103501CrossRef

Bharathi S, Chervenak A, Deelman E, Mehta G, Su MH, Vahi K (2008) Characterization of scientific workflows. In: 2008 Third Workshop on Workflows in Support of Large-Scale Science. IEEE, pp 1–10. https://doi.org/10.1109/WORKS.2008.4723958

Mohammadzadeh A, Masdari M, Gharehchopogh FS et al (2021) A hybrid multi-objective metaheuristic optimization algorithm for scientific workflow scheduling. Cluster Comput 24:1479–1503. https://doi.org/10.1007/s10586-020-03205-zCrossRef

Topcuoglu H, Hariri S, Wu MY (2002) Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Trans Parallel Distrib Syst 13(3):260–274. https://doi.org/10.1109/71.993206CrossRef

Mohammadzadeh A, Masdari M, Gharehchopogh FS et al (2021) Improved chaotic binary grey wolf optimization algorithm for workflow scheduling in green cloud computing. Evol Intell 14:1997–2025. https://doi.org/10.1007/s12065-020-00479-5CrossRef

10.

Arabnejad H, Barbosa JG (2014) List scheduling algorithm for heterogeneous systems by an optimistic cost table. IEEE Trans Parallel Distrib Syst 25(3):682–694. https://doi.org/10.1109/TPDS.2013.57CrossRef

11.

Xu Y, Li K, Hu J, Li K (2014) A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues. Inform Sci 270:255–287. https://doi.org/10.1016/j.ins.2014.02.122MathSciNetCrossRefMATH

12.

Al Badawi A, Shatnawi A (2013) Static scheduling of directed acyclic data flow graphs onto multiprocessors using particle swarm optimization. Comput Oper Res 40(10):2322–2328. https://doi.org/10.1016/j.cor.2013.03.015MathSciNetCrossRefMATH

13.

Dordaie N, Jafari Navimipour N (2018) A hybrid particle swarm optimization and hill climbing algorithm for task scheduling in the cloud environments. ICT Press. 4(4):199–202. https://doi.org/10.1016/j.icte.2017.08.001CrossRef

14.

Keshanchi B, Jafari NN (2016) Priority-based task scheduling algorithm in cloud systems using a memetic algorithm. J Circuits Syst Comput 25(10):1650119. https://doi.org/10.1142/S021812661650119XCrossRef

15.

Hosseini Shirvani M, Noorian Talouki R (2021) Bi-objective scheduling algorithm for scientific workflows on cloud computing platform with makespan and monetary cost minimization approach. Complex Intell Syst. https://doi.org/10.1007/s40747-021-00528-1CrossRef

16.

Oukfif K, Oulebsir FB, Bouzefrane S, Banerjee S (2020) Workflow scheduling with data transfer optimization and enhancement of reliability in cloud data centers. Int J Commun Netw Distrib Syst. https://doi.org/10.1504/IJCNDS.2020.10021223CrossRef

17.

Boeres C, Sardiña IM, Drummond LMA (2011) An efficient weighted bi-objective scheduling algorithm for heterogeneous systems. Parallel Comput 37(8):349–364. https://doi.org/10.1016/j.parco.2010.10.003CrossRef

18.

Zhang L, Li K, Li C, Li K (2017) Bi-objective workflow scheduling of the energy consumption and reliability in heterogeneous computing systems. Inf Sci 379(10):241–256. https://doi.org/10.1016/j.ins.2016.08.003CrossRef

19.

Wang X, Yeo CS, Buyya R, Su J (2011) Optimizing makespan and reliability for workflow applications with reputation and look-ahead genetic algorithm. Fut Gener Comput Syst 27(8):1124–1134. https://doi.org/10.1016/j.future.2011.03.008CrossRef

20.

Amandeep V, Sakshi K (2017) A hybrid multi-objective particle swarm optimization for scientific workflow scheduling. Parallel Comput 62:1–19. https://doi.org/10.1016/j.parco.2017.01.002MathSciNetCrossRef

21.

Mohammadzadeh A, Masdari M, Gharehchopogh FS (2021) Energy and cost-aware workflow scheduling in cloud computing data centers using a multi-objective optimization algorithm. J Netw Syst Manag 29(31):2021. https://doi.org/10.1007/s10922-021-09599-4CrossRef

22.

Kennedy J, Eberhart R (1995) Particle swarm optimization. In: Proceedings of IEEE International Conference on Neural Networks. IV, pp 1942–1948. https://doi.org/10.1109/ICNN.1995.488968

23.

Mirjalili S, Mirjalili SM, Lewis A (2014) Grey Wolf optimizer. Adv Eng Softw 69(46–61):2014. https://doi.org/10.1016/j.advengsoft.2013.12.007CrossRef

24.

Mirjalili S, Lewis A (2016) The Whale optimization algorithm. Adv Eng Softw 95:51–67. https://doi.org/10.1016/j.advengsoft.2016.01.008CrossRef

25.

Sathya Sofia A, GaneshKumar P (2018) Multi-objective task scheduling to minimize energy consumption and makespan of cloud computing using NSGA-II. J Netw Syst Manag 26:463–485. https://doi.org/10.1007/s10922-017-9425-0CrossRef

26.

Bahnasawy NA, Fatma O, Magdy AK, Mervat M (2011) Optimization procedure for algorithms of task scheduling in high performance heterogeneous distributed computing systems. Egypt Inform J 12(3):219–229. https://doi.org/10.1016/j.eij.2011.10.001CrossRef

27.

Zhou J, Zhang M, Sun J, Wang T, Zhou X, Hu S (2022) DRHEFT: deadline-constrained reliability-aware HEFT algorithm for real-time heterogeneous MPSoC systems. IEEE Trans Reliab 71:178–189. https://doi.org/10.1109/TR.2020.2981419CrossRef

28.

Zhou J, Sun J, Zhou X, Wei T, Hu XS (2018) Resource management for improving soft error and lifetime reliability of real-time MPSoCs. IEEE Trans Comput-Aided Des Integr Circuits Syst 38(12):2215–2228. https://doi.org/10.1109/TCAD.2018.2883993CrossRef

29.

Hosseini Shirvani MS, Noorian TR (2021) A novel hybrid heuristic-based list scheduling algorithm in heterogeneous cloud computing environment for makespan optimization. Parallel Comput 108:102828. https://doi.org/10.1016/j.parco.2021.102828MathSciNetCrossRef

30.

Gulbaz R, Siddiqui AB, Anjum N, Alotaibi AA, Althobaiti T, Ramzan N (2021) Balancer genetic algorithm—a novel task scheduling optimization approach in cloud computing. Appl Sci 11:6244. https://doi.org/10.3390/app11146244CrossRef

31.

Alsaidy SA, Abbood AD, Sahib MA (2020) Heuristic initialization of PSO task scheduling algorithm in cloud computing. J King Saud Univ Comput Inf Sci. https://doi.org/10.1016/j.jksuci.2020.11.002CrossRef

32.

Natesan G, Chokkalingam A (2019) Task scheduling in heterogeneous cloud environment using mean grey wolf optimization algorithm. ICT Press 5(2):110–114. https://doi.org/10.1016/j.icte.2018.07.002CrossRef

33.

Chen X et al (2020) A WOA-based optimization approach for task scheduling in cloud computing systems. IEEE Syst J 14(3):3117–3128. https://doi.org/10.1109/JSYST.2019.2960088CrossRef

34.

Thennarasu SR, Selvam M, Srihari K (2020) A new whale optimizer for workflow scheduling in cloud computing environment. J Ambient Intell Human Comput 12(3):3807–3814. https://doi.org/10.1007/s12652-020-01678-9CrossRef

35.

Zhou J, Wang T, Cong P, Lu P, Wei T, Chen M (2019) Cost and makespan-aware workflow scheduling in hybrid clouds. J Syst Archit 100:101631. https://doi.org/10.1016/j.sysarc.2019.08.004CrossRef

36.

Natesan G, Chokkalingam A (2020) An improved Grey Wolf optimization algorithm based task scheduling in cloud computing environment. Int Arab J Inf Technol 17(1):73–81. https://doi.org/10.34028/iajit/17/1/9CrossRef

37.

Abdel-Basset M, Shahat DE, Deb K, Abouhawwash M (2020) Energy-aware whale optimization algorithm for real-time task scheduling in multiprocessor systems. Appl Soft Comput. https://doi.org/10.1016/j.asoc.2020.106349CrossRef

38.

Zhou X, Zhang G, Wang T, Zhang M, Wang X, Zhang W (2020) Makespan–cost–reliability-optimized workflow scheduling using evolutionary techniques in clouds. J Circuits Syst Comput 29(10):1–21. https://doi.org/10.1142/S0218126620501674CrossRef

39.

Tanha M, Hosseini Shirvani MS, Rahmani AM (2021) A hybrid meta-heuristic task scheduling algorithm based on genetic and thermodynamic simulated annealing algorithms in cloud computing environments. Neural Comput Appl 33:16951–16984. https://doi.org/10.1007/s00521-021-06289-9CrossRef

40.

Noorian TR, Hosseini Shirvani MS, Motameni H (2021) A heuristic-based task scheduling algorithm for scientific workflows in heterogeneous cloud computing platforms. J King Saud Univ-Comput Inf Sci. https://doi.org/10.1016/j.jksuci.2021.05.011CrossRef

41.

Durillo JJ, NaeV PR (2014) Multi-objective energy-efficient workflow scheduling using list-based heuristics. Futur Gener Comput Syst 36:221–236. https://doi.org/10.1016/j.future.2013.07.005CrossRef

42.

Javadi B, Abawajy J, Buyya R (2012) Failure-aware resource provisioning for hybrid cloud infrastructure. J Parallel Distrib Comput 72(10):1318–1331. https://doi.org/10.1016/j.jpdc.2012.06.012CrossRef

43.

Choudhary A, Govil MC, Singh G, Awasthi LK, Pilli ES (2018) Task clustering-based energy-aware workflow scheduling in cloud environment. In: 2018 IEEE 20th International Conference on High Performance Computing and Communications; IEEE 16th International Conference on Smart City; IEEE 4th International Conference on Data Science and Systems (HPCC/SmartCity/DSS), 2018, pp 968–973. https://doi.org/10.1109/HPCC/SmartCity/DSS.2018.00160.

44.

Lin CS, Lin CS, Lin YS, Hsiung PA, Shih C (2013) Multi-objective exploitation of pipeline parallelism using clustering, replication and duplication in embedded multi-core systems. J Syst Archit 59(10):1083–1094. https://doi.org/10.1016/j.sysarc.2013.05.024CrossRef

45.

Akbari M, Rashidi H (2016) A multi-objectives scheduling algorithm based on cuckoo optimization for task allocation problem at compile time in heterogeneous systems. Expert Syst Appl 60(30):234–248. https://doi.org/10.1016/j.eswa.2016.05.014CrossRef

46.

Jin S, Schiavone G, Turgut D (2008) A performance study of multiprocessor task scheduling algorithms. J Supercomput 43(1):77–97. https://doi.org/10.1007/s11227-007-0139-zCrossRef

47.

Yang XS, Deb S (2009) Cuckoo search via Levy flights. In: Proceedings of World Congress on Nature and Biologically Inspired Computing, pp 210–214. https://doi.org/10.1109/NABIC.2009.5393690.

48.

Saeedi P, Hosseini Shirvani MS (2021) An improved thermodynamic simulated annealing-based approach for resource-skewness-aware and power-efficient virtual machine consolidation in cloud datacenters. Soft Comput 25:5233–5260. https://doi.org/10.1007/s00500-020-05523-1CrossRef

49.

Mirmohseni SM, Javadpour A, Tang C (2021) LBPSGORA: create load balancing with particle swarm genetic optimization algorithm to improve resource allocation and energy consumption in clouds networks. Math Problems Eng 2021:1–15. https://doi.org/10.1155/2021/5575129CrossRef

Title: A hybrid bi-objective scheduling algorithm for execution of scientific workflows on cloud platforms with execution time and reliability approach
Authors: Yeganeh Asghari Alaie
Mirsaeid Hosseini Shirvani
Amir Masoud Rahmani
Publication date: 26-07-2022
Publisher: Springer US
Published in: The Journal of Supercomputing / Issue 2/2023
Print ISSN: 0920-8542
Electronic ISSN: 1573-0484
DOI: https://doi.org/10.1007/s11227-022-04703-0

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 2/2023

Stable parallel training of Wasserstein conditional generative adversarial neural networks

VANET authentication protocols: security analysis and a proposal

Traffic sign detection based on multi-scale feature extraction and cascade feature fusion

Secure cloud storage with anonymous deduplication using ID-based key management

Traffic-aware dynamic controller placement in SDN using NFV

A cost and makespan aware scheduling algorithm for dynamic multi-workflow in cloud environment

Premium Partner