Scheduling divisible loads in bus networks with arbitrary processor release times

AbstractThe problem of processing divisible loads in a distributed bus network architecture with arbitrary processor available/release times is considered. The objective is to optimally distribute the load among the processors in the system in such a way that the processing time of the entire load is a minimum. Different cases of release time distributions are considered. First, we present the analysis for the case in which the processors are assumed to be available from the time instant at which the processing load arrives at the system. In this case, a multi-installment load distribution strategy is adopted. We develop basic recursive equations for the case when the processors in the system are heterogeneous and extend the analysis to the case of homogeneous processors. Then the case of arbitrary processor release times is considered. Closed-form solutions for the processing time when the processor release times are identical are derived. For a general case of arbitrary processor release times, a heuristic algorithm is presented. All the cases are demonstrated through several illustrative examples