On Graham's bound for cyclic scheduling

This paper addresses the performance of list scheduling a cyclic set of N non-preemptive dependent generic tasks on m identical processors. The reduced precedence graph is assumed to be strongly connected but the number of simultaneously active instances of a generic task is not restricted to be at most one. Some properties on arbitrary schedules are first given. Then, we restrict to regular schedules for which it is shown that the number of ready or active tasks at any instant is at least the minimum height H* of a directed circuit of the reduced precedence graph. The average cycle time of any regular list schedule is then shown to be at most (2 - (min{H*, m}/m)) times the absolute minimum average cycle time. This result, which is similar well-known (2 - (1/m)) Graham's bound applying for non-cyclic scheduling, shows to what extent regular list schedules take the: parallelism of the cyclic task system into account. (C) 2000 Elsevier Science B.V. All rights reserved.