Marin Bougeret
email: bougeret@imag.fr

Pierre Francois Dutot
email: dutot@imag.fr

Klaus Jansen

Christina Robenek

Denis Trystram
email: trystram@imag.fr

Scheduling jobs on heterogeneous platforms ⋆

In the context of grid scheduling we consider a scheduling scenario, where parallel jobs have to be scheduled non-preemptively on heterogeneous computational platforms of processors. The speed of the processors may differ among the platforms and the jobs are submitted simultaneously or over the time and cannot run across multiple platforms. We focus on the target of minimizing the total makespan, i.e. the global latest finishing time of a job. In this paper we present an AFPTAS for the problem without release times and show how to generalize our result to malleable jobs and jobs with release times.

Introduction

For solving problems that include large-scale computation grid computing gets more and more important. The efficient coordination of those computations appearing as atomic jobs on distributed resources is a difficult task. To get theoretical insights one first need to think of an adequate model that realizes the main principles of grid computing. In this paper we focus on a scheduling scenario, where parallel jobs have to be scheduled non-preemptively on heterogeneous computational platforms of processors. In order to complete extensive computations as fast as possible we are interested in minimizing the total makespan, i.e. the global latest finishing time of a job. The jobs are submitted simultaneously or over the time and cannot run across multiple platforms. In the following we describe our basic model where we consider heterogeneous platforms with different speeds and parallel jobs without release times (SPP ). Later we fit this model to take malleable jobs and release times into account. Model. In our setting we have n jobs {J 1 , . . . , J n } that have to be scheduled on N platforms P ℓ , ℓ ∈ {1, . . . , N }. A platform P ℓ contains a set M ℓ of m ℓ identical processors. We assume the platforms to be sorted by non-decreasing order of their number of processors (or machines), i.e. m 1 ≤ m 2 ≤ . . . ≤ m N . To each platform is assigned a speed value s ℓ ∈ R > 0. Every job J j is described by a pair (p j , q j ) of the length of a job p j (number of operations) and a number of parallel processors q j (degree of parallelism), that J j requires when executed. We assume q j ≤ m N = max ℓ m ℓ for all jobs, if not there is no feasible schedule. Since sometimes we will identify jobs with rectangles we call q j the width of job J j . Consequently, the area (or work ) of a job is p j q j and for a list of jobs or rectangles L we denote with A(L) the total area of the jobs (or rectangles) in L. A job J j is only allowed to be scheduled within one platform, its processing time in platform P ℓ is t ℓ j := pj s ℓ if q j ≤ m ℓ else t ℓ j = ∞. We assume furthermore (by scaling) min ℓ s ℓ = 1 and define t max := max j,ℓ {t ℓ j |t ℓ j < ∞}, which is less than p max := max j p j (as min ℓ s ℓ = 1). Our objective is to find a non-preemptive schedule of all jobs into the platforms minimizing C max := max ℓ C max (ℓ), where C max (ℓ) denotes the completion time of a feasible schedule in P ℓ . For an instance J of SPP let OPT(J) denote the optimum value for C max . For a minimization problem as SPP we say that an algorithm B has absolute ratio α, if sup J B(J) /OP T (J) ≤ α, and asymptotic ratio α, if α ≥ lim sup OP T (J)→∞ B(J) /OP T (J), respectively. A minimization problem admits an (asymptotic) polynomial-time approximation scheme ((A)PTAS), if there exists a family of polynomial-time approximation algorithms {B ε |ε > 0} of (asymptotic) (1 + ε)-approximations. We call an approximation scheme fully polynomial ((A)FPTAS), if the running time of every algorithm B ε is bounded by a polynomial in the size of the input |J| and 1 ε . Related work. For N = 1 the problem is equivalent to scheduling n parallel jobs on m identical machines. The well-known List Algorithm of Garey and Graham [START_REF] Garey | Bounds for Multiprocessor Scheduling with Resource Constraints[END_REF] achieves absolute ratio 2 for this problem. For the case that the number of machines is polynomially bounded in the number of jobs a (1.5 + ε)approximation for the contiguous case and a (1 + ε)-approximation for the noncontiguous case were given in [START_REF] Jansen | Approximation algorithms for scheduling parallel jobs: Breaking the approximation ratio of 2[END_REF]. For malleable job scheduling there are several results, as e.g. in [START_REF] Du | Complexity of scheduling parallel task systems[END_REF], [START_REF] Jansen | Linear-time approximation schemes for scheduling malleable parallel tasks[END_REF], [START_REF] Jansen | Scheduling malleable parallel tasks: An asymptotic fully polynomial time approximation scheme[END_REF] and [START_REF] Mounié | Efficient approximation algorithms for scheduling malleable tasks[END_REF].

If N = 1 and the jobs are assigned to processors of consecutive addresses, the problem corresponds directly to strip packing. For strip packing classical shelf-based algorithms are given in [START_REF] Coffman | Performance bounds for level-oriented two-dimensional packing algorithms[END_REF]. Further results are given in [START_REF] Schiermeyer | Reverse-fit: A 2-optimal algorithm for packing rectangles[END_REF], [START_REF] Steinberg | A strip-packing algorithm with absolute performance bound 2[END_REF] and [START_REF] Harren | A 5/3 + ε approximation for strip packing[END_REF]. An important result is an AFPTAS for strip packing with additive constant O( 1 /ε 2 h max ) given by Kenyon and Rémila in [START_REF] Kenyon | A near optimal solution to a two-dimensional cutting stock problem[END_REF], where h max denotes the height of the tallest rectangle (i.e. the length of the longest job). This constant was improved by Jansen and Solis-Oba, who presented in [START_REF] Jansen | New approximability results for 2-dimensional packing problems[END_REF] an APTAS with additive constant h max .

The problem SPP is also closely related to the generalized multiple strip packing (MSP ) where rectangles have to be packed into strips of infinite height and different widths. Here one wants to find a packing that minimizes the maximum of the heights used in every strip. It corresponds to the case that all platforms are identical and the jobs need to be scheduled on contiguous processors. For MSP Zhuk [START_REF] Zhuk | Approximate algorithms to pack rectangles into several strips[END_REF] showed that there is no polynomial time approximation algorithm with absolute ratio better than 2 (unless P = N P ). Later, Ye et al. [START_REF] Ye | On-line multiple-strip packing[END_REF] obtained an algorithm for MSP with ratio 2 + ε. In [START_REF] Bougeret | Approximation algorithms for multiple strip packing[END_REF] we presented a tight 2-approximation and an AFPTAS for MSP. Keep in mind that because of the contiguity constraint algorithms for SPP cannot be directly applied to the generalized MSP, but vice versa. However, in general approximation ratios are not preserved, but the optimal value for generalized MSP is an upper bound of the optimal value for SPP.

Schwiegelshohn et al. [START_REF] Schwiegelshohn | Online scheduling in grids[END_REF] achieved ratio 3 scheduling parallel jobs on heterogeneous platforms with identical speeds without release times, and ratio 5 with release times. Tchernykh et al. presented in [START_REF] Tchernykh | Two level job-scheduling strategies for a computational grid[END_REF] an algorithm with absolute ratio 10 without release times. For scheduling parallel jobs on identical platforms, we proposed recently a low cost approximation algorithm with absolute ratio 5 /2 in [START_REF] Bougeret | A low cost 5/2 approximation for scheduling rigid jobs on multiple organizations[END_REF]. We were able to improve our result to a fast 5 /2-approximation for heterogeneous platforms with identical speeds and under the additional constraint that every job can be scheduled in each platform [START_REF] Bougeret | A fast 5/2approximation algorithm for hierarchical scheduling[END_REF]. Our results. In this paper we present an AFPTAS for SPP with additive factor O( 1 /ε 2 p max ).

Theorem 1. For every accuracy ε there exists an approximation algorithm with running time polynomial in the size of the input |J| and 1 /ε that produces for every instance J of SPP a schedule of length at most (1+ε)OPT(J)+O( 1 /ε 2 p max ).

In practical applications the jobs are usually small compared to the optimum so that an algorithm with a good asymptotic ratio is more applicable than one with a worse absolute ratio. If p max ≤ ε 3 OPT(J) for an instance J, the makespan of the schedule constructed by our algorithm is very close to the optimum (≤ (1 + ε)OP T (J) + O(1/ε 2 p max ) ≤ (1 + cε)OP T (J)) for a constant c ∈ R ≥0 , while an absolute 2 or 3-approximation may be quite far away. To our best knowledge this is also the first result for platform scheduling that takes different speed values among the platforms into account. Since the platforms may have different numbers of processors the AFPTAS in [START_REF] Bougeret | Approximation algorithms for multiple strip packing[END_REF] does not apply for SPP, because it is based on cutting a solution for a single strip and distributing it well-balanced. Additionally, we do not assume that every job fits in every platform. Thus, the algorithm in [START_REF] Bougeret | A fast 5/2approximation algorithm for hierarchical scheduling[END_REF] does also not apply. The algorithm and its analysis are given in Section 2. Since we assign each job to processors of consecutive addresses our algorithm also applies to the generalized MSP. Moreover, in Section 4 we show how our model and the algorithm can be slightly modified to achieve an AFPTAS for scheduling malleable jobs in heterogeneous platforms with different speeds. In Section 5 we give an AFPTAS for SPP with release times. Due to space reduction missing proofs can be found in the appendix.

An AFPTAS for SPP

Our algorithm is based on an LP -relaxation where migration and preemption are allowed. That is a job is allowed to be split into fractions that are executed in different platforms (if they fit). Emanating from the solution of the LP we compute a unique assignment of almost all jobs to the platforms. This is done by skillful rounding the fractions of jobs using a result of Lenstra et al. [START_REF] Lenstra | Approximation algorithms for scheduling unrelated parallel machines[END_REF]; i.e. the number of remaining fractional jobs per platform will be bounded by O( 1 /ε 2 ). Remarkably, the rounding technique needs except an (approximate) solution of the LP no extra information about the speed values. For each platform we reschedule the obtained integral jobs with an approximation algorithm for strip packing [START_REF] Kenyon | A near optimal solution to a two-dimensional cutting stock problem[END_REF] and schedule the fractional jobs behind them. An overview of the algorithm is given in Figure 1.

Algorithm 1

1: Solve a linear program relaxation of the problem (1) and get a fractional schedule where preemption and migration are allowed. 2: Group the fractional jobs corresponding to the LP-solution as described in steps 1-4 in Section 2.2 according their widths and for every platform P ℓ obtain sets L ℓ wide and L ℓ narrow of wide and narrow fractional rectangles, respectively. 3: Via a general assignment problem (2) round the fractional rectangles and obtain sets of rounded rectangles Lℓ wide , Lℓ narrow and fractional rectangles F ℓ for ℓ ∈ {1, . . . , N }. 4: for all ℓ ∈ {1, . . . , N } do 5:

Pack Lℓ wide ∪ Lℓ narrow with the approximation algorithm for strip packing in [14] into platform P ℓ .

6:

Schedule the fractional jobs in F ℓ greedily on top of the schedule corresponding to the packing obtained before. 7: end for

Relaxed Schedule

Let J be an instance of SPP and let T be the makespan of an optimum schedule for J. To simplify the structure of the schedule instead of handling the specific processing times t ℓ j we consider each platform as a two-dimensional bin of width m ℓ and height T s ℓ and schedule the jobs concerning their lengths p j within this bin. Furthermore, we abandon the constraint that a job has to be scheduled nonpreemptively and within only one platform. We represent the schedule of a job J j = (p j , q j ) as a (finite) sequence of pairs (I i , Q i ) i∈I(j) , I(j) ⊂ N, where every I i ⊂ [0, T ] is a time interval and every Q i is a set of processors so that there is a uniquely defined platform P ℓi ∈ {1, . . . , N } with Q i ⊂ M ℓi and |Q i | = q j . Additionally, we assume that the following conditions hold:

(i) the time intervals for job J j within the same platform do not overlap except maybe at the endpoints, i.e. for all ℓ ∈ {1, . . . , N }

i,i ′ ∈I(j),i =i ′ ℓi=ℓ=ℓ i ′ • I i ∩ • I i ′ = ∅, where • A denotes the interior of a set A. (ii) N ℓ=1 s ℓ {i∈I(j)|Qi⊂M ℓ } |I i | ≥ p j (covering constraint
). (iii) at any time for every processor there is at most one job running on it. Keep in mind that under this constraints a job is allowed to be split among the platforms and may be executed in two different platforms at the same time, but never in parallel with itself within the same platform (except for a discrete time, when one piece starts and another ends). It can be executed on two different (not necessary disjoint) subsets of processors within the same platform during different time intervals, where only the endpoints of the time intervals may overlap. An example how such a relaxed schedule can look like is given in Figure 1:

Assume that T = 10/s ℓ1 and job J j needs to be scheduled on q j = 3 processors for p j = 7.5 operations. So in P ℓ1 it is scheduled on processors {7, 8, 9} during time [0, 1/s ℓ1 ] and on processors {2, 3, 4} during time [5/s ℓ1 , 7/s ℓ1 ]. In P ℓ2 it is scheduled on processors {1, 2, 3} during time [0, 3/s ℓ2 ] and in P ℓ3 it is scheduled on processors {3, 4, 5} during time [3.5/s ℓ3 , 5/s ℓ3 ]. This gives 1 + 2 = 3 operations in P ℓ1 , 3 operations in P ℓ2 and 1.5 operations in P ℓ3 (this fulfills the covering constraint). The relaxed schedule can be formulated via the linear T s ℓ1 = 10

P ℓ1 T s ℓ2 P ℓ2 T s ℓ3 P ℓ3 Job J j , p j = 7.5, q j = 3 Fig. 1. Relaxed schedule program below: For each platform in P ℓ , 1 ≤ ℓ ≤ N we introduce configura- tions C ℓ . A configuration C ℓ is a function C ℓ : {1, . . . , n} -→ {0, 1}, so that {j∈{1,...,n}|C ℓ (j)=1} q j ≤ m ℓ .
It tells us which jobs can be scheduled in parallel in platform P ℓ . By definition, the number q(ℓ) of different configurations for P ℓ is bounded by 2 n . Let C ℓ = {C ℓ 1 , . . . , C ℓ q(ℓ) } denote the set of all configurations for a platform P ℓ . In the LP below the variable x C ℓ k indicates the length of configuration C ℓ k . That means that the jobs in {j ∈ {1, . . . , n}|C ℓ k (j) = 1} are executed in platform P ℓ during x C ℓ k operation steps.

q(ℓ) k=1 x C ℓ k = s ℓ T ℓ ∈ {1, . . . , N } N ℓ=1 {k∈{1,...,q(ℓ)}|C ℓ k (j)=1} x C ℓ k ≥ p j j ∈ {1, . . . , n} x C ℓ k ≥ 0 k ∈ {1, . . . , q(ℓ)}, ℓ ∈ {1, . . . , N } (1)
The first N constraints ensure that the makespan C max (ℓ) in each platform P ℓ does not exceed T . The next n constraints are covering constraints for the n jobs. They make sure that every job is executed sufficiently long. We describe how to solve the LP efficiently in the full version of this article.

Lemma 1. If T is the makespan of an optimum schedule for SPP(J), the linear program above (1) is a relaxation of SPP(J).

Rounding the Fractional Solution.

In this section we round the jobs in order to get a unique assignment of every job to a subset of processors of a platform. Consider an approximate solution (x C ℓ k ) of the LP-relaxation. We introduce a new variable x ℓ j ∈ [0, p j ] that indicates the length of the fraction of job J j that is scheduled on P ℓ . Formally this is x ℓ j = {k∈{1,...,q(ℓ)}|C ℓ k (j)=1} x C ℓ k , the sum of the length of all configurations in P ℓ in which J j appears. We can assume for all jobs J j the equality N ℓ=1 x ℓ j = p j , if not we simply delete job J j from appropriate configurations or replace a configuration by two "shorter" configurations (one with job J j and one without, their total length is the same as the one of the original configuration). For all fractions x ℓ j of a platform P ℓ we build rectangles (x ℓ j , q j ) of height x ℓ j and width q j . In the following steps the rectangles of every platform P ℓ are grouped geometrically.

y ℓ y ℓ j,2 H ℓ M 2H ℓ M 3H ℓ M G ℓ 1 G ℓ 2 G ℓ 3
Rectangle (x ℓ j , q j ), a fraction of J j .

Fig. 2. Constructing L ′ℓ wide 1. Choose ε ′ := ε /3 and partition the rectangles into wide and narrow rectangles, L ℓ wide := {(x ℓ j , q j )|q j > ε ′ m ℓ } and L ℓ narrow := {(x ℓ j , q j )|q j ≤ ε ′ m ℓ }. 2. Build a stack of the rectangles in L ℓ wide ordered by non-increasing width. The total height of the stack is denoted with H ℓ . 3. Set M := ( 1 /ε ′2 ). Divide the stack into M groups G ℓ i by drawing M -1 horizontal lines at height iH ℓ /M for i ∈ {1, . . . , M -1} through it. If the interior of a rectangle intersects a horizontal line, cut the rectangle along this line and introduce two new rectangles, so that every rectangle can be assigned to exactly one group. Let L ′ℓ wide denote the modified list of rectangles (see Figure 2). With y ℓ j,i ∈ [0, p j ] we denote the fraction of job j that is assigned to G ℓ i . Let z ℓ j,i = y ℓ j,i/p j ∈ [0, 1] denote the scaled fraction. 4. Compute A(L ℓ narrow ) = (x ℓ j ,qj )∈L ℓ narrow x ℓ j q j and locate the corresponding rectangles on top of the stack as group G ℓ 0 . Let y ℓ j,0 ∈ [0, p j ] denote the fraction of a narrow job J j that is assigned to G ℓ 0 and and let z ℓ j,0 = y ℓ j,0/p j ∈ [0, 1].

If we were able to round the variables z ℓ j,i to integer values {0, 1} (without losing too much), this would imply a unique assignment of every rectangle to exactly one group of a platform. Re-identifying the rectangles with jobs, where we identify the height of a rectangle with the length of a job, this would also imply a unique assignment of every job to a platform. We achieve such a rounding of the variables z ℓ j,i via the following general assignment problem, so that there remain at most M + 1 fractionally assigned rectangles per platform.

n j=1 z ℓ j,0 p j q j ≤ A(L ℓ narrow ) ℓ ∈ {1, . . . , N } n j=1 z ℓ j,i p j ≤ H ℓ M i ∈ {1, . . . , M }, ℓ ∈ {1, . . . , N } N ℓ=1 M i=0 z ℓ j,i ≥ 1 j ∈ {1, . . . , n} z ℓ i,j ∈ [0, 1] (2)
The above formulation is related to the problem of scheduling jobs on parallel unrelated machines with (M + 1)N machines. Each group G ℓ i corresponds to a machine. Lenstra et al. showed in [START_REF] Lenstra | Approximation algorithms for scheduling unrelated parallel machines[END_REF] that a feasible solution (z ℓ i,j ) of this problem can be rounded to a feasible solution (z ℓ i,j ) of the corresponding integer program formulation in polynomial time, so that there remains at most one fractional job zℓ i,j < 1 per machine. Hence, we get a unique assignment of almost all rectangles to the platforms P ℓ except at most M + 1 fractionally assigned rectangles per platform. Let F ℓ denote the set of rectangles with fractional variables zℓ j,i after the rounding. We will execute the corresponding jobs at the end of the schedule; their total processing time is bounded by (M + 1)t max . From now on we consider for each platform P ℓ an instance of strip packing containing a set of wide rectangles Lℓ wide := {(z ℓ j,i p j , q j )|z ℓ j,i = 1, i > 0} and a set of narrow rectangles Lℓ narrow := {(z ℓ j,0 p j , q j )|z ℓ j,0 = 1}. In every platform we repack the pre-assigned rectangles in Lℓ wide ∪ Lℓ narrow using the following strip packing subroutine by Kenyon and Rémila [START_REF] Kenyon | A near optimal solution to a two-dimensional cutting stock problem[END_REF].

Strip Packing Subroutine.

For wide rectangles in Lℓ

wide we generate a list of rounded rectangles Lℓ sup with only a constant number M of different widths w 1 , . . . , w M for the rectangles: We partition the stack of Lℓ wide into M groups by drawing M horizontal lines at height i Hℓ M , i ∈ {0, 1 . . . , M -1}. Thus, we obtain at most M threshold rectangles, i.e. rectangles that intersect either with their lower bounds or with their interiors such a horizontal line. The widths of rectangles between the ith and the (i + 1)th line are rounded up to the width of the ith threshold rectangle, i ∈ {0, 1, . . . , M -1}. For rectangles above the M th line we take the width of the M th threshold rectangle. The main part of the algorithm is to produce a fractional packing for the rectangles in Lℓ sup using a linear program. In doing so we build configurations Cℓ j := {α ℓ ij : w i |i ∈ {1, . . . , M }}, i.e. multisets of widths where αℓ ij denotes the number of rectangles of width w i in Cℓ j and

M i=1 αℓ ij w i ≤ m ℓ .
Then the following LP is solved. min

q ℓ j=1 xℓ j s.t. q ℓ j=1 αℓ ij xℓ j ≥ β ℓ i for all i ∈ {1, .
. . , M } xℓ j ≥ 0 for all j ∈ {1, . . . , q ℓ }.

(

) 3
The variable xℓ j indicates the height of configuration Cℓ j , β ℓ i is the total height of rectangles of width w i in Lℓ sup and q ℓ denotes the number of possible configurations. A feasible solution of the LP corresponds to a fractional strip packing. The fractional packing can be converted into an integral one. Then the narrow rectangles in Lℓ narrow are added in the remaining space next to the integral packing and on top of it with Next Fit Decreasing Height heuristic.

Analysis

In the end we re-identify the rectangles with jobs, i.e. their widths with q j and their heights with p j . Note that a packing of the rectangles of total height h ℓ in platform P ℓ corresponds to a schedule with makespan h ℓ /s ℓ . Then the fractional jobs in F ℓ are scheduled on top. To directly apply strip packing results we scale the widths of all rectangles in Lℓ sup ∪ Lℓ narrow by 1 /m ℓ . Furthermore we consider platform P ℓ as a strip of width 1 and infinite height. As we consider each platform and the allocated jobs independently, this has no impact on the solution.

Analyzing the Output

Let (x C ℓ k ) be an approximate solution of (1) and let Lℓ wide ∪ Lℓ narrow contain the rectangles that have to be repacked in Step 5 of Algorithm 1 with the strip packing subroutine above. For a list of rectangles L let Lin SP (L) denote the height of an optimal fractional strip packing for the rectangles in L. By construction we have that the height of an optimal fractional strip packing for the wide and narrow rectangles in L ℓ wide ∪ L ℓ narrow into platform P ℓ , is less than the length of the schedule corresponding to the approximate solution of (1) constructed in step 1, that is Lin SP (L ℓ wide ∪ L ℓ narrow ) ≤ s ℓ (1 + 3ε)Lin(J). Let "≤" denote a partial order on lists of rectangles. For a list of rectangles L let S denote the shape of a stack built as described above. We say L ≤ L ′ for two lists of rectangles, if shape S ′ covers S. It is clear that Lin SP ( Lℓ wide ) ≤ Lin SP ( Lℓ sup ), since Lℓ wide ≤ Lℓ sup . With Lemma 3 in [START_REF] Kenyon | A near optimal solution to a two-dimensional cutting stock problem[END_REF] we conclude Lin SP ( Lℓ

sup ) ≤ 1 + 1 M ε ′ Lin SP ( Lℓ wide ) and A( Lℓ sup ) ≤ 1 + 1 M ε ′ A( Lℓ wide )
. We go on with step 2 and consider the stack built from L ′ℓ wide in the 3rd step of the grouping procedure in Section 2.2. We introduce a new list of rectangles L ′ℓ sup that is developed when in each group G ℓ i of the stack, i ∈ {1, . . . , M }, the width of each rectangle is rounded up to the widest width of a rectangle that is contained in this group. Remember that every rectangle in L ′ℓ wide is uniquely assigned to one of the groups G ℓ i since we introduced two new rectangles for border rectangles before. Notice that during building Lℓ wide in step 3 of Algorithm 1 we do not increase the total height of any group G ℓ i and we do not exceed the largest width of a rectangle that appears in it. Thus, we obtain Lℓ wide ≤ L ′ℓ sup . Since Lin SP (L ′ℓ wide ) = Lin SP (L ℓ wide ) and A(L ′ℓ wide ) = A(L ℓ wide ) this gives:

Lemma 2. For all ℓ ∈ {1, . . . , N } we have a) Lin SP ( Lℓ

sup ) ≤ 1 + 1 M ε ′ 2 Lin SP (L ℓ wide ) b) A( Lℓ sup ) ≤ 1 + 1 M ε ′ 2 A(L ℓ wide ).
Let h ℓ sup denote the height of the packing produced by converting the fractional solution of (3) into an integral one. This is done by adding for each configuration appearing with height > 0 in the fractional solution the maximum height of a rectangle. Each basic solution of (3) has at most M non-zero entries and one can show that there are effectively at most 2M different configurations in platform P ℓ [START_REF] Kenyon | A near optimal solution to a two-dimensional cutting stock problem[END_REF]. So we conclude h ℓ sup ≤ Lin SP ( Lℓ sup ) + (1 + 2M ) max{p j |(p j , q j ) ∈ Lℓ sup }. Note that we only packed the rounded rectangles in Lℓ sup so far. Let h ℓ denote the height after adding the narrow rectangles in Lℓ narrow to platform P ℓ , ℓ ∈ {1, . . . , N }. We can now bound h ℓ : Lemma 3. For all ℓ ∈ {1, . . . , N } we have

h ℓ ≤ (1 + 7ε)Lin(J)s ℓ + O( 1 /ε 2 ) max{p j |(p j , q j ) ∈ L ℓ wide ∪ L ℓ narrow }.
The packing in each platform P ℓ corresponds to a schedule with length (referring to p j ) at most (1 + 7ε)Lin(J)s ℓ + ( 36 ε 2 + 1) max{p j |(p j , q j ) ∈ L ℓ wide ∪ L ℓ narrow }, thus we conclude that its completion time (referring to t ℓ j ) is bounded by (1 + 7ε)Lin(J) + O( 1 ε 2 t max ). The remaining jobs in F ℓ have total processing time bounded by (M + 1)t max ∈ O( 1 ε 2 t max ) ≤ O( 1 ε 2 p max ), since t max ≤ p max as min s ℓ = 1. Adding now the remaining jobs in F ℓ to the schedule does not change the magnitude of the additive factor. With rescaling ε and since Lin(J) ≤ OPT(J) we obtain that the makespan of the produced schedule in each platform P ℓ is less than C max (ℓ) ≤ (1 + ε)OPT(J) + O( 1 ε 2 p max ) and conclude our main Theorem 1. Since during the repacking process we considered jobs as rectangles, we assigned every job to a set of processors with consecutive addresses. Thus we also obtain an AFPTAS for multiple strip packing for strips with different widths (in this case we have s ℓ = 1 for all ℓ ∈ {1, . . . , N }).

Running Time of the Algorithm

The time needed for solving [START_REF] Bougeret | Approximation algorithms for multiple strip packing[END_REF] approximately via max-min resource sharing (details in the full version)in step 1 is

O(N n 2 ε -6 log 2 (n) log 2 (1/ε) log(N max s ℓ )).
The number of non-zero configurations in the final solution is bounded by

O(n(ε -2 + ln n)) [15]. So step 2 takes time O(N n 2 (ε -2 + log n) log(n 2 (ε -2 + log n)) = O(N n 2 ε -2 log 2 (n) log(1/ε))
, since there are at most n 2 (ε -2 + log n) rectangles in each platform that have to be sorted. We represent the assignment problem in step 3 as a weighted bipartite graph G = (V 1 , V 2 , E), where V 1 corresponds to the N (M + 1) machines (parts of the stacks), V 2 to the jobs. There is an edge between the node representing part i of the stack for P ℓ and the node representing job J j if z ℓ j,i > 0. This assignment problem can be converted in time O

(|E||V 1 |) = O(|V 1 | 2 |V 2 |) = O(ε -2 N 2 n) into
another assignment problem, whose corresponding graph is a forest [START_REF] Plotkin | Fast approximation algorithms for fractional packing and covering problems[END_REF]. Applying the rounding technique in [START_REF] Lenstra | Approximation algorithms for scheduling unrelated parallel machines[END_REF] to the new assignment takes time in

O(|V 1 | + |V 2 |) = O(ε -2 N + n). So step 3 takes time in O(ε -2 N 2 n).
In step 5 it is sufficient to solve the corresponding linear program (3) approximatively with accuracy ε also via a max-min resource sharing problem. This can be done in time O(M (ε -2 + ln M ) ln(ε -1 ) max{M + ε -3 , M ln ln(M ε -1 )}) for every platform [START_REF] Jansen | Approximation algorithms for min-max and max-min resource sharing problems and applications[END_REF]. Since M ∈ O(ε -2 ) this gives for step 5 a total running time in O(N ε -7 ). The overall running time sums up to O(ε -7 N 2 n 2 log 2 (n) log 2 (1/ε) log(N max s ℓ )).

Malleable Jobs

One can also obtain an AFPTAS for scheduling malleable jobs non-preemptively by only adding a few modifications to the algorithm. To get a better overview we do not consider the platform speeds here. But remember that one can easily add speeds here by considering bins of height s ℓ T instead of T , where T denotes an optimum value for the makespan for scheduling malleable jobs in platforms. In the following we give a short instruction how to adjust our algorithm: In malleable scheduling a job J j is described by a function p j : {1, . . . , m N } -→ Q + ∪ ∞, where p j (k) is the length of job j running on k parallel processors of a platform. We introduce a configuration as a map f ℓ : {1, . . . , m ℓ } -→ {0} ∪ {1, . . . , n} that assigns a processor to a job (0 for idle time). Instead of solving (1) we can solve in a similar way the following linear program:

f ℓ ∈F ℓ x f ℓ = T ℓ ∈ {1, . . . , N } N ℓ=1 m ℓ k=1 1 p j (k) f ℓ ∈F ℓ ,|f -1 (j)=k| x f ℓ ≥ 1 j ∈ {1, . . . , n} x f ℓ ≥ 0. (4)
Consider step 2 of the algorithm. Let a ℓ i , b ℓ i be the smallest and the largest width of a rectangle in group G ℓ i and let W ℓ i,j be the set of widths job J j adopts in G ℓ i . To guarantee that we have chosen the right number of processors for a job we add the following steps before rounding the jobs via the general assignment problem:

-For i ∈ {1, . . . , M } and w ∈ W ℓ i,j let y ℓ j,i (w) denote the fraction of job j of width w that is assigned to G ℓ i . Let z ℓ j,i = w∈Wi,j y ℓ j,i (w) be the complete fraction of job j in G ℓ i . -For each part i ∈ {1, . . . , M } and job j with |W ℓ j,i | ≥ 2 compute k ℓ j,i := arg min k∈[a ℓ i ,b ℓ i ] p ℓ j (k) and replace the rectangles corresponding to job j in G ℓ i by (z ℓ j,i p j (k ℓ j,i )k ℓ j,i ). Note that p j (k ℓ j,i ) is the smallest processing time among all processor numbers k ∈ [a ℓ i , b ℓ i ]. -For each job j with |W ℓ j,0 | ≥ 2 compute k ℓ j,0 := arg min k∈[0,ε ′ m ℓ ] p ℓ j (k)k and replace all rectangles corresponding to job j in G ℓ 0 by (z ℓ j,0 p j (k ℓ j,0 ), k ℓ j,0 ).

Including different speed values we define the processing time of job J j in platform P ℓ as t ℓ j (k) = pj (k) s ℓ . Note that t ℓ j (k) = ∞ is possible. We define p max := max j,k {p j (k)|p j (k) < ∞} and t max := max j,k,ℓ {t ℓ j (k)|t ℓ j (k) < ∞}. To include speed values in the linear program we change the first N constraints of LP (4) into ... = s ℓ T , since different speeds can be considered as providing length s ℓ T instead of T for the schedule. During the repacking process the algorithm remains the same and finally we achieve the following theorem Theorem 2. There is an AFPTAS for scheduling non-preemptive malleable jobs in heterogeneous platforms with different speeds with additive factor O( 1 /ε 2 p max ).

Release Times

Theorem 3. There is an AFPTAS for scheduling parallel jobs in heterogeneous platforms with different speeds and release times with additive factor O(1/ε 3 p max ).

For a better overview we describe here the idea for the proof when all platforms run with the same speed, i.e. s ℓ = 1 for all ℓ ∈ {1, . . . , N }. The general case can be derived from it. Let r j denote the release time of job J j and Φ := max j r j . We assume that Φ > εT , otherwise it is easy. As in [START_REF] Hall | Approximation Schemes for Constrained Scheduling Problems[END_REF] we round down the release times to the next multiples of iεT i ∈ {0, 1, . . . , 1/ε} and obtain new release times r1 . . . , rn with at most R = O(1/ε) different values ρ 1 , . . . , ρ R . To recover the loss we made by rounding down we shift the final schedule by εT in the end. For every platform P ℓ we consider R new platforms Pℓ,i , i ∈ {1, . . . , R}, with m ℓ processors and create a new instance JR of SPP (without release times) with RN platforms and n jobs. A job J j can now be scheduled in platform Pℓ,i if it fits and if it is already released, i.e. q j ≤ m ℓ and rj ≤ ρ i . For each of the new platforms Pℓ,i the value of an optimal fractional schedule is at most εT .

⋆ Research supported by German Research Foundation (DFG) project JA612/12-1, "Design and analysis of approximation algorithms for two-and three-dimensional packing problems", and DGA-CNRS


Marin Bougeret
email: bougeret@imag.fr

Pierre-François Dutot
email: pfdutot@imag.fr

Klaus Jansen

Christina Otte

Denis Trystram
email: trystram@imag.fr

A fast 5/2-approximation algorithm for hierarchical scheduling

We present in this article a new approximation algorithm for scheduling a set of n independent rigid (meaning requiring a fixed number of processors) jobs on hierarchical parallel computing platform. A hierarchical parallel platform is a collection of k parallel machines of different sizes (number of processors). The jobs are submitted to a central queue and each job must be allocated to one of the k parallel machines (and then scheduled on some processors of this machine), targeting the minimization of the maximum completion time (makespan). We assume that no job require more resources than available on the smallest machine. This problem is hard and it has been previously shown that there is no polynomial approximation algorithm with a ratio lower than 2 unless P = N P . The proposed scheduling algorithm achieves a 5 2 ratio and runs in O(log(npmax)knlog(n)), where pmax is the maximum processing time of the jobs. Our results also apply for the Multi Strip Packing problem where the jobs (rectangles) must be allocated on contiguous processors.

Introduction

Context and motivation. The evolution of the technology over the last past years leads to the emergence of new types of parallel and distributed platforms. Many of these new computing systems are hierarchical in nature. Such computing systems may be composed of several parallel machines, each having a certain number of processors, or composed of several clusters, each having a certain number of computers [START_REF] Foster | The anatomy of the grid: Enabling scalable virtual organizations[END_REF]. Thus, we make no distinctions between machines/clusters on one side, and between processors/computers on the other side.

In order to fully exploit the large number of available resources for reaching the best performances, we need to revisit the classical resource management algorithms taking into account new features induced by the hierarchical hardware. In such platforms, the users submit their jobs in a centralized queue. The resource manager selects the jobs and allocates them to a machine, and then the jobs are scheduled locally. We assume in this work that the machines have enough processors so as each job fits entirely in any machine. Notice that jobs are not executed on processors that belong to different machines.

In the common context of an execution by successive batches, we target on the minimization of the makespan (defined as the maximum completion time over all the processors) which is the most popular objective function [START_REF] Feitelson | Theory and practice in parallel job scheduling[END_REF]. We assume that the processing times of the jobs are available at the beginning (the algorithm is clairvoyant [START_REF] Feitelson | Theory and practice in parallel job scheduling[END_REF]).

Related works. Let us qualify by regular, the case where the machines have the same number of processors. The irregular case corresponds to the situation where the machines have different sizes.

There exist a lot of related works for the regular case, as it is closely related to the multiple strip packing problem. Indeed, the only difference is that in multiple strip packing (MSP), the jobs are considered as rectangles and thus, they must be allocated on "consecutive" processors. This problem (and the non-contiguous version) are strongly N P -hard, and Zhuk [START_REF] Zhuk | Approximate algorithms to pack rectangles into several strips[END_REF] (and later Schwiegelshohn et al. [START_REF] Schwiegelshohn | Online scheduling in grids[END_REF]) showed that there is no approximation algorithm with absolute ratio better than 2 unless P = N P , even for 2 machines. The proof is a gap reduction from 2-partition problem. The main related positive results for MSP are a 2 + ε-approximation in [START_REF] Ye | On-Line Multiple-Strip Packing[END_REF] whose cost is doubly exponential in 1 ǫ , a (costly) 2-approximation and an AFPTAS in [START_REF] Bougeret | Approximation algorithm for multiple strip packing[END_REF]. Some variants have been investigated (like in [START_REF] Pascual | Cooperation in multi-organization scheduling[END_REF]) where additional constraints come from pre-allocation.

Concerning the hierarchical scheduling problem in the irregular case, one of the most relevant work is the result of Schwiegelshohn, Tchernykh and Yahyapour [START_REF] Schwiegelshohn | Online scheduling in grids[END_REF]. The authors address a version of this problem where a job may not fit everywhere, meaning that a job may requires more processors than the total number of processors of some machines. They provide a 3-approximation for the off-line case, and a 5-approximation when the jobs are submitted over time (on-line). Their algorithms handle non-clairvoyant jobs (meaning that the processing time of a job is only known at the end of its execution), but do not easily apply for MSP. They also emphasize that the performance of the classical Garey and Graham's list scheduling algorithm is significantly worsened in hierarchical environments. Finally, (as we will see in remark 4), it is possible to derive a better approximation ratio using the remark in [START_REF] Ye | On-Line Multiple-Strip Packing[END_REF] that leads to a 2 + ǫ ratio (in time polynomial in 1 ǫ ) for the regular case. However, the cost of the induced algorithm is considerably too large, for instance taking ǫ = 1 2 leads to a cost in Ω(n 60 )! Contribution. Our main contribution is a new 5 2 -approximation (almost) greedy algorithm (called F AHS for fast approximation hierarchical scheduler) for scheduling a set of (clairvoyant) rigid jobs on parallel machines that have different num-ber of processors, and where every job fits everywhere. The algorithm runs in O(log(np max )knlog(n)). This result also applies for MSP.

Preliminaries

Problem statement

The problem studied in this paper is to schedule n jobs on a parallel system composed of k parallel machines. Machine M i (for 1 ≤ i ≤ k) has m i processors. We assume that m i ≤ m i+1 for any i. A job J j is characterized by the number of processing resources needed for its completion, denoted by q j ∈ N * (sometimes called the degree of parallelism) and its corresponding processing time p j ∈ N * . The q j processors must be allocated on the same machine. We assume that every jobs fits everywhere, meaning that max j q j ≤ m 1 . We denote by w j = p j q j the work of job J j . The objective is to minimize the maximum completion time over all the machines (called the makespan and denoted by C max ). Given a fixed instance, we denote by C * the optimal makespan for this instance.

Other notations

Given a schedule, we denote by u i (t) the utilization of M i at time t, which is the sum of the required number of processors of all the jobs that are running on M i at time t. We say that job J j1 is higher than job J j2 if q j1 ≥ q j2 . We extend the p j , q j , w j previous notations to P (X), Q(X) and W (X) where X is a set of jobs and the capital letter denotes the sum of the corresponding quantity of all the jobs in the set (for instance P (X) = Σ Jj ∈X p j ).

We call shelf a set of jobs that are scheduled on the same machine and finish at the same time. Scheduling a shelf at time t means that all the jobs of the shelf finish at time t. This reverse definition of shelf (where usually jobs start simultaneously) is used because some machines are filled from right to left. Using v as a guess for the optimal makespan C * , let L = {J j |p j > v 2 } denote the set of long jobs, and let H i = {J j |q j > mi 2 } denote the set of high jobs for M i , for 1 ≤ i ≤ k.

Useful results

We present briefly in this section some classical results that we will use later. Let us recall first the well known Highest First (HF ) list algorithm that, given a set of jobs and one machine, starts from time 0 and schedules at any time the highest job which fits. Secondly, let us state the following result that was established by Steinberg [START_REF] Steinberg | A strip-packing algorithm with absolute performance bound 2[END_REF]. Notice that even if this result is stated in term of rectangle packing, it remains valid for parallel jobs (without the contiguous constraint).

Theorem 1 ([8]

). Let L = {r 1 , . . . , r n } be a set of rectangles. Let w j , h j and s j denote the width, the height and the surface of r j . Let S(L) = Σ n j=1 s j , w max = max j w j and h max = max j h j . If

w max ≤ u, h max ≤ v and 2S(L) ≤ uv -max(2w max -u, 0)max(2h max -v, 0)
then it is possible to pack L (in time O(nlog 2 (n)/log(log(n))) in a rectangular box of width u and height v.

We are now ready to describe the F AHS algorithm.

Algorithm

As we target a 5/2 ratio, it is convenient to consider that we have in each machine an empty available rectangular area of height m i and length 5C * /2. Moreover, we want to particularly take care of the jobs that have a processing time greater than C * /2, since these jobs are harder to schedule. As C * is unknown, we use the classical dual approximation technique [START_REF] Hochbaum | A polynomial approximation scheme for scheduling on uniform processors: Using the dual approximation approach[END_REF], and we denote by v the current guess of C * . According to this technique, our goal is to provide the F AHS (Fast Approximation Hierarchical Scheduler) algorithm that either schedules all the jobs with a makespan lower than 5v/2 or rejects v, implying that v < C * . For the sake of simplicity, we do not mention in the algorithm the "reject" instruction. Thus, we consider throughout the paper that v ≥ C * , and it is implicit that if one of the claimed properties is wrong during the execution, the considered v should be rejected.

F AHS is described in detail in Algorithm 1. The principle is to fill the machines from the smallest (M 1 ) to the largest one. As long as it is possible, we aim at scheduling on each M i a set of jobs whose total work is greater than m i v. The algorithm is designed such that the only reason for failing (meaning that it does not reach m i v) is the lack of jobs. Thus, if a failure occurs, there will be only a few amount of jobs that will be straightforward to schedule.

In order to schedule a work of (at least) m i v, we first intent to schedule a set X of jobs of H i such that P (X) is greater than 2v (phase 1). If it fails, we schedule as many jobs of H i as possible (again in phase 1), with a strict limit P (X) < 3v/2 to have enough space to pack a shelf of long jobs between 3v/2 and 5v/2. Then, we select (in phase 2) some jobs of I\H i , targeting a total work of at least m i v.

These selected jobs are then scheduled in phase 3. If the work goal m i v is reached we schedule the considered jobs in M i (using the add algorithm in Algorithm 2 in case 1 or HF in case 2), otherwise (case 3) there is by construction only a few amount of unscheduled jobs, and they are scheduled using the pack procedure described in Algorithm 3.

Remark 1 (Notation). For any set X considered in the algorithm or in the proof, we use the X notation to denote the set X during the execution of the algorithm ( X ⊂ X). We consider that a job is removed from the instance when it is scheduled.

Algorithm 1 Fast Approximation Hierarchical Scheduler (F AHS)

for all i, Hi ← Hi and L ← L

for i = 1 to k do ---------------phase 1 --------------- if Hi ∩ L = ∅ then • Jj i ← highest job of Hi ∩ L • schedule Jj i at time 0 and remove it from Hi ∩ L else • Jj i ← "dummy" job (with pj i = qj i = 0) end if if pj i + P ( Hi \ L) ≥ 2v then • target ← 2v else • target ← v end if
• schedule sequentially (in any order) jobs of Hi \ L (and remove them from Hi) until one of them ends later than target or until ( Hi \ L = ∅) • High ← jobs scheduled on Mi • reschedule jobs of High in non-increasing order of height

if target = v then ---------------phase 2 --------------- • Select ← ∅
• add to Select some jobs of Ĩ \ Hi (and remove them from Ĩ) in non increasing order of their work, until (W (High) + W (Select) ≥ miv) or until ( Ĩ \ Hi = ∅) ---------------phase 3 --------------if W (High) + W (Select) > 5 4 miv then //case 1 • schedule Select using add(i, Select) else if 5 4 miv ≥ W (High) + W (Select) ≥ miv then //case Proof. Phase 1 and phase 2 run in O(nlog(n)) as the jobs are sorted according to their height at the end of phase 1 and according to their work before starting the phase 2. Phase 3 runs in O(nlog(n)) because of the HF algorithm. Thus, for a fixed value of v, the cost of F AHS is in O(knlog(n)), and the dichotomic search on v can be done in log(np max ) since np max is an upper bound of the optimal.⊓ ⊔

Analysis of the algorithm

Notice first that the case where target = 2v is clear as in this case the schedule has a makespan lower than 5v 2 , and the scheduled work is greater than 2v mi 2 = m i v. Thus, we will focus on the second part of F AHS, where target = v. We will first prove in lemma 1, 2 and 3 that (if v ≥ C * , as usual) it is possible to schedule the considered set of jobs with a makespan lower than 5v 2 in the three cases of phase 3. Then, the final proof of F AHS is derived in theorem 2.

Lemma 1 (Feasibility of case 1). Any call to add(i, Select) produces a valid schedule of makespan lower than 5v 2 .

Proof. Notice first that calling the add procedures implies that target = v. We assume that the sets High and Select have been constructed in phase 1 and 2, implying W (High) + W (Select) > 5 4 m i v. Let p = |Select| and Select = {J ′ 1 , . . . , J ′ p }, with w ′ j+1 ≤ w ′ j for all j, as stated in Algorithm 1. Let us start with the following properties:

1) P (High) ≤ 3 2 v 2) for all J ′ j ∈ Select, w ′ j > miv 4 , implying J ′ j ∈ L and 0 ≤ p ≤ 4 3) ∀X ⊂ Select, W (High) + W (Select \ X) < vm i
The first property is true because target = v, and the jobs of High scheduled in phase 1 have a processing time lower than v 2 . The second point comes from the fact that W (Select \ {J ′ p }) < m i v and W (Select) > 5 4 m i v. This implies that w ′ p > miv 4 and property 2. The third point is true by definition of phase 2. We start by creating a shelf Sh with the higher jobs of Select (as depicted figure 1). We schedule Sh at time 5v 2 (remind that it means that all the jobs of Sh finish at time 5v 2 ), which is possible according to property 1. Let α denote the number of jobs in this shelf. As Select ∩ H i = ∅, we know that α ≥ 2, implying that cases where p ≤ 2 are straightforward.

We now study the cases where p = 3. Let J 1 be the remaining job (we use the same notations as in Algorithm 2). Let us now analyze how the add procedure schedules J 1 . Let us suppose by contradiction that J 1 intersects Sh.

Let t ′ 1 = 5v 2 -t 1 -p 1 . We get W (High ∪ Sh) > t 1 (m i -q 1 ) + t ′ 1 (m i -q 1 ) + (Q(Sh) -(m i -q 1 )) v 2 > t 1 (m i -q 1 ) + ( 3v 2 -t 1 )(m i -q 1 ) + (3q 1 -m i ) v 2 = m i v
0000 0000 0000 0000 1111 1111 1111 1111 0000 0000 0000 0000 1111 1111 1111 1111 0000 0000 0000 0000 1111 1111 1111 1111 00000 00000 00000 00000 11111 11111 11111 11111 0 0 1 1 The inequality Q(Sh) ≥ 2q 1 used above is true since add schedules the highest jobs in the shelf. The inequality W (High ∪ Sh) > m i v is a contradiction according to property 3, implying that J 1 must fit in the "staircase".

0 0 0 0 0 1 1 1 1 1 t 1 v 2v Sh J 2 J 1 high t ′ 1 2v v 3v 2 J 1
Let us now study the case where p = 4. Let Select ′ = Select \ {J ′ 4 }. We have W (Select ′ ) > 3 miv 4 (according to property 2), implying W (High) + 3 miv 4 < W (High∪Select ′ ) ≤ vm i . Thus, we get P (High) mi 2 < W (High) < miv 4 , leading to P (High) < v 2 . Thus, the second shelf sh ′ scheduled at time 3v 2 does not intersect jobs of High. It ends the proof of feasibility of case 1. ⊓ ⊔

Concerning the feasibility of case 2, we prove a slightly more general statement which can be interpreted as a particular case of Steinberg's theorem [START_REF] Steinberg | A strip-packing algorithm with absolute performance bound 2[END_REF].

Lemma 2 (Feasibility of case 2). Let us consider an arbitrary machine M with m processors. Let v such that for all j ∈ X, p j ≤ v. Let X be a set of jobs such that W (X) ≤ αmv, with α ≥ 1. Then, the HF algorithm schedule X on M with a makespan lower than 2αv.

Proof. Let C denote the makespan of the schedule, and let J j0 be a job that finishes at time C. If q j0 > m 2 , then all the jobs J j of X have q j > m 2 , implying αmv ≥ W (X) > C 2 m. Let us suppose now that q j0 ≤ m 2 . Let s denote the starting time of J j0 . As there are strictly less than q j0 available processors between time 0 and s, we have W (X) > p j0 q j0 + s(mq j0 ), implying s < W (X)

m-qj 0 - pj 0 qj 0 m-qj 0 . Thus, C ≤ s + p j0 ≤ W (X) m -q j0 + p j0 m -2q j0 m -q j0 ≤ v (α + 1)m -2q j0 m -q j0
As the last expression is an increasing function of q j0 and q j0 ≤ m 2 we get C ≤ 2αv.⊓ ⊔ Remark 3. Notice that Lemma 2 does not apply for strip packing. However this lemma can be simply adapted using Steinberg algorithm [START_REF] Steinberg | A strip-packing algorithm with absolute performance bound 2[END_REF], as explained in Section 5

We now study the feasibility of case 3.

Lemma 3 (Feasibility of case 3). The pack procedure schedules all the remaining jobs.

0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 v 2v J 8 J 9 J 7 J 10 J 11 v 2v J 5 J 12 J 13 H1 i Σ 4 j=1 w j < m 2 v Σ 5 j=1 w j ≥ m 2 v p 12 + p 13 ≤ 3v 2 Σ 11 j=7 q j ≤ m 4 + m 5 J 2 J 1 J 3 J 4 M 2 M 1 M 3 M 5 M 4
Fig. 2. Example for the pack procedure. Case 3 occurs for i = 3. H1 i is defined as in Lemma 3.

Proof. Let i be the index of the current machine when case 3 occurs for the first time. Let H0

i be Hi at line 7 of phase 1 (after setting the value of J ji ) and let H1

i be Hi at the beginning of phase 3. Notice that W (High ∪ Select) < m i v implies that we collected all the jobs of Ĩ \ H1 i , and thus the set of jobs that have not been scheduled on {M 1 , . . .

, M i-1 } is High ∪ Select ∪ H1 i . If i = k, then W (High ∪ Select ∪ H1 i ) ≤ vm i (otherwise, v is
rejected), and HF is sufficient according to lemma 2. We consider now that i < k. Jobs of High ∪ Select are scheduled (on M i ) with a makespan lower than 5v 2 using again lemma 2. We now prove that pack(i, H1 i ) successfully schedules H1 i . If H1 i ∩ L = ∅, it implies that H0 i \ L = H0 i , and thus P ( H1 i ) ≤ P ( H0 i ) ≤ 2vp ji ≤ 2v because phase 3 only occurs if target = v. Thus, we can schedule H1

i sequentially on M i+1 .

If H1

i ∩ L = ∅, then there is one job of H i ∩ L scheduled on M 1 , . . . , M i . Moreover, P ( H1 i \ L) ≤ P ( H0 i \ L) ≤ 3v 2 as there was not enough jobs to fill M i up to 2v. We will prove that pack(i, H1 i ) can schedule H1 i ∩ L on machines {M i+1 , . . . , M k } such that no job (of H1 i ∩ L) is scheduled after time v on M k . Then, it will be obvious that H1

i \ L can be added on M k between v and 5v 2 . Let us prove it by contradiction by assuming that there is a job of H1 i ∩ L scheduled on machine M k after time v (meaning that we stared a second shelf of jobs of H1 i ∩ L on M k ). For any t ∈ [|1, . . . , k|], let S t denote the schedule constructed by F AHS on machine M t , and S * t be the schedule (for a fixed optimal solution) on machine M t . Let X = ∪ i t=1 S t and X * = ∪ i t=1 S * i . We have Q(X ∩H i ∩L) ≥ Q(X * ∩H i ∩L) as in phase 1 we scheduled on machines M 1 . . . M i the i highest jobs of H i ∩ L (called the J jt in the algorithm), and the optimal cannot schedule more than i jobs of H i ∩ L on these machines. Moreover, we have Q(S t ∩ H i ∩ L) > m t for every t in [|i + 1, k|] as we started a second shelf on each of these machines. Thus, it means that Q( H1 i ∩ L) > Σ k t=i+1 m t which is impossible as the optimal solution had a total height of jobs of H i L greater than Q( H1 i ∩ L) to schedule on M i+1 , . . . , M k . ⊓ ⊔

We can now complete the main proof.

Theorem 2. If v ≥ C * , F AHS schedules all the jobs with a makespan lower than 5v 2 .

Proof. If case 3 of phase 3 occurs, then we know according to lemma 3 that all the remaining jobs are scheduled in 5v 2 . Otherwise, we know that for every i ∈ [|1, . . . , k|], the F AHS algorithm had a target equal to 2v, or executed case 1 or case 2. This implies by construction that the area scheduled on M i is greater than (and in this case exactly equal to) m i v. Thus, there can not be unscheduled jobs at the end.⊓ ⊔

Concluding remarks

In this paper, we presented a new algorithm for scheduling a set of clairvoyant rigid jobs in a hierarchical parallel platform, assuming that every job fits in any machine. A sophisticated analysis proved that it is a 5 2 -approximation, improving the best existing algorithm. There exists for this problem a lower bound equal to 2.

We now explain how to adapt the algorithms and the proofs to the MSP problem where jobs, called rectangles, must be allocated on contiguous processors. The only adaptation needed is in Lemma 2, where HF can be directly replaced by Steinberg's algorithm (see Section 2.3). Phase 1, pack and add build contiguous schedule (and thus a valid schedule for rectangles), and proofs of Lemma 1 and 3 still hold for the contiguous case. Thus, we get a 5 2 -approximation algorithm for MSP that runs O(log(np max )knlog 2 (n)/log(log(n)).

We describe now how to achieve a 2 + ǫ ratio for this problem at the price of a much higher algorithm complexity. This result is an extension of the result in [START_REF] Ye | On-Line Multiple-Strip Packing[END_REF] that was established for the regular case.

Remark 4. There is a 2+2ǫ-approximation that runs in O(nlog 2 (n)/log(log(n))f (k, n, ǫ)) where f (k, n, ǫ) is the complexity of any 1+ǫ algorithm for the Q||C max problem with k machines and n jobs (for example f (ǫ) = O(kn 10 ǫ 2 ) using [START_REF] Hochbaum | A polynomial approximation scheme for scheduling on uniform processors: Using the dual approximation approach[END_REF]).

Proof. We follow here the same idea as in [START_REF] Ye | On-Line Multiple-Strip Packing[END_REF]. Let I denote the instance of the irregular hierarchical problem (where every job fits everywhere). We define an instance I ′ of the Q||C max problem as follows. For each job J J of I we associate a job J ′ j of I ′ of processing time p ′ j = w j . For each machine M i of I ′ we associate a machine M ′ i of I ′ whose speed is m i . Then, we apply a P T AS (and get a schedule S ′ ≤ (1 + ǫ)Opt(I ′ )) on I ′ . The schedule gives a partition of the jobs of I among the different machines. Let X ′ i denote the set of jobs scheduled on M ′ i in S ′ , and let X i denote the corresponding set of jobs (meaning the jobs of same index) in I. Let c ′ i denote the completion time on M ′ i . We create the schedule S of I as follows. According to the Steinberg's theorem (see Section 2.3), we know that for each i the set X i can be scheduled in a "box" (created on machine M i ) of size

m i × 2c ′ i as c ′ i = W (X ′ i ) mi = W (Xi)
mi . Thus, the makespan of S is lower than 2max i c ′ i ≤ 2(1 + ǫ)Opt(I ′ ) ≤ 2(1 + ǫ)Opt(I).

A natural (but hard) question is to fill the gap between the new approximation ratio 5 2 and the lower bound with a low cost algorithm.

Fig. 1 .

 1 Fig. 1. Example for the add procedure. Case where p = 3 is depicted on the left side, and case where p = 4 is depicted on the right side.

  Let us now quickly analyze the running time of F AHS.Remark 2. F AHS runs in O(log(np max )knlog(n)).

	jobs from
	Hi)
	end if
	• break //all the jobs are scheduled
	end if
	end if
	end for

2 • reschedule jobs High ∪ Select on Mi using HF algorithm else //case 3 if i=k then • reschedule High ∪ Select ∪ Hi on Mi using HF algorithm (and remove jobs from Hi) else • reschedule High ∪ Select on Mi using HF algorithm • schedule Hi on {Mi+1, . . . , M k } using pack(i, Hi) (and remove

⋆ M. Bougeret has a PhD grant from DGA-CNRS. ⋆⋆ Research supported by German Research Foundation (DFG) project JA 612/12-1, "Design and analysis of approximation algorithms for 2D and 3D packing problems".

Algorithm 2 add(i, Select)

• create a shelf Sh with the highest jobs of Select and schedule Sh at time 5v 2

• reschedule Sh such that the shortest jobs are on the top (as depicted figure 1)

• create a shelf Sh ′ using J1 and J2 and schedule

• add to Sh a job Jj from Hi ∩ L end while • schedule all the jobs of Sh \ {Jj} at time 0 if Q(Sh) > mx then

• schedule Jj at time v else

• schedule Jj at time 0 end if end while • schedule all the remaining jobs (which all belong to Hi \ L) sequentially on M k from v end if


Marin Bougeret
email: bougeret@imag.fr

Pierre-Francois Francois Dutot
email: dutot@imag.fr

Klaus Jansen

Christina Otte

Denis Trystram
email: trystram@imag.fr

Approximation Algorithm for Multiple Strip Packing

Keywords:

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

In this paper we study the Multiple Strip Packing (MSP) problem, a generalization of the well-known Strip Packing (SP) problem. For a given set of rectangles, r 1 , . . . , r n , with heights and widths ≤ 1, the goal is to find a non-overlapping orthogonal packing without rotations into k ∈ N strips [0, 1] × [0, ∞), minimizing the maximum of the heights. As much as Strip Packing, its generalization Multiple Strip Packing is not only of theoretical interest, but also has many applications to real-world problems as in computer grids, server consolidation and in cutting problems. In computer grids for example, MSP is related to the problem of finding a schedule for parallel tasks into different clusters of processors with minimum makespan [START_REF] Schwiegelshohn | Online scheduling in grids[END_REF]. Consider an instance L = {r 1 , . . . , , r n } of MSP. The value k always denotes the number of strips S 1 , . . . , S k . For i ∈ {1, . . . , k} the value h i denotes the height of a feasible packing in strip S i . For an algorithm A for MSP let A(L) be the output of the algorithm, in this case the maximum height of the packing generated, i.e. max i∈{1,...,k} h i . The optimal value is denoted with OP T (L), in this case the minimal height that can be achieved. The quality of an approximation algorithm is measured by its performance ratio. For a minimization problem as MSP we say that A has absolute ratio α, if sup L A(L) /OP T (L) ≤ α, and asymptotic ratio α, if α ≥ lim sup OP T (L)→∞ A(L) /OP T (L), respectively. A minimization problem admits an (asymptotic) polynomial-time approximation scheme ((A)PTAS), if there exists a family of polynomial-time approximation algorithms {A ε |ε > 0} of (asymptotic) (1 + ε)-approximations. We call an approximation scheme fully polynomial ((A)FPTAS), if the running-time of every algorithm A ε is bounded by a polynomial in n and 1 ε . Zhuk showed in [START_REF] Zhuk | Approximate algorithms to pack rectangles into several strips[END_REF] that there is no approximation algorithm for MSP with absolute ratio less than 2. Since MSP can be reduced to 3-Partition, it is also strongly N P -hard. Therefore a PTAS and an FPTAS are ruled out and an AFPTAS is asymptotically the best possible. A related problem is 3D Strip Packing (3SP), which also is a generalization of Strip Packing. Here the goal is to find a packing of a given list of cuboids with side lengths bounded by one into a 3-dimensional strip [0, 1] × [0, 1] × [0, ∞), minmizing the height of the packing. Multiple Strip Packing with k strips can be reduced to 3SP by introducing a cuboid with depth 1 /k for each rectangle packing the strips next to each other. Parallel Job Scheduling in Grids with identical machines is also a related problem. In the offline case we have m machines M i with ℓ processors and jobs j ∈ J with processing time p j , and a size size j . The jobs must be executed on parallel processors within one machine M i , but not necessary on consecutive processors. The machines can be seen as strips with width l and the jobs as vertically scissile rectangles with width size j and height p j . In Multiple Strip Packing we have just the additional constraint that a job must be scheduled on consecutive processors. Unfortunately this is the reason why approximation algorithms for Parallel Job Scheduling cannot be applied to MSP maintaining their ratio.

Known Results. Multiple Strip Packing was first considered by Zhuk [START_REF] Zhuk | Approximate algorithms to pack rectangles into several strips[END_REF], who showed that there is no approximation algorithm with abolute ratio better than 2, and later by Ye et. al. [START_REF] Ye | On-line multiple-strip packing[END_REF]. Both concentrated on the online case. Additonally an approximation algorithm for the offline case with ratio 2 + ε was achieved in [START_REF] Ye | On-line multiple-strip packing[END_REF]. For Strip Packing Coffman et al. gave in [START_REF] Coffman | Performance bounds for level-oriented two-dimensional packing algorithms[END_REF] an overview about performance bounds for shelf-orientated algorithms as N F DH (Next Fit Decreasing Height) and F F DH (First Fit Decreasing Height). Those adopt an absolute ratio of 3, and 2.7, respectively. Schiermeyer [START_REF] Schiermeyer | Reverse-fit: A 2-optimal algorithm for packing rectangles[END_REF] and Steinberg [START_REF] Steinberg | A strip-packing algorithm with absolute performance bound 2[END_REF] presented independently an algorithm for SP with absolute ratio 2. A further important result is an AFPTAS for SP with additive constant O( 1 /ε 2 ) of Kenyon and Rémila [START_REF] Kenyon | A near optimal solution to a two-dimensional cutting stock problem[END_REF]. This constant was improved by Jansen and Solis-Oba, who presented in [START_REF] Jansen | New approximability results for 2-dimensional packing problems[END_REF] an APTAS with additive constant 1. For 3SP Jansen and Solis-Oba obtained an algorithm with ratio 2 + ε in [START_REF] Jansen | An asymptotic approximation algorithm for 3d-strip packing[END_REF] as an improvement of the formerly known result by Miyazawa and Wakabayashi [START_REF] Miyazawa | Cube packing[END_REF], who presented an algorithm with asymptotic ratio at most 2.64. Bansal et al. presented in [2] an algorithm for 3SP with a ratio of T ∞ ≈ 1.69, which is the best known result. Schwiegelshohn et al. [START_REF] Schwiegelshohn | Online scheduling in grids[END_REF] achieved ratio 3 for a version of Parallel Job Scheduling in Grids without release times, and ratio 5 with release times. Tchernykh et al. presented in [START_REF] Tchernykh | Two level job-scheduling strategies for a computational grid[END_REF] an algorithm with absolute ratio 10 for the case of machines with different numbers of processors and without release times. However, this algorithm cannot be applied directly to MSP because of the non-contiguity.

Our Results. In this paper we present an approximation algorithm with absolute ratio 2, which is an improvement of the former result of 2 + ε by Ye et al. [START_REF] Ye | On-line multiple-strip packing[END_REF] and best possible, unless P = N P. We also introduce an AFPTAS for Mutiple Strip Packing, which is a generalization of the algorithm of Kenyon and Rémila [START_REF] Kenyon | A near optimal solution to a two-dimensional cutting stock problem[END_REF]. Our algorithm achieves an additive constant of O(1), if the number of strips is sufficient large, otherwise an additive constant of O( 1 /ε 2 ). Furthermore we show how to use the simple shelf-based heuristics N F DH and F F DH to obtain approximation algorithms for MSP with the same asymptotic ratio as for SP.

Organisation of the Paper. In the next section we introduce two shelf-based algorithms, using Next Fit and First Fit policies. In Section 3 we present a 2approximation for MSP. Here we distinguish between different sizes for k. For k = 1 we use the 2-approximation of Steinberg [START_REF] Steinberg | A strip-packing algorithm with absolute performance bound 2[END_REF] or Schiermeyer [START_REF] Schiermeyer | Reverse-fit: A 2-optimal algorithm for packing rectangles[END_REF]. If k = 2 or bounded by a specified constant c we make use of a result by Bansal et al. [START_REF] Bansal | How to maximize the total area of rectangle packed into a rectangle[END_REF] for Rectangle Packing with Area Maximization (RP A). For k ≥ c we use an approximation algorithm for 2D bin packing with asymptotic ratio 1.69 of Caprara [START_REF] Caprara | Packing 2-dimensional bins in harmony[END_REF]. In the last section we present an AFPTAS for MSP. Here we generalize the algorithm by Kenyon and Rémila [START_REF] Kenyon | A near optimal solution to a two-dimensional cutting stock problem[END_REF]. Interestingly, the additive constant in our AFPTAS can be reduced from O( 1 /ε 2 ) to O(1), if the number k of strips is large enough.

Shelf-based algorithms

In this section we modify the shelf-based heuristics NFDH and FFDH. [START_REF] Coffman | Performance bounds for level-oriented two-dimensional packing algorithms[END_REF]. A shelf is a row of items placed next to each other left-justified. The baseline of a shelf is either the bottom of the bin or the extended upper edge of the tallest item packed in the shelf below. NFDH generates for a given list of rectangles L = {r 1 , . . . , r n } a packing into a strip with height at most 2OP T SP (L)+h max , FFDH produces a packing of height at most 1.7OP T SP (L)+h max , where OP T SP (L) is the optimum value of Strip Packing for the instance L and h max is the height of the tallest item in L. Via this modification we obtain approximation algorithms for Multiple Strip Packing with the same asymptotic ratios. Furthermore, we present another algorithm, that computes for rectangles with widths bounded by ε < 1 a packing of height at most 1 /(1-ε)OP T (L) + 2h max . We show now that for any instance L of MSP the output of A k is less than αOPT(L) + h max . Let t ∈ N be the number of shelves produced by A in Step 1 and H j , j ∈ {1, . . . , t}, the height of the jth shelf. Since there are no items intersecting the 0th line (see Fig 1), the height h 1 of the first strip S 1 is bounded by h max + 1 k t j=1 H jh max after the last step of the algorithm. For a strip S i , i ∈ {2, . . . , k}, containing the items between the (i -1)th and the ith line and the ones intersecting the (i -1)th line, we have h i ≤ A k (L) = max i∈{1,...,k}

P t j=1 Hj -hmax k + h max = A(L)-hmax k + h max . We conclude
h i ≤ A(L) -h max k + h max ≤ αOPT SP (L) + h max -h max k + h max = αOPT SP (L) k + h max .
Since 1 /kOPT SP (L) is a lower bound for OPT(L) the proof is complete.

The running-time of the above algorithm is O(n log n).

Corollary The packing generated by the above algorithm is very smooth, in the sense that the heights of the strips only differ by h max .

Lemma 1. For a set of rectangles L = {r 1 , . . . , r n } Algorithm 2 with output A(L) generates a packing into k strips, so that max i∈{1,...,k} |A(L) -

h i | ≤ h max .
This leads to a further result about rectangles with bounded width. Coffman et al. showed in [START_REF] Coffman | Performance bounds for level-oriented two-dimensional packing algorithms[END_REF] that F F DH applied to an instance L of rectangles with widths bounded by 1 /m for some integer m generates a packing into a strip of height at most (1 + 1 m )OP T SP (L) + h max . Our result for packing into k strips is the following: Theorem 3. For a set of rectangles L = {r 1 , . . . , r n } with widths bounded by ε > 0 we obtain by the Algorithm 2 with output A(L) a packing into k strips with height less than 1 1-ε OP T (L) + 2h max .

For ε = 1 m this is equal to A(L) ≤ 1 + 1 m-1 OPT(L) + 2h max .

A two-approximation for MSP

In this section we construct a polynomial-time approximation algorithm for MSP with absolute ratio 2. Since there is no approximation algorithm for MSP with ratio smaller than 2 (unless P=NP), this is the best possible result. To handle different sizes of k we use, besides the well-known algorithms of Steinberg [START_REF] Steinberg | A strip-packing algorithm with absolute performance bound 2[END_REF] or Schiermeyer [START_REF] Schiermeyer | Reverse-fit: A 2-optimal algorithm for packing rectangles[END_REF], a result of Bansal et al. [START_REF] Bansal | How to maximize the total area of rectangle packed into a rectangle[END_REF] for Rectangle Packing with Area Maximization (RP A) and a of Caprara [START_REF] Caprara | Packing 2-dimensional bins in harmony[END_REF].

One or two strips

The case k = 1 is trivial, because we can use the algorithm of Steinberg [START_REF] Steinberg | A strip-packing algorithm with absolute performance bound 2[END_REF] or Schiermeyer [START_REF] Schiermeyer | Reverse-fit: A 2-optimal algorithm for packing rectangles[END_REF] with absolute performance bound 2.

Theorem 4 (Steinberg [START_REF] Steinberg | A strip-packing algorithm with absolute performance bound 2[END_REF]). Let L = {r 1 , . . . , r n } be a set of rectangles with heights h i and widths w i and Q be a rectangle with width u and height v. Let h := max i∈{1,...,n} h i and w := max i∈{1,...,k} w i . If the following inequalities hold,

w ≤ u, h ≤ v, 2SIZE(L) ≤ uv -(2w -u) + (2h -v) + ( 1
)
then it is possible to pack L into the rectangle Q.(As usual, x + = max(x, 0).)

Therefore let us first consider the case for k = 2. Here we use the PTAS found by Bansal et al. [START_REF] Bansal | How to maximize the total area of rectangle packed into a rectangle[END_REF] for RPA. In RPA we are given a set of rectangles L = {r 1 , . . . , r n } with widths w i and heights h i and a bin of unit size. The goal is to find a feasible packing of a subset L ′ ⊂ L of the rectangles and to maximize the area of the rectangles in L ′ .

Algorithm 5

1 Guess the height of an optimal solution for MSP and denote it with v. 2 Scale the heights of the rectangles in L by 1 /v so that the corresponding packing fits into one bin of height and width one. 3 The set of resulting rectangles L v is now considered as an instance of RPA with OPT RP A (L) = SIZE(L v ), where SIZE(L v ) is the total area of all rectangles in L v . Apply the algorithm in [START_REF] Bansal | How to maximize the total area of rectangle packed into a rectangle[END_REF] with accuracy ε = 1 /2 and find a packing of a subset L ′ v ⊂ L v with total area at least (1ε)SIZE(L v ). By rescaling the rectangles of L ′ v get a packing for the first strip with height at most v.

4 Since SIZE(L v ) ≤ 2 the remaining items in L v \L ′ v have total area SIZE(L v \L ′ v ) ≤ εSIZE(L v ) ≤ 1.
Therefore we can pack them with Steinberg's algorithm into a strip of height at most 2. Rescaling gives us a second strip of height at most 2v.

The running-time of the algorithm is polynomial in n:

In the first step we can assume that the heights of the rectangles are rational, so by multiplying with a common denominator they become integer values. Then the optimum height v of MSP is also integer and equals a sum of heights of the rectangles in L, so we have h max ≤ v ≤ nh max . Thus Binary Search takes at most log(nh max ) iterations to find the value v. Step 3 is also polynomial, since we apply the algorithm in [START_REF] Bansal | How to maximize the total area of rectangle packed into a rectangle[END_REF] for a fixed accuracy ε = 1 /2.

A bounded number of strips

In the case of a constant number of strips we can use an extended version of the PTAS for RP A in [START_REF] Bansal | How to maximize the total area of rectangle packed into a rectangle[END_REF] called kRP A. Another helpful tool is the next lemma. The proof can be obtained applying Steinberg's algorithm for h, w, u = 1 and v = k /2 in equation 1.

Lemma 2. If L is an instance of 2DBP with total area SIZE(L) ≤ k /4 and k ≥ 3, then there exists a packing of L into k bins.

Algorithm 6

1 Guess an optimal height for MSP and denote it with v. 2 Scale the heights of the rectangles in L by 1 /v so that the corresponding packing fits into k bins of height and width one. 3 The set of resulting rectangles L v is now considered as an instance of RPA with OPT RP A (L) = SIZE(L v ). Apply kRP A to k bins of unit size and find for an accuracy ε ≤ 1 /4 a packing for a subset L ′ v ⊂ L v with total area (1ε)SIZE(L v ). By rescaling the rectangles of L ′ v we get k bins of height v. 4 For the total area of the remaining rectangles in

L v \L ′ v we have SIZE(L v \L ′ v ) = εSIZE(L v ) ≤ k /4.
Pack those rectangles according to Lemma 2 into k bins and rescale the rectangles. This results again in k bins of height at most v. 5 Stack every two bins on top of each other and get a solution with k bins of height at most 2v.

A large number of strips

Caprara presented in [START_REF] Caprara | Packing 2-dimensional bins in harmony[END_REF] a shelf algorithm for 2DBP that produces a solution whose asymptotic ratio can be made arbitrarily close to T ∞ = 1.69.... Clearly if the number of strips is large enough (≈ 10 4 ) applying this algorithm we get a twoapproximation for M SP stacking every two bins on each other. Alternatively, we can use the recently published two-approximation for 2DBP by Jansen et al. [START_REF] Jansen | Two for one: Tight approximation of 2d bin packing[END_REF] to achieve this result. Along with the previous sections we have the following:

Theorem 7. For any k ∈ N there is a polynomial-time algorithm for MSP with absolute ratio two.

An AFPTAS for MSP

In this section we present an AFPTAS for MSP. The algorithm is a generalization of an AFPTAS found by Kenyon and Rémila [START_REF] Kenyon | A near optimal solution to a two-dimensional cutting stock problem[END_REF] for Strip Packing. For an instance L of Strip Packing and an accuracy ε > 0 their algorithm generates a packing with height (1 + ε)OP T SP (L) + O( 1 /ε 2 )h max . Our algorithm achieves the same ratio for Multiple Strip Packing. For instances with k sufficient large, namely k ∈ Ω( 1 /ε 3 ), our algorithm adopts an improved additive constant of O(1).

More precisely for an accuracy ε and k ≥ ⌈ 128 /ε 3 ⌉ we get an approximation ratio of (1 + ε)OPT(L) + 6h max .

The regular case

As in Section 2 we divide a packing into one strip into k parts of nearly the same height and distribute them to k strips.

Theorem 8 (Kenyon & Rémila [9]). For a list L = {r 1 , . . . , r n } of rectangles and an accuracy ε > 0 the algorithm A KR ε in [START_REF] Kenyon | A near optimal solution to a two-dimensional cutting stock problem[END_REF] generates a packing into one strip with height at most (1 + ε)OP T SP (L) + (4( 2+ε ε ) 2 + 1)h max .

Our result is the following:

Theorem 9. For a list L = {r 1 , . . . , r n } of rectangles with widths and heights ≤ 1 and an accuracy ε > 0 there exits an algorithm A ε that generates a packing into k strips, so that

A ε (L) ≤ (1 + ε)OP T (L) + (2( 2+ε ε ) 2 + 2)h max .

Instances with a large number of strips

In this section we consider the case k ≥ ⌈ 128 /ε 3 ⌉. In this case it is possible to improve the additive constant to O(1)h max by balancing the configurations.

Rounding. We choose ε ′ = ε /4 (w.l.o.g. 1 /ε ′ integral) and divide the list of rectangles L into a list of narrow rectangles L narrow := {r i ∈ L|w(r i ) ≤ ε ′ } and a list of wide rectangles L wide := {r i ∈ L|w(r i ) > ε ′ }. Then we round L wide to an instance L sup with only M := ( 1 /ε ′ ) 2 different widths. For the rounding step we put the wide rectangles sorted by non-increasing widths left-aligned on a stack. Let ST ACK(L) denote the total area of the plane covered by this stack and let H denote its height. Moreover, for arbitrary lists L ′′ , L ′ we define a relation ≤ g , so that L ′′ ≤ g L ′ , if and only if ST ACK(L ′′ ) ⊆ ST ACK(L ′ ). We draw M -1 horizontal lines through ST ACK(L) with distance H /M starting at the bottom. Therefore we get M so-called threshold rectangles. A rectangle is a threshold rectangle if it either with its interior or with its lower edge intersects a line at height iH /M, i ∈ {1, . . . , M -1}. For i ∈ {1, . . . , M -1} we round up the width of each rectangle between the lines iH /M and (i+1)H /M to the width of the ith threshold rectangle. The widths of the rectangles below the first line are rounded up to the width of the undermost rectangle in the stack. So we get at most M groups of different widths (see Fig 2). Furthermore, we get a list L sup of rectangles with widths larger than ε ′ and only M different widths, in particular we have L wide ≤ g L sup .

Fractional Packing. Our first objective is to create a fractional packing for the wide rectangles into k strips. To do this we introduce configurations. A configuration is a non-empty multiset of widths, which sum up to less than one. Denote with q the number of different configurations C j with height x j . Let α ij be the number of occurence of width w i in configuration C j and let β i be the total height of all rectangles of width w i . Based on the solution of the following Linear Program min q j=1 x j k s.t. q j=1 α ij x j ≥ β i for all i ∈ {1, . . . , M } x j ≥ 0 for all j ∈ {1, . . . , q}, (LP(L sup )) by distributing the configurations to k strips we get the requested fractional packing for the rectangles in L sup . Note that rank(α ij ) ij ≤ M and hence a basic solution x of LP (L sup ) has at most M nonzero entries. In the next section we show how to transform a fractional packing into a feasible packing for L sup . Later the rectangles in L narrow are packed into the idle space in a Greedy manner. For a list L of rectangles let LIN (L) denote the height of an optimum fractional packing for L. Let h 0 := LIN (L sup ) and note that h 0 ≤ OP T (L). Lemma 3. Let x = (x 1 , . . . , x q ) be a solution of LP (L sup ) with at most m ≤ M nonzero entries x 1 , . . . , x m . For k ≥ ⌈ 128 /ε 3 ⌉ we get a fractional packing into k strips with height at most (1 + ε ′ )h 0 and at most m ′ ≤ 2M different configurations.

Proof. First we fractionally pack the rectangles into the configurations. Imagine each configuration C j as a bin with height x j and width c j and divide it into α ij columns of widths w i and height x j . Pack the rectangles in L sup of width w i in a Greedy manner fractionally into the columns of width w i until exactly height x j , starting with j = 1. In this way each column contains a sequence of rectangles, which completely fits inside the column, and possibly the top part of a rectangle, that started in a previous column, and the bottom part of a rectangle, that is too tall to fit into this column. Since m j=1 α ij x j ≥ β i , there will be maybe more than enough space for the rectangles of width w i in the configurations. In this case we distribute the rectangles among the columns and delete the additional space. So we split a configuration C j into two parts, one of the old type where the columns of width w i are completely filled and one without columns of width w i . This case may happen only M times. So we have in total m ′ = m + M ≤ 2M configurations C 1 , . . . C m ′ with nonzero heights x 1 , . . . , x m ′ . Notice that there exist configurations with height larger or equal h 0 , since if not we conclude

m ′ j=1 x j < m ′ h 0 ≤ 2M h 0 ε ′ = ε /4 = 32h0
ε 2 < kh 0 , which is a contradiction. Consider a configuration C j , j ∈ {1, . . . , m ′ }. If x j ≥ h 0 we allocate ⌊ xj /h0⌋ empty strips with height h 0 for C j . If then xj /h0 -⌊ xj /h0⌋ ≤ ε ′ h 0 , we assign to C j additional space with height ( xj /h0 -⌊ xj /h0⌋) in a strip, that has already height h 0 . If xj /h0 -⌊ xj /h0⌋ > ε ′ h 0 , we divide ( xj /h0 -⌊ xj /h0⌋) into at most 1 /ε ′ stripes with height less or equal ε ′ h 0 . So assign to C j additional space of height ε ′ h 0 in no more than 1 /ε ′ strips, which are already occupied until height h 0 . In the same way as the remaining stripes we handle configurations of height less than h 0 . Since there are at most 2M configurations with nonzero height, we get at most

2M /ε ′ = 2 /ε ′ 3 ≤ 2•4 3
/ε 3 ≤ k additional assignments of height ε ′ h 0 , which can be distributed to k strips. Thus by this assignment policy, where the configurations are balanced, each strip has allocated area of height at most (1 + ε ′ )h 0 for at most 2 different configurations. Integral Packing. The next Lemma shows how to get from a fractional packing to a feasible integral packing. A proof is given in the full paper. Lemma 4. Let x = (x 1 , . . . , x q ) be a solution of LP (L sup ) with at most m ′ ≤ 2M nonzero entries x 1 , . . . , x m ′ . For k ≥ ⌈ 128 /ε 3 ⌉ we can convert x to a feasible packing for the wide rectangles with height at most (1 + ε ′ )h 0 + 2h max and at most 2 different configurations per strip.

0 h 0 -h max h 0 h 0 + h max (1 + ε ′ )h 0 + h max (1 + ε ′ )h 0 + 2h max C j C ℓ
Since we can guarantee that there are at most 2 different configurations per strip, the additive constant will be improved, while the running-time is still polynomial in n and 1 /ε. Our last step is to pack the narrow rectangles. We use a modified version of the NFDH algorithm: For strip S i as above we pack narrow rectangles with NFDH into the empty space next to the configurations until the total height is at most (1+ε ′ )h 0 +2h max . After that we repeat the process for strip S i+1 . When all strips are filled in this way, we draw a horizontal line at height (1 + ε ′ )h 0 + 2h max in each strip and pack the remaining narrow rectangles with Algorithm 2 on top (see Fig 3 and4). Thus we can ensure by Lemma 1 that the maximum difference of the heights of two arbitrary strips is at most h max (see Fig 4). Let h f inal denote the height of the packing after packing the narrow rectangles. + 6h max + ε ′ h 0 .

0 h 0 -h max h 0 h 0 + h max (1 + ε ′ )h 0 + h max (1 + ε ′ )h 0 + 2h max
For details we refer to the full paper. The next lemma is shown in [START_REF] Kenyon | A near optimal solution to a two-dimensional cutting stock problem[END_REF] for the Linear Program corresponding to Strip Packing, but obviously also holds for our linear program LP (L sup ).

Theorem 1 .

 1 Let A be one of the shelf-based Strip Packing algorithms NFDH or FFDH with asymptotic ratio α > 1, that creates for an instance L a packing of height less than αOPT SP (L) + h max . For any k ∈ N there exists an algorithm A k that packs a list of rectangles L into k strips with A k (L) ≤ αOPT(L) + h max . Proof. For any instance L of MSP we define the algorithm A k as follows 1 Pack the sorted rectangles with A into one strip S. (In particular the rectangles are first sorted by non-increasing height.) Let A(L) denote the height of S. 2 Cut out the first shelf and pack it into the first strip S 1 . 3 Divide the residual strip S into k parts: 3.1 For each ℓ ∈ {0, 1, . . . , k} draw a horizontal line across S at height ℓ(A(L)h max )/k. 3.2 For ℓ ∈ {0, 1, . . . , k -1} pack all items intersecting the ℓth line and all items between the ℓth and (ℓ + 1)th line into strip S ℓ+1 .

Fig. 1 .

 1 Fig. 1. Dividing strip S.

Fig. 2 .

 2 Fig. 2. Rounding the rectangles in Lsup.

Fig. 3 .

 3 Fig. 3. Si with Cj and C ℓ .

Fig. 4 .

 4 Fig. 4. Si after packing the narrow rectangles.

Lemma 5 .

 5 Let k ≥ ⌈ 128 /ε 3 ⌉. If h f inal ≥ (1 + ε ′ )h 0 + 2h max , then we have h f inal ≤ SIZE(Lsup∪Lnarrow) k(1-ε ′ )

Lemma 6 . [ 9 ] 10 1Theorem 11 .

 691011 For the rounded instance L sup and L wide the inequalitiesLIN (L sup ) ≤ LIN (L wide ) 1 + 1 M ε ′ and SIZE(L sup ) ≤ SIZE(L wide ) 1 + 1 M ε ′ hold.The entire algorithm is now defined as follows:Algorithm Set ε ′ := ε /4 and M := ( 1 /ε ′ ) 2 .2 Partition L into L wide and L narrow . 3 Construct L sup , so that L wide ≤ g L sup and there are only M different widths in L sup . 4 Solve the linear program LP (L). 5 Construct a feasible solution for L sup by balancing the configurations. 6 Use modified N F DH to pack the rectangles in L narrow into the remaining space and on top of the strips. If k ≥ ⌈ 128 /ε 3 ⌉ the Algorithm 10 generates for an instance L of MSP a packing of height at most (1 + ε)OPT(L) + O(1)h max .

  1. Let L be an instance of MSP. In a packing generated by the above algorithm A k we have max i∈{1,...,k} |h i -A k (L)| ≤ 2h max , where h i denotes the height of strip S i . For each i ∈ {1, . . . , k} pack one shelf according to the N F DH heuristic into strip S i , that means starting in the lower left corner pack the rectangles next to each other on the baseline of strip S i , until the next rectangle does not fit. Draw a new baseline at the top edge of the tallest rectangle (that clearly is the first one). 3 Take the strip S -with the current lowest height h -and pack one shelf according to the N F DH heuristic on top of the shelves. 4 Repeat Step 3 until all rectangles are packed.

	Another way to pack a set of rectangles with a modified version of the N F DH
	heuristic into k strips is the following:
	Algorithm 2
	1 Sort the rectangles by non-increasing height.
	2

⋆ Work supported by EU project "'AEOLUS: Algorithmic Principles for Building Efficient Overlay Computers"', EU contract number 015964, and DFG project JA612/12-1, "'Design and analysis of approximation algorithms for two-and threedimensional packing problems"', and DGA-CNRS