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

Workflow Scheduling Algorithm Based on Weighted Decomposition of Paths' QoS

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

The QoS-constrained scheduling problem for workflow described by Directed Acyclic Graph（DAG） is a typical NP-hard problem.The goal of this scheduling problem was analyzed and a novel workflow scheduling algorithm based on weighted decomposition of paths＇ QoS was proposed.By dividing the global QoS constraint of the whole workflow into local QoS constraints of single tasks,the algorithm transformed the global optimization problem into a series of local optimization problems and reduced the complexity of the problem.In the process of dividing the global QoS constraint of the whole workflow,the algorithm divided the QoS constraints for each path and then divided each path＇s QoS constraint into single tasks＇ QoS constraints by using the sums of unit QoS gain between tasks＇ optional services as weights.As the simulation result shows,this new algorithm has better efficiency and can find a better solution compared to other algorithms based on decomposition of global QoS constraint such as DTL and DBL.