Solution of a cyclic scheduling problem with resource constraints using independent iterations

A cyclic scheduling problem is defined by a finite set of generic tasks with resource or precedence constraints to be executed an infinity of times. Although these problems have important applications, few were up to now studied as combinatorial optimization problems. The paper considers a set of dependent generic tasks and dedicated classes of processors. The objective is the maximization of the frequency of the taks occurrences. The paper proposes a characterization of the feasible solutions and an efficient polynomial algorithm, based on a topological sort on the precedence graph, that provides an optimal schedule of the tasks.