Divisible load scheduling on arbitrary distributed networks via virtual routing approach

Abstract

In this paper, we propose a distributed algorithm for scheduling divisible loads originating from single site on arbitrary networks. We first propose a mathematical model and formulate the scheduling problem as an optimization problem with an objective to minimize the processing time of the loads. A number of theoretical results on the solution of the optimization problem are derived. On the basis of these results, we propose our algorithm using the concept of virtual routing. The proposed algorithm has three attractive features - distributed working style, simple structure, in terms of implementation ease, and offers generalized approach for handling divisible load scheduling for any network topology. This is the first time in the divisible load scheduling literature that a distributed strategy is attempted.