Optimal algorithms for scheduling large-scale divisible load on heterogeneous systems in non-blocking mode of communication

This paper considers scheduling large-scale divisible load on heterogeneous single-level tree networks to minimize the whole processing time. A more realistic and general model, i.e., both processors and links may have different speeds and arbitrary start-up costs, and with non-blocking mode of communication, is introduced. Under such environment, results are obtained including: (1) closed-form expressions both for the processing time and the fraction of load for each processor are derived; (2) the influence of start-up costs on the optimal processing time is analyzed; and (3) for bounded number of processors with large-scale workload, optimal sequence and algorithms for distributing divisible load are proposed Numerical examples are presented to illustrate the analysis.