key: cord-0781160-2o2m2tfj
authors: Dong, Jianming; Pan, Hong; Ye, Cunkui; Tong, Weitian; Hu, Jueliang
title: No-wait two-stage flowshop problem with multi-task flexibility of the first machine
date: 2020-07-04
journal: Inf Sci (N Y)
DOI: 10.1016/j.ins.2020.06.052
sha: d4a5c993d0ddb4c0b2bad1f4083836a49601e325
doc_id: 781160
cord_uid: 2o2m2tfj

For the creation of intelligent management systems in hospitals, efficient resource arrangement is essential. Motivated by a real-world scenario in hospitals, we introduce the no-wait two-stage flowshop scheduling problem with the first-stage machine having multi-task flexibility. In this problem, each job has two operations which are processed in order on a two-stage flowshop without preemption and time delay between or on machines. The multi-task flexibility allows the first-stage machine to process the second-stage operations. The goal is to minimize the maximum completion time of all jobs. To the best of our knowledge, this is a pioneering work on this problem. We discover several novel structural properties, based on which we present a linear-time combinatorial algorithm with an approximation ratio [Formula: see text]. This problem and its variants can find many other meaningful applications in modern manufacturing systems, such as the robot cell scheduling with computer numerical control machines or printed circuit boards. The idea behind our algorithm may inspire more practical algorithms.

Upon the completion of a surgery on the operating room bed, each patient should be transferred to a recovery bed as soon as possible to start the postanesthesia procedure. Operating room beds are capable of doing the operations of recovery room beds. In contrast, a recovery room bed is usually lack of necessary equipments for surgical operations. Thus unavailability of a bed in the recovery room at the end of a surgical operation can incur the beginning of postanesthesia procedure in the operating room until the discharge of a bed in the recovery room [14] .

Motivated by the aforementioned scenario, we introduce and investigate a meaningful twostage flowshop scheduling problem. Formally, there are two machines M 1 and M 2 and a job set J = {J 1 , J 2 , . . . , J n }. Each job J i , i ∈ {1, 2, . . . , n} has two operations A i and B i , named as the first-and second-stage operation respectively, which must be processed in order without preemption and any time delay. That is, 1) both A i and B i should be processed non-preemptively; 2) once A i is completed, B i has to be processed immediately; 3) B i cannot start processing until A i has been completely processed. Besides, we add flexibility for the first-stage machine M 1 such that it is able to process the second-stage operations, as an analogy with the relation between operating room and recovery room. We say M 1 has the multi-task flexibility. Our goal is the minimize the makespan, i.e. the maximum completion time of all jobs. To name our problem, we adopt the three-field notation α|β|γ introduced by Graham et al. [12] . In the α field (i.e. the scheduling environment), we use F 2 to represent the two-stage flowshop. In the β field (i.e. the job characteristics and constraints), we use "nwt" to represent the no-wait constraint and "mtflx M 1 → M 2 " to represent the multi-task flexibility of the first-stage machine. In the γ field (i.e. the objective function), we use C max to represent the classic makespan minimization. Thus our problem can be denoted as F 2 |nwt, mtf lx M 1 → M 2 |C max .

Flowshop problems with either nwt or mtflx constraint have been studied extensively in the literature [13, 4, 22, 18, 31] . However, the exploration of a flowshop under both the nwt and mtflx constraints is rare. To the best of our knowledge, the F 2 |nwt, mtf lx M 1 → M 2 |C max problem has never been studied before, though a preemptive version, i.e. F 2 |nwt, mtf lx, prmp|C max , was presented by Khorasanian and Moslehi [16] , who gave two mathematical models optimally solving small-sized instances and a local search heuristic for the large-sized instances. We, on the other hand, focus on the design of approximation algorithm. Suppose A is any approximation algorithm and I is an instance. Let C A max (I) and C * max (I) denote the makespan generated by A and the optimal algorithm, respectively. The performance ratio of the algorithm A on I is C A max (I) C * max (I) . The algorithm A is a ρ-approximation for a minimization problem if sup I C A max (I) C * max (I) ≤ ρ. Our main contributes are summarized as follows.

• We propose a new scheduling model F 2 |nwt, mtf lx M 1 → M 2 |C max , which finds applications in hospital intelligent management systems. In addition, our F 2 |nwt, mtf lx M 1 → M 2 |C max problem is able to model more real-world applications and thus has profound practical impact. The automated computer numerical control (CNC) machines are widely applied in metal cutting industries. They are highly flexible and can perform different operations as long as the cutting tools required for these operations are loaded in the tool magazine of the machine [7] . Due to the expensive cost of the CNC machines, the multi-task flexibility is allowed on these machines to decrease the operating cost. Multi-task flexibility can also arise in the assembly of printed circuit boards (PCB), as the feeder tapes holding the components to be inserted may be present either on one machine only, or on several machines. In modern manufacturing systems, robots are installed in order to reduce labor cost, to increase output, to provide more flexible production systems and to replace people working in dangerous or hazardous conditions [5] . They are mainly used as material handling devices in robotic cells, where a robotic cell contains two or more robot-served machines [15] . There are no buffers at or between the machines, which requires the job scheduling to satisfy the no-wait constraints. Considering modern manufacturing systems where each robot cell contains CNC machines or PCBs, our F 2 |nwt, mtf lx M 1 → M 2 |C max problem can perfectly model these applications.

• We study the NP-hardness of the proposed problem and present a NP-hardness proof via a reduction from the Partition problem. We also design an approximation algorithm with a worst-case performance ratio of 13 8 . At a high level, we first obtain a non-trivial lower bound for the optimal solution; then propose two greedy algorithms, which utilize the no-wait and multi-task flexibility constraints to explore the structural properties of our problem; finally construct an intricate combinatorial algorithm by invoking the aforementioned two algorithms as subroutines. A case-by-case analysis shows the approximation ratio 13 8 . The discovered structural properties are of independent interest as it can be utilized to study other related scheduling problems.

In the following context, Section 2 introduces the most related works; In Section 3, we give necessary definitions and notations, present a lower bound for the optimal makespan, and show a trivial NP-hardness proof for the F 2 |nwt, mtf lx M 1 → M 2 |C max problem. Our 13 8 -approximation algorithm is presented in Section 4 and analyzed in Section 5. Section 6 concludes the paper and proposes several directions for the future work.

There is an extremely rich literature on the flowshop scheduling problems with nwt (i.e. no-wait) or mtflx (i.e. multi-task flexibility) constraint. In this section, we review most related works mainly along these two directions.

In the traditional flowshop scheduling problem, all jobs need to be processed in order on the flowshop machines, i.e. each job starts on the first-stage machine, then it is processed on the second-stage machine, up to the last machine. The intermediate storage capacity between machines, named as buffer, are considered infinite and machines are always available for processing jobs [20] .

When buffers between machines are not available, i.e. intermediate storage capacity is considered zero, blocking occurs, as a job, having completed processing on a machine, remains on the machine until the next-stage machine becomes available for processing. Such a scenario is characterized as the blocking environment. The no-wait environment is similar to the blocking environment but more restrictive by requiring that a job must be processed from start to completion without any interruption either on or between machines. Under the three-field notation, the no-wait or blocking flow-shop scheduling problem with makespan minimization is denoted as F m |nwt|C max or F m |blocking|C max , respectively.

Flowshop scheduling under the no-wait or blocking environment has been investigated extensively in the literature. In particular, Reddi and Ramamoorthy [29] proved F 2 |nwt|C max is equivalent to F 2 |blocking|C max . It was shown that F 2 |nwt|C max can be reduced to a special case of the Traveling Salesman problem [26, 29] and can be solved in polynomial time by the Gilmore-Gomory algorithm [10] . When m ≥ 3, F m |nwt|C max is strongly NP-hard [30, 21] . Because of the complex nature of the general F m |nwt|C max problem, exact methods are used to solve small instances while heuristics and metaheuristics methods are more common for larger instances. Examples can be found in [28, 23, 1, 24, 2] . As the F 2 |nwt|C max problem is polynomially solvable, the following works either provide computationally efficient heuristics or consider its variant by changing environment constraints and/or adopting different objective functions. Glass, Gupta, and Potts [11] considered the case where jobs might have missing operations in F 2 |nwt|C max and presented an efficient heuristic with a worst-case ratio of 4/3. Wang, Yang, and Lin [34] proposed simulated annealing and genetic algorithms for F 2 |nwt|C max . Espinouse, Formanowicz, and Penz [9, 8] studied the complexity of the F 2 |nwt|C max problem with several machine availability constraints and proposed heuristic algorithms. Wang et al. [32] investigated a hybrid variant of F 2 |nwt|C max , where the first stage contains a single machine and the second stage contains several identical parallel machines, and designed a branch-and-bound algorithm. Allahverdi et al. [3] established local and global dominance relations to solve the no-wait two-stage flowshop scheduling problem to minimize maximum lateness, where setup times are considered separate from processing times. There are plenty other works on the no-wait or blocking flowshop scheduling. Readers may refer to three excellent surveys [13, 4, 22] . More specifically, Hall and Sriskandarajah [13] presented an excellent review of the literature, covering about 130 papers, on scheduling problems (including flowshop, job shop, and open shop) with no-wait and/or blocking in process since 1970s until mid-1993; The continuing survey paper by Allahverdi [4] provides analysis and an extensive review of more than 300 papers that appeared since the mid-1993 to the beginning of 2016; Miyata and Nagano [22] presented a thorough review on the flowshop scheduling problem with blocking conditions, covering 139 papers ranging from 1969 up to early 2019.

The multi-task flexibility allows the machine at one stage to process operations at the other stages. Suppose M i → M k denotes that the machine at the i-th stage is capable of processing operations at the k-th stage. Let M i ↔ M k indicate that M i → M k and M k → M i holds simultaneously.

Lee and Mirchandani [17] introduced and investigated the F 2 |mtf lx M 1 ↔ M 2 |C max problem. They studied its NP-hardness and presented an effective heuristic algorithm. Liao et al. [19] considered the F m |mtf lx|C max problem and presented two mixed integer programming models, one is for the case where the job sequence is given and the other is for the case where the job sequence is to be determined. Pan and Chen [25] studied three possible cases of the F 2 |mtf lx|C max problem, i.e.

The NP-hardness was proved for all cases. In addition, they developed three branch and bound algorithms. Cheng and Wang [6] proved the NP-hardness for the F 2 |mtf lx M 1 ↔ M 2 |C max problem in the ordinary sense and presented a pseudo-polynomial dynamic programming approach. Motivated by the applications in image processing, Wei and He [27] studied a general variant of the F 2 |mtf lx M 1 ← M 2 |C max problem, where each first-stage operation A i needs more processing time on M 2 compared with M 1 . They provided a pseudo-polynomial time optimal algorithm and a polynomial time approximation algorithm with a tight worst-case ratio 2. Wei et al. [33] gave a fully polynomial time approximation scheme for the F 2 |mtf lx M 1 ← M 2 |C max problem.

Recall that in the F 2 |nwt, mtf lx M 1 → M 2 |C max problem, each job J i , i ∈ {1, 2, . . . , n} needs to be processed non-preemptively without any time delay and the machine M 1 can process the secondstage operations. Suppose A i and B i have the processing time a i and b i respectively. Let p i = a i +b i denote the total processing time of the job J i . We remark that B i cannot start processing until A i has been completed and B i has the same processing time no matter on M 1 or M 2 . Let [n] denote the integer set {1, 2, . . . , n} for any positive integer n. As all indexes in the following context are integers, ∈ [i, j] represents ∈ {i, i + 1, . . . , j} for an index . Let a = i∈[n] a i and b = i∈[n] b i denote the total processing time of operations on M 1 and M 2 respectively. For a feasible schedule π, its makespan is defined as C π max . Suppose π * is the optimal schedule and C π * max is its makespan. We use C * max to represent C π * max for the sake of simplicity.

The optimal makespan C * max for the F 2 |nwt, mtf lx M 1 → M 2 |C max problem can be lower bounded by

Proof. We only need to prove the lower bound max max

For any job, its two operations needs to be processed in order and without any interruption either on or between machines. Therefore, the first term is trivial. When M 1 finishes processing all first-stage operations, at least one second-stage operation needs to be processed, from which the second term follows. As the second-stage operation of each job can only be processed after the corresponding first-stage operation is finished on M 1 , there is a necessary idle time slot of a duration at least min i∈[n] {a i } on M 2 before it starts processing any operation. Thus, the third term follows.

2

The proof is similar to the NP-hardness proof for the F 2 |mtf lx M 1 → M 2 |C max problem [25] .

The main idea is constructing a reduction from the Partition problem, which decides whether a given multiset S of n positive integers {s 1 , s 2 , . . . , s n } can be partitioned into two subsets S 1 and S 2 such that the sum of the numbers in S 1 equals the sum of the numbers in S 2 .

Given a Partition instance, we define a F 2 |nwt, mtf lx M 1 → M 2 |C max instance with each job J i having processing time a i = 0, b i = s i , i ∈ [n]. According to the lower bound for the optimal makespan we obtained in Theorem 3.1, the optimal makespan of the constructed instance is at least 1 2 i∈[n] s i . We can easily observe that the Partition instance has a Yes answer if and only if the constructed instance has a makespan of 1 2 i∈[n] s i . 2

In this section, we give descriptions for two versions of the 13 8 -approximation algorithm. We sort jobs in non-increasing order with respect to the size of the second-stage operation. In sequel, we assume the job sequence J 1 , J 2 , . . . , J n satisfies b 1 ≥ b 2 ≥ . . . ≥ b n without loss of generality. Next, we introduce the key concepts, critical job and critical position. The critical position is the very first position in the job sequence such that b 1 is no larger than the total processing time of the second-stage operations for jobs before this position (inclusively). The critical job is the job at the critical position.

And we say k is the critical position.

We say a machine is idle or not busy if it is not processing any operations. A flowshop is not busy before it completes processing all jobs if both machines of the flowshop have the overlapping idle time slot before the makespan. If the flowshop is not busy under a feasible schedule, we can always request the flowshop to process the unfinished operations earlier to fill this idle gap and thus obtain a feasible schedule with a smaller makespan. Without loss of generality, in the following discussions, we only consider the feasible schedules that keep the flowshop always busy.

Roughly, our algorithm finds the critical job and then schedule the jobs before and after the critical position by invoking two greedy subroutines. Both subroutines take advantage of the multitask flexibility of the first-stage machine and schedule a part of the second-stage operations on M 1 such that the flowshop is always busy and the overlapping processing time between M 1 and M 2 , i.e. the total amount of time that M 1 and M 2 are simultaneously processing operations, is greedily maximized. This is why our algorithm is named as Max-Overlap. Let o denote the overlapping processing time between M 1 and M 2 .

Lemma 4.1 For any feasible schedule π, the makespan can be computed as

Proof. Suppose T 1 is the total time before the makespan that M 1 is busy while M 2 is idle. Similarly, we can define T 2 . As o is the overlapping processing time between M 1 and M 2 , the total processing time of operations on the flowshop is a

This proves the lemma. 2

The first subroutine, denoted as Alg1(g, i, j), takes in a subsequence of jobs J i , J i+1 , . . . , J j , i ≤ j ∈ [n] and a job J g , g ∈ [i, j]. Alg1 considers the case where J g has a relatively large second-stage operation with respect to the total processing time of J i , J i+1 , . . . , J j . When we call Alg1(g, i, j), let M 1 start processing A g as early as possible following the existing subschedule on the flowshop and greedily schedule the jobs J i , J i+1 , . . . , J j in order on M 1 right after A g without any delay. Refer to Algorithm 1 for detailed description and Figure 1 for a visualized demo. As a result, the flowshop is always busy when processing the job set {J g } ∪ {J i , J i+1 , . . . , J j }. Then, we have the following lemma via a simple discussion whether b g ≤ ∈[i,j] p holds. 

. . , J j } such that the flowshop is always busy and the overlapping time is large.

# Sub-schedule on M 1 2: Start processing σ 1 as early as possible; 3: Let σ 2 = B g ; # Sub-schedule on M 2 4: Start processing σ 2 as early as possible; 5: return π = (σ 1 , σ 2 );

The second subroutine, denoted as Alg2(i, j), takes in a subsequence of jobs J i , J i+1 , . . . , J j , i ≤ j ∈ [n]. We pair up the adjacent jobs {J , J +1 }, ∈ {i, i + 2, i + 4, . . .}. Then we swap the jobs in the same pair and obtain a new job sequence J i+1 , J i , J i+3 , J i+2 , . . . . If there are even number of jobs, the reordered job sequence is J i+1 , J i , J i+3 , J i+2 , . . . , J j , J j−1 ; otherwise, the reordered job sequence is J i+1 , J i , J i+3 , J i+2 , . . . , J j−1 , J j−2 , J j . We alternatively schedule the jobs such that one is processed on both machines and the other one is completely processed on M 1 . Refer to Algorithm 2 for detailed description and Figure 2 for a visualized demo.

. Therefore, the schedule returned by Alg2(i, j) makes the flowshop always busy. We estimate the overlapping time between M 1 and M 2 in Lemma 4.3. 

Proof.

If there are even number of jobs, the reordered job sequence is J i+1 , J i , J i+3 , J i+2 , . . . , J j , J j−1 . For each ∈ {i, i + 2, i + 4, . . .}, J is completely processed on M 1 while J +1 is processed on both machines. Because of p = a + b ≥ b +1 , when M 1 starts processing J , M 2 starts processing B +1 .

No-wait two-stage flowshop problem with multi-task flexibility of the first machine9 (Refer to Figure 2 .) The overlapping time can be calculated as

where the first inequality is because of

When there are odd number of jobs, the overlapping time can be computed similarly.

This proves the lemma. 

. . . Recall that b 1 has relatively large with respect to the total processing time of the second-stage operation of jobs before the critical position if it exists. More specifically, ∈[2,k−1] b < b 1 ≤ ∈[k,n] b for the critical position k. The rough idea of the Max-Overlap algorithm is to schedule the jobs sequences J 1 , . . . , J k−1 and J k , . . . , J n with Alg1 and Alg2, respectively. However, there are two problems: 1) the critical position may not exist; 2) when the critical position is close to the boundary, i.e. 1 or n, the trivial combination of Alg1 and Alg2 is not able to achieve the approximation ratio 13/8. Therefore, our algorithm Max-Overlap needs to handle these special cases carefully. Refer to Algorithm 3 for a detailed description of the Max-Overlap algorithm.

In this section, we will prove that the worst-case performance ratio of the Max-Overlap algorithm is 13 8 . As shown in Algorithm 3, there are two versions for the Max-Overlap algorithm. The first version is the brute-force implementation of the second version. It simply computes 9 feasible schedule candidates and outputs the one with the minimum makespan. This version is easy to implement but provides little information for the worst-case analysis. On the other hand, the second version offers a detailed case-by-case discussion to avoid the unnecessary computation of some schedule candidates in the first version. Such discussions are helpful to our analysis. We summarize the cases and corresponding analyses in Table 1 . , π 5 , π 6 Lemma 5.5 Case 6 5 16 LB < b 1 < 3 8 LB k ≤ 3 π 4 , π 5 , π 6 , π 7 , π 8 , π 9 Lemma 5.6

Lemma 5.1 In Case 1, i.e. b 1 ≥ 3 8 LB, we have C π 1 max ≤ 13 8 C * max .

Proof. In this case, we consider the schedule π 1 , which is returned by Alg1(1, 2, n) . By Lemma 4.2 and Lemma 4.1,

By Theorem 3.1, we have C * max ≥ LB ≥ max{ a+b 2 , p 1 }. When b 1 ≤ ∈[2,n] p , we have

where the first inequality follows from b 1 ≥ 3 8 LB. When b 1 > ∈[2,n] p , we have

No-wait two-stage flowshop problem with multi-task flexibility of the first machine11

Input: a job sequence J 1 , J 2 , . . . , J n with b 1 ≥ b 2 ≥ . . . , ≥ b n ; Output: a feasible schedule such that the flowshop is always busy and the overlapping time is large.

A brute-force version:

1: π 1 = Alg1(1, 2, n); 2: π 2 = Alg2(1, n); 3: π 3 = Alg1(1, 2, k − 1) followed by Alg2(k, n); 4: π 4 = Alg1(1, 2, 3) followed by Alg2(4, n); 5: π 5 = Alg1(1, 2, 3) followed by Alg1(4, 5, n); 6: π 6 = Alg1(1, 2, 2) followed by Alg1(3, 4, n); 7: π 7 = Alg1(3, 4, n) followed by Alg1(1, 2, 2); 8: π 8 = Alg1(1, 4, n) followed by Alg1(2, 3, 3); 9: π 9 = Alg1(1, 4, n) followed by Alg1(3, 2, 2); 10: π = arg min π∈{π 1 ,π 2 ,...,π 9 } {C π max }; 11: return π;

An efficient case-by-case version: π = arg min π∈{π 4 ,π 5 ,π 6 ,π 7 ,π 8 ,π 9 } {C π max }; Proof. In this case, we consider the schedule π 2 , which is returned by Alg2(1, n) . By Lemma 4.3 and Lemma 4.1,

By Theorem 3.1, we have C * max ≥ LB ≥ max{ a+b 2 , a, p 1 }. Then we have

where the first inequality follows from b 1 ≤ 2 8 LB. This proves the lemma. 

Proof. In this case, we consider the schedule π 1 , which is returned by Alg1(1, 2, n) . As the critical position does not exist, it must be the case

By Lemma 4.2 and Lemma 4.1,

where the first inequality follows from Eq.(5.1); the third inequality is because of C * max ≥ LB ≥ a and b 1 < 3 8 LB. This proves the lemma. Proof. As b 1 ≥ b 2 ≥ . . . ≥ b n and k ≥ 4, we have

where the last inequality holds due to the definition of the critical job.

Case 4.1 k < n: we consider the schedule π 3 , which is the sub-schedule Alg1(1, 2, k − 1) followed by the sub-schedule Alg2(k, n). By Lemma 4.2 and Lemma 4.3, the total overlapping time between M 1 and M 2 can be lower bounded as

where the second inequality follows from the definition of the critical job; the third inequality is due to the fact b k−1 ≥ b k ; the last inequality is because of Eq.(5.2).

By Theorem 3.1, we have C * max ≥ LB ≥ max{ a+b 2 , a}. Combing Lemma 4.1 and b 1 < 3 8 LB, we have

Case 4.2 k = n: we consider the schedule π 1 , which is returned by Alg1(1, 2, n) . According to the definition of the critical job, b 1 > ∈[2,n−1] b . As k ≥ 4 holds and b 1 ≥ b 2 ≥ . . . ≥ b n , we have b 1 > 2b n , from which we have

From Lemma 4.2, Lemma 4.1, and C * max ≥ LB ≥ a, the makespan can be computed as

where the first inequality is because of Eq.(5.3); the second inequality is due to the fact b 1 < 3 8 LB. To summarize, min{C π 1 max , C π 3 max } ≤ 13 8 C * max holds in Case 4. This proves the lemma. 2

The following lemmas discuss the cases when the critical position k ≤ 3. To avoid trivial cases, we assume there are at least five jobs, i.e. n ≥ 5.

Lemma 5.5 In Case 5, i.e. 2 8 LB < b 1 < 5 16 LB and the critical position k ≤ 3, we have min{C π 4 max , C π 5 max , C π 6 max } ≤ 13 8 C * max .

Proof. By the definition of the critical job and the fact that

we investigate three subcases based on the value of b 4 .

In this subcase, we consider the schedule π 4 , which is Al-g1(1, 2, 3) followed by Alg2(4, n). 

where the second inequality follows from b 1 ≤ b 2 + b 3 ; the third inequality is because of Eq.(5.4); the last inequality is due to b 2 + b 3 ≤ 3 2 b 1 . By Theorem 3.1, we have C * max ≥ LB ≥ max{ a+b 2 , a}, and thus

In this subcase, we consider the schedule π 5 , which is Alg1(1, 2, 3) followed by Alg1(4, 5, n). 

No-wait two-stage flowshop problem with multi-task flexibility of the first machine15

where the second inequality is because of b

∈[4,n] b , and Eq.(5.5); the third inequality is due to b 2 + b 3 ≤ 3 2 b 1 . By Theorem 3.1, we have C * max ≥ LB ≥ max{ a+b 2 , a}, and thus

∈[4,n] b : In this subcase, we consider the schedule π 6 , which is Al-g1(1, 2, 2) followed by Alg1 (3, 4, n) .

By Lemma 4.2, the total overlapping time between M 1 and M 2 is

where the second inequality follows from b 1 ≥ b 2 ≥ . . . ≥ b n ; the third inequality is because of b 4 ≥ 2 3 ∈[4,n] b . By Theorem 3.1, we have C * max ≥ LB ≥ max{ a+b 2 , a}, and thus

where the first inequality is due to b 2 ≥ b 3 ; the second inequality follows from b 3 ≤ 1

we consider the schedule π 6 , which is Alg1(1, 2, 2) followed by Alg1 (3, 4, n) . By Lemma 4.2, the total overlapping time between M 1 and M 2 is

By Theorem 3.1, we have C * max ≥ LB ≥ max{ a+b 2 , a}. If b 3 ≤ ∈ [4,n] p , by Lemma 4.1, we have

where the third inequality is because of

where the third inequality is because of b 1 ≤ 5 16 LB. To summarize, min{C π 4 max , C π 5 max , C π 6 max } ≤ 13 8 C * max holds in Case 5. This proves the lemma. 2

Lemma 5.6 In Case 6, i.e. 5 16 LB ≤ b 1 < 3 8 LB and the critical position k ≤ 3, we have min{C π 4 max , C π 5 max , C π 6 max , C π 7 max , C π 8 max , C π 9 max } ≤ 13 8 C * max .

Proof. By the definition of the critical job and the fact that

Similar to Case 5, we discuss two subcases according to the value of b 2 + b 3 . 

where the second inequality follows from b 1 ≤ b 2 + b 3 ; the third inequality is because of Eq.(5.4); the fourth inequality is because of ∈[4,n] b > 2 3 b 1 ; the last inequality is due to b 1 ≥ 5 16 LB. By Theorem 3.1, we have C * max ≥ LB ≥ a+b 2 , and thus

In this subcase, we consider the schedule π 5 , which is Alg1(1, 2, 3) followed by Alg1(4, 5, n). As b 4 ≤ 2 3 ∈[4,n] b , Eq.(5.5) also holds in this case. That is,

By Lemma 4.2, the total overlapping time between M 1 and M 2 is

where the second inequality is because of b 1 ≤ b 2 + b 3 and Eq.(5.5); the third inequality is due to the condition ∈[4,n] b > 2 3 b 1 in Case 6.1.1; the last inequality is due to b 1 ≥ 5 16 LB. Similar to Case 6.1.1.1, we have C π 5 max ≤ 13

When a 2 ≥ a 3 , we consider the schedule π 8 , which is Alg1(1, 4, n) followed by Al-g1(2, 3, 3). When a 2 < a 3 , we consider the schedule π 9 , which is Alg1(1, 4, n) followed by Alg1 (3, 2, 2) . Due to the symmetry between π 8 and π 9 , the analysis for the case a 2 < a 3 will be similar to the case a 2 ≥ a 3 . Next, we focus on analyzing π 8 when a 2 ≥ a 3 .

In this case, using Lemma 4.2 and Lemma 4.3 to estimate the lower bound of the overlapping processing time o between M 1 and M 2 is not enough. We need to consider the overlapping processing time caused by the concatenation of Alg1(1, 4, n) and Al-g1(2, 3, 3). Refer to Figure 3 for details. When ∈ [4,n] p + a 2 ≥ b 1 , M 1 is always busy (refer to the left subfigure in Figure 3 ) and thus the total overlapping time between M 1 and M 2 is o ≥ b 1 +min{b 2 , p 3 } = b 1 +b 3 . By Lemma 4.1,

where the second inequality is because of Eq.(5.6); the third inequality is due to b 1 ≤ 5 16 LB.

When ∈ [4,n] p + a 2 < b 1 (refer to the right subfigure in Figure 3 ), the makespan can be computed as

By Eq.(5.6), we have

from which we can obtain a 2 ≤ 5 9 b 1 .

where the second inequality is because of a 3 ≤ a 2 ≤ 5 9 b 1 ; the second inequality is due to Figure 3 : An illustration for π 8 = Alg1(1, 4, n) followed by Alg1 (2, 3, 3) . The cases ∈[4,n] p + a 2 ≥ b 1 and ∈ [4,n] p + a 2 < b 1 are shown on the left and right respectively. Note that p 3 < b 2 may happen, which is not reflected in the figure.

• Case 6.1.2 ∈[4,n] b ≤ 2 3 b 1 : In this subcase, we consider the schedule π 6 , which is Al-g1(1, 2, 2) followed by Alg1(3, 4, n). By Lemma 4.2, the total overlapping time between M 1 and M 2 is

where the second inequality follows from

By Lemma 4.1, the makespan can be calculated as

No-wait two-stage flowshop problem with multi-task flexibility of the first machine19

where the second inequality is due to b 3 ≤ 3 5 b 1 and ∈[4,n] b ≤ 2 3 b 1 ; the third inequality follow from b 1 < 3 8 LB.

Case 6.2 b 2 +b 3 > 6 5 b 1 : we investigate two subcases based on whether a 1 is equal to max{a 1 , a 2 , a 3 }.

• Case 6.2.1 max{a 1 , a 2 , a 3 } = a 1 :

Similar to Case 6.1.1.3, we consider the schedule π 8 and π 9 when a 2 ≥ a 3 and a 2 < a 3 respectively. Again, due to the symmetry between these two subcases, we focus on analyzing π 8 when a 2 ≥ a 3 . Recall that π 8 is Alg1(1, 4, n) followed by Alg1(2, 3, 3). A visualization demo can be found in Figure 3 .

When ∈[4,n] p +a 2 ≥ b 1 , M 1 is always busy (refer to the left subfigure in Figure 3 ) and thus the total overlapping time between M 1 and M 2 is o ≥ b 1 + min{b 2 , p 3 } = b 1 + b 3 . Therefore, we have

where the second inequality is because of b 1 ≥ b 2 ; the third inequality is due to b 2 + b 3 > 6 5 b 1 ; the fourth inequality follows from b 1 ≥ 5 16 LB. When ∈[4,n] p + a 2 < b 1 (refer to the left subfigure in Figure 3 ), we have a 2 ≤ b 1 and the makespan can be computed as

where the second inequality is because of b 2 ≤ b 1 and a 1 ≤ max{a 2 , a 3 } = a 2 ≤ b 1 .

• Case 6.2.2 max{a 1 , a 2 , a 3 } = a 1 : In this subcase, we consider the schedule π 7 , which is Alg1(3, 4, n) followed by Alg1(1, 2, 2).

When ∈[4,n] p + a 1 ≥ b 3 (refer to the left subfigure in Figure 4 ), M 1 is always busy and thus the total overlapping time between M 1 and M 2 is

By Lemma 4.1, we have

When ∈[4,n] p +a 1 < b 3 , (refer to the right subfigure in Figure 4) , the makespan is computed as

where the second inequality is because of max{a 1 , a 2 , a 3 } = a 1 and b 1 ≥ b 2 ≥ b 3 ; the third inequality is due to a 1 ≤ ∈[4,n] p + a 1 < b 3 ≤ b 1 . Figure 4 : An illustration for π 7 = Alg1(3, 4, n) followed by Alg1 (1, 2, 2) . The cases ∈[4,n] p + a 1 ≥ b 3 and ∈[4,n] p + a 1 < b 3 are shown on the left and right respectively. Note that p 2 < b 1 may happen, which is not reflected in the figure.

To summarize, min{C π 4 max , C π 5 max , C π 6 max , C π 7 max , C π 8 max , C π 9 max } ≤ 13 8 C * max holds in Case 6. This proves the lemma.

Theorem 5.1 The Max-Overlap algorithm is a O(n)-time approximation algorithm with a worst-case performance ratio 13 8 .

Proof. We consider the brute-force version, which simply computes 9 feasible schedules and returns the one with the minimum makespan. Without loss of generality, we assume all operations are integers. Sorting jobs with respect to the size of the second-stage operations takes linear time if any linear sorting algorithm, such as Radix-Sort, is applied. Computing each schedule takes O(n) time. In total, the Max-Overlap algorithm has a linear time complexity.

Lemmas 5.1-5.6 consider all possible inputs and guarantee to find a feasible schedule with makespan at most 13 8 C * max . In other words, among the 9 schedules {π 1 , π 2 , . . . , π 9 }, no matter what job sequence is taken as an input, there always exists one schedule π such that C π max ≤ 13 8 C * max . Therefore, the approximation ratio of the Max-Overlap algorithm is 13 8 . 2

In this paper, we study the F 2 |nwt, mtf lx M 1 → M 2 |C max problem, a variant of the classic twostage flowshop scheduling problem with the makespan minimization objective. We add the no-wait constraint and allow the first-stage machine to have the multi-task flexibility. Both constraints are motivated by the arrangement of two most intensive resources in hospitals, i.e. operation room beds and recovery room beds. In addition, our problem is capable of modeling more real-world applications, such as robot cell scheduling containing CNC machines or PCBs, We investigate the NP-hardness of the proposed problem and design a linear-time algorithm achieving an approximation ratio of 13 8 . Our algorithm utilizes both no-wait and multi-task flexibility to compress the feasible schedule such that the overlapping processing time between two machines is as large as possible. The analysis of our algorithm is based on case-by-case discussions by using the nontrivial structural properties of the problem we discovered. We believe the approximation ratio cannot have a big improvement under the current ideas and structural properties. In future, we will follow these three directions: 1) discover more novel structural properties to increase the approximation ratio; 2) extend the current model for more real-applications to introduce more interesting models and utilize the current idea to design practical algorithms; 3) design high performance heuristic algorithms for the problem and conduct simulation and/or numerical study.

New heuristics for no-wait flowshops to minimize makespan

No-Wait Flowshop Scheduling Problem with two Criteria

Two-machine no-wait flowshop scheduling problem with uncertain setup times to minimize maximum lateness

A survey of scheduling problems with no-wait in process

Production Management Systems

A note on scheduling alternative operations in two-machine flowshops

Throughput optimization in two-machine flowshops with flexible operations

Complexity results and ap-proximation algorithms for the two machine no-wait flow-shop with limited machine availability

Minimizing the makespan in the two-machine no-wait flow-shop with limited machine availability

Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem

Two-machine no-wait flow shop scheduling with missing operations

Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey

A Survey of Machine Scheduling Problems with Blocking and No-Wait in Process

Operating rooms scheduling

Cyclic scheduling in a robotic production line

Two-machine flow shop scheduling problem with blocking, multitask flexibility of the first machine, and preemption

Concurrent routing, sequencing, and setups for a two-machine flexible manufacturing cell

An iterated greedy heuristic for no-wait flow shops with sequence dependent setup times, learning and forgetting effects

No-wait two-stage flowshop problem with multi-task flexibility of the first machine23

Flow-shop scheduling with flexible processors

Addressing the gap in scheduling research: A review of optimization and heuristic methods in production scheduling

Complexity of flowshop scheduling problems with a new blocking constraint

The blocking flow shop scheduling problem: A comprehensive and conceptual review Expert Systems

A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem

An improved iterated greedy algorithm for the no-wait flow shop scheduling problem with makespan criterion

Scheduling alternative operations in two-machine flow-shops

Ein Beitrag zum Reihenfolgeproblem

A two-stage semi-hybrid flowshop problem in graphics processing

A No-Wait Flowshop Scheduling Heuristic to Minimize Makespan

On the flow-shop sequencing with no wait in process

The Three-Machine No-Wait Flow Shop is NP-Complete

A hybrid multi-objective immune algorithm for a flow shop scheduling problem with bi-objectives: Weighted mean completion time and weighted mean tardiness

A branch-and-bound algorithm for two-stage no-wait hybrid flowshop scheduling

Comparison of scheduling efficiency in two/three-machine no-wait flow shop problem using simulated annealing and genetic algorithm

A FPTAS for a two-stage hybrid flow shop problem and optimal algorithms for identical jobs

USA Coronavirus