Scoring and Dynamic Hierarchy-Based NSGA-II for Multiobjective Workflow Scheduling in the Cloud

Huifang Li, Binyang Wang, Yan Yuan, Meng Chu Zhou, Yushun Fan, Yuanqing Xia

Research output: Contribution to journalArticlepeer-review

Abstract

Cloud computing becomes a promising technology to reduce computation cost by providing users with elastic resources and application-deploying environments as a pay-per-use model. More scientific workflow applications have been moved or are being migrated to the cloud. Scheduling workflows turns to the main bottleneck for increasing resource utilization and quality of service (QoS) for users. This work formulates workflow scheduling as multiobjective optimization problems and proposes a Scoring and Dynamic Hierarchy-based NSGA-II (Nondominated Sorting Genetic Algorithm II), called SDHN for short, to minimize both makespan and cost of workflow execution. First, a scoring criterion is developed to calculate the total score for each individual during population updating, which is used as a quantitative index to evaluate the dominance degree of individuals among the whole population. Hence, SDHN can distinguish individuals within the same dominance level and target its search toward the directions of elite solutions as their different dominance degrees and accordingly improve search efficiency. Second, a population-based dynamic hierarchical structure (HS) and its evolutionary rules are presented to update HS by comparing each child with all parental individuals from bottom to up until finding a proper dominant level. Since traversing all HS levels is not needed in most cases, the number of individual comparisons is reduced and SDHN's updating efficiency is greatly improved, especially for large-scale and complex applications. Third, to guarantee its converging to the near-optimal solutions, adaptive adjustment strategies (AASs) are designed to prevent the search from falling into local optima or diverging by checking the number of individuals at the highest HS level and then modifying the relevant genetic operations to guide the evolutionary process to approach the global Pareto Front. Extensive experiments are conducted to verify SDHN, and the results show that it outperforms the existing algorithms in the quality and diversity of resulting solutions as well as convergence time.

Original languageEnglish (US)
JournalIEEE Transactions on Automation Science and Engineering
DOIs
StateAccepted/In press - 2021

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Electrical and Electronic Engineering

Keywords

  • Cloud computing
  • Cloud computing
  • Dynamic scheduling
  • Heuristic algorithms
  • metaheuristics
  • multiobjective optimization
  • Optimization
  • Quality of service
  • Statistics
  • Task analysis
  • workflow scheduling.

Fingerprint

Dive into the research topics of 'Scoring and Dynamic Hierarchy-Based NSGA-II for Multiobjective Workflow Scheduling in the Cloud'. Together they form a unique fingerprint.

Cite this