基于路径QoS加权分解的工作流调度算法

作     者：徐战 王劲林 吴刚 李俊 刘磊 

作者机构：中国科学技术大学自动化系合肥230027 中国科学院声学研究所国家网络新媒体工程技术研究中心北京100190 

出 版 物：《系统仿真学报》 (Journal of System Simulation)

年 卷 期：2012年第24卷第5期

页      面：1035-1040页

核心收录：

学科分类：08[工学] 0802[工学-机械工程] 0825[工学-航空宇航科学与技术] 0701[理学-数学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：863国家高技术研究发展计划(2008AA01A317) 

主　　题：QoS约束 有向无环图 加权分解 工作流调度 

摘      要：采用有向无环图DAG(Directed Acyclic Graph)描述的工作流在QoS约束下的调度问题是一类典型的NP难问题。分析了DAG工作流调度问题的调度目标,提出了一种基于路径QoS加权分解的工作流调度算法,通过将工作流的全局QoS约束分解为单个任务的局部QoS约束,将整个工作流的全局优化问题转化为单个任务的局部优化问题,降低了问题的复杂度。在对整个DAG工作流的QoS约束进行分解时,算法对工作流的每条路径的QoS约束进行分解,并以任务可选能力服务间的单位QoS增益之和作为权值,将单条路径的QoS约束分解到组成路径的每个任务。仿真结果表明,与其他基于QoS分解的DTL、DBL等算法相比,该算法具有更高的调度效率,能够找到更好的调度方案。