Line search method for solving a non-preemptive strictly periodic scheduling problem

We study a non‐preemptive strictly periodic scheduling problem. This problem arises for example in the avionic field where a set of $N$ periodic tasks (measure of a sensor, data presentation, etc.) has to be scheduled on $P$ processors distributed on the plane. In this article, we consider an existing heuristic 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. This iterative process continues until an equilibrium is reached. We present a new method to compute the best response which significantly improves the previously proposed heuristic, and compares favorably with MILP solutions.