Résolution d’un problème d’ordonnancement cyclique à itérations indépendantes et constraintes de ressources. (Solution of a cyclic scheduling problem with independent iterations and resource constraints). (French) Zbl 0726.90032

Summary: A cyclic scheduling problem is defined by a finite set of generic tasks with resource or precedence constraints to be executed infinitely often. Although these problems have important applications, few were up to now studied as combinatorial optimization problems.
We consider a set of dependent generic tasks and dedicated classes of processors. The objective is the maximization of the frequency of the task occurrences. We propose a characterization of the feasible solutions and an efficient polynomial algorithm, based on a topological search on the precedence graph, that provides an optimal schedule of the tasks.


90B35 Deterministic scheduling theory in operations research
90C60 Abstract computational complexity for mathematical programming problems
Full Text: DOI EuDML