A dynamic multipopulation genetic algorithm for multiobjective workflow scheduling based on the longest common sequence

A cloud workflow scheduling problem is extremely challenging for its large scale and the elasticity and heterogeneity of cloud resources. In this paper, we model a cloud workflow scheduling as a multi-objective optimization problem in which makespan and energy consumption need to be simultaneously optimized. To address the problem, we propose a dynamic multiple population genetic algorithm (DMGA), in which the population is divided into three sub-populations (i.e., superior, ordinary, and inferior sub-populations). Accordingly, three sets of genetic operators are introduced. Concretely, the traditional genetic operators are selected by the ordinary sub-population. On the contrary, two types of the longest common subsequence (LCS) respectively based on superior individuals and inferior individuals are utilized to design two specific genetic operators, which are adopted by the superior sub-population and the inferior sub-population, respectively. For the superior sub-population, some superior gene blocks can be saved by the new proposed genetic operators, which is beneficial for speeding up the convergence. For the inferior sub-population, some inferior gene blocks can be destroyed based on the new genetic operators, which is favorable for helping the inferior individuals to jump out of local optima. Moreover, the dynamic multiple population framework enable an individual to perform diverse search behaviors in different generations aiming to satisfy distinct requirements of different fitness landscapes. We conducted experiments with 2 heuristic algorithms, 5 algorithms designed specifically for workflow scheduling, and 3 popular swarm intelligence algorithms. In the comparison of the five measures, DMGA outperformed the other algorithms on more than 50% of the tested dataset. The results indicate that DMGA outperforms other state-of-the-art peer algorithms on different scheduling problems, especially on large scale problems. Moreover, positive effectiveness of the new proposed strategies is also verified by a set of experiments.

Automated summary

In this paper, a cloud workflow scheduling problem is modeled as a multi-objective optimization problem and a dynamic multiple population genetic algorithm (DMGA) is proposed to address the problem. The experimental results show that DMGA outperforms other algorithms on multiple tested datasets, especially on large-scale problems. Moreover, the effectiveness of the new proposed strategies is also verified by a set of experiments.