Divisible Load Scheduling with Improved Asymptotic Optimality

Divisible load model allows scheduling algorithms that give nearly optimal makespan with practical computational complexity. Beaumont et al. have shown that their algorithm produces a schedule whose makespan is within 1 + O(1/root T) times larger than the optimal solution when the total amount of tasks T scales up and the other conditions are fixed. We have proposed an extension of their algorithm for multiple masters with heterogeneous performance of processors but limited to uniform network performance. This paper analyzes the asymptotic performance of our algorithm, and shows that the asymptotic performance of our algorithm is either 1 + O(1/root T), 1 + O(log T/T) or 1 + O(1/T), depending on the problem. For the latter two cases, our algorithm asymptotically outperforms the algorithm by Beaumont et al.