Approximating Two-Machine Flow Shop Problem with Delays when Processing Times Depend Only on Machines Alexander Ageev and Alexei Baburin Sobolev Institute of Mathematics, pr. Koptyuga 4, Novosibirsk, Russia ageev@math.nsc.ru, ababur@sicex.ru Abstract. We study the two-machine flow shop problem with (minimum) de- lays.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 process- ing 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 ). Keywords: approximation algorithm, scheduling problem, flow shop, mini- mum delays, worst-case ratio Introduction 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 commu- nication 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 modifica- tion 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 sched- ule. 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 326 Alexander Ageev and Alexei Baburin and intermediate minimum delays. Following the extension [13] of the three-field nota- tion 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 algo- rithm 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+ 2q+2 q+4 , 2−q} where max{a, b} − min{a, b} q= . max{a, b} The algorithm can be implemented in O(n2 ) time. Since it can be shown that min{1 + 2q+2 q+4 , 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 machineP1 (machine P 2), the order P of executing P jobs on machine 2 (machine 1) is optimal if p j 1j ≤ j p2j (if p j 1j > p j 2j ). 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 . Title Suppressed Due to Excessive Length 327 1 Preliminaries Before proceeding to the main part we introduce basic notation and make some obser- vations 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. Note that σ(2, j) ≥ σ(1, j) + aj + lj . for all j ∈ J. For a schedule σ = (σ(1, 1), σ(2, 1), . . . , σ(2, n)), denote by Cj (σ) the completion time of job j in σ; then CP j (σ) = σ(2, j) P + bj . The length of a schedule σ is Cmax (σ) = maxj∈J Cj (σ). Let A = j∈J aj , B = j∈J bj , and L = maxj∈J lj . Let ∗ Cmax denote the length of a shortest 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 ϕ (1) ϕ (2) ϕ (3) ϕ (n) t=0 t ψ(1) ψ(2) ψ(3) ψ(n) Fig. 1. ϕ(k) (ψ(k)) is the k-th job executed by machine 1 (machine 2) σ(1, ϕ(1)) = 0 and for any k = 2, . . . , n, σ(1, ϕ(k)) = σ(1, ϕ(k − 1)) + aϕ(k−1) , σ(2, ψ(k)) = σ(2, ψ(k − 1)) + bψ(k−1) . 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 (ϕ(1), . . . , ϕ(n)) and (ψ(1), . . . , ψ(n)). 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 328 Alexander Ageev and Alexei Baburin permutations (ϕ, ψ), the early schedule [ϕ, ψ] can be found in linear time. Indeed, to find σ it suffices to determine x = σ(2, ψ(1)). For any k = 1, . . . , n we have k−1 X σ(2, ψ(k)) = x + bψ(i) ≥ σ(1, ϕ(k)) + aϕ(k) + lϕ(k) . i=1 Pk−1 Thus x = min{σ(1, ϕ(k)) + aϕ(k) + lϕ(k) − i=1 bψ(i) : k = 1, . . . , n}, which can be found in linear time. It is easy to see that a schedule σ is feasible if and only if min{σ(2, j) − σ(1, j) − aj − lj : j ∈ J} ≥ 0. Observe that for a schedule σ with the job permutations (ϕ, ψ) min{σ(2, j) − σ(1, j) − aj − lj : j ∈ J} = 0 (1) if and only if σ = [ϕ, ψ]. 2 Short schedules 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, ∗ Cmax ≥ Λ = max{A, B, max{aj + bj + lj }}. (2) j∈J 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. Then Cmax (σ) ≤ (1 + min{A,B} Λ ∗ )Cmax . 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 σ ∗ . In other words, for any j ∈ J, σ ′ (1, j) = σ ∗ (1, j), σ ′ (2, j) = σ ∗ (2, j) + A. (3) Title Suppressed Due to Excessive Length 329 It is clear that σ ′ is a feasible schedule. Note that by (2) A = A A ∗ Λ Λ ≤ Λ Cmax . Thus by ′ the construction of σ , A ∗ A ∗ Cmax (σ ′ ) = Cmax (σ ∗ ) + A ≤ Cmax (σ ∗ ) + C = (1 + )Cmax . (4) Λ max Λ Now consider the schedule σ ′′ whose pair of jobs permutations is (ϕ, ψ ∗ ) and such that σ ′′ (2, ψ ∗ (1)) = σ ′ (2, ψ ∗ (1)). Thus the schedule σ ′′ may differ from the schedule σ ′ on machine 1 and coincides with σ ′ on machine 2. Since the completion time of the last operation on machine 1 is A for all schedules, σ ′′ (1, j) ≤ σ ∗ (1, j) + A and so σ ′′ (1, j) + aj + lj ≤ σ ∗ (1, j) + aj + lj + A ≤ σ ∗ (2, j) + A (by (3)) = σ ′ (2, j) = σ ′′ (2, j) for all j ∈ J. It follows that σ ′′ is a feasible schedule. Since σ ′ and σ ′′ coincide on machine 2, Cmax (σ ′′ ) = Cmax (σ ′ ). However, since σ and σ ′′ have the same jobs permu- tation ϕ on machine 1 and σ is a short schedule, we have that Cmax (σ) ≤ Cmax (σ ′′ ). Finally, by (4) we obtain A ∗ Cmax (σ) ≤ Cmax (σ ′′ ) = Cmax (σ ′ ) ≤ (1 + )C . Λ max ⊔ ⊓ 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 O(n log n) time. 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 prob- lem 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. 330 Alexander Ageev and Alexei Baburin Algorithm SPECIAL Step 0. Sort the jobs in nondecreasing order of delays. For convenience, we will further assume that l1 ≤ l2 ≤ . . . ≤ ln = L. (5) Step k. For k = 1, . . . , n construct the schedule σk = [ϕk , ψ] where ψ = (1, . . . , n) and ϕk = (k + 1, . . . , n, 1, . . . , k) if k ≤ n − 1 and ϕn = (1, . . . , n) (see Fig. 2). Pick out a schedule σ ∈ {σ1 , . . . , σn } having the shortest length and construct a sched- ule τ = σ. Output τ . k+1 n 1 k t=0 t 1 k k+1 n Fig. 2. The schedule constructed at Step 2 of algorithm SPECIAL 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 Cmax 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. P j∈J lj l (a + b)(n + 1) m ∗ Cmax ≥ + (6) 2 n Proof. Let σ be a feasible schedule with the job permutations ϕ and ψ. Then for any j ∈ J, n X Cmax (σ) ≥ σ(1, j) + aj + lj + bψ(k) k=ψ −1 (j) ϕ−1 (j) n X X = aϕ(k) + lj + bψ(k) . k=1 k=ψ −1 (j) By taking into account that aj ≡ a and bj ≡ b, it follows that ϕ−1 (j) n 1X X X  Cmax (σ) ≥ aϕ(k) + lj + bψ(k) n j∈J k=1 k=ψ −1 (j) Title Suppressed Due to Excessive Length 331 ϕ−1 (j) n P 1X X j∈J lj X X  = aϕ(k) + bψ(k) + n n j∈J k=1 j∈J k=ψ −1 (j) P 1  X −1 j∈J lj X  = a ϕ (j) + b (n − ψ −1 (j) + 1) + n n j∈J j∈J P 1  j∈J lj  = an(n + 1) + bn(n + 1) + 2n P n (n + 1)(a + b) j∈J jl = + . 2 n By combining (6) with (2), we obtain the following lower bound: P ∗ (a + b)(n + 1) j lj Cmax ≥ LB = max{a + b + L, an, + }. (7) 2 n We now proceed to establishing an upper bound on the length of the schedule returned by algorithm Special. Lemma 2. For any k = 1, . . . , n, Cmax (σk ) ≤ max{Xk , Yk } (8) 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 (1). Since σk (1, k) = a(n − 1) and σk (1, n) = a(n − k − 1), (1) implies that min{σk (2, k) − an − lk , σk (2, n) − a(n − k) − ln } ≥ 0. We now claim that in fact min{σk (2, k) − an − lk , σk (2, n) − a(n − k) − ln } = 0. (9) 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) > an + lk − b(k − j) − a(n − k + j − 1) = lk + (a − b)(k − j) + a ≥ lj + a, 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) > a(n − k) + ln − b(n − j) − a(j − k − 1) = (a − b)(n − j) + ln + a ≥ lj + a, 332 Alexander Ageev and Alexei Baburin 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 . If the latter is true, then Cmax (σk ) = σk (2, n) + b = a(n − k) + ln + b = Xk . Thus (8) does hold true, as required. ⊔ ⊓ 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 + , 2 − q}Cmax (10) q+4 where q = a−b a . Proof. First, observe that since τ is a short schedule, by Theorem 1 b ∗ ∗ Cmax (τ ) ≤ (1 + )Cmax = (2 − q)Cmax . a On the other hand, by the definition of short schedule, Cmax (τ ) = Cmax (σ) ≤ Cmax (σ). Thus, to prove the theorem it suffices to justify the following inequality:  2q + 2  ∗ Cmax (σ) ≤ 1 + Cmax . (11) q+4 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 σ, Pn Pn Cmax (σk ) Yk Cmax (σ) ≤ k=1 ≤ k=1 n Pn n Pn ann + k=1 b(n − k + 1) + k=1 lk = Pn n n+1 lk = an + b + k=1 2 n Pn a(n − 1) n+1 n+1 lk = +a +b + k=1 2 2 2 n 3 ∗ (by (7)) ≤ Cmax . (12) 2 Title Suppressed Due to Excessive Length 333 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 σ, n Pn k=r+1 Cmax (σk ) o Cmax (σ) ≤ min , Cmax (σr ) ≤ min{S1 , S2 } (13) n−r where Pn Pn Pn k=r+1 Yk an(n − r) + k=r+1 b(n − k + 1) + k=r+1 lk S1 = = , (14) n−r n−r S2 = Xr = a(n − r) + b + L. (15) Set t = n − r and µ = nt . Then by (15) and (7), t ∗ S2 ≤ an + b + L ≤ (1 + µ)Cmax . (16) n Moreover, by rearranging the expression (14) we obtain that Pn n+r+1 lk S1 = an + b(n + 1) − b + k=r+1 2 n−r Pn n+r−1 t+1 t+1 lk =a +a +b + k=n−t+1 2 2 2 t n+1 n+1  1 t+1 t+1  1 =R+ a +b + βµ + a +b + β + β( − µ) 2 2 2 2 2 2 Pn where β = 1t k=n−t+1 lk and 2n − t − 1 t+1 t+1 n+1 n+1 R=a +a +b −a −b 2 4 4 2 2 2n − t − 3 2n − t + 1 =a −b . 4 4 By (2), 2n − t 2n − t 2−µ 2−µ ∗ R≤ (a − b) = anq = anq ≤ qCmax . 4 4n 4 4 Furthermore, by Lemma 1 we have Pn n+1 n+1 (a + b)(n + 1) lk a +b + βµ = + k=n−t+1 ≤ Cmax ∗ . 2 2 2 n 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 Cmax ∗ whereas by Lemma 1, it is bounded from below by Pn t+1 t+1 (a + b)(t + 1) lk a +b +β =a + k=n−t+1 . 2 2 2 t So we obtain that t+1 t+1 ∗ a +b + β ≤ Cmax . 2 2 334 Alexander Ageev and Alexei Baburin Summing up, we arrive at the following inequality: 2−µ ∗ 3 ∗ 1 S1 ≤ qCmax + Cmax + β( − µ). 4 2 2 Thus from (13), (16), and the last inequality we obtain ∗ 2−µ ∗ 3 ∗ 1 Cmax (σ) ≤ min{(1 + µ)Cmax , qCmax + Cmax + β( − µ)}. 4 2 2 It follows that Cmax (σ) ≤ 23 Cmax ∗ if µ ≤ 12 and 2−µ 3 ∗ Cmax (σ) ≤ min{1 + µ, q + }Cmax 4 2 if µ > 21 . Thus Cmax (σ) ≤ (1 + µ∗ )Cmax ∗ where µ∗ satisfies 2 − µ∗ 3 q + = 1 + µ∗ , 4 2 which implies that µ∗ = 2q+2 q+4 . Together with (12) this implies (11), as required. ⊔ ⊓ Observe that 2q + 2 min{1 + , 2 − q} ≤ (2 − q ′ ) q+4 where q ′ satisfies q ′2 + 5q ′ − 2 = 0. √ By resolving this quadratic equation, we get q ′ = − 25 + 21 33 and so √ 2q + 2 5 1√ 9 − 33 min{1 + , 2 − q} ≤ (2 + − 33) = < 1.628. q+4 2 2 2 Thus we have the following Corollary 1. Algorithm SPECIAL √ solves F 2 | lj , p1j = a, p2j = b | Cmax with an 9− 33 approximation factor of 2 < 1.628 in O(n2 ) time. In the case when a = b the approximation ratio of algorithm Special is bounded by 1.5. ⊔ ⊓ References 1. Ageev A.A.: A 3/2-approximation for the proportionate two machine flow shop scheduling with minimum delays. In: Approximation and Online Algorithms, LNCS, vol.4927, pp. 55–66 (2008) 2. Dell’Amico M.: Shop problems with two machines and time lags. Operations Research 44, 777–787 (1996) 3. Dell’Amico M., Vaessens R.J.M.: Flow and open shop scheduling on two machines with transportation times and machine-independent processing times is NP-hard. In: Materiali di discussione 141, Dipartimento di Economia Politica, Università di Modena (1996) Title Suppressed Due to Excessive Length 335 4. Graham R.L., Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G.: Optimization and ap- proximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics 5, 287–326 (1979) 5. Johnson S.M.: Optimal two- and three-stage production schedules with setup times in- cluded. Naval Research Logistics Quarterly 1, 61–68 (1954) 6. Johnson S.M.: Discussion: Sequencing n jobs on two machines with arbitrary time lags. Management Science 5, 293–298 (1958) 7. Karuno Y., Nagamochi H.: A better approximation for the two-machine flow shop schedul- ing problem with time lags. In: Algorithms and Computation, LNCS, vol. 2906, pp. 309– 318 (2003) 8. Kern W., Nawijn W.M.: Scheduling multi-operation jobs with time lags on a single ma- chine, In: U. Faigle and C. Hoede (eds), Proceedings of the 2nd Twente Workshop on Graphs and Combinatorial Optimization, Enschede, 1991. 9. Lenstra J.K: Private communication, 1991. 10. Mitten L.G.: Sequencing n jobs on two machines with arbitrary time lags. Management Science 5, 293–298 (1958) 11. Strusevich V.A.: A heuristic for the two-machine open-shop scheduling with transporta- tion times. Discrete Applied Mathematics 93, 287–304 (1999) 12. Yu W.: The two-machine shop problem with delays and the one-machine total tardiness problem. Ph.D. thesis, Department of Mathematics and Computer Science, Technische Universiteit Eindhoven (1996) 13. Yu W., Hoogeveen H., Lenstra J.K.: Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard. J. Sched. 7, 333–348 (2004) 14. Zhang X., van de Velde S.: Polynomial-time approximation schemes for scheduling prob- lems with time lags. J. Sched. 13, 553–559 (2010)