Scheduling Periodic Tasks in a Hard Real-Time Environment

We give a rigorous account on the complexity landscape of an im-portant real-time scheduling problem that occurs in the design of software-based aircraft control. The goal is to distribute tasks τi = (ci, pi) on a minimum number of identical machines and to compute offsets ai for the tasks such that no collision occurs. A task τi releases a job of running time ci at each time ai + k · pi, k ∈ N0 and a collision occurs if two jobs are simultaneously active on the same ma-chine. Our main results are as follows: (i) We show that the minimization prob-lem cannot be approximated within a factor of n1−ε for any ε> 0. (ii) If the periods are harmonic (for each i, j one has pi | p j or p j | pi), then there exists a 2-approximation for the minimization problem and this result is tight, even asymptotically. (iii) We provide asymptotic approximation schemes in the har-monic case if the number of different periods is constant