基于并行分层的工作流调度优化算法

来源：计算机集成制造系统杂志2014年第5期北京时间：

作者：谭文安,路广振,孙勇

单位：1.南京航空航天大学计算机科学与技术学院2.上海第二工业大学计算机与信息学院

摘要：针对给定截止时间约束下用有向无环图描述的工作流时间费用优化问题,逆向分层算法未考虑工作流中各个任务在实际执行过程中的并行性而带来相对较多的时间碎片,提出一种基于并行分层的工作流调度算法——并发级别工作流调度算法。该算法将工作流在实际执行过程中的某个任务和其他一个(或具有依赖关系的相邻多个）并行执行的任务尽量划分到同一层,并根据各层的并行度分配冗余时间,对每层中存在具有依赖关系的多个相邻任务采用Markov决策过程算法进行时间费用优化。对平衡结构和非平衡结构的有向无环图所描述的工作流进行大量模拟实验,对比最小临界路径算法、逆向分层算法和期限顶级算法,实验结果表明所提算法具有较显著的优势。

关键词：并行分层,工作流调度,有向无环图,启发式,优化算法

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