MOELS: Multiobjective Evolutionary List Scheduling for Cloud Workflows

Cloud computing has nowadays become a dominant technology to reduce the computation cost by elastically providing resources to users on a pay-per-use basis. More and more scientific and business applications represented by workflows have been moved or are in active transition to cloud platforms. Therefore, efficient cloud workflow scheduling methods are in high demand. This paper investigates how to simultaneously optimize makespan and economical cost for workflow scheduling in clouds and proposes a multiobjective evolutionary list scheduling (MOELS) algorithm to address it. It embeds the classic list scheduling into a powerful multiobjective evolutionary algorithm (MOEA): a genome is represented by a scheduling sequence and a preference weight and is interpreted to a scheduling solution via a specifically designed list scheduling heuristic, and the genomes in the population are evolved through tailored genetic operators. The simulation experiments with the real-world data show that MOELS outperforms some state-of-the-art methods as it can always achieve a higher hypervolume (HV) value. Note to Practitioners - This paper describes a novel method called MOELS for minimizing both costs and makespan when deploying a workflow into a cloud datacenter. MOELS seamlessly combines a list scheduling heuristic and an evolutionary algorithm to have complementary advantages. It is compared with two state-of-the-art algorithms MOHEFT (multiobjective heterogeneous earliest finish time) and EMS-C (evolutionary multiobjective scheduling for cloud) in the simulation experiments. The results show that the average hypervolume value from MOELS is 3.42% higher than that of MOHEFT, and 2.27% higher than that of EMS-C. The runtime that MOELS requires rises moderately as a workflow size increases.