Divisible load scheduling on single-level tree networks with buffer constraints

Scheduling a divisible load on a heterogeneous single-level tree network wi th processors having finite-size buffers is addressed. We first present the closed-form solutions for the case when the available buffer size at each site is assumed to be infinite Then we analyze the case when these buffer s izes are of finite size. For the first lime in the domain of DLT (divisible load theory) literature, the problem of scheduling with finite-size buffer s is addressed, For this case, we present a novel algorithm, referred to as incremental balancing strategy (IBS), to obtain an optimal load distributi on. Algorithm IBS adopts a strategy to feed the divisible load in a step-by -step incremental balancing fashion by taking advantage of the available cl osed-form solutions of the optimal scheduling for the case without buffer s ize constraints. Based on the rigorous mathematical analysis, a number of i nteresting and useful properties exhibited by the algorithm are proven. We present a very useful discussion on the implications of this problem on the effect of sequencing discussed in the literature [1]. Also, the impact of Rule A [2], a rule that obtains a reduced optimal network to achieve optima l processing time by eliminating a redundant set of processor-link pairs, i s also discussed. Numerical examples are presented to ease understanding.