Liu, Yu; Xiang, Dongyang; Zheng, Chundi Scheduling and optimizing algorithm for parallel tasks in heterogeneous distributed computing systems. (Chinese. English summary) Zbl 1363.68033 Syst. Eng. Electron. 38, No. 2, 332-338 (2016). Summary: 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) are carefully analyzed. Further, an improved algorithm with time complexity \(O(M\times N^3)\) 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 respectively. Hence, the proposed algorithm is sure to enhance the coefficient of the utilization for the whole system resources. MSC: 68M20 Performance evaluation, queueing, and scheduling in the context of computer systems 68M14 Distributed systems 68R10 Graph theory (including graph drawing) in computer science Keywords:distributed computing systems; directed acyclic graph; task schedule; longest dynamic critical path PDFBibTeX XMLCite \textit{Y. Liu} et al., Syst. Eng. Electron. 38, No. 2, 332--338 (2016; Zbl 1363.68033) Full Text: DOI