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 ea...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.展开更多
基金The Natural Science Foundation of Hunan Province(No.2018JJ2153)the Scientific Research Fund of Hunan Provincial Education Department(No.18B356)+1 种基金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).
文摘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.
