Mutation-driven and population grouping PRO algorithm for scheduling budget-constrained workflows in the cloud

Huifang Li*, Bing Chen, Jingwei Huang, Julio Ruben Cañizares Abreu, Senchun Chai, Yuanqing Xia

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

Benefiting from cloud computing’s elasticity, scalability, and pay-per-use model, more and more scientific applications are deployed in or migrated to the cloud. Workflow scheduling still faces many challenges due to the growing scales of workflows and the diversified user QoS requirements. In this work, we propose a Mutation-driven and population Grouping Poor and Rich Optimization algorithm (MG-PRO) for scheduling workflows in the cloud to minimize makespan while satisfying the budget constraints. Specifically, we first adopt the middle-class sub-population into the original Poor and Rich Optimization algorithm (PRO), and develop the update strategies for rich and middle-class sub-populations to increase the randomness and search diversity. Secondly, the update mechanism for rich individuals is enriched, and the middle-class sub-population is guided by elite rich individuals, which enhances the information exchange and sharing among sub-populations. Finally, an evolution-aware mutation strategy is designed, where the mutation probability is adjusted adaptively as the dynamic monitoring of the population update process, and the two-point and triangular crossover-based mutations are used alternately to intervene the evolution trajectory according to the degree of objective optimization, resulting in a better balance between exploration and exploration. Extensive experiments are conducted on well-known scientific workflows with different types and scales through WorkflowSim. The experimental results show that, in most cases, MG-PRO outperforms existing algorithms in terms of constraint satisfiability, solution quality and stability. It can generate near-optimal solutions with the different budget constraints satisfied in a relatively short time, for example, the makespan resulting from MG-PRO is at most 59.95% shorter than other meta-heuristic algorithms, and at least 7.33% shorter than all its peers.

Original languageEnglish
Pages (from-to)1137-1158
Number of pages22
JournalCluster Computing
Volume27
Issue number1
DOIs
Publication statusPublished - Feb 2024

Keywords

  • Cloud computing
  • Meta-heuristics
  • Poor and Rich Optimization algorithm
  • Workflow scheduling

Fingerprint

Dive into the research topics of 'Mutation-driven and population grouping PRO algorithm for scheduling budget-constrained workflows in the cloud'. Together they form a unique fingerprint.

Cite this