Scheduling periodic tasks in a hard real-time environment

We consider a 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 a_i + k· p_i, k ∈ N₀ and a collision occurs if two jobs are simultaneously active on the same machine. We shed some light on the complexity and approximability landscape of this problem. 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.