nach oben

The Journal of Supercomputing

Erschienen in:

06.02.2020

Scheduling scientific workflows on virtual machines using a Pareto and hypervolume based black hole optimization algorithm

verfasst von: Fatemeh Ebadifard, Seyed Morteza Babamir

Erschienen in: The Journal of Supercomputing | Ausgabe 10/2020

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The problem of workflow scheduling on virtual machines in a cloud environment is to find the near optimal permutation of the assignment of independent computational jobs on a set of machines that satisfies conflicting objectives. This problem is known to be an NP-hard problem. Evolutionary multiobjective algorithms are optimization methods to solve such problems. hypervolume is one of the most important criteria that is used to both as solution evaluation and as a guidance for near-optimal selection of a set of solutions called the Pareto front. In this paper, a new hypervolume-based multiobjective algorithm is proposed for driving the Pareto front. To this end, we extend the single-objective Black hole heuristic algorithm based on the adopted \(\theta \)-dominance relation to improving the diversity and convergence to an optimal Pareto front. The conflicting objectives are resource utilization, resource cost, and the workflow makespan (completion time). Also to presenting the appropriate scheduling algorithm, we have proven the correctness of the proposed algorithm by providing the behavioral model of the suggested system using model checking tool. For this purpose, we first introduce the behavioral model of the proposed system using Abstract state machine and extract the properties of the algorithm in the form of linear temporal logic. Then we encode the algorithm using the model checker tool Abstract state Machine Meta-model-based Language and verify the accuracy of the algorithm based on the expected properties, reachability, fairness, and deadlock-free. In order to demonstrate the effectiveness of our method we: (1) extended the WorkflowSim tools, (2) applied it to both balanced and imbalanced workflows and (3) compared results to algorithms, Strength Pareto Evolutionary Algorithm-2, Non-dominated Sorting Genetic Algorithm-2, Multi-Swarm MultiObjective Optimization, Intelligent Water Drops algorithm and Genetic Algorithm and Pareto-based Grey Wolf Optimizer. The comparisons show that by increasing the number of users requests and their correlations, the proposed algorithm can find more optimal Pareto front.

Vorheriger Artikel SWEclat: a frequent itemset mining algorithm over streaming data using Spark Streaming

Nächster Artikel A novel parallel Markov clustering method in biological interaction network analysis under multi-GPU computing environment

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Garey MR, Johnson DS (1990) Computers and intractability; a guide to the theory of NP-completeness. W. H. Freeman & Co., New YorkMATH

Fleischer M (2003) The measure of Pareto optima applications to multi-objective metaheuristics. In: Proceedings of the 2nd International Conference on Evolutionary Multi-criterion Optimization, EMO’03. Springer, Berlin, pp 519–533

Zitzler E, Kunzli S (2004) Indicator-based selection in multiobjective search. In: In Proceedings of 8th International Conference on Parallel Problem Solving from Nature (PPSN VIII). Springer, pp 832–842

Beume N, Naujoks B, Emmerich M (2007) SMS-EMOA: multiobjective selection based on dominated hypervolume. Eur J Oper Res 181:1653–1669MATH

Igel C, Hansen N, Roth S (2007) Covariance matrix adaptation for multi-objective optimization. Evol Comput 15:1–28

Ebadifard F, Babamir SM (2017) Optimizing multi objective based workflow scheduling in cloud computing using black hole algorithm. In: 2017 3th International Conference on Web Research (ICWR), pp 102–108

Hatamlou A (2013) Black hole: a new heuristic optimization approach for data clustering. Inf Sci 222:175–184 Including Special Section on New Trends in Ambient Intelligence and Bio-inspired SystemsMathSciNet

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

Calheiros RN, Ranjan R, Beloglazov A, De Rose CAF, Buyya R (2011) Cloudsim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms. Softw Pract Exp 41:23–50

10.

Zitzler E, Laumanns M, Thiele L (2002) SPEA2: improving the strength Pareto evolutionary algorithm for multiobjective optimization

11.

Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6:182–197

12.

Yao G-S, Ding Y-S, Hao K-R (2017) Multi-objective workflow scheduling in cloud system based on cooperative multi-swarm optimization algorithm. J Central South Univ 24:1050–1062

13.

Kalra M, Singh S (2019) Multicriteria workflow scheduling on clouds under deadline and budget constraints. Concurr Comput Pract Exp 31:e5193

14.

Khalili A, Babamir SM (2017) Optimal scheduling workflows in cloud computing environment using Pareto based grey wolf optimizer. Concurr Comput Pract Exp 29:e4044

15.

Li J, Su S, Cheng X, Huang Q, Zhang Z, Cost-conscious scheduling for large graph processing in the cloud. In: 2011 IEEE International Conference on High Performance Computing and Communications, pp 808–813

16.

Dongarra JJ, Jeannot E, Saule E, Shi Z (2007) Bi-objective scheduling algorithms for optimizing makespan and reliability on heterogeneous systems. In: Proceedings of the Nineteenth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA ’07. ACM, New York, pp 280–288

17.

Sih GC, Lee EA (1993) A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures. IEEE Trans Parallel Distrib Syst 4:175–187

18.

Doğan A, Özgüner F (2005) Biobjective scheduling algorithms for execution time–reliability trade-off in heterogeneous computing systems*. Comput J 48:300–314

19.

Bilgaiyan S, Sagnika S, Das M (2015) A multi-objective cat swarm optimization algorithm for workflow scheduling in cloud computing environment. In: Jain LC, Patnaik S, Ichalkaranje N (eds) Intelligent computing, communication and devices. Springer, New Delhi, pp 73–84

20.

Udomkasemsub O, Xiaorong L, Achalakul T (2012) A multiple-objective workflow scheduling framework for cloud data analytics. In: 2012 Ninth International Conference on Computer Science and Software Engineering (JCSSE), pp 391–398

21.

Wu Z, Ni Z, Gu L, Liu X (2010) A revised discrete particle swarm optimization for cloud workflow scheduling. In: 2010 International Conference on Computational Intelligence and Security, pp 184–188

22.

Zhang M, Li H, Liu L, Buyya R (2018) An adaptive multi-objective evolutionary algorithm for constrained workflow scheduling in clouds. Distrib Parallel Databases 36:339–368

23.

Verma A, Kaushal S (2017) A hybrid multi-objective particle swarm optimization for scientific workflow scheduling. Parallel Comput 62:1–19MathSciNet

24.

Xu H, Yang B, Qi W, Ahene E (2016) A multi-objective optimization approach to workflow scheduling in clouds considering fault recovery. KSII Trans Internet Inf Syst 10(3):976–995

25.

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

26.

Ajeena Beegom AS, Rajasree MS (2019) Non-dominated sorting based PSO algorithm for workflow task scheduling in cloud computing systems. J Intell Fuzzy Syst 37(5):6801–6813

27.

Alazzam H, Alhenawi E, Al-Sayyed R (2019) A hybrid job scheduling algorithm based on Tabu and harmony search algorithms. J Supercomput 76:7994–8011

28.

Dharwadkar N, Poojara S, Kadam P (2018) Fault tolerant and optimal task clustering for scientific workflow in cloud. Int J Cloud Appl Comput 8:1–19

29.

Singh V, Gupta I, Jana P (2019) An energy efficient algorithm for workflow scheduling in IAAS cloud. J Grid Comput

30.

Durillo JJ, Fard HM, Prodan R Moheft (2012) A multi-objective list-based method for workflow scheduling. In: 4th IEEE International Conference on Cloud Computing Technology and Science Proceedings, pp 185–192

31.

Durillo JJ, Prodan R (2014) Multi-objective workflow scheduling in Amazon EC2. Cluster Comput 17:169–189

32.

Talukder AKMKA, Kirley M, Buyya R (2009) Multiobjective differential evolution for scheduling workflow applications on global grids. Concurr Comput Pract Exp 21:1742–1756

33.

Tsai J-T, Fang J-C, Chou J-H (2013) Optimized task scheduling and resource allocation on cloud computing environment using improved differential evolution algorithm. Comput Oper Res 40:3045–3055MATH

34.

Yu J, Kirley M, Buyya R (2007) Multi-objective planning for workflow execution on grids. In: Proceedings of the 8th IEEE/ACM International Conference on Grid Computing, GRID ’07. IEEE Computer Society, Washington, pp 10–17

35.

Zhu Z, Zhang G, Li M, Liu X (2016) Evolutionary multi-objective workflow scheduling in cloud. IEEE Trans Parallel Distrib Syst 27:1344–1357

36.

Durillo JJ, Prodan R, Barbosa JG (2015) Pareto tradeoff scheduling of workflows on federated commercial clouds. Simul Model Pract Theory 58:95–111 Special Issue on TECHNIQUES AND APPLICATIONS FOR SUSTAINABLE ULTRASCALE COMPUTING SYSTEMS

37.

Zhou X, Zhang G, Sun J, Zhou J, Wei T, Hu S (2019) Minimizing cost and makespan for workflow scheduling in cloud using fuzzy dominance sort based heft. Future Gener Comput Syst 93:278–289

38.

Auger A, Bader J, Brockhoff D, Zitzler E (2012) Hypervolume-based multiobjective optimization: theoretical foundations and practical implications. Theor Comput Sci 425:75–103 Theoretical Foundations of Evolutionary ComputationMathSciNetMATH

39.

Jiang S, Zhang J, Ong Y, Zhang AN, Tan PS (2015) A simple and fast hypervolume indicator-based multiobjective evolutionary algorithm. IEEE Trans Cybern 45:2202–2213

40.

Schutze O, Hernandez VAS, Trautmann H, Rudolph G (2016) The hypervolume based directed search method for multi-objective optimization problems. J Heuristics 22:273–300

41.

Wong CSY, Al-Dujaili A, Sundaram S (2016) Hypervolume-based direct for multi-objective optimisation. In: Proceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion, GECCO ’16 Companion. ACM, New York, pp 1201–1208

42.

Yuan Y, Xu H, Wang B, Yao X (2016) A new dominance relation-based evolutionary algorithm for many-objective optimization. IEEE Trans Evol Comput 20:16–37

43.

Yamagishi K, Gonsalves T, Itoh K (2009) Service cost and utilization rate optimization in service systems. J Integr Des Process Sci 13:1–8

44.

Ebadifard F, Babamir SM (2018) A pso-based task scheduling algorithm improved using a load-balancing technique for the cloud computing environment. Concurr Comput Pract Exp 30:e4368 E4368 CPE-16-0467.R4

45.

Ebadifard F, Babamir SM (2018) A modified black hole-based multi-objective workflow scheduling improved using the priority queues for cloud computing environment. In: 2018 4th International Conference on Web Research (ICWR), pp 162–167

46.

Fatemeh Ebadifard SMB (2018) A multi-objective approach with waspas decision-making for workflow scheduling in cloud environment. Int J Web Res 1:1–10

47.

Rivera-Lopeze R, Canul-Reich J (2018) Differential evolution algorithm in the construction of interpretable classification models. In: Aceves-Fernandez MA (ed) Artificial intelligence. Emerging trends and applications, Chap. 3, 1st edn. IntechOpen

48.

Ausiello G, Crescenzi P, Gambosi G, Kann V, Marchetti-Spaccamela A, Protasi M (2013) Complexity and approximation: combinatorial optimization problems and their approximability properties. Springer, New YorkMATH

49.

Tasgetiren MF, Liang Y-C, Sevkli M, Gencyilmaz G (2007) A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem. Eur J Oper Res 177:1930–1947MATH

50.

Deb K, Jain H (2014) An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: solving problems with box constraints. IEEE Trans Evol Comput 18:577–601

51.

Grodzevich O, Romanko O (2006) Normalization and other topics in multiobjective optimization. In: Proceedings of the FieldsMITACS Industrial Problems Workshop

52.

Kirkpatrick S (1984) Optimization by simulated annealing: quantitative studies. J Stat Phys 34:975–986MathSciNet

53.

Jensen MT (2003) Reducing the run-time complexity of multiobjective EAS: the NSGA-II and other algorithms. IEEE Trans Evol Comput 7:503–515

54.

Ebadifard F, Doostali S, Babamir SM (2018) A firefly-based task scheduling algorithm for the cloud computing environment: formal verification and simulation analyses. In: 9th International Symposium on Telecommunications, IST 2018, Tehran, Iran, December 17–19, pp 664–669

55.

Bharathi S, Chervenak A, Deelman E, Mehta G, Su M, Vahi K (2008) Characterization of scientific workflows. In: 2008 Third Workshop on Workflows in Support of Large-Scale Science, pp 1–10

56.

Singh V, Gupta I, Jana PK (2019) An energy efficient algorithm for workflow scheduling in IAAS cloud. J Grid Comput

57.

Durillo JJ, Nebro AJ (2011) jMetal: a java framework for multi-objective optimization. Adv Eng Softw 42:760–771

58.

Okabe T, Jin Y, Sendhoff B (2003) A critical survey of performance indices for multi-objective optimisation. In: The 2003 Congress on Evolutionary Computation, 2003. CEC ’03, vol 2, pp 878–885

59.

Zitzler E, Thiele L (1999) Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Trans Evol Comput 3:257–271

60.

Zitzler E, Knowles J, Thiele L (2008) Quality assessment of Pareto set approximations. Springer, Berlin, pp 373–404

61.

Auger A, Bader J, Brockhoff D, Zitzler E (2009) Theory of the hypervolume indicator: optimal \(\mu \)-distributions and the choice of the reference point. In: Proceedings of the Tenth ACM SIGEVO Workshop on Foundations of Genetic Algorithms, FOGA ’09. ACM, New York, pp 87–102

62.

Ishibuchi H, Hitotsuyanagi Y, Tsukamoto N, Nojima Y (2010) Many-objective test problems to visually examine the behavior of multiobjective evolution in a decision space. In: Proceedings of the 11th International Conference on Parallel Problem Solving from Nature: Part II, PPSN’10. Springer, Berlin, pp 91–100

63.

Zou X, Chen Y, Liu M, Kang L (2008) A new evolutionary algorithm for solving many-objective optimization problems. IEEE Trans Syst Man Cybern Part B (Cybern) 38:1402–1412

64.

Bader J, Zitzler E (2011) Hype: an algorithm for fast hypervolume-based many-objective optimization. Evol Comput 19:45–76

65.

Saaty TL (2008) Decision making with the analytic hierarchy process. Int J Serv Sci 1:83–98

66.

Saaty T (2008) Decision making with the analytic hierarchy process. Int J Serv Sci 1:83–98

Titel: Scheduling scientific workflows on virtual machines using a Pareto and hypervolume based black hole optimization algorithm
verfasst von: Fatemeh Ebadifard
Seyed Morteza Babamir
Publikationsdatum: 06.02.2020
Verlag: Springer US
Erschienen in: The Journal of Supercomputing / Ausgabe 10/2020
Print ISSN: 0920-8542
Elektronische ISSN: 1573-0484
DOI: https://doi.org/10.1007/s11227-020-03183-4

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Weitere Artikel der Ausgabe 10/2020

An efficient continuous range query processing scheme in mobile P2P networks

δ-Transitive closures and triangle consistency checking: a new way to evaluate graph pattern queries in large graph databases

Predator–prey approach in modeling users’ data packets forwarding

Elastic edge cloud resource management based on horizontal and vertical scaling

Relevance maximization for high-recall retrieval problem: finding all needles in a haystack

Adapting the TopLeaders algorithm for dynamic social networks