A list scheduling algorithm for heterogeneous systems based onrna critical node cost table and pessimistic cost table

摘要

This paper presents a novel list‐based scheduling algorithm called Improved Predict Earliest FinishrnTime for static task scheduling in a heterogeneous computing environment. The algorithm calculatesrnthe task priority with a pessimistic cost table, implements the feature prediction with a criticalrnnode cost table, and assigns the best processor for the node that has at least 1 immediaternsuccessor as the critical node, thereby effectively reducing the schedule makespan withoutrnincreasing the algorithm time complexity. Experiments regarding aspects of randomly generatedrngraphs and real‐world application graphs are performed, and comparisons are made based onrnthe scheduling length ratio, robustness, and frequency of the best result. The results demonstraternthat the Improved Predict Earliest Finish Time algorithm outperforms the Predict Earliest FinishrnTime and Heterogeneous Earliest Finish Time algorithms in terms of the schedule length ratio, frequencyrnof the best result, and robustness while maintaining the same time complexity.