DAG多级相关节点聚类的多目标工作流调度  

Multi-objective Workflow Scheduling of Multi-level Clustering of DAG Related Nodes

作　　者：向志华 XIANG Zhi-hua(Department of Information and Technology,Guangdong Polytechnic College,Zhaoqing 526100,China)

机构地区：[1]广东理工学院信息技术学院,广东肇庆526100

出　　处：《控制工程》2020年第9期1595-1602,共8页Control Engineering of China

基　　金：2019年广东省普通高校特色创新类项目(2019KTSCX249);广东理工学院质量工程项目(ZXKCJS20202)。

摘　　要：针对科学工作流的为多目标调度问题,将成本、时间和数据传输量作为基本优化目标,提出基于有向无环图(Directed Acyclic Graph,DAG)模型的多级相关节点聚类(Multi-level correlated Nodes Clustering,MNC)方法。首先,针对在连续级别上直接连接的Peer-to-Peer群集组对等任务,将多个依赖节点打包到不同层次的DAG工作流中,并将具有父节点和子节点关系的两个节点分成同组。然后,针对MNC科学工作流调度模型,采用遗传算法进行模型的染色体数据表示、调度译码算法以及极值解的求解方法设计等,建立了科学工作流调度的多目标优化模型;最后,通过在随机生成工作流数据上模拟实验显示,所提算法在网络运行成本、计算时间和数据传输量等指标上的性能优势,验证了算法有效性。In order to solve the multi-objective scheduling problem of running scientific workflow,it takes cost,time and data transmission as the basic optimization objectives,and proposes the multi-level correlation node clustering(MNC)which is based on directed acyclic graph(DAG)model.Firstly,for peer-to-peer cluster group tasks that are directly connected at a continuous level,it packs multiple dependent nodes into DAG workflows at different levels,and divides two nodes with parent and child relationship into the same group.Secondly,based on the MNC scientific workflow scheduling model,it uses the genetic algorithm to represent the model’s chromosome data,calls the decoding algorithm,designs the extreme value solution,and establishes a multi-objective optimization model for scientific workflow scheduling;Finally,through the simulation experiment on randomly generated workflow data,the performance advantages of the proposed algorithm on network operation cost,calculation time and data transmission amount are shown,and the effectiveness of the algorithm is verified.

关 键 词：DAG图 多级相关 节点聚类 多目标 工作流 调度优化 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] TP391[自动化与计算机技术—控制科学与工程]