# Minimizing the Makespan for a Two-Stage Three-Machine Assembly Flow Shop Problem with the Sum-of-Processing-Time Based Learning Effect

Authors: Win-Chin Lin
Journal: Discrete Dynamics in Nature and Society
 (2018)

---

## Abstract

Two-stage production process and its applications appear in many production environments. Job processing times are usually assumed to be constant throughout the process. In fact, the learning effect accrued from repetitive work experiences, which leads to the reduction of actual job processing times, indeed exists in many production environments. However, the issue of learning effect is rarely addressed in solving a two-stage assembly scheduling problem. Motivated by this observation, the author studies a two-stage three-machine assembly flow shop problem with a learning effect based on sum of the processing times of already processed jobs to minimize the makespan criterion. Because this problem is proved to be NP-hard, a branch-and-bound method embedded with some developed dominance propositions and a lower bound is employed to search for optimal solutions. A cloud theory-based simulated annealing (CSA) algorithm and an iterated greedy (IG) algorithm with four different local search methods are used to find near-optimal solutions for small and large number of jobs. The performances of adopted algorithms are subsequently compared through computational experiments and nonparametric statistical analyses, including the Kruskal–Wallis test and a multiple comparison procedure.


---

## Body

## 1. Introduction

This study considers a two-stage assembly scheduling problem consisting ofn jobs. Each of the n jobs has two parts (components) to be processed first, and the parts are then assembled on one assembly operation into an ordered product. At the first stage, two distinct parts can be fabricated at the same time in two dedicated machines, M1 and M2. Once the parts are finished, they are transmitted to the second stage, the assembly stage. There is a single assembly machine, M3, in this stage to assemble parts into the ordered product. The assembly work can only start after the two parts are completed and delivered to the assembly line. The objective of the production plan is to minimize the maximum completion time among all the jobs, i.e., to minimize the makespan.Wu et al. [1] studied the makespan minimization in the two-stage three-machine flow shop problem with position-based learning consideration based on Biskup [2]. Wu et al. [3] addressed a two-stage three-machine flow shop scheduling problem with a cumulated learning function to minimize the flowtime (or total completion time). They developed a branch-and-bound algorithm and proposed six versions of hybrid particle swam optimization (PSO) to solve it. However, the sum-of-processing-times-based learning model (based on [4]) has yet to be considered in two-stage assembly flow shop environment. In light of the lack of studies on the sum-of-processing-times-based learning model, this research studies a two-stage three-machine assembly problem with a learning effect based on sum of the processing times of already processed jobs to minimize the makespan criterion.The paper proceeds as follows. Section2 presents some notations and problem definition. Section 3 provides some dominant properties and a lower bound to be used in a branch-and-bound method and then introduces a cloud theory-based simulated annealing (CSA) and four versions of the iterated greedy (IG) algorithm. Section 4 provides computational results. Section 5 is the conclusion.


### 1.1. Literature Survey

Invoking a real-world example of fire engine manufacturing and assembly procedure, Lee et al. [5] studied the issue of minimizing the makespan in the three-machine assembly-type flow shop scheduling problem. A fire engine consists of two parts, a body and a chassis, which are manufactured separately in two production lines in the plant; an engine, bought from outside, can be considered ready. Once the body and chassis are completed, they will be transmitted to the assembly line, where the end product, a fire engine, is built up. They proved the problem is strongly NP-complete, discussed some special polynomial-time solvable cases, and constructed exact and heuristics for them. Potts et al. [6] also demonstrated the complexity of the proposed problem with several machines in the first stage. They introduced several heuristic algorithms and presented the worst-case analysis of performances of these algorithms. Hariri and Potts [7] developed a branch-and-bound method, embedded with some dominance properties, for the considered problem with several machines in the first stage. Sun et al. [8] proposed 14 heuristics algorithms to solve the problem.Allahverdi and Al-Anzi [9] proposed two evolutionary algorithms, a particle swarm optimization (PSO) and a tabu search, and a simple efficient algorithm to solve the considered problem. Koulamas and Kyparisis [10] studied a two-stage assembly flow shop scheduling problem with uniform parallel machines on one or both stages. They presented an asymptotically optimal heuristic to minimize the makespan, as the number of jobs increase. Their results improved earlier results in some situations. Fattahi et al. [11] considered the same problem but all machines in the first (possibly including two manufacturing stages) stage(s) can process all kinds of parts, named a hybrid flow shop in the first stage(s). They proposed several heuristics based on Johnson’s rule and evaluated the performance of them. Fattahi et al. [12] also considered the hybrid flow shop problem but with setup time and presented a hierarchical branch-and-bound algorithm with several lower bounds and upper bounds. Hatami et al. [13] addressed a distributed assembly permutation scheduling problem in which the first stage comprised several identical flow shop factories. These factories, each with a permutation flow shop scheduling problem, produced parts which were later assembled by a single machine in the assembly stage. Komaki et al. [14] addressed a two-manufacturing-stage hybrid flow shop scheduling problem and one assembly stage to minimize the makespan, where the hybrid meant identical parallel machines or dedicated machines could present in the fabrication stages. They presented a lower bound, several heuristics, and two metaheuristic algorithms based on an artificial immune system. Their computational results showed the outperformance of the proposed lower bound and heuristic algorithms. Jung et al. [15] considered a slightly different two-stage assembly scheduling problem. A single manufacturing machine was used in the first stage to produce various types of parts which were assembled into various products (ordered by customers) in the second stage. The aforementioned studies addressed the problem with respect to the makespan criterion.With regard to performance criteria other than the makespan for two stages or more stages assembly flow shop problems, Allahverdi and Aydilek [16] provided research works focusing on the following criteria: mean (or total) completion time, a weighted sum of mean completion time and makespan, maximum lateness, total tardiness, and bicriteria. Some of these studies were together with other machine settings, for example, setup times often treated as separate ones from processing times or due dates required by customers. For instance, Maleki-Darounkolaei et al. [17] minimized the weighted mean completion time and makespan for the proposed problem with sequence-dependent setup times and blocking times. For more studies on different criteria and different machine settings for two-stage or three-stage assembly flow shop problem, readers can refer to Al-Anzi and Allahverdi [18], Allahverdi and Al-Anzi [19], Al-Anzi and Allahverdi [20], Allahverdi and Al-Anzi [21], Fattahi et al. [11], Allahverdi and Aydilek [16], and Jung et al. [15], among others.Several real-life examples or applications for two-stage and three-stage assembly problem can be found in Lee et al. [5], Potts et al. [6], Tozkapan et al. [22], Allahverdi and Al-Anzi [19], Al-Anzi and Allahverdi [20], Sung and Kim [23], Allahverdi and Al-Anzi [24], Cheng et al. [25], Fattahi et al. [11], Mozdgir et al. [26], Fattahi et al. [12], Hatami et al. [13], and Jung et al. [15], among others.On the other hand, the learning concept has been widely addressed in different branches of industry, for example, product development, job rotation, and job scheduling problem [27]. The first application in scheduling literature appeared in airplane’s manufacturing, where the assembly costs reduced as the times of repetitions increased [28]. Yelle [29] gave a comprehensive survey on learning curves applied in many industries including manufacturing sector. In addition to the excellent review on scheduling with learning effect by Biskup [30], Anzanello and Fogliatto [27] also gave a review on the wide applicability of learning curve models in production systems. The work of Azzouz et al. [31] is a more recent survey paper in the scheduling literature providing applications of learning effects.In scheduling techniques, Biskup [2] and Cheng and Wang [32] were some of the early researchers who proposed modeling a learning effect by a learning curve (function). Since then, many other learning curves (functions) in connection with a single machine, flow shop, or other scheduling problems, have been developed and modified.Kuo and Yang work [4], one of the extensively discussed studies on the scheduling research community, proposed the sum-of-processing-times-based learning model, in which the real processing time of a job is relevant to the sum of the previous work times. Actually, the sum-of-processing-times based learning model is relevant to a long-winded and uninterrupted production process in which initial steps are set up. In manufacturing steel plates or bars by a foundry, the products are required to be inspected for surface defects. A single inspector is regarded as a processor or a system to work on those steel bars (jobs). After the processor finishes some work units (jobs), he will spend less time on processing follow-up work units as his experiences grow. Thus, Dondeti and Mohanty [33] modeled the real processing time of a job as a function of the sum of the processing times of the already processed jobs.Further modifications of the sum-of-processing-times based learning effect in scheduling problems were proposed by Cheng et al. [34], Yin et al. [35], Rudek [36], Wu et al. [37], Lu et al. [38], Wu and Wang [39], and Pei et al. [40], among others. The readers may refer to Azzouz et al. [31] for other commonly discussed learning models: position-based learning, truncated learning, and exponential learning.


## 1.1. Literature Survey

Invoking a real-world example of fire engine manufacturing and assembly procedure, Lee et al. [5] studied the issue of minimizing the makespan in the three-machine assembly-type flow shop scheduling problem. A fire engine consists of two parts, a body and a chassis, which are manufactured separately in two production lines in the plant; an engine, bought from outside, can be considered ready. Once the body and chassis are completed, they will be transmitted to the assembly line, where the end product, a fire engine, is built up. They proved the problem is strongly NP-complete, discussed some special polynomial-time solvable cases, and constructed exact and heuristics for them. Potts et al. [6] also demonstrated the complexity of the proposed problem with several machines in the first stage. They introduced several heuristic algorithms and presented the worst-case analysis of performances of these algorithms. Hariri and Potts [7] developed a branch-and-bound method, embedded with some dominance properties, for the considered problem with several machines in the first stage. Sun et al. [8] proposed 14 heuristics algorithms to solve the problem.Allahverdi and Al-Anzi [9] proposed two evolutionary algorithms, a particle swarm optimization (PSO) and a tabu search, and a simple efficient algorithm to solve the considered problem. Koulamas and Kyparisis [10] studied a two-stage assembly flow shop scheduling problem with uniform parallel machines on one or both stages. They presented an asymptotically optimal heuristic to minimize the makespan, as the number of jobs increase. Their results improved earlier results in some situations. Fattahi et al. [11] considered the same problem but all machines in the first (possibly including two manufacturing stages) stage(s) can process all kinds of parts, named a hybrid flow shop in the first stage(s). They proposed several heuristics based on Johnson’s rule and evaluated the performance of them. Fattahi et al. [12] also considered the hybrid flow shop problem but with setup time and presented a hierarchical branch-and-bound algorithm with several lower bounds and upper bounds. Hatami et al. [13] addressed a distributed assembly permutation scheduling problem in which the first stage comprised several identical flow shop factories. These factories, each with a permutation flow shop scheduling problem, produced parts which were later assembled by a single machine in the assembly stage. Komaki et al. [14] addressed a two-manufacturing-stage hybrid flow shop scheduling problem and one assembly stage to minimize the makespan, where the hybrid meant identical parallel machines or dedicated machines could present in the fabrication stages. They presented a lower bound, several heuristics, and two metaheuristic algorithms based on an artificial immune system. Their computational results showed the outperformance of the proposed lower bound and heuristic algorithms. Jung et al. [15] considered a slightly different two-stage assembly scheduling problem. A single manufacturing machine was used in the first stage to produce various types of parts which were assembled into various products (ordered by customers) in the second stage. The aforementioned studies addressed the problem with respect to the makespan criterion.With regard to performance criteria other than the makespan for two stages or more stages assembly flow shop problems, Allahverdi and Aydilek [16] provided research works focusing on the following criteria: mean (or total) completion time, a weighted sum of mean completion time and makespan, maximum lateness, total tardiness, and bicriteria. Some of these studies were together with other machine settings, for example, setup times often treated as separate ones from processing times or due dates required by customers. For instance, Maleki-Darounkolaei et al. [17] minimized the weighted mean completion time and makespan for the proposed problem with sequence-dependent setup times and blocking times. For more studies on different criteria and different machine settings for two-stage or three-stage assembly flow shop problem, readers can refer to Al-Anzi and Allahverdi [18], Allahverdi and Al-Anzi [19], Al-Anzi and Allahverdi [20], Allahverdi and Al-Anzi [21], Fattahi et al. [11], Allahverdi and Aydilek [16], and Jung et al. [15], among others.Several real-life examples or applications for two-stage and three-stage assembly problem can be found in Lee et al. [5], Potts et al. [6], Tozkapan et al. [22], Allahverdi and Al-Anzi [19], Al-Anzi and Allahverdi [20], Sung and Kim [23], Allahverdi and Al-Anzi [24], Cheng et al. [25], Fattahi et al. [11], Mozdgir et al. [26], Fattahi et al. [12], Hatami et al. [13], and Jung et al. [15], among others.On the other hand, the learning concept has been widely addressed in different branches of industry, for example, product development, job rotation, and job scheduling problem [27]. The first application in scheduling literature appeared in airplane’s manufacturing, where the assembly costs reduced as the times of repetitions increased [28]. Yelle [29] gave a comprehensive survey on learning curves applied in many industries including manufacturing sector. In addition to the excellent review on scheduling with learning effect by Biskup [30], Anzanello and Fogliatto [27] also gave a review on the wide applicability of learning curve models in production systems. The work of Azzouz et al. [31] is a more recent survey paper in the scheduling literature providing applications of learning effects.In scheduling techniques, Biskup [2] and Cheng and Wang [32] were some of the early researchers who proposed modeling a learning effect by a learning curve (function). Since then, many other learning curves (functions) in connection with a single machine, flow shop, or other scheduling problems, have been developed and modified.Kuo and Yang work [4], one of the extensively discussed studies on the scheduling research community, proposed the sum-of-processing-times-based learning model, in which the real processing time of a job is relevant to the sum of the previous work times. Actually, the sum-of-processing-times based learning model is relevant to a long-winded and uninterrupted production process in which initial steps are set up. In manufacturing steel plates or bars by a foundry, the products are required to be inspected for surface defects. A single inspector is regarded as a processor or a system to work on those steel bars (jobs). After the processor finishes some work units (jobs), he will spend less time on processing follow-up work units as his experiences grow. Thus, Dondeti and Mohanty [33] modeled the real processing time of a job as a function of the sum of the processing times of the already processed jobs.Further modifications of the sum-of-processing-times based learning effect in scheduling problems were proposed by Cheng et al. [34], Yin et al. [35], Rudek [36], Wu et al. [37], Lu et al. [38], Wu and Wang [39], and Pei et al. [40], among others. The readers may refer to Azzouz et al. [31] for other commonly discussed learning models: position-based learning, truncated learning, and exponential learning.


## 2. Notation Definition and Problem Formulation

At the outset, we define some notations and then describe the proposal problem.


### 2.1. Notations

n: total number of jobs m = 3: total number of machines J i: code for the ith job, i=1,2,…,n ω = { J 1 , J 2 , … , J n }: set of n jobs M l: machine code l, l=1,2,3 S andS∗: complete job schedules (sequences) S 1, S2, SA, and SU: partial job schedules (sequences) index[j]: the job scheduled in the jth position (in a job sequence) d: number of jobs removed from a sequence (S)


### 2.2. Input Parameters

p i, qi, ri: component processing times of job Ji on machines M1, M2, and M3, respectively, for i=1,2,…,n a: learning index and a<0 T 0: initial temperature T f: final temperature λ: annealing index


### 2.3. Decision Variables

T l k: starting time of the kth job (in S) on machine Ml, l=1,2,3 C l i S: completion time of job Ji on machine Ml, i=1,2,…,n;l=1,2,3 C l [ i ] S: completion time of the job in position i on machine Ml, l=1,2,3 C m a x ( S ): completion time for the last job in S or makespan or C3n(S)


### 2.4. Problem Formulation

We assume that a set ofn jobs, ω, are available at time zero and will be processed on fixed three machines, M1, M2, and M3. Each job Ji has three components to be processed on all three machines in three operations. Two components are first processed in parallel on machines M1 and M2 and then on machine M3 for the assembly operation. Machines M1 and M2 have no idle times at the first stage of operation. A job to be processed on machine M3 cannot start until it has been processed on machines M1 and M2. No machine can process more than one job at a time. Furthermore, preemption is not allowed; i.e., a job cannot be interrupted once it has begun processing. Sum of the component processing times on machines M1, M2, and M3 are pi1+∑j=1k-1pja, qi1+∑j=1k-1qja, and ri1+∑j=1k-1rja, respectively, where a is a learning index and a<0.For the convenience of reading, we further letPk=1+∑j=1k-1p[j], Qk=1+∑j=1k-1q[j], Rk=1+∑j=1k-1r[j], Pka=1+∑j=1k-1pja, Qka=1+∑j=1k-1qja, and Rka=1+∑j=1k-1rja.Now, for a scheduleS, the completion time C3[k]S of a job Ji to be scheduled on kth position on machine M3 in S is calculated as C3[k]S=max⁡{T1k+piPka,T2k+qiQka,T3k}+rjRka, where T1k, T2k, and T3k denote the starting times of a job (job Ji here) to be assigned to the kth position on machines M1, M2, and M3, respectively, in S. The objective is to find a scheduleS∗ that minimizes the makespan; i.e., CmaxS∗=minS⁡{C31S,C32S,…,C3nS}. For the Gantt chart of illustrating the considered two-stage three-machine environment, readers can refer to Lee et al. [5].


## 2.1. Notations

n: total number of jobs m = 3: total number of machines J i: code for the ith job, i=1,2,…,n ω = { J 1 , J 2 , … , J n }: set of n jobs M l: machine code l, l=1,2,3 S andS∗: complete job schedules (sequences) S 1, S2, SA, and SU: partial job schedules (sequences) index[j]: the job scheduled in the jth position (in a job sequence) d: number of jobs removed from a sequence (S)


## 2.2. Input Parameters

p i, qi, ri: component processing times of job Ji on machines M1, M2, and M3, respectively, for i=1,2,…,n a: learning index and a<0 T 0: initial temperature T f: final temperature λ: annealing index


## 2.3. Decision Variables

T l k: starting time of the kth job (in S) on machine Ml, l=1,2,3 C l i S: completion time of job Ji on machine Ml, i=1,2,…,n;l=1,2,3 C l [ i ] S: completion time of the job in position i on machine Ml, l=1,2,3 C m a x ( S ): completion time for the last job in S or makespan or C3n(S)


## 2.4. Problem Formulation

We assume that a set ofn jobs, ω, are available at time zero and will be processed on fixed three machines, M1, M2, and M3. Each job Ji has three components to be processed on all three machines in three operations. Two components are first processed in parallel on machines M1 and M2 and then on machine M3 for the assembly operation. Machines M1 and M2 have no idle times at the first stage of operation. A job to be processed on machine M3 cannot start until it has been processed on machines M1 and M2. No machine can process more than one job at a time. Furthermore, preemption is not allowed; i.e., a job cannot be interrupted once it has begun processing. Sum of the component processing times on machines M1, M2, and M3 are pi1+∑j=1k-1pja, qi1+∑j=1k-1qja, and ri1+∑j=1k-1rja, respectively, where a is a learning index and a<0.For the convenience of reading, we further letPk=1+∑j=1k-1p[j], Qk=1+∑j=1k-1q[j], Rk=1+∑j=1k-1r[j], Pka=1+∑j=1k-1pja, Qka=1+∑j=1k-1qja, and Rka=1+∑j=1k-1rja.Now, for a scheduleS, the completion time C3[k]S of a job Ji to be scheduled on kth position on machine M3 in S is calculated as C3[k]S=max⁡{T1k+piPka,T2k+qiQka,T3k}+rjRka, where T1k, T2k, and T3k denote the starting times of a job (job Ji here) to be assigned to the kth position on machines M1, M2, and M3, respectively, in S. The objective is to find a scheduleS∗ that minimizes the makespan; i.e., CmaxS∗=minS⁡{C31S,C32S,…,C3nS}. For the Gantt chart of illustrating the considered two-stage three-machine environment, readers can refer to Lee et al. [5].


## 3. Solution Approach

A branch-and-bound (B&B) method is used to solve the proposed problem for small number of jobs withn=8,9,10,11. Several dominance properties and a lower bound (LB) are developed and incorporated into the branch-and-bound method to increase the search efficiency. Since the proposed problem is NP-hard, to solve the problem for large number of jobs, we utilize a cloud theory-based simulated annealing (CSA) algorithm and an iterated greedy (IG) algorithm with four different local search methods. It has been shown [7, 22, 23, 41] that the permutation schedules, in which the jobs are processed in the same order in all machines, are dominant with respect to the makespan criterion. Consequently, we limit our research to permutation schedules for the proposed problem. Using the three-field classified system in scheduling literature (see [42]), the proposed problem can be represented as AF2(2,1)/prmu, LEt/Cmax.


### 3.1. Dominance Properties and a Lower Bound

Dominance rules are commonly used to improve search efficiency of heuristics in the scheduling research, for example, Lee et al. [5], Potts et al. [6], and Tozkapan et al. [22]. In this section, we will develop some dominance (elimination) properties and a LB embedded in a B&B method for finding optimal solutions. Let S=(S1,i,j,S2) and S′=(S1,j,i,S2) denote two sequences in which S1 and S2 are partial job sequences (or empty) and there are at most (k-2) scheduled jobs in S1, 1≤k≤n. To show S dominates S′, it suffices to show that C3jS<C3i(S′). In the following, we construct several dominance rules to assist in eliminating nodes in the B&B method. Two lemmas are provided to shorten the proof of the properties. The proofs of Lemma 1 and Properties 3 to 9 are given in the Appendix.Lemma 1.
If0<x≤y, 0<C, and a<0, then xC+ya≤yC+xa.Note that if0<x<y, 0<C, and a<0, then xC+ya<yC+xa.Lemma 2.
If1≤λ, 0≤t, and a<0, then 0≤λ1-1+ta-1-1+λta.Note that Lemma2 has already been proved by Kuo and Yang [4].Property 3.
Ifpi<pj, qi<qj, rj<ri, T3k> max{T1k+pjPka,T2k+qjQka}, T1k+piPka+pjPk+pia>max⁡{T2k+qiQka+qjQk+qia,T3k+riRka}, and T1k+pjPka+piPk+pja>max⁡{T2k+qjQka+qiQk+qja,T3k+rjRka}, then S dominates S′.Property 4.
Ifpi<pj, qi<qj, rj<ri, T3k>max{T1k+pjPka,T2k+qjQka}, T2k+qiQka+qjQk+qia>max⁡{T1k+piPka+pjPk+pia,T3k+riRka}, and T2k+qjQka+qiQk+qja>max⁡{T1k+pjPka+piPk+pja,T3k+rjRka}, then S dominates S′.Property 5.
Ifpi<pj, qi<qj, ri<rj, T3k>max⁡{T1k+pjPka,T2k+qjQka}, and riRka>max⁡{pjPk+pia,qjQk+qia}, then S dominates S′.Property 6.
Ifpi<pj, rj<ri, T1k+piPka>max⁡{T2k+qiQka,T2k+qjQka,T3k}, and pi(Pk+p)a>max⁡{qiQk+qja,qjQk+qia,riRka}, then S dominates S′.Property 7.
Ifqi<qj, rj<ri, T2k+qiQka>max⁡{T1k+piPka,T1k+pjPka,T3k}, and qi(Qk+qj)a>max⁡{pi(Pk+pj)a,pjPk+pia,riRka}, then S dominates S′.Property 8.
Ifpi<pj, qi<qj, ri<rj, T1k+piPka>max⁡{T2k+qjQka,T3k}, and riRka>max⁡{pjPk+pia,qjQk+qia}, then S dominates S′.Property 9.
Ifpi<pj, qi<qj, ri<rj, T2k+qiQka>max⁡{T1k+pjPka,T3k}, and riRka>max⁡{pjPk+pia,qjQk+qia}, then S dominates S′.The next property follows the same idea of Kuo and Yang [4], Theorem 1 thereof, but it is modified to accommodate the learning situation. Let S=(SA,SU), where SA has (k-1) jobs, 1≤k≤n, and SU has (n-k+1) jobs. Let r(k)≤rk+1≤⋯≤rn represent nondecreasing orders of processing time of jobs in SU for Machine 3.Property 10.
IfT3k≥max⁡T1k+∑i=knpi1+∑j=1i-1p[j]a,T2k+∑i=knqi1+∑j=1i-1q[j]a, then(SA,SM3) dominate (SA,SU), where SM3 is the partial schedule according to nondecreasing order of the processing times of SU in Machine 3. (Note that the complexity of Property 10 is O(nlog⁡(n))As a job being placed in a schedule on thekth position, 1≤k≤n, a LB, based on similar idea of Lee et al. [5], can be acquired as follows. (1)LBS=maxT3k+∑i=knri1+∑j=0i-1rja+mini∈SU⁡max⁡T3k,T1k+pi1+∑j=0k-1pja,T2k+qi1+∑j=0k-1qja-T3k,max⁡∑i=1npi1+∑j=0i-1pja,∑i=1nqi1+∑j=0i-1qja+mini∈SU⁡ri1+∑j=1nrj-ria.Note that T11=0, T21=0, T31=0, p(0)=0, q(0)=0, andr0=0.For the branch-and-bound (B&B) method in this study, we employ the depth-first search [43] in the branching procedure: a branch is selected and explored systematically until it is pruned out or its end node is reached. The B&B method allocates jobs starting from the first position (k=1) and in the forward to last position (k=n) allocation. To enhance the performance of the B&B method, the starting sequence (schedule) found by the algorithm IGLS3 (see more details in the next subsection) is considered as an incumbent sequence. Then, the depth-first search method is executed from the initial node and its descents from the tree, to renew the incumbent sequence. Apply Properties 3 to 9 to eliminate branches. If the LB of unsearched nodes is greater than or equal to the makespan of the incumbent sequence than eliminate the node and all nodes sprouting from it in the branch. For active nodes, Property 10 are applied to examine whether the order of unscheduled jobs can be allocated. Repeat the procedure until all nodes are explored.The above B&B method is also used to evaluate the effectiveness of the adopted algorithms, a cloud-based annealing algorithm, and an iterated greed algorithm for small number of jobs.For the study problem without learning consideration, AF2(2,1)//Cmax has been shown to be NP-hard (see [5]), so does AF2(2,1)/prmu,LEt/Cmax. In order to search for good quality solutions and shorten the computer CPU times, we utilize a metaheuristic cloud theory-based simulated annealing (CSA) algorithm, Li et al. [44] and Li and Du [45], and four versions of the iterated greedy (IG) algorithm, Ruiz and Stützle [46], for (near-) optimal solutions. The details are introduced in the following subsections.


### 3.2. A Cloud Theory-Based Simulated Annealing Algorithm

The simulated annealing algorithm (SA), a random optimization method, was first proposed by Kirkpatrick [47]. SA has been frequently and successfully adopted in combinatorial optimization problems because of its capability of escaping from local minimum in the searching process. SA imitates the process of the physical annealing to the solution of an optimization problem. It starts by constructing an initial solution, S0, from a high initial temperature, T0, and selects a solution S1 randomly in the neighborhood of S0. Whether S1 is accepted as an incumbent solution depends on the temperature and on Cmax(S0) and Cmax(S1), values of the objective function and the makespan. If Cmax(S1)≤Cmax(S0), then S1 is accepted and replaces S0; otherwise, S1 can also be accepted with a probability exp⁡[-(Cmax(S1)-Cmax(S0))/T]. As the temperature T decreases gradually, SA repeats the above process and converges to a global solution (in theory) or finds a local solution at the end the process. Allahverdi and Al-Anzi [21] successfully applied SA on an assembly flow shop problem. Although SA has been successfully applied to solve several optimization problems, it has also been found unable to solve some combinatorial optimization problems. Readers can refer to the reference listed in Boussaïd et al. [48].The basic concept of the cloud theory has been proposed by Li et al. [44] and Li and Du [45]. Torabzadeh and Zandieh [49] proposed a cloud theory-based simulated annealing (CSA) algorithm for the 2-stage m-machine assembly flow shop scheduling problem with a bicriteria objective function. They showed that their CSA performed better than the best existing SA [21]. Studying the same scheduling problem but with learning consideration and a different criterion, we then adapt the CSA for the problem. For more details about CSA, readers may refer to Li and Du [45] and Lv et al. [50].For the CSA to search better quality solutions, one local heuristic based on the idea of Johnson’s rule [51] was constructed. The resultant solution from the heuristic was then put in CSA as an initial solution. The Johnson-based local search heuristic, coded as J_mean, is as follows.TheJ_mean local search heuristic is shown as follows.(1)
For eachJi, i=1,2,…,n, let A1i=(pi+qi)/2 and B2i=ri be the processing times M1 and M2. N={J1,J2,…,Jn}.(2)
Lets=1, t=n.(3)
(i)
Ifmin⁡A11,A12,…,A1n,B21,B22,…,B2n=sayA1i, then assign Ji to the sth position and delete job Ji from N. Set s=s+1, and go to (4).(ii)
Ifmin⁡A11,A12,…,A1n,B21,B22,…,B2n=sayB2i, then assign Ji to the tth position and delete Ji from N. Set t=t-1, and go to (4).(4)
DeleteJi from N, if N is not empty, and then go to (3); otherwise, stop.Note that the total computational complexity ofJ_mean algorithm, which is the same as that of Johnson’s rule, is On2. The parameters aroused in CSA such as initial temperature T0, final temperature Tf, and annealing index λ need to be determined. We referred to the values of the corresponding parameters used in Allahverdi and Aydilek [16] and performed a pilot study similar to the study in Wu et al. (2017). Finally, we adopt the T0=0.1, Tf=10-5, and λ=0.98. The procedure of CSA is as in Algorithm 1.Algorithm 1:Procedure of the proposed CSA.
Input initial and final temperature, (T0,Tf), and annealing index λ. Randomly generate a solution, improved by (Johnson’s rule based)J_mean, then by a pairwise interchange, denote the solution S0, Calculate Cmax(S0). Do while T < T f Set Sout=S0, r=0, and T=T0. LetEn=T, He=T, andu0=1-T. LetEn∗=max⁡En+He-1/3⋅rand0,1,eps where eps<10-8. Let T∗=En∗⋅-2ln⁡u0. Set K=0. Do while K < N r (Nr, a predetermined number of iteration is set at 20) Choose i and j randomly with i,j∈1,2,…,nandi≠j, swap the ith job and jth job in S0 to obtain a new solution S1. Calculate the makespans Cmax(S0) and Cmax(S1). If Cmax(S1)<Cmax(S0), then replaceS0 byS1; else, replace S0by S1 when e x p ⁡ [ - ( C m a x S 1 - C m a x S 0 ) / ( C m a x ( S 0 ) ⋅ T ∗ ) ] < U, where U~rand(0, 1). LetK=K+1. End while Let r=r+1 and T=T0∗λr. End while Output a final solution Sout.In the CSA procedure (Algorithm1), En (the range of the cloud),He (the cloud drops’ dispersive degree), and a given certain value u0 are parameters from a normal distribution in the cloud theory-based simulated annealing algorithm [50]. In addition, the number of iterations Nr can be raised to enhance the searching capability of CSA [16].


### 3.3. Iterated Greedy Algorithm

The iterated greedy (IG) algorithm was proposed by Ruiz and Stützle [46]. The great advantages of this method are as follows: it is simple to implement and has been confirmed to yield high-quality solutions for flow shop problems [52]. The IG has been extensively employed for the last ten years in the scheduling research, especially in the (permutation or hybrid) flow shop problem, for example, Pan and Ruiz [53], Msakni et al. [54], Dubois-Lacoste et al. [55], and Pan et al. [56]. In this study, we propose an IG algorithm with four different local search methods, i.e., four versions of IG, coded as IGLS1, IGLS2, IGLS3, and IGLS4.When performing the IG, one randomly generates an initial solution and uses it repeatedly to execute destruction and construction cycles until a stopping criterion is reached [46]. In the destruction stage, d jobs are removed from the incumbent solution S to form a new partial sequence SD with n-d jobs. Let SR be the sequence with a size of d jobs created that contain the removed jobs according to the order of their appearances in S. In the construction stage, we choose the jobs of SR to be reinserted in the partial solution SD using the Nawaz-Enscore-Ham (NEH) mechanism [57]. Each job in SR has an assigned order, and the job with the first order is inserted in all possible positions of SD. The position with the best objective value is held. The same iteration is repeated for all remaining jobs in SR. Note that the complexity of NEH algorithm is O(n3m).Similar to Ruiz and Stützle [46], the IGLS algorithms utilize an acceptance criterion to determine whether a new solution should be kept or not. It adopts W=T·∑ipi+qi+ri/(100·n·m) as the temperature in the IG algorithm, where T is a controllable variable with 0<T<1. The procedure of IG algorithm is described as in Algorithm 2.Algorithm 2:An IG algorithm, IGLS3.
Initialization: Randomly generate an initial solution S. Improve S by a local search (e.g. LS3). The LS3 is as follows. ( 1 ) Randomly select one job among then jobs. ( 2 ) Insert the selected job to n possible positions, keep the best (the lowest C m a x) solution. ( 3 ) Repeat the steps until all njobs have been selected and inserted back; update the best solution if better solution is found. ( 4 ) Output the final solution, S0. Set S0 = S1 and Sbest=S1; Do while  iter < M m a x (a predetermined number of iterations Mmax is set equal to 30) Destruction stage. DivideS1 into SD and SR, where SD is a set of d removed jobs and SR a set of the remaining (n-d) jobs; Construction stage For the removed d jobs, execute the NEH mechanism to SR one after another until it yields the best sequence, coded as S2; Improve S2 by one of the four local search methods, LS1, LS2, LS3, LS4, coded as S3. (Acceptance criterion) If Cmax(S3)<Cmax(S1), then update S1 by S3; IfCmax(S3)<Cmax(Sbest), then Update Sbest by S3; Else if q≤exp(Cmax(S3)-Cmax(S1))/W) then Update S1 by S3; (Note that q ~ rand(0,1).) End while Output the final solution S bestWe used four different neighborhood structures as local search paths after the construction stage in the IG algorithm. The insertion neighborhood structure, LS3, is described in step(2) of the IG algorithm. The neighborhood structures for LS1, LS2, and LS4 are described as follows. Let S=J1,J2,…,Jn be a solution (i.e., a sequence of n jobs) and Cmax(S) be the objective value, i.e., the makespan, of the S.LS1: swap the structures of adjacent positions.(1)
Selectk1=1, k2=k1+1.(2)
Swap the job numbers between the positionsk1 and k2 in S,and let S0 denote the new solutions.(3)
IfCmax(S0) is less than CmaxS1 then update S by S0.(4)
Letk1=k1+1 and k2=k2+1. Repeat (2) and (3) until k1=n-1.(5)
Repeat steps(1) to (4) until CmaxS0 cannot be improved.(6)
Return the best found solution, denoted asS0.LS2: complete swap and best-first neighborhood structure.(1)
Swaps each pair of positions (jobs) inS.(2)
Calculate the resultantCmax.(3)
CompareCmax’s for all possible n(n+1)/2 pairs.(4)
Keep the best one, sayS0, with the lowest value of Cmax.(5)
IfCmaxS0<CmaxS1, then interchange the job numbers between the pair of positions for the best; i.e., updateS byS0.(6)
Repeat steps(1) to (5) until Cmax(S0) cannot be improved.(7)
Return the best found solution,S0.LS4: first-improvement swap neighborhood structure is as follows.(1)
Letk1=1, k2=k1+1.(2)
Swap the job numbers between the positionsk1 and k2 in S, and let S0 denote the new solutions.(3)
IfCmaxS0 is less than Cmax(S1) then update S by S0.(4)
Letk2=k2+1. Repeat (2) and (3) until k2=n.(5)
Letk1=k1+1. Repeat steps (2) to (4) until k1=n-1.(6)
Repeat steps(1) to (5) until CmaxS0 cannot be improved.(7)
Return the best found solution, denoted asS0.The ideas of the LS1, LS2, LS3, and LS4 are modified from three local searches proposed by Della Croce et al. [58]. The complexities of those three local searches are On2. The proposed LS1, LS2, LS3, and LS4 are very fast; even their complexities are not easily found. As for other neighborhood structures and local search methods, one can refer to Li et al. [59] and Wang et al. [60, 61], among others.


## 3.1. Dominance Properties and a Lower Bound

Dominance rules are commonly used to improve search efficiency of heuristics in the scheduling research, for example, Lee et al. [5], Potts et al. [6], and Tozkapan et al. [22]. In this section, we will develop some dominance (elimination) properties and a LB embedded in a B&B method for finding optimal solutions. Let S=(S1,i,j,S2) and S′=(S1,j,i,S2) denote two sequences in which S1 and S2 are partial job sequences (or empty) and there are at most (k-2) scheduled jobs in S1, 1≤k≤n. To show S dominates S′, it suffices to show that C3jS<C3i(S′). In the following, we construct several dominance rules to assist in eliminating nodes in the B&B method. Two lemmas are provided to shorten the proof of the properties. The proofs of Lemma 1 and Properties 3 to 9 are given in the Appendix.Lemma 1.
If0<x≤y, 0<C, and a<0, then xC+ya≤yC+xa.Note that if0<x<y, 0<C, and a<0, then xC+ya<yC+xa.Lemma 2.
If1≤λ, 0≤t, and a<0, then 0≤λ1-1+ta-1-1+λta.Note that Lemma2 has already been proved by Kuo and Yang [4].Property 3.
Ifpi<pj, qi<qj, rj<ri, T3k> max{T1k+pjPka,T2k+qjQka}, T1k+piPka+pjPk+pia>max⁡{T2k+qiQka+qjQk+qia,T3k+riRka}, and T1k+pjPka+piPk+pja>max⁡{T2k+qjQka+qiQk+qja,T3k+rjRka}, then S dominates S′.Property 4.
Ifpi<pj, qi<qj, rj<ri, T3k>max{T1k+pjPka,T2k+qjQka}, T2k+qiQka+qjQk+qia>max⁡{T1k+piPka+pjPk+pia,T3k+riRka}, and T2k+qjQka+qiQk+qja>max⁡{T1k+pjPka+piPk+pja,T3k+rjRka}, then S dominates S′.Property 5.
Ifpi<pj, qi<qj, ri<rj, T3k>max⁡{T1k+pjPka,T2k+qjQka}, and riRka>max⁡{pjPk+pia,qjQk+qia}, then S dominates S′.Property 6.
Ifpi<pj, rj<ri, T1k+piPka>max⁡{T2k+qiQka,T2k+qjQka,T3k}, and pi(Pk+p)a>max⁡{qiQk+qja,qjQk+qia,riRka}, then S dominates S′.Property 7.
Ifqi<qj, rj<ri, T2k+qiQka>max⁡{T1k+piPka,T1k+pjPka,T3k}, and qi(Qk+qj)a>max⁡{pi(Pk+pj)a,pjPk+pia,riRka}, then S dominates S′.Property 8.
Ifpi<pj, qi<qj, ri<rj, T1k+piPka>max⁡{T2k+qjQka,T3k}, and riRka>max⁡{pjPk+pia,qjQk+qia}, then S dominates S′.Property 9.
Ifpi<pj, qi<qj, ri<rj, T2k+qiQka>max⁡{T1k+pjPka,T3k}, and riRka>max⁡{pjPk+pia,qjQk+qia}, then S dominates S′.The next property follows the same idea of Kuo and Yang [4], Theorem 1 thereof, but it is modified to accommodate the learning situation. Let S=(SA,SU), where SA has (k-1) jobs, 1≤k≤n, and SU has (n-k+1) jobs. Let r(k)≤rk+1≤⋯≤rn represent nondecreasing orders of processing time of jobs in SU for Machine 3.Property 10.
IfT3k≥max⁡T1k+∑i=knpi1+∑j=1i-1p[j]a,T2k+∑i=knqi1+∑j=1i-1q[j]a, then(SA,SM3) dominate (SA,SU), where SM3 is the partial schedule according to nondecreasing order of the processing times of SU in Machine 3. (Note that the complexity of Property 10 is O(nlog⁡(n))As a job being placed in a schedule on thekth position, 1≤k≤n, a LB, based on similar idea of Lee et al. [5], can be acquired as follows. (1)LBS=maxT3k+∑i=knri1+∑j=0i-1rja+mini∈SU⁡max⁡T3k,T1k+pi1+∑j=0k-1pja,T2k+qi1+∑j=0k-1qja-T3k,max⁡∑i=1npi1+∑j=0i-1pja,∑i=1nqi1+∑j=0i-1qja+mini∈SU⁡ri1+∑j=1nrj-ria.Note that T11=0, T21=0, T31=0, p(0)=0, q(0)=0, andr0=0.For the branch-and-bound (B&B) method in this study, we employ the depth-first search [43] in the branching procedure: a branch is selected and explored systematically until it is pruned out or its end node is reached. The B&B method allocates jobs starting from the first position (k=1) and in the forward to last position (k=n) allocation. To enhance the performance of the B&B method, the starting sequence (schedule) found by the algorithm IGLS3 (see more details in the next subsection) is considered as an incumbent sequence. Then, the depth-first search method is executed from the initial node and its descents from the tree, to renew the incumbent sequence. Apply Properties 3 to 9 to eliminate branches. If the LB of unsearched nodes is greater than or equal to the makespan of the incumbent sequence than eliminate the node and all nodes sprouting from it in the branch. For active nodes, Property 10 are applied to examine whether the order of unscheduled jobs can be allocated. Repeat the procedure until all nodes are explored.The above B&B method is also used to evaluate the effectiveness of the adopted algorithms, a cloud-based annealing algorithm, and an iterated greed algorithm for small number of jobs.For the study problem without learning consideration, AF2(2,1)//Cmax has been shown to be NP-hard (see [5]), so does AF2(2,1)/prmu,LEt/Cmax. In order to search for good quality solutions and shorten the computer CPU times, we utilize a metaheuristic cloud theory-based simulated annealing (CSA) algorithm, Li et al. [44] and Li and Du [45], and four versions of the iterated greedy (IG) algorithm, Ruiz and Stützle [46], for (near-) optimal solutions. The details are introduced in the following subsections.


## 3.2. A Cloud Theory-Based Simulated Annealing Algorithm

The simulated annealing algorithm (SA), a random optimization method, was first proposed by Kirkpatrick [47]. SA has been frequently and successfully adopted in combinatorial optimization problems because of its capability of escaping from local minimum in the searching process. SA imitates the process of the physical annealing to the solution of an optimization problem. It starts by constructing an initial solution, S0, from a high initial temperature, T0, and selects a solution S1 randomly in the neighborhood of S0. Whether S1 is accepted as an incumbent solution depends on the temperature and on Cmax(S0) and Cmax(S1), values of the objective function and the makespan. If Cmax(S1)≤Cmax(S0), then S1 is accepted and replaces S0; otherwise, S1 can also be accepted with a probability exp⁡[-(Cmax(S1)-Cmax(S0))/T]. As the temperature T decreases gradually, SA repeats the above process and converges to a global solution (in theory) or finds a local solution at the end the process. Allahverdi and Al-Anzi [21] successfully applied SA on an assembly flow shop problem. Although SA has been successfully applied to solve several optimization problems, it has also been found unable to solve some combinatorial optimization problems. Readers can refer to the reference listed in Boussaïd et al. [48].The basic concept of the cloud theory has been proposed by Li et al. [44] and Li and Du [45]. Torabzadeh and Zandieh [49] proposed a cloud theory-based simulated annealing (CSA) algorithm for the 2-stage m-machine assembly flow shop scheduling problem with a bicriteria objective function. They showed that their CSA performed better than the best existing SA [21]. Studying the same scheduling problem but with learning consideration and a different criterion, we then adapt the CSA for the problem. For more details about CSA, readers may refer to Li and Du [45] and Lv et al. [50].For the CSA to search better quality solutions, one local heuristic based on the idea of Johnson’s rule [51] was constructed. The resultant solution from the heuristic was then put in CSA as an initial solution. The Johnson-based local search heuristic, coded as J_mean, is as follows.TheJ_mean local search heuristic is shown as follows.(1)
For eachJi, i=1,2,…,n, let A1i=(pi+qi)/2 and B2i=ri be the processing times M1 and M2. N={J1,J2,…,Jn}.(2)
Lets=1, t=n.(3)
(i)
Ifmin⁡A11,A12,…,A1n,B21,B22,…,B2n=sayA1i, then assign Ji to the sth position and delete job Ji from N. Set s=s+1, and go to (4).(ii)
Ifmin⁡A11,A12,…,A1n,B21,B22,…,B2n=sayB2i, then assign Ji to the tth position and delete Ji from N. Set t=t-1, and go to (4).(4)
DeleteJi from N, if N is not empty, and then go to (3); otherwise, stop.Note that the total computational complexity ofJ_mean algorithm, which is the same as that of Johnson’s rule, is On2. The parameters aroused in CSA such as initial temperature T0, final temperature Tf, and annealing index λ need to be determined. We referred to the values of the corresponding parameters used in Allahverdi and Aydilek [16] and performed a pilot study similar to the study in Wu et al. (2017). Finally, we adopt the T0=0.1, Tf=10-5, and λ=0.98. The procedure of CSA is as in Algorithm 1.Algorithm 1:Procedure of the proposed CSA.
Input initial and final temperature, (T0,Tf), and annealing index λ. Randomly generate a solution, improved by (Johnson’s rule based)J_mean, then by a pairwise interchange, denote the solution S0, Calculate Cmax(S0). Do while T < T f Set Sout=S0, r=0, and T=T0. LetEn=T, He=T, andu0=1-T. LetEn∗=max⁡En+He-1/3⋅rand0,1,eps where eps<10-8. Let T∗=En∗⋅-2ln⁡u0. Set K=0. Do while K < N r (Nr, a predetermined number of iteration is set at 20) Choose i and j randomly with i,j∈1,2,…,nandi≠j, swap the ith job and jth job in S0 to obtain a new solution S1. Calculate the makespans Cmax(S0) and Cmax(S1). If Cmax(S1)<Cmax(S0), then replaceS0 byS1; else, replace S0by S1 when e x p ⁡ [ - ( C m a x S 1 - C m a x S 0 ) / ( C m a x ( S 0 ) ⋅ T ∗ ) ] < U, where U~rand(0, 1). LetK=K+1. End while Let r=r+1 and T=T0∗λr. End while Output a final solution Sout.In the CSA procedure (Algorithm1), En (the range of the cloud),He (the cloud drops’ dispersive degree), and a given certain value u0 are parameters from a normal distribution in the cloud theory-based simulated annealing algorithm [50]. In addition, the number of iterations Nr can be raised to enhance the searching capability of CSA [16].


## 3.3. Iterated Greedy Algorithm

The iterated greedy (IG) algorithm was proposed by Ruiz and Stützle [46]. The great advantages of this method are as follows: it is simple to implement and has been confirmed to yield high-quality solutions for flow shop problems [52]. The IG has been extensively employed for the last ten years in the scheduling research, especially in the (permutation or hybrid) flow shop problem, for example, Pan and Ruiz [53], Msakni et al. [54], Dubois-Lacoste et al. [55], and Pan et al. [56]. In this study, we propose an IG algorithm with four different local search methods, i.e., four versions of IG, coded as IGLS1, IGLS2, IGLS3, and IGLS4.When performing the IG, one randomly generates an initial solution and uses it repeatedly to execute destruction and construction cycles until a stopping criterion is reached [46]. In the destruction stage, d jobs are removed from the incumbent solution S to form a new partial sequence SD with n-d jobs. Let SR be the sequence with a size of d jobs created that contain the removed jobs according to the order of their appearances in S. In the construction stage, we choose the jobs of SR to be reinserted in the partial solution SD using the Nawaz-Enscore-Ham (NEH) mechanism [57]. Each job in SR has an assigned order, and the job with the first order is inserted in all possible positions of SD. The position with the best objective value is held. The same iteration is repeated for all remaining jobs in SR. Note that the complexity of NEH algorithm is O(n3m).Similar to Ruiz and Stützle [46], the IGLS algorithms utilize an acceptance criterion to determine whether a new solution should be kept or not. It adopts W=T·∑ipi+qi+ri/(100·n·m) as the temperature in the IG algorithm, where T is a controllable variable with 0<T<1. The procedure of IG algorithm is described as in Algorithm 2.Algorithm 2:An IG algorithm, IGLS3.
Initialization: Randomly generate an initial solution S. Improve S by a local search (e.g. LS3). The LS3 is as follows. ( 1 ) Randomly select one job among then jobs. ( 2 ) Insert the selected job to n possible positions, keep the best (the lowest C m a x) solution. ( 3 ) Repeat the steps until all njobs have been selected and inserted back; update the best solution if better solution is found. ( 4 ) Output the final solution, S0. Set S0 = S1 and Sbest=S1; Do while  iter < M m a x (a predetermined number of iterations Mmax is set equal to 30) Destruction stage. DivideS1 into SD and SR, where SD is a set of d removed jobs and SR a set of the remaining (n-d) jobs; Construction stage For the removed d jobs, execute the NEH mechanism to SR one after another until it yields the best sequence, coded as S2; Improve S2 by one of the four local search methods, LS1, LS2, LS3, LS4, coded as S3. (Acceptance criterion) If Cmax(S3)<Cmax(S1), then update S1 by S3; IfCmax(S3)<Cmax(Sbest), then Update Sbest by S3; Else if q≤exp(Cmax(S3)-Cmax(S1))/W) then Update S1 by S3; (Note that q ~ rand(0,1).) End while Output the final solution S bestWe used four different neighborhood structures as local search paths after the construction stage in the IG algorithm. The insertion neighborhood structure, LS3, is described in step(2) of the IG algorithm. The neighborhood structures for LS1, LS2, and LS4 are described as follows. Let S=J1,J2,…,Jn be a solution (i.e., a sequence of n jobs) and Cmax(S) be the objective value, i.e., the makespan, of the S.LS1: swap the structures of adjacent positions.(1)
Selectk1=1, k2=k1+1.(2)
Swap the job numbers between the positionsk1 and k2 in S,and let S0 denote the new solutions.(3)
IfCmax(S0) is less than CmaxS1 then update S by S0.(4)
Letk1=k1+1 and k2=k2+1. Repeat (2) and (3) until k1=n-1.(5)
Repeat steps(1) to (4) until CmaxS0 cannot be improved.(6)
Return the best found solution, denoted asS0.LS2: complete swap and best-first neighborhood structure.(1)
Swaps each pair of positions (jobs) inS.(2)
Calculate the resultantCmax.(3)
CompareCmax’s for all possible n(n+1)/2 pairs.(4)
Keep the best one, sayS0, with the lowest value of Cmax.(5)
IfCmaxS0<CmaxS1, then interchange the job numbers between the pair of positions for the best; i.e., updateS byS0.(6)
Repeat steps(1) to (5) until Cmax(S0) cannot be improved.(7)
Return the best found solution,S0.LS4: first-improvement swap neighborhood structure is as follows.(1)
Letk1=1, k2=k1+1.(2)
Swap the job numbers between the positionsk1 and k2 in S, and let S0 denote the new solutions.(3)
IfCmaxS0 is less than Cmax(S1) then update S by S0.(4)
Letk2=k2+1. Repeat (2) and (3) until k2=n.(5)
Letk1=k1+1. Repeat steps (2) to (4) until k1=n-1.(6)
Repeat steps(1) to (5) until CmaxS0 cannot be improved.(7)
Return the best found solution, denoted asS0.The ideas of the LS1, LS2, LS3, and LS4 are modified from three local searches proposed by Della Croce et al. [58]. The complexities of those three local searches are On2. The proposed LS1, LS2, LS3, and LS4 are very fast; even their complexities are not easily found. As for other neighborhood structures and local search methods, one can refer to Li et al. [59] and Wang et al. [60, 61], among others.


## 4. Computational Experiments and Results

In this section, we present our experimental tests of examining the efficiency of all adopted algorithms. The branch-and-bound method was performed for small number of jobs; a CSA and an iterated greedy (IG) algorithm with 4 different local search methods (coded as IGLS1 IGLS2, IGLS3, and IGLS4) were performed for both small and large numbers of jobs. These algorithms were performed in Fortran (version 6.6, Compaq Visual Fortran) on a PC (Windows XP) with Intel(R) Core(TM) i7 Duo CPU 2.66-GHz and RAM size of 1.99 GB. The normal job processing times on machinesM1, M2, and M3, in line with the scheme of Lee et al. [5], were generated at random from a discrete uniform distribution U(1,100), respectively. All the parameters used in CSA adopted the settings of Wu et al. [1] while all the parameters in IG used the results of previous tests.In the computational experiments for small number of jobs,n was set at 8, 9, 10, and 11. Following the suggestion by Liu et al. [62], we set the learning index (a) at a=-0.1, -0.01, and -0.001. The number of jobs removed from a sequence was set at d=2, 3, and 4; no more than half of a number of jobs were removed. One hundred instances were tested for each combination of n, a, and d. A total of 3600 instances were examined. Tables 1, 2, and 3 summarized the computational results. The optimal solutions were acquired by running the B&B method for the chosen small number of jobs. We report the average error percentage (AEP) here, where AEP=100(Ai-Oi∗)%, and Ai was obtained by each metaheuristic and Oi∗ by the B&B method. Figure 1 shows the performance results of CSA and IGLS algorithms.Table 1
Computational results of the branch-and-bound method.
n a Branch and Bound method Number of nodes CPU time (sec.) Number of Feasible Solutions mean max mean max 8 - . 100 28960.00 28960 0.35 0.41 100 - . 010 28960.67 28964 0.35 0.39 100 - . 001 28960.69 28966 0.35 0.41 100  9 - . 100 260649.00 260649 3.63 3.76 100 - . 010 260650.20 260661 3.64 3.78 100 - . 001 260650.01 260654 3.62 3.73 100  10 - . 100 2606502.00 2606523 47.08 48.92 100 - . 010 2606502.00 2606518 46.93 48.69 100 - . 001 2606503.00 2606561 30.56 33.18 100  11 - . 100 28671517.06 28671719 422.13 485.43 100 - . 010 28671513.38 28671543 529.33 593.48 100 - . 001 28671513.06 28671530 529.24 593.19 100Table 2
The AEP of algorithms for small number of jobs.
n a d Algorithm IGLS1 IGLS2 IGLS3 IGLS4 CSA mean max mean max mean max mean max mean max 8 - 0.001 2 0.000 0.013 0.008 0.812 0.000 0.013 0.007 0.630 0.000 0.000 3 0.000 0.010 0.000 0.000 0.000 0.000 0.000 0.002 0.000 0.000 4 0.000 0.000 0.000 0.000 0.000 0.002 0.000 0.001 0.000 0.000 - 0.01 2 0.007 0.455 0.001 0.047 0.006 0.455 0.014 0.748 0.000 0.003 3 0.002 0.105 0.000 0.002 0.000 0.002 0.001 0.047 0.000 0.003 4 0.001 0.047 0.000 0.002 0.000 0.018 0.001 0.047 0.000 0.003 - 0.1 2 0.043 2.277 0.001 0.028 0.004 0.175 0.031 0.634 0.001 0.037 3 0.011 0.308 0.003 0.308 0.006 0.403 0.010 0.308 0.001 0.037 4 0.011 0.403 0.003 0.308 0.004 0.403 0.009 0.308 0.001 0.037  9 - 0.001 2 0.008 0.806 0.000 0.004 0.005 0.233 0.005 0.233 0.000 0.004 3 0.000 0.008 0.000 0.000 0.008 0.812 0.008 0.806 0.000 0.004 4 0.002 0.215 0.000 0.001 0.000 0.000 0.000 0.002 0.000 0.004 - 0.01 2 0.009 0.815 0.020 1.932 0.004 0.342 0.010 0.877 0.001 0.038 3 0.001 0.079 0.000 0.006 0.009 0.877 0.009 0.815 0.001 0.038 4 0.001 0.007 0.000 0.038 0.000 0.013 0.001 0.013 0.001 0.038 - 0.1 2 0.014 0.421 0.007 0.517 0.007 0.421 0.020 0.504 0.006 0.382 3 0.011 0.421 0.001 0.049 0.002 0.139 0.010 0.421 0.006 0.382 4 0.009 0.421 0.006 0.406 0.000 0.009 0.006 0.131 0.006 0.382  10 - 0.001 2 0.016 1.544 0.016 1.544 0.016 1.544 0.002 0.216 0.000 0.001 3 0.017 1.544 0.016 1.544 0.000 0.000 0.028 2.757 0.000 0.001 4 0.000 0.001 0.000 0.000 0.000 0.000 0.000 0.001 0.000 0.001 - 0.01 2 0.017 1.551 0.000 0.007 0.000 0.014 0.029 2.851 0.000 0.005 3 0.001 0.009 0.000 0.001 0.000 0.007 0.001 0.009 0.000 0.005 4 0.001 0.091 0.000 0.004 0.000 0.001 0.001 0.006 0.000 0.005 - 0.1 2 0.143 5.765 0.029 1.571 0.019 1.615 0.076 3.603 0.003 0.049 3 0.063 3.603 0.011 0.879 0.012 0.878 0.052 3.603 0.003 0.049 4 0.005 0.075 0.011 0.873 0.012 0.873 0.006 0.130 0.003 0.049  11 - 0.001 2 0.030 1.609 0.000 0.016 0.021 2.056 0.016 1.580 0.000 0.000 3 0.000 0.004 0.000 0.016 0.000 0.000 0.000 0.016 0.000 0.000 4 0.000 0.016 0.000 0.016 0.000 0.000 0.000 0.016 0.000 0.000 - 0.01 2 0.011 0.462 0.001 0.098 0.001 0.036 0.024 2.229 0.000 0.004 3 0.002 0.053 0.001 0.098 0.000 0.003 0.001 0.016 0.000 0.004 4 0.002 0.098 0.001 0.098 0.000 0.002 0.002 0.098 0.000 0.004 - 0.1 2 0.070 1.548 0.004 0.113 0.012 0.276 0.042 1.273 0.008 0.257 3 0.016 0.351 0.015 1.266 0.005 0.113 0.024 1.266 0.008 0.257 4 0.028 1.266 0.014 1.243 0.004 0.100 0.023 1.266 0.008 0.257  mean  0.015 0.733 0.005 0.385 0.004 0.329 0.013 0.763 0.002 0.065Table 3
The mean ranks of algorithms in Kruskal–Wallis test for small and large number of jobs.
Algorithm Smalln Bign Number of obs. Mean Rank Number of obs. Mean Rank IGLS1 36 115.14 36 82.38 IGLS2 36 80.96 36 70.67 IGLS3 36 80.39 36 65.50 IGLS4 36 115.64 36 79.83 CSA 36 60.38 36 154.13  Total 180 90.50 180 90.50 ∗Note that average scores were used for ties.Figure 1
Boxplots of AEP for algorithms.As for the capability of the B&B method, we report the maximum and average number of nodes and the maximum and average execution times (in seconds) in Table1. As the numbers of job size (n) increased, the (mean and maximum) nodes increased; the CPU times increased dramatically as the n increased (Table 1, columns 4 and 5). If the number of nodes goes beyond 108, the B&B method would skip to the next instance, and instances solved out with less than 108 nodes were recorded as feasible solution. The computational results are shown in the last column of Table 1. No matter what the number of jobs (n) or the learning index (a), all instances are solvable within 108 nodes. As for the impact of particular dominant properties on the efficiency of branch and bound (B&B), it can be easily done in the same way as that of Wu et al. [1].For the proposed algorithms, CSA and IGLS, the AEPs are presented in Table2. All AEPs of the CSA and IGLS algorithms increased slightly as the learning effect strengthened; i.e., the value of learning index (a) became larger, as shown in Table 2. As the amount of destruction (d) increased, the AEPs decreased as well; this is because the larger the value of d is, the wider the searching scope explores. Overall, the CSA (with mean AEP of 0.1%) performed the best; however, also note that the worst IGLS1 was with mean AEP of 1.5% (the last row of Table 2). The CPU times were all within 0.1 seconds; we thus omitted them here.To compare whether the differences in the solution quality of the CSA and IGLS algorithms were statistically significant, the parametric or nonparametric statistical tests have commonly been employed [63]. There are three assumptions of the parametric analysis of variance (ANOVA), i.e., normality, homoscedasticity, and independence of the residuals. We carried out an ANOVA on AEPs and examined the assumption of normality for the residuals (using SAS 9.4). The value of the Kolmogorov–Smirnov D statistic was 0.18, and the asymptotic two-sided p value was less than 0.01; the level of significance was in general set at 0.05. Since the normality assumption was violated for the samples of AEP, we then used the nonparametric Kruskal–Wallis test on ranks of AEPs to test whether the populations of AEPs were the same. Table 3 (column 3) showed the mean ranks of the CSA and IGs algorithms.In Table4 (column 2), with p value (Asymp. Sig) < 0.001, it is indicated that there were significantly statistical differences among the performances of the CSA and IGLS algorithms. Consequently, a multiple comparison method, which was based on pairwise two-sample rankings, was conducted to determine pairwise differences between algorithms. We employed the Dwass–Steel–Critchlow–Fligner (DSCF) procedure [64, 65]. As shown in Table 5, the mean ranks of AEPs could be separated significantly into two groups, at 0.05 level of significance. As illustrated in Table 5 (columns 2 and 3) of SDCF test, CSA (AEP = 0.001), IGLS2 (AEP = 0.004), and IGLS3 (AEP = 0.004) were in a better performance group and the IGLS1 (AEP = 0.015) and IGLS4 (AEP = 0.013) were in a worse performance group.Table 4
Kruskal–Wallis test statistics for both small and large number of jobs.
Kruskal-Wallis test Smalln Bign Chi-Square 31.2217 84.4702 DF 4 4 Asymp. Sig. <0.0001 <0.0001Table 5
Critchlow-Fligner procedure for differences among algorithms for small number of jobs.
Pairwise ComparisonBetween Algorithms Dwass-Steel-Critchlow-Fligner procedure Smalln Bign DSCF value Pr > DSCF DSCF value Pr > DSCF IGLS1 vs. IGLS2 3.8926 0.0467 1.3734 0.8682 IGLS1 vs. IGLS3 3.8944 0.0465 2.1489 0.5497 IGLS1 vs. IGLS4 0.0239 1.0000 0.4338 0.9981 IGLS1 vs. CSA 6.4046 <.0001 8.1987 <.0001 IGLS2 vs. IGLS3 0.0642 1.0000 1.0924 0.9386 IGLS2 vs. IGLS4 3.9490 0.0418 1.2615 0.9000 IGLS2 vs. CSA 2.3163 0.4730 10.3262 <.0001 IGLS3 vs. IGLS4 4.1744 0.0262 2.0630 0.5894 IGLS3 vs. CSA 2.3432 0.4609 10.4627 <.0001 IGLS4 vs. CSA 6.3081 <.0001 8.8412 <.0001In the computational experiments for the large number of jobs, following Liu et al. [62], we also set the learning index a=-0.1, -0.01, and -0.001; the number of jobs removed, d, was set at 10, 15, and 20; the numbers of jobs was set at n=40, 50, 60, and 70. One hundred instances were tested for each combination of n, d, and a; a total of 3600 instances were examined. We calculated the relative percent deviation (RPD), RPD=100Ai-A∗/A∗%, where Ai was obtained from each algorithm and A∗ was the minimum value among the CSA and four IGLS algorithms.As shown in Table6, the mean RPDs of CSA and IGLS algorithms increased as the learning index increased from -0.001 to -0.1 regardless of the number of jobs. As for the impact of the number of removed jobs (d) on RPDs, the average RPDs were 0.0118, 0.0113, and 0.0113, for d=10, 15, and 20, respectively. Figure 2 provided the boxplots of RPDs for each number of d with these five algorithms.Table 6
The RPD of five algorithms for large number of jobs.
n a d Algorithm IGLS1 IGLS2 IGLS3 IGLS4 CSA mean max mean max mean max mean max mean max 40 - 0.001 10 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.02 1.55 15 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.02 1.55 20 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.02 1.55 - 0.01 10 0.00 0.02 0.00 0.01 0.00 0.01 0.00 0.02 0.02 0.97 15 0.00 0.01 0.00 0.01 0.00 0 0.00 0.01 0.02 0.97 20 0.00 0.01 0.00 0.00 0.00 0.01 0.00 0.01 0.02 0.97 - 0.1 10 0.02 0.12 0.01 0.04 0.00 0.06 0.02 0.09 0.04 1.51 15 0.02 0.09 0.01 0.12 0.01 0.04 0.02 0.10 0.04 1.51 20 0.02 0.17 0.01 0.08 0.01 0.04 0.02 0.17 0.04 1.51  50 - 0.001 10 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.02 0.31 15 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.02 0.31 20 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.02 0.31 - 0.01 10 0.00 0.32 0.00 0.01 0.00 0.01 0.00 0.02 0.01 0.30 15 0.00 0.01 0.00 0.01 0.00 0.00 0.00 0.01 0.01 0.30 20 0.00 0.01 0.00 0.01 0.00 0.01 0.00 0.01 0.01 0.30 - 0.1 10 0.03 0.28 0.01 0.06 0.01 0.10 0.02 0.23 0.08 1.09 15 0.02 0.09 0.01 0.18 0.00 0.04 0.02 0.07 0.08 1.08 20 0.02 0.14 0.01 0.28 0.01 0.07 0.01 0.12 0.08 1.08  60 - 0.001 10 0.00 0.32 0.00 0.00 0.00 0.00 0.00 0.00 0.02 0.38 15 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.02 0.38 20 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.02 0.38 - 0.01 10 0.00 0.01 0.00 0.00 0.00 0.00 0.00 0.01 0.02 0.47 15 0.00 0.02 0.00 0.00 0.00 0.00 0.00 0.01 0.02 0.47 20 0.00 0.01 0.00 0.01 0.00 0.00 0.00 0.01 0.02 0.47 - 0.1 10 0.03 0.18 0.01 0.04 0.01 0.09 0.02 0.08 0.08 1.24 15 0.02 0.14 0.01 0.05 0.01 0.05 0.02 0.18 0.08 1.24 20 0.02 0.11 0.01 0.07 0.01 0.06 0.02 0.11 0.08 1.24  70 - 0.001 10 0.00 0.03 0.00 0.00 0.00 0.00 0.00 0.00 0.03 0.35 15 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.03 0.35 20 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.03 0.35 - 0.01 10 0.00 0.06 0.00 0.00 0.00 0.00 0.00 0.00 0.05 0.6 15 0.00 0.02 0.00 0.00 0.00 0.00 0.00 0.01 0.05 0.6 20 0.00 0.01 0.00 0.00 0.00 0.00 0.00 0.01 0.05 0.6 - 0.1 10 0.03 0.17 0.01 0.08 0.00 0.11 0.02 0.17 0.07 0.74 15 0.02 0.14 0.01 0.07 0.01 0.11 0.02 0.11 0.06 0.74 20 0.02 0.11 0.01 0.05 0.01 0.10 0.02 0.10 0.06 0.74  mean 0.01 0.07 0.00 0.03 0.00 0.03 0.01 0.05 0.04 0.79Figure 2
Boxplots of RPD for algorithms.The boxplots of the RPDs displayed the performances of the CSA and IG algorithms for large numbers of jobs. The CSA algorithm performed slightly worse than those of the four IGLS types. We carried out another ANOVA on RPDs and examined the normality assumption for the residuals; thep value was less than 0.01 from the Kolmogorov–Smirnov normality test. Therefore, the normality assumption was invalid for the RPD samples. A Kruskal–Wallis test on ranks of RPDs was subsequently used to check whether the RPD samples were from the same distribution. Table 3 (column 5) shows the mean ranks of the CSA and four IGLS algorithms for the large numbers of jobs. In Table 4 (column 3), the asymptotic p value is less than 0.0001. Consequently, the DSCF procedure was used to find pairwise differences between pairs of the CSA and IGLS algorithms. As displayed in Table 5 (columns 4 and 5), the IGLS algorithms were in one better performance group, whereas the CSA algorithm was the worst in large number of jobs case. Moreover, the boxplots of the RPDs (Figure 2) of the IGLS3 and IGLS2 showed less dispersion than the others. In other words, the IGLS2 and IGLS3 were both accurate and stable for solving the problem of the large numbers of jobs.


## 5. Conclusions and Future Studies

A makespan minimization problem for a two-stage three-machine assembly flow shop scheduling with sum-of-processed-times based processing times has been addressed. A branch-and-bound method embedded with a LB and several dominance properties was proposed for the small number of jobs(n=8,9,10,11). Since the problem is NP-hard, two algorithms, a cloud theory-based simulated annealing (CSA) algorithm and an iterated greedy (IG) algorithm with four local search methods, have been adopted to solve the problem for the large number of jobs (n=40,50,60,70). These algorithms seemed to perform well for both small number of jobs (n=8,9,10,11) and large number of jobs (n=40,50,60,70). The computational results validate the effectiveness, as claimed by researchers in the scheduling research community, of the proposed IG algorithm with four different local search methods. However, the CSA was still a competitive metaheuristic algorithm, especially for small-number-of-jobs problems in this study.The occurrences of the study problem in many plant manufacturing environments have been exemplified by outstanding researchers such as these referred to in the introduction. Some potential research topics worthy of investigation are different learning curves including the position-based learning, an exponential learning, truncated learning, or general learning functions, especially different learning functions for different stages, i.e., at component manufacturing stage and at the assembly stage. This study considers two stages; however, there are several published papers that investigated three-stage flow shop assembly problem but all without learning effect. Therefore, extending to multistage assembly problem with learning consideration in some of these stages can be another future topic to pursue. One may generalize the properties for general nonincreasing learning curves,pik=pif(∑j=1k-1p[j]), where f is a nonincreasing function describing the learning effect (similarly for qi and ri) or job based nonincreasing learning curve, pijk=pijf(k) or pijk=pij-bijmin⁡k-1,gij. Readers may refer to Rudek [66–68] and Wang et al. [60, 61] for further details.



---

*Source: 8170294-2018-05-23.xml*