QoS 约束下的分层工作流调度算法

摘要 将工作流抽象为有向无环图(Directed Acyclic Graph，DAG)的建模方法已经取得广泛应用，时间约束下执行费用优化问题仍是其一个难解的问题.通过分析有向无环图中的并行结构，对模型进行有效的层次划分是一种有效的解决方案.针对如何合理划分分层后模型中的冗余时间问题，提出了一种基于结构分析的分层工作流调度算法(Structure Analysis Based Level,SAL).该算法针对分层后各层次中的并行执行过程，提出一种更加合理的冗余时间划分方法，通过模拟工作流DAG建模实验，对比分析SAL算法与最小关键路径法(Minimum Critical Path,MCP)、逆向分层算法(Deadline Bottom Level,DBL)效果，实验结果表明SAL算法的有效性