Alberto Marchetti-Spaccamela
email: alberto@dis.uniroma1.it

Cyriel Rutten
email: cyrielrutten@gmail.com

Suzanne Van Der Ster
email: suzanne.vander.ster@vu.nl

Andreas Wiese
email: awiese@mpi-inf.mpg.de

Assigning sporadic tasks to unrelated machines

Keywords: Scheduling, Sporadic task systems, Unrelated machines, Demand bound function, Integer linear programming, Rounding

come

Introduction

The sporadic task model is a model of recurrent processes in hard real-time systems that has received great attention in the last years; see for example [START_REF] Baker | Schedulability analysis of multiprocessor sporadic task systems[END_REF][START_REF] Baruah | Open problems in real-time scheduling[END_REF], and references therein. A sporadic task τ = (c τ , d τ , t τ ) is characterized by a worst-case execution time c τ , a relative deadline d τ , and a minimum interarrival separation t τ . Such a sporadic task generates a potentially infinite sequence of jobs with successive job arrivals separated by at least t τ time units, it has an execution requirement less than or equal to c τ and a deadline that occurs d τ time units after its arrival time.

A sporadic task system is comprised of several such sporadic tasks. Since the actual interarrival times can vary, there are infinitely many job sequences that can be generated. A sporadic task system is said to be feasible upon a specified platform if it is possible to schedule the system on the platform such that all jobs of all tasks will meet their deadlines, under all permissible combinations of job arrival sequences by the different tasks comprising the system.

The feasibility analysis of sporadic task systems on single processors has been extensively studied [START_REF] Baker | Schedulability analysis of multiprocessor sporadic task systems[END_REF]. It is known that the Earliest Deadline First (EDF) algorithm, that schedules at any time the job with the earliest absolute deadline, is optimal in the sense that for any sequence of jobs it produces a valid schedule, whenever a valid schedule exists [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard real-time environment[END_REF]. However, it is co-NP-hard to decide whether a task system is feasible on a single machine [START_REF] Eisenbrand | EDF-schedulability of synchronous periodic task systems is coNP-hard[END_REF].

On multiprocessor systems, there are two main paradigms for scheduling: global and partitioned scheduling. In the former, all tasks can use all machines, and jobs can even be migrated from one machine to another. In the partitioned scheduling approach each task has to be assigned to one of the machines such that all its jobs have to be executed on this specific machine. Since the process of partitioning tasks among processors reduces a multiprocessor scheduling problem to a series of single-processor problems, the optimality of EDF for preemptive single-processor scheduling makes EDF a reasonable algorithm to use as the run-time scheduling algorithm on each machine.

In recent years, hardware design has seen a highly visible trend towards heterogeneous processors. In particular, modern hardware architectures often contain specialized processors for certain tasks (e.g., graphical processors, floating-point units). To model the actual behavior of the different types of processors when making scheduling decisions, in this paper we assume that the given machines are unrelated; i.e., we assume that the processing time of each task depends on the machine where it is executed, including the possibility that some tasks cannot be executed on some machines at all. For attacking our problem, we will be using an integer linear program (ILP). It is NP-hard to solve ILPs optimally [START_REF] Karp | Reducibility among combinatorial problems[END_REF], but the corresponding LP relaxation (i.e., where the integrality constraints on the variables are relaxed) can be solved in polynomial time. Hence, a common approach is to solve the relaxation and transform the obtained fractional solution into an integer solution, at the cost of worsening the objective value or violating the constraints in a controlled way. As part of our techniques, we present a new method to round a very general class of linear programs for assignment problems, without worsening the objective value and with carefully bounding the (then unavoidable) errors on the constraints due to the rounding.

Related work

As mentioned above, deciding whether a task system is feasible on a single machine is a co-NP-hard problem [START_REF] Eisenbrand | EDF-schedulability of synchronous periodic task systems is coNP-hard[END_REF]. This motivates approximate feasibility tests that run efficiently but introduce an error in the decision process, controlled by an accuracy parameter α (the speedup). If an α-approximation test returns "feasible", then the task set is guaranteed to be feasible on an α-speed processor(s); if the test returns "infeasible", the task set is guaranteed to be infeasible on a unit-speed processor(s). For the case of a single processor, an FPTAS feasibility test for EDF has been proposed [START_REF] Chakraborty | Approximate schedulability analysis[END_REF] (i.e., for any > 0, there exists a (1 + )-approximation test with running time polynomial in the number of tasks and in 1/ ).

In the case of m identical processors, assuming the global paradigm, the natural EDF-policy is no longer optimal, but it is known that any feasible collection of jobs on m machines of unit speed is schedulable using EDF on m machines of speed 2-1 m [START_REF] Phillips | Optimal time-critical scheduling via resource augmentation[END_REF]. Also, a corresponding test for task sets is known [START_REF] Baruah | Improved multiprocessor global schedulability analysis[END_REF][START_REF] Bonifaci | A constant-approximate feasibility test for multiprocessor real-time scheduling[END_REF]. Recently, Anand et al. [START_REF] Anand | Meeting deadlines: how much speed suffices?[END_REF] presented an online algorithm needing only a speedup factor of e/(e -1) ≈ 1.58.

In the case of the partitioned paradigm, to the best of our knowledge, the multiplemachines case has only been studied for identical machines. Most of prior research has considered the special case of implicit-deadline systems in which all tasks have their deadlines equal to their period parameters (i.e., d τ = t τ for all τ ). Then, a set of tasks is feasible on one machine if and only if the sum of the utilizations c τ /t τ is at most one and the problem reduces to Makespan Minim ization. In Eisenbrand and Rothvoß [START_REF] Eisenbrand | A PTAS for static priority real-time scheduling with resource augmentation[END_REF] a PTAS was proposed for the case where tasks are scheduled according to fixed priorities using resource augmentation. In that paper also the existence of an FPTAS is ruled out, thus showing that the problem is strongly NP-hard.

If deadlines are not implicit, much less is known. Baruah and Fisher [9] propose an algorithm which can partition any set of tasks that is feasible on m machines such that the assignment is feasible if the machines run 4 -2 m times faster. In Fisher et al. [START_REF] Fisher | The partitioned scheduling of sporadic tasks according to staticpriorities[END_REF] a similar result is given if the tasks are scheduled according to static priorities, rather than with the more powerful EDF policy. Chen and Chakraborty [START_REF] Chen | Resource augmentation bounds for approximate demand bound functions[END_REF] improved upon these results by showing that a deadline-monotonic policy with approximate demand bound functions leads to a feasibility test with speedup factor 3e-1 e -1 m ≈ 2.6322 -1 m in case of constrained deadlines (d τ ≤ t τ for all τ ) and a speedup factor of 3 -1 m for unconstrained deadlines.

As mentioned above, we assume the machines to be unrelated, meaning that the processing times of the tasks can differ on the different machines. To the best of our knowledge the unrelated-machines setting has not been studied for arbitrary-deadline sporadic tasks. For implicit-deadline task systems some results are known, that are discussed below.

However, the setting with unrelated machines is well-studied for assigning jobs to minimize the makespan. Lenstra et al. [START_REF] Lenstra | Approximation algorithms for scheduling unrelated parallel machines[END_REF] give a 2-approximation algorithm for the problem of minimizing the makespan of a set of jobs and prove that it is NP-hard to achieve a performance ratio better than 1.5. Despite a lot of effort, the only improvements in the setting of an arbitrary number of machines are a 1.75-approximation algorithm for the graph balancing case [START_REF] Ebenlendr | Graph balancing: a special case of scheduling unrelated parallel machines[END_REF] and a 33/17 ≈ 1.94-estimation algorithm for the restricted assignment case [START_REF] Svensson | Santa Claus schedules jobs on unrelated machines[END_REF]. A generalization of this problem is the Generalized Assignment Problem (GAP). In this problem, assigning a job j to a machine i incurs a certain (global) cost c i, j . Shmoys and Tardos [START_REF] Shmoys | An approximation algorithm for the generalized assignment problem[END_REF] give a 2-approximation for this problem; to be more precise, they devise an algorithm computing a schedule with makespan 2T and cost at most C, given that a solution with the same cost and a makespan of T exists.

Azar and Epstein [START_REF] Azar | Convex programming for scheduling unrelated machines[END_REF] consider p norms (for finite p > 1, rather than the makespan) for which they improved the previously best result of θ( p) [START_REF] Awerbuch | Load balancing in the L p norm[END_REF] to a 2-approximation and even a √ 2-approximation for the 2 norm. This was improved to a better-than-two result for all p > 1 in [START_REF] Kumar | Approximation algorithms for scheduling on multiple machines[END_REF].

For a constant number of machines, polynomial-time approximation schemes are known [START_REF] Jansen | Improved approximation schemes for scheduling unrelated parallel machines[END_REF][START_REF] Lenstra | Approximation algorithms for scheduling unrelated parallel machines[END_REF]. Rather than focusing on a constant number of machines, one could also consider the case of a constant number of machine types; each machine belongs to one of the types and the processing time of each job depends only on the job and the type of the machine it is assigned to. For the problem of assigning implicit-deadline task systems to unrelated machines of two different types, an approximation algorithm is given in [START_REF] Raravi | Assigning real-time tasks on heterogeneous multiprocessors with two unrelated types of processors[END_REF] based on the first-fit heuristic with a worst-case performance ratio of 2. For the same problem, a PTAS was given later [START_REF] Raravi | A PTAS for assigning sporadic tasks on two-type heterogeneous multiprocessors[END_REF]. In the meantime, a PTAS was given [START_REF] Wiese | Partitioned EDF scheduling on a few types of unrelated multiprocessors[END_REF] for any constant number of machine types. The authors justify their contribution in [START_REF] Raravi | A PTAS for assigning sporadic tasks on two-type heterogeneous multiprocessors[END_REF] by pointing out that their PTAS for two different types has a much lower run-time complexity than the one in [START_REF] Wiese | Partitioned EDF scheduling on a few types of unrelated multiprocessors[END_REF] applied to two machine types.

The NP-hardness of solving arbitrary ILPs inspired the search for algorithms that transform the fractional solution of an LP relaxation into an integer solution. The goal is that such a solution either has a bounded loss on the objective function while satisfying all constraints, or gives a bound on the amount that any constraint is violated. There are many problems than can be well approximated using LP rounding, see e.g., [START_REF] Williamson | The Design of Approximation Algorithms[END_REF] for an introduction.

The LP rounding procedure we will present in Sect. 3 produces an integral solution that maintains an objective value not worse than that of the optimal fractional solution, while guaranteeing a bound on the violation of any constraint in the system. This procedure is based on ideas presented in [START_REF] Karp | Global wire routing in two-dimensional arrays[END_REF], where a solution for an integer linear program (without objective function) is found by rounding the solution to the LP relaxation such that each variable is rounded up or rounded down and each constraint of the program is violated by at most a constant factor (depending on the maximum sum of elements over all columns of the coefficient matrix).

Our contribution To the best of our knowledge, no non-trivial algorithm is known for assigning a set of sporadic tasks to a set of unrelated machines. We first present an algorithm that, given a task system for which a task assignment on m machines exists, finds a task assignment that can be scheduled on m machines that are 8 + 2 √ 6 ≈ 12.9 times as fast.

This result is obtained through a new rounding procedure that is first presented separately in Sect. 3. The procedure is designed for rounding a fractional solution of the LP relaxation of any assignment-type problem where items (e.g., tasks in our case) have to be assigned to resources (e.g., machines) while obeying some knapsacktype constraints. Given that each resource-item combination appears in at most γ constraints, the procedure preserves the constraint that every item is assigned and all other constraints are violated by at most a factor of γ + 1. Further, the cost of this rounded solution is no more than the optimal cost of the LP relaxation. In fact, the wellknown 2-approximation algorithm for the generalized assignment problem by Shmoys and Tardos [START_REF] Shmoys | An approximation algorithm for the generalized assignment problem[END_REF] can be derived as a direct corollary from our rounding procedure. We apply the procedure to a sparse LP formulation which approximately models the task assignment problem on unrelated machines and obtain the mentioned result (after some technical modifications of the LP). Also, we show that no polynomial-time algorithm can compute a task assignment needing a speedup factor of 2for > 0, unless P = N P. Note that this bound is stronger than the best known (3/2 -)-hardness result for the contained problem of minimizing the makespan when scheduling jobs on unrelated machines [START_REF] Lenstra | Approximation algorithms for scheduling unrelated parallel machines[END_REF].

For the case that the number of machines is fixed, we present a polynomial-time algorithm that either finds a feasible task assignment on m machines that are 1 + times as fast, or guarantees that no solution exists on unit-speed processors.

In order to be able to achieve these results, we need deep understanding of the demand bound function (dbf) which yields a necessary and sufficient condition for a task system to be feasible on one machine. In particular, we present two new relaxations for handling this well-studied function. For our result for an arbitrary number of machines, we give a set of sparse linear constraints which approximate the dbf up to a constant factor. Due to the sparsity we are able to design an efficient iterative rounding procedure.

For the case of a constant number of machines, we observe that we cannot exploit the technique of partitioning the task set into "big" and "small" tasks as in the job scheduling problem. A task having a small execution time or small utilization (formally defined in the next section) might still be very tight in the sense that its relative deadline is fairly small. Therefore, even if all large tasks are already assigned, assigning the small tasks is still very tricky, i.e., they cannot be scheduled easily by spreading them over machines which still have some capacity left. An important feature of our dbf relaxation is that the feasibility test of assigning a task with deadline D to a machine having tasks with deadlines <D already assigned to it, requires only limited information of the previously assigned tasks. To be more explicit, the approximate demand bound function for each task only needs to be evaluated at a constant number of points. Afterwards we just approximate the function by the task's utilization. We exploit this feature and other tricks to polynomially bound the running time of a dynamic programming algorithm.

Given is a set M of m parallel unrelated machines and a sporadic task system T , with |T | = n. Each task τ ∈ T is characterized by a set of values ({c i,τ } i∈M , d τ , t τ ), where c i,τ is its execution time on machine i, d τ is its deadline, relative to its arrival time, and t τ denotes the minimum interarrival time between two jobs of τ and is called the period. We assume all parameters to be integer and strictly positive. We study the problem of finding a task assignment T = {T i } i∈M such that ∪ i T i = T . Without loss of generality we can restrict to task assignments with the property that T i ∩ T i = ∅ for any two machines i = i .

A task assignment is feasible if for any machine i, any job arrival sequence of the tasks in T i can be feasibly scheduled on i, allowing jobs to be preempted. Since each task is assigned to exactly one machine, after finding an assignment, EDF will be our scheduling algorithm of choice, by its optimality for single-machine scheduling [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard real-time environment[END_REF].

An α-approximation test for the problem of assigning tasks to unrelated machines is an algorithm that runs in polynomial time and which either guarantees that there is no feasible integral assignment of the tasks to the given machines (running at unit speed), or finds an integral assignment which is feasible if the machines run at speed α.

By u i,τ we denote the utilization of task τ on machine i and we define it as u i,τ = c i,τ /t τ . Given a task assignment T , we define the utilization of each machine i by u i = τ ∈T i u i,τ . Note that in a feasible assignment u i ≤ 1, for all i ∈ M, is a necessary but not sufficient condition for feasibility [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard real-time environment[END_REF].

Clearly, the necessary condition u i ≤ 1 for all i ∈ M implies that if there is a task τ such that u i,τ > 1, this task will never be assigned to machine i. Further, if for any task τ and machine i it holds that c i,τ > d τ , then τ will not be assigned to machine i. If it were assigned to machine i, the first job of τ clearly could not be completed before c i,τ and would miss its deadline at d τ .

Feasibility test The synchronous arrival sequence for task system T is defined to be the collection of job arrivals in which each task in T generates a job at time instant zero, and subsequent jobs arrive as soon as legally permitted (i.e., task τ generates a job at each time-instant k t τ , k = 0, 1, 2, . . .).

It is known [START_REF] Baruah | Preemptively scheduling hard-real-time sporadic tasks on one processor[END_REF] that a set of sporadic tasks T i is EDF-schedulable on machine i if and only if the following conditions are satisfied:

1. the utilization of the task system does not exceed 1, i.e., u i = τ ∈T i u i,τ ≤ 1, 2. all jobs with deadlines [0, lcm τ ∈T i (t τ )] in the synchronous arrival sequence of T i meet their deadlines (where lcm denotes the least common multiple).

This immediately yields an exponential-time test to check whether T i is EDFschedulable; however we recall that the problem is co-NP-hard [START_REF] Eisenbrand | EDF-schedulability of synchronous periodic task systems is coNP-hard[END_REF] and that it is not known whether it can be determined in pseudo-polynomial time.

A necessary and sufficient condition for a task system T to be schedulable is based on the demand bound function. In the case of unrelated machines we have the following condition.

Proposition 1 ([10]) An assignment T = {T i } i∈M is feasible for task system T if and only if for all

i ∈ M dbf T ,i (s) := τ ∈T i :d τ ≤s s + t τ -d τ t τ c i,τ ≤ s ∀s ≥ 0.
We write dbf i instead of dbf T ,i whenever the assignment T is clear from the context. Further, we define dbf i (τ, s) := (s + t τd τ )/t τ c i,τ , i.e., dbf i (τ, s) denotes the contribution of task τ to dbf T ,i (s).

Rounding procedure

In this section we introduce the LP rounding procedure that was designed for ILPs that represent assignment problems. After that, we show that this procedure generalizes the result of Shmoys and Tardos [START_REF] Shmoys | An approximation algorithm for the generalized assignment problem[END_REF] for the Generalized Assignment Problem.

The rounding procedure

Almost any combinatorial optimization problem can be formulated as an integer linear programming (ILP) problem with integral (or binary) decision variables and linear constraints. A feasible or optimal solution to this ILP is then a feasible or optimal solution to the problem originally considered. Unfortunately, solving ILPs in general is NP-hard [START_REF] Karp | Reducibility among combinatorial problems[END_REF]. A common approach is to, instead, solve the corresponding LP relaxation, where the integrality constraints on the decision variables are relaxed. In a second step, one turns this fractional solution into an integral solution without (1) violating the constraints too much, or (2) losing too much in the objective value with respect to the LP optimum.

In this section we present an LP rounding procedure that is specially designed for ILPs that stem from assignment problems. It guarantees that after applying the rounding, the obtained integral solution violates the constraints from the ILP by only a bounded factor (depending on the structure of the LP matrix) and the objective value of the LP optimum is preserved. In Sect. 4 we use this procedure to obtain a constantfactor approximation test for the problem of assigning tasks to unrelated machines. Since the procedure itself is independent of the application we will use it for, we present it here in more general terminology than we will need later. The rounding procedure is quite similar to the procedure presented in [START_REF] Karp | Global wire routing in two-dimensional arrays[END_REF], but in contrast to the latter, ensures that in the resulting integral solution one obtains a feasible integral assignment.

Assume we want to solve the following assignment problem: given is a set of n items and a set of m resources M and a set R ⊆ {1, . . . , m} × {1, . . . , n} containing all combinations (i, j) such that it is allowed to assign item j to resource i. For each combination (i, j) ∈ R we are given a cost c i, j denoting the cost of assigning item j to i. The goal is to assign each item j to a resource i to minimize the total cost, and such that for each resource i a set of knapsack-type constraints is satisfied. Each item appears in at most γ constraints per resource. W.l.o.g. we assume that each itemresource combination appears in exactly γ of these constraints. Formally, we are given the set R and for all (i, j) ∈ R we define decision variable z i, j , which is equal to 1 if item j is assigned to resource i, and 0 otherwise. Let θ := n γ . We are also given non-negative values a i, j and b i for all (i, j) ∈ R and ∈ {1, . . . , θ}, such that for each (i, j) ∈ R, a i, j > 0 for at most γ out of the θ coefficients. We want to solve the following integer linear program (ILP). min

(i, j)∈R c i, j z i, j i:(i, j)∈R z i, j = 1 f o rj = 1, . . . , n; (1a) j:(i, j)∈R a i, j z i, j ≤ b i for i = 1, . . . , m; = 1, . . . , θ; (1b) z i, j ∈ {0, 1} for all (i, j) ∈ R (1c)
We denote by L P 0 the LP relaxation of the above ILP. The contribution of item j in constraint of resource i is expressed by coefficient a i, j . Note that if this is larger than the 'capacity' b i , item j will never be assigned to resource i in an integral solution.

However, for our reasoning in Sect. 4 we need to round LP relaxations of the above type where possibly a i, j > b i . We assume w.l.o.g. that a i, j ≤ 1 for all i, j, (which can be ensured by linear scaling).

Solving the LP relaxation of this problem usually does not give an integral solution and hence items are fractionally assigned to multiple resources. Our rounding procedure turns this solution into an integral solution, such that each capacity constraint is not violated by more than γ times the maximum coefficient on the left-hand side. Further, the cost of this rounded solution will not be more than the optimal cost from the fractional LP solution.

In typical assignment-type problems, the number of constraints where the same resource-item combination appears, is often low. For example, in the linear program that we will use in Sect. 4 for the problem of assigning tasks to unrelated machines, we will have that γ = 2. In an LP relaxation for the problem of scheduling jobs on unrelated machines to minimize the makespan, we even have γ = 1.

Our rounding procedure is iterative and in each iteration h we compute an extremepoint solution z h of a linear program L P h , where, as defined above, L P 0 equals the LP relaxation of the original assignment problem and for h ≥ 0 each L P h+1 is obtained by fixing the value for some variable(s) or removing some constraint(s) of L P h . Whenever during this process constraints have become redundant (e.g., because all their variables have been already fixed) we remove them from the LP.

Given a feasible fractional solution z h , to obtain L P h+1 we first fix all variables which are integral in z h , i.e., those variables are not allowed to be changed anymore in the remainder of the procedure. Let s be the number of variables in L P h and let r a and r b be the number of constraints of types (1a) and (1b), respectively. Let r = r a + r b . To obtain L P h+1 , we either fix and delete one or more variables (in case that s > r ), or delete a constraint while ensuring that in the final solution that constraint will not be violated too much. Later in this section we will explain how to identify these constraints and bound the amount that these constraints can be violated in the final solution. Along the way we ensure that the constraints of type (1a) are always satisfied exactly and that the costs in the objective are not increased.

ALGORITHM 1: Iterative Rounding Procedure

Input: A set of m resources, a set of n items and a set R ⊆ {1, . . . , m} × {1, . . . , n} and for each (i, j) ∈ R and ∈ {1, . . . , θ} values c i, j ≥ 0, b i ≥ 0 and a i, j ≥ 0 and L P 0 , the LP relaxation of (1) loop Solve L P h consisting of s variables and r constraints and find extreme-point solution z h . if s > r then z h has at least one integral entry. fix all integral entries at their value, remove them from the program and update right-hand side coefficients remove all inequalities that have become redundant by fixing the integral values else find a resource i and ∈ {1, . . . , θ} such that max w∈S n j=1 a i, j (w i, jz h i, j ) ≤ γ , where S = {0, 1} s remove the inequality corresponding to the found i and .

end if

The remaining linear program is L P h+1 end loop return Integral solution zi, j for all (i, j) ∈ R such that c z ≤ c z 0 and (5) holds.

Note that if there is some variable z i, j that is fixed at value 1 and removed from the program, for all i ∈ M\{i}, z i , j will be set to 0 and also be removed from the program. The constraint of type (1a) corresponding to this item j is then superfluous and will also be removed. We also update the right-hand side of each constraint where z i, j appears, taking into account that we decided to assign j to i which thus reduces the remaining capacities of i, for each of the up to θ remaining constraints.

The following lemma is the key to show that this algorithm works correctly.

Lemma 1 Let L P h be the linear program that is solved in iteration h of the rounding procedure, having s variables and r constraints. Let z h be an extreme-point solution to this LP. If s > r , then z h has at least one integral entry. If s ≤ r , then there is a resource i and some ∈ {1, . . . , θ} such that max w∈S n j=1 a i, j (w i, jz h i, j ) ≤ γ , where S is the integer solution space for all remaining variables, i.e., S = {0, 1} s . Proof Assume that the subproblem in iteration h (described by L P h ) is defined as Az ≤ b. First assume that s > r . Then the null space of A is non-empty. Let z 0 be a vector in the null space of A. Since z h is an extreme-point solution to L P h it cannot be expressed as the convex combination of two (or more) solutions to L P h (see also e.g., [START_REF] Karloff | Linear Programming[END_REF]). If z h does not have any integral entry then we can find a value δ > 0 such that z h +δ •z 0 and z h -δ •z 0 are both solutions to L P h and, in particular, z h is a convex combination of these two solutions. Therefore, z h must have at least one integral entry. Now assume that s ≤ r . For this case, we show that there always exists a constraint l of type (1b) such that max w∈S {(Aw) l -(Az) l } ≤ γ . We show the statement by contradiction. Assume that the statement is not true; that is, for each constraint l of type (1b) it holds that there exists a vector w ∈ S such that

(Aw) l -(Az) l > γ.
(

) 2
In each previous round, if variables were removed from the program, also constraints that had become redundant, were removed. Therefore, for all variables present in the linear program in this round, the corresponding constraint of type (1a) is also still present in the linear program (and this constraint is not present if all of its variables have been removed from the program). It follows that m i=1 j:z i, j present z i, j = r a .

(

) 3
Define L as the set of constraints of type (1b) present in the current linear program. For any q = (i, j), let L q denote the set of these constraints containing variable z q . Then,

γ (r -r a ) = γ r b (2) < l∈L max w∈S ((Aw) l -(Az) l ) all a l,q ≥0 = l∈L ((A1) l -(Az) l ) = l∈L q a l,q (1 -z q ) = q l∈L q a l,q (1 -z q ) ≤ q γ (1 -z q ) = γ s - q γ z q = γ (s -r a ). ( 4
)
The second inequality follows since each variable z q appears in at most γ constraints of type (1b) and since we assumed that a l,q ≤ 1 for all constraints l ∈ L and all variables q. The chain of inequalities implies that γ (rr a ) < γ (sr a ) ⇒ r < s which is a contradiction to being in the case that s ≤ r . Hence, we conclude that if s ≤ r , there must be a constraint l of type (1b), for which max w∈S {(Aw) l -(Az) l } ≤ γ .

Given an extreme-point solution z h for a linear program L P h , we can find in polynomial time a constraint which can be dropped, assuming that the number of variables is bounded by the number of constraints (i.e., s ≤ r ). For each of the polynomial number of constraints, we try the most "pessimistic" vector w ∈ S = {0, 1} s . This vector w is obtained by taking w i, j = 1 for all (i, j), since a i, j ≥ 0 for all (i, j) and all ∈ {1, . . . , θ}.

Theorem 1 Let m, n, γ ∈ N. Let θ = n γ . Suppose we are given a set R ⊆ {1, . . . , m} × {1, . . . , n} of pairs (i, j) that we define a decision variable z i, j for. For each (i, j) ∈ R and ∈ {1, . . . , θ} we are given values ci, j ≥ 0, b i ≥ 0, and a i, j ≥ 0, such that for each (i, j) ∈ R, a i, j > 0 for at most γ coefficients. Assume that the resulting linear program L P 0 , as given in [START_REF] Albers | An event stream driven approximation for the analysis of real-time systems[END_REF], is feasible and denote by z * its optimal solution. Then there is a polynomial-time algorithm computing an integral solution z with c z ≤ c z * which satisfies i:(i, j)∈R zi, j = 1 f or j = 1, . . . , n; (5a)

j:(i, j)∈R a i, j zi, j ≤ b i + γ max j a i, j f or i = 1, . . . , m; = 1, . . . , θ; (5b) zi, j ∈ {0, 1} f or all (i, j) ∈ R. ( 5c
)
Proof Before applying the rounding procedure, we scale each linear constraint such that max j a i, j = 1 for each combination of a resource i and a value ∈ {1, . . . , θ}. We apply our iterative rounding procedure, where L P 0 equals the LP relaxation of (1) and for each h ≥ 0, L P h+1 is obtained from L P h by either fixing the value of some variable(s) or removing some constraint(s). Suppose we computed an extremepoint solution z h for L P h . Then if s > r , according to Lemma 1, z h must have at least one integral value. Those variables that have an integer value in z h are fixed at these values and the variables are removed from the program. If a variable z i, j is fixed at value 1, then for all i ∈ M\{i}, the variables z i , j will be fixed at value 0 and be removed and the constraint of type (1a) corresponding to j will also be removed. Also the right-hand side of each constraint of type (1b) where z i, j appears will be updated, considering that assigning item j to resource i used a i, j of the capacity in constraint . Note that the optimal objective value of the resulting linear program L P h+1 is not larger than the optimal objective in L P h since z h induces a solution to L P h+1 with the same objective value as z h gives in L P h .

If s ≤ r , we know by Lemma 1 that a constraint l exists, such that

max w∈S {(Aw) l -(Az) l } ≤ γ (6)
and it can be found in polynomial time. To this end, we check for each resource i whether j (1z i, j ) ≤ γ . This is sufficient since all a i, j ≥ 0 and the maximum value any variable z i, j can take is 1. (In fact, it is even true that if the latter condition is satisfied all constraints of a given resource can be removed.) Since the removed constraint satisfies (6), we know that whatever value the variables in this constraint will get in the final solution, the additive error in the right-hand side of this constraint will be at most γ , assuming that all a i, j ≤ 1. Note that removing constraints cannot increase the costs of the final solution. At the end we scale all constraints back to their original values. Thus, the resulting solution satisfies (5b). Finally, we know that in each iteration either of the two cases of Lemma 1 applies and thus after a polynomial number of iterations either all constraints or all variables are removed and we are done.

Generalized assignment problem

In fact, a direct consequence of Theorem 1 is a 2-approximation algorithm for the Generalized Assignment Problem (GAP), as it was first presented by Shmoys and Tardos [START_REF] Shmoys | An approximation algorithm for the generalized assignment problem[END_REF]. Given are a set of n jobs and a set of m unrelated machines. For each combination of a job j and a machine i we are given the running time p i, j of j on i and a cost c i, j . For given values C ≥ 0 and T ≥ 0, the goal is to find an assignment of the jobs to the machines with total cost at most C and such that each machine has a makespan of at most T . In Shmoys and Tardos [START_REF] Shmoys | An approximation algorithm for the generalized assignment problem[END_REF], a polynomial-time algorithm is presented that finds a solution with cost at most C and makespan at most 2T , given that a solution of cost at most C and makespan at most T exists. The canonical LP formulation for GAP is the following:

min m i=1 n j=1 c i, j x i, j m i=1 x i, j = 1 f o rj = 1, . . . , n; (7a) n j=1 p i, j x i, j ≤ T for i = 1, . . . , m; (7b) x i, j ≥ 0 for all (i, j) s.t. p i, j ≤ T (7c)
If the optimal objective value is strictly greater than C then there is no solution obeying C and T . Otherwise, Theorem 1 directly gives a polynomial-time procedure that finds an integral solution with cost at most C and a makespan of at most 2T , using that we have exactly one constraint per machine, i.e., γ = 1. In fact, for this specific LP it is known that the iterative rounding procedure described above gives the mentioned result; see e.g., [START_REF] Lau | Iterative Methods in Combinatorial Optimization[END_REF].

Arbitrary number of machines

In this section we present an α = 8 + 2 √ 6 ≈ 12.9-approximation test for assigning tasks to unrelated machines and we show that the problem is NP-hard to approximate to within a ratio of 2for any > 0.

Constant-factor approximation test

We will formulate the problem of assigning tasks to unrelated machines as a linear program, such that the tasks on each machine can be feasibly scheduled using the EDF-scheduler. First, we derive a set of linear inequalities which are -necessary, meaning that they are fulfilled by any feasible assignment, -approximately sufficient, meaning that any integral assignment which (approximately) fulfills the constraints is feasible if the speed of the machine is increased by some constant factor, and -sparse, meaning that each variable occurs in only two capacity constraints.

For each pair of a machine i and a task τ , such that u i,τ ≤ 1 and c i,τ ≤ d τ , we introduce a variable y i,τ modeling to assign τ to machine i. Note that for pairs (i, τ ) that do not satisfy these conditions we do not need a variable y i,τ since it will be infeasible to assign such a τ to machine i. The first constraints are utilization bounds on all tasks assigned to the same machine i. Formally, we demand that

τ ∈T u i,τ y i,τ ≤ 1 ∀i ∈ M. ( 8
)
Secondly, we require that for all tasks with their deadline in the interval

(2 k-1 , 2 k ],
the sum of their execution time is at most 2 k . Formally, we require

τ ∈T :d τ ∈(2 k-1 ,2 k ] c i,τ y i,τ ≤ 2 k ∀i ∈ M, ∀k ∈ N. (9)
We call these conditions the relaxed dbf constraints. It is clear that these constraints have to be fulfilled by any feasible task assignment. Since they are linear, they can be used in an LP relaxation for the problem. Their sparsity gives the potential to use the rounding procedure from Sect. 3 to obtain an integral solution that violates the relaxed dbf constraints only by a constant factor. The following lemma shows that-even when violated up to a constant factor-the presented constraints are approximately sufficient.

Lemma 2 Let T be an assignment for the task system T such that, for all machines i, τ ∈T i u i,τ ≤ β and τ ∈T i :

d τ ∈(2 k-1 ,2 k ] c i,τ ≤ β 2 k .
Then dbf T ,i (s) ≤ 6βs for all s ≥ 0 and T is a feasible task assignment under a speedup factor of 6β.

Proof Let π ∈ N and s := 2 π . Consider an assignment T of the tasks in T to the machines in M. For any machine i ∈ M, we bound dbf i (s) := dbf T ,i (s) by

dbf i (s) = τ ∈T i : d τ ≤s s + t τ -d τ t τ c i,τ ≤ τ ∈T i : d τ ≤s s c i,τ t τ + c i,τ ≤ s τ ∈T i c i,τ t τ + τ ∈T i : d τ ≤s c i,τ = s τ ∈T i u i,τ + log 2 (s) k=0 τ ∈T i : d τ ∈(2 k-1 ,2 k ] c i,τ ≤ βs + π k=0 β 2 k ≤ βs + β 2 π +1 = βs + 2βs = 3βs.
Hence, for any machine i and for arbitrary s we get that dbf i (s) ≤ dbf i (2 log 2 s ) ≤ 3β 2 log 2 s ≤ 6βs. This implies that T is a feasible assignment for scheduling the tasks in T to the set of unrelated machines whenever the machines receive a speedup factor of 6β.

Let ρ > 1. We define the function r (x) := ρ log ρ x . Assume we are given an instance of our problem. Let d max := max τ ∈T d τ and define the set D ρ := {ρ 0 , ρ 1 , . . . , r (d max )}. We now formulate the following linear program, denoted by Ass-LP, where the deadlines are rounded up to the nearest power of ρ rather than to the nearest power of 2 (as implicitly done in the relaxed dbf constraints given above).

i∈M y i,τ = 1 ∀τ ∈ T, ( 10a
) τ ∈T u i,τ y i,τ ≤ 1 ∀i ∈ M, ( 10b
) τ ∈T : r (d τ )=D c i,τ y i,τ ≤ D ∀D ∈ D ρ , ∀i ∈ M, ( 10c
)
y i,τ ≥ 0 ∀τ ∈ T, ∀i ∈ M : u i,τ ≤ 1 ∧ c i,τ ≤ d τ . ( 10d
)
If Ass-LP is infeasible, then there can be no feasible (integral) task assignment. Now assume that it is feasible and we have computed a feasible solution y * . For each machine i and deadline D ∈ D ρ we extract a value

U i,D := τ ∈T : r (d τ )=D c i,τ y * i,τ .
Based on these values, we define a strengthened variation of Ass-LP, denoted by SAss-LP in the sequel. We obtain the latter by replacing the constraints (10c) by the following set of constraints:

τ ∈T : r (d τ )=D c i,τ y i,τ ≤ U i,D ∀D ∈ D ρ , ∀i ∈ M. ( 10c
)
Clearly if y * is a feasible solution for Ass-LP, it is also a feasible solution for SAss-LP and if SAss-LP is infeasible, then no feasible task assignment exists. We now round y * to an integral solution which approximately satisfies SAss-LP by using the rounding procedure presented in Sect. 3. Note that each machine-task combination appears in one constraint of type (10b) and in one of type (10c ). Hence, when applying Theorem 1, we have that γ = 2. Therefore, applying the rounding procedure from Theorem 1 gives a task assignment ŷ that satisfies constraints (10a) and (10d) and the following two inequalities

τ ∈T u i,τ ŷi,τ ≤ 3 ∀i ∈ M, ( 11
)
τ ∈T : r (d τ )=D c i,τ ŷi,τ ≤ U i,D + 2D ∀D ∈ D ρ , ∀i ∈ M. ( 12
)
Observe that U i,D ≤ D for all D ∈ D ρ and all machines i, and hence the vector ŷ violates the relaxed dbf -constraints by at most a factor of β = 3. Hence, Lemma 2 directly implies that the task assignment given by the vector ŷ is feasible with a speedup of 18 if we choose ρ = 2. However, using the definition of U i,D and a more careful calculation, we can bound the needed speedup even further.

Lemma 3 If we choose ρ = 1 + √ 6/3, the task assignment implied by the variables ŷ is feasible if the machines run at speed 8 + 2 √ 6.

Proof Let T denote the assignment implied by the integral variables ŷ. Correspondingly, T i denotes the set of tasks that are assigned to machine i, that is T i = {τ ∈ T : ŷi,τ = 1}. We show that for the task assignment implied by ŷ, dbf T ,i (s) ≤ (8+2 √ 6)s for all s and any machine i, if we choose ρ = 1 + √ 6/3:

dbf T ,i (s) = τ ∈T i : d τ ≤s s + t τ -d τ t τ c i,τ ≤ τ ∈T i : r (d τ )≤r (s) s c i,τ t τ + c i,τ ≤ s τ ∈T c i,τ t τ ŷi,τ + τ ∈T : r (d τ )≤r (s) c i,τ ŷi,τ = s τ ∈T u i,τ ŷi,τ + log ρ (r (s)) k=0 τ ∈T : r (d τ )=ρ k c i,τ ŷi,τ (11)
&( 12)

≤ 3s + log ρ (r (s)) k=0 U i,ρ k + 2ρ k ≤ 3s + ρ log ρ (r (s)) + 2 log ρ (r (s)) k=0 ρ k = 3s + r (s) + 2 ρ log ρ (r (s))+1 -1 ρ -1 ≤ 3s + r (s) + 2ρ r (s) ρ -1 ≤ s(3 + ρ + 2 ρ 2 ρ -1 ) = 8 + 2 √ 6 s.
The last inequality follows since r (s) ≤ ρs, whereas the last equality follows by optimization of the value of ρ, i.e., we set ρ := 1 + √ 6/3.

Theorem 2 There is a (8 + 2 √ 6)-approximation test for the problem of assigning tasks to unrelated machines.

Proof We solve the linear program Ass-LP and if feasible, we formulate the program SAss-LP given by (10a), (10b), (10c ) and (10d). We then apply Theorem 1 to obtain the integral vector ŷ, noting that γ = 2. The result follows from choosing ρ = 1 + √ 6/3 and applying Lemma 3.

Hardness result

Finally, we show that it is NP-hard to decide whether a task system T has an assignment which is feasible on m unrelated machines, even with a speedup factor of 2-, for any > 0; the proof follows the lines of the ( 3 2 -)-hardness result for makespan minimization in [START_REF] Lenstra | Approximation algorithms for scheduling unrelated parallel machines[END_REF]. We reduce from the 3-Dimensional Matching problem which is known to be NP-complete [START_REF] Lenstra | Approximation algorithms for scheduling unrelated parallel machines[END_REF] and is defined below. Instance of 3-dimensional matching Given are three disjoint sets, consisting of n elements each:

A = {a 1 , a 2 , . . . , a n } , B = {b 1 , b 2 , . . . , b n } and C = {c 1 , c 2 , . . . , c n }. Also, given is a family F = {F 1 , F 2 , . . . , F m } of m ≥ n
triples such that each triple contains exactly one element from the set A, one from B, and one from C, that is,

|F i ∩ A| = |F i ∩ B| = |F i ∩ C| = 1 for all i ∈ {1, . . . , m} .
Question Does F contain a 3-dimensional matching, i.e., a subfamily F ⊆ F for which |F | = n and F i ∈F F i = A ∪ B ∪ C ? Let > 0. Consider an instance I of 3-Dimensional Matching. We create an instance (task system) T for sporadic real-time scheduling on unrelated parallel machines in the following way:

-Define a large constant M := 2/ .

-Associate a machine i with each triple F i , yielding m machines.

-Let F(a k ) ⊆ F be the set of triples containing element a k ∈ A. We will slightly abuse notation and also use F(a k ) to refer to the set of machines corresponding to the triples in andc i,τ g = 2 otherwise. We refer to these tasks as being type I tasks. There will be n tasks of type I. -For each element c l ∈ C, create one task τ l such that d τ l = M and t τ l = ∞. Further, c i,τ l = M -1 if c l ∈ F i , and c i,τ l = 2M otherwise. We refer to these tasks as being type II tasks. There will be n tasks of type II. -For each element

F(a k ). Further, let f (a k ) := |F(a k )|. Note that a k ∈A f (a k ) = m. -For each element b g ∈ B, create one task τ g such that d τ g = 1 and t τ g = ∞. Further, c i,τ g = 1 if b g ∈ F i ,
a k ∈ A, create f (a k )-1 dummy tasks dum(k 1 ),. . . dum(k f (a k )-1 )
which have a deadline and period equal to one. Each dummy task dum(k z ) has c i,k z = 1 if i ∈ F(a k ), and c i,k z = 2 otherwise. Note that in total there will be mn dummy tasks.

In Lemmas 4 and 5 we show that the reduction from 3-Dimensional Matching is valid.

Lemma 4 If there exists a 3-dimensional matching for I, then there exists a feasible assignment for T .

Proof Let F * ⊆ F be the triples in the 3-dimensional matching. For all triples F i = a k , b g , c l ∈ F * , schedule tasks τ g and τ l on machine i. Note that machine i can process the tasks assigned to it. Also, all tasks corresponding to elements in B and C have been scheduled. As the element a k is only covered by one triple in G * , it follows that there are f (a k )-1 machines remaining in F(a k ) which are not assigned any tasks yet. Assign the f (a k )-1 dummy tasks dum(k 1 ), . . . dum(k f (a k )-1 ) to these machines. Note that a machine in F(a k ) can process exactly one dummy task corresponding to the element a k .

Before giving Lemma 5, we first need to show some propositions about the elements in the created scheduling instance T .

Proposition 2 For any ρ < 2, no task τ g corresponding to an element b g ∈ B can be scheduled on a machine i if b g / ∈ F i , even under a speedup of ρ.

Proposition 3 For any ρ < 2, no task τ l corresponding to an element c l ∈ C can be scheduled on a machine i if c l / ∈ F i , even under a speedup of ρ.

Proposition 4 For any ρ < 2, no dummy task dum(k z ) corresponding to an element a k ∈ A can be scheduled on a machine i if i / ∈ F(a k ), even under a speedup of ρ.

Proof We argue for Proposition 2. Propositions 3 and 4 follow similarly. The proof is by contradiction; let a task τ g corresponding to an element b g ∈ B be scheduled on a machine i such that b g / ∈ F i . Then c i,τ h = 2. At time d τ g = 1 the first job of task τ g needs to be completed and hence a speedup of 2 is required.

Proposition 5 For any ρ < 2 -/2, no dummy task dum(k z ) can be scheduled together with another task on the same machine, even under a speedup of ρ.

Proof We argue by contradiction. We consider three cases:

-Suppose that two dummy tasks were scheduled on the same machine. Both dummies would need to finish their first job by their first deadline which is at time 1.

Their accumulated processing requirement to the machine would be at least 2 and hence a speedup of at least 2 would be required. -Suppose a dummy task and a task of type I were scheduled on the same machine.

We reason analogously to the previous case. -Suppose a dummy task and a task of type II were scheduled on the same machine. Consider time instant M, where the dummy task should have finished M jobs, whereas the other task should have finished its first job. The accumulated processing requirement for the machine by time M would be at least

M * 1 + (M -1) = 2M -1. Hence, a speedup of 2M-1 M = 2 -1 M = 2 -/2 >
ρ would be required, by our definition of M. Lemma 5 For any ρ < 2 -/2, if there exists a feasible assignment for T with speedup ρ, then there exists a 3-dimensional matching for I.

Proof Proposition 5 yields that each dummy task gets its own machine, even under a speedup of ρ < 2-/2. Therefore, and by Proposition 4, for all a k ∈ A, there remains in each group F(a k ) one machine available to process tasks of type I or II, even under a speedup of ρ < 2. In total there are m -(mn) = n machines left which do not process a dummy task. There are 2n tasks of type I and II. Since a single machine cannot process two tasks of the same type under a speedup less than 2, it follows that each machine which does not process a dummy task, processes one task of type I and one task of type II. Let i k ∈ F(a k ) be the machine which does not process a dummy task but instead one task of type I and one task of type II. By Propositions 2 and 3, the only way for machine i k to be feasible, even under a speedup of ρ < 2, is when it processes the tasks corresponding to b g and c l where F i k = a k , b g , c l . It follows that the machines i k , for k ∈ {1, . . . , m}, define a 3-dimensional matching for I.

Theorem 3 Let > 0.
There is no (2 -)-approximation test for the problem of assigning tasks to unrelated machines, unless P = N P.

Proof Theorem 3 follows by Lemmas 4 and 5, and by the 3-Dimensional Matching problem being NP-complete.

We remark that our hardness result is different from the one by Andersson and Tovar [START_REF] Andersson | Competitive analysis of partitioned scheduling on uniform multiprocessors[END_REF]. They show that any algorithm needs a speedup factor of at least 2for finding a feasible partition on m related parallel machines for a given task system with implicit deadlines in case the task system is feasible when migration is allowed.

Constant number of machines

Assuming that the number of machines m is bounded by a constant, in this section we present a polynomial-time dynamic programming (DP) algorithm that gives a (1 + )approximation test for any > 0. During phase p, p = 1, 2, . . . , n, the DP computes a possible assignment of task τ p , using assignments of the first ( p -1) tasks. In order to obtain a DP-table of bounded size we introduce an approximation of the demand bound function such that the contribution of each task can be derived by using only a constant number of values.

By scaling all parameters, we assume that d min = min τ ∈T d τ = 1. Let > 0, and assume without loss of generality that < 1/2. Let L be the minimum integer which satisfies 1 ≤ (1 + ) L-1 2 . We define the function dbf * as

dbf * i (τ, s) := s+t τ -d τ t τ c i,τ if s < (1 + ) L d τ , c i,τ t τ s otherwise.
Given a task assignment T of the tasks in T to the machines, we define

dbf * T ,i (s) := τ ∈T i dbf * i (τ, s) ∀s > 0.
Further, to have clean notation, we write dbf * i (s) instead of dbf * T ,i (s) in case the assignment T is clear from the context. The key observation is that for computing the function dbf * i (τ, s) for a fixed task τ , it suffices to know the utilization of the task τ and the values of the demand bound function dbf i (τ, s) for s ∈ d τ , (1 + ) L d τ . Exploiting the properties of the functions dbf T ,i (s) and dbf * T ,i (s) yields that dbf * T ,i is a (1 + )-approximation of the 'real' demand bound function dbf T ,i .

Lemma 6 Given an assignment T and a constant < 1/2. Then, for all machines i,

(i) if dbf * T ,i ((1 + ) k ) ≤ α(1 + ) k for all k ∈ N ≥0 , then dbf T ,i (s) ≤ (1 + ) 2 αs for all s ≥ 0; (ii) if dbf T ,i (r ) ≤ r for all r ≥ 0, then dbf * T ,i (s) ≤ (1 + )s for all s ≥ 0.
Proof For the first claim, we first show that a slightly stronger statement holds for all powers of 1 + . We show that if for all k ∈ N ≥0 it holds that dbf * T ,i ((1

+ ) k ) ≤ α(1 + ) k , then for all k ∈ N ≥0 it holds that dbf T ,i (1 + ) k ≤ (1 + )α(1 + ) k . ( 13
)
Subsequently, we show that then for all s it holds that dbf T ,i (s) ≤ (1 + ) 2 αs. Inequality [START_REF] Bonifaci | A constant-approximate feasibility test for multiprocessor real-time scheduling[END_REF] trivially holds for all k with (1 + ) k ≤ d min , as then dbf i (τ, (1 + ) k ) = 0 for all tasks τ ∈ T . Assume that ( 13) holds for all k ∈ N ≥0 with k < k, we show that it then also holds for k. Let s := (1+ ) k . Consider some partition of the tasks

T = {T 1 , . . . , T m }. Let T early i := {τ ∈ T i |(1 + ) L d τ < s} and T late i := T i \T early i . By definition of dbf * T ,i it follows that dbf T ,i (s) ≤ τ ∈T i dbf * i (τ, s) + τ ∈T early i c i,τ = dbf * T ,i (s) + τ ∈T early i c i,τ . (14)
Further, since for τ ∈ T

early i it holds that d τ < s (1+ ) L , τ ∈T early i c i,τ ≤ τ ∈T early i s (1+ ) L + t τ -d τ t τ c i,τ = τ ∈T early i dbf i τ, s (1 + ) L ≤ dbf T ,i s (1 + ) L ( * ) ≤ αs (1 + ) L-1 ≤ 2 αs ≤ αs. ( 15
)
The inequality at ( * ) is due to the induction hypothesis; we assumed Inequality (13) to be correct for all k < k and

s (1+ ) L = (1 + ) k for k = k -L. (Note that although this was only shown for k ∈ N ≥0 , it holds also if k = k -L < 0, since then (1 + ) k ≤ 1 = d min .) The penultimate inequality follows from 1 (1+ ) L-1 < 2 .
Inequalities ( 14) and ( 15) imply that dbf T ,i (s) ≤ dbf * T ,i (s) + αs ≤ (1 + )αs. For all values of s which are not powers of 1 + , we observe that the function dbf T ,i (s) is non-decreasing and thus if Inequality [START_REF] Bonifaci | A constant-approximate feasibility test for multiprocessor real-time scheduling[END_REF] holds for all k ∈ N ≥0 , then (i) holds for all s. That is, for values s that are not powers of 1 + we need an additional factor of 1 + .

For the second claim no induction is necessary and we calculate that

dbf * T ,i (s) < τ ∈T late i dbf i (τ, s) + τ ∈T early i s -d τ + s (1+ ) L t τ c i,τ ≤ τ ∈T late i dbf i (τ, s) + τ ∈T early i s -d τ + t τ t τ + s (1 + ) L t τ c i,τ ≤ dbf T ,i (s) + τ ∈T early i ( 2 u i,τ )s = dbf T ,i (s) + 2 dbf * T early i ,i (s) ≤ dbf T ,i (s) + 2 dbf * T ,i (s). Therefore, (1 -2 )dbf * T ,i (s) ≤ dbf T ,i (s), i.e., dbf * T ,i (s) ≤ (1 + )dbf T ,i (s), for any < 1/2.
Note that, in contrast to other approximations of the demand bound function considered in the literature (e.g., [START_REF] Albers | An event stream driven approximation for the analysis of real-time systems[END_REF]), in Lemma 6 we do not use an analysis task by task, and we do not bound the ratio dbf (τ, s)/dbf * (τ, s). In fact, the latter can be unbounded: consider for example a task τ with c τ = 1, d τ = 1, and p τ = M for a very large value M, then dbf (τ, s) ≥ 1 for all s ≥ 1 whereas dbf * (τ, [START_REF] Albers | An event stream driven approximation for the analysis of real-time systems[END_REF]

+ ) L ) = (1 + ) L /M.
Observe that Lemma 6 implies that at the cost of a (1 + ) 2 -speedup it suffices to check whether the condition dbf * T ,i (s) ≤ s is (approximately) satisfied at powers of 1 + . Therefore, the DP may characterize each task τ only by its utilization and the constantly many values dbf * i (τ, (1

+ ) k ) (namely those values for integers k such that d τ ≤ (1 + ) k < (1 + ) L d τ , for each machine i).
For each task τ , each machine i and all ∈ N ≥0 , we introduce a vector v(i, τ ) by defining position

v(i, τ ) := dbf * i (τ, (1 + ) ) (1 + ) .
Recall that for any vector a the infinity norm a ∞ = max i {a i }. The following proposition follows by definition.

Proposition 6 Consider an assignment T . For all machines i ∈ M, it holds that

τ ∈T i v(i, τ ) ∞ ≤ α if and only if dbf * T ,i ((1 + ) ) ≤ α(1 + ) , for all ∈ N ≥0 .
We present a dynamic programming algorithm which either (1) asserts that there is no feasible assignment of the tasks to the machines by showing that there is no assignment T of tasks to machines such that we have

τ ∈T i v(i, τ ) ∞ ≤ 1 + for each machine i, or (2) finds an assignment T such that τ ∈T i v(i, τ ) ∞ ≤ 1 + O( )
for each machine i. In the latter case, Lemma 6 and the above proposition imply an approximation test for the problem of assigning tasks to a constant number of unrelated machines. The test either concludes that the task system is not feasible (without speedup) or provides an assignment which is feasible in case the machines have a speedup factor of 1 + O( ).

Assume without loss of generality that the tasks τ 1 , . . . , τ n are ordered such that d τ p ≤ d τ p+1 for each p. We partition the tasks into groups

G k := {τ |(1 + ) k ≤ d τ < (1 + ) k+1 } for each k ∈ N ≥0 .
The proposed DP works in phases; one phase for each task. The key idea is that when trying to assign task τ ∈ G k , the DP needs only a constant number of values from the assignment of the previously considered tasks.

Define L (k) := min{k, L} (such that k -L (k) ≥ 0). For all tasks having a deadline at most a factor (1 + ) L smaller than d τ p , the DP needs to know how much the vectors of tasks from each group G k (with k -L (k) < k ≤ k) contribute towards dimension on machine i, for k ≤ ≤ k + L. For the same groups G k the DP needs to know the summed utilization per machine i over group G k . For the other groups G k with k ≤ k -L (k) for each machine i, only the aggregated utilization over all groups is needed. Formally we need, for all i, Ideally, we would like the DP to store all possible combinations of the above quantities that can result from assigning the tasks of previous iterations. Then, the DP could compute the values for the next iteration by taking each combination of values from the last iteration and additionally schedule task τ to one of the machines. Unfortunately, the number of possible combinations of the above values is not polynomially bounded, as already the input values (which then imply the utilization, etc.) might be in an exponential range. In order to bound them, we round entries of the vectors v(i, τ ). The DP then performs the described procedure with the rounded vectors. This will result in a polynomial-time procedure.

-the sum τ ∈T i ∩ k-L (k) k =0 G k u i,τ , -the sum τ ∈T i ∩G k u i,τ , for all k s.t. k -L (k) < k ≤ k,
Consider a task τ ∈ G k , k ∈ N ≥0 . For all i and τ , define v (i, τ ) := n n v(i, τ )

for each ≤ k + L, and v (i, τ ) := u i,τ := n n u i,τ for each > k + L. The following lemma bounds the rounding error.

Lemma 7

Let i be a machine and T i be a set of tasks. For all ∈ N ≥0 , it holds that

τ ∈T i v (i, τ ) ≤ τ ∈T i v(i, τ ) ≤ τ ∈T i v (i, τ ) + .
Proof Consider a task τ ∈ T i . Define k(τ ) such that τ ∈ G k(τ ) . We show for each τ ∈ T i and the corresponding k(τ ) that v (i, τ ) ≤ v(i, τ ) ≤ v (i, τ ) + /n. The statement trivially follows. The case where ≤ k(τ ) + L follows trivially from the relation x ≤ x < x + 1 which holds for any x. Therefore, consider the case > k(τ

) + L. Since τ ∈ G k(τ ) , it follows that d τ < (1 + ) k(τ )+1 . Hence, dbf * i (τ, (1 + ) ) = c i,τ t τ (1 + ) = u i,τ (1 + ) which yields v(i, τ ) = u i,τ
. The result for the case > k(τ ) + L now also follows from x ≤ x < x + 1. Note that each rounded vector v (i, τ ) can be described with only constantly many pieces of information. When working with the rounded vectors, for the quantities mentioned above, there are only a polynomial number of combinations (assuming that m is a constant). In particular, the dynamic programming table will be of polynomial size. Formally, the dynamic programming table consists of entries of the form ( p, z, w, c) where -p ∈ {0, . . . , n} denotes the phase of the DP. In phase p, task τ p is being assigned to a machine. Let k be an integer such that τ p ∈ G k ; -in phase p, for each machine i, the value z ( p) i is of the form n for some integer , denoting the rounded aggregated utilization for machine i due to the tasks having a deadline at least a factor of (1 + ) L smaller with respect to the deadline of task τ p ; -in phase p, for each machine i and each k with k -

L (k) < k ≤ k, the value w ( p) i,k
is of the form n for some integer , denoting the rounded utilization of tasks in

G k ∩ T i ; -in phase p, for each triple (i, k , k ) ∈ C p with C p = {(i, k , k ) : 1 ≤ i ≤ m; k ≤ k < k + L and k -L (k ) < k ≤ k}, the value c ( p)
i,k ,k is of the form n for some integer , denoting the quantity τ ∈T i ∩G k v (i, τ ) k , expressing how much the vectors of the tasks in G k on machine i contribute towards dimension k . We require the following set of conditions to be satisfied for a DP-cell ( p, z, w, c) to exist; for each machine i ∈ M and all k ∈ {k, . . . , k + L}

z i + k -L (k ) k =k-L (k) +1 w i,k + k k =k -L (k ) +1 c i,k ,k ≤ 1 + . ( 16
)
This condition implies that, for all parameters, z i , w i,k , c i,k ,k ≤ 1 + .

n • (1 + )n m • (1 + )n mL • (1 + )n mL 2 ≤ n (1 + )n 2mL 2
Each entry ( p, z, w, c) of the DP-table either stores 'YES' or 'NO' depending on whether or not there is an assignment of the tasks τ 1 , . . . , τ p to the machines which yields the quantities given by the vectors z, w, c. We proceed by describing how to fill the DP-table. First, initialize the table by assigning a 'YES'-entry to (0, 0, 0, 0) and a 'NO'-entry to any other entry with p = 0. Assume that for some p, all entries of the form ( p -1, z ( p-1) , w ( p-1) , c ( p-1) ) have been computed. The DP-table is then iteratively extended to phase p. Phase p considers each combination of assigning task τ p to some machine i and a DPcell ( p -1, z ( p-1) , w ( p-1) , c ( p-1) ) with a 'YES'-entry. Intuitively, the DP computes which values for z ( p) , w ( p) , and c ( p) are obtained if it takes the task assignment encoded in the DP-cell ( p -1, z ( p-1) , w ( p-1) , c ( p-1) ) and additionally schedules task τ p to machine i.

Let tasks τ p-1 and τ p be in group G h and G k , respectively. Almost all entries of the vectors are equal and hence we only list the values which differ with respect to the entries from phase p -1. If h = k and task τ p is assigned to machine i, then w

( p) i,k = w ( p-1) i,k + u i,τ p , and c ( p) i,k,k = c ( p-1) i,k,k + v (i, τ p ) k for all k ∈ {k, . . . , k + L}.
If h = k, w.l.o.g. we assume that h = k -1 (e.g., by creating dummy tasks of zero processing requirement to fill in-between groups that otherwise would be empty and thus, non-existent). Then, z

( p) g = z ( p-1) g + w ( p-1)
g,k-L (k) for all machines g ∈ M; as we have moved up one group, tasks from group G k-L (k) now have their deadline at least a factor (1 + ) L away from d τ p and their utilizations are not stored separately anymore, but in a aggregated way. For the tasks in groups G k such that k -L (k) < k < k and all machines g ∈ M we still store the utilizations per group and thus w

( p) g,k = w ( p-1) g,k .
For group G k we also store the utilization for the machine i that it was assigned to, so w ( p) i,k = u i,τ p and w ( p) g,k = 0 for all machines g = i. Since τ p is assigned to machine i, c

( p) i,k,k = v (i, τ p ) k for all k : k ≤ k ≤ k + L; and for all machines g = i, c ( p) g,k,k = 0 for all k : k ≤ k ≤ k + L. Finally, c ( p) g,k ,k = c ( p-1) g,k ,k for all machines g ∈ M, all k : k ≤ k ≤ k + L and all k : k -L (k ) < k < k.
Hereafter, the DP checks whether the computed values z ( p) , w ( p) and c ( p) satisfy the condition given in [START_REF] Ebenlendr | Graph balancing: a special case of scheduling unrelated parallel machines[END_REF]. If this is the case, then the corresponding DPcell ( p, z ( p) , w ( p) , c ( p) ) is filled with a 'YES'-entry and we say that this DP-cell extends the DP-cell ( p -1, z ( p-1) , w ( p-1) , c ( p-1) ). In case there does not exist a DP-cell ( p -1, z ( p-1) , w ( p-1) , c ( p-1) ) which can be extended to the DP-cell ( p, z ( p) , w ( p) , c ( p) ), the latter DP-cell is filled with a 'NO'-entry.

The DP-table is filled inductively, phase by phase, until each cell in the DP-table is filled. In the next lemma we show for any machine i the equivalence between the inequalities τ ∈T i v (i, τ ) ∞ ≤ 1 + on the one hand, and condition (16) on the other hand.

Lemma 8 For phase p, if there exists a DP-cell of the form ( p, z ( p) , w ( p) , c ( p) ) with a 'YES'-entry, then there exists a task assignment T of the first p tasks to the machines, such that for each i ∈ M it holds that

τ ∈T i v (i, τ ) ∞ ≤ 1 + .
Proof Consider some phase p and assume that the statement is correct for all phases p < p. Let k be such that τ p ∈ G k . As no first job of any task in G k has its deadline before (1 + ) k it follows by induction that for all : 0 ≤ < k it holds that τ ∈T i v (i, τ ) ≤ 1 + . Next, we show the statement for phase p and the corresponding dimension k. Consider DP-cell of the form ( p, z ( p) , w ( p) , c ( p) ) with a 'YES'-entry. We denote by ( 16) ( p) the corresponding inequality given in ( 16) at phase p of the DP, that is, when task τ p is being assigned to a machine. For all machines i it follows that,

τ ∈T i v (i, τ ) k = k-L (k) k =0 τ ∈T i ∩G k u i,τ + k k =k-L (k) +1 τ ∈T i ∩G k v (i, τ ) k = z ( p) i + k k =k-L (k) +1 c ( p) i,k ,k (16) ( p) ≤ 1 + .
The last inequality follows by setting the parameter k of (16

) ( p) equal to k. Next, consider the dimensions : k < ≤ k + L. Note that d τ p < (1+ ) k+1 . Consequently, every task in ∪ k k =0 G k has its first deadline before (1 + ) k+1
, that is, being in phase p of the DP where τ p ∈ G k it follows that G k = ∅ for all k > k. This insight is used in the first equality below.

τ ∈T i v (i, τ ) = -L ( ) k =0 τ ∈T i ∩G k u i,τ + k k = -L ( ) +1 τ ∈T i ∩G k v (i, τ ) = ⎛ ⎝ z ( p) i + -L ( ) k =k-L (k) +1 w ( p) i,k ⎞ ⎠ + k k = -L ( ) +1 c ( p) i,k , (16) ( p) ≤ 1 + .
The last inequality follows by setting the parameter k of (16) ( p) equal to . Finally, the analysis for any dimension > k + L is equal to that of the dimension = k + L as the contribution of each task to any dimension ≥ k + L will be approximated by its utilization. Thus, τ ∈T i v (i, τ ) ∞ ≤ 1 + and the statement follows.

Lemma 9 For phase p, there exists a DP-cell of the form ( p, z ( p) , w ( p) , c ( p) ) with a 'YES'-entry, if there exists a task assignment T of the first p tasks to the machines, such that for each i ∈ M it holds that τ ∈T i v (i, τ ) First we need to show that the DP-cell ( p, z ( p) , w ( p) , c ( p) ) exists, that is, we need to check whether the inequality (16) ( p) holds. From the lemma statement it is known that τ ∈T i v (i, τ ) ≤ 1 + , for all . Thus, in particular, this inequality also holds for all dimensions k ∈ {k, . . . , k + L}. Therefore, for each machine i and each dimension k ∈ {k, . . . , k + L} it holds that

z ( p) i + k -L (k ) k =k-L (k) +1 w ( p) i,k + k k =k -L (k ) +1 c ( p) i,k ,k = k -L (k ) k =0 τ ∈G k v (i, τ ) k + k k =k -L (k ) +1 c ( p) i,k ,k = k -L (k ) k =0 τ ∈G k v (i, τ ) k + k k =k -L (k ) +1 τ ∈G k v (i, τ ) k = τ ∈T ( p) i v (i, τ ) k ≤ 1 + .
Consequently, the DP-cell ( p, z ( p) , w ( p) , c ( p) ) exists. The DP-cell ( p, z ( p) , w ( p) , c ( p) ) trivially extends the DP-cell ( p -1, z ( p-1) , w ( p-1) , c ( p-1) ) by assigning task τ p to machine i if τ p ∈ T ( p) i

. By induction it follows that the DP-cell ( p, z ( p) , w ( p) , c ( p) ) contains a 'YES'-entry, for all p ∈ {0, 1, . . . , n}.

Combining Lemmas 6, 7, 8 and 9, and Proposition 6 yields a (1+7 )-approximation test, for any and a constant number of machines. The claim on the running time follows from Proposition 7. If for a given > 0 we run the above procedure with := /7, rather than with , we obtain a (1 + )-approximation test.

Theorem 4 For a constant number of machines and for any > 0 there exists a (1 + )-approximation test, that runs in time polynomial in the number of tasks.

Proof We show that for a constant number of unrelated machines, the algorithm given above either concludes that the task system is infeasible, or returns an assignment of tasks to machines that is feasible with a speedup factor of 1 + 7 . The running time is polynomial in n, given that m and are constants. First, we redefine = min{ , 1/2}. Suppose that there is a DP-cell of the form (n, z, w, c) containing a 'YES'-entry. Due to Lemma 8 there is an assignment T of all tasks to the machines such that τ ∈T i v (i, τ ) ∞ ≤ 1 + , for each machine i ∈ M. By Lemma 7 this implies that τ ∈T i v(i, τ ) ∞ ≤ 1+2 . Due to Proposition 6 this implies that dbf * T ,i ((1+ ) k ) ≤ (1 + 2 )(1 + ) k for each k ∈ N.

Finally, Lemma 6 implies that the computed task assignment is feasible if the machines run with speed (1 + ) 2 (1 + 2 ) ≤ 1 + 7 (as < 1/2).

On the other hand, if all DP-cells of the form (n, z, w, c) have a 'NO'-entry, then, by Lemma 9, for any task assignment T there must be a machine i with τ ∈T i v (i, τ )

∞ > 1 + . By Lemma 7 this yields then that also

τ ∈T i v(i, τ )
∞ > 1 + . Proposition 6 yields that for this machine i there exists a time instant s which is a power of (1 + ) such that dbf * T ,i (s) > (1 + )s. Finally, (the negation of) Lemma 6 yields that there is a time instant r for which dbf T ,i (r ) > r . Since, for any partition T , there exist a machine i and a time instant r such that T violates the feasibility condition, it follows that the task system T is infeasible if the machines run at unit speed.

The claim that the running time is polynomial in n for given constant m and follows from Proposition 7 and the fact that each entry of the table can be decided upon in polynomial time. Herewith, note that L = O(log (1+ ) (1/ 2 )), which is constant if is constant.

Conclusion

In this paper we presented the first results for assigning sporadic tasks with arbitrary deadlines to unrelated parallel processors. Through the development of a new LP rounding procedure and approximations of the demand bound function we found a 8 + 2 √ 6 ≈ 12.9-approximate feasibility test for an arbitrary number of machines. We hope that future research might bring the approximation ratio down and close the gap between 12.9 and our lower bound of 2. One possible tool might be configuration-LPs which are often stronger than assignment-LPs like the one that we use here (see e.g., [START_REF] Asadpour | Santa Claus meets hypergraph matchings[END_REF][START_REF] Bansal | The Santa Claus problem[END_REF][START_REF] Svensson | Santa Claus schedules jobs on unrelated machines[END_REF]). Another interesting direction would be to obtain better approximations for the case that the processors are unrelated but there are only a few types of processors (e.g., CPUs and GPUs), as done in e.g., [START_REF] Raravi | Assigning real-time tasks on heterogeneous multiprocessors with two unrelated types of processors[END_REF][START_REF] Raravi | A PTAS for assigning sporadic tasks on two-type heterogeneous multiprocessors[END_REF][START_REF] Wiese | Partitioned EDF scheduling on a few types of unrelated multiprocessors[END_REF].

Our rounding procedure is very general and can not only be applied to the problem of assigning tasks to machines but for any assignment problem which allows for a sparse linear program. It would be interesting to see other new applications for it. Additionally, it would be interesting if a better rounding procedure can be given for large values of γ .

For a constant number of machines we give a polynomial-time approximation scheme. While for scheduling jobs on unrelated machines, a PTAS is relatively easy to obtain once one has the tools from Lenstra et al. [START_REF] Lenstra | Approximation algorithms for scheduling unrelated parallel machines[END_REF] at hand, for assigning sporadic tasks, much more sophisticated machinery was required.

∞ ≤ 1

 1 + .Proof Consider the assignment T( p) where the first p tasks are assigned to the machines such thatτ ∈T ( p) i v (i, τ ) ∞ ≤ 1+ for all machines i ∈ M. Let τ p ∈ G k .Define the following values for each machine i:z for k ∈ {k -L (k) , . . . ,k}, and c , τ ) k for k ∈ {k, . . . , k + L}, and for k ∈ {k -L (k ) , . . . , k}.

  and -the sum τ ∈T i ∩G k v(i, τ ) , for all s.t. k ≤ ≤ k + L and all k s.t. -L ( ) < k ≤ k.

Proposition 7

 7 The number of DP-cells is bounded by n((1+ )n/ ) 2mL 2 .Proof The values z i , w i,k and c i,k ,k are all stored with accuracy n and hence each of those can take (1 + )n/ many different realizations. Further, i can take m different values whereas k and k can take L different values if the DP is in a certain phase p. Further, there are at most n phases for the DP. It follows that the number of cells of the DP table is no more than