A Two-stage Multi-population Genetic Algorithm with Heuristics for Workflow Scheduling in Heterogeneous Distributed Computing Environments

Abstract

Workflow scheduling in Heterogeneous Distributed Computing Environments (HDCEs) is a NP-hard problem. Although a number of scheduling approaches have been proposed for workflow scheduling in HDCEs, there is still a room and need for improvement. To fill the gaps, this study formulates workflow scheduling problem in HDCEs as a complete, solvable and extensible integer programming mathematical model with precedence and resource constraints that provides a theoretical foundation for developing workflow scheduling strategy. Then, this study develops a novel two-stage multi-population genetic algorithm with heuristics for workflow scheduling. In particular, two-stage multi-population coevolution strategy is employed with designed novel methods for population initialization, genetic operation, individual decoding and improvement. To estimate the validity, extensive experiments are designed and conducted on various scenarios based on real and random workflow applications. The results have shown the practical viability of the proposed algorithm outperforming conventional approaches.