Skip to main content
Top
Published in: Neural Computing and Applications 24/2021

18-07-2021 | Original Article

A hybrid meta-heuristic task scheduling algorithm based on genetic and thermodynamic simulated annealing algorithms in cloud computing environments

Authors: Mozhdeh Tanha, Mirsaeid Hosseini Shirvani, Amir Masoud Rahmani

Published in: Neural Computing and Applications | Issue 24/2021

Log in

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

search-config
loading …

Abstract

Cloud providers deliver heterogeneous virtual machines to run complicated jobs submitted by users. The task scheduling issue is formulated to a discrete optimization problem which is well-known NP-Hard. This paper presents a hybrid meta-heuristic algorithm based on genetic and thermodynamic simulated annealing algorithms to solve this problem. In the proposed algorithm, the genetic and simulated annealing algorithms have respective global and local search inclinations covering each other's shortcomings. A novel theorem is presented and applied to produce a semi-conducted initial population. In a used genetic algorithm with a global trend, the crossover operator is performed to explore search space. The thermodynamic simulated annealing algorithm is utilized to improve the efficiency, which considers entropy and energy difference concepts in the cooling schedule process. After obtaining a suitable solution, one of the three novel neighbor operators is randomly called to enhance the given solution potentially. In this way, the efficient balance between exploration and exploitation in the search space is achieved. Simulation results prove that the proposed hybrid algorithm has 10.17%, 9.31%, 7.76%, and 8.21% dominance in terms of makespan, schedule length ratio, speedup, and efficiency against other comparative algorithms.

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!

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!

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!

Literature
3.
go back to reference Hosseini Shirvani M (2020) To move or not to move: an iterative four-phase cloud adoption decision model for IT outsourcing based on TCO. J Soft Comput Inf Technol 9(2):7–17 Hosseini Shirvani M (2020) To move or not to move: an iterative four-phase cloud adoption decision model for IT outsourcing based on TCO. J Soft Comput Inf Technol 9(2):7–17
5.
go back to reference Hosseini Shirvani M, Ghojoghi A (2018) Server consolidation schemes in cloud computing environment: a review. Eur J Eng Res Sci 1(2018):18–24 Hosseini Shirvani M, Ghojoghi A (2018) Server consolidation schemes in cloud computing environment: a review. Eur J Eng Res Sci 1(2018):18–24
6.
go back to reference Keshanch B, Jafari Navimipour N (2016) Priority-based task scheduling algorithm in cloud systems using a memetic algorithm. J Circuits Syst Comput 25(10):1–33 Keshanch B, Jafari Navimipour N (2016) Priority-based task scheduling algorithm in cloud systems using a memetic algorithm. J Circuits Syst Comput 25(10):1–33
8.
go back to reference Amin GR, Hosseini Shirvani M (2009) Evaluation of scheduling solutions in parallel processing using DEA FDH model. J Ind Eng Int 5(9):58–62 Amin GR, Hosseini Shirvani M (2009) Evaluation of scheduling solutions in parallel processing using DEA FDH model. J Ind Eng Int 5(9):58–62
9.
go back to reference Hosseini-Shirvani M (2015) Evaluating of feasible solutions on parallel scheduling tasks with DEA decision maker. J Adv Comput Res 6:109–115 Hosseini-Shirvani M (2015) Evaluating of feasible solutions on parallel scheduling tasks with DEA decision maker. J Adv Comput Res 6:109–115
15.
go back to reference Liou J, Palis MA (1996) An efficient task clustering heuristic for scheduling DAGs on multiprocessors. Symp Parallel Distrib Process 152–156 Liou J, Palis MA (1996) An efficient task clustering heuristic for scheduling DAGs on multiprocessors. Symp Parallel Distrib Process 152–156
23.
go back to reference de Vicente J, Lanchares J, Hermida R (2003) Placement by thermodynamic simulated annealing. Phys Lett A 317(56):415–423CrossRef de Vicente J, Lanchares J, Hermida R (2003) Placement by thermodynamic simulated annealing. Phys Lett A 317(56):415–423CrossRef
24.
go back to reference Xu Y, Li K, Hu J, Li K (2014) A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues. Inf Sci 270:255–287MathSciNetCrossRef Xu Y, Li K, Hu J, Li K (2014) A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues. Inf Sci 270:255–287MathSciNetCrossRef
25.
go back to reference Hosseini Shirvani M (2018) A new shuffled genetic-based task scheduling algorithm in heterogeneous distributed systems. Heterog Distrib Syst J Adv Comput Res, pp 19–36 Hosseini Shirvani M (2018) A new shuffled genetic-based task scheduling algorithm in heterogeneous distributed systems. Heterog Distrib Syst J Adv Comput Res, pp 19–36
27.
go back to reference Azimi S, Pahl C, Hosseini Shirvani M (2020) Particle swarm optimization for performance management in multi-cluster IoT edge architectures. In: International cloud computing conference CLOSER, pp 328–337 Azimi S, Pahl C, Hosseini Shirvani M (2020) Particle swarm optimization for performance management in multi-cluster IoT edge architectures. In: International cloud computing conference CLOSER, pp 328–337
28.
go back to reference SA Alsaidy, AD Abbood, MA Sahib (2020) Heuristic initialization of PSO task scheduling algorithm in cloud computing. J King Saud Univ Comput Inf Sci 13 In Press SA Alsaidy, AD Abbood, MA Sahib (2020) Heuristic initialization of PSO task scheduling algorithm in cloud computing. J King Saud Univ Comput Inf Sci 13 In Press
29.
go back to reference Keshani M, Jahanshahi MH (2009) Using simulated annealing for task scheduling in distributed systems. In: 2009 International conference on computational intelligence, modelling and simulation Keshani M, Jahanshahi MH (2009) Using simulated annealing for task scheduling in distributed systems. In: 2009 International conference on computational intelligence, modelling and simulation
33.
go back to reference Mirjalili S, Mirjalili SM, Lewis A (2014) Grey wolf optimizer. Adv Eng Softw 69:46–61CrossRef Mirjalili S, Mirjalili SM, Lewis A (2014) Grey wolf optimizer. Adv Eng Softw 69:46–61CrossRef
34.
go back to reference Mirjalili S, Lewis A (2016) The whale optimization algorithm. Adv Eng Softw 95:51–67CrossRef Mirjalili S, Lewis A (2016) The whale optimization algorithm. Adv Eng Softw 95:51–67CrossRef
35.
go back to reference Rashedi E, Nezamabadi-Pour H, Saryazdi S (2009) GSA: a gravitational search algorithm. Inf Sci 179(13):2232–2248CrossRef Rashedi E, Nezamabadi-Pour H, Saryazdi S (2009) GSA: a gravitational search algorithm. Inf Sci 179(13):2232–2248CrossRef
37.
go back to reference Guo P, Xue Z (2017) Cost-effective fault-tolerant scheduling algorithm for real-time tasks in cloud systems. In: 2017 17th IEEE international conference on communication technology Guo P, Xue Z (2017) Cost-effective fault-tolerant scheduling algorithm for real-time tasks in cloud systems. In: 2017 17th IEEE international conference on communication technology
38.
go back to reference Darbha S, Agrawal DP (1997) A task duplication based scalable scheduling algorithm for distributed memory systems. J Parallel Distrib Comput 46:15–27CrossRef Darbha S, Agrawal DP (1997) A task duplication based scalable scheduling algorithm for distributed memory systems. J Parallel Distrib Comput 46:15–27CrossRef
39.
go back to reference Palis MA, Liou JC, Wie DSL (1996) Task clustering and scheduling for distributed memory parallel architectures. IEEE Trans Parallel Distrib Syst 7(1):46–55CrossRef Palis MA, Liou JC, Wie DSL (1996) Task clustering and scheduling for distributed memory parallel architectures. IEEE Trans Parallel Distrib Syst 7(1):46–55CrossRef
44.
go back to reference Sreenu K, Malempati S (2018) FGMTS: fractional grey wolf optimizer for multi-objective task scheduling strategy in cloud computing. J Intell Fuzzy Syst 1–14 Sreenu K, Malempati S (2018) FGMTS: fractional grey wolf optimizer for multi-objective task scheduling strategy in cloud computing. J Intell Fuzzy Syst 1–14
45.
go back to reference Khalili A, Babamir SM (2017) Optimal scheduling workflows in cloud computing environment using Pareto-based Grey wolf optimizer. Concurr Comput Pract Exp 29:e4044CrossRef Khalili A, Babamir SM (2017) Optimal scheduling workflows in cloud computing environment using Pareto-based Grey wolf optimizer. Concurr Comput Pract Exp 29:e4044CrossRef
46.
go back to reference Biswas T, Kuila P, Kumar-Ray A, Sarkar M (2019) Gravitational search algorithm based novel workflow scheduling for heterogeneous computing systems. Simul Model Pract Theory 96:101932CrossRef Biswas T, Kuila P, Kumar-Ray A, Sarkar M (2019) Gravitational search algorithm based novel workflow scheduling for heterogeneous computing systems. Simul Model Pract Theory 96:101932CrossRef
50.
go back to reference Hosseini-Shirvani M, Gorji AB (2020) Optimization of automatic web services composition using genetic algorithm. Int J Cloud Comput 9(4):397–411CrossRef Hosseini-Shirvani M, Gorji AB (2020) Optimization of automatic web services composition using genetic algorithm. Int J Cloud Comput 9(4):397–411CrossRef
52.
go back to reference Bäck T (1996) Evolutionary algorithms in theory and practice. Oxford University Press, Oxford, p 120CrossRef Bäck T (1996) Evolutionary algorithms in theory and practice. Oxford University Press, Oxford, p 120CrossRef
53.
go back to reference Kamalinia A, Ghaffari A (2016) Hybrid task scheduling method for cloud computing by genetic and PSO algorithms. J Inf Syst Telecommun (JIST) 4(4):271–281 Kamalinia A, Ghaffari A (2016) Hybrid task scheduling method for cloud computing by genetic and PSO algorithms. J Inf Syst Telecommun (JIST) 4(4):271–281
Metadata
Title
A hybrid meta-heuristic task scheduling algorithm based on genetic and thermodynamic simulated annealing algorithms in cloud computing environments
Authors
Mozhdeh Tanha
Mirsaeid Hosseini Shirvani
Amir Masoud Rahmani
Publication date
18-07-2021
Publisher
Springer London
Published in
Neural Computing and Applications / Issue 24/2021
Print ISSN: 0941-0643
Electronic ISSN: 1433-3058
DOI
https://doi.org/10.1007/s00521-021-06289-9

Other articles of this Issue 24/2021

Neural Computing and Applications 24/2021 Go to the issue

Premium Partner