We study the two-machine flow shop problem with (minimum) delays.The current best approximation factor achieved for this problem is 11/6 ≈ 1.833 (due to Karuno and Nagamochi; their algorithm runs in time O(n log n)). Our main result is a 1.628-approximation algorithm for the case when processing times depend only on machines. This case is strongly NP-hard even when all processing times are equal. The running time of our algorithm is O(n2).
In the two-machine flow shop problem with (minimum) delays there are two machines available from time zero onwards for processing n jobs. Each machine can process at most one job at a time. Each job j consists of two operations; the second operation must start no earlier than lj time units after the completion of the first operation. The first (second) operation has to be executed by machine 1 (machine 2) and processing the first (second) operation takes time p1j (p2j ). The objective is to minimize the makespan, or the schedule length, that is the maximum job completion time. As in [13], we denote this problem by F 2 | lj | Cmax.
The problems with minimum delays arise, in particular, in manufacturing where there may be a transportation time from one production facility to another, and in computer systems where the output of a task on one processor may require a communication time so as to become the input to a subsequent task on another processor.
The first result related to F 2 | lj | Cmax is due to Johnson [5] who presents an O(n log n) algorithm for F 2 || Cmax. Johnson [6] and Mitten [10] show that a modification of Johnson’s algorithm for F 2 || Cmax can be used to find an optimal permutation schedule, i.e., the schedule in which the jobs are executed by each machine in the same order. If all delays are equal, the set of optimal schedules contains a permutation schedule. However, this is not the case when there are at least two distinct delay values (see [6]. Kern and Nawijn [8] consider a single-machine problem with two operations per jobs Copyright c by the paper’s authors. Copying permitted for private and academic purposes. In: A. Kononov et al. (eds.): DOOR 2016, Vladivostok, Russia, published at http://ceur-ws.org and intermediate minimum delays. Following the extension [13] of the three-field notation scheme introduced by Graham et al. [4] we denote this problem by 1 | lj | Cmax. Yu et al. [12, 13] show that this problem is equivalent to F 2 | lj | Cmax. Kern and Nawijn [8] show that 1 | lj | Cmax is weakly NP-hard. This result is strengthened to NP-hardness in the strong sense for F 2 | lj | Cmax by Lenstra [9], for F 2 | lj, p1j = p2j | Cmax by Dell’Amico and Vaessens [3], and for F 2 | lj ∈ {0, l}, p1j = p2j | Cmax by Yu [12]. Yu et al. [13] prove that F 2 | lj, pij = 1 | Cmax is NP-hard in the strong sense. Dell’Amico [2] presents several 2-approximation algorithms with running time O(n log n) where n is the number of jobs. Karuno and Nagamochi [7] develop an 11/6 -approximation algorithm with running time O(n log n). Ageev [1] presents a 3/2-approximation algorithm for F 2 | lj, p1j = p2j | Cmax. Zhang and van de Velde [14] present a PTAS for F 2 | lj | Cmax under the assumption that lmax ≤ μpmin where lmax is the maximum delay, pmin is the smallest positive processing time of any operation and μ is a fixed number (that is, it is not part of the problem instance).
The question whether there exists a polynomial-time algorithm for the problem 1 | lj | Cmax with a better approximation ratio remains open though it has been posed by several researchers (see, for example, Strusevich [11]).
We consider the special case where p1j = a and p2j = b for all jobs j, or problem F 2 | lj, p1j = a, p2j = b | Cmax. Notice that this problem remains strongly NP-hard as it follows from the above mentioned result due to Yu et al. [13]. We present an approximation algorithm, whose approximation ratio is bounded by min{1+ 2qq++42 , 2−q} where q = max{a, b} − min{a, b} .
max{a, b} The algorithm can be implemented in O(n2) time. Since it can be shown that min{1 + 2qq++42 , 2 − q} < 1.628, this implies a 1.628-approximation for F 2 | lj, p1j = a, p2j = b | Cmax. For the case when a = b we get a 3/2-approximation. Note that the same approximation factor for this case follows from the above mentioned result by Ageev [1]. One of the ingredients of the algorithm is an observation that the length of any reasonable schedule in F 2 | lj | Cmax is at most twice the length of a shortest schedule. The reasonable schedule (we further call them short) is meant to be the schedule in which given an arbitrary order of executing jobs on machine 1 (machine 2), the order of executing jobs on machine 2 (machine 1) is optimal if Pj p1j ≤ Pj p2j (if Pj p1j > Pj p2j). Note that given a job order on one machine, finding an optimal order on the other is equivalent to solving the trivial single-machine problem with release times. As a by-product this observation provides a fairly simple 2-approximation algorithm for solving F 2 | lj | Cmax. The crucial part of our analysis is a lower bound for the length of a shortest schedule which is a straightforward extension of an observation due to Yu [12].
The paper is organized as follows. In Section 2 we introduce basic notation and definitions. We also make a few observations and assumptions that do not restrict generality. In Section 3 we give a simple 2-approximation for F 2 | lj | Cmax. In Section 4 we present an approximation algorithm for F 2 | lj, p1j = a, p2j = b | Cmax.
Before proceeding to the main part we introduce basic notation and make some observations and assumptions that do not restrict generality. An instance of F 2 | lj | Cmax consists of a set of jobs J = {1, . . . , n}. Each job j ∈ J consists of two operations O1,j and O2,j whose lengths will be denoted by aj and bj, respectively. For each j ∈ J operation O2,j is separated from O1,j by a delay of length at least lj time units. For any j ∈ J , we denote by σ(1, j) and σ(2, j) the starting times of O1,j and O2,j, respectively.
σ(2, j) ≥ σ(1, j) + aj + lj.
for all j ∈ J . For a schedule σ = (σ(
Observe that any feasible schedule for an instance of F 2 | lj | Cmax can be replaced
by a schedule such that it has the same orders of jobs on machines and the same length
but both machines process the jobs without idle times. Thus we may assume that both
machines process the jobs without idle times and machine 1 starts processing at time
0. Then any feasible schedule σ defines a pair of permutations (ϕ, ψ) of the set J such
that ϕ specifies the order of processing operations on machine 1 and ψ specifies that
on machine 2. More specifically, ϕ(k) (ψ(k)) is the k-th job executed by machine 1
(machine 2) (see Fig 1). Thus if (ϕ, ψ) is the pair of permutations of a schedule σ, then
ϕ (
ϕ (
Note that for any j ∈ J , ϕ−1(j) (ψ−1(j)) means the order number in which job j is
processed on machine 1 (machine 2). We will further represent the permutations ϕ and
ψ by the sequences (ϕ(
For any pair of permutations (ϕ, ψ), denote by [ϕ, ψ] the unique schedule having the
shortest length among all feasible schedules that run jobs according to the permutations
(ϕ, ψ). We say that σ is an early schedule if σ = [ϕ, ψ]. Note that given a pair of
permutations (ϕ, ψ), the early schedule [ϕ, ψ] can be found in linear time. Indeed, to
find σ it suffices to determine x = σ(2, ψ(
i=1 Thus x = min{σ(1, ϕ(k)) + aϕ(k) + lϕ(k) − Pik=−11 bψ(i) : k = 1, . . . , n}, which can be found in linear time.
min{σ(2, j) − σ(1, j) − aj − lj : j ∈ J } ≥ 0.
min{σ(2, j) − σ(1, j) − aj − lj : j ∈ J } = 0 if and only if σ = [ϕ, ψ]. 2
Let σ be a feasible schedule for an instance of F 2 | lj | Cmax. Since the length of a shortest schedule is at least the maximum machine load and the maximum job length,
Cm∗ax ≥ Λ = max{A, B, mj∈aJx{aj + bj + lj}}.
Then Cmax(σ) ≤ (1 + min{A,B} )Cm∗ax.
Λ We say that a feasible schedule is short if it has the shortest length among all schedules with the same (fixed) order of processing the operations on machine 1 when A ≤ B and if it has the shortest length among all schedules with the same (fixed) order of processing the operations on machine 2 when A > B. It is clear that any optimal schedule is a short schedule.
Given a job order on machine 1, a corresponding short schedule can be found in O(n log n) time (it is obviously equivalent to solving the single-machine scheduling problem with release times). The following theorem shows that the length of any short schedule is at most twice the length of a shortest schedule, thereby providing a fairly simple 2-approximation algorithm for solving F 2 | lj | Cmax.
Theorem 1. Let I be an instance of F 2 | lj | Cmax and let σ be a short schedule of I. Proof. Since the problem is symmetric with respect to the machine indices and the time axis, it suffices to consider the case when A ≤ B. Let (ϕ, ψ) be the pair of job permutations corresponding to σ and let (ϕ∗, ψ∗) be that corresponding to an optimal schedule σ∗. Consider the schedule σ′ whose pair of jobs permutations is that of σ∗ and such that all operations on machine 2 start exactly A time units later than in σ∗.
σ′(1, j) = σ∗(1, j),
σ′(2, j) = σ∗(2, j) + A.
(
Cmax(σ′) = Cmax(σ∗) + A ≤ Cmax(σ∗) + Cm∗ax = (1 + )Cm∗ax.
(
Now consider the schedule σ′′ whose pair of jobs permutations is (ϕ, ψ∗) and such
that σ′′(2, ψ∗(
≤ σ∗(2, j) + A
(by (
Cmax(σ) ≤ Cmax(σ′′) = Cmax(σ′) ≤ (1 +
A Λ )Cm∗ax.
Given a feasible schedule σ, we will denote by σ a short schedule whose order of jobs on machine 1 coincides with that of σ if A ≤ B and whose order of jobs on machine 2 coincides with that of σ if A > B. As it was mentioned above, σ can be found in
3
Algorithm for F 2 | lj , p1j = a, p2j = b | Cmax In this section we present an approximation algorithm for the special case of the problem when p1j = a and p2j = b for all j ∈ J . Recall that for brevity we set aj = p1j and bj = p2j.
Since the the case when a ≤ b trivially reduces to the case when a ≥ b (and vice versa), we will further assume that a ≥ b. Recall that this case of the problem remains strongly NP-hard as it follows from the NP-hardness result due to Yu et al. [13].
We now proceed to the description of the algorithm. The algorithm successively constructs k schedules, selects a schedule having minimum length among them and outputs the short schedule obtained from it. The schedules are generated by cyclic shifts of operations executed on machine 1 while the operations on machine 2 are executed in a fixed order. The idea behind the construction is to apply Lemma 1 (see below) in the worst-case analysis. ⊔⊓
Step 0. Sort the jobs in nondecreasing order of delays. For convenience, we will further assume that Pick out a schedule σ ∈ {σ1, . . . , σn} having the shortest length and construct a schedule τ = σ. Output τ .
k+1 t=0 n 1 k 1 k k+1 t n Running time. As it was shown in Section 2, the early schedule σk for each k = 1, . . . , n can be constructed in linear time. Furthermore, as it was noticed in Section 3, the schedule σ can be obtained from σ in O(n log n) time. Thus the total running time of the algorithm is O(n2).
Approximation ratio. We first show a lower bound for Cm∗ax that will play a crucial role in establishing an upper bound on the approximation ratio of algorithm Special. The lemma below is a straightforward extension of an observation due to Yu [12, 13] (Lemma 2 in [13]).
Lemma 1.
Cm∗ax ≥ l (a + b)2(n + 1) + Pjn∈J lj m (
Cmax(σ) ≥ n1 X j∈J
k=1 Cmax(σ) ≥ σ(1, j) + aj + lj +
ϕ−1(j) = X aϕ(k) + lj +
k=1 ϕ−1(j)
X aϕ(k) + lj + n X n
X k=ψ−1(j) k=ψ−1(j) bψ(k) bψ(k). n
X k=ψ−1(j)
bψ(k) ϕ−1(j) n = 1 X X aϕ(k) + X X bψ(k) + Pj∈J lj n j∈J k=1 j∈J k=ψ−1(j) n = n1 aXj∈J ϕ−1(j) + bX(n − ψ−1(j) + 1) + Pj∈J lj j∈J n = 21n an(n + 1) + bn(n + 1) + Pj∈J lj n = (n + 1)(a + b) + Pj∈J lj .
2 n
Cm∗ax ≥ LB = max{a + b + L,an, (a + b)2(n + 1) + Pnj lj }. (
Lemma 2. For any k = 1,...,n,
Cmax(σk) ≤ max{Xk,Yk} where Xk = a(n − k) + b + L and Yk = an + b(n − k + 1) + lk.
Proof. Let 1 ≤ k ≤ n. Note that by construction σk satisfies (
min{σk(2,k) − an − lk,σk(2,n) − a(n − k) − ln} ≥ 0.
min{σk(2,k) − an − lk,σk(2,n) − a(n − k) − ln} = 0.
Assume to the contrary that σk(2,k) > an + lk and σk(2,n) > a(n − k) + ln. Assume first that 1 ≤ j ≤ k. Then
σk(1,j) = σk(1,n) + a + a(j − 1) = a(n − k − 1) + aj = a(n − k + j − 1) and σk(2,j) + b(k − j) = σk(2,k). Since lj ≤ lk and a ≥ b, it follows that σk(2,j) − σk(1,j) = σk(2,k) − b(k − j) − a(n − k + j − 1) i. e., σk(2,j) − σk(1,j) − lj − a > 0. Assume now that k + 1 ≤ j ≤ n. Then σk(1,j) = a(j − k − 1) and σk(2,j) + b(n − j) = σk(2,n). Similarly to the above, we have σk(2,j) − σk(1,j) = σk(2,n) − b(n − j) − a(j − k − 1) > an + lk − b(k − j) − a(n − k + j − 1) = lk + (a − b)(k − j) + a ≥ lj + a, > a(n − k) + ln − b(n − j) − a(j − k − 1) = (a − b)(n − j) + ln + a ≥ lj + a, which means that σk(2, j) − σk(1, j) − lj − a > 0. Summing up, we arrive at the conclusion that σk(2, j) − σk(1, j) − lj − a > 0 for all j ∈ J , which contradicts the fact that σk is an early schedule.
By the claim, either σk(2, k) = an + lk, or σk(2, n) = a(n − k) + ln. If the former holds, then
Cmax(σk) = σk(2, k) + b(n − k + 1) = an + lk + b(n − k + 1) = Yk.
Cmax(σk) = σk(2, n) + b = a(n − k) + ln + b = Xk.
Theorem 2. Let I be an instance of the problem F 2 | lj, p1j = a, p2j = b | Cmax and τ be a schedule output by algorithm SPECIAL. Then 2q + 2 Cmax(τ ) ≤ min{1 + q + 4 , 2 − q}Cm∗ax On the other hand, by the definition of short schedule, Cmax(τ ) = Cmax(σ) ≤ Cmax(σ).
b Cmax(τ ) ≤ (1 + a )Cm∗ax = (2 − q)Cm∗ax.
Cmax(σ) ≤ 1 +
Cmax(σ) ≤
3
(by (
= = an + b
Pkn=1 Cmax(σk) Pkn=1 Yk
n ≤ n ann + Pkn=1 b(n − k + 1) + Pkn=1 lk
n n + 1 + Pkn=1 lk
2 n = a(n − 1) + a 2 n + 1 2 + b n + 1 2 +
Pkn=1 lk n For k = 1, . . . , n, let θ(k) = Yk − Xk. Since θ(k) = an + b(n − k + 1) + lk − a(n − k) − b − L
= (a − b)k + bn + lk − L, θ(k) is a non-decreasing function of k and θ(n) = an > 0, i. e., Yn > Xn. Thus the following two cases are possible: either Yk ≥ Xk for all k = 1, . . . , n, or there exists an index r ∈ {1, . . . , n − 1} such that Yr < Xr and Yk ≥ Xk for all k = r + 1, . . . , n.
Case 1: Yk ≥ Xk for all k = 1, . . . , n. Then by the construction of σ,
⊔⊓
(
Case 2: there exists an index r ∈ {1,...,n − 1} such that Yr < Xr and Yk ≥ Xk for all k = r + 1,...,n. Then by the construction of σ,
Cmax(σ) ≤ minnPkn=r+n1−Cmrax(σk),Cmax(σr)o ≤ min{S1,S2} where
S1 = Pkn=r+1 Yk = an(n − r) + Pkn=r+1 b(n − k + 1) + Pkn=r+1 lk ,
n − r n − r
S2 = Xr = a(n − r) + b + L.
Set t = n − r and μ = nt . Then by (15) and (
S2 ≤ ntan + b + L ≤ (1 + μ)Cm∗ax.
(
S1 = an + b(n + 1) − bn + r + 1 + Pkn=r+1 lk
2 n − r
= an +2r − 1 + at +2 1 + bt +2 1 + Pkn=nt−t+1 lk
= R + an +2 1 + bn +2 1 + βμ + 21 at +2 1 + bt +2 1 + β + β(21 − μ)
where β = 1t Pkn=n−t+1 lk and
By (
R = a2n − t − 1 + at +4 1 + bt +4 1 − an +2 1 − bn +2 1
2 = a2n − t − 3 − b2n − t + 1.
4 4
R ≤ 2n4− t(a − b) = 2n4n− tanq = 2 −4 μanq ≤ 2 −4 μqCm∗ax.
an +2 1 + bn +2 1 + βμ = (a + b)(n + 1) + Pkn=n−t+1 lk 2 n ≤ Cm∗ax.
Now consider the instance I′ of the problem formed by the subset of jobs {n − t + 1,...,n} with the same parameters as in I. It is clear that the length of a shortest schedule in I′ is at most Cm∗ax whereas by Lemma 1, it is bounded from below by at +2 1 + bt +2 1 + β = a(a + b)(t + 1) + Pkn=n−t+1 lk .
2 t
at +2 1 + bt +2 1 + β ≤ Cm∗ax.
which implies that μ∗ = 2qq++42 . Together with (
S1 ≤ if μ > 21 . Thus Cmax(σ) ≤ (1 + μ∗)Cm∗ax where μ∗ satisfies ⊔⊓ ⊔⊓
By resolving this quadratic equation, we get q′ = − 25 + 12 √33 and so min{1 + 2q + 2 5 1 √ q + 4 , 2 − q} ≤ (2 + 2 − 2 33) = 9 − √33 2 < 1.628.
Corollary 1. Algorithm SPECIAL solves F 2 | lj , p1j = a, p2j = b | Cmax with an approximation factor of 9−√33 < 1.628 in O(n2) time. In the case when a = b the 2 approximation ratio of algorithm Special is bounded by 1.5.