基于二维编码两阶段协同进化遗传算法的云工作流调度优化  

Two stage coevolutionary genetic algorithm with two dimensional coding for cloud workflow scheduling

作　　者：单晓杭[1] 章衡 谢毅 SHAN Xiaohang;ZHANG Heng;XIE Yi(Key Laboratory of Special Purpose Equipment and Advanced Processing Technology,Ministry of Education,Zhejiang University of Technology,Hangzhou 310032,China;School of Management Engineering and E-Business,Zhejiang Gongshang University,Hangzhou 310018,China;Contemporary Business and Trade Research Center,Zhejiang Gongshang University,Hangzhou 310018,China)

机构地区：[1]浙江工业大学特种装备制造与先进加工技术教育部/浙江省重点实验室,浙江杭州310032 [2]浙江工商大学管理工程与电子商务学院,浙江杭州310018 [3]浙江工商大学现代商贸研究中心,浙江杭州310018

出　　处：《计算机集成制造系统》2023年第2期568-580,共13页Computer Integrated Manufacturing Systems

基　　金：国家社会科学基金资助项目(17BGL237)。

摘　　要：针对当前启发式算法依赖于特定问题,元启发式方法存在搜索空间不完备或在完备空间上搜索效率不高,以及传统一维编码存在冗余空间等问题,提出一种基于二维编码两阶段协同进化遗传算法(TDTSGA)的云工作流调度优化方法。在TDTSGA中采用一种新的二维个体编码方法,设计了基于二维层次排序和拓扑排序的交叉变异方法,同时采用了两阶段协同进化策略。通过在各种工作流应用案例上进行广泛实验,验证了TDTSGA的优越性。The heuristic method is problem-dependent and fits only a particular of problems while the meta heuristic method has the problems of incomplete search space or low search efficiency in the complete space,and redundant space in traditional one-dimensional coding.To fill the gaps,a Two-stage coevolutionary Genetic Algorithm with Two Dimensional coding(TDTSGA)was proposed for cloud workflow scheduling.In this algorithm,a new two-dimensional individual coding method was used,the crossover and mutation methods based on two-dimensional hierarchical sorting and topological sorting were designed,and a two-stage coevolution strategy was employed.Extensive experiments were conducted on various workflow applications,and the result demonstrated the performance of TDTSGA was better than that of existing classical approachs.

关 键 词：工作流 云计算 调度优化 遗传算法 协同进化 

分 类 号：TP391[自动化与计算机技术—计算机应用技术] TP311[自动化与计算机技术—计算机科学与技术]