A study of the cyclic scheduling problem on parallel processors

The authors address the problem of scheduling a set of generic tasks to be perfromed infinitely often without preemption on finitely many parallel processors. These tasks are subject to a set of uniform constraints, modeled by a uniform graph G. The problem is to find a periodic schedule that minimizes the cycle time. Although the problem is NP-hard, the authors show that the special case where G is a circuit can be solved in polynomial time. They then study the structure of the set of solutions in the general case and determine several dominant subsets of schedules by analyzing the periodic structure of the allocation function and the induced uniform constraints on the schedule. In particular, the authors prove the dominance of circular schedules, in which the occurrences of any task are successively perfromed by all the processors. Finally, they propose a greedy heuristic that provides a good circular schedule.