Scheduling periodic tasks in a hard real-time environment

We give a rigorous account on the complexity landscape of an important real-time scheduling problem that occurs in the design of software-based aircraft control. The goal is to distribute tasks τ _i=(c _i ,p _i ) on a minimum number of identical machines and to compute offsets a _i for the tasks such that no collision occurs. A task τ _i releases a job of running time c _i at each time and a collision occurs if two jobs are simultaneously active on the same machine. Our main results are as follows: (i) We show that the minimization problem cannot be approximated within a factor of n ^1-ε for any ε>0. (ii) If the periods are harmonic (for each i,j one has p _i |p _j or p _j |p _i ), 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 harmonic case if the number of different periods is constant.