A New Method for Multi-installment Divisible-Load Scheduling

Minimizing the make-span of the entire divisible load is the primary objective of multi-installment scheduling in heterogeneous parallel and distributed systems. This is a significantly difficult problem to address because we have to find the optimal number m of installments, optimal number n of processors taking part in computation, and optimal load partition A = [α_ij]_n×m with each element represents the load fraction assigned to each processor in different installment. Therefore, this problem involves 2+n m variables. In this paper, we first find the function expression of the optimal load partition A with respect to the number m of installments and the number n of processors participating in computation, i.e., A = f (n, m), thereby reducing the dimension of the problem down to 2. Then we propose a new heuristic method for finding the optimal numbers of installments and processors. Finally, experimental results show that the make span of the entire divisible load obtained by the proposed method is smaller than those by the existing multi-installment scheduling methods, which implies the effectiveness of the proposed method.