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

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

针对科学工作流的为多目标调度问题,将成本、时间和数据传输量作为基本优化目标,提出基于有向无环图(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.