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 scheduling constrained-deadline tasks (i.e. d(τ) ≤ p(τ)) with a static-priority policy one possibly needs machines, which are a factor f > 1 faster than it is needed for the EDF policy. Baruah & Burns [BB08] sandwiched this factor between 1.5 and 2. We pinpoint this value to f = 1/Ω ≈ 1.76 by characterizing the properties of task systems, which attain this value. Here, Ω ≈ 0.56 is a well known constant from complex calculus, defined as real root of x · ex = 1. We further consider a multiprocessor setting, where a given set of tasks has to be assigned to machines, such that each partition is RM-schedulable and the number of occupied processors is minimized. For the popular case that the tasks are equipped with implicit-deadlines, i.e. d(τ) = p(τ), we develop new algorithms as well as intractability results: We state an asymptotic PTAS under resource augmentation. This is achieved by two concepts: First we derive that using a merging and clustering procedure, the instance can be modified, such that the utilization of tasks is lowerbounded by a constant, without excluding near-optimal solutions. Secondly, we introduce a relaxed notion of feasibility, which yields a drastic reduction of complexity and admits to compute solutions via dynamic programming. We introduce a simple First-Fit-like heuristic and obtain that this algorithm behaves nearly optimal on average, by proving that the expected waste is upperbounded by O(n3/4(log n)3/8), if the instance of n tasks is generated randomly. Here, we assume that the utilization values c(τ)/p(τ) of the tasks are drawn uniformly at random from [0, 1]. We state a new approximation algorithm with a running time of O(n3), which can be sketched as follows: Create a graph with the tasks being the nodes and insert edges, if both incident tasks can be scheduled together on a processor. Then define suitable vertex costs and compute a min-cost matching, where the costs are the sum of edge costs plus the vertex costs of not covered nodes. From such a matching solution we can then extract a feasible multiprocessor schedule. The approximation ratio of this algorithm can be proven to tend to 3/2, improving over the previously best known ratio of 7/4 [BLOS95]. We consider a column-based linear programming relaxation for this multiprocessor scheduling problem and derive that the asymptotic integrality gap is located between 4/3 ≈ 1.33 and 1 + ln(2) ≈ 1.69. We disprove the existence of an asymptotic FPTAS, which yields that the problem is strictly harder to approximate than its special case of Bin Packing.