A Two-stage Multi-population Genetic Algorithm with Heuristics for Workflow Scheduling in Heterogeneous Distributed Computing Environments
A Two-stage Multi-population Genetic Algorithm with Heuristics for Workflow Scheduling in Heterogeneous Distributed Computing Environments
复制标题
DOI：
10.1109/tcc.2021.3137881
复制
发表时间：
2023-04-01
影响因子：
6.5
通讯作者：
Chien, Chen-Fu
中科院分区：
文献类型：
--
作者：
Xie, Yi;Gui, Feng-Xian;Chien, Chen-Fu
异构分布式计算环境中的工作流调度是一个NP难问题。虽然已经提出了一些调度方法在HDCE的工作流调度，仍然有一个空间和需要改进。为了填补这一空白，本研究将HDCE中的工作流调度问题描述为一个完整的、可解的、可扩展的具有优先级和资源约束的整数规划数学模型，为工作流调度策略的制定提供了理论基础。然后，本文提出了一种新的两阶段多种群遗传算法的工作流调度。特别地，采用两阶段多种群协同进化策略，设计了新的种群初始化、遗传操作、个体解码和改进方法。为了评估有效性，广泛的实验设计和进行各种场景的基础上真实的和随机的工作流应用程序。结果表明，该算法优于传统的方法的实际可行性。
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.