Abstract:

Strategies of parallel task scheduling have direct influences on the executing time of an application, but the perfect schedule which makes finishing time of the application shortest is a nonpolynomial completion time problem.By creating the mathematical models of heterogeneous distributed computing systems (DCS) and static task scheduling, the main procedure and deficiencies of the exist longest dynamic critical path algorithm (LDCP) is carefully analyzed.Further, an improved algorithm with time complexity O(M×N3) to decrease idle time blocks of processors based on the node information flow quantity is proposed.Experiments show that the proposed algorithm outperforms the traditional algorithm and the sorted nodes in leveled directed acyclic graph division algorithm (SNLDD) in the schedule length, speedup and computation efficiency.The schedule length of the improved algorithm is shorter than those of the LDCP and SNLDD algorithms by 19.03% and 8.02%，respectively.The average speedup gained by the improved algorithm is greater than those of the LDCP and SNLDD algorithms by 18.42% and 7.96%，respectively.The computation efficiency of the improved algorithm can get the amount of 10.17% and 3.72% increase than those of the LDCP and SNLDD algorithms.Hence, the proposed algorithm is sure to enhance the coefficient of the utilization for the whole system resources.