On the computational complexity of periodic scheduling

In periodic scheduling jobs arrive regularly and have to be executed on one or several machines or processors. An enormous amount of literature has been published on this topic, e.g. the founding work of Liu & Layland [LL73] is among the top cited computer science papers, according to Citeseer database. The majority of these papers is mainly concerned about practical applications and several important theoretical questions remained unsolved. Let S be a set of periodic tasks, where each task τ ∈ S releases a job of running time c(τ) and relative deadline d(τ) at each integer multiple of its period p(τ). In the single-processor scheduling one considers rules like Earliest-Deadline-First (EDF) or Rate-monotonic (RM) scheduling, that determine the order, in which the jobs have to be processed. The principal question here is to predict, whether such a schedule is feasible, i.e. whether all jobs are finished before their individual deadlines. It was well-known that to validate the feasibility of an EDF-schedule, one has to evaluate the condition But the complexity status of this test remained unknown, despite of many heuristic approaches in the literature. We prove that testing this condition is coNP-hard even in special cases, answering an open question of Baruah & Pruhs [BP09]. For a static-priority schedule of implicit-deadline tasks, i.e. d(τ) = p(τ), it is known that the jobs of a task τ will meet their deadlines if and only if there exists a fix-point r ∈ [0,p(τ)] of the equation where the sum ranges over all tasks with priority higher than τ . We settle the complexity status of this problem by proving its NP-hardness, even if one asks for modest approximations. Both results are achieved by bridging the more practically oriented area of Real-time scheduling and the field of algorithmic number theory. In fact, the intractability follows by a chain of reductions to simultaneous Diophantine approximation (SDA), which is a classical problem in the geometry of numbers and deals with finding a small denominator Q ∈ {1,…,N}, that yields a good approximation to a given vector of rational numbers α ∈ Qn, i.e. maxi=1,…,n |Qαi - ⎡Qαi⎦| ≤ ε. We strengthen existing hardness results for SDA such that they admit intractability results also for a directed version, where the goal is to find a Q ∈ {1,…,N} with maxi=1,…,n(⎡Qαi⎤ - Qαi) ≤ ε. We show that this problem remains NP-hard if one asks for an approximation that may exceed the bound N by a factor of nO(1/loglogn) and the error bound ε by 2nO(1). As an application we are able to answer an open question of Conforti et al. [CSW08] negatively by obtaining NP-hardness for the problem of optimizing a linear function over a mixing set {(s,y ∈ R≥0 × Zn | s + aiyi ≥ bi ∀i = 1,…, n}. Furthermore we obtain that, regardless to the used ‖ · ‖p-norm, the problem of finding a shortest positive vector in a lattice is not approximable within a factor of nO(1/loglogn), unless NP = P. For sch