东南大学学报（英文版）2020，Vol.36Issue(4)：399-406,8.DOI:10.3969/j.issn.1003-7985.2020.04.005
基于任务属性组合的工作流调度时间优化算法
Time optimization for workflow scheduling based on the combination of task attributes
摘要
Abstract
In order to reduce the scheduling makespan of a workflow,three list scheduling algorithms,namely,level and out-degree earliest-finish-time(LOEFT),level heterogeneous selection value(LHSV),and heterogeneous priority earliest-finish-time(HPEFT)are proposed.The main idea hidden behind these algorithms is to adopt task depth,combined with task out-degree for the accurate analysis of task prioritization and precise processor allocation to achieve time optimization.Each algorithm is divided into three stages:task levelization,task prioritization,and processor allocation.In task levelization,the workflow is divided into several independent task sets on the basis of task depth.In task prioritization,the heterogeneous priority ranking value(HPRV)of the task is calculated using task out-degree,and a non-increasing ranking queue is generated on the basis of HPRV.In processor allocation,the sorted tasks are assigned one by one to the processor to minimize makespan and complete the task-processor mapping.Simulation experiments through practical applications and stochastic workflows confirm that the three algorithms can effectively shorten the workflow makespan,and the LOEFT algorithm performs the best,and it can be concluded that task depth combined with out-degree is an effective means of reducing completion time.关键词
有向无环图/工作流调度/任务深度/任务出度/列表启发式Key words
directed acyclic graph/workflow scheduling/task depth/task out-degree/list heuristic分类
信息技术与安全科学引用本文复制引用
鲁睿其,朱晨妍,蔡海林,周嘉伟,蒋军强..基于任务属性组合的工作流调度时间优化算法[J].东南大学学报（英文版）,2020,36(4):399-406,8.基金项目
Foundation items:The Natural Science Foundation of Hunan Province(No.2018JJ2153),the Scientific Research Fund of Hunan Provincial Education Department(No.18B356),the Foundation of the Research Center of Hunan Emergency Communication Engineering Technology(No.2018TP2022),the Innovation Foundation for Postgraduate of the Hunan Institute of Science and Technology(No.YCX2018A06). （No.2018JJ2153）
