# A Genetic Algorithm for a Two-Machine Flowshop with a Limited Waiting Time Constraint and Sequence-Dependent Setup Times

Authors: Ju-Yong Lee
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

This study considers a two-machine flowshop with a limited waiting time constraint between the two machines and sequence-dependent setup times on the second machine. These characteristics are motivated from semiconductor manufacturing systems. The objective of this scheduling problem is to minimize the total tardiness. In this study, a mixed-integer linear programming formulation was provided to define the problem mathematically and used to find optimal solutions using a mathematical programming solver, CPLEX. As CPLEX required a significantly long computation time because this problem is known to be NP-complete, a genetic algorithm was proposed to solve the problem within a short computation time. Computational experiments were performed to evaluate the performance of the proposed algorithm and the suggested GA outperformed the other heuristics considered in the study.


---

## Body

## 1. Introduction

The two-machine flowshop scheduling problem with a limited waiting time constraint and sequence-dependent setup times investigated in this study is motivated by semiconductor manufacturing systems. In a two-machine flowshop, all jobs are processed in the same order of machine 1 and then machine 2, which is called permutation schedule. Owing to the limited waiting time constraint, jobs must be started on the second machine within a limited waiting time after the completion of those jobs on the first machine. Additionally, sequence-dependent setup times are incurred between two consecutive jobs on the second machine. The objective function of this scheduling problem is a minimization of the total tardiness. Thus, this problem can be defined byF2|max−wait and sij|∑iTi in the three-field notation suggested by [1], where max-wait and sij refer to a limited waiting time constraint and sequence-dependent setup times, respectively. Ti is the tardiness of job i defined as Ti=maxCi−di,0, where Ci and di are the completion time and due date of job i, respectively. This scheduling problem is NP-complete because the typical two-machine flowshop tardiness problem is NP-complete [2].The considered limited waiting time constraint is common in semiconductor wafer fabrication, in which there are many chemical processing processes. One example is a flowshop consisting of cleaning and diffusion processes [3]. Wafers that have completed the cleaning process may have problems that increase the likelihood of contamination and decrease quality if the surface is exposed to air for a long time before the next process (the diffusion process). To prevent this problem, the limited waiting time constraint is set between cleaning and diffusion processes. Additionally, if the chemical treatment effect is valid only when the treated wafer is processed on the next machine within a certain time after the treatment, the waiting time would be limited. If a wafer violates this time limit, the first operation must be reworked or discarded in case of high contamination. Failure to comply with the time constraints usually occurs when production volume is high, reducing productivity and causing management losses.Setup time refers to the time required for preparation before processing jobs. If the setup time for a succeeding job varies depending on the preceding job, it is called the sequence-dependent setup time. In other words, the setup time depends on the sequence of the jobs. In semiconductor manufacturing systems, wafers for different types of products may require different chemicals or operating temperatures even though they are processed in the same machine. Therefore, job scheduling is important to schedule jobs to minimize the setup times when the sequence-dependent setup times are considered.A two-machine flowshop scheduling problem with sequence-dependent setup times (SDSTs) to minimize the makespan is very similar to the typical travel salesman problem (TSP) [4], and dynamic programming methods [5, 6] and branch and bound algorithms [7, 8] have been proposed to obtain optimal solutions for the problem. However, since finding optimal solutions of the flowshop problem with SDST requires considerably long computation times, recent studies have focused on development of metaheuristic algorithms: genetic algorithms [9–11], variable neighborhood search algorithm [12], migrating bird optimization algorithm [13], discrete artificial bee colony optimization [14], iterated greedy algorithm [15–17], and local search based heuristic algorithm [18].A two-machine flowshop scheduling problem with a limited waiting time (LWT) constraint to minimize the makespan has been proven to be NP-hard [19]. For this problem, [19, 20] suggest branch and bound algorithms to find optimal solutions, and [21] proposes several dominance properties for optimal solutions. The study in [22] considers a situation where some jobs skip the first machine in a two-machine flowshop and suggests an approximation algorithm to minimize the waiting time variation of jobs. The study in [23] considers a three-machine flowshop with overlapping waiting time constraints and proposes a branch and bound algorithm to minimize makespan. The study in [24, 25] consider flowshop problems with time lag constraints and develop a simulated annealing algorithm and a constructive heuristic algorithm with and insertion mechanism, respectively. On the other hand, for a flowshop problem with LWT for the objective of minimizing total tardiness, a heuristic algorithm and a Lagrangian relaxation-based lower bound strategy [26] have been developed.Only a few studies have considered SDSTs and LWT together, although both are common and important in semiconductor manufacturing systems. The study in [3] suggests a branch and bound algorithm for the objective of minimizing makespan. On the other hand, no-wait flowshop problems with SDSTs have been studied recently. The study in [27] proposes a branch and bound algorithm for no-wait flowshop, and [28] proposes a pairwise iterated greedy algorithm, while [29] suggests an insertion neighborhood search algorithm to minimize total flowtime. Note that this study is the first attempt to consider the two-machine flowshop with SDST and LWT for the objective of minimizing total tardiness.In this study, a mixed-integer programming formulation for the considered scheduling problem is provided to describe the problem clearly and to obtain optimal schedule by CPLEX. Additionally, heuristic algorithms are developed to obtain good (or near-optimal) schedules in a short computation time rather than an optimal schedule because the problem is NP-complete. Three types of heuristics are proposed: list scheduling methods, a constructive heuristic, and a genetic algorithm. To demonstrate the performance of the proposed heuristic algorithms, computational experiments were performed on randomly generated instances.In the remainder of this paper,Section 2 describes the problem considered in this study in more detail including several assumptions and presents a mixed-integer linear programming formulation. Section 3 proposes heuristic algorithms. Section 4 describes the computational experiments and shows the results. Finally, Section 5 concludes the paper with a short summary.


## 2. Problem Description

In this section, the considered scheduling problem is described in more detail, and a mixed-integer linear programming formulation is presented. There aren jobs to be processed in the two-machine flowshop with a limited waiting time constraint and sequence-dependent setup times on the second machine. Here, only permutation schedules are considered; that is, job sequences on the two machines are the same. Although permutation schedules are not dominant in the problem, permutation schedules are common in real situations because of the simplicity of work management, flexibility in material handling, and limitation in buffer space. Note that permutation schedules are dominant in a typical two-machine flowshop with regular measures, including total tardiness. Other assumptions include the following:(i)
All jobs are ready to start at time zero(ii)
Information on the jobs to be scheduled is given; that is, processing time, due date, limited waiting time, and sequence-dependent setup time are given in advance(iii)
Preemption is not allowed(iv)
Each machine can process only one job at a time, and a job can be processed on only one machine at a timeIn this paper, symbols in Table1 are used to describe the mathematical formulation and proposed algorithms.Table 1
Notations for the description of the proposed algorithms.
SymbolDefinitionJSet of jobs,J=1,…,ni,jJob indiceskMachine indexk=1,2pikProcessing time of jobi on machine kdiDue date of jobiwiLimited waiting time of jobisijSequence-dependent setup time between jobsi and jrIndex of the job at therth position in a schedulexir1 if jobi is assigned to the rth position in a schedule and 0 otherwiseyijr1 if jobsi and j are assigned consecutively to positions r and r + 1 and 0 otherwisebrkStart time of therth job on machine kcrkCompletion time of therth job on machine kTrTardiness of therth jobΣPartial scheduleσiPartial schedule obtained withσ followed by job iUSet of unscheduled jobsCkσCompletion time of partial scheduleσ on machine kCompletion times and tardiness of the jobs in a given sequence are computed as follows:(1)c11=p11,(2)c12=p11+p12,(3)cr1=maxcr−11+pr1,cr−12+sr−1r−wr,forr≥2,(4)cr2=maxcr1,cr−12+sr−1r+pr2,forr≥2,(5)Tr=max0,cr2−dr,for alli.The mixed-integer linear programming (MILP) formulation for the problems is given:(6)Pminimize∑rTr,subject to(7)∑rxir=1,∀i,(8)∑ixir=1,∀r,(9)br1+∑ipi1xir≤br+11,r≤n−1,(10)br2+∑ipi2xir+∑i∑jsijyijr≤br+12,r≤n−1,(11)br1+∑ipi1xr≤br2,∀r,(12)br1+∑ipi1+wixir≥br2,∀r,(13)xir+xjr+1−1≤yijr,∀i≠j,r=1,…,n−1,(14)yijr≤xir,∀i≠j,r=1,…,r,…,n−1,(15)yijr≤xjr+1,∀i≠j,r=1,…,r,…,n−1(16)br2+∑ipi2xir≤cr2,∀r,(17)cr2−∑idixir≤Tr,∀r,(18)br1,br2,cr2≥0,∀r,(19)xir,yijr∈0,1,∀i,j,r.Objective function (6) is to minimize the total tardiness. Constraints (7) and (8) ensure that each job is placed at only one position in the sequence, and only one job can be placed at each position. Constraints (9)–(12) define the start time of each job in the considered flowshop. Constraints (13)–(15) define the relationship between xir and yijr for sequence-dependent setup times. Constraints (16) and (17) compute the completion time and tardiness of jobs. Constraints (18) and (19) define the domain of the decision variables.


## 3. Heuristic Algorithms

In this section, three types of heuristic algorithms are proposed to solve the considered problem. The algorithms are list scheduling rules, a modified NEH algorithm (MNEH), and a genetic algorithm (GA). As only permutation schedules are considered in this study, feasible permutation schedules are obtained by these heuristic algorithms, and completion times and tardiness of each jobs are computed with equations (1)–(5) provided in Section 2.


### 3.1. List Scheduling Rules

List scheduling rules are widely used in practice (e.g., in semiconductor manufacturing systems) because they are intuitive and easy to develop and apply. Four list scheduling rules are used as described below, and schedules are obtained by sorting jobs in a nondecreasing order of the values according to the methods:(i)
Earliest due date (EDD):di(ii)
Modified due date (MDD):di′′=maxdi,C2σi,foriεU(iii)
Slack:maxdi−C2σi,0,foriεU(iv)
Greedy:maxC2σi−di,0,foriεU


### 3.2. Modified NEH Algorithm

The heuristic algorithm proposed in this subsection is modified from the constructive NEH algorithm [30], which is known to work well in flowshop scheduling problems and has been modified by many researchers for various scheduling problems. The procedure of MNEH is summarized as follows.


#### 3.2.1. Procedure: MNEH

(i)
Step 0. Obtain a seed sequence from the list scheduling method. Let σ be this sequence and set σ∗=∅,r=1. Go to Step 1.(ii)
Step 1. Select the rth job in σ. Go to Step 2.(iii)
Step 2. For i=1;i≤σ∗+1;i++, insert the selected job into the ith position of σ∗ and compute the total tardiness.(iv)
Step 3. Among the σ∗+1 partial schedules obtained in Step 2, select a partial schedule that results in minimum total tardiness. Let σ∗ be the selected partial schedule. Go to Step 4.(v)
Step 4.r⟵r+1. If r<n, go to Step 1; otherwise, go to Step 5.(vi)
Step 5. Set i=1 and j=2. Go to Step 6.(vii)
Step 6. Generate a new sequence by interchanging two jobs in the ith and jth positions in σ∗. If the total tardiness of the new sequence is less than that of σ∗, then replace σ∗ with the new sequence and go to Step 5; otherwise, go to Step 7.(viii)
Step 7. Let j←j+1. If j≤n, go to Step 6; otherwise, let i←i+1 and j←i+1. If i<n, go to Step 6; otherwise, terminate. σ∗ is the final solution of this heuristic.


### 3.3. Genetic Algorithm

The GA was first introduced [31] as an optimization method that mimics the evolution of the natural world, and it is one of the most popular methods in the field of optimization because of its powerful search mechanism and ability to solve problems. The effectiveness of a GA depends on the procedure design, operators, and parameters. Thus, the following subsections describe the design of the proposed GA in this study.


#### 3.3.1. Solution Representation

In the proposed GA, solutions are expressed in the chromosome structure, and the performance of the algorithm may vary depending on how the chromosome is expressed. In this study, the sequence of jobs is expressed in chromosomal structure because only the permutation schedule is considered.


#### 3.3.2. Initial Population

To generate an initial population, list scheduling methods and the MNEH algorithm are used. That is, four solutions are generated from the list scheduling methods and used to generate four further solutions by MNEH. However, Steps 5–7 of MNEH are not applied here because these steps require a long computation time in large-sized problems. The remainder of the initial population is generated randomly.


#### 3.3.3. Fitness Evaluation

Fitness is the evaluated objective value of a solution; that is, the evaluation value represents how good a solution is. Here, the total tardiness, which is aimed to be minimized by the objective function of the considered problem, is used for fitness evaluation. Then, the lower the total tardiness, the better the solution.


#### 3.3.4. Selection

Selection is to choose a set of parents from the population to generate the offspring. In general, selection is based on the quality of the solutions and randomness. In the proposed GA, the two most widely used schemes in the literature (tournament and roulette) are used for selection.In the tournament method, four chromosomes are selected randomly from the population, and pairwise comparisons are performed to choose two chromosomes as parents. That is, the better of the first two chromosomes and the better of the last two chromosomes are selected as the parents.For the roulette methods, the inverse of the objective function value for all chromosomesi in the population is computed; that is, fi=1/∑rTr+1. Note that 1 is added to the denominator to avoid a case of dividing by zero because the objective function value (total tardiness Tr) can be zero.The selection probability of each chromosome in the population is then obtained byprobi=fi/∑fi. Based on these selection probabilities of chromosomes, two chromosomes to be parents are selected randomly.


#### 3.3.5. Crossover

The purpose of the crossover operation is to generate better offspring by exchanging the information of the selected parents. In the proposed GA, nine types of crossover are considered: one-point order crossover (OX1), two-point order crossover (OX2), order-based crossover (OBX), position-based crossover (PBX), partially matched crossover (PMX), similar job crossover (SJX), two-point similar job crossover (SJX2), similar block crossover (SBX), and two-point similar block crossover (SBX2).For a description of these crossovers, letparent1 and parent2 be the selected parents to generate offspring.(i)
Procedure: OX1Step 0. Let point1 be a randomly selected cutoff point from parent1.Step 1. Offspring inherits the front part (from the first to point1) of parent1.Step 2. Delete jobs that are already placed in offspring from parent2.Step 3. Place the jobs in parent2 into the unplaced positions of offspring in the order in which they appear in parent2.(ii)
Procedure: OX2Step 0. Let point1 and point2 be two randomly selected cutoff points from parent1.Step 1. Offspring inherits the middle part (between point1 and point2) of parent1.Step 2. Delete jobs that are already placed in offspring from parent2.Step 3. Place the jobs in parent2 into the unplaced positions of offspring from left to right in the order in which they appear in parent2.(iii)
Procedure: OBXStep 0. Let setJ be a set of jobs from parent1 at random.Step 1. Let setP be a set of positions corresponding jobs in setJ from parent2.Step 2. Place the jobs in setJ into the positions in setP of offspring from left to right in the order in which the jobs appear in parent1.Step 3. Delete jobs that are already placed in offspring from parent2.Step 4. Place the jobs in parent2 into the unplaced positions of offspring from left to right in the order in which they appear in parent2.(iv)
Procedure: PBXStep 0. Select a set of positions from parent1 at random.Step 1. Offspring inherits the jobs placed in the positions of the set from parent1.Step 2. Delete jobs that are already placed in offspring from parent2.Step 3. Place the jobs in parent2 into the unplaced positions of offspring from left to right in the order in which they appear in parent2.(v)
Procedure: PMXStep 0. Let point1 and point2 be two randomly selected cutoff points from parent1.Step 1. Offspring inherits the middle part (between point1 and point2) of parent1.Step 2. For each unplaced position in offspring, the job in the same position in parent2 is placed.Step 3. Delete jobs that are already placed in offspring from parent2.Step 4. If duplicate jobs occur before point1 and after point2, these jobs are exchanged with the remaining jobs in parent2, considering the order of parent2.(vi)
Procedure: SJXStep 0. Offspring inherits jobs in the same position in the two parents.Step 1. Let point1 be a randomly selected cutoff point from parent1.Step 2. Offspring inherits the front part (from the first to the point1) of parent1.Step 3. Delete jobs that are already placed in offspring from parent2.Step 4. Place the jobs in parent2 into the unplaced positions of offspring in the order in which they appear in parent2.In SJX2, Steps 1 and 2 of SJX are modified by considering two cutoff points, as in OX2. Additionally, SBX and SBX2 are very similar to SJX and SJX2, respectively. In SBX and SBX2, a block means two consecutive jobs, and the only difference is that an offspring inherits the blocks in the same position in the two parents in Step 0. Thus, the detailed procedures of SJX2, SBX, and SBX2 are omitted.


#### 3.3.6. Mutation

A mutation is an operation to escape from the local optimum and increase the variability and diversity in the population. This operation partially modifies a chromosome to generateoffspring with a new chromosome. In the proposed GA, three types of mutation schemes are considered: interchange, insertion, and swap.(i)
Interchange: two randomly selected jobs are interchanged.(ii)
Insertion: a randomly selected job is inserted into a randomly selected position.(iii)
Swap: a randomly selected job is swapped with the next job.


#### 3.3.7. Improvement (Local Search)

Local search methods are commonly used in genetic algorithms as well as other (meta)heuristics to improve the solutions. A local search strategy based on insertion is also used in the proposed GA. This local search is triggered when the current best objective function value is not improved for a predetermined number of consecutive generations. When the local search is triggered, insertion is applied3n times to the best solution in the population, where n is the number of jobs. If the new solution is better than the current best solution, the current solution is replaced with the new solution. Note that because excessive local search attempts may consume a long computation time, the number of interchanges is limited to 3n.


#### 3.3.8. Restart

The goal of a restart procedure is to avoid premature convergence in the population and improve the solution quality obtained by GA. The restart procedure in the proposed GA is based on that of Ruiz and Maroto [32]. This restart procedure is triggered when the current best objective function value is not improved for a predetermined number of consecutive generations. The restart procedure is summarized below.(i)
Procedure: restartStep 0. Sort the chromosomes in the population in a nondecreasing order of their fitness value.Step 1. Keep the first 20% of chromosomes and remove the remaining 80% of the chromosomes from the population.Step 2. For the 20% of the population size, chromosomes are selected randomly from the first 20% of chromosomes, and the selected chromosomes are mutated once with an insertion operation.Step 3. For the 20% of the population size, chromosomes are selected randomly from the first 20% of chromosomes, and the selected chromosomes are mutated once with an interchange operation.Step 4. The remaining 40% of chromosomes are generated randomly.


#### 3.3.9. Termination Criterion

The termination criterion applied to the proposed GA is the maximum CPU time. That is, when the maximum CPU time from the start of the GA elapses, the GA procedure stops.


#### 3.3.10. Whole Procedure of the Proposed GA

The procedure of the proposed GA is summarized below, using the operators described above.(i)
Procedure: proposed GA(ii)
Step 0. Let POP, Psize, pc, and pm be the population, population size, crossover probability, and mutation probability, respectively.(iii)
Step 1. Generate an initial population with Psize chromosomes. Let POP be the initial population.(iv)
Step 2. Set i=1. While i<Psize, do the following.(v)
Perform a selection operation to select two parents from POP. Letparent1 and parent2 be the selected parents.(vi)
Generate a random numberrand in [0, 1]. If rand<pc, perform a crossover operation to generate offspring1 and offspring2. Otherwise, offspring1 and offspring2 inherit the information from parent1 and parent2, respectively.(vii)
Generate a random numberrand in [0, 1]. If rand<pm, perform a mutation operation for offspring1 and offspring2.(viii)
Evaluate the fitness value ofoffspring1 and offspring2.(ix)
Ifoffsping1 is better than the worst chromosome in POP, replace the worst chromosome with offsping1. Repeat the same procedure for offspring2.(x)
Leti=i+2.(xi)
Step 3. Check the local search condition; if it is met, trigger a local search for the best chromosome in POP.(xii)
Step 4. Check the restart condition; if it is met, trigger the restart procedure for POP. Evaluate the fitness values of the chromosomes in POP.(xiii)
Step 5. Check the termination condition; if it is met, terminate and the best solution in POP is the final solution. Otherwise, go to Step 2.


## 3.1. List Scheduling Rules

List scheduling rules are widely used in practice (e.g., in semiconductor manufacturing systems) because they are intuitive and easy to develop and apply. Four list scheduling rules are used as described below, and schedules are obtained by sorting jobs in a nondecreasing order of the values according to the methods:(i)
Earliest due date (EDD):di(ii)
Modified due date (MDD):di′′=maxdi,C2σi,foriεU(iii)
Slack:maxdi−C2σi,0,foriεU(iv)
Greedy:maxC2σi−di,0,foriεU


## 3.2. Modified NEH Algorithm

The heuristic algorithm proposed in this subsection is modified from the constructive NEH algorithm [30], which is known to work well in flowshop scheduling problems and has been modified by many researchers for various scheduling problems. The procedure of MNEH is summarized as follows.


### 3.2.1. Procedure: MNEH

(i)
Step 0. Obtain a seed sequence from the list scheduling method. Let σ be this sequence and set σ∗=∅,r=1. Go to Step 1.(ii)
Step 1. Select the rth job in σ. Go to Step 2.(iii)
Step 2. For i=1;i≤σ∗+1;i++, insert the selected job into the ith position of σ∗ and compute the total tardiness.(iv)
Step 3. Among the σ∗+1 partial schedules obtained in Step 2, select a partial schedule that results in minimum total tardiness. Let σ∗ be the selected partial schedule. Go to Step 4.(v)
Step 4.r⟵r+1. If r<n, go to Step 1; otherwise, go to Step 5.(vi)
Step 5. Set i=1 and j=2. Go to Step 6.(vii)
Step 6. Generate a new sequence by interchanging two jobs in the ith and jth positions in σ∗. If the total tardiness of the new sequence is less than that of σ∗, then replace σ∗ with the new sequence and go to Step 5; otherwise, go to Step 7.(viii)
Step 7. Let j←j+1. If j≤n, go to Step 6; otherwise, let i←i+1 and j←i+1. If i<n, go to Step 6; otherwise, terminate. σ∗ is the final solution of this heuristic.


## 3.2.1. Procedure: MNEH

(i)
Step 0. Obtain a seed sequence from the list scheduling method. Let σ be this sequence and set σ∗=∅,r=1. Go to Step 1.(ii)
Step 1. Select the rth job in σ. Go to Step 2.(iii)
Step 2. For i=1;i≤σ∗+1;i++, insert the selected job into the ith position of σ∗ and compute the total tardiness.(iv)
Step 3. Among the σ∗+1 partial schedules obtained in Step 2, select a partial schedule that results in minimum total tardiness. Let σ∗ be the selected partial schedule. Go to Step 4.(v)
Step 4.r⟵r+1. If r<n, go to Step 1; otherwise, go to Step 5.(vi)
Step 5. Set i=1 and j=2. Go to Step 6.(vii)
Step 6. Generate a new sequence by interchanging two jobs in the ith and jth positions in σ∗. If the total tardiness of the new sequence is less than that of σ∗, then replace σ∗ with the new sequence and go to Step 5; otherwise, go to Step 7.(viii)
Step 7. Let j←j+1. If j≤n, go to Step 6; otherwise, let i←i+1 and j←i+1. If i<n, go to Step 6; otherwise, terminate. σ∗ is the final solution of this heuristic.


## 3.3. Genetic Algorithm

The GA was first introduced [31] as an optimization method that mimics the evolution of the natural world, and it is one of the most popular methods in the field of optimization because of its powerful search mechanism and ability to solve problems. The effectiveness of a GA depends on the procedure design, operators, and parameters. Thus, the following subsections describe the design of the proposed GA in this study.


### 3.3.1. Solution Representation

In the proposed GA, solutions are expressed in the chromosome structure, and the performance of the algorithm may vary depending on how the chromosome is expressed. In this study, the sequence of jobs is expressed in chromosomal structure because only the permutation schedule is considered.


### 3.3.2. Initial Population

To generate an initial population, list scheduling methods and the MNEH algorithm are used. That is, four solutions are generated from the list scheduling methods and used to generate four further solutions by MNEH. However, Steps 5–7 of MNEH are not applied here because these steps require a long computation time in large-sized problems. The remainder of the initial population is generated randomly.


### 3.3.3. Fitness Evaluation

Fitness is the evaluated objective value of a solution; that is, the evaluation value represents how good a solution is. Here, the total tardiness, which is aimed to be minimized by the objective function of the considered problem, is used for fitness evaluation. Then, the lower the total tardiness, the better the solution.


### 3.3.4. Selection

Selection is to choose a set of parents from the population to generate the offspring. In general, selection is based on the quality of the solutions and randomness. In the proposed GA, the two most widely used schemes in the literature (tournament and roulette) are used for selection.In the tournament method, four chromosomes are selected randomly from the population, and pairwise comparisons are performed to choose two chromosomes as parents. That is, the better of the first two chromosomes and the better of the last two chromosomes are selected as the parents.For the roulette methods, the inverse of the objective function value for all chromosomesi in the population is computed; that is, fi=1/∑rTr+1. Note that 1 is added to the denominator to avoid a case of dividing by zero because the objective function value (total tardiness Tr) can be zero.The selection probability of each chromosome in the population is then obtained byprobi=fi/∑fi. Based on these selection probabilities of chromosomes, two chromosomes to be parents are selected randomly.


### 3.3.5. Crossover

The purpose of the crossover operation is to generate better offspring by exchanging the information of the selected parents. In the proposed GA, nine types of crossover are considered: one-point order crossover (OX1), two-point order crossover (OX2), order-based crossover (OBX), position-based crossover (PBX), partially matched crossover (PMX), similar job crossover (SJX), two-point similar job crossover (SJX2), similar block crossover (SBX), and two-point similar block crossover (SBX2).For a description of these crossovers, letparent1 and parent2 be the selected parents to generate offspring.(i)
Procedure: OX1Step 0. Let point1 be a randomly selected cutoff point from parent1.Step 1. Offspring inherits the front part (from the first to point1) of parent1.Step 2. Delete jobs that are already placed in offspring from parent2.Step 3. Place the jobs in parent2 into the unplaced positions of offspring in the order in which they appear in parent2.(ii)
Procedure: OX2Step 0. Let point1 and point2 be two randomly selected cutoff points from parent1.Step 1. Offspring inherits the middle part (between point1 and point2) of parent1.Step 2. Delete jobs that are already placed in offspring from parent2.Step 3. Place the jobs in parent2 into the unplaced positions of offspring from left to right in the order in which they appear in parent2.(iii)
Procedure: OBXStep 0. Let setJ be a set of jobs from parent1 at random.Step 1. Let setP be a set of positions corresponding jobs in setJ from parent2.Step 2. Place the jobs in setJ into the positions in setP of offspring from left to right in the order in which the jobs appear in parent1.Step 3. Delete jobs that are already placed in offspring from parent2.Step 4. Place the jobs in parent2 into the unplaced positions of offspring from left to right in the order in which they appear in parent2.(iv)
Procedure: PBXStep 0. Select a set of positions from parent1 at random.Step 1. Offspring inherits the jobs placed in the positions of the set from parent1.Step 2. Delete jobs that are already placed in offspring from parent2.Step 3. Place the jobs in parent2 into the unplaced positions of offspring from left to right in the order in which they appear in parent2.(v)
Procedure: PMXStep 0. Let point1 and point2 be two randomly selected cutoff points from parent1.Step 1. Offspring inherits the middle part (between point1 and point2) of parent1.Step 2. For each unplaced position in offspring, the job in the same position in parent2 is placed.Step 3. Delete jobs that are already placed in offspring from parent2.Step 4. If duplicate jobs occur before point1 and after point2, these jobs are exchanged with the remaining jobs in parent2, considering the order of parent2.(vi)
Procedure: SJXStep 0. Offspring inherits jobs in the same position in the two parents.Step 1. Let point1 be a randomly selected cutoff point from parent1.Step 2. Offspring inherits the front part (from the first to the point1) of parent1.Step 3. Delete jobs that are already placed in offspring from parent2.Step 4. Place the jobs in parent2 into the unplaced positions of offspring in the order in which they appear in parent2.In SJX2, Steps 1 and 2 of SJX are modified by considering two cutoff points, as in OX2. Additionally, SBX and SBX2 are very similar to SJX and SJX2, respectively. In SBX and SBX2, a block means two consecutive jobs, and the only difference is that an offspring inherits the blocks in the same position in the two parents in Step 0. Thus, the detailed procedures of SJX2, SBX, and SBX2 are omitted.


### 3.3.6. Mutation

A mutation is an operation to escape from the local optimum and increase the variability and diversity in the population. This operation partially modifies a chromosome to generateoffspring with a new chromosome. In the proposed GA, three types of mutation schemes are considered: interchange, insertion, and swap.(i)
Interchange: two randomly selected jobs are interchanged.(ii)
Insertion: a randomly selected job is inserted into a randomly selected position.(iii)
Swap: a randomly selected job is swapped with the next job.


### 3.3.7. Improvement (Local Search)

Local search methods are commonly used in genetic algorithms as well as other (meta)heuristics to improve the solutions. A local search strategy based on insertion is also used in the proposed GA. This local search is triggered when the current best objective function value is not improved for a predetermined number of consecutive generations. When the local search is triggered, insertion is applied3n times to the best solution in the population, where n is the number of jobs. If the new solution is better than the current best solution, the current solution is replaced with the new solution. Note that because excessive local search attempts may consume a long computation time, the number of interchanges is limited to 3n.


### 3.3.8. Restart

The goal of a restart procedure is to avoid premature convergence in the population and improve the solution quality obtained by GA. The restart procedure in the proposed GA is based on that of Ruiz and Maroto [32]. This restart procedure is triggered when the current best objective function value is not improved for a predetermined number of consecutive generations. The restart procedure is summarized below.(i)
Procedure: restartStep 0. Sort the chromosomes in the population in a nondecreasing order of their fitness value.Step 1. Keep the first 20% of chromosomes and remove the remaining 80% of the chromosomes from the population.Step 2. For the 20% of the population size, chromosomes are selected randomly from the first 20% of chromosomes, and the selected chromosomes are mutated once with an insertion operation.Step 3. For the 20% of the population size, chromosomes are selected randomly from the first 20% of chromosomes, and the selected chromosomes are mutated once with an interchange operation.Step 4. The remaining 40% of chromosomes are generated randomly.


### 3.3.9. Termination Criterion

The termination criterion applied to the proposed GA is the maximum CPU time. That is, when the maximum CPU time from the start of the GA elapses, the GA procedure stops.


### 3.3.10. Whole Procedure of the Proposed GA

The procedure of the proposed GA is summarized below, using the operators described above.(i)
Procedure: proposed GA(ii)
Step 0. Let POP, Psize, pc, and pm be the population, population size, crossover probability, and mutation probability, respectively.(iii)
Step 1. Generate an initial population with Psize chromosomes. Let POP be the initial population.(iv)
Step 2. Set i=1. While i<Psize, do the following.(v)
Perform a selection operation to select two parents from POP. Letparent1 and parent2 be the selected parents.(vi)
Generate a random numberrand in [0, 1]. If rand<pc, perform a crossover operation to generate offspring1 and offspring2. Otherwise, offspring1 and offspring2 inherit the information from parent1 and parent2, respectively.(vii)
Generate a random numberrand in [0, 1]. If rand<pm, perform a mutation operation for offspring1 and offspring2.(viii)
Evaluate the fitness value ofoffspring1 and offspring2.(ix)
Ifoffsping1 is better than the worst chromosome in POP, replace the worst chromosome with offsping1. Repeat the same procedure for offspring2.(x)
Leti=i+2.(xi)
Step 3. Check the local search condition; if it is met, trigger a local search for the best chromosome in POP.(xii)
Step 4. Check the restart condition; if it is met, trigger the restart procedure for POP. Evaluate the fitness values of the chromosomes in POP.(xiii)
Step 5. Check the termination condition; if it is met, terminate and the best solution in POP is the final solution. Otherwise, go to Step 2.


## 3.3.1. Solution Representation

In the proposed GA, solutions are expressed in the chromosome structure, and the performance of the algorithm may vary depending on how the chromosome is expressed. In this study, the sequence of jobs is expressed in chromosomal structure because only the permutation schedule is considered.


## 3.3.2. Initial Population

To generate an initial population, list scheduling methods and the MNEH algorithm are used. That is, four solutions are generated from the list scheduling methods and used to generate four further solutions by MNEH. However, Steps 5–7 of MNEH are not applied here because these steps require a long computation time in large-sized problems. The remainder of the initial population is generated randomly.


## 3.3.3. Fitness Evaluation

Fitness is the evaluated objective value of a solution; that is, the evaluation value represents how good a solution is. Here, the total tardiness, which is aimed to be minimized by the objective function of the considered problem, is used for fitness evaluation. Then, the lower the total tardiness, the better the solution.


## 3.3.4. Selection

Selection is to choose a set of parents from the population to generate the offspring. In general, selection is based on the quality of the solutions and randomness. In the proposed GA, the two most widely used schemes in the literature (tournament and roulette) are used for selection.In the tournament method, four chromosomes are selected randomly from the population, and pairwise comparisons are performed to choose two chromosomes as parents. That is, the better of the first two chromosomes and the better of the last two chromosomes are selected as the parents.For the roulette methods, the inverse of the objective function value for all chromosomesi in the population is computed; that is, fi=1/∑rTr+1. Note that 1 is added to the denominator to avoid a case of dividing by zero because the objective function value (total tardiness Tr) can be zero.The selection probability of each chromosome in the population is then obtained byprobi=fi/∑fi. Based on these selection probabilities of chromosomes, two chromosomes to be parents are selected randomly.


## 3.3.5. Crossover

The purpose of the crossover operation is to generate better offspring by exchanging the information of the selected parents. In the proposed GA, nine types of crossover are considered: one-point order crossover (OX1), two-point order crossover (OX2), order-based crossover (OBX), position-based crossover (PBX), partially matched crossover (PMX), similar job crossover (SJX), two-point similar job crossover (SJX2), similar block crossover (SBX), and two-point similar block crossover (SBX2).For a description of these crossovers, letparent1 and parent2 be the selected parents to generate offspring.(i)
Procedure: OX1Step 0. Let point1 be a randomly selected cutoff point from parent1.Step 1. Offspring inherits the front part (from the first to point1) of parent1.Step 2. Delete jobs that are already placed in offspring from parent2.Step 3. Place the jobs in parent2 into the unplaced positions of offspring in the order in which they appear in parent2.(ii)
Procedure: OX2Step 0. Let point1 and point2 be two randomly selected cutoff points from parent1.Step 1. Offspring inherits the middle part (between point1 and point2) of parent1.Step 2. Delete jobs that are already placed in offspring from parent2.Step 3. Place the jobs in parent2 into the unplaced positions of offspring from left to right in the order in which they appear in parent2.(iii)
Procedure: OBXStep 0. Let setJ be a set of jobs from parent1 at random.Step 1. Let setP be a set of positions corresponding jobs in setJ from parent2.Step 2. Place the jobs in setJ into the positions in setP of offspring from left to right in the order in which the jobs appear in parent1.Step 3. Delete jobs that are already placed in offspring from parent2.Step 4. Place the jobs in parent2 into the unplaced positions of offspring from left to right in the order in which they appear in parent2.(iv)
Procedure: PBXStep 0. Select a set of positions from parent1 at random.Step 1. Offspring inherits the jobs placed in the positions of the set from parent1.Step 2. Delete jobs that are already placed in offspring from parent2.Step 3. Place the jobs in parent2 into the unplaced positions of offspring from left to right in the order in which they appear in parent2.(v)
Procedure: PMXStep 0. Let point1 and point2 be two randomly selected cutoff points from parent1.Step 1. Offspring inherits the middle part (between point1 and point2) of parent1.Step 2. For each unplaced position in offspring, the job in the same position in parent2 is placed.Step 3. Delete jobs that are already placed in offspring from parent2.Step 4. If duplicate jobs occur before point1 and after point2, these jobs are exchanged with the remaining jobs in parent2, considering the order of parent2.(vi)
Procedure: SJXStep 0. Offspring inherits jobs in the same position in the two parents.Step 1. Let point1 be a randomly selected cutoff point from parent1.Step 2. Offspring inherits the front part (from the first to the point1) of parent1.Step 3. Delete jobs that are already placed in offspring from parent2.Step 4. Place the jobs in parent2 into the unplaced positions of offspring in the order in which they appear in parent2.In SJX2, Steps 1 and 2 of SJX are modified by considering two cutoff points, as in OX2. Additionally, SBX and SBX2 are very similar to SJX and SJX2, respectively. In SBX and SBX2, a block means two consecutive jobs, and the only difference is that an offspring inherits the blocks in the same position in the two parents in Step 0. Thus, the detailed procedures of SJX2, SBX, and SBX2 are omitted.


## 3.3.6. Mutation

A mutation is an operation to escape from the local optimum and increase the variability and diversity in the population. This operation partially modifies a chromosome to generateoffspring with a new chromosome. In the proposed GA, three types of mutation schemes are considered: interchange, insertion, and swap.(i)
Interchange: two randomly selected jobs are interchanged.(ii)
Insertion: a randomly selected job is inserted into a randomly selected position.(iii)
Swap: a randomly selected job is swapped with the next job.


## 3.3.7. Improvement (Local Search)

Local search methods are commonly used in genetic algorithms as well as other (meta)heuristics to improve the solutions. A local search strategy based on insertion is also used in the proposed GA. This local search is triggered when the current best objective function value is not improved for a predetermined number of consecutive generations. When the local search is triggered, insertion is applied3n times to the best solution in the population, where n is the number of jobs. If the new solution is better than the current best solution, the current solution is replaced with the new solution. Note that because excessive local search attempts may consume a long computation time, the number of interchanges is limited to 3n.


## 3.3.8. Restart

The goal of a restart procedure is to avoid premature convergence in the population and improve the solution quality obtained by GA. The restart procedure in the proposed GA is based on that of Ruiz and Maroto [32]. This restart procedure is triggered when the current best objective function value is not improved for a predetermined number of consecutive generations. The restart procedure is summarized below.(i)
Procedure: restartStep 0. Sort the chromosomes in the population in a nondecreasing order of their fitness value.Step 1. Keep the first 20% of chromosomes and remove the remaining 80% of the chromosomes from the population.Step 2. For the 20% of the population size, chromosomes are selected randomly from the first 20% of chromosomes, and the selected chromosomes are mutated once with an insertion operation.Step 3. For the 20% of the population size, chromosomes are selected randomly from the first 20% of chromosomes, and the selected chromosomes are mutated once with an interchange operation.Step 4. The remaining 40% of chromosomes are generated randomly.


## 3.3.9. Termination Criterion

The termination criterion applied to the proposed GA is the maximum CPU time. That is, when the maximum CPU time from the start of the GA elapses, the GA procedure stops.


## 3.3.10. Whole Procedure of the Proposed GA

The procedure of the proposed GA is summarized below, using the operators described above.(i)
Procedure: proposed GA(ii)
Step 0. Let POP, Psize, pc, and pm be the population, population size, crossover probability, and mutation probability, respectively.(iii)
Step 1. Generate an initial population with Psize chromosomes. Let POP be the initial population.(iv)
Step 2. Set i=1. While i<Psize, do the following.(v)
Perform a selection operation to select two parents from POP. Letparent1 and parent2 be the selected parents.(vi)
Generate a random numberrand in [0, 1]. If rand<pc, perform a crossover operation to generate offspring1 and offspring2. Otherwise, offspring1 and offspring2 inherit the information from parent1 and parent2, respectively.(vii)
Generate a random numberrand in [0, 1]. If rand<pm, perform a mutation operation for offspring1 and offspring2.(viii)
Evaluate the fitness value ofoffspring1 and offspring2.(ix)
Ifoffsping1 is better than the worst chromosome in POP, replace the worst chromosome with offsping1. Repeat the same procedure for offspring2.(x)
Leti=i+2.(xi)
Step 3. Check the local search condition; if it is met, trigger a local search for the best chromosome in POP.(xii)
Step 4. Check the restart condition; if it is met, trigger the restart procedure for POP. Evaluate the fitness values of the chromosomes in POP.(xiii)
Step 5. Check the termination condition; if it is met, terminate and the best solution in POP is the final solution. Otherwise, go to Step 2.


## 4. Computational Experiments

### 4.1. Test Instance and Environment

Computational experiments were performed with randomly generated problems to evaluate the performance of the proposed algorithms. All algorithms were coded in Java, and the experiments were performed on a PC with a 3.2 GHz Intel Core i7-8700 CPU.To generate problem instances, job information (processing times, sequence-dependent setup times SDST, and limited waiting times LWT) was generated according to the method presented in [3]. The processing times were generated from U1,50, where Ua,b denotes the discrete uniform distribution with a range a,b. SDST and LWT were generated from U0,50 and U1,100, respectively. The due dates of the jobs were generated from UX1−T−R/2,X1−T+R/2, where X is the lower bound on the makespan, and T and R are the tardiness factor and range of due dates parameters, respectively. Here, to obtain the values of X, we assumed that SDSTs for each job i were set to sij=minsij|∀j and LWTs were infinite; then X is obtained by Johnson’s algorithm [33] that provides the minimum makespan in the typical two-machine flowshop. For the distribution of due dates, three levels for each of T and R were used; that is, T=0.2,0.4,and0.6 and R=0.2,0.5,and0.8.


### 4.2. GA Calibration

The performance of GA significantly depends on its operators and parameters. Hence, a calibration experiment is needed to select the best operators and parameters. The proposed GA has eight operators and parameters, which are listed below, and all possible combinations were evaluated to obtain the best among them.(i)
Selection: two levels (tournament and roulette)(ii)
Crossover: nine levels (OX1, OX2, OBX, PBX, PMX, SJX, SJX2, SBX, and SBX2)(iii)
Mutation: three levels (interchange, insertion, and swap)(iv)
Population sizePsize: three levels 30,50,100(v)
Crossover probabilitypc: six levels 0.2,0.35,0.5,0.65,0.8,0.95(vi)
Mutation probabilitypm: four levels 0.2,0.4,0.6,0.8(vii)
Local searchPl: three levels 5,10,20(viii)
RestartPr: four levels 25,50,75,100For these eight types of operators and parameters, 46,656 different combinations are possible. To simplify the experiment, this test is divided into two experiments. The first experiment was to select the best combination for selection, crossover, and mutation, and the second experiment was to find the best combination for the other parameters.For the evaluation and selection for the GA operators in the first experiment, a full factorial design of selection, crossover, and mutation is considered; hence, 54 different algorithms are tested. The remaining parameters were fixed toPsize,pc,pm,Pl,Pr=50,0.5,0.4,10,50. Additionally, four levels were considered for the number of jobs n=20,50,100and200, and five instances for each combination (T, R, and n) were generated. That is, 180 problem instances were generated. For a termination criterion, the maximum CPU time was set to 30n milliseconds (ms). To compare different GAs for each problem instance, the relative deviation index (RDI) was considered as a measure; RDI is defined as RDUI=Algsol−Minsol/Maxsol−Minsol, where Algsol is the objective function value from the current algorithm, and Minsol and Maxsol are the minimum and maximum values among the objective function values obtained from the algorithms in this comparison, respectively. Particularly when Maxsol=Minsol, RDI will be 0 for all the algorithms.To see the effect of GA operators on the performance, analysis of variance (ANOVA) was performed using SPSS and the ANOVA table is shown in Table2. As can be seen in the table, the performance of the proposed GA was significantly affected by the operators with a significance level of 0.05. According to the F-values, three operators were significantly effective on the RDI. Figure 1 illustrates the main effect plot to find the best operators with lower RDI values. As shown in the figure, roulette, OX2, and insertion showed better performance. This is possibly because the change of fore and rear parts in sequences can lead to searching for better sequences in this scheduling problem with sequence-dependent setup times. For mutation, insertion is observed to be the best, which has been regarded in various flowshop scheduling studies as the best mutation operator [32]. Therefore, roulette, OX2, and insertion were used in the following experiment.Table 2
ANOVA for the effect of GA operators on the performance.
SourcesSum. squaresDFMSFp-valueCorrected model200.087533.77566.464≤0.001Intercept2110.73012110.73037160.094≤0.001Selection9.65819.658170.026≤0.001Crossover35.65784.45778.468≤0.001Mutation116.139258.0701022.336≤0.001Selection × crossover27.60583.45160.749≤0.001Selection × mutation0.58820.2945.1750.006Crossover × mutation7.298160.4568.030≤0.001Selection × crossover × mutation3.143160.1963.458≤0.001Error549.03896660.057––Total2859.8559720–––Corrected total749.1259719–––Significance level = 0.05.Figure 1
Main effect plot of GA operators.The second experiment was performed to find the best combination of parameters of the proposed GA. Considering all levels ofPsize,pc,pm,Pl,Pr, 864 different combinations were evaluated using the same approach as that for the operators. The ANOVA results are summarized in Table 3, which shows that pc, pm, and Pr are the most significant parameters that affect the GA performance. As shown in Figure 2, which illustrates the main effect plot of GA parameters, RDI had the lowest value at each of Psize,pc,pm,Pl,Pr=50,0.35,0.6,5,75, respectively. The bath-curves are observed for all parameters except Pl. That is, both higher and lower values from the selected values yielded worse results, validating the chosen range of values for these parameters in the experiments. For Pl, frequent local searches were more effective when the best solution in the population was not improved. Notably, the probability of mutation is larger than that of crossover. This is probably because a small change by a mutation may lead to a better sequence rather than crossover. That is, because limited waiting time constraints and sequence-dependent setup times were considered in this study, the solution may be improved by small changes in a job sequence. Thus, using the selected parameters, the proposed GA attempts to find better solutions by keeping the sequences in good solutions and making a few changes. In summary, the proposed GA uses roulette, OX2, and insertion for the operators and Psize=50, pc=0.35, pm=0.6, Pl=5, and Pr=75 for the parameters.Table 3
ANOVA for the effect of GA parameters on the performance.
SourcesSum. squaresDFMSFp-valueCorrected model157.1038630.1823.329≤0.001Intercept29023.089129023.089530673.217≤0.001Psize1.62920.81514.897≤0.001pc23.04354.60984.267≤0.001pm40.992313.664249.839≤0.001Pr23.98937.996146.206≤0.001Pl0.19720.0981.8000.165Psize×pc1.070100.1071.9570.034Psize×pm1.58560.2644.831≤0.001Psize×Pr1.92260.3205.859≤0.001Psize×Pl0.52840.1322.4130.047pc×pm12.065150.80414.707≤0.001pc×Pr12.324150.82215.023≤0.001pc×Pl0.752100.0751.3750.185pm×Pr3.82790.4257.774≤0.001pm×Pl0.35560.0591.0830.370Pr×Pl2.80460.4678.544≤0.001Psize×pc×pm1.502300.0500.9160.599Psize×pc×Pr1.334300.0440.8130.754Psize×pc×Pl0.845200.0420.7730.750Psize×pm×Pr0.280180.0160.2850.999Psize×pm×Pl0.454120.0380.6920.761Psize×Pr×Pl5.064120.4227.716≤0.001pc×pm×Pr4.008450.0891.6280.005pc×pm×Pl1.068300.0360.6510.928pc×Pr×Pl0.914300.0300.5570.976pm×Pr×Pl0.676180.0380.6870.828Psize×pc×pm∗Pr2.371900.0260.4821.000Psize×pc∗pm×Pl1.741600.0290.5310.999Psize×pc×Pr×Pl1.798600.0300.5480.998Psize×pm×Pr×Pl1.024360.0280.5200.992pc×pm×Pr×Pl2.236900.0250.4541.000Psize×pc×pm×Pr×Pl4.7041800.0260.4781.000Error8458.3031546560.055——Total37638.495155520———Corrected total8615.406155519———Significance level = 0.05.Figure 2
Main effect plots of GA parameters.


### 4.3. Performance Evaluation

First, the performance of the proposed MILP formulation was evaluated using CPLEX 12.9. To avoid excessive computation times for CPLEX, the maximum CPU time limit was set to 3,600 seconds (s) for each instance. For the evaluation of MILP, four levels for the number of jobsn=5,10,15,and20 were considered, and five instances for each combination of T,R,andns were generated. That is, 36 combinations for T,R,andn were considered, and 180 problem instances are generated. The results are summarized in Table 4, which shows the average computation time (ACPUT) and the number of instances (NI) that failed to find an optimal solution within the computation time limit (3,600 s). As can be seen in the table, CPLEX obtained optimal solutions for all problems up to n=10 but could not find optimal solutions for eight problems with n=15. Furthermore, for n=20, no problems were solved to optimality within the computation time limit.Table 4
Performance of CPLEX.
nACPUTsNI50.080103.220151419.53820360045In general, due dates significantly affect due date-related measures (e.g., total tardiness, which is the objective function of the considered scheduling problem in this study). Hence, the impact of the due dates on the performance of CPLEX was analyzed. The computation times of CPLEX with respect to the due date parametersT,R are summarized in Table 5, when n=15. As can be seen from the table, the performance of CPLEX was significantly affected by the values of T and R. Particularly, when T=0.2and0.4, the instances took a significantly long computation time to be solved. However, when T=0.6, the instances were solved within shorter computation times. That is, CPLEX can solve problems quickly when the due dates of jobs are tight. Regarding the range of due dates R, problems in which due dates of jobs are widely distributed were solved in a shorter computation time.Table 5
Effect of due date parameters on the performance of CPLEX.
TR=0.20.50.8Average0.21435.141580.842313.121776.370.42172.742473.35880.951842.350.6905.23255.19759.17639.86Average1504.371436.461317.751419.53Next, the performances of the proposed list scheduling rules and MNEH algorithms were evaluated by comparison to solutions obtained from CPLEX. Here, letMNEHx be an MNEH algorithm that starts with an initial solution obtained by a list scheduling rule x. Note that, for the instances not solved within the time limit, the solutions terminated at the time limit were compared. Table 6 presents the average gaps between the heuristics and CPLEX, Heusol−CPLEXsol/CPLEXsol, and the number of instances where heuristics found solutions which were equal to or better than those of CPLEX. As can be observed in the table, MEDD and Greedy demonstrated good performance among the list scheduling rules, and MNEHMEDD was the best performing heuristic algorithm. However, the average gaps from CPLEX were too large. These results explain why a metaheuristic algorithm, GA, was needed to find good solutions within a short computation time in this study.Table 6
Performance of the heuristic algorithms (versus CPLEX).
Algorithmn=5101520Avg, sumEDD0.97, 0a2.07, 010.58, 04.52, 04.53, 0MEDD0.30, 91.1, 04.69, 02.03, 02.03, 9Slack0.88, 31.48, 06.17, 02.73, 02.81, 3Greedy0.44, 91.02, 04.39, 02.25, 02.02, 9MNEHEDD0.06, 290.17, 90.71, 00.25, 00.3, 40MNEHMEDD0.05, 310.16, 70.66, 00.26, 20.28, 40MNEHSlack0.04, 320.21, 70.71, 00.3, 10.31, 40MNEHGreedy0.08, 290.28, 11.52, 00.38, 00.56, 31aAverage error gap, number of instances (out of 45 instances) for which the algorithm found solutions better than or equal to those from CPLEX.To evaluate the performance of the suggested GA, a performance evaluation by comparing it with other algorithms was required. However, to the best of our knowledge, there are no algorithms for the same problem considered in this study. Thus, the evaluation was performed by comparing the proposed GA to CPLEX in small-sized problem instances (n = 5, 10, and 15) and the proposed heuristic algorithms in medium- and large-sized problem instances (n=20, 50, 100, and 200). Through these comparisons, the effectiveness of the solutions from the proposed GA was evaluated. In these experiments, the maximum computation times of GA were set to four levels 50n,100n,500n,and1,000nms. Let GAx be the genetic algorithm in which the maximum computation time is set to x⋅nms. The effectiveness of GA solutions compared to those from CPLEX is shown in Table 7. As can be seen from the table, the suggested GA found optimal solutions for almost all problem instances. Particularly, GA outperformed CPLEX for n=20; a minus value means that the objective value of solutions from GA is less than that from CPLEX. This is probably because CPLEX fails to obtain optimal solutions within the maximum CPU time for n=20.Table 7
Evaluation of GA compared to CPLEX.
nGA50GA100GA500GA100050.00, 45a0.00, 450.00, 450.00, 45100.00, 440.00, 450.00, 450.00, 45150.01, 350, 390, 42−0.01, 4320−0.14, 38−0.15, 39−0.17, 41−0.18, 43aAverage error gap, number of instances (out of 45 instances) for which the algorithm found solutions better than or equal to those from CPLEX.For the medium and large problem instances, the GA solutions were compared with those from the MNEH algorithms. The results of this test are summarized in Table8, which shows RDI values and the number of instances where a heuristic finds the best solutions among the heuristic solutions. The table illustrates that GAs outperformed MNEH algorithms, although GAs took longer CPU times. Additionally, in the case where GA50 and MNEHGreedy had similar computation times (approximately 10 s), GA50 still showed better performance. Overall, although GA requires a longer CPU time, GA solves the problems better, and the CPU time of GA50 is also reasonably short.Table 8
Comparison between the proposed heuristic algorithms.
AlgorithmRDICPUTn=20501002002050100200MNEHEDD0.73, 0a0.67, 10.57, 10.55, 0<0.010.030.384.63MNEHMEDD0.72, 00.64, 00.6, 00.96, 0<0.010.040.46.12MNEHSlack0.86, 00.93, 10.97, 00.66, 0<0.010.040.446.12MNEHGreedy0.10, 150.7, 10.66, 00.23, 4<0.010.040.5910.19GA500.07, 230.13, 60.19, 40.17, 412.5510GA1000.05, 270.1, 90.14, 50.15, 4251020GA5000.02, 380.02, 330.05, 130.08, 5102550100GA10000.00, 430.00, 450, 450.00, 452050100200aAverage RDI, number of instances (out of 45 instances) for which the algorithm found solutions better than or equal to those from CPLEX.Additionally, the effectiveness of the proposed GA was evaluated through comparison with a simulated annealing (SA) algorithm, which is also a widely used metaheuristic for various optimization problems. SA attempts to improve an initial solution repeatedly by making small alterations until further improvements cannot be made by such alterations. The SA algorithm can avoid entrapment in a local optimum by allowing occasional uphill moves that deteriorate the objective function value. In this experiment, a simple SA algorithm is devised for comparison with the proposed GA. In this SA algorithm, a neighborhood solutionσ′ of a solution σ is generated using an insertion method, which is reported as the best mutation in the previous experiment. If Δ=Tσ′−Tσ<0, where Tx is the total tardiness of solution x, σ is replaced with σ′. Otherwise, if Δ≥0, the replacement is done with probability e−Δ/τ, where τ is a parameter called the temperature. This replacement procedure is repeated L times at a temperature, where L is called the epoch length, which is set to n2. The temperature is initially set to τ0=100 and decreases gradually by a cooling function, which is set as τx+1=τx−α, where α is a parameter that is set to 0.025 in this algorithm. The algorithm is terminated when the temperature decreases to zero or the computation time reaches the maximum computation time. The procedure of this SA algorithm is summarized below.


#### 4.3.1. Procedure: SA

(i)
Step 0. Set initial values for parameters used in the algorithm τ0=100,L=n2andα=0.025. Let τ=τ0 and l=0.(ii)
Step 1. Set an initial solution σ as the best solution among those obtained with MNEHEDD, MNEHMEDD, MNEHSlack, and MNEHGreedy. Let σ∗⟵σ.(iii)
Step 2. If τ=0, terminate and return σ∗ as the final solution. Otherwise, let l=0.(iv)
Step 3. Generate a neighborhood solution σ′ of σ by an insertion method.(v)
Step 4. Compute Δ=Tσ′−Tσ. If Δ<0, let σ←σ′ and σ∗←σ. Otherwise, let σ←σ′ with probability e−Δ/τ.(vi)
Step 5. Let l=l+1. If l<L, go to Step 3. Otherwise, τ=τ−α and go to Step 2.For fair comparison, the same maximum completion time is set for SA. LetSA500 and SA1000 be the simulated annealing algorithms in which the maximum CPU times are set to 500n and 1000n, respectively. Here, GA500 and GA1000 are compared with SA500 and SA1000, respectively.The results of comparisons with the SA algorithms are summarized in Table9, which shows the average rate of Algso/maxsol, where Algsol is the objective function value from the current algorithm, and Maxsol=maxGAx,SAx, where x=500 and 1000. Note that because the objective value can be zero, the maximum values are used as the denominator rather than the minimum value to avoid dividing by zero; and if Maxsol is zero, then the rate will be zero. According to this measurement, algorithms with low rate value are better algorithms. As can be seen from Table 9, the proposed GA outperformed a simple SA except for n=50. Additionally, the outperformance is clearer in large-sized problems. Although the devised SA for this test was simple, the effectiveness of the proposed GA is validated from the results.Table 9
Comparison between GA and SA.
nGA500SA500GA1000SA1000200.9660.9830.9660.987500.9070.9080.9260.9031000.8180.9670.8280.9682000.8440.9340.8340.926Finally, to check the effects of due date parameters (T and R) on the performance of GA, convergence rate charts are proposed in Figure 3. For T values, instances generated with large T values converged more quickly in the early generations. That is, when the due dates of jobs are tight, GA can find good solutions in early generations. This result is like that of CPLEX. On the other hand, instances with R=0.5 converged at later generations. That is, when the range of due dates is moderate, GA requires more computation time to find good solutions. According to the results, instances with a moderate range of due dates are more complicated than those of other cases.Figure 3
Convergence rate of GA solutions according to the due date parameters,T and R. (a) Convergence rate according to T values. (b) Convergence rate according to R values.
(a)(b)


## 4.1. Test Instance and Environment

Computational experiments were performed with randomly generated problems to evaluate the performance of the proposed algorithms. All algorithms were coded in Java, and the experiments were performed on a PC with a 3.2 GHz Intel Core i7-8700 CPU.To generate problem instances, job information (processing times, sequence-dependent setup times SDST, and limited waiting times LWT) was generated according to the method presented in [3]. The processing times were generated from U1,50, where Ua,b denotes the discrete uniform distribution with a range a,b. SDST and LWT were generated from U0,50 and U1,100, respectively. The due dates of the jobs were generated from UX1−T−R/2,X1−T+R/2, where X is the lower bound on the makespan, and T and R are the tardiness factor and range of due dates parameters, respectively. Here, to obtain the values of X, we assumed that SDSTs for each job i were set to sij=minsij|∀j and LWTs were infinite; then X is obtained by Johnson’s algorithm [33] that provides the minimum makespan in the typical two-machine flowshop. For the distribution of due dates, three levels for each of T and R were used; that is, T=0.2,0.4,and0.6 and R=0.2,0.5,and0.8.


## 4.2. GA Calibration

The performance of GA significantly depends on its operators and parameters. Hence, a calibration experiment is needed to select the best operators and parameters. The proposed GA has eight operators and parameters, which are listed below, and all possible combinations were evaluated to obtain the best among them.(i)
Selection: two levels (tournament and roulette)(ii)
Crossover: nine levels (OX1, OX2, OBX, PBX, PMX, SJX, SJX2, SBX, and SBX2)(iii)
Mutation: three levels (interchange, insertion, and swap)(iv)
Population sizePsize: three levels 30,50,100(v)
Crossover probabilitypc: six levels 0.2,0.35,0.5,0.65,0.8,0.95(vi)
Mutation probabilitypm: four levels 0.2,0.4,0.6,0.8(vii)
Local searchPl: three levels 5,10,20(viii)
RestartPr: four levels 25,50,75,100For these eight types of operators and parameters, 46,656 different combinations are possible. To simplify the experiment, this test is divided into two experiments. The first experiment was to select the best combination for selection, crossover, and mutation, and the second experiment was to find the best combination for the other parameters.For the evaluation and selection for the GA operators in the first experiment, a full factorial design of selection, crossover, and mutation is considered; hence, 54 different algorithms are tested. The remaining parameters were fixed toPsize,pc,pm,Pl,Pr=50,0.5,0.4,10,50. Additionally, four levels were considered for the number of jobs n=20,50,100and200, and five instances for each combination (T, R, and n) were generated. That is, 180 problem instances were generated. For a termination criterion, the maximum CPU time was set to 30n milliseconds (ms). To compare different GAs for each problem instance, the relative deviation index (RDI) was considered as a measure; RDI is defined as RDUI=Algsol−Minsol/Maxsol−Minsol, where Algsol is the objective function value from the current algorithm, and Minsol and Maxsol are the minimum and maximum values among the objective function values obtained from the algorithms in this comparison, respectively. Particularly when Maxsol=Minsol, RDI will be 0 for all the algorithms.To see the effect of GA operators on the performance, analysis of variance (ANOVA) was performed using SPSS and the ANOVA table is shown in Table2. As can be seen in the table, the performance of the proposed GA was significantly affected by the operators with a significance level of 0.05. According to the F-values, three operators were significantly effective on the RDI. Figure 1 illustrates the main effect plot to find the best operators with lower RDI values. As shown in the figure, roulette, OX2, and insertion showed better performance. This is possibly because the change of fore and rear parts in sequences can lead to searching for better sequences in this scheduling problem with sequence-dependent setup times. For mutation, insertion is observed to be the best, which has been regarded in various flowshop scheduling studies as the best mutation operator [32]. Therefore, roulette, OX2, and insertion were used in the following experiment.Table 2
ANOVA for the effect of GA operators on the performance.
SourcesSum. squaresDFMSFp-valueCorrected model200.087533.77566.464≤0.001Intercept2110.73012110.73037160.094≤0.001Selection9.65819.658170.026≤0.001Crossover35.65784.45778.468≤0.001Mutation116.139258.0701022.336≤0.001Selection × crossover27.60583.45160.749≤0.001Selection × mutation0.58820.2945.1750.006Crossover × mutation7.298160.4568.030≤0.001Selection × crossover × mutation3.143160.1963.458≤0.001Error549.03896660.057––Total2859.8559720–––Corrected total749.1259719–––Significance level = 0.05.Figure 1
Main effect plot of GA operators.The second experiment was performed to find the best combination of parameters of the proposed GA. Considering all levels ofPsize,pc,pm,Pl,Pr, 864 different combinations were evaluated using the same approach as that for the operators. The ANOVA results are summarized in Table 3, which shows that pc, pm, and Pr are the most significant parameters that affect the GA performance. As shown in Figure 2, which illustrates the main effect plot of GA parameters, RDI had the lowest value at each of Psize,pc,pm,Pl,Pr=50,0.35,0.6,5,75, respectively. The bath-curves are observed for all parameters except Pl. That is, both higher and lower values from the selected values yielded worse results, validating the chosen range of values for these parameters in the experiments. For Pl, frequent local searches were more effective when the best solution in the population was not improved. Notably, the probability of mutation is larger than that of crossover. This is probably because a small change by a mutation may lead to a better sequence rather than crossover. That is, because limited waiting time constraints and sequence-dependent setup times were considered in this study, the solution may be improved by small changes in a job sequence. Thus, using the selected parameters, the proposed GA attempts to find better solutions by keeping the sequences in good solutions and making a few changes. In summary, the proposed GA uses roulette, OX2, and insertion for the operators and Psize=50, pc=0.35, pm=0.6, Pl=5, and Pr=75 for the parameters.Table 3
ANOVA for the effect of GA parameters on the performance.
SourcesSum. squaresDFMSFp-valueCorrected model157.1038630.1823.329≤0.001Intercept29023.089129023.089530673.217≤0.001Psize1.62920.81514.897≤0.001pc23.04354.60984.267≤0.001pm40.992313.664249.839≤0.001Pr23.98937.996146.206≤0.001Pl0.19720.0981.8000.165Psize×pc1.070100.1071.9570.034Psize×pm1.58560.2644.831≤0.001Psize×Pr1.92260.3205.859≤0.001Psize×Pl0.52840.1322.4130.047pc×pm12.065150.80414.707≤0.001pc×Pr12.324150.82215.023≤0.001pc×Pl0.752100.0751.3750.185pm×Pr3.82790.4257.774≤0.001pm×Pl0.35560.0591.0830.370Pr×Pl2.80460.4678.544≤0.001Psize×pc×pm1.502300.0500.9160.599Psize×pc×Pr1.334300.0440.8130.754Psize×pc×Pl0.845200.0420.7730.750Psize×pm×Pr0.280180.0160.2850.999Psize×pm×Pl0.454120.0380.6920.761Psize×Pr×Pl5.064120.4227.716≤0.001pc×pm×Pr4.008450.0891.6280.005pc×pm×Pl1.068300.0360.6510.928pc×Pr×Pl0.914300.0300.5570.976pm×Pr×Pl0.676180.0380.6870.828Psize×pc×pm∗Pr2.371900.0260.4821.000Psize×pc∗pm×Pl1.741600.0290.5310.999Psize×pc×Pr×Pl1.798600.0300.5480.998Psize×pm×Pr×Pl1.024360.0280.5200.992pc×pm×Pr×Pl2.236900.0250.4541.000Psize×pc×pm×Pr×Pl4.7041800.0260.4781.000Error8458.3031546560.055——Total37638.495155520———Corrected total8615.406155519———Significance level = 0.05.Figure 2
Main effect plots of GA parameters.


## 4.3. Performance Evaluation

First, the performance of the proposed MILP formulation was evaluated using CPLEX 12.9. To avoid excessive computation times for CPLEX, the maximum CPU time limit was set to 3,600 seconds (s) for each instance. For the evaluation of MILP, four levels for the number of jobsn=5,10,15,and20 were considered, and five instances for each combination of T,R,andns were generated. That is, 36 combinations for T,R,andn were considered, and 180 problem instances are generated. The results are summarized in Table 4, which shows the average computation time (ACPUT) and the number of instances (NI) that failed to find an optimal solution within the computation time limit (3,600 s). As can be seen in the table, CPLEX obtained optimal solutions for all problems up to n=10 but could not find optimal solutions for eight problems with n=15. Furthermore, for n=20, no problems were solved to optimality within the computation time limit.Table 4
Performance of CPLEX.
nACPUTsNI50.080103.220151419.53820360045In general, due dates significantly affect due date-related measures (e.g., total tardiness, which is the objective function of the considered scheduling problem in this study). Hence, the impact of the due dates on the performance of CPLEX was analyzed. The computation times of CPLEX with respect to the due date parametersT,R are summarized in Table 5, when n=15. As can be seen from the table, the performance of CPLEX was significantly affected by the values of T and R. Particularly, when T=0.2and0.4, the instances took a significantly long computation time to be solved. However, when T=0.6, the instances were solved within shorter computation times. That is, CPLEX can solve problems quickly when the due dates of jobs are tight. Regarding the range of due dates R, problems in which due dates of jobs are widely distributed were solved in a shorter computation time.Table 5
Effect of due date parameters on the performance of CPLEX.
TR=0.20.50.8Average0.21435.141580.842313.121776.370.42172.742473.35880.951842.350.6905.23255.19759.17639.86Average1504.371436.461317.751419.53Next, the performances of the proposed list scheduling rules and MNEH algorithms were evaluated by comparison to solutions obtained from CPLEX. Here, letMNEHx be an MNEH algorithm that starts with an initial solution obtained by a list scheduling rule x. Note that, for the instances not solved within the time limit, the solutions terminated at the time limit were compared. Table 6 presents the average gaps between the heuristics and CPLEX, Heusol−CPLEXsol/CPLEXsol, and the number of instances where heuristics found solutions which were equal to or better than those of CPLEX. As can be observed in the table, MEDD and Greedy demonstrated good performance among the list scheduling rules, and MNEHMEDD was the best performing heuristic algorithm. However, the average gaps from CPLEX were too large. These results explain why a metaheuristic algorithm, GA, was needed to find good solutions within a short computation time in this study.Table 6
Performance of the heuristic algorithms (versus CPLEX).
Algorithmn=5101520Avg, sumEDD0.97, 0a2.07, 010.58, 04.52, 04.53, 0MEDD0.30, 91.1, 04.69, 02.03, 02.03, 9Slack0.88, 31.48, 06.17, 02.73, 02.81, 3Greedy0.44, 91.02, 04.39, 02.25, 02.02, 9MNEHEDD0.06, 290.17, 90.71, 00.25, 00.3, 40MNEHMEDD0.05, 310.16, 70.66, 00.26, 20.28, 40MNEHSlack0.04, 320.21, 70.71, 00.3, 10.31, 40MNEHGreedy0.08, 290.28, 11.52, 00.38, 00.56, 31aAverage error gap, number of instances (out of 45 instances) for which the algorithm found solutions better than or equal to those from CPLEX.To evaluate the performance of the suggested GA, a performance evaluation by comparing it with other algorithms was required. However, to the best of our knowledge, there are no algorithms for the same problem considered in this study. Thus, the evaluation was performed by comparing the proposed GA to CPLEX in small-sized problem instances (n = 5, 10, and 15) and the proposed heuristic algorithms in medium- and large-sized problem instances (n=20, 50, 100, and 200). Through these comparisons, the effectiveness of the solutions from the proposed GA was evaluated. In these experiments, the maximum computation times of GA were set to four levels 50n,100n,500n,and1,000nms. Let GAx be the genetic algorithm in which the maximum computation time is set to x⋅nms. The effectiveness of GA solutions compared to those from CPLEX is shown in Table 7. As can be seen from the table, the suggested GA found optimal solutions for almost all problem instances. Particularly, GA outperformed CPLEX for n=20; a minus value means that the objective value of solutions from GA is less than that from CPLEX. This is probably because CPLEX fails to obtain optimal solutions within the maximum CPU time for n=20.Table 7
Evaluation of GA compared to CPLEX.
nGA50GA100GA500GA100050.00, 45a0.00, 450.00, 450.00, 45100.00, 440.00, 450.00, 450.00, 45150.01, 350, 390, 42−0.01, 4320−0.14, 38−0.15, 39−0.17, 41−0.18, 43aAverage error gap, number of instances (out of 45 instances) for which the algorithm found solutions better than or equal to those from CPLEX.For the medium and large problem instances, the GA solutions were compared with those from the MNEH algorithms. The results of this test are summarized in Table8, which shows RDI values and the number of instances where a heuristic finds the best solutions among the heuristic solutions. The table illustrates that GAs outperformed MNEH algorithms, although GAs took longer CPU times. Additionally, in the case where GA50 and MNEHGreedy had similar computation times (approximately 10 s), GA50 still showed better performance. Overall, although GA requires a longer CPU time, GA solves the problems better, and the CPU time of GA50 is also reasonably short.Table 8
Comparison between the proposed heuristic algorithms.
AlgorithmRDICPUTn=20501002002050100200MNEHEDD0.73, 0a0.67, 10.57, 10.55, 0<0.010.030.384.63MNEHMEDD0.72, 00.64, 00.6, 00.96, 0<0.010.040.46.12MNEHSlack0.86, 00.93, 10.97, 00.66, 0<0.010.040.446.12MNEHGreedy0.10, 150.7, 10.66, 00.23, 4<0.010.040.5910.19GA500.07, 230.13, 60.19, 40.17, 412.5510GA1000.05, 270.1, 90.14, 50.15, 4251020GA5000.02, 380.02, 330.05, 130.08, 5102550100GA10000.00, 430.00, 450, 450.00, 452050100200aAverage RDI, number of instances (out of 45 instances) for which the algorithm found solutions better than or equal to those from CPLEX.Additionally, the effectiveness of the proposed GA was evaluated through comparison with a simulated annealing (SA) algorithm, which is also a widely used metaheuristic for various optimization problems. SA attempts to improve an initial solution repeatedly by making small alterations until further improvements cannot be made by such alterations. The SA algorithm can avoid entrapment in a local optimum by allowing occasional uphill moves that deteriorate the objective function value. In this experiment, a simple SA algorithm is devised for comparison with the proposed GA. In this SA algorithm, a neighborhood solutionσ′ of a solution σ is generated using an insertion method, which is reported as the best mutation in the previous experiment. If Δ=Tσ′−Tσ<0, where Tx is the total tardiness of solution x, σ is replaced with σ′. Otherwise, if Δ≥0, the replacement is done with probability e−Δ/τ, where τ is a parameter called the temperature. This replacement procedure is repeated L times at a temperature, where L is called the epoch length, which is set to n2. The temperature is initially set to τ0=100 and decreases gradually by a cooling function, which is set as τx+1=τx−α, where α is a parameter that is set to 0.025 in this algorithm. The algorithm is terminated when the temperature decreases to zero or the computation time reaches the maximum computation time. The procedure of this SA algorithm is summarized below.


### 4.3.1. Procedure: SA

(i)
Step 0. Set initial values for parameters used in the algorithm τ0=100,L=n2andα=0.025. Let τ=τ0 and l=0.(ii)
Step 1. Set an initial solution σ as the best solution among those obtained with MNEHEDD, MNEHMEDD, MNEHSlack, and MNEHGreedy. Let σ∗⟵σ.(iii)
Step 2. If τ=0, terminate and return σ∗ as the final solution. Otherwise, let l=0.(iv)
Step 3. Generate a neighborhood solution σ′ of σ by an insertion method.(v)
Step 4. Compute Δ=Tσ′−Tσ. If Δ<0, let σ←σ′ and σ∗←σ. Otherwise, let σ←σ′ with probability e−Δ/τ.(vi)
Step 5. Let l=l+1. If l<L, go to Step 3. Otherwise, τ=τ−α and go to Step 2.For fair comparison, the same maximum completion time is set for SA. LetSA500 and SA1000 be the simulated annealing algorithms in which the maximum CPU times are set to 500n and 1000n, respectively. Here, GA500 and GA1000 are compared with SA500 and SA1000, respectively.The results of comparisons with the SA algorithms are summarized in Table9, which shows the average rate of Algso/maxsol, where Algsol is the objective function value from the current algorithm, and Maxsol=maxGAx,SAx, where x=500 and 1000. Note that because the objective value can be zero, the maximum values are used as the denominator rather than the minimum value to avoid dividing by zero; and if Maxsol is zero, then the rate will be zero. According to this measurement, algorithms with low rate value are better algorithms. As can be seen from Table 9, the proposed GA outperformed a simple SA except for n=50. Additionally, the outperformance is clearer in large-sized problems. Although the devised SA for this test was simple, the effectiveness of the proposed GA is validated from the results.Table 9
Comparison between GA and SA.
nGA500SA500GA1000SA1000200.9660.9830.9660.987500.9070.9080.9260.9031000.8180.9670.8280.9682000.8440.9340.8340.926Finally, to check the effects of due date parameters (T and R) on the performance of GA, convergence rate charts are proposed in Figure 3. For T values, instances generated with large T values converged more quickly in the early generations. That is, when the due dates of jobs are tight, GA can find good solutions in early generations. This result is like that of CPLEX. On the other hand, instances with R=0.5 converged at later generations. That is, when the range of due dates is moderate, GA requires more computation time to find good solutions. According to the results, instances with a moderate range of due dates are more complicated than those of other cases.Figure 3
Convergence rate of GA solutions according to the due date parameters,T and R. (a) Convergence rate according to T values. (b) Convergence rate according to R values.
(a)(b)


## 4.3.1. Procedure: SA

(i)
Step 0. Set initial values for parameters used in the algorithm τ0=100,L=n2andα=0.025. Let τ=τ0 and l=0.(ii)
Step 1. Set an initial solution σ as the best solution among those obtained with MNEHEDD, MNEHMEDD, MNEHSlack, and MNEHGreedy. Let σ∗⟵σ.(iii)
Step 2. If τ=0, terminate and return σ∗ as the final solution. Otherwise, let l=0.(iv)
Step 3. Generate a neighborhood solution σ′ of σ by an insertion method.(v)
Step 4. Compute Δ=Tσ′−Tσ. If Δ<0, let σ←σ′ and σ∗←σ. Otherwise, let σ←σ′ with probability e−Δ/τ.(vi)
Step 5. Let l=l+1. If l<L, go to Step 3. Otherwise, τ=τ−α and go to Step 2.For fair comparison, the same maximum completion time is set for SA. LetSA500 and SA1000 be the simulated annealing algorithms in which the maximum CPU times are set to 500n and 1000n, respectively. Here, GA500 and GA1000 are compared with SA500 and SA1000, respectively.The results of comparisons with the SA algorithms are summarized in Table9, which shows the average rate of Algso/maxsol, where Algsol is the objective function value from the current algorithm, and Maxsol=maxGAx,SAx, where x=500 and 1000. Note that because the objective value can be zero, the maximum values are used as the denominator rather than the minimum value to avoid dividing by zero; and if Maxsol is zero, then the rate will be zero. According to this measurement, algorithms with low rate value are better algorithms. As can be seen from Table 9, the proposed GA outperformed a simple SA except for n=50. Additionally, the outperformance is clearer in large-sized problems. Although the devised SA for this test was simple, the effectiveness of the proposed GA is validated from the results.Table 9
Comparison between GA and SA.
nGA500SA500GA1000SA1000200.9660.9830.9660.987500.9070.9080.9260.9031000.8180.9670.8280.9682000.8440.9340.8340.926Finally, to check the effects of due date parameters (T and R) on the performance of GA, convergence rate charts are proposed in Figure 3. For T values, instances generated with large T values converged more quickly in the early generations. That is, when the due dates of jobs are tight, GA can find good solutions in early generations. This result is like that of CPLEX. On the other hand, instances with R=0.5 converged at later generations. That is, when the range of due dates is moderate, GA requires more computation time to find good solutions. According to the results, instances with a moderate range of due dates are more complicated than those of other cases.Figure 3
Convergence rate of GA solutions according to the due date parameters,T and R. (a) Convergence rate according to T values. (b) Convergence rate according to R values.
(a)(b)


## 5. Conclusion

In this study, we considered a two-machine flowshop scheduling problem with limited waiting time constraints and sequence-dependent setup times, which is very important in semiconductor manufacturing systems. A mixed-integer programming formulation is provided to describe the considered problem clearly and used to obtain optimal solutions with CPLEX. However, CPLEX could not obtain optimal solutions whenn=20 because the considered problem is NP-complete. Thus, to obtain good solutions in a short computation time, three types of heuristic algorithms were proposed: list scheduling methods, a constructive heuristic algorithm, and a genetic algorithm (GA). To find the best combination of the GA, 46,656 different combinations were evaluated, and the suggested GA outperformed the other heuristics. Additionally, GA found optimal solutions for all instances with n=5, 10, and 15 and showed better performance compared to CPLEX when n=20. Thus, it can be said that GA works well to obtain acceptable solutions within a reasonably short computation time.Although the limited waiting time constraint and sequence-dependent setup times are very important characteristics in semiconductor manufacturing systems, there are only a few studies considering both characteristics together. Thus, we need to develop more effective and efficient methodologies including many types of metaheuristics. On the other hand, since it is very difficult to find optimal solutions for the considered problem, it is necessary to develop effective lower bounding strategies to evaluate solutions obtained by heuristic algorithms. Also, different waiting time constraints like overlapping waiting time constraints in [23] can be considered in the future research. Finally, since the problem considered in this study is a simple type of flowshop, this problem can be extended to more practical flowshops like hybrid flowshops in which there are parallel machines in each stage.



---

*Source: 8833645-2020-11-24.xml*