基于任务属性组合的工作流调度时间优化算法

• 作者: 鲁睿其 朱晨妍 蔡海林 周嘉伟 蒋军强
• 来源期刊: 东南大学学报（英文版）
• 学科: 工学
• 关键词: 有向无环图 工作流调度 任务深度 任务出度 列表启发式
• 年，卷（期）: 2020,（4）
• 页码范围: 399-406
• 页数: 8页
• 分类号: TP393
• 语种: 英文
• DOI: 10.3969/j.issn.1003-7985.2020.04.005

摘要

为了缩短工作流调度完工时间,提出3种列表调度算法:分级和出度最早完成时间算法(LOEFT)、分级异构选择值算法(LHSV)和异构优先最早完成时间算法(HPEFT).主要思想是利用任务深度,融合任务出度来准确分析任务优先级,精确分配处理器,实现时间优化.算法均分为3个阶段:任务分级、任务排序和处理器分配.任务分级阶段,依据任务深度将工作流划分为若干独立的任务集;任务排序阶段,利用任务出度计算出任务的异构优先排序值(HPRV),并据其降序生成任务队列;处理器分配阶段,将排序排列任务逐一分配至使其完工时间最小的处理器,完成任务-处理器的映射.通过实际应用和随机工作流仿真,证实3种算法可以有效地缩短工作流的完工时间,且LOEFT表现最好.任务深度结合出度是缩短工作流调度完工时间的有效手段.