Approximating the non-contiguous Multiple Organization Packing Problem

Marin Bougeret^{⋆}^{1}, Pierre François Dutot^{1}, Klaus Jansen^{2}, Christina Otte^{2}, and Denis Trystram^{1}

1 Grenoble University ZIRST 51, avenue Jean Kuntzmann 38330 Montbonnot Saint Martin, France

             {bougeret,pfdutot,trystram@imag.fr}

2 Department of Computer Science Christian-Albrechts-University to Kiel Christian-Albrechts-Platz 4, 24098 Kiel, Germany.

               {kj,cot}@informatik.uni-kiel.de

Abstract. We present in this paper a ^{5}/2-approximation algorithm for scheduling rigid jobs on multi-organizations. For a given set of n jobs, the goal is to construct a schedule for N organizations (composed each of m identical processors) minimizing the maximum completion time (makespan). This algorithm runs in O(n(N + log(n)) log(np_{max})), where p_{max} is the maximum processing time of the jobs. It improves the best existing low cost approximation algorithms. Moreover, the proposed analysis can be extended to a more generic approach which suggests different job partitions that could lead to low cost approximation algorithms of ratio better than ^{5}/2.

1 Problem statement

In this paper we consider the problem of scheduling rigid jobs on Multi-organizations. An organization is a set of m identical available processors. A job j must be executed on q_{j} processors (sometimes called the degree of parallelism) during p_{j} units of time. The q_{j} processors must be allocated on the same organization. The makespan of the schedule is defined as the maximum finishing time over all the jobs. Given a set of n jobs, the goal is to find a non-overlapping schedule of all the jobs on N organizations while minimizing the makespan.

This problem is closely related to strip packing problems. Indeed, if we add the constraint of using contiguous processors, then scheduling a job j on q_{j} contiguous processors during p_{j} units of time is equivalent to packing a rectangle of width q_{j} and height p_{j}.

⋆ This work has been supported by DGA-CNRS

Related works. Strip packing, rigid jobs scheduling and Multi-organizations scheduling problems are all strongly N P -hard, and Zhuk [1] showed that there is no polynomial time approximation algorithm with absolute ratio better than 2 for strip packing.

For Strip Packing problem, Coffman et al. gave in [2] an overview about performance bounds for shelf-oriented algorithms as NF DH (Next Fit Decreasing Height) and F F DH (First Fit Decreasing Height). These algorithms have a approximation ratio of 3 and 2.7, respectively. Schiermeyer [3] and Steinberg [4] presented independently an algorithm for Strip Packing with absolute ratio 2. A further important result for the Strip Packing problem is an AFPTAS with additive constant O(^{1}/ϵ^{2}) of Kenyon and Rémila [5]. This constant was improved by Jansen and Solis-Oba, who presented in [6] an APTAS with additive constant 1. Concerning the multi-strip packing problem, there is a 2 + ϵ approximation in [7] whose algorithmic cost is doubly exponential in \frac{1}{ϵ}. In [8] we gave a 2 approximation with a large algorithmic cost and an AFPTAS for this problem.

Let us now review the related work about rigid job scheduling. For one organization, the famous List Algorithm for scheduling with resource constraints of Garey and Graham [9] can be applied (when there is only one resource to share) to schedule rigid jobs, and is then a 2 approximation. The rigid job scheduling problem on multi-organization has been studied with an on-line setting in [10]. The authors achieved a ratio of 3 without release times (and 5 with release times). Notice that these results do not require the knowledge of the processing times of the jobs. Moreover, the organizations may have a different number of processors. The rigid job scheduling problem on multi-organizations has been extended in [11] for the case where the jobs are submitted to local queues on each cluster with the extra constraint that the initial local schedules must not be worsened. The authors provide a 3-approximation.

Generally, the results about rigid job scheduling cannot be adapted to the more constrained contiguous version. To the best of our best knowledge, there is still no (reasonable) α such that for any instance I, Optc(I) ≤ αOptnc(I) (where Optc denotes the contiguous optimal value and Optnc the non-contiguous one). The authors of [12] show that α > 1 by constructing a (rather) simple instance with 8 jobs and 4 machines.

Our contribution. In this paper, we present a \frac{5}{2} approximation algorithm for the rigid job scheduling problem on multi-organizations that runs in O(n(N +log(n)) log(np_{max})), where p_{max} is the maximum processing time of the jobs. Moreover, we suggest how the approach used for the^{5}/2-algorithm could extended to get approximation algorithms with better ratio and a low algorithmic cost.

Organization of the Paper. The preliminaries for the ^{5}/2-approximation are in Section 2. In Section 3.1 to 3.4 we describe how to construct a preallocation of the “big” jobs that fits in the targeted makespan. In Section 4 we show how to turn this preallocation into a compact schedule, and in Section 5 we analyze the complexity of the algorithm. The discussions on the approach are in Section 6.

2 Principle and definitions

Let us now give some definitions that are used throughout the proofs and the description of the algorithm. We first extend the previous p_{j} and q_{j} notations to Q(X) and P (X) where X is a set of jobs. We also define the surface (sometimes also called the area) of a set of jobs as S(X) = Σ_{j∈X}q_{j}p_{j}. A layer is a set of jobs which are scheduled sequentially on the same organization. The length of a layer Lay is P (Lay), the sum of the processing time of all the jobs in Lay. A shelf is a set of jobs which are scheduled on the same organization, and which start at the same time. Given a shelf sh, the value Q(sh) is called the height of sh. What we call a bin can be seen as a reservation of a certain number of processors (generally m) during a certain amount of time. The algorithm will add some jobs to bins, and given a bin b, we denote by Q(b) the value Σ_{{j∈b}}q_{j}. Given a sequence of bins seq, we denote by Q(seq) the value Σ_{b∈seq}Q(b). These notations are extended in the same way for P and S. In the whole paper, we consider that the sets of jobs used as parameters in the algorithms are modified after the calls.

Let us sketch how ^{5}/2 algorithm is constructed. Let OP T denote the value of an optimal solution. We target a \frac{5}{2} ratio by both ensuring that, for each organization at least half of the processors are used at any time before the starting time of the last job, and that the small jobs (whose processing time is lower than ^{OP T}/2 and height lower than ^{m}/2) are scheduled at the end. Thus, if the makespan of the final schedule is due to a small job, it is lower than the processing time of the small job plus the starting time of this job, implying a makespan lower than ^{OP T}/2 + 2OP T = ^{5OP T}/2. As the optimal value is not known, we use the well known dual approximation technique [13]. Let w denote the current guess of OP T. The schedule is built in three steps. In the first one we compute a preallocation π_{0} of the “big” (p_{j} > ^{w}/2 or q_{j} > ^{m}/2) jobs. Then we apply a list algorithm which turns π_{0} into a “compact” schedule π_{1} (see Section 4). Finally, the final schedule π is constructed by adding to π_{1} the small remaining jobs using again a list algorithm (see also Section 4).

Let us define the following sets:

• let L_{H} = {j|q_{j} > ^{m}/2} be the set of high jobs

• let L_{XL} = {j|p_{j} > ^{3w}/4} be the set of extra long jobs

• let L_{L} = {j|^{3w}/4 ≥ p_{j} > ^{w}/2} be the set of long jobs

• let L_{B} = (L_{XL} ⋃ L_{L}) ⋂ L_{H} be the set of huge jobs

• let I′ = L_{H} ⋃ L_{XL} ⋃ L_{L}

We will prove that either we schedule I with a resulting makespan lower than ^{5w}/2, or w < OP T. Notice that for the sake of simplicity we did not add the “reject” instructions in the algorithm. Thus we consider in all the proof that w ≥ OP T, and it is implicit that if one of the claimed properties is wrong during the execution, the considered w should be rejected. Notice that we only consider the w values such that Q(L_{XL} ⋃ L_{L}) ≤ Nm and P (L_{H}) ≤ Nw.

We start by providing in Section 3 the three phase algorithm Build P realloc that builds the preallocation π_{0} of the jobs of I′. We will denote by π_{0}^{i} the set of preallocated jobs in organization O_{i}. In phase 1 we preallocate the high jobs. In phase 2 and phase 3 we preallocate the long and extra long jobs by first packing shelves of jobs into bins, and then putting these bins into organizations. An example of a preallocation is depicted Figure 1.

3 Construction of the preallocation

3.1 Phase 1

Let N_{1} be the number of organizations used in phase 1. In phase 1, the jobs of L_{H} are packed in N_{1} organizations. The Create Layer(X, l) procedure creates a layer Lay of length at most l, using a Best Fit (according to the processing times) policy (BFP). Thus, Create Layer(X, l) add at each step the longest job that fits. Thus, phase 1 calls for each organization (until L_{H} is empty) Create Layer(L_{H},^{5w}/2).

Let us introduce some notations. Let Lay_{i} denote the set of jobs scheduled in the layer created in organization O_{i}. Let L_{XL}^{1} and L_{L}^{1} denote the remaining jobs of L_{XL} and L_{L} after phase 1. Thus, for the moment we have π_{0}^{i} = Lay_{i} for all i ≤ N_{1}.

Lemma 1 (phase 1). If ∃i_{0} < N_{1} such that P (π_{0}^{i_{0}}) ≤ 2w then it is straightforward to pack all the jobs of I′. Otherwise, we get ∀i ∈ {1, …, N_{1} − 1}, S(π_{0}^{i}) > wm and N_{1} ≤ ⌈^{N}/2⌉ .

Proof. First let us notice that phase 1 ends, as P (L_{H}) ≤ Nw and P (π_{0}^{i}) > w for every organization where we do not run out of jobs to schedule. We first suppose that ∃i_{0} < N_{1} such that P (π_{0}^{i_{0}}) ≤ 2w. In this case we just have to prove that it is straightforward to preallocate L_{XL} ⋃ L_{L}. We proceed by contradiction by supposing that we never ran out of jobs of L_{XL} ⋃ L_{L}. When the algorithm creates a layer for a organization i, we know due to the BFP order that it will pack at least two jobs of L_{B}, if L_{B} is not empty. The hypothesis implies that during the execution of phase 1, L_{H} \ L_{B} was empty before L_{B}. Thus, for i < N_{1}, there is at least two jobs of L_{B} in π_{0}^{i}, meaning that ∀i with 1 ≤ i < N_{1}, Q((L_{XL} ⋃ L_{L}) ⋂ π_{0}^{i}) > m.

Concerning the N − N_{1} other organizations, we can create shelves of jobs of L_{L} ⋃ L_{XL} using a best fit according to the height (BFH), implying that each shelf has a height of at least ^{2m}/3 according to Lemma 2. Packing two shelves in each organization, we get ∀i > N_{1}, Q((L_{XL} ⋃ L_{L}) ⋂ π_{0}^{i}) > ^{4m}/3 > m.

Finally, let us check what is scheduled in organization N_{1}. If two jobs of L_{B} are scheduled in this organization, then Q((L_{XL} ⋃ L_{L}) ⋂ π_{0}^{N_{1}}) > m. If one job of L_{B} is scheduled, then we create one shelf of jobs of L_{XL} ⋃ L_{L}, and Q((L_{XL} ⋃ L_{L}) ⋂ π_{0}^{N_{1}}) > ^{m}/2 + ^{2m}/3. If no huge job is scheduled in organization N_{1}, we pack as before two shelves of jobs of L_{XL} ⋃ L_{L}. Thus, if in every case we have Q((L_{XL} ⋃ L_{L}) ⋂ π_{0}^{N_{1}}) > m. Thus, we get Q((L_{XL} ⋃ L_{L})) > Nm, which is impossible.

Let us prove the second part of the lemma. First notice that for any i < N_{1}, S(π_{0}^{i}) > 2w^{m}/2 = mw. Moreover, we have 2(N_{1} − 1)w < Σ_{i=1}^{N_{1}}P (π_{0}^{i}) = P (L_{H}) ≤ Nw, implying N_{1} ≤ ⌈^{N}/2⌉.⊓ ⊔

Thus, we now assume until the end of the proof that we are in the second case of Lemma 1 where ∀i ∈ {1, …, N_{1} − 1}, S(π_{0}^{i}) > mw and N_{1} ≤ ⌈^{N}/2⌉.

3.2 Phase 2

In phase 2 the jobs of L_{XL}^{1} ⋃ L_{L}^{1} are scheduled in organization N_{1} by creating shelves according to what is already scheduled in organization N_{1}. We denote by L_{XL}^{2} and L_{L}^{2} the remaining jobs of L_{XL}^{1} and L_{L}^{1} after phase 2. Let us first define two procedures used for phase 2 and phase 3.

The procedure P ack Shelf(X, b, f) creates a shelf sh using the Best Fit (according to the height) policy (BFH), and packs it into bin b. The f parameter represents the available height of b (meaning that b corresponds to f free processors during a certain amount of time), implying of course that Q(sh) ≤ f. Thus P ack Shelf(X, b, f) adds at each step the highest possible job of X that fits. We assume that the length of the bin is larger than p_{j}, for all j ∈ X.

The procedure GreedyP ack(X, seq) creates for each empty bin b ∈ seq one shelf of jobs of X using P ack Shelf(X, b, m). This procedure returns the last bin in which a shelf has been created. Let us now come back to the description of phase 2.

Depending on the set of jobs already scheduled in O_{N_{1}}, the Create P adding() procedure creates n_{bin_{L}} empty bins of length ^{3w}/4 and n_{bin_{XL}} empty bins of length w, which are added in organization O_{N_{1}}. Let us define for each case how many bins of each type are created by Create P adding():

• If P (Lay_{N_{1}}) ∈]^{3w}/2,^{7w}/4] then set (n_{bin_{L}}, n_{bin_{XL}}) to (1, 0)

• If P (Lay_{N_{1}}) ∈]w,^{3w}/2] then set (n_{bin_{L}}, n_{bin_{XL}}) to (0, 1)

• If P (Lay_{N_{1}}) ∈]^{3w}/4, w] then if Q(L_{L}^{1}) ≥ ^{5}/4 then set (n_{bin_{L}}, n_{bin_{XL}}) to (2, 0) else set (n_{bin_{L}}, n_{bin_{XL}}) to (0, 1)

• If P (Lay_{N_{1}}) ∈]^{w}/2,^{3w}/4] then set (n_{bin_{L}}, n_{bin_{XL}}) to (1, 1)

• If P (Lay_{N_{1}}) ∈ [0,^{w}/2] then set (n_{bin_{L}}, n_{bin_{XL}}) to (0, 2)

Let pad_{L} be a sequence of n_{bin_{L}} bins of length ^{3w}/4 and pad_{XL} be a sequence of n_{bin_{XL}} bins of length w. Create P adding() returns (pad_{L}, pad_{XL}). All in all, phase 2 can be described by the following procedure calls:

• Let (pad_{L}, pad_{XL}) = Create P adding()

• GreedyP ack(L_{XL}^{1}, pad_{XL})

• GreedyP ack(L_{L}^{1}, pad_{L})

• GreedyP ack(L_{L}^{1}, pad_{XL})

Fig. 1. An example of pre-allocation

3.3 Phase 3

In phase 3 we first schedule the jobs of L_{XL}^{2} using the N_{2} = N − N_{1} remaining organizations. Then, we schedule the jobs of L_{L}^{2} using also this N_{2} organizations. Finally, the possibly remaining jobs of L_{L}^{2} are added to the last bin used for the extra long jobs. Therefore, let us define the add(X, b) procedure. The add(X, b) procedure packs one or two “small” shelves of jobs of X in the bin b (starting from the top of the bin for the sake of clarity). Notice that, as b will be the last bin used for extra long jobs, the available height (for the jobs of X) in b will be generally lower than m. Here is the description of add(X, b):

• If the left side of b is at time w then let l = 2 else let l = 1

• Repeat l times the call P ack Shelf(X, b, m − Q(b)) and pack the created shelves in b.

An example of a call to the add procedure is given in Figure 1 for the case where l = 2.

We now define two sequences of bins seq_{XL} and seq_{L}, such that every bin of seq_{XL} (resp. seq_{L}) will (possibly) contains one shelf of jobs of L_{XL}^{2} (resp. L_{L}^{2}). Notice that a free organization can be seen as two bins of length w (and height m), three bins of length ^{3w}/4, or one bin of length w and two bins of length ^{3w}/4. Thus, seq_{XL} is composed of 2(N − N_{1}) bins (b_{1}, …, b_{2(N−N_{1})}) of length w, considering that we created two bins in each of the organizations {O_{N_{1}+1}, … O_{N}}, starting from O_{N_{1}+1}. This implies that for all i ≥ 1, bins b_{2i−1} and b_{2i} are in O_{N_{1}+i}. The sequence seq_{L} is composed of 3(N − N_{1}) bins (b′_{1}, …, b′_{3(N−N_{1})}) of length ^{3w}/4, considering that we created three bins in each of the organizations {O_{N_{1}+1}, … O_{N}}, from O_{N} to O_{N_{1}+1}. This implies that for all i ≥ 1, bins b′_{3i−2}, b′_{3i−1} and b′_{3i} are in O_{N−i+1}. Notice that these two sequences are not ordered in the same way.

All in all, phase 3 can be described by the following procedure calls:

• Let last = GreedyP ack(L_{XL}^{2}, seq_{XL})

• GreedyP ack(L_{L}^{2}, seq_{L})

• add(L_{L}^{2}, last)

Let start the analysis of phase 3 with a remark about P ack Shelf(X, b, f).

Lemma 2. Let Sh denote the shelf created by P ack Shelf(X, b, f). If we know that the k highest jobs of X fit in f, then Q(Sh) > \frac{k}{k+1}f.

Proof. Let x be the cardinal of X. Let us assume that q_{i} ≥ q_{i+1} for 1 ≤ i < x. Let i_{0} ≥ k+1 be the first index such that job i_{0} is not in Sh. Let a = Σ_{i=1}^{i_{0}−1}q_{i}. We have Q(Sh) ≥ a ≥ (i_{0} − 1)q_{i_{0}} > (i_{0} − 1)(f − a) leading to a > \frac{i_{0}−1}{i_{0}}f ≥ \frac{k}{k+1}f.⊓ ⊔

Lemma 3 (phase 3). If there remains an unscheduled job after phase 3, then S(L_{XL}^{2} ⋃ L_{L}^{2}) > (N_{2} +^{1}/8)mw.

Proof. Let us first suppose that L_{XL}^{2} ≠ ∅. Let a_{XL} = 2(N − N_{1}) be the number of bins in seq_{XL}. After having filled the first a_{XL} − 1 bins (using a width of at least ^{2}/3 according to Lemma 2), the width of remaining jobs of L_{XL}^{2} is strictly larger than m. Thus we get Q(L_{XL}^{2}) > ^{2m}/3(a_{XL} − 1) + m = ^{4m}/3N_{2} +^{m}/3 and S(L_{XL}^{2}) > (N_{2} +^{1}/4)mw.

We now suppose that L_{XL}^{2} = ∅. In every organization that contains two bins of jobs of L_{XL}^{2}, the total scheduled area is strictly larger than 2 ×^{2m}/3 ×^{3w}/4 = wm. In every organization that contains three bins of jobs of L_{L}^{2}, the total scheduled area is strictly larger than 3 ×^{2m}/3 ×^{w}/2 = wm. We have to consider two cases according to the position of the last bin last (the left side of last may be located at time 0 or w). Let i_{0} be the index of the organization that contains last.

In the first case where the left side of last is at time 0, two bins (of length 3w/4 and height m) were created after the bin last in organization O_{i_{0}}. Then, if the remaining jobs of L_{L}^{2} do not fit in last, the total area of the jobs scheduled in organization O_{i_{0}} is strictly larger than (2^{2m}/3 + m)^{w}/2 > ^{7wm}/6. Then we just sum the area packed over all the organizations, and get the desired result.

In the second case where the left side of last is at time w (as depicted in Figure 1), the only room in organization O_{i_{0}} to schedule jobs of L_{L}^{2} is in last. In organization O_{i_{0}}, the area of (extra long) jobs contained in the first bin is strictly larger than ^{wm}/2. The add procedure will create two shelves (one next to the other) of jobs of L_{L}^{2} in last.

Let last′ and L′_{L} be the set of jobs in last and L_{L}^{2} respectively, just before the call of the add procedure. If Q(last′) > ^{m}/2, and as the remaining jobs of L_{L}^{2} don’t fit in last, we have that Q(L′_{L}) > m − Q(last′)′. This implies S(last′ ⋃ L′_{L}) > 3w/4Q(last′) +^{w}/2(m − Q(last)′) > ^{5wm}/8. If Q(last′) ≤ ^{m}/2 (see Figure 1) then add creates a first shelf of jobs of L_{L}^{2} of height at least^{(m−Q(last′))}/2, and then tries to pack the remaining jobs in the second shelf. Thus in this case, S(last′ ⋃ L′_{L}) > 3w/4Q(last′) +^{w}/2 (\frac{(m−Q(last′))}{2} + m − Q(last′)) > ^{3mw}/4.⊓ ⊔

3.4 Main algorithm

In this section we recall the overall algorithm that builds the preallocation, and we provide the main proof of the preallocation. Notice that we drop the L_{L}^{i} and L_{XL}^{i} notations for writing the algorithm as we consider that the sets of jobs (used as parameters in the procedures) are modified after the calls.

Algorithm 1 Build Prealloc(I′)

Phase 1 [1] Let i = 0

[2] Let i = i + 1, and let Lay_{i} = Create Layer(L_{H},^{5w}/2) Pack Lay_{i} in organization S_{i} from time 0

[3] Repeat step 3 until L_{H} is empty

Phase 2 [4] Let (pad_{L}, pad_{XL}) = Create P adding()

[5] Let last = GreedyP ack(L_{XL}, pad_{XL})

[6] Call GreedyP ack(L_{L}, pad_{L})

[7] Call GreedyP ack(L_{L}, pad_{XL})

Phase 3 [8] Let seq_{XL} and seq_{L} be defined as described in Section 3.3

[9] Let last_{2} = GreedyP ack(L_{XL}, seq_{XL})

[10] If last_{2} is not null, set last to last_{2}

[11] Call GreedyP ack(L_{L}, seq_{L})

[12] Call add(L_{L}, last)

Theorem 1. Build P realloc(I′) creates a preallocation π_{0} of makespan lower than ^{5w}/2.

Proof. Remind that L_{XL}^{1} and L_{L}^{1} denote the remaining jobs of L_{XL} and L_{L} after Phase 1. The makespan of the preallocation is by construction lower than ^{5w}/2. We know that according to Lemma 1 phase 1 terminates and the area scheduled in the first N_{1} − 1 organizations is greater than (N_{1} − 1)wm. We proceed by contradiction by supposing that L_{XL}^{1} ⋃ L_{L}^{1} is not empty after Phase 2 and Phase 3, and showing that S(I′) > Nmw. We proceed by case analysis according to what is scheduled in O_{N_{1}}.

If P (Lay_{N_{1}}) > \frac{7}{4}w, then S(Lay_{N_{1}}) > \frac{7}{8}mw and CreateP adding doesn’t create any bin. If L_{XL}^{1} and L_{L}^{1} are not completely scheduled by phase 3, then according to Lemma 3 we get S(L_{XL}^{1} ⋃ L_{L}^{1}) > (N_{2} + \frac{1}{8})mw. Thus in this case we have S(Lay_{N_{1}} ⋃ L_{XL}^{1} ⋃ L_{L}^{1}) > (N_{2} + 1)mw, implying S(I′) > Nmw.

If \frac{7}{4}w ≥ P (Lay_{N_{1}}) > \frac{3}{2}w, then S(Lay_{N_{1}}) > \frac{3}{4}mw and CreateP adding creates one bin of length \frac{3}{4}w. Recall that the jobs of L_{L}^{1} are first scheduled in pad_{L}. If Q(pad_{L}) is larger than \frac{m}{2}, then S(Lay_{N_{1}} ⋃ pad_{L}) > \frac{3}{4}mw + \frac{1}{4}mw = mw. Thus, the total area packed in the first N_{1} is strictly larger than N_{1}wm. Then, according to Lemma 3, L_{XL}^{2} ⋃ L_{L}^{2} must fit in the N_{2} remaining organizations. If Q(pad_{L}) ≤ \frac{m}{2}, then the N_{2} remaining organizations are available for L_{XL}^{1}. Thus, if L_{XL}^{1} ≠ ∅ at the end, then S(L_{XL}^{1}) > (N_{2} + \frac{1}{4})mw, and S(Lay_{N_{1}} ⋃ L_{XL}^{1}) > (N_{2} + 1)mw.

If \frac{3}{2}w ≥ P (Lay_{N_{1}}) > w, then S(Lay_{N_{1}}) > \frac{1}{2}mw and CreateP adding creates one bin of length w. If Q(pad_{XL}) is larger than \frac{2m}{3} then S(Lay_{N_{1}} ⋃ pad_{XL}^{1}) > mw and we conclude with Lemma 3. Otherwise, the N_{2} remaining organizations are available for L_{L}^{1}. Moreover, remind that in this case the only bin in pad_{XL} will be used for jobs of L_{L} during the call of add. Then, if L_{L}^{1} does not fit, we have Q(L_{L}^{1} ⋃ L_{XL}^{1}) > (2N_{2} +1)m and S(Lay_{N_{1}} ⋃ L_{L}^{1} ⋃ L_{XL}^{1}) > \frac{mw}{2} +N_{2}wm+ \frac{wm}{2} = (N_{2} + 1)mw.

If w ≥ P (Lay_{N_{1}}) > \frac{3}{4}w, then S(Lay_{N_{1}}) > \frac{3}{8}mw and two cases are possible according to the value of Q(L_{L}^{1}). If Q(L_{L}^{1}) ≥ \frac{5m}{4}, CreateP adding creates two bins of length \frac{3}{4}w. Then, S(Lay_{N_{1}} ⋃ pad_{L}) > (\frac{3}{8} + \frac{5}{8})mw and we conclude with Lemma 3. Otherwise, if Q(L_{L}^{1}) < \frac{5m}{4}, CreateP adding creates one bin pad_{XL} of length w. If Q(pad_{XL}) (after the call line 5) is larger than \frac{2m}{3} then S(Lay_{N_{1}} ⋃ pad_{XL}^{1}) > \frac{7}{8}mw and we conclude with Lemma 3. Otherwise, jobs of L_{XL}^{1} are all scheduled in pad_{XL}. As N_{2} ≥ 1, at least three bins are available for L_{L}^{1}, which is sufficient given that Q(L_{L}^{1}) < \frac{5m}{4}.

If \frac{3}{4}w ≥ P (Lay_{N_{1}}) > \frac{1}{2}w, then S(Lay_{N_{1}}) > \frac{1}{4}mw and CreateP adding creates one bin of length w and one bin of length \frac{3}{4}w. If extra long jobs are not scheduled at the end of the algorithm, then S(Lay_{N_{1}} ⋃ pad_{XL}) > \frac{3}{4}mw. Since L_{XL}^{2} do not fit into N_{2} free organizations, we have also S(L_{XL}^{2}) > (N_{2} + \frac{1}{4})mw. Thus we conclude that the extra long jobs are successfully scheduled. Let us suppose now that the long jobs are not completely scheduled. If Q(pad_{XL}) ≥ \frac{5m}{9} then S(Lay_{N_{1}} ⋃ pad_{XL} ⋃ pad_{L}) > (\frac{1}{4} + \frac{5}{12} + \frac{1}{3})mw = mw. Otherwise, let L′_{L} denote the set of remaining jobs of L_{L}^{1} just before the call to add. The area scheduled in the N_{2} last organizations is larger than the one scheduled in the optimal. If L′_{L} does not fit in pad_{XL} during the call to add, then Q(L_{XL}^{1} + L′_{L}) > m and S(Lay_{N_{1}} ⋃ pad_{L} ⋃ pad_{XL} ⋃ L′_{L}) > (\frac{1}{4} + \frac{1}{3} + \frac{1}{2})mw > mw.

If \frac{1}{2}w > P (Lay_{N_{1}}), CreateP adding creates two bins of length w. If N_{1} > 1, then S(⋃_{i=1}^{N_{1}} Lay_{i}) > S(⋃_{i=1}^{N_{1}−2} Lay_{i}) + \frac{5}{4}mw > (N_{1} − 1)mw + \frac{1}{4}mw because the first job of Lay_{N_{1}} does not fit in the previous organization. Thus, if Q(L_{XL}^{1}) > m then we have S(⋃_{i=1}^{N_{1}} Lay_{i} ⋃ pad_{XL}) > N_{1}mw and we conclude with Lemma 3. Otherwise, we have an empty bin in the sequence pad_{XL} and N_{2} free organizations available for L_{L}^{1}. Let L′_{L} be L_{L}^{1} before the call to add. If add does not schedule L′_{L} in last then Q(L_{XL}^{1})+Q(L′_{L}) > m and S(⋃_{i=1}^{N_{1}} Lay_{i} ⋃ L_{XL}^{1} ⋃ L′_{L}) > (N1 − \frac{3}{4} + \frac{1}{3} + \frac{1}{2})mw > N_{1}mw. If N_{1} ≤ 1 then we have two bins of length w in each of the N organizations, which is of course sufficient to pack L_{XL}^{1} ⋃ L_{L}^{1}.⊓ ⊔

4 From the preallocation to the final schedule

From now on, we suppose that the preallocation π_{0} is built. For each organization O_{i}, π_{0} indicates first a (possibly empty) sequence of high jobs j_{1}^{i}, …, j_{x_{i}}^{i} that have to be scheduled sequentially from time 0. Then, π_{0} contains an ordered sequence of shelves Sh_{1}^{i}, …, Sh_{x′_{i}}^{i}. Moreover, the makespan of π_{0} is by construction less than ^{5w}/2.

Definition 1. Let u_{i}(t) be the utilization of organization O_{i} at time t, i.e. u_{i}(t) is the sum of all the q_{j} for any job j which scheduled on organization i at time t. A schedule is ^{1}/2 compact if and only if for every organization O_{i} there exists a time t_{i} such that for all t ≤ t_{i}, u_{i}(t) ≥ ^{m}/2 and u_{i} restricted to t > t_{i} is not increasing.

Let us now describe the algorithm LS_{π_{0}} which turns π_{0} into a ^{1}/2 compact schedule π_{1} of I′. We first define the procedure Add Asap(X, O_{i}) which scans organization O_{i} from time 0, and for every time t starts any possible job(s) in X that fit(s) at time t. The LS_{π_{0}} works as follows: for every organization O_{i}, pack first sequentially the high jobs j_{x}^{i} for 1 ≤ x ≤ x_{i} and then call Add Asap(Sh_{x}, O_{i}) for 1 ≤ x ≤ x′_{i}.

Lemma 4. The makespan of π_{1} is lower than the one of π_{0}, and π_{1} is ^{1}/2 compact.

Proof. Let σ_{i} be a schedule in a (single) organization O_{i} (of makespan C_{i}), let X be a set of jobs and let σ′_{i} be the schedule (of makespan C′_{i}) produced by Add Asap(X, O_{i}). If σ_{i} is ^{1}/2 compact and if forall j ∈ X, q_{j} ≤ ^{m}/2, then σ′_{i} is 1/2 compact. The proof is straightforward by induction on the cardinality of X. Moreover, if ∑_{X} q_{j} ≤ m, then C′_{i} ≤ C_{i} + max_{X}p_{j} because in the worst case all the jobs of X only start at time C_{i}. Using these two properties, we prove the lemma for every organization O_{i} by induction on the number of call(s) to Add Asap(Sh_{x}, O_{i}).⊓ ⊔

Remark 1. Notice that in Lemma 4 we do not take care of the particular structure which occurs when add creates two shelves of jobs of L_{L} as depicted Figure 1. However, it is easy to see that the proof can be adapted.

Now that π_{1} is built, we add the small remaining jobs (I \ I′) using a list algorithm that scans all the organizations from time 0 and schedules as soon as possible any non scheduled job. Let π denote the obtained schedule.

Theorem 2. The makespan of π is lower than ^{5w}/2.

Proof. The proof is by induction on the cardinal of I \ I′. At the beginning, π_{1} is ^{1}/2 compact, as proved in Lemma 4. Each time a job j is scheduled by the list algorithm, the obtained packing remains ^{1}/2 compact because q_{j} ≤ \frac{m}{2}. Thus it is clear that π is ^{1}/2 compact.

Let us assume that the makespan of π is due to a job j ∈ I \ I′ that starts at time s. As π is ^{1}/2 compact, this implies that when scheduling job j we had t_{i} ≥ s for any organization i. Thus, we have S(I) > ∑_{i=1}^{N} \frac{t_{i}}{2} ≥ N \frac{s}{2}, implying that s < 2w, and thus that the makespan of π is lower than ^{5w}/2.⊓ ⊔

5 Complexity

Phase 1 can be implemented in O(Nn + n log(n)). Indeed, we first sort the high jobs in non increasing order of their processing times. Then, each layer can be created in O(n). Phase 2 and phase 3 can also be implemented in O(Nn + n log(n)) by sorting the long (and extra long) jobs in non increasing order of their required processors. Thus π_{0} is constructed in O(Nn + n log(n)).

The LS_{π_{0}} algorithm can be implemented in O(n log(n)). Instead of scanning time by time and organization by organization, this algorithm can be implemented by maintaining a list that contains the set of “currently” scheduled jobs. The list contains 3-tuples (j, t, i) indicating that job j (scheduled on organization i) finishes at time t. Thus, instead of scanning every time from 0 it is sufficient to maintain sorted this list according to the t values (in non decreasing order), and to only consider at every step the first element of the list. Then, it takes O(log(n)) to find a job j_{0} in the appropriate shelf that fits at time t, because a shelf can be created as a sorted array. It also takes O(log(n)) to insert the new event corresponding to the end of j_{0} in the list.

The last step, which turns π_{1} into the final schedule can also be implemented in O(n log(n)) using a similar global list of events. Notice that for any organization O_{i}, there exists a t_{i} such that before t_{i} the utilization is an arbitrary function strictly larger than ^{m}/2, and after t_{i} a non increasing after. Scheduling a small job before t_{i} would require additional data structure to handle the complex shape. Thus we do not schedule any small job before t_{i} as it is not necessary for achieving the ^{5}/2 ratio. Therefore, we only add those events that happen after t_{i} when initializing the global list for this step. To summarize, for this step we only need to sort the small jobs in non increasing order of their required number of processors, and then apply the same global list algorithm.

The binary search on w to find the smallest w which is not rejected can be done in O(log(np_{max})) as all the processing times can be assumed to be integers. Thus the overall complexity of the ^{5w}/2 approximation is in O(log(np_{max})n(N + log(n))).

6 Toward better approximation ratios

In this paper we provided a low cost ^{5}/2-approximation algorithm using a new approach. We discuss in this section how the proposed approach can be used for reaching better approximation bounds. The approach can be summarized in the two following main steps. The first one consists in constructing a ^{1}/2 compact schedule π_{1} of the big jobs I′ by creating a pre-allocation π_{0} and “compressing” it. Then, the remaining small jobs (I \ I′) are added to π_{1} in a second step using the classical list scheduling algorithm LS.

We would like to recall the arguments that make our second step easy to analyze, and see what could be some other promising partitions. In our partition, the second step guaranties a makespan lower than ^{5w}/2 because:

• adding a job j with q_{j} ≤ ^{m}/2 to a ^{1}/2 compact schedule with LS produces another ^{1}/2 compact schedule,

• if the makespan is due to a small job j_{0} that starts at time s_{0}, then s_{0} ≤ 2w (since the schedule is ^{1}/2 compact), leading to a makespan lower than s_{0} + p_{j_{0}} ≤ ^{5w}/2.

Let us now propose other partitions that could be considered. We could define I′ = {j|q_{j} > αm_{i} or p_{j} > βw} with appropriate values 0 < α < 1 and 0 < β < 1. Then, the previous steps become:

1. construct a pre-allocation π_{0} of I′ (for instance based on shelves and layers) and make sure that, when compressed using LS_{π_{0}}, the obtained schedule π_{1} is 1 − α compact (meaning that for every organization, the utilization is greater than 1 − α, and then it is non-increasing),

2. add the small remaining jobs (I \ I′) using LS.

Thus, the makespan of jobs added in the second step would be bounded by b = (\frac{1}{1−α} + β)w, implying that the makespan of the pre-allocation should also be bounded by b.

For example, we can target a ^{7}/3 ratio by only studying how to pre-allocate I′ = \{j|q_{j} > \frac{m_{i}}{2} or p_{j} > \frac{w}{3} \}, or a ratio 2 by studying how to pre-allocate I′ = \{j|q_{j} > \frac{m_{i}}{3} or p_{j} > \frac{w}{2} \}. Obviously, if the preallocation is built using again shelves and layers, the difficulty will probably arise when merging the different types of jobs (high, extra long or long ones for example), and will may be only need to handle more particular cases.

Let us remark that this technique will not be easy to apply with (contiguous) rectangles, since the property of ^{1}/2 compactness becomes hard to guarantee.

References

1. S. Zhuk, “Approximate algorithms to pack rectangles into several strips,” Discrete Mathematics and Applications, vol. 16, no. 1, pp. 73–85, 2006.

2. E. Coffman Jr, M. Garey, D. Johnson, and R. Tarjan, “Performance bounds for level-oriented two-dimensional packing algorithms,” SIAM J. Comput., vol. 9, p. 808, 1980.

3. I. Schiermeyer, “Reverse-fit: A 2-optimal algorithm for packing rectangles,” Lecture Notes in Computer Science, pp. 290–290, 1994.

4. A. Steinberg, “A strip-packing algorithm with absolute performance bound 2,” SIAM Journal on Computing, vol. 26, p. 401, 1997.

5. C. Kenyon and E. Rémila, “A near-optimal solution to a two-dimensional cutting stock problem,” Mathematics of Operations Research, pp. 645–656, 2000.

6. K. Jansen and R. Solis-Oba, “New approximability results for 2-dimensional packing problems,” Lecture Notes in Computer Science, vol. 4708, p. 103, 2007.

7. D. Ye, X. Han, and G. Zhang, “On-Line Multiple-Strip Packing,” in Proceedings of the 3rd International Conference on Combinatorial Optimization and Applications, p. 165, Springer, 2009.

8. M. Bougeret, P.-F. Dutot, K. Jansen, C. Otte, and D. Trystram, “Approximation algorithm for multiple strip packing,” Proceedings of the 7th Workshop on Approximation and Online Algorithms (WAOA), 2009.

9. M. Garey and R. Graham, “Bounds for multiprocessor scheduling with resource constraints,” SIAM J. Comput., vol. 4, no. 2, pp. 187–200, 1975.

10. U. Schwiegelshohn, A. Tchernykh, and R. Yahyapour, “Online scheduling in grids,” in Proceedings of IPDPS, pp. 1–10, 2008.

11. P.-F. Dutot, F. Pascual, K. Rzadca, and D. Trystram, “Approximation algorithms for the multi-organization scheduling problem,” Submitted to: IEEE Transactions on Parallel and Distributed Systems (TPDS), 2010.

12. P.-F. Dutot, G. Mounié, and D. Trystram, Handbook of Scheduling, ch. Scheduling Parallel Tasks: Approximation Algorithms. CRC Press, 2004.

13. D. S. Hochbaum and D. B. Shmoys, “A polynomial approximation scheme for scheduling on uniform processors: Using the dual approximation approach,” SIAM J. Comput., vol. 17, no. 3, pp. 539–551, 1988.