List schedules for cyclic scheduling Original Research Article

This paper adresses the definition and properties of list scheduling in the context of scheduling a cyclic set of n non-preemptive and non-reentrant-dependent tasks on m identical processors when the reduced precedence graph is assumed to be strongly connected. It is first shown that the average cycle time of an arbitrary list schedule is at most (2 − 1m) times the absolute minimum average cycle time. K-periodic list schedules are then shown to be the list schedules associated with special priority mappings called K-periodic linear orders. Moreover, given a list that offers the performance ratio p in the non-cyclic case and whose structure is quasi K-periodic in the cyclic case, it is shown that each of its corresponding K-periodic linear orders provides a list schedule with the same guarantee. Since the well-known Coffman-Grahamʹs list is shown to be quasi K-periodic, its performance may be transferred to UET cyclic problems.