A Multi-Objective Memetic Algorithm for Workflow Scheduling in Clouds

Feng Yao

doi:10.1109/TETCI.2024.3462856

A Multi-Objective Memetic Algorithm for Workflow Scheduling in Clouds

2024-01-01

1

PRE

AI

DOI：10.1109/TETCI.2024.3462856

原文链接

原文求助

摘要

En 中文

Simultaneously optimizing monetary cost and makespan of workflow execution is substantial to enhance the competitiveness of cloud services, but it still imposes challenges. Heuristics-based algorithms are often problem-dependent and well-suitable for special cases, but the complexity of workflow structures seriously challenges their generalization. Metaheuristics-based algorithms pose good generalization, but the elasticity and heterogeneity of cloud resources seriously impact their search efficiency. Inspired by previous works, we tailor a memetic workflow scheduling algorithm (KDMA for short) that embeds a heuristic local search operator into the multi-objective metaheuristic algorithm to combine their strengths and complement each other's shortcomings. Specifically, the proposed local search operator searches for a set of solutions with good convergence and diversity by accumulating tasks one by one. This operator is good at gathering workflow tasks into a limited range of candidate resources, thereby guiding the metaheuristic algorithm to focus on exploring potential solution regions. Moreover, KDMA includes an adaptive strategy to determine the number of solutions reproduced by the problem-special local search operator based on its past overall contribution. We compare KDMA to five representative algorithms over 25 real-world workflow instances to corroborate its superior all-around performance by performing the best on 21 workflow instances. Meanwhile, we conduct an ablation analysis to verify the performance contributions of two proposed mechanisms.

Keyword:

Memetic computation

workflow scheduling

cloud computing

multi-objective

local search

A Multi-Objective Memetic Algorithm for Workflow Scheduling in Clouds

摘要

期刊

机构

引用论文