Complexity and Inapproximability Results for Parallel Task Scheduling and Strip Packing

Abstract

We study Parallel Task Scheduling Pm|size_j|C_max with a constant number of machines. This problem is known to be strongly NP-complete for each m ≥ 5, while it is solvable in pseudo-polynomial time for each m ≤ 3. We give a positive answer to the long-standing open question whether this problem is strongly NP-complete for m = 4. As a second result, we improve the lower bound of $\frac {12}{11}$ for approximating pseudo-polynomial Strip Packing to $\frac {5}{4}$. Since the best known approximation algorithm for this problem has a ratio of $\frac {5}{4} + \varepsilon$, this result almost closes the gap between approximation ratio and inapproximability result. Both results are proved by a reduction from the strongly NP-complete problem 3-Partition.

1 Introduction

In the Parallel Task Scheduling problem denoted as P|size_j|C_max in the three-field-notation, a set of jobs J has to be scheduled on m machines minimizing the makespan C_max. Each job j ∈ J has a processing time $p(j) \in \mathbb {N}$ and requires $q(j) \in \mathbb {N}$ machines. A schedule S is given by two functions $\sigma : J \rightarrow \mathbb {N}$ and ρ : J → 2^{1,…,m}. The function σ maps each job to a start point in the schedule, while ρ maps each job to the set of machines it is processed on. We say a machine i contains a job j ∈ J if i ∈ ρ(j). A schedule is feasible if each machine processes at most one job at a time and each job is processed on the required number of machines (i.e. |ρ(j)| = q(j)). The objective is to find a feasible schedule S minimizing the makespan C_max := maxj∈J(σ(j) + p(j)).

In 1989, Du and Leung [9] proved the Parallel Task Scheduling problem P|size_j|C_max to be strongly NP-complete for all m ≥ 5, while P|size_j|C_max is solvable by a pseudo-polynomial time algorithm for all m ≤ 3. In this paper, we address the case of m = 4, which has been open since and prove:

Theorem 1

Parallel Task Scheduling on 4 machines is stronglyNP-complete.

Building on this result, we can prove a lower bound for the absolute approximation ratio of pseudo-polynomial time algorithms for the Strip Packing problem, where an algorithm A has absolute approximation ratio α if A(I)/OPT(I) ≤ α for all instances I of the given problem. In the Strip Packing problem a set of rectangular items I has to be placed into a strip of width $W \in \mathbb {N}$ and infinite height. Each item i ∈ I has a width $w(i) \in \mathbb {N}_{\leq W}$ and a height $h(i) \in \mathbb {N}$. A packing of the items I into the strip is a function $\rho : I \rightarrow \mathbb {Q}_{0} \times \mathbb {Q}_{0}$, which places the items axis-parallel into the strip by assigning the left bottom corner of an item to a position in the strip such that for each item i ∈ I with ρ(i) = (x_i,y_i) we have x_i + w(i) ≤ W. We say two items i,j ∈ Ioverlap if they share an inner point. A packing is feasible if no two items overlap. The height of a packing is defined as H := maxi∈Iy_i + h(i). The objective is to find a feasible packing of the items I into the strip that minimizes the packing height. If all item sizes are integral, we can transform feasible packings to packings where all positions are integral without enlarging the packing height [5]. Therefore, we can assume that we have packings of the form $\rho : I \rightarrow \mathbb {N}_{0} \times \mathbb {N}_{0}$.

Lately, pseudo-polynomial time algorithms for Strip Packing where the width of the strip is allowed to appear polynomially in the running time of the algorithm, while it appears only logarithmically in the input size of the instance, gained high interest. In a series of papers [11, 20, 21, 23, 26], the best approximation ratio was improved to $\frac {5}{4} +\varepsilon$. On the other hand, it is not possible to find an algorithm with approximation ratio better than $\frac {12}{11}$, except P = NP [1]. In this paper, we improve this lower bound to $\frac {5}{4}$, which almost closes the gap between lower bound and best algorithm (Fig. 1).

Theorem 2

It is NP-Hardto find a pseudo-polynomial time approximation algorithm forStrip Packing with an absolute approximation ratio strictly betterthan$\frac {5}{4}$.

Fig. 1

The upper and lower bounds for the best possible approximation for pseudo-polynomial Strip Packing achieved so far

1.1 Related Work

Parallel Task Scheduling

In 1989, Du and Leung [9] proved Parallel Task Scheduling Pm|size_j|C_max to be strongly NP-complete for all m ≥ 5, while it is solvable by a pseudo-polynomial time algorithm for all m ≤ 3. Amoura et al. [2], as well as Jansen and Porkolab [19], presented a polynomial-time approximation scheme (in short PTAS) for the case that m is a constant. A PTAS is a family of polynomial-time algorithms that finds a solution with an approximation ratio of (1 + ε) for any given value ε > 0. If m is polynomially bounded by the number of jobs, a PTAS exists [23]. Nevertheless, if m is arbitrarily large, the problem gets harder. By a simple reduction from the Partition problem, one can see that there is no polynomial time algorithm with approximation ratio smaller than $\frac {3}{2}$. Parallel Task Scheduling with arbitrarily large m has been widely studied [10, 12, 25, 31]. The algorithm with the best known absolute approximation ratio of $\frac {3}{2}+\varepsilon$ was presented by Jansen [17].

Strip Packing

The Strip Packing problem was first studied in 1980 by Baker et al. [4]. They presented an algorithm with an absolute approximation ratio of 3. This ratio was improved by a series of papers [8, 16, 27,28,29]. The algorithm with the best known absolute approximation ratio by Harren, Jansen, Prädel and van Stee [15] achieves a ratio of $\frac {5}{3} +\varepsilon$. By a simple reduction from the Partition problem, one can see that it is impossible to find an algorithm with better approximation ratio than $\frac {3}{2}$, unless P = NP.

For this problem also asymptotic approximation algorithms have been studied. An algorithm for a minimization problem has an asymptotic approximation ratio of α, if there is a constant c (which might depend on ε or the maximal occurring item height h_max) such that the objective value A(I) computed by the algorithm is bounded by α OPT(I) + c. The lower bound of $\frac {3}{2}$ does not hold for asymptotic approximation ratios and they have been studied in various papers [3, 8, 14]. Kenyon and Rémila [24] presented an asymptotic fully polynomial approximation scheme (in short AFPTAS) with additive term $\mathcal {O}(h_{\max }/\varepsilon ^{2})$, where h_max is the largest occurring item height. An approximation scheme is fully polynomial if its running time is polynomial in 1/ε as well. This algorithm was simultaneously improved by Sviridenko [30] and Bougeret et al. [6] to an algorithm with an additive term of $\mathcal {O}(h_{\max }\log (1/\varepsilon )/\varepsilon )$. Furthermore, at the expense of the running time, Jansen and Solis-Oba [22] presented an asymptotic PTAS with an additive term of h_max.

Recently, the focus shifted to pseudo-polynomial time algorithms. Jansen and Thöle [23] presented an pseudo-polynomial time algorithm with approximation ratio of $\frac {3}{2} + \varepsilon$. Later Nadiradze and Wiese [26] presented an algorithm with ratio $\frac {7}{5} + \varepsilon$. Its approximation ratio was independently improved to $\frac {4}{3} + \varepsilon$ by Gálvez et al. [11] and by Jansen and Rau [21]. 5/4 + ε is the best approximation ratio so far, achieved by an algorithm by Jansen and Rau [20]. All these algorithms have a polynomial running time if the width of the strip W is bounded by a polynomial in the number of items.

In contrast to Parallel Task Scheduling, Strip Packing cannot be approximated arbitrarily close to 1, if we allow pseudo-polynomial running time. This was proved by Adamaszek et al. [1] by presenting a lower bound of $\frac {12}{11}$. As a consequence, Strip Packing admits no quasi-polynomial time approximation scheme, unless NP ⊆ DTIME(2^polylog(n)). For an overview on 2-dimensional packing problems and open questions regarding these problems, we refer to the survey by Christensen et al. [7].

1.2 Organization of this Paper

In Section 2, we will prove Theorem 1 by a reduction from the strongly NP-complete problem 3-Partition. First, we describe the jobs to construct for this reduction. Afterward, we prove: if the 3-Partition instance is a Yes-instance, then there is a schedule with a specific makespan, and if there is a schedule with this specific makespan then the 3-Partition instance has to be a Yes-instance. While the first claim can be seen directly, the proof of the second claim is more involved. Proving the second claim, we first show that it can be w.l.o.g. supposed that each machine contains a certain set of jobs. In the next step, we prove some implications on the order in which the jobs appear on the machines which finally leads to the conclusion that the 3-Partition instance has to be a Yes-instance. In Section 3 we discuss the implications for the inapproximability of pseudo-polynomial Strip Packing.

2 Hardness of Scheduling Parallel Tasks

In this Section, we prove Theorem 1 by a reduction from the 3-Partition problem. In this problem, we are given a list $\mathcal {I} = (\iota _{1},\dots ,\iota _{3z})$ of 3z positive integers with ${\sum }_{i = 1}^{3z}\iota _{i} = zD$ and D/4 < ι_i < D/2 for each 1 ≤ i ≤ 3z. The problem is to decide whether there exists a partition of the set I = {1,…,3z} into sets I₁,…,I_z such that ${\sum }_{i \in I_{j}} \iota _{i} = D$ for each 1 ≤ j ≤ z. This problem is strongly NP-complete see [13] problem [SP15]. Hence, it cannot be solved in pseudo-polynomial time, unless P = NP.

Before we start constructing the reduction, we introduce some notations. Let j ∈ J and J^′⊆ J. We define the work of j as w(j) := p(j) ⋅ p(j) and the total work of J^′ as $w(J^{\prime }) := {\sum }_{j \in J^{\prime }} w(j)$. For a given schedule S = (σ,ρ), we denote by n_j(J^′) the number of jobs from the set J^′ that are finished before the start of the job j, i.e., n_j(J^′) = |{i ∈ J^′ : σ(i) + p(i) ≤ σ(j)}|. Furthermore, we will use a notation defined in [9] for swapping a part of the content of two machines; let j ∈ J be a job that is processed by at least two machines, M and M^′, with start point σ(j). We can swap the content of the machines M and M^′ after time σ(j) without violating any scheduling constraint. We define this swapping operation as SWAP(σ(j),M,M^′).

The main idea of our reduction is to construct a set of structure jobs. These structure jobs have the property that each possible way to schedule them with the optimal makespan leaves z gaps, each with processing time D, i.e., it happens exactly at z distinct times that a machine is idle, and the duration of each idle time is exactly D, see Fig. 2 at the hatched areas. As a consequence, partition jobs, which have processing times equal to the 3-Partition numbers, can only be scheduled with the desired makespan if the 3-Partition instance is a Yes-instance.

Fig. 2

Packing of structure jobs with gaps (hatched area) for 3-Partition items. The items in the green area (left) are repeated z times. With the displayed choice of processing times, the items in the red area (right) can be rotated by 180 degrees such that α is scheduled on M₄ after the job in B and β is scheduled on M₁ before the job in A

2.1 Construction

In this section, we will construct a scheduling instance for P4|size_j|C_max from a given 3-Partition instance. In the following two paragraphs, we will give an intuition which jobs we introduce why with which processing time. An overview of the introduced jobs and their processing times can be found in Table 1 and the fourth paragraph of this section.

Table 1 Overview of the generated jobs

Given a 3-Partition instance, we construct ten disjoint sets of jobs A, B, a, b, c, α, β, γ, δ, and λ, which will be forced to be scheduled as in Fig. 2 by choosing suitable processing times. In the first step, we add a unique token to the processing time of each set of jobs to be processed simultaneously to ensure that these jobs have to be processed at the same time in every schedule. As this token, we choose D^x, where x ∈{2,…,7} and D is the required sum of the items in each partition set. For example for jobs in B we define a processing time of D², while we define the processing time of each job in α such that it contains D⁷ + D² + D³, see Fig. 2.

Unfortunately, the tokens D² to D⁷ are not enough to ensure that the schedule in Fig. 2 is the only possible one. Consider the jobs contained in the red area (right) in Fig. 2. With the choice of processing times as shown in the figure, it is possible to rotate the red area by 180 degrees such that α is scheduled on M₄ and β is scheduled on M₁. After rotating every second of these set of jobs, it is possible to reorder the jobs, and fusing the areas for the 3-Partition items into two or three areas, see Fig. 3. To prohibit this possibility to rotate, we introduce one further token D⁸. This token is added to the processing time of some jobs such that the combined processing time of the jobs in the red area on M₁ differs from the one on M₄. To ensure this, we have to give up the property that in each of the sets A,B,a,b,c,α,β,γ,δ all jobs have the same processing time. More precisely, each job in the sets c, δ, and γ receives a unique processing time.

Fig. 3

A reordering we have to prohibit, because it fuses the areas for 3-Partition items into two areas, one area on M₂ and one area on M₃ if z is even, and into three areas if z is odd

In the following, we describe the jobs constructed for the reduction. We introduce two sets A and B of 3-processor jobs, three sets a, b and c of 2-processor jobs, and five sets α, β, γ, δ, and λ of 1-processor jobs. The description of the jobs inside these sets and their processing times can be found in Table 1. We call these jobs structure jobs. Additionally, we generate for each i ∈{1,…,3z} one 1-processor job, called partition job, with processing time ι_i and define P as the set containing all partition jobs. Last, we define W := (z + 1)(D² + D³ + D⁴) + z(D⁵ + D⁶ + D⁷) + z(7z + 1)D⁸. Note that the total work of the introduced jobs adds up to 4W, i.e., a schedule without idle times has makespan W while each schedule containing idle times has a makespan, which is strictly larger than W.

Given a set $J \subseteq \bigcup \{A , B , a , b , c , \alpha , \beta , \delta , \lambda \}$ of the jobs constructed this way, their total processing time p(J) has the form ${\sum }_{i = 2}^{7} x_{i}D^{i}$, with $x_{i} \in \mathbb {N}$ for i = 2,…,7. For each occurring x_i, we want the tokens Dⁱ to be unique in the way that x_iDⁱ < D^i+ 1 for each possible occurring sum of processing times of structure jobs and each i = 2,…,7. Let k_max be the largest occurring coefficient in the sum of processing times of any given subset of the generated structure jobs, i.e., k_max ≤ 4z(7z + 1). If D ≤ k_max, we scale each number in the 3-Partition instance with k_max, before constructing the jobs. As a result in the scaled instance it holds that k_maxDⁱ < D^i+ 1. Since k_max depends polynomially on z, the input size of the scaled instance will still depend polynomially on the input size of the original instance. In the following, let us assume that D > k_max in the given 3-Partition instance. Note that in a schedule without idle times, a machine cannot contain a set of jobs, with processing times that add up to a value where one of the coefficients is larger than the corresponding one in W.

In the following two subsections, we will prove that there is a schedule with makespan W if and only if the 3-Partition instance is a Yes-instance.

2.2 Partition to Schedule

Let $\mathcal {I}$ be a Yes-instance of 3-Partition with partition I₁,…,I_z. One can easily verify that the structure jobs can be scheduled as shown in Fig. 4. After each job γ_j, for each 1 ≤ j ≤ z, we have a gap with processing time D. We schedule the partition jobs with indices out of I_j directly after γ_j. Their processing times add up to D, and therefore they fit into the gap. The resulting schedule has a makespan of W.

Fig. 4

An optimal schedule, for a Yes-instance, where $t_0 := {\sum }_{k = 2}^4D^k+ zD^8$, $t_1 := {\sum }_{k = 2}^7D^k + (7z-1)D^8$, and $t_2 := {\sum }_{k = 2}^7D^k + 7zD^8$

2.3 Schedule to Partition

Let a schedule S = (σ,ρ) with makespan W be given. We will now step by step describe why $\mathcal {I}$ has to be a Yes-instance of 3-Partition. In the first step, we will show that we can transform the schedule such that each machine contains a certain set of jobs.

Lemma 1

We can transform the schedule S into a schedule such thatM₁contains the jobs$\bigcup \{A , a , \alpha , \lambda _1\}$,M₂contains the jobs$\bigcup \{A , B , c , \check {a} , \check {b} , \check {\gamma } , \check {\delta }\}$,M₃contains the jobs$\bigcup \{A , B , c , \hat {a} , \hat {b} , \hat {\gamma } , \hat {\delta }\}$andM₄contains the jobs$\bigcup \{B , b , \beta , \lambda _2\}$,where$a = \check {a} \dot \cup \hat {a}$,$b = \check {b} \dot \cup \hat {b}$,$\gamma = \check {\gamma } \dot \cup \hat {\gamma }$,and$\delta = \check {\delta } \dot \cup \hat {\delta }$.Furthermore, if the jobs are scheduled in this way, it holdsthat$|\check {a}| = |\check {\gamma }|$and$|\check {b}| = |\check {\delta }|$.

Proof

First, we will show that the content of the machines can be swapped, without enlarging the makespan, such that M₂ and M₃ each contain all the jobs in A ∪ B. We will show this claim inductively. For the induction basis, consider the job in A ∪ B with the smallest starting point in this set. We can swap the complete content of the machines such that M₂ and M₃ contain this job. For the induction step, let us assume that the first i jobs from the set A ∪ B are scheduled on the machines M₂ and M₃. Consider the (i + 1)st job. This job is either already scheduled on the machines M₂ and M₃, and we do nothing, or there is one machine M ∈{M₂,M₃}, which does not contain this job. Let us assume the latter. Let M^′∈{M₁,M₄} be the third machine containing the i-th job in A ∪ B. We transform the schedule such that M₂ and M₃ contain the (i + 1)-th job, by performing a swapping operation SWAP(σ(x_i),M,M^′). After this swap M, and hence both machines M₂ and M₃, will contain the (i + 1)st job, which concludes the proof that the content of the machines can be swapped such that M₂ and M₃ each contain all the jobs in A ∪ B.

In the next step, we will determine the set of jobs contained by the machines M₁ and M₄ using the token D⁸. Besides the jobs in A ∪ B, M₂ and M₃ contain jobs with total processing time of (z + 1)D³ + zD⁵ + zD⁶ + zD⁷ + z(7z + 1)D⁸. Hence, M₂ and M₃ cannot contain jobs in α ∪ β ∪ λ, since their processing times contain D² or D⁴. Therefore, each job in α ∪ β ∪ λ has to be processed either on M₁ or on M₄. Furthermore, each job in A ∪ B has to be processed on one of the machines M₁ or M₄ additional to the machines M₂ and M₃ since each of these jobs needs three machines to be scheduled. In addition to the jobs jobs in $\bigcup \{A , B , \alpha , \beta , \lambda \}$, M₁ and M₄ together contain further jobs with a total processing time of zD⁵ + 2zD⁶ + zD⁷ + 6z²D⁸. Exclusively jobs from the set a ∪ b have a processing time containing D⁶. Therefore, each machine processes z of them. Hence corresponding to D⁸, a total processing time of 3z²D⁸ is used by jobs in the set a ∪ b on each machine. This leaves a processing time of (4z² + z)D⁸ for the jobs in α ∪ β ∪ λ on M₁ and M₄. All the 2(z + 1) jobs in α ∪ β ∪ λ contain D³ in their processing time. Therefore, each machine M₁ and M₄ processes exactly z + 1 of them. We will swap the content of M₁ and M₄ so that λ₁ is scheduled on M₁. As a consequence, M₁ processes z jobs from the set α ∪ β ∪{λ₂}, with processing times that sum up to 4z²D⁸ in the D⁸ component. The jobs in α have with 4zD⁸ the largest amount of D⁸ in their processing time. Therefore, M₁ has to process all of them since z ⋅ 4zD⁸ = 4z²D⁸, while M₄ contains the jobs in β ∪{λ₂}. Since we have p(α ∪{λ₁}) = (z + 1)D² + (z + 1)D³ + zD⁷ + z(4z + 1)D⁸, jobs from the set A ∪ B ∪ a ∪ b with total processing time of (z + 1)D⁴ + zD⁵ + zD⁶ + 3z²D⁸ have to be scheduled on M₁. In this set, the jobs in A are the only jobs with processing times containing D⁴, while the jobs in a are the only jobs with a processing time containing D⁵. As a consequence, M₁ processes the jobs $\bigcup \{A , a , \alpha , \{\lambda _1\}\}$. Analogously we can deduce that M₄ processes the jobs $\bigcup \{B , b , \beta , \{\lambda _2\}\}$.

In the last step, we will determine which jobs are scheduled on M₂ and M₃. As shown before, each of them contains the jobs A ∪ B. Furthermore, since no job in c is scheduled on M₁ or M₄, and they require two machines to be processed, machines M₂ and M₃ both contain the set c. Additionally, each job in γ ∪ δ has to be scheduled on M₂ or M₃ since they are not scheduled on M₁ or M₄. Each job in a ∪ b occupies one of the machines M₁ and M₄. The second machine they occupy is either M₂ or M₃. Let $\check {a} \subseteq a$ be the set of jobs that is scheduled on M₂ and $\hat {a} \subseteq a$ be the set that is scheduled on M₃. Clearly $a =\check {a} \dot \cup \hat {a}$. We define the sets $\hat {b}, \check {b}, \hat {\delta },\check {\delta }, \hat {\gamma }$, and $\check {\gamma }$ analogously. By this definition, M₂ contains the jobs $\bigcup \{A , B , \check {a} , \check {b} , \check {\delta } , \check {\gamma } , c\}$ and M₃ contains the jobs $\bigcup \{A , B , \hat {a} , \hat {b} , \hat {\delta } , \hat {\gamma } , c\}$.

We still have to prove that $|\check {a}| = |\check {\gamma }|$ and $|\check {b}| = |\check {\delta }|$. First, we notice that $|\check {a}| + |\check {b}| = z$ since these jobs are the only jobs with a processing time containing D⁶. So besides the jobs in $\bigcup \{A , B, c , \check {a} , \check {b}\}$, M₂ contains jobs with total processing time of $(z-|\check {a}|)D^5 + (z-|\check {b}|)D^7 + {\sum }_{i = 1}^z(3z-i)D^8 =|\check {b}| D^5 + |\check {a}|D^7 + {\sum }_{i = 1}^z(3z-i)D^8$. Since the jobs in δ are the only jobs in δ ∪ γ having a processing time containing D⁵, we have $|\check {\delta }|= |\check {b}|$ and analogously $|\check {\gamma }|= |\check {a}|$. □

In the next steps, we will prove that it is possible to transform the order in which the jobs appear on the machines to the one in Fig. 4. Notice that, since there is no idle time in the schedule, each start point of a job i is given by the sum of processing times of the jobs on the same machine scheduled before i. So the start position σ(i) of a job i has the form

$$\sigma(i) = x_{0} + x_{2}D^{2}+ x_{3}D^{3}+ x_{4}D^{4}+ x_{5}D^{5}+ x_{6}D^{6}+ x_{7}D^{7}+ x_{8}D^{8}$$

for − zD ≤ x₀ ≤ zD < D² and 0 ≤ x_j ≤ 4z(7z + 1) ≤ D for each 2 ≤ j ≤ 8. Note that − zD ≤ x₀ since the processing time of the jobs in γ is given by D⁷ + (3z − i1)D⁸ − D and there are at most z of them while x₀ ≤ zD since the total sum of processing times of partition jobs is at most zD. This equation for σ(i) allows us to analyze how many jobs of which type are scheduled before a job i on the machine that processes i. For example, let us look at the coefficient x₄. This value is just influenced by jobs with processing times containing D⁴. The only jobs with these processing times are the jobs in the set A ∪ β ∪{λ₂}. The jobs in β ∪{λ₂} are just processed on M₄, while the jobs in A each are processed on the three machines M₁, M₂, and M₃. Therefore, we know that at the starting point σ(i) of a job i scheduled on machines M₁, M₂ or M₃ we have that x₄ = n_i(A). Furthermore, if i is scheduled on M₄ we know that x₄ = n_i(β) + n_i({λ₂}). In Table 2, we present which sets influences which coefficients in which way when job i is started on the corresponding machine.

Table 2 Overview of the values of the coefficients at the start point of a job i, if i is scheduled on machine M_j

Let us consider the start point σ(i) of a job i that uses more than one machine. We know that σ(i) is the same on all the used machines and therefore the coefficients are the same as well. In the following, we will study for each of the sets A, B, a, b, c what we can conclude for the starting times of these jobs. For each of the sets, we will present an equation, which holds at the start of each item in this set. These equations give us a strong set of tools for our further arguing.

Lemma 2

Let beA^′∈ A,B^′∈ B,a^′∈ a,b^′∈ b,andc^′∈ c.It holds that

$$ {n}_{A^{\prime}}(c) - {n}_{A^{\prime}}(\{\lambda_{1}\}) = {n}_{A^{\prime}}(B) - {n}_{A^{\prime}}(\{\lambda_{1}\}) ={n}_{A^{\prime}}(\alpha) = {n}_{A^{\prime}}(b) = {n}_{A^{\prime}}(a)\text{,} $$

(1)

$$ {n}_{B^{\prime}}(c) - {n}_{B^{\prime}}(\{\lambda_{2}\}) = {n}_{B^{\prime}}(A) - {n}_{B^{\prime}}(\{\lambda_{2}\}) = {n}_{B^{\prime}}(\beta) = {n}_{B^{\prime}}(a) = {n}_{B^{\prime}}(b)\text{,} $$

(2)

$$ {n}_{a^{\prime}}(B) = {n}_{a^{\prime}}(\alpha) + {n}_{a^{\prime}}(\{\lambda_{1}\})) = {n}_{a^{\prime}}(c)\text{,} $$

(3)

$$ {n}_{b^{\prime}}(A) = {n}_{b^{\prime}}(\beta) + {n}_{b^{\prime}}(\{\lambda_{2}\}) = {n}_{b^{\prime}}(c)\text{,} $$

(4)

and

$$ {n}_{c^{\prime}}(b) = {n}_{c^{\prime}}(a)\text{.} $$

(5)

Proof

We will prove these equations using the conditions for the coefficients from Table 2. We write $={~}_{x_{i}}$ when the coefficient x_i is the reason why the equality is true.

To prove (1), we will consider the start points of the jobs in A. Each job A^′∈ A is scheduled on machines M₁, M₂ and M₃. As a consequence the coefficients on all these tree machines have to be the same, when the job A^′ starts. Therefore, we know that at σ(A^′) we have

$$ {n}_{A^{\prime}}(B) ={~}_{x_{2}} {n}_{A^{\prime}}(\alpha) + {n}_{A^{\prime}}(\{\lambda_{1}\}) ={~}_{x_{3}} {n}_{A^{\prime}}(c)\mathrm{.} $$

(i)

Furthermore, we know that

$${n}_{A^{\prime}}(a) ={~}_{x_{6}} {n}_{A^{\prime}}(\check{a}) + {n}_{A^{\prime}}(\check{b}) ={~}_{x_{6}} {n}_{A^{\prime}}(\hat{a}) + {n}_{A^{\prime}}(\hat{b})\mathrm{.} $$

Since ${n}_{A^{\prime }}(a) = {n}_{A^{\prime }}(\check {a}) + {n}_{A^{\prime }}(\hat {a})$ and ${n}_{A^{\prime }}(b) = {n}_{A^{\prime }}(\check {b}) + {n}_{A^{\prime }}(\hat {b})$, because $a = \check {a} \dot \cup \hat {a}$ and $b = \check {b} \dot \cup \hat {b}$, we can deduce that ${n}_{A^{\prime }}(\hat {a}) = {n}_{A^{\prime }}(\check {b})$ and ${n}_{A^{\prime }}(\check {a}) = {n}_{A^{\prime }}(\hat {b})$ and therefore

$$ {n}_{A^{\prime}}(a) = {n}_{A^{\prime}}(b)\mathrm{.} $$

(ii)

Additionally, we know that

$${n}_{A^{\prime}}(\alpha) ={~}_{x_{7}} {n}_{A^{\prime}}(\check{b}) + {n}_{A^{\prime}}(\check{\gamma}) ={~}_{x_{7}} {n}_{A^{\prime}}(\hat{b}) + {n}_{A^{\prime}}(\hat{\gamma})\mathrm{.} $$

Thanks to this equality, we can show that ${n}_{A^{\prime }}(\alpha ) = {n}_{A^{\prime }}(b)$: First, we show ${n}_{A^{\prime }}(\alpha ) \geq {n}_{A^{\prime }}(b)$. Let b^′∈ b be the last job in b scheduled before A^′ if there is any. Let us w.l.o.g assume that $b^{\prime } \in \hat {b}$. It holds that

$$\begin{array}{@{}rcl@{}} {n}_{A^{\prime}}(b) &&\overset{\sigma(b^{\prime}) < \sigma(A^{\prime})}{=} {n}_{b^{\prime}}(b) + 1 ={~}_{x_{7}} {n}_{b^{\prime}}(\hat{b}) + {n}_{b^{\prime}}(\hat{\gamma}) + 1 \\ &&\overset{\sigma(b^{\prime}) < \sigma(A^{\prime})}{\leq} {n}_{A^{\prime}}(\hat{b}) + {n}_{A^{\prime}}(\hat{\gamma}) ={~}_{x_{7}} {n}_{A^{\prime}}(\alpha) \mathrm{.} \end{array} $$

If there is no such b^′ we have ${n}_{A^{\prime }}(b) = 0 \leq {n}_{A^{\prime }}(\alpha )$. Next, we show ${n}_{A^{\prime }}(\alpha ) \leq {n}_{A^{\prime }}(b)$. Let b^″∈ b be the first job in b scheduled after A if there is any. Let us w.l.o.g assume that $b^{\prime \prime } \in \check {b}$. It holds that

$${n}_{A^{\prime}}(b) \overset{\sigma(A^{\prime}) < \sigma(b^{\prime\prime})}{=} {n}_{b^{\prime\prime}}(b) ={~}_{x_{7}} {n}_{b^{\prime\prime}}(\check{b}) + {n}_{b^{\prime\prime}}(\check{\gamma}) \overset{\sigma(A^{\prime}) < \sigma(b^{\prime\prime})}{\geq}{n}_{A^{\prime}}(\check{b}) + {n}_{A^{\prime}}(\check{\gamma}) ={~}_{x_{7}} {n}_{A^{\prime}}(\alpha)\mathrm{.} $$

If there is no such b^″, we have ${n}_{A^{\prime }}(b) = z \geq {n}_{A^{\prime }}(\alpha )\mathrm {.}$ As a consequence, we have

$$ {n}_{A^{\prime}}(\alpha) = {n}_{A^{\prime}}(b)\mathrm{.} $$

(iii)

In summary, we can deduce that

$${n}_{A^{\prime}}(c) - {n}_{A^{\prime}}(\{\lambda_{1}\}) ={~}_{(\mathrm{i})} {n}_{A^{\prime}}(B) - {n}_{A^{\prime}}(\{\lambda_{1}\}) ={~}_{(\mathrm{i})} {n}_{A^{\prime}}(\alpha) ={~}_{(\text{iii})} {n}_{A^{\prime}}(b) ={~}_{(\text{ii})} {n}_{A^{\prime}}(a)\mathrm{,} $$

which concludes the proof of (1). Since the Table 2 is symmetrically, we can deduce correctness of (2) analogously.

Next we prove the (3) and (4). Each item a^′∈ a is scheduled on machine M₁ and on one of the machines M₂ or M₃. For both possibilities $a \in \hat {a}$ or $a\in \check {a}$, we can deduce (3) directly from the Table 2:

$${n}_{a^{\prime}}(B) ={~}_{x_{2}} {n}_{a^{\prime}}(\alpha) + {n}_{a^{\prime}}(\{\lambda_{1}\}) ={~}_{x_{3}} {n}_{a^{\prime}}(c) \mathrm{.} $$

Analogously, we deduce (4):

$${n}_{b^{\prime}}(A) ={~}_{x_{4}} {n}_{b^{\prime}}(\beta) + {n}_{b^{\prime}}(\{\lambda_{2}\}) ={~}_{x_{3}} {n}_{b^{\prime}}(c) \mathrm{.} $$

Last, we prove (5). Each item c^′∈ c is scheduled on M₂ and M₃. Let a^′∈ a be the job with the smallest σ(a^′) ≥ σ(c^′). Let us w.l.o.g assume that $a^{\prime } \in \hat {a}$. It holds that

$$\begin{array}{@{}rcl@{}} {n}_{c^{\prime}}(\check{a}) + {n}_{c^{\prime}}(\check{b}) &=&{~}_{{x}_{6}} {n}_{{c}^{\prime}}(\hat{a}) + {n}_{{c}^{\prime}}(\hat{b}) \leq {n}_{a^{\prime}}(\hat{a}) + {n}_{a^{\prime}}(\hat{b}) ={~}_{{x}_{6}} {n}_{a^{\prime}}(a)\\ & =& {n}_{a^{\prime}}(\hat{a}) + {n}_{a^{\prime}}(\check{a}) = {n}_{c^{\prime}}(\hat{a}) + {n}_{c^{\prime}}(\check{a})\mathrm{.} \end{array} $$

As a consequence, we have ${n}_{c^{\prime }}(\check {b}) \leq {n}_{c^{\prime }}(\hat {a})$ and ${n}_{c^{\prime }}(\hat {b}) \leq {n}_{c^{\prime }}(\check {a})$. Analogously, let b^′∈ b be the job with the smallest σ(b^′) ≥ σ(c^′). Let us w.l.o.g assume that $b^{\prime } \in \check {b}$. It holds that

$$\begin{array}{@{}rcl@{}} {n}_{c^{\prime}}(\hat{a}) + {n}_{c^{\prime}}(\hat{b}) &=&{~}_{x_{6}} {n}_{c^{\prime}}(\check{a}) + {n}_{c^{\prime}}(\check{b}) \leq {n}_{b^{\prime}}(\check{a}) + {n}_{b^{\prime}}(\check{b}) ={~}_{x_{6}} {n}_{b^{\prime}}(b)\\ &=& {n}_{b^{\prime}}(\hat{b}) + {n}_{b^{\prime}}(\check{b}) = {n}_{c^{\prime}}(\hat{b}) + {n}_{c^{\prime}}(\check{b}). \end{array} $$

Therefore, ${n}_{c^{\prime }}(\check {a}) \leq {n}_{c^{\prime }}(\hat {b})$ and ${n}_{c^{\prime }}(\hat {a}) \leq {n}_{c^{\prime }}(\check {b})$. As a consequence from both equations, we have ${n}_{c^{\prime }}(\check {a}) = {n}_{c^{\prime }}(\hat {b})$ and ${n}_{c^{\prime }}(\hat {a}) = {n}_{c^{\prime }}(\check {b})$. Together with ${n}_{c^{\prime }}(\check {a}) + {n}_{c^{\prime }}(\check {b}) ={~}_{x_6} {n}_{c^{\prime }}(\hat {a}) + {n}_{c^{\prime }}(\hat {b})$ (5), i.e., ${n}_{c^{\prime }}(b) = {n}_{c^{\prime }}(a)$, is a direct consequence. □

These equations give us the tools to analyze the given schedule with makespan W. To this point we have proved that we can assume that the machines M₁ to M₄ contain the correct sets of jobs. Consider the jobs from the sets A, B, a, b, and c. Note that if one job from the set A ∪ B ∪ a ∪ b ∪ c is started no (other) job from the set A ∪ B ∪ c can be processed at the same time, since these jobs will always share at least one machine when processed. The next step is to prove that the jobs in these sets appear in the correct order, namely $B_0,c_0,A_0,\binom {b_1}{a_1},B_1, c_1,A_1, \dots$ see Fig. 5. We will prove this claim in two steps. First, we will show that in this schedule the first and last jobs have to be elements from the set A ∪ B (see Lemma 3). Afterward, we will prove that between two successive jobs from the set A there appears exactly one jobs from each set B, a, b, and c, and prove an analogue statement for two successive jobs from the set B (see Lemma 4).

Fig. 5

The processing order of the jobs in the sets A, B, a, b, and c

With the knowledge gathered in the proofs of Lemma 3 and Lemma 4, we can prove that the given schedule can be transformed such that all jobs are scheduled contiguously, i.e., on an interval of machines, and that $\mathcal {I}$ has to be a Yes-instance of 3-Partition (see Lemma 5). In the following, we write = _(l), when the equation (l) is the reason why the equality is true.

Lemma 3

One jobi ∈ A ∪ Bis the first job which is processed, i.e.,σ(i) = 0.Furthermore one job from the setj ∈ A ∪ Bis the last job to be processed in the schedule, i.e.,σ(i) + p(j) = W.

Proof

Let i := argminι∈A∪Bσ(ι) be the job with the smallest start point in A ∪ B, (i.e., n_i(A) = 0 = n_i(B)). If i ∈ A it holds that

$$0= {n}_{i}(B) ={~}_{(1)} {n}_{i}(\alpha) + {n}_{i}(\{\lambda_{1}\}) ={~}_{(1)} {n}_{i}(a) + {n}_{i}(\{\lambda_{1}\}) $$

and therefore n_i(a) = n_i(α) = 0 = n_i({λ₁}). The jobs a ∪ α ∪{λ₁}∪ A are the only jobs, which are contained on machine M₁. Since n_i(A) = 0 as well, it has to be that σ(i) = 0. If i ∈ B we can prove σ(i) = 0 analogously using equality (2).

Since the schedule stays valid if we mirror the schedule such that the new start points are s^′(i) = W − σ(i) − p(i) for each job i, the last job has to be in the set A ∪ B as well. □

Next, we will show that the items in the sets A and B have to be scheduled alternatingly. Let (A₀,…,A_z) be the set A and (B₀,…,B_z) be the set B each ordered by increasing size of the starting points. Simply swap the jobs if they do not have this order.

Lemma 4

Ifσ(B₀) = 0,it holds for each itemi ∈{0,…,z} that

$$ i= {n}_{A_{i}}(A) = {n}_{A_{i}}(B) - 1 = {n}_{A_{i}}(c) - 1 = {n}_{A_{i}}(\alpha) = {n}_{A_{i}}(b) = {n}_{A_{i}}(a)\mathrm{,} $$

(6)

and

$$ i= {n}_{B_{i}}(B) = {n}_{B_{i}}(A) = {n}_{B_{i}}(\beta) = {n}_{B_{i}}(c) = {n}_{B_{i}}(a) = {n}_{B_{i}}(b)\mathrm{,} $$

(7)

and ${n}_{A_{i}}(\{\lambda _1\})= 1$ as well as ${n}_{B_{i}}(\{\lambda _2\})= 0$.

Proof

We will prove this lemma by proving the following claim:

• Claim 1 If σ(B₀) = 0, it holds for each item i ∈{0,…,z} that

  $${n}_{A_{i}}(A) ={n}_{A_{i}}(B) - {n}_{A_{i}}(\{\lambda_{1}\}) $$

  and ${n}_{A_{i}}(\{\lambda _1\}) = 1$.

We will prove this claim inductively and per contradiction. Assume for contradiction that

$${n}_{A_{0}}(B) - {n}_{A_{0}}(\{\lambda_{1}\}) >{n}_{A_{0}}(A) = 0\mathrm{.} $$

Therefore, we have $1 \leq {n}_{A_0}(B) - {n}_{A_0}(\{\lambda _1\})\mathrm {.}$ Let a^′∈ a, b^′∈ b and c^′∈ c be the first started jobs in their sets. Since

$${n}_{A_{0}}(b) ={~}_{(1)} {n}_{A_{0}}(a) ={~}_{(1)} {n}_{A_{0}}(c) - {n}_{A_{0}}(\{\lambda_{1}\}) ={~}_{(1)} {n}_{A_{0}}(B) - {n}_{A_{0}}(\{\lambda_{1}\}) \geq 1\mathrm{,} $$

the jobs a^′,b^′ and c^′ start before A₀. It holds that ${n}_{b^{\prime }}(c) ={~}_{(4)} {n}_{b^{\prime }}(A) = 0\mathrm {.}$ Therefore, c^′ has to start after b^′ resulting in ${n}_{{c^{\prime }}}({b}) \geq 1$. Furthermore, we have ${n}_{{a^{\prime }}}({c}) ={~}_{(3)} {n}_{{a^{\prime }}}({B}) \geq 1.$ Hence, c^′ has to start before a^′ resulting in ${n}_{{c^{\prime }}}({a}) = 0$. In total we have $1 \leq {n}_{{c^{\prime }}}({b}) ={~}_{(5)} {n}_{{c^{\prime }}}({a}) = 0$, a contradiction. Therefore, we have ${n}_{{A_0}}({B}) - {n}_{{A_0}}({\{\lambda _{1}\}}) \leq {n}_{{A_0}}({A}) = 0$. As a consequence, it holds that $1 \leq {n}_{{A_0}}({B}) \leq {n}_{{A_0}}({\{\lambda _1\}}) \leq 1$ and we can conclude ${n}_{{A_0}}({B}) = 1 = {n}_{{A_0}}({\{\lambda _{1}\}})$ as well as ${n}_{{A_0}}({B}) - {n}_{{A_0}}({\{\lambda _1\}}) = {n}_{{A_0}}({A})$. Therefore $1 = {n}_{{A_{i}}}({\{\lambda _1\}})$ holds for all i ∈{0,…,z}. To this point we have proved the induction basis.

For the induction step it is enough to prove that ${n}_{A_{i}}(B) - 1 = {n}_{A_{i}}(A)$ for all i ∈{0,…,z}. To prove this, we first show that if this condition holds for for all i^′ up to an i ∈{0,…,z} we can derive the (6) and an equation which is similar to (7) for all these i^′. Choose i ∈{0,…,z} such that

$$ {n}_{A_{i^{\prime}}}(B) - 1 = {n}_{A_{i^{\prime}}}(A) $$

(8)

for all i^′∈{0,…,i}. A direct consequence from this equation is the (6) for all i^′∈{0,…,i}:

$$i^{\prime} = {n}_{A_{i}^{\prime}}(A) ={~}_{(8)} {n}_{A_{i}^{\prime}}(B) - 1 ={~}_{(1)} {n}_{A_{i}^{\prime}}(c) - 1 ={~}_{(1)} {n}_{A_{i}^{\prime}}(\alpha) ={~}_{(1)} {n}_{A_{i}^{\prime}}(b) ={~}_{(1)} {n}_{A_{i}^{\prime}}(a)\mathrm{.} $$

Furthermore, we have ${n}_{B_{i}}(B) = i = {n}_{A_{i}}(A) = {n}_{A_{i}}(B) -1\mathrm {.}$ Therefore B_i has to be scheduled before A_i. Additionally, we have ${n}_{B_{i}}(B)-1 = {n}_{B_{i-1}}(B) = i-1 = {n}_{A_{i-1}}(A) = {n}_{A_{i-1}}(B) -1\mathrm {,}$ so B_i has to be scheduled after A_i− 1. Therefore, we have ${n}_{{B_{i}}}({B}) = {n}_{B_{i}}(A)$ and the following equation is a consequence for all i^′∈{0,…,i}:

$$ \begin{array}{lll} i^{\prime} & = {n}_{B_{i^{\prime}}}(B) = {n}_{B_{i^{\prime}}}(A) ={~}_{(2)} {n}_{B_{i^{\prime}}}(c) ={~}_{(2)} {n}_{B_{i^{\prime}}}(\beta) + {n}_{B_{i^{\prime}}}(\{\lambda_{2}\})\\ & ={~}_{(2)} {n}_{B_{i^{\prime}}}(a) + {n}_{B_{i^{\prime}}}(\{\lambda_{2}\}) ={~}_{(2)} {n}_{B_{i^{\prime}}}(b) + {n}_{B_{i^{\prime}}}(\{\lambda_{2}\})\mathrm{.} \end{array} $$

(9)

We still have to prove Claim 1, to prove the lemma. To this point, we have proved the base of the induction. However, we still have to prove ${n}_{A_{i + 1}}(B) - 1 = {n}_{A_{i + 1}}(A)$ since we already know that ${n}_{A_{i}}(\{\lambda _1\}) = 1$ for all i ∈{0,…,z}. We will prove this in two steps:

• Claim 2${n}_{A_{i + 1}}(B) - 1 \leq {n}_{A_{i + 1}}(A)$

Assume for contradiction that ${n}_{A_{i + 1}}(B) -1 > {n}_{A_{i + 1}}(A).$ As a consequence, we have

$$1 = {n}_{A_{i + 1}}(A) - {n}_{A_{i}}(A) < {n}_{A_{i + 1}}(B) - 1 - ({n}_{A_{i}}(B) - 1) = {n}_{A_{i + 1}}(B) - {n}_{A_{i}}(B)\mathrm{,} $$

and hence, ${n}_{A_{i + 1}}(B) - {n}_{A_{i}}(B) \geq 2$. Therefore, there are jobs B_i+ 1,B_i+ 2 ∈ B that are scheduled between A_i and A_i+ 1. Since we have

$$\begin{array}{@{}rcl@{}} 2 & \leq& {n}_{A_{i}}(B) - 1 - ({n}_{A_{i}}(B) - 1) ={~}_{(1)} {n}_{A_{i}}(c) - 1 - ({n}_{A_{i + 1}}(c) - 1)\\ &=&{~}_{(1)} {n}_{A_{i}}(b) - {n}_{A_{i + 1}}(b) ={~}_{(1)} {n}_{A_{i}}(a) - {n}_{A_{i + 1}}(a) \end{array} $$

there have to be two jobs a^′,a^″∈ a, b^′,b^″∈ b and c^′,c^″∈ c that are scheduled between A_i and A_i+ 1 as well. W.l.o.g we assume that σ(a^′) ≤ σ(a^″), σ(b^′) ≤ σ(b^″) and σ(c^′) ≤ σ(c^″).

Next, we will deduce in which order the jobs a^′, a^″, b^′, b^″, c^′, c^″, B_i+ 1, and B_i+ 2 appear in the schedule. It holds that

$${n}_{b^{\prime\prime}}(c) ={~}_{(4)} {n}_{b^{\prime\prime}}(A) \overset{\sigma(A_{i}) < \sigma(b^{\prime\prime})}{=} {n}_{A_{i}}(A) + 1 ={~}_{(8)} {n}_{A_{i}}(B) ={~}_{(1)} {n}_{A_{i}}(c)\mathrm{} $$

since b^″ starts after A_i but before A_i+ 1. Therefore, b^′ and b^″ have to finish before c^′, i.e., σ(b^′) < σ(b^″) < σ(c^′), since no job from the set c can be scheduled between A_i and b^″. As a consequence, we have

$${n}_{c^{\prime}}(a) ={~}_{(5)} {n}_{c^{\prime}}(b) \overset{\sigma(A_{i}) < \sigma(b^{\prime}) < \sigma(b^{\prime\prime}) < \sigma(c^{\prime})}{\geq} {n}_{A_{i}}(b) + 2 ={~}_{(1)} {n}_{A_{i}}(a) + 2 \mathrm{.} $$

Hence, a^″ has to start before c^′ as well. Additionally, it holds that

$${n}_{B_{i + 2}}(c) ={~}_{(2)} {n}_{B_{i + 2}}(A) \overset{\sigma(A_{i})<\sigma(B_{i + 2})}{=} {n}_{A_{i}}(A) + 1 ={~}_{(8)} {n}_{A_{i}}(B) ={~}_{(1)} {n}_{A_{i}}(c)\mathrm{.}$$

since B_i+ 2 starts after A_i but before A_i+ 1. As a consequence, B_i+ 2 has to start before c^′. Additionally, it holds that

$${n}_{a^{\prime\prime}}(B) ={~}_{(3)} {n}_{a^{\prime\prime}}(c) \overset{\sigma(A_{i})<\sigma(a^{\prime\prime})<\sigma(c^{\prime})}{=} {n}_{A_{i}}(c) ={~}_{(1)} {n}_{A_{i}}(B)\mathrm{.}$$

Therefore, a^″ has to start before B_i+ 1, since there can not be a job from the set B scheduled between A_i and a^″.

To this point, we have deduced that the jobs have to appear in the following order in the schedule: A_i, a^′, a^″, B_i+ 1, B_i+ 2, c^′, c^″, A_i+ 1. However, this schedule is not feasible, since we have

$$\begin{array}{@{}rcl@{}} {n}_{A_{i}}(a) + 2 &&\overset{\sigma(A_{i})< \sigma(a^{\prime})<\sigma(a^{\prime})<\sigma(B_{i + 1})}{\leq} {n}_{B_{i + 1}}(a) \leq_{(2)} {n}_{B_{i + 1}}(A) \\ &&\overset{\sigma(A_{i}) < \sigma(B_{i + 1}) < \sigma(A_{i + 1})}{=} {n}_{A_{i}}(A) + 1 ={~}_{(1)} {n}_{A_{i}}(a) + 1\mathrm{,} \end{array} $$

a contradiction.

Therefore, the assumption ${n}_{A_{i + 1}}(B) - 1 > {n}_{A_{i + 1}}(A)$ was wrong, and it holds that ${n}_{A_{i + 1}}(B) - 1 \leq {n}_{A_{i + 1}}(A)$ proving Claim 2.

• Claim 3${n}_{A_{i + 1}}(B) - 1 \geq {n}_{A_{i + 1}}(A)$

Assume for contradiction that ${n}_{A_{i + 1}}(B) - 1 < {n}_{A_{i + 1}}(A)\mathrm {.}$ As a consequence, it holds that ${n}_{A_{i + 1}}(B) = {n}_{A_{i}}(B)$ since

$${n}_{A_{i}}(B) - 1 \leq {n}_{A_{i + 1}}(B) - 1 \overset{\text{assumption}}{\leq} {n}_{A_{i + 1}}(A) - 1 = {n}_{A_{i}}(A) = {n}_{A_{i}}(B) - 1\mathrm{.} $$

Furthermore, there has to be at least one job B_i+ 1 ∈ B that starts after A_i+ 1 since |A| = |B|. Therefore, we have ${n}_{B_{i + 1}}(c) - {n}_{B_{i}}(c) = {n}_{B_{i + 1}}(A) - {n}_{B_{i}}(A) \geq 2 \mathrm {.}$ As a consequence, there are jobs c^′,c^″∈ c which are scheduled between B_i and B_i+ 1. Let c^′ be the first job in c scheduled after B_i and c^″ be the next. Since we do not know the value of ${n}_{B_{i}}(\{\lambda _2\})$ or ${n}_{B_{i + 1}}(\{\lambda _2\})$, we can just deduce from (2) that ${n}_{B_{i + 1}}(a) - {n}_{B_{i}}(a) \geq 1$. Therefore, there has to be a job a^′∈ a that is scheduled between B_i and B_i+ 1.

We will now look at the order in which the jobs A_i, A_i+ 1, c^′, c^″ and a^′ have to be scheduled. First, we know that A_i and A_i+ 1 have to be scheduled between c^′ and c^″, since

$${n}_{A_{i}}(c) ={~}_{(1)} {n}_{A_{i}}(B) \overset{\sigma(B_{i}) < \sigma(A_{i})< \sigma(B_{i + 1})}{=} {n}_{B_{i}}(B) + 1 ={~}_{(9)} {n}_{B_{i}}(A) + 1 ={~}_{(2)} {n}_{B_{i}}(c) + 1 $$

and

$${n}_{A_{i + 1}}(c) ={~}_{(1)} {n}_{A_{i + 1}}(B) \overset{\sigma(B_{i}) < \sigma(A_{i + 1})< \sigma(B_{i + 1})}{=} {n}_{B_{i}}(B) + 1 ={~}_{(9)} {n}_{B_{i}}(A) + 1 ={~}_{(2)} {n}_{B_{i}}(c) + 1\mathrm{,} $$

and hence there has to be exactly one job from the set c scheduled between B_i and A_i, as well as B_i and A_i+ 1. Furthermore, we know that a^′ has to be scheduled between c^′ and c^″ as well, since

$${n}_{a^{\prime}}(c) ={~}_{(3)} {n}_{a^{\prime}}(B) \overset{\sigma(B_{i}) < \sigma(a^{\prime})}{=} {n}_{B_{i}}(B) + 1 ={~}_{(9)} {n}_{B_{i}}(A) + 1 ={~}_{(2)} {n}_{B_{i}}(c) + 1\mathrm{.} $$

As a consequence, we can deduce that there is a job b^′∈ b which is scheduled between c^′ and c^″, since

$${n}_{c^{\prime\prime}}(b) ={~}_{(5)} {n}_{c^{\prime\prime}}(a) {\overset{\sigma(c^{\prime})<\sigma(a^{\prime})< \sigma(c^{\prime\prime})}{\geq}} {n}_{c^{\prime}}(a) + 1 ={~}_{(5)} {n}_{c^{\prime}}(b) + 1\mathrm{.} $$

We know about this b^′ that

$${n}_{b^{\prime}}(A) ={~}_{(4)} {n}_{b^{\prime}}(c) \overset{\sigma(B_{i}) <\sigma(c^{\prime})<\sigma(b^{\prime})< \sigma(c^{\prime\prime})}{=} {n}_{B_{i}}(c) + 1 ={~}_{(2)} {n}_{B_{i}}(A) + 1\mathrm{,}$$

so b^′ has to be scheduled between A_i and A_i+ 1.

Fig. 6

Proved positions of the jobs in the sets A, a, and α

In summary, the jobs are scheduled as follows: B_i, c^′, A_i, b^′, A_i+ 1, c^″, B_i+ 1. However, this schedule is infeasible since

$${n}_{A_{i}}(b) ={~}_{(1)} {n}_{A_{i}}(B) - 1 \overset{\text{assumption}}{=} {n}_{A_{i + 1}}(B) - 1 ={~}_{(1)} {n}_{A_{i + 1}}(b) = {n}_{A_{i}}(b) + 1\mathbb{,}$$

a contradiction.

As a consequence, it has to hold that ${n}_{A_{i + 1}}(B) - 1 \geq {n}_{A_{i + 1}}(A)$ proving Claim 3. Altogether as a consequence of Claim 2 and Claim 3, we have proved that ${n}_{A_{i + 1}}(B) - {n}_{A_{i + 1}}(\{\lambda _1\}) = {n}_{A_{i + 1}}(A)$ for all i ∈{0,…,z}. This concludes the proof of the Claim 1.

Last we have to prove the (7). To do this we have to prove that ${n}_{B_{i}}(\{\lambda _1\})= 0$ for all i ∈{0,…,z}. We do this by proving the following claim.

• Claim 4λ₂ is scheduled after the last job in B.

To prove the (7), we have to prove that ${n}_{B_{i}}(\{\lambda _2\}) = 0$ for each i ∈{0,…,z}, i.e., we have to prove Claim 4. Assume there is an i ∈{0,…,z} with ${n}_{B_{i}}(\{\lambda _2\}) > 0$. Let i be the smallest of these indices. We know that

$$i -1 ={~}_{(9)}{n}_{B_{i}}(A) - 1 = {n}_{B_{i}}(A) - {n}_{B_{i}}(\{\lambda_{2}\}) ={~}_{(2)} {n}_{B_{i}}(a)\mathrm{.}$$

Since ${n}_{A_{i}}(b) ={~}_{(1)} {n}_{A_{i}}(a) ={~}_{(6)} i = {n}_{B_{i}}(a) + 1 ={~}_{(2)} {n}_{B_{i}}(b) + 1$ there has to be an unique a^′∈ a and an unique b^′∈ b scheduled between B_i and A_i. Furthermore, since ${n}_{A_{i}}(c) ={~}_{(6)} i + 1$ and ${n}_{B_{i}}(c) ={~}_{(9)} i$, there has to be a c^′∈ c scheduled between B_i and A_i as well. At the start of b^′ it holds that ${n}_{b^{\prime }}(c) ={~}_{(4)} {n}_{b^{\prime }}(A) = {n}_{A_{i-1}}(A) + 1 ={~}_{(4)} {n}_{A_{i-1}}(c)$, so b^′ has to start before c^′. Additionally, at the start of a^′ we have ${n}_{a^{\prime }}(c) ={~}_{(4)} {n}_{a^{\prime }}(B) = {n}_{B_{i}}(B) + 1 ={~}_{(9)} {n}_{B_{i}}(c) + 1$ and therefore a^′ hast to start after c^′. In total, the jobs appear in the following order: B_i,b^′,c^′,a^′,A_i. But this can not be the case, since we have

$${n}_{B_{i-1}}(a) \overset{(\sigma(c^{\prime})< \sigma(a^{\prime}))}{=} {n}_{c^{\prime}}(a) ={~}_{(5)} {n}_{c^{\prime}}(b)\overset{(\sigma(B_{i})<\sigma(b^{\prime})<\sigma(c^{\prime}))}{=} {n}_{B_{i-1}}(b) + 1 ={~}_{(2)} {n}_{B_{i-1}}(a) + 1. $$

Hence, we have contradicted that assumption. Hence, we have ${n}_{B_{i}}(\{\lambda _2\}) = 0$ for all i ∈{0,…,z} and (7) is a consequence:

$${n}_{B_{i}}(b) = {n}_{B_{i}}(a) = {n}_{B_{i}}(c) = {n}_{B_{i}}(\beta) = {n}_{B_{i}}(A) = {n}_{B_{i}}(B) = i\mathrm{.} $$

□

A direct consequence of Lemma 4 is that the last job on M₂ is a job in A. Since the (1) and (2), as well as (3) and (4), are symmetric, we can deduce an analogue statement if the first job on M₂ is in A. More precisely, we can show that ${n}_{B_{i}}(A) - {n}_{B_{i}}(\{\lambda _2\}) = {n}_{B_{i}}(B)$ and ${n}_{B_{i}}(\{\lambda _2\}) = 1$ for each B_i ∈ B in this case. This would imply that the last job on M₂ is a job in B. Since we can mirror the schedule such that the last job is the first job, we can suppose that the first job on M₂ is a job in B.

At this point, we know which machines process which jobs and for all the jobs using more than one machine we know the rough order of their processing by the (6) and (7). These are all the tools we need to prove that if the optimal schedule for the scheduling instance derived from $\mathcal {I}$ has makespan W then $\mathcal {I}$ is a Yes-instance for 3-Partition and we will prove it in the next lemma.

Lemma 5

If the optimal schedule for the scheduling instance derivedfrom$\mathcal {I}$hasmakespan W then$\mathcal {I}$isa Yes-instance for 3-Partition and we can transform the schedule such thatall jobs are scheduled on contiguous machines.

Proof

First, we will prove that M₁ processes the jobs A ∪ a ∪ α ∪{λ₁} in the order λ₁, A₀, a₁, α₁, A₁, a₂, α₂, A₂, …, a_z, α_z, A_z, where a_i ∈ a and α_i ∈ α for each i ∈{1,…z}, see Fig. 6. Lemma 4 ensures that the first job on M₁ is the job λ₁. Furthermore, since $0={n}_{A_0}(A)={~}_{(6)} {n}_{A_0}(\alpha ) ={~}_{(6)} {n}_{A_0}(a)$, the second job on M₁ is A₀. For each i ∈{1,…,z} it holds that ${n}_{A_{i}}(\alpha ) ={~}_{(6)} {n}_{A_{i-1}}(\alpha ) + 1$ and ${n}_{A_{i}}(a) ={~}_{(6)}{n}_{A_{i-1}}(a) + 1$. Therefore, there is exactly one job a_i ∈ a and one job α_i ∈ α scheduled between the jobs A_i− 1 and A_i. It holds that ${n}_{A_{i-1}}(a) + 1 ={~}_{(6)} i ={~}_{(7)} {n}_{B_{i}}(a)$. Therefore, a_i has to be scheduled between A_i− 1 and B_i. As a consequence, we have ${n}_{a_{i}}(\alpha ) + 1 = {n}_{a_{i}}(\alpha ) + {n}_{a_{i}}(\{\lambda _1\}) ={~}_{(3)} {n}_{a_{i}}(B) = {n}_{B_{i}}(B) ={~}_{(7)} {n}_{B_{i}}(a) = {n}_{a_{i}}(a) + 1.$ Therefore, a_i has to be scheduled before α_i and the jobs appear in machine M₁ in the described order. As a result, we know about the start point of A_i that

$$\begin{array}{@{}rcl@{}} \sigma(A_{i}) &=& p(\lambda_{1}) + ip_{a} + i p_{\alpha} + i p_{A} \\ &=& (i + 1)(D^{2} + D^{3}) + i(D^{4} + D^{5} + D^{6}+ D^{7}) + (7zi+z)D^{8}. \end{array} $$

Now, we will show that the machine M₄ processes the jobs B ∪ b ∪ β ∪{λ₂} in the order B₀, β₁, b₁, B₁, β₂, b₂, B₂, …, β_z, b_z, B_z, λ₂ see Fig. 7. The first job on M₄ is the job B₀, since Lemma 3 states that one of the jobs in A ∪ B has start point 0 and we decided w.l.o.g. that B₀ is this job. Equation (7) ensures that between the jobs B_i and B_i+ 1 there is scheduled exactly one job b_i+ 1 ∈ b and exactly one job β_i+ 1 ∈ β. It holds that ${n}_{A_{i}}(b) + 1 ={~}_{(6)} i + 1 ={~}_{(7)} {n}_{B_{i + 1}}(b)\mathrm {.}$ Therefore, b_i+ 1 has to be scheduled between A_i and B_i+ 1. As a consequence, it holds that

$$\begin{array}{@{}rcl@{}} {n}_{b_{i + 1}}(\beta) &&\overset{{{n}_{b_{i + 1}}(\{\lambda_{2}\}) = 0}}{=} {n}_{b_{i + 1}}(\beta) + {n}_{b_{i + 1}}(\{\lambda_{2}\}) ={~}_{(4)} {n}_{b_{i + 1}}(A) \\ && \overset{\sigma(A_{i})< \sigma(b_{i + 1}) < \sigma(B_{i + 1})}{=} {n}_{B_{i + 1}}(A) ={~}_{(7)} {n}_{B_{i + 1}}(b)\\ && \overset{\sigma(A_{i})< \sigma(b_{i + 1}) < \sigma(B_{i + 1})}{=} {n}_{b_{i + 1}}(b) + 1\mathrm{.} \end{array} $$

Hence, b_i+ 1 has to be scheduled after β_i+ 1 and the jobs on machine M₄ appear in the described order. As a result, we know about the start point of B_i that

$$\begin{array}{@{}rcl@{}} \begin{array}{lll} \sigma(B_{i}) = & i p_{b} + i p_{\beta} + ip_{B}\\ = & iD^{2} + iD^{3} + iD^{4} + iD^{5} + iD^{6} + iD^{7} + (i(7z-1))D^{8}. \end{array} \end{array} $$

Fig. 7

Proved positions of the jobs in the sets B, b, and β

Next, we can deduce that the jobs in c are scheduled as shown in Fig. 7. We have ${n}_{B_{i}}(c) ={~}_{(7)} i ={~}_{(6)} {n}_{A_{i}}(c)-1$. Therefore, there exists an c^′∈ c for each i ∈{0,…,z}, which is scheduled between B_i and A_i. The processing time between B_i and A_i is exactly σ(A_i) − σ(B_i) − p(B_i) = D³ + (z + i)D⁸. As a consequence, one can see with an inductive argument that c_i ∈ c with p(c_i) = D³ + (z + i)D⁸ has to be positioned between B_i and A_i, since the job in c with the largest processing time, c_z, fits between B_z and A_z only.

In this step, we will transform the schedule such that all jobs are scheduled on contiguous machines. To this point, this property is obviously fulfilled by the jobs in A ∪ B ∪ c. However, the jobs in a ∪ b might be scheduled on non-contiguous machines. We know that the a_i and b_i are scheduled between A_i− 1 and B_i. One part of a_i is scheduled on M₁ and one part of b_i is scheduled on M₄, while each other part is scheduled either on M₂ or on M₃ but both parts on different machines, because σ(B_i)−σ(A_i− 1)−p(A_i) = D⁵+D⁶+D⁷+(6z−i)D⁸ < D⁵+ 2D⁶+D⁷+ 6zD⁸ = p(a_i)+p(b_i) for each i ∈{0,…,z}. Since A_i and B_i+ 1 both are scheduled on machines M₂ and M₃, we can swap the content of the machines between these jobs such that the other part of a_i is scheduled on M₂ and the other part of b_i is scheduled on M₃. We do this swapping step for all i ∈{0,…,z − 1} such that all other parts of jobs in a are scheduled on M₂ and all other part of jobs in b are scheduled on M₃ respectively. After this swapping step, all jobs are scheduled on contiguous machines.

Now, we will show that $\mathcal {I}$ is a Yes-instance. To this point we know that M₂ contains the jobs A ∪ B ∪ a ∪ c. Since $\check {a} = a$ and $|\check {a}| = |\check {\gamma }|$, it has to hold by Lemma 1 that $\check {\gamma } = \gamma$ implying that M₂ contains all jobs in γ. Furthermore, since $\check {b} = \emptyset$ and $|\check {b}| = |\check {\delta }|$, we have $\check {\delta } = \emptyset$ and therefore M₂ does not contain any job in δ. Besides the jobs A ∪ B ∪ a ∪ c ∪ γ, M₂ processes further jobs with total processing time zD. Therefore, all the jobs in P are processed on M₂. We will now analyse where the jobs in γ are scheduled. The only possibility where these jobs can be scheduled is the time between the end of a_i and the start of B_i for each i ∈{1,…,z} since at each other time the machine is occupied by other jobs. The processing time between the end of a_i and the start of B_i is exactly σ(B_i) − σ(A_i− 1) − p(A_i− 1) − p(a_i) = D⁷ + (3z − i)D⁸. The job in γ with the largest processing time is the job γ₁ with p(γ₁) = D⁷ + (3z − 1)D⁸ − D. This job only fits between a₁ and B₁. Inductively we can show that γ_i ∈ γ with p(γ_i) = D⁷ + (3z − i)D⁸ − D has to be scheduled between a_i and B_i on M₂. Furthermore since p(γ_i) = D⁷ + (3z − i)D⁸ − D and the processing time between the end of a_i and the start of B_i is D⁷ + (3z − i)D⁸, there is exactly D processing time left. This processing time has to be occupied by the jobs in P since this schedule has no idle times. Therefore, we have for each i ∈{1,…,z} a subset P_i ⊆ P containing jobs with processing times adding up to D such that $P_1 \dot \cup {\dots } \dot \cup P_z = P$. As a consequence $\mathcal {I}$ is a Yes-instance. □

3 Hardness of Strip Packing

In this section, we will prove the Theorem 2. This can be done straight forward, by using the reduction from above. Note that in the transformed optimal schedule, all jobs are scheduled on contiguous machines, i.e., the machines the jobs are schedule on are Neighbors in the natural order (M₁,M₂,M₃,M₄). As a consequence, we have proved that this problem is strongly NP-complete even if we restrict the set of feasible solutions to those where all jobs are scheduled on contiguous machines. We will now describe how this insight delivers a lower bound of $\frac {5}{4}$ for the best possible approximation ratio for pseudo-polynomial Strip Packing and in this way prove the Theorem.

To show our hardness result for Strip Packing, let us consider the following instance. We define W := (z + 1)(D² + D³ + D⁴) + z(D⁵ + D⁶ + D⁷) + z(7z + 1)D⁸ as the width of the strip, i.e., it is the same as the considered makespan in the scheduling problem. For each job j defined in the reduction above, we introduce an item i with w(i) = p(j) and height h(i) = q(j). Now, we can show analogously that if the 3-Partition instance is a Yes-instance, there is a packing of height 4 (one example is the packing in Fig. 4); and on the other hand if there is a packing with height 4, the 3-Partition instance has to be a Yes-instance. If the 3-Partition instance is a No-instance, the optimal packing has a height of at least 5 since the optimal height for this instance is integral. Therefore, we cannot approximate Strip Packing better than $\frac {5}{4}$ in pseudo-polynomial time unless P = NP.

3.1 Variants of Strip Packing

Lastly we look at a variant of the Strip Packing problem called Scheduling of Contiguous Moldable Parallel Tasks. In this problem setting we are given an (arbitrary large) set of m machines, which have some kind of total order, and a set of parallel tasks J. Each task j ∈ J has a set D_j ⊆{1,…,m} of machine amounts it can be processed on, e.g., if D_j = {3,7} the job j can be processed either on three or on seven machines. For each q ∈ D_j it has an individual processing time $p(j,q) \in \mathbb {N}_{>0} \cup \{\infty \}$. A schedule S is given by two functions $\sigma : J \rightarrow \mathbb {N}$ and ρ : J → 2^{1,…,m}. The function σ maps each job to a start point in the schedule, while ρ maps each job to an interval of machines it is processed on. A schedule is feasible if each machine processes at most one job at a time and each job is processed on the required number of machines, (i.e., |ρ(j)|∈ D_j).

This problem directly contains the Strip Packing problem as a special case by setting D_i = {w(i)} and p(i,w(i)) = h(i) for each item i ∈ I, and hence, it is NP-hard to approximate it better than $\frac {5}{4}$ in pseudo-polynomial time. However, it is also NP-hard to find a better approximation than $\frac {5}{4}$ if we require D_j = {1,…,m} and $p(j,q) \in \mathbb {N}_{>0}$ for each job and number of machines. To show this, we use the reduction from above. The number of machines is m := (z + 1)(D² + D³ + D⁴) + z(D⁵ + D⁶ + D⁷) + z(7z + 1)D⁸. For each item i ∈ I constructed for the Strip Packing instance, we introduce one job i with p(i,q) = 5, if q < w(i) and p(i,q) = h(i), if q ≥ w(i). Obviously a schedule with height 4 can be found if and only if each job i uses w(i) machines and the 3-Partition instance is a Yes-instance. Otherwise the optimal schedule has a makespan of 5. Hence it is not possible to find an algorithm with approximation ratio better than 5/4, unless P = NP.

Note that in this construction the processing time function is not monotone, i.e., we do not have p(j,q) ⋅ q ≤ p(j,q + 1) ⋅ (q + 1) for each q ∈{1,…,m − 1}. Hence, there could be a PTAS for the monotone case.

4 Conclusion

In this paper, we positively answered the long standing open question whether the problem P4|size_j|C_max is strongly NP-complete. This closes the gap between strongly NP-completeness for at least 5 machines, and the possibility to solve the problem in pseudo-polynomial time for at most 3 machines.

Furthermore, we have improved the lower bound for pseudo-polynomial Strip Packing to $\frac {5}{4}$. The best known published algorithm has an approximation ratio of $\frac {4}{3}$. This leaves a gap between the lower bound and the best known algorithm. However, very recently we were able to find a pseudo-polynomial time algorithm with approximation ratio $\frac {5}{4} +\varepsilon$ [20], which closes this gap.

Lastly, we have considered Scheduling of Contiguous Moldable Parallel Tasks and proved that in the non-monotone case there is no pseudo-polynomial time algorithm with approximation ratio better than 5/4 unless P = NP. However, in the monotone case, finding a PTAS might be possible. In our opinion, it is an interesting open problem, whether there is a PTAS for the monotone case or not, especially since there is an FPTAS for the case that m > 8n/ε, see [18].