Propagation mechanism for a non-preemptive strictly periodic scheduling problem

We study a non-preemptive strictly periodic scheduling prob- lem. This problem, introduced in [6, 4], arises for example in the avionic field where a set of N periodic tasks (measure of a sensor, etc.) has to be scheduled on P processors distributed on the plane. In the related fi eld of cyclic scheduling, some notable success has been recently achieved through the use of speci c constraint propagation. In this article, we consider a heuristic, first proposed by Al Sheikh et al. 2012, which is based on the notion of equilibrium. Following a game theory analogy, each task tries successively to optimize its own schedule and therefore to produce the best response, given the other schedules. We present a propagation mechanism for non-overlapping constraints which signi cantly improves this heuristic