José R Correa
email: correa@uchile.cl

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

Jannik Matuschke
email: matuschke@math.tu-berlin.de

Leen Stougie
email: l.stougie@vu.nl

Ola Svensson
email: ola.svensson@epfl.ch

Víctor Verdugo

J Verschae
email: jverschae@ing.uchile.cl

Strong LP formulations for scheduling splittable jobs on unrelated machines

A natural extension of the makespan minimization problem on unrelated machines is to allow jobs to be partially processed by different machines while incurring an arbitrary setup time. In this paper we present increasingly stronger LP-relaxations for this problem and their implications on the approximability of the problem. First we show that the straightforward LP, extending the approach for the original problem, has an integrality gap of 3 and yields an approximation algorithm of the same factor. By applying a lift-and-project procedure, we are able to improve both the integrality gap and the implied approximation factor to 1 + φ, where φ is the golden ratio. Since this bound remains tight for the seemingly stronger machine configuration LP, we propose a new, infinite, job configuration LP, that we prove has a finite representation and can be solved in polynomial time up to any accuracy. Interestingly, we show that our problem cannot be approximated within a factor better than e e-1 ≈ 1.582 (unless P = N P), which is larger than the inapproximability bound of 1.5 for the original problem.

Introduction

The unrelated machine scheduling problem, R||C max in the three-field notation of [START_REF] Graham | Optimization and approximation in deterministic sequencing and scheduling: a survey[END_REF], has attracted significant attention within the scientific community. The problem is to find a schedule of jobs with machine-dependent processing times that minimizes the makespan, i.e., the maximum machine load. Lenstra et al. [START_REF] Lenstra | Approximation algorithms for scheduling unrelated parallel machines[END_REF] designed a polynomial time linear programming based rounding algorithm and showed that the algorithm has a worst-case approximation ratio of 2, and that the existence of a polynomial time algorithm with ratio smaller than 3/2 would prove that P = N P.

A natural generalization of this problem is to allow jobs to be split and processed on multiple machines simultaneously, where in addition a setup has to be performed on every machine processing the job. This generalized scheduling problem finds applications in production planning, e.g., in textile and semiconductor industries [START_REF] Kim | Unrelated parallel machine scheduling with setup times and a total weighted tardiness objective[END_REF][START_REF] Serafini | Scheduling jobs on several machines with the job splitting property[END_REF], and disaster relief operations [START_REF] Van Der Ster | The allocation of scarce resources in disaster relief[END_REF]. Formally, we are given a set of m machines M and a set of n jobs J with processing times p ij ∈ Z + and setup times s ij ∈ Z + for every i ∈ M and j ∈ J. A schedule corresponds to a vector x ∈ [0, 1] M ×J , where x ij denotes the fraction of job j that is assigned to machine i, satisfying i∈M x ij = 1 for all j ∈ J. If job j is processed (partially) on machine i then a setup of length s ij has to be performed on the machine. During the setup of a job the machine is occupied and thus no other job can be processed nor be set up. This results in the definition of load of machine i ∈ M as j:xij >0 (x ij p ij + s ij ). The objective is to minimize the makespan, the maximum load of the schedule. We denote this problem by R|split,setup|C max . Note that by setting p ij = 0 and interpreting the setup times s ij as processing requirements we obtain the classical problem without job splitting, R||C max . Related Work. Reducing the approximability gap for R||C max is a prominent open question [START_REF] Williamson | The Design of Approximation Algorithms[END_REF]. Since the seminal work by Lenstra et al. [START_REF] Lenstra | Approximation algorithms for scheduling unrelated parallel machines[END_REF] there has been a considerable amount of effort leading to partial solutions to this question. In the restricted assignment problem, the processing times are of the form p ij ∈ {p j , ∞} for all i, j ∈ J. A special case of this setting, in which each job can only be assigned to two machines, was considered by Ebenlendr et al. [START_REF] Ebenlendr | Graph balancing: A special case of scheduling unrelated parallel machines[END_REF]. They note that while the lower bound of 3/2 still holds, a 7/4approximation can be obtained. For the general restricted assignment problem Svensson [START_REF] Svensson | Santa claus schedules jobs on unrelated machines[END_REF] broke the barrier of 2, by showing it is approximable within a factor of 33/17 + ε ≈ 1.9412 + ε by an algorithm based on a machine configuration linear programming relaxation where each variable indicates the subset of jobs assigned to a given machine. On the other hand, this relaxation has an integrality gap of 2 for general unrelated machines [START_REF] Verschae | On the configuration-LP for scheduling on unrelated machines[END_REF], as was the case for the linear programming relaxation in [START_REF] Lenstra | Approximation algorithms for scheduling unrelated parallel machines[END_REF]. Configuration LPs have also been studied extensively for the max-min version of the problem [START_REF] Asadpour | Santa claus meets hypergraph matchings[END_REF][START_REF] Bansal | The Santa Claus problem[END_REF][START_REF] Feige | On allocations that maximize fairness[END_REF][START_REF] Haeupler | New constructive aspects of the Lovász Local Lemma[END_REF][START_REF] Polacek | Quasi-polynomial local search for restricted max-min fair allocation[END_REF][START_REF] Verschae | On the configuration-LP for scheduling on unrelated machines[END_REF], which has become known as the Santa Claus problem.

The literature on scheduling problems with splittable jobs is significantly less abundant. To the best of our knowledge such a problem has been presented for the first time in a production problem in the textile industry [START_REF] Serafini | Scheduling jobs on several machines with the job splitting property[END_REF]. It was modeled as a restricted assignment version, in which each job is associated to a specific subset of compatible machines on which it can be processed and can be split arbitrarily and processed independently on these machines. However no setup times are considered. The jobs are released over time and the goal is minimizing the maximum (weighted) tardiness. It turns out that this problem is solvable in polynomial time if machines are identical or uniform; the paper considers also the case of unrelated machines providing pseudopolynomial time algorithms. Another application of splittable jobs appears in production scheduling for semiconductor wafers [START_REF] Kim | Unrelated parallel machine scheduling with setup times and a total weighted tardiness objective[END_REF], again with the objective of minimizing the total weighted tardiness. The authors provide different variants of a local search heuristic to solve the problem in practice.

Theoretical results on the subject are not only scarce, but also restricted to the special case of identical machines. In particular, Xing and Zhang [START_REF] Xing | Parallel machine scheduling with splitting jobs[END_REF] describe a (1.75 -1/m)-approximation for makespan minimization, which was later improved to 5/3 by Chen et al. [START_REF] Chen | Lot-sizing scheduling with batch setup times[END_REF]. The problem with splittable jobs, setup times, and the objective of minimizing the sum of completion times, having arisen in modeling a problem on disaster relief operations [START_REF] Van Der Ster | The allocation of scarce resources in disaster relief[END_REF], is studied by Schalekamp et al. [START_REF] Schalekamp | Split scheduling with uniform setup times[END_REF]. They give a polynomial time algorithm in the case of 2 machines and job-and machine-independent setup times, and a 2.781approximation algorithm for arbitrary m. This was later improved to 2 + ε in [START_REF] Correa | Approximation algorithms for scheduling splitting jobs with setup times[END_REF], even in the presence of weights, in which case the problem is NPhard [START_REF] Schalekamp | Split scheduling with uniform setup times[END_REF].

Another setting that comes close to job splitting is preemptive scheduling with setup times [START_REF] Liu | Minimizing total completion time subject to job release dates and preemption penalties[END_REF][START_REF] Potts | Integrating scheduling with batching and lot-sizing: A review of algorithms and complexity[END_REF][START_REF] Schuurman | Preemptive scheduling with job-dependent setup times[END_REF], which does not allow simultaneous processing of parts of the same job. We also refer to the survey [START_REF] Allahverdi | A survey of scheduling problems with setup times or costs[END_REF] and references therein for results on other scheduling problems with setup costs.

Our Contribution. Due to the novelty of the considered problem, our aim is to advance the understanding of its approximability, in particular in comparison to R||C max . We first study the integrality gap of a natural generalization of the LP relaxation by Lenstra et al. [START_REF] Lenstra | Approximation algorithms for scheduling unrelated parallel machines[END_REF] to our setting and notice that their rounding technique does not work in our case. This is because it might assign a job with very large processing time to a single machine, while the optimal solution splits this job. On the other hand, assigning jobs by only following the fractional solution given by the LP might incur a large number of setups (belonging to different jobs) to a single machine. We get around these two extreme cases by adapting the technique from [START_REF] Lenstra | Approximation algorithms for scheduling unrelated parallel machines[END_REF] so as to only round variables exceeding a certain threshold while guaranteeing that only one additional setup time is required per machine. This yields a 3-approximation algorithm presented in Section 2. Additionally, we show that the integrality gap of this LP is exactly 3, and therefore our algorithm is best possible for this LP.

In Section 3 we improve the approximation ratio by tightening our LP relaxation with a lift-and-project approach. We refine our previous analysis by balancing the rounding threshold, resulting in a (1 + φ + ε)-approximation for any ε > 0, where φ ≈ 1.618 is the golden ratio. Surprisingly, we can show that this number is best possible for this LP; even for the seemingly stronger machine configuration LP mentioned above. This suggests that considerably different techniques are necessary to match the 2-approximation algorithm for R||C max . Indeed, we also show in Section 5 that it is N P-hard to approximate within a factor e e-1 ≈ 1.582, a larger lower bound than the 3/2 hardness result known for R||C max . For the restricted assignment case, where s ij ∈ {s j , ∞} and p ij ∈ {p j , ∞}, we obtain a (2 + ε)-approximation algorithm, for any ε > 0, matching the 2-approximation of [START_REF] Lenstra | Approximation algorithms for scheduling unrelated parallel machines[END_REF] in Section 4. We remark that the solutions produced by all our algorithms have the property that at most one split job is processed on each machine. This property may be desirable in practice since in manufacturing systems setups require labor causing additional expenses.

As the integrality gaps of all mentioned relaxations are no better than 1+φ, we propose a novel job based configuration LP relaxation in Section 6.2 that has the potential to lead to better guarantees. Instead of considering machine configurations that assign jobs to machines, we introduce job configurations, describing the assignment of a particular job to the machines. The resulting LP cuts away worst-case solutions of the other LPs considered in this paper, rendering it a promising candidate for obtaining better approximation ratios. While the job configuration LP has an infinite set of variables, we show that we can restrict a priori to a finite subset. Applying discretization techniques we can approximately solve the LP within a factor of (1 + ε) by separation over the dual constraints. Finally, we study the projection of this polytope to the assignment space and derive an explicit set of inequalities that defines this polytope. An interesting open problem is to determine the integrality gap of the job configuration LP.

A 3-approximation algorithm

Our 3-approximation algorithm is based on a generalization of the LP by Lenstra, Shmoys, and Tardos [START_REF] Lenstra | Approximation algorithms for scheduling unrelated parallel machines[END_REF]. Let C * be a guess on the optimal makespan. Consider the following feasibility LP, whose variable x ij denotes the fraction of job j assigned to machine i.

[LST] :

i∈M x ij = 1 for all j ∈ J, (1)
j∈J x ij (p ij + s ij ) ≤ C * for all i ∈ M, (2)
x ij = 0 for all i ∈ M, j ∈ J : s ij > C * , (3)
x ij ≥ 0 for all i ∈ M, j ∈ J.

Notice that the smallest value of C * such that [LST] is feasible can be computed in polynomial time. Indeed, there are at most n • m different thresholds for C * that changes the subset of equalities considered in [START_REF] Bansal | The Santa Claus problem[END_REF]. We solve one linear program for each of them, where C * is treated as a variable and the objective function is to minimize C * . Among all these linear programs we select the one of the smallest C * and such that it is consistent with the corresponding threshold for the s ij 's. The computed C * value satisfies that C * ≤ OPT, where OPT is the optimal solution of the original problem R|split,setup|C max .

Let x be a feasible extreme point of [LST]. We define the bipartite graph G(x) = (J ∪ M, E(x)), where E(x) = {ij : 0 < x ij }. Using the same arguments as in [START_REF] Lenstra | Approximation algorithms for scheduling unrelated parallel machines[END_REF], not repeated here, we can show the following property.

Lemma 1 For every extreme point x of [LST], each connected component of G(x) is a pseudotree; a tree plus at most one edge that creates a single cycle.

We devise a procedure for rounding the extreme point x. To this end, we define

E + = {ij ∈ E(x) : x ij > 1/2} and J + = {j ∈ J : there exists i ∈ M with ij ∈ E + },
i.e., those jobs that the fractional solution x assigns to some machine by a factor of more than 1/2. In our rounding procedure each job j ∈ J + is completely assigned to the machine i ∈ M for which x ij > 1/2. We now show how to assign the remaining jobs.

Let us call G (x) the subgraph of G(x) induced by (J ∪M )\J + . Notice that every edge ij in G (x) satisfies 0

< x ij ≤ 1/2. Also, since G (x) is a subgraph of G(x) every connected component of G (x) is a pseudotree. Definition 1 Given A ⊆ E(G (x)), we say that a machine i ∈ M is A- balanced, if there exists at most one job j ∈ J \ J + such that ij ∈ A. We say that a job j ∈ J \ J + is A-processed if there is at most one machine i ∈ M such that ij / ∈ A and x ij > 0.
In what follows we seek to find a subset A ⊆ E(G (x)) such that each job j ∈ J \ J + is A-processed and each machine is A-balanced. We will show that this is enough for a 3-approximation, by assigning each job j ∈ J \ J + to machine i by a fraction of at most 2x ij for each ij ∈ A, and not assigning it anywhere else. Since every job j ∈ J \ J + is A-processed and x ij ≤ 1/2 for all i ∈ M (including the only machine i with ij / ∈ A, if it exists), job j will be completely assigned. Also, since each machine is A-balanced, the load of each machine i will be affected by at most the setup-time of one job j. This setup time s ij is at most C * by restriction (3). This and the fact that the processing time of a job on each machine is at most doubled are the basic ingredients to show the approximation factor of 3.

Construction of the set A. In the following, we denote by (T, r) a rooted tree T with root r. Consider a connected component T of G (x). Since G (x) is a subgraph of G(x), Lemma 1 implies that T is a pseudotree. We denote by C = j 1 i 1 j 2 i 2 • • • j i j 1 the only cycle of T (if it exists), which must be of even length. If such a cycle does not exist we choose any path in T from j 1 to some i . The jobs in the cycle are J(C) = {j 1 , . . . , j } and the machines are M (C) = {i 1 , . . . , i }. In the cycle, we define the matching K C = {(j k , i k ) : k ∈ {1, . . . , }}. In the forest T \ K C , we denote by (T u , u) the tree rooted in u, for every u ∈ J(C). Notice that by deleting the matching, no two vertices of J(C) will be in the same component of T \ K C .

For every u ∈ J(C), by directing the edges of (T u , u) away from the root, we obtain a directed tree, each level of which consists either entirely of machinenodes or entirely of job-nodes. We delete all edges going out of machine nodes, i.e., all edges entering job-nodes. The remaining edges we denote by A u . We define A := u∈J(C) A u ; see Figure 1 for a depiction of the situation. The following two lemmas show that the set A is indeed A-processed and A-balanced.

Lemma 2 Every job j ∈ J \ J + is A-processed.
Proof Consider first a job j k ∈ J(C). Since j k is the root of the tree T j k , the set A contains all its incident edges apart from the edge (i k , j k ), which was removed as part of the matching K C . Therefore j k is A-processed for all k ∈ {1, . . . , }. Now consider a job j / ∈ J(C). This job j is part of a directed tree T u and has exactly 1 incoming edge in that tree. By construction of A u , this edge is the only edge incident to the job-node that is deleted, hence it is A-processed.

Lemma 3 Every machine i ∈ M is A-balanced.
Proof Any machine i ∈ M is a node of some tree T u . By construction, the single incoming edge into i of T u is the only edge incident to i that survives in A, hence i is A-balanced.

Given set A, we apply the following rounding algorithm that constructs a new assignment x. The algorithm also outputs a binary vector ỹij ∈ {0, 1} which indicates whether job j is (partially) assigned to machine i or not.

Algorithm 1 Rounding(x)

1: Construct the graphs G(x), G (x), and the set A as above. 2: For all ij ∈ E + , xij ← 1 and ỹij ← 1;

3: For all ij ∈ A, xij ← x ij k:kj∈A x kj and ỹij ← 1; 4: For all ij ∈ E \ (E + ∪ A), xij ← 0 and ỹij ← 0.
Theorem 1 There exists a 3-approximation algorithm for R|split,setup|C max .

Proof Let x be an extreme point of [LST] and consider the output x, ỹ of algorithm Rounding(x). Clearly x, ỹ can be computed in polynomial time. We show that the schedule that assigns a fraction xij of job j to machine i has a makespan of at most 3C * . This implies the theorem since, as discussed before, C * ≤ OPT. First we show that x ≥ 0 defines a valid assignment, i.e., i∈M xij = 1 for all j. Indeed, this follows directly by the algorithm Rounding(x): If j ∈ J + , then there exists a unique machine i ∈ M with ij ∈ E + and therefore j is completely assigned to machine i.

If j ∈ J + , then i∈M xij = i:ij∈A x ij k:kj∈A x kj = 1.
Now we show that the makespan of the solution is at most 3C * . First notice that for every ij ∈ E + we have that 1

= xij = ỹij ≤ 2x ij , because ij ∈ E + implies that x ij > 1/2.
On the other hand, for every j ∈ J \ J + we have that k:kj∈A x kj ≥ 1/2, because at most one machine that processes j fractionally is not considered in A. We conclude that x ≤ 2x. Then for every i ∈ M it holds that j∈J

(x ij p ij + ỹij s ij ) = j:ij∈E+ (x ij p ij + ỹij s ij ) + j:ij∈A (x ij p ij + ỹij s ij ) ≤ j:ij∈E+ 2x ij (p ij + s ij ) + j:ij∈A (2x ij p ij + s ij ) ≤ 2C * + j:ij∈A s ij .
Recall that machine i is A-balanced, and therefore there is at most one job j with ij ∈ A. Also, ij ∈ A implies that ij ∈ E(x) = {ij : x ij > 0}, and hence, by (3) in [LST], s ij ≤ C * . We conclude that j:ij∈A s ij ≤ C * , and the theorem follows.

We finish this section by noting that our analysis is tight. Specifically, it can be shown that the gap between the LP solution and the optimum can be arbitrarily close to 3.

Theorem 2 For any ε > 0, there exists an instance such that (3 -ε)C * ≤ OPT, where C * is the smallest number such that [LST] is feasible. Proof We give a family of instances {I k } k∈N such that OPT/C * approaches 3 as k goes to infinity. This suffices for showing the theorem.

M 1 M M 2k+1 J M k k k k p ij = 2k s ij = 0 p ij = 0 s ij = 1
Instance I k has a set J of 2k + 1 jobs. For each job j ∈ J we introduce its own set of k identical machines M j , i.e., M j ∩ M j = ∅ if j = j . We define s ij = 1 and p ij = 2k for each j ∈ J and i ∈ M j , and

s ij = p ij = ∞ if i ∈ M j with j = j.
Additionally, we introduce a new family of k machines M , where for all j ∈ J and i ∈ M we have p ij = 0 and s ij = 1. See Fig. 2 for a depiction of the construction.

We claim that the LP has a solution with C * = 1 + 1 2k while OPT = 3. To see that OPT = 3, notice that there are two possible cases. If all jobs in J are completely assigned to machines in M then the makespan is clearly 3 since there are k machines in M and 2k + 1 jobs, and each job has to use a setup time of 1 on each machine. Otherwise, there exists one job j ∈ J that is completely assigned to machines in M j . It is easy to see that the solution that minimizes the makespan on these machines assigns job j up to a fraction of 1/k to each machine in M j . Then the load on each machine i ∈ M j is 1 + p ij /k = 3. Therefore OPT = 3.

We now give a feasible solution to [LST] with C * := 1+ 1 2k . This is obtained with the following fractional assignment,

x ij := 1 2k
for each j ∈ J and i ∈ M j ∪ M , 0 otherwise.

Since |M j ∪ M | = 2k it is clear that every job is completely assigned. Then, to see that in [LST] (2) is satisfied, notice that for i ∈ M we have that

j∈J x ij (p ij + s ij ) = j∈J x ij = 2k + 1 2k = 1 + 1 2k = C * ,
and similarly, for i ∈ M j , j ∈J

x ij (p ij + s ij ) = x ij (p ij + s ij ) = 2k + 1 2k = C * .
We conclude that the gap for instance

I k is 3 1+ 1 2k
, which converges to 3 when k goes to infinity.

An LP with integrality gap 1 + φ

In this section we refine the previous algorithm and improve the approximation ratio. Since [LST] has a gap of 3, we strengthen it in order to obtain a stronger LP. To this end notice that inequalities (2) in [LST] are the LP relaxation of the following constraints of the mixed integer linear program with binary variables y ij for machine i and job j:

j∈J (x ij p ij + y ij s ij ) ≤ C * for all i ∈ M, (4)
x ij ≤ y ij for all i ∈ M and j ∈ J.

A stronger relaxation is obtained by applying a lift and project step [START_REF] Lovász | Cones of matrices and set-functions and 0-1 optimization[END_REF] to the first inequality. For some fixed choice ij multiplying both sides of the i-th inequality (4) by the corresponding variable y ij implies (by leaving out terms)

y ij x ij p ij + y 2 ij s ij ≤ y ij C * .
In case C * -s ij > 0, this inequality implies the valid linear inequality

x ij p ij C * -s ij ≤ y ij , (6)
since every feasible integer solution has y ij x ij = x ij and y 2 ij = y ij . Note that, in optimal solutions of the LP relaxation, y ij attains the smallest value that satisfies (5) and [START_REF] Ebenlendr | Graph balancing: A special case of scheduling unrelated parallel machines[END_REF]. Therefore, we define

α ij = max 1, pij C * -sij if C * > s ij ,
and α ij = 1 otherwise, and substitute y ij by α ij x ij to obtain the strengthened LP relaxation

[LST strong ] : i∈M x ij = 1
for all j ∈ J, (7)

j∈J x ij (p ij + α ij s ij ) ≤ C * for all i ∈ M, (8)
x ij = 0 for all i ∈ M, j ∈ J : s ij > C * , (9)
x ij ≥ 0 for all i ∈ M, j ∈ J.

Notice that this LP is at least as strong as [LST] since α ij ≥ 1. Since the α ij variables depend on C * , we cannot use the approach of Section 3 to find the smallest C * value such that [LST strong ] is feasible. Instead, for any ε > 0, we find a value of C * such that [LST strong ] is feasible and

C * ≤ (1 + ε)OPT.
This follows by a straightforward binary search procedure on integer powers of 1 + ε. Note that the value of C * that we find here might be strictly larger than the one used in the previous section. Let x be an extreme point of this LP. We use a rounding approach similar to the one in the previous section. Consider the graph G(x). As before, each connected component of G(x) is a pseudotree, using the same arguments that justified Lemma 1. Also, we define again a set of jobs J + that the LP assigns to one machine by a sufficiently large fraction. In the previous section this fraction was 1/2. Now we parameterize it by β ∈ (1/2, 1), to be chosen later.

We define

E + = {j ∈ E(x) : x ij > β} and J + = {j ∈ J : there exists i ∈ M with ij ∈ E + }.
Consider the subgraph G (x) of G(x) induced by the set of nodes (J ∪ M ) \ J + . Let A be a set constructed as in the previous section. Then, as in Section 2, every machine is A-balanced and every job is A-processed. Now we apply the algorithm Rounding(x) of the last section to obtain a new assignment x, ỹ. We show that for β = φ -1 this is a solution with makespan (1 + φ)C * , where φ = (1 + √ 5)/2 ≈ 1.618 is the golden ratio. The following technical lemma is needed.

Lemma 4 Let β be a real number such that 1/2 < β < 1. Then

max 0≤µ≤1 µ + max 1 β , 1 -µ 1 -β = max 1 1 -β , 1 + 1 β . Proof Let f (µ) = µ + max 1 β , 1-µ 1-β .
Clearly f is a piece-wise linear function with at most two different slopes. Therefore, it is maximized when µ ∈ {0, 1} or when µ is the breakpoint of the function, i. e., when µ solves the equation µ + 1/β = µ + (1 -µ)/(1 -β). Let µ 0 be the solution of this equation. A simple computation shows that f (µ 0 ) = 2, which implies that max 0≤µ≤1 f (µ) = max{f (0), f (µ 0 ), f (1)} = max{1/(1 -β), 2, 1 + 1/β}. Since 1/2 < β < 1, we have 1/(1 -β) > 2 and 1 + 1/β > 2, which implies the lemma.

Theorem 3 For any ε > 0, there exists a (1 + φ + ε)-approximation algorithm for the problem R|split,setup|C max .

Proof By binary search we find C * such that [LST strong ] is feasible, and such that C * ≤ (1 + ε )OPT. Let x be an extreme point of [LST strong ] with this value of C * , and let x, ỹ be the output of algorithm Rounding(x) described in Section 2. The fact that x, ỹ correspond to a feasible assignment follows from the same argument as in the proof of Theorem 1. We now show that the makespan of this solution is at most (1+φ)C * , which implies the approximation factor.

For any edge ij ∈ E + , we have

x ij > β and hence 1 = xij = ỹij ≤ 1/β • x ij .
Additionally, for every j ∈ J \ J + , we have again, by the choice of A, that it is A-processed. Hence, k:kj / ∈A x kj ≤ β, because at most one machine that processes j fractionally is not considered in A. Thus, k:kj∈A x kj ≥ 1 -β, which implies that xij ≤ x ij /(1 -β). Hence, for machine i,

j∈J (x ij p ij + ỹij s ij ) = j:ij∈E+ (x ij p ij + ỹij s ij ) + j:ij∈A (x ij p ij + ỹij s ij ) ≤ 1 β j:ij∈E+ x ij (p ij + s ij ) + 1 1 -β j:ij∈A x ij p ij + j:ij∈A s ij .
Since machine i is A-balanced, there exists at most one job j with ij ∈ A (if there is no such job then i has load at most C * /β). Let j(i) be that job, and define µ i = s ij(i) /C * . Then notice that

x ij(i) (p ij(i) + α ij(i) s ij(i) ) ≥ x ij(i) p ij(i) 1 + s ij(i) C * -s ij(i) = x ij(i) p ij(i) 1 + µ i 1 -µ i = x ij(i) p ij(i) 1 1 -µ i .
Combining the last two inequalities we obtain that j∈J

(x ij p ij + ỹij s ij ) ≤ 1 β j:ij∈E+ x ij (p ij + s ij ) + 1 1 -β x ij(i) p ij(i) + s ij(i) ≤ 1 β j:ij∈E+ x ij (p ij + s ij ) + 1 -µ i 1 -β x ij(i) (p ij(i) + α ij(i) s ij(i) ) + µ i C * ≤ max 1 β , 1 -µ i 1 -β j∈J x ij (p ij + α ij s ij ) + µ i C * ≤ C * µ i + max 1 β , 1 -µ i 1 -β .
Therefore, by the previous lemma we have that the load of each machine is at most C * • max{1/(1 -β), 1 + 1/β}. The latter factor is minimized when

1/(1 -β) = 1 + 1/β, hence β = (-1 + √ 5)/2 = (1 + √ 5)/2 -1 = φ - 1. Together with the fact that C * ≤ (1 + ε )OPT, the approximation ratio becomes (1 + 1/(φ -1))(1 + ε ) = (1 + φ)(1 + ε ) and choosing ε = (1 + φ)ε completes the proof.
We close this section by showing that 1 + φ is the best approximation ratio achievable by [LST strong ].

Theorem 4 For any ε > 0, there exists an instance such that Proof Consider the instance depicted in Fig. 3. It consists of two disjoint sets of jobs J and J . Each job j ∈ J forms a pair with its corresponding job j ∈ J . Each such pair is associated with a parent machine i p (j ) = i p (j ) = i p such that both j and j can be processed on this machine with setup time s i p j = s i p j = φ/2 and p i p j = p i p j = 0. Each job j of each pair is furthermore associated with a child machine i c (j) such that s ic(j)j = 0 and p ic(j)j = φ + 1 = 1/(2 -φ). In addition, there is a single top job j t that can be processed on any of the parent machines with setup time 1 and processing time 0. All other setup and processing times are infinite.

C * (1 + φ -ε) ≤ OPT, where C * is the smallest number such that [LST strong ] is feasible. jt j 1 j 1 j k j k i 1 p i k p ic(j 1 ) ic(j 1 ) ic(j k ) ic(j k ) • • • p ij = 0 s ij = 1 p ij = 0 s ij = 1 2(φ -1)
p ij = 1 2 -φ s ij = 0
We will show that the makespan of any feasible solution is at least 1 + φ while the LP relaxation has a value of 1 + 1/k. First, it is easy to check that the following fractional assignment is a feasible solution to [LST strong ] with

C * = 1 + 1/k. x ij =          φ -1 for j ∈ J ∪ J , i = i p (j), 2 -φ for j ∈ J ∪ J , i = i c (j), 1 k
for j = j t , i = i p for all = 1, . . . , k, 0 otherwise.

To see that the optimal makespan of the instance is 1 + φ, let i p (j ) be the machine that receives the top job j t in an optimal solution (note that p j t i = 0 for all i, and hence this job is never split). Similarly, jobs j and j are not split in an optimal solution. If either of these jobs is completely assigned to its child machine, then the makespan of the schedule is 1/(2 -φ) = 1 + φ. Otherwise, j and j are both assigned to i p (j ) = i p (j ), which then has a load of 1 + 1/(φ -1) = 1 + φ. The theorem follows by choosing k large enough for the given ε.

A (2 + ε)-approximation algorithm for restricted assignment

In this section we consider the restricted assignment setting, i.e., for every job j there exists a set of machines M j such that p ij = p j , s ij = s j if i ∈ M j and

p ij = s ij = ∞ if i / ∈ M j .
We use the same relaxation as in the previous section to show that this version admits a 2-approximation algorithm, [LST strong ] :

i∈Mj x ij = 1
for all j ∈ J, [START_REF] Grötschel | Geometric Algorithms and Combinatorial Optimization[END_REF] j∈J:i∈Mj

x ij (p j + α j s j ) ≤ C * for all i ∈ M, (11)
x ij = 0 for all i ∈ M, j ∈ J :

s ij > C * , (12)
x ij ≥ 0 for all j ∈ J and i ∈ M j , where α j = max {1, p j /(C * -s j )}. Let x be an extreme point of this LP. As the basis for the rounding procedure we consider in this case the graph G (x) = (J (x) ∪ M, E (x)) defined by the set of edges E (x) = {ij : 0 < x ij < 1} and the set of job-nodes J (x) = {j ∈ J : j is incident to some e ∈ E (x)}; i.e., we fix all variables x ij that have value 0 or 1. As before, each connected component of G (x) is a pseudotree. Let A be the set constructed as in Section 2, now based on the graph G (x).

As in Section 2, consider a component of G (x) and choose a perfect matching K C on its cycle C (if it exists). For every job-node u ∈ J(C), let T u denote the out-tree rooted at u in the forrest obtained by removing K C from C. Given a job j, let u(j) be the unique node in the cycle such that j is a node of T u(j) , and let ch(j) denote the children of job j in that tree. Note that ch(j) corresponds to a set of machines.

We will prove that an additional time of C * units on each machine in ch(j) are enough for processing j completely. Then, distributing each job on the set ch(j) processes each job completely and each machine of ch(j) will be overloaded by at most C * . We start by noticing a simple lower bound on the degree of any job-node in G (x). In what follows we denote by δ(v) the set of edges incident to node v in G (x).

Lemma 5 Let δ(j) denote the set of edges incident to j ∈ J (x) in G (x). Then |δ(j)| ≥ max{2, α j }.

Proof By construction, it is clear that |δ(j)| ≥ 2 since for every edge ij of G (x) we have that x ij < 1. Define the variable y ij as y ij = 1 if 0 < x ij < 1 and 0 otherwise. Noticing that [START_REF] Haeupler | New constructive aspects of the Lovász Local Lemma[END_REF]

implies α j x ij ≤ 1 |δ(j)| = i∈Mj y ij ≥ i∈Mj α j x ij = α j .
The lemma follows by the integrality of |δ(j)|.

Let i be any machine in ch(j). Note that in [LST strong ] already a load of x ij (p j + α j s j ) units of time on i are reserved for job j. Let L ij := x ij (p j + α j s j ) + C * -s j be the amount of time available just for processing job j on machine i if we increase the load of the machine by C * . The following lemma shows that the total amount of available space over all machines in ch(j), i.e. i∈ch(j) L ij , suffices to process job j fully.

Lemma 6

For any job j it holds that i∈ch(j)

L ij ≥ p j .
Proof For any job-node j ∈ J (x), there is at most one machine adjacent to j in G (x) that is not in ch(j). Let us call this machine i * j . Then, by the previous lemma we have that i∈ch(j)

L ij = |ch(j)|(C * -s j ) + i∈ch(j) x ij (p j + α j s j ) ≥ (|δ(j)| -1)(C * -s j ) + (1 -x i * j j )(p j + α j s j ) ≥ max{1, α j -1}(C * -s j ) + (1 -x i * j j
)(p j + α j s j ). In the case that α j = 1, we can bound this expression by C * -s j , which is greater than or equal to p j , as p j /(C * -s j ) ≤ 1 in this case. Therefore we can assume that α j > 1 and hence α j = p j /(C * -s j ). Again use that (11) implies α j x ij ≤ 1, whence x ij ≤ 1/α j , for any i, j, to obtain i∈ch(j)

L ij ≥ ( α j -1)(C * -s j ) + (1 -x i * j j )(p j + α j s j ) ≥ ( α j -1)(C * -s j ) + 1 - 1 α j (p j + α j s j ) = ( α j -1)(C * -s j ) + (α j -1)( p j α j + s j ) = ( α j -1)(C * -s j ) + (α j -1)C * ≥ ( α j + α j -2)(C * -s j ).
Since α j > 1 implies α j ≥ 2, the last expression is at least α j (C * -s j ) = p j , which proves the lemma.

Theorem 5 For any ε > 0, there exists a (2 + ε)-approximation algorithm for scheduling splittable jobs on unrelated machines under restricted assignment.

Proof By binary search we find C * such that [LST strong ] is feasible, and such that C * ≤ (1 + ε )OPT. The previous lemma shows that we can process each fractional job j in ch(j) if we allow a makespan of 2C * . With the choice ε = 2ε , this yields the claimed approximation guarantee by noting that by construction ch(j) ∩ ch(k) = ∅ for any pair of fractional jobs j, k.

Finally, we remark that setting all p j = 0, which implies α j = 1, yields the LP relaxation of the restricted assignment version of R||C max , implying an integrality gap of 2; see [START_REF] Lenstra | Approximation algorithms for scheduling unrelated parallel machines[END_REF].

Hardness of approximation

By reducing from Max k-Cover, we derive an inapproximability bound of e/(e -1) ≈ 1.582 for R|split,setup|C max , indicating that the problem might indeed be harder from an approximation point of view compared to the classic R||C max , for which 3/2 is the best known lower bound [START_REF] Lenstra | Approximation algorithms for scheduling unrelated parallel machines[END_REF].

Theorem 6 For any ε > 0, there is no e e-1 -ε -approximation algorithm for R|split,setup|C max unless P = N P.

Proof We prove the hardness of R|split,setup|C max by providing a reduction from the Max k-Cover problem defined as follows: given a universe of elements e 1 , . . . , e m and a family of subsets of this universe S 1 , . . . , S n , find k sets that maximizes the number of covered elements, i.e., the number of elements contained in the union of the selected sets. In a seminal paper [START_REF] Feige | A threshold of log(n) for approximating set cover[END_REF], Feige showed that it is N P-hard to distinguish between instances in which all elements can be covered with k disjoint sets and instances where no k sets can cover more than a (1 -1 e ) + ε fraction of the elements for any ε > 0. In addition, this hardness holds for instances where all sets have the same cardinality, namely m/k.

Given a Max k-Cover instance where each set has cardinality m/k we construct an instance of our problem in polynomial time as follows. We define n jobs, one for each set S j . We define a set of n -k generic machines with the property that on each one of them each job j has setup time 1 and processing time 0. Next, we create an element-machine m i for each element e i , on which each job j with e i ∈ S j requires setup time s mij = 0 and processing time p mij = m/k = |S j |, and each job j with e i / ∈ S j has setup time s ei,j = 2 and

p mij = m/k = |S j |.
We observe that any solution to this instance of R|split,setup|C max with a makespan strictly less than 2 schedules n -k jobs on the generic machines. The remaining k jobs correspond to k sets from the Max k-Cover instance and the makespan depends on the number of elements these sets cover. To see this, first note that we can only assign a remaining job to an elementmachine that corresponds to an element of its set; otherwise, the makespan would immediately be 2. Thus, we may assume that the processing of the k jobs that do not go to the generic machines, will be completely done on element-machines. Now, on the one hand, if the k remaining jobs correspond to k disjoint sets, each of cardinality m/k, that cover all elements, then the total processing time m/k of each of these jobs can be split into equal fractions k/m of length 1 each, on each of its m/k element-machines. Since, setup times for these job-parts are 0, each element-machine gets a load of 1. This together with the fact that each generic-machine is assigned only one job yields a solution of makespan 1.

On the other hand, if the remaining k jobs correspond to k sets that cover at most (1 -1/e + ε )m elements, then we have to divide a total processing time of m over (1 -1 e + ε )m element-machines. In the best case this yields a makespan of m (1-1 e +ε )m = e e-1 -ε. This proves that it is N P-hard to distinguish between instances that have optimal makespan 1 and instances that have optimal makespan e e-1 -ε for any ε > 0.

Notice that the construction used in this lower bound makes it non-valid for the restricted assignment version of the problem. For that version the best known lower bound is still 3/2, resulting from the basic makespan problem without splits [START_REF] Lenstra | Approximation algorithms for scheduling unrelated parallel machines[END_REF].

Configuration LP relaxations

A basic tool of combinatorial optimization is to design stronger linear programs based on certain configurations. These LPs often provide improved integrality gaps and thus lead to better approximation algorithms as long as they can be solved efficiently and be rounded appropriately. We consider two configuration LPs in this section: a machine configuration LP, which we show to exhibit, surprisingly, the same integrality gap of 1 + φ as already observed for [LST strong ], and a job configuration LP, which we show to be much more promising.

A machine configuration LP

In machine scheduling the most widely used configuration LP uses as variables the possible configurations of jobs on a given machine. These machine configuration LPs have been successfully studied for the unrelated machine setting since the pioneering work of Bansal and Sviridenko [START_REF] Bansal | The Santa Claus problem[END_REF]. Recent progress in the area includes [START_REF] Ebenlendr | Graph balancing: A special case of scheduling unrelated parallel machines[END_REF][START_REF] Svensson | Santa claus schedules jobs on unrelated machines[END_REF][START_REF] Sviridenko | Approximating the configuration-lp for minimizing weighted sum of completion times on unrelated machines[END_REF][START_REF] Verschae | On the configuration-LP for scheduling on unrelated machines[END_REF].

The standard way to formulate a machine configuration LP relaxation for allocation problems is to have a variable for each machine i and each subset (configuration or bundle) B of jobs that can be feasibly assigned to i with respect to a guessed makespan C * . In the context of R|split,setup|C max the natural extension of a configuration B for machine i is associated with a vector x B ∈ [0, 1] J that specifies what fraction of job j is scheduled on machine i in the configuration. Let B i denote this set of feasible configurations for machine i and guessed makespan C * . Thus, we have that B ∈ B i if and only if

j:x B j >0 (x B j p ij + s ij ) ≤ C * .
The machine configuration LP is now a feasibility LP with a variable ρ B for each B ∈ i∈M B i indicating whether or not the configuration B is assigned to a machine i and it has the following constraints:

[MCLP] :

B∈Bi ρ B ≤ 1 for all i ∈ M, i∈M B∈Bi x B j ρ B ≥ 1 for all j ∈ J, ρ B ≥ 0 for all B ∈ i∈M B i .
The first set of constraints says that we should (fractionally) assign at most one configuration to each machine and the second set of constraints says that each job should be (fractionally) assigned (at least) once. It is easy to see that [MCLP] is a relaxation of our problem and that the minimum C * such that [MCLP] is feasible provides a lower bound on the optimal makespan OPT. Rather surprisingly, we show that this seemingly stronger relaxation has the same integrality gap as the strengthened assignment LP [LST strong ].

Theorem 7 For any ε > 0, there exists an instance such that C * (1 + φ -ε) ≤ OPT, where C * is the smallest number such that [MCLP] is feasible.

Proof The construction is similar to that in the proof of Theorem 4.

We first select the parameters of the construction. Let β = φ -1 and select k, G, d to be large integers (dependent on ε) so that

1 - 1 k d G ≥ β and G d ≥ 1 β -ε. (13)
Based on these parameters we construct the integrality gap instance as follows.

There are k disjoint groups of jobs J 1 , . . . , J k , each containing G jobs, i.e., J 1 = {j

1 , . . . , j

(G) 1 }, . . . , J k = {j (1)
k , . . . , j

k }. For each job j ∈ k =1 J there is a child machine i c (j) and for each group = 1, . . . , k there is a parent machine i p (j (1) G) ) that can process all the jobs in J .

) = i p (j (2) ) = • • • = i p (j (
Finally, there is a top job j t (see Fig. 4 and notice the tree structure with j t being the root).

The processing times and setup times are as follows,

p ij =          0 for j ∈ k =1 J , i = i p (j), 1 1-β for j ∈ k =1 J , i = i c (j), 0 for j = j t , i = i p (j) for any j ∈ k =1 J , ∞
otherwise. First we prove that an optimal solution has makespan at least 1 + φ -ε. To see this, let i p (j (i) ) be the machine that receives the top job j t in an optimal solution (since p j t i = 0 for all i, this job is never split). Similarly, jobs j (1) , . . . , j G) are not split in an optimal solution. If either of these jobs is completely assigned to its child machine, then the makespan of the schedule is G) are all assigned to i p (j [START_REF] Kim | Unrelated parallel machine scheduling with setup times and a total weighted tardiness objective[END_REF].

s ij =          1 d for j ∈ k =1 J , i = i p (j), 0 for j ∈ k =1 J , i = i c (j), 1 for j = j t , i = i p (j) for any j ∈ k =1 J , ∞ otherwise. jt j (1) 1 j (G) 1 j (1) k j (G) k i 1 p i k p ic(j (1) 1 ) ic(j (G) 1 ) ic(j (1)
k ) ic(j (G) k ) • • • • • • • • • p ij = 0 s ij = 1 p ij = 0 s ij = 1/d p ij = 1/(1 -β) s ij = 0
1/(1 -β) = 1 + φ. Otherwise, j (1) , . . . j (
(1) ) = • • • = i p (j (G) ), which will have a load of 1 + G/d ≥ 1 + 1 β -ε = 1 + φ -ε, using that G/d ≥ 1/β -ε by
Having proved that an optimal solution has makespan at least 1 + φ -ε, we complete the proof by showing that [MCLP] is feasible for C * = 1. Since j t has setup time 1 and processing time 0 on all parent machines, we have that a configuration B i t that schedules j t completely on machine i and no other job is feasible for these machines. We choose ρ B i t = 1/k for each parent machine, i.e., for each machine i = i p (j) for some j ∈ k =1 J . Note that this will assign job j t fractionally and also leaves a (1 -1/k) fraction of space on each parent machine for other configurations.

It remains to assign the jobs in k =1 J . For any such a job j, define the configuration B c j , that assigns a (1 -β) fraction of it to its child machine i c (j) and nothing else; i.e., x B c j j = 1 -β and x B c j j = 0 for any other job j = j. B c j is a feasible configuration for machine i c (j), because job j has processing time 1/(1 -β) and setup time 0 on that machine. We choose ρ B c j = 1 for each j ∈ k =1 J . Thus, so far we have assigned a fraction 1 -β of each job j ∈ k =1 J , i.e., a β fraction of these jobs remains to be assigned. We will assign this remaining fraction to the parent machine for each job. To construct the configurations necessary for this, we consider each group = 1, 2, . . . , k separately. As the jobs in J have processing time 0 and setup time 1/d on i p , a feasible configuration for i p is to completely schedule any d jobs in J . There are G d different ways of forming such a configuration, i.e., by selecting d jobs out of the G jobs in J . Recall that i p has a (1-1/k) fraction of remaining space for processing such configurations. We use this space completely, by assigning an equal fraction to each of the G d configurations containing exactly d jobs, i.e., we choose ρ B = (1 -1/k)/ G d for each configuration B ∈ B i p that completely schedules d of the jobs in J on machine i p . This will schedule the remaining β fraction of a job in J because it is part of exactly G-1 d-1 such configurations and

1 - 1 k G-1 d-1 G d = 1 - 1 k d G ≥ β,
where the last inequality follows from [START_REF] Kim | Unrelated parallel machine scheduling with setup times and a total weighted tardiness objective[END_REF]. Since this holds for every group , each job is completely assigned and each machine receives (fractionally) a configuration of makespan 1. We have thus proved that [MCLP] is feasible for C * = 1 and the statement follows.

A job configuration LP

As the machine configuration LP does not provide any improvement over the assignment LP [LST strong ], we introduce a new family of configuration LPs, which we call job configuration LPs. A configuration f for a given job j specifies the fraction of j that is scheduled on each machine. The configuration consists of two vectors x f ∈ [0, 1] M and y f ∈ {0, 1} M such that i∈M x f i = 1 and

y f i = 1 if and only if x f i > 0. On machine i ∈ M configuration f requires time t f i := p ij x f i + s ij y f i .
Let F j be the set of configurations for job j with t f i ≤ C * for all i ∈ M . Then every feasible solution to R|split,setup|C max with makespan C * corresponds to an integer solution of

[CLP] :

f ∈Fj λ f = 1 for all j ∈ J, j∈J f ∈Fj λ f t f i ≤ C * for all i ∈ M, λ f ≥ 0 for all f ∈ j∈J F j .
Note that this formulation has infinitely many variables. However, by investigating the separation problem of the convex dual of [CLP], we will show that we can restrict [CLP] without loss of generality to the finite subset of so-called maximal configurations. A configuration f ∈ F j is maximal, if there is at most one machine i ∈ M with 0 < x f i < x max ij , where

x max ij := (C * -s ij )/p ij .
Theorem . Note that there is a separating inequality corresponding to a configuration f ∈ F j for some job j such that µ j + i∈M t f i δ i < 0. If f is not maximal, then there are two distinct machines i and k such that 0 < x f i < x max ij and 0 < x f k < x max kj . Assume without loss of generality δ i p ij ≤ δ k p kj and consider the configuration f obtained by shifting as much of job j as possible from machine k to machine i, i.e.,

x f :=      min{x max ij , x f i + x f k } if = i, max{0, x f k + x f i -x max ij } if = k, x f
otherwise.

Observe that µ j + i∈M t f i δ i ≤ µ j + i∈M t f i δ i < 0. Iterating this argument we obtain a configuration that is maximal and whose inequality is violated by (µ, δ). This implies that [D] is completely described by the inequalities corresponding to maximal configurations. Therefore, [CLP] has a feasible solution if and only if the restriction of [CLP] to maximal configurations has a feasible solution.

Note that while Theorem 8 enables us to restrict [CLP] to a finite number of configurations, the number of variables is still exponential in the input size. In order to approximately solve the LP in polynomial time, we will discretize [CLP]. Given ε > 0, the discretization will violate the makespan C * by a factor of 1 + ε: If [CLP] is feasible then the discretized LP, [CLP] d , will also be feasible, while if [CLP] d is feasible then [CLP] is feasible for configurations with makespan C * (1 + ε).

For a given job j we define the set of discretized configurations F d j as all configurations such that all x f i take values that are multiples of ε/m, i.e., F d j contains configurations f with Proof Given a configuration f ∈ F j we define a rounded configuration f with

x f i = k i • ε/m for some k i ∈ {0, . . . ,
x f i := x f i • m ε • ε m and y f i = y f i for all i ∈ M. Notice that x f i -ε/m ≤ x f i ≤ x f i and therefore i∈M x f i ≥ 1 -ε. Thus f ∈ F d j .
machine i ∈ M with 0 < x f i < x max ij := (C * -s ij ) • m p ij • ε ε m . Lemma 8
> i∈M C * • δ i + j∈J µ j , 0 ≤ µ j + i∈M t f i δ i for all j ∈ J, f ∈ F d j , δ i ∈ R + , µ j ∈ R for all i ∈ M, j ∈ J.
To determine the feasibility of this dual program we use the equivalence of separation and optimization [START_REF] Grötschel | Geometric Algorithms and Combinatorial Optimization[END_REF]. Given a solution µ, δ the separation problem can be solved by fixing j ∈ J and solving the minimization problem

[P j ] : min i∈M t f i δ i : f ∈ F d j .
By the same argument as given in the proof of Theorem 8, notice that the optimal solution of [P j ] is a maximal configuration. With this observation at hand, we solve [P j ] efficiently. First, we guess the machine i * ∈ M with 0 < x f i * < x max i * j together with the fraction x f i * . Recall that x f i * must be one of only m/ε + 1 different values, thus this guessing takes only polynomial time. For a given i * and x f i * , problem [P j ] reduces to finding a set S ⊆ M \ {i * } such that i∈S x max ij ≥ 1-ε-x f i * while minimizing i∈S δ i (x max ij p ij +s ij ). Observe that this is a Knapsack Cover problem, which can be solved in pseudopolynomial by adapting the dynamic program for the standard Knapsack problem [START_REF] Ibarra | Fast approximation algorithms for the Knapsack and Sum of Subset problems[END_REF]. This yields a polynomial algorithm in our case since the values x max ij are of the form k i • m/ε for some k i ∈ {0, . . . , m/ε }.

Projection of the job configuration LP. Observe that any convex combination of job configurations λ can be translated into a pair of vectors x λ , y λ ∈ [0, 1] M ×J in the assignment space by setting

x λ ij := f ∈Fj λ f x f i and y λ ij := f ∈Fj λ f y f i .
We show that applying this projection to [CLP] leads to assignment vectors described by the following set of inequalities:

[CLP proj ] : j∈J (p ij x ij + s ij y ij ) ≤ C * for all i ∈ M, (14)
i∈M

(β i x ij + γ i y ij ) ≥ K(j, β, γ) for all j ∈ J, β, γ ∈ R M , (15)
with K(j, β, γ) Proof Let λ be a feasible solution to [CLP] and let β, γ ∈ R M + . By definition of K(j, β, γ) for any j ∈ J we have that

:= min i∈M (β i x f i + γ i y f i ) : f ∈ F j .
i∈M β i x ij + γ i y ij = i∈M f ∈Fj λ f β i x f i + γ i y f i ≥ K(j, β, γ).
Furthermore by feasibility of λ we obtain the following inequality, proving that (x λ , y λ ) is a feasible solution to [CLP proj ].

j∈J

p ij x λ ij + s ij y λ ij = j∈J f ∈Fj p ij λ f x f i + s ij λ f y f i = j∈J f ∈Fj λ f t f i ≤ C * .
To prove the converse consider (x, y) a feasible solution to [CLP proj ]. Clearly, there exists λ ∈ [CLP] with x = x λ , y = y λ if and only if the following LP has a feasible solution.

f ∈Fj x f i λ f = x ij for all i ∈ M, j ∈ J, f ∈Fj y f i λ f = y ij for all i ∈ M, j ∈ J, Applying inequality [START_REF] Lenstra | Approximation algorithms for scheduling unrelated parallel machines[END_REF] to the term C * in the objective function of this dual, we obtain the lower bound i∈M j∈J

f ∈Fj λ f =
x ij (β ij + p ij δ i ) + y ij (γ ij + s ij δ i ) + j∈J µ j .
This, in turn, can be lower bounded using inequalities (15) by j∈J K j, (β ij + p ij δ i ) i∈M , (γ ij + s ij δ i ) i∈M + µ j .

To conclude observe that the constraints of the dual guarantee that each of the summands is non-negative, implying that the dual is bounded.

The following lemma shows that all inequalities of [LST strong ] are special cases of the inequalities of [CLP proj ] and therefore the latter linear program is at least as strong as the former.

Lemma 9 Let x, y be a feasible solution to [CLP proj ] for some value of C * . Then x is a feasible solution to [LST strong ] for the same value of C * .

Proof Let x, y be a feasible solution to [CLP proj ] for the given value of C * . For any j ∈ J and any f ∈ F j , observe that i∈M x f i = 1 and also x f i ≥ 0 for all i ∈ M . Therefore [START_REF] Liu | Minimizing total completion time subject to job release dates and preemption penalties[END_REF] implies i∈M x ij = 1 and x ij ≥ 0 for all i ∈ M . Now assume s ij > C * for some i ∈ M and j ∈ J. Then x f i = 0 in all configurations f ∈ F j and therefore (15) implies x ij = 0 for any such pair of job and machine. Finally, observe that x f i ≤ x max ij in all configurations and therefore -α ij x f i + y f i ≥ 0 for all f ∈ F j with α ij as defined in Section 3. Therefore, inequalities [START_REF] Liu | Minimizing total completion time subject to job release dates and preemption penalties[END_REF] imply α ij x ij ≤ y ij for all i ∈ M and j ∈ J and thus inequalities [START_REF] Lenstra | Approximation algorithms for scheduling unrelated parallel machines[END_REF] imply j∈J x ij (p ij +α ij s ij ) ≤ C * for all i ∈ M . Hence x is a feasible solution for [LST strong ] with makespan C * .

In particular, Lemma 9 implies that the integrality gap of [CLP] is at most that of [LST strong ]. We conclude this section by showing that already a very special class of inequalities [START_REF] Liu | Minimizing total completion time subject to job release dates and preemption penalties[END_REF] from [CLP proj ] is sufficient to eliminate the gap in the worst-case instances of [LST strong ]. For a set of machines S ⊆ M let L(j, S) := i∈M \S max C * -sij pij , 0 be the maximum fraction of job j that can be processed within time C * by the machines in M \ S. The following inequalities are satisfied by the vector x, y induced by any feasible solution to R|split,setup|C * max with makespan at most C * .

i∈S x ij 1 -L(j, S ∪ S ) + i∈S y ij ≥ 1 for all j ∈ J and S, S ⊆ M with L(j, S∪S ) < 1.

One way to validate these inequalities is to observe that they are a special case of inequalities ( 15), obtained by setting β i = 1 1-L(j,S∪S ) for j ∈ S and 0 everywhere else, and γ i = 1 for i ∈ S and 0 everywhere else. The corresponding value K(j, β, γ) can be verified to be at least 1. However, for an alternative and more direct argument for the validity of the inequalities, observe that any feasible solution must process a total fraction of at least 1 -L(j, S ∪ S ) on the machines in S ∪ S . Therefore, either i∈S x ij ≥ 1 -L(j, S ∪ S ) or at least one machine in S is used to process job j. In either case, the left hand side of the corresponding inequality is at least 1. Now consider the example instance given in the proof of Theorem 4 and depicted in Fig. 3. If C * < 1 + φ, then L(j, {i p (j)}) = C * /p ic(j)j < 1 and therefore y ip(j)j = 1 for all j ∈ J ∪ J in any feasible solution to [CLP proj ]. This immediately implies infeasibility of [CLP proj ] for any C * < 1 + φ. We also note that the exact same argument applies to the worst-case instance of the machine configuration LP.

It will be interesting to find out if this job configuration LP will indeed have a better integrality gap and accompanying approximation algorithm.

Fig. 1

 1 Fig. 1 Construction of set A. Double lines represent edges in K C , single lines edges in A, and dotted lines are edges deleted in the construction.

Fig. 2

 2 Fig. 2 Example showing that [LST] has a gap of 3.

Fig. 3

 3 Fig. 3 Example showing that [LSTstrong] has a gap of 1 + φ.

Fig. 4

 4 Fig. 4 Example showing that [MCLP] has a gap of 1 + φ.

Theorem 9

 9 If λ ∈ [CLP] then (x λ , y λ ) ∈ [CLP proj ]. Conversely, if (x, y) ∈ [CLP proj ] then there exists λ ∈ [CLP] such that x = x λ and y = y λ .

  8 [CLP] is feasible if and only if the restriction of [CLP] to maximal configurations is feasible. To see this, let δ ∈ R M + and µ ∈ R J be an infeasible solution to [D]

	Proof Consider the convex dual of [CLP], which is described by
	[D] : min	C * • δ i +	µ j ,
	i∈M		j∈J
	s.t. µ j +	t f i δ i ≥ 0	for all j ∈ J, f ∈ F j ,
		i∈M
	δ i ∈ R + , µ j ∈ R	for all i ∈ M, j ∈ J.
	By convex duality (see e.g. [23, Theorem 2.2]), [CLP] is feasible if and only
	if [D] has a bounded value. We prove that every inequality of [D] is implied by
	an inequality corresponding to a maximal configuration, concluding that [D] is
	polyhedral.

  m/ε }, and y f i = 1 if and only if x f i > 0. Moreover, we relax the requirement that the fractions x f i add up to one, and only ask that ix f i ≥ 1 -ε. The discretized configuration LP [CLP] d istherefore described exactly as [CLP], only replacing F j by F d j . We now prove [CLP] d indeed approximates [CLP] arbitrarily well. Lemma 7 If [CLP] is feasible for makespan C * , then [CLP] d is feasible for makespan C * . Also, if [CLP] d is feasible for makespan C * , then [CLP] is feasible for makespan (1 + ε)C * .

  This implies that if [CLP] is feasible then also [CLP] d . Conversely, given a solution of [CLP] d we can multiply the vector (x f i ) i∈M for each f ∈ F d j by a factor of 1/(1 -ε) = 1 + O(ε). This yields configurations that violate the makespan C * by a factor of 1 + O(ε), and thus [CLP] is feasible for this type of configurations. Next we show that [CLP] d can be solved in polynomial time. Again, maximal configurations will play an important role in our proof. In the context of the discretization, a configuration f ∈ F d j is maximal if and only if there is at most one

  The program [CLP] d can be solved in polynomial time. Moreover, if the LP is feasible there always exists a solution in which all configurations in the support are maximal.

Proof By Farkas' Lemma (see e.g.

[START_REF] Schrijver | Theory of Linear and Integer Programming[END_REF]

), [CLP] d is feasible if and only if the following LP is infeasible, 0

  1 for all j ∈ J, By duality, the latter holds if and only if the following LP is bounded.min i∈M j∈J (x ij β ij + y ij γ ij ) +

	t f i λ f ≤ C *	for all i ∈ M,
	j∈J f ∈Fj
	λ f ≥ 0	for all f ∈

j∈J F j . j∈J µ j + i∈M C * δ i s.t. i∈M x f i β ij + y f i γ ij + µ j + i∈M t f i δ i ≥ 0 for all j ∈ J, f ∈ F j , δ i ≥ 0 for all i ∈ M.

Acknowledgements This work was partially supported by Nucleo Milenio Información y Coordinación en Redes ICM/FIC P10-024F, by EU-IRSES grant EUSACOU, by the DFG Priority Programme "Algorithm Engineering" (SPP 1307), by the Berlin Mathematical School, by ERC Starting Grant 335288-OptApprox, and by FONDECYT project 3130407.