×

Time optimization for workflow scheduling based on the combination of task attributes. (English) Zbl 1474.90158

Summary: 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.

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI