基于路径QoS加权分解的工作流调度算法
Workflow Scheduling Algorithm Based on Weighted Decomposition of Paths' QoS作者机构:中国科学技术大学自动化系合肥230027 中国科学院声学研究所国家网络新媒体工程技术研究中心北京100190
出 版 物:《系统仿真学报》 (Journal of System Simulation)
年 卷 期:2012年第24卷第5期
页 面:1035-1040页
核心收录:
学科分类:08[工学] 0802[工学-机械工程] 0825[工学-航空宇航科学与技术] 0701[理学-数学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术(可授工学、理学学位)]
基 金:863国家高技术研究发展计划(2008AA01A317)
摘 要:采用有向无环图DAG(Directed Acyclic Graph)描述的工作流在QoS约束下的调度问题是一类典型的NP难问题。分析了DAG工作流调度问题的调度目标,提出了一种基于路径QoS加权分解的工作流调度算法,通过将工作流的全局QoS约束分解为单个任务的局部QoS约束,将整个工作流的全局优化问题转化为单个任务的局部优化问题,降低了问题的复杂度。在对整个DAG工作流的QoS约束进行分解时,算法对工作流的每条路径的QoS约束进行分解,并以任务可选能力服务间的单位QoS增益之和作为权值,将单条路径的QoS约束分解到组成路径的每个任务。仿真结果表明,与其他基于QoS分解的DTL、DBL等算法相比,该算法具有更高的调度效率,能够找到更好的调度方案。