Affiliations: School of Computer Science and Engineering, South China University of Technology, Guangzhou 510006, Guangdong, China
Correspondence:
[*]
Corresponding author: Naqin Zhou, School of Computer Science and Engineering, South China University of Technology, Guangzhou 510006, Guangdong, China. E-mail: [email protected].
Abstract: A novel task scheduling algorithm called Merge Tasks and Predict Earliest Finish Time (MTPEFT) has been proposed for static task scheduling in a heterogeneous computing environment. The algorithm merges tasks satisfying constraints and assigns the best processor for the node that has at least one immediate successor as the critical node, thereby effectively reducing the schedule length without increasing the algorithm time complexity. Experiments regarding aspects of randomly generated graphs and real-world application graphs are performed, and comparisons are made based on the scheduling length ratio, robustness and frequency of the best result. The results show that the MTPEFT algorithm outperforms the PEFT, CPOP and HEFT algorithms in terms of the schedule length ratio, frequency of the best result and robustness while maintaining the same time complexity.
