Time Optimization for Workflow Scheduling by Incorporating Level Strategy into Out-Degree.

Efficient workflow scheduling plays a critical role in achieving high performance in heterogeneous distributed computing systems. Given its key importance, workflow scheduling has been extensively studied, and various algorithms have been proposed in the literature mainly for systems with homogeneous or heterogeneous processors. Most of the algorithms leverage the average computation cost to prioritize tasks, and few focus on the combination of the level and out-degree of tasks, which both have a considerable impact on scheduling. A new list scheduling algorithm called level and out-degree earliest finish time (LOEFT) is proposed in this paper to address the problem of static workflow scheduling in a heterogeneous computing environment to reduce the workflow execution time. This algorithm has three major phases: task leveling, task prioritization and processor selection. In the task leveling phase, tasks are categorized into different groups based on depth value to ensure data transmission completeness. In the task prioritizing phase, the upward rank value is combined with the out-degree of every task to calculate the heterogeneous priority rank value on different processors and leverage the value to sort all tasks. In the processor selection phase, the selected task is assigned to the processor, which minimizes the former's earliest finish time. The experimental simulation of randomly generated DAG and real-world application workflows proves that the LOEFT algorithm can significantly reduce the workflow execution time. [ABSTRACT FROM AUTHOR]