HEFT-IPF: A Three-Phase Scheduling Algorithm for Heterogeneous Multi-Cloud Environment

Abstract

Workflow scheduling (WFS) in a heterogeneous multi-cloud (HMC) environment is a critical problem, aiming to minimize overall completion time (i.e., makespan) and maximize resource utilization. Numerous heuristic and metaheuristic algorithms have been developed to address the problem of WFS. One well-known and benchmark algorithm is called heterogeneous earliest finish time (HEFT). This algorithm allocates the precedence-constrained workflow tasks to the clouds by calculating the task prioritization, followed by the cloud selection. However, it does not consider the task characterization phases, namely initialization, processing, and finalization (IPF), which leads to poor makespan and resource utilization. Therefore, this paper introduces a WFS algorithm called HEFT-IPF to enhance the HEFT algorithm’s performance by considering task characterization. HEFT-IPF algorithm overlaps the execution of tasks by executing their initialization and finalization phases while strictly preserving their precedence constraints. The HEFTIPF algorithm performance is compared with that of the HEFT algorithm by considering various scientific workflows, namely epigenomics, laser interferometer gravitational-wave observatory (LIGO), cybershake, sRNA identification protocol using highthroughput technology (SIPHT), and montage. Two performance measures, makespan and resource utilization, are used to compare with HEFT and HEFT-IPF algorithms. Simulation results show that the HEFT-IPF algorithm outperforms the HEFT algorithm, achieving a 28.36% average reduction in makespan and a 23.33% average improvement in resource utilization.