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

摘要：

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

关键词：工作流调度、有向无环图、结构分析、启发式算法

所属期刊栏目：36

分类号：TP393(计算技术、计算机技术)

资助基金：国家自然科学基金项目61272036

在线出版日期：2016-09-18（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：1444-1448