A Priority-Based Level Heuristic Approach for Scheduling DAG Applications with Uncertainties

In a typical distributed computing system, as the availability of resources and the precise execution time of different calculations are usually difficult to predict, how to effectively schedule complex calculations composed of interdependent tasks has become a challenge. The priority-based (PB) scheduling scheme, which is designed to maximize the parallelism of ready tasks, has shown better performance than other existing algorithms. However, the PB algorithm has the problem of excessive computing overhead and long running time in some cases. To address this issue, this paper proposes the priority-based level (PBL) algorithm. Experiments results show that the PBL , in comparison with their counterparts, manages to significantly reduce the algorithm running overhead while maintaining the scheduling results.