# Clustering and Genetic Algorithm Based Hybrid Flowshop Scheduling with Multiple Operations

Authors: Yingfeng Zhang; Sichao Liu; Shudong Sun
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

This research is motivated by a flowshop scheduling problem of our collaborative manufacturing company for aeronautic products. The heat-treatment stage (HTS) and precision forging stage (PFS) of the case are selected as a two-stage hybrid flowshop system. In HTS, there are four parallel machines and each machine can process a batch of jobs simultaneously. In PFS, there are two machines. Each machine can install any module of the four modules for processing the workpeices with different sizes. The problem is characterized by many constraints, such as batching operation, blocking environment, and setup time and working time limitations of modules, and so forth. In order to deal with the above special characteristics, the clustering and genetic algorithm is used to calculate the good solution for the two-stage hybrid flowshop problem. The clustering is used to group the jobs according to the processing ranges of the different modules of PFS. The genetic algorithm is used to schedule the optimal sequence of the grouped jobs for the HTS and PFS. Finally, a case study is used to demonstrate the efficiency and effectiveness of the designed genetic algorithm.


---

## Body

## 1. Introduction

This research is motivated by a flowshop scheduling problem of our collaborative manufacturing company for aeronautic product. This company is composed of a set of multiple stages with each stage having parallel machines. According to our investigation, precision forging stage is the bottleneck because it has many WIP (work in progress) stock at different times. Therefore, we focus mainly on the scheduling method of this stage and its previous stage (heat-treatment).The heat-treatment stage (HTS) combined with the precision forging stage (PFS) forms a two-stage hybrid flowshop system. Figure1 describes the details of these two stages. As seen in Figure 1, the HTS has four parallel machines and the PFS has two parallel machines. The HTS can process five workpieces at one machine simultaneously, while the PFS can process one workpiece at one time. In PFS, four modules are used to process the different workpieces with different sizes, and the setup time and working time of each module have an effect on the efficiency of PFS. As a result, in PFS of collaborative company, the phenomenon that most of the modules’ working time deviate their nominal working time often occurs. In addition, there are many WIP blocked for PFS because the multiple workpieces with different sizes can be simultaneously processed in each machine of HTS.Figure 1
Two-stage hybrid flowshop scheduling within collaborating company.In contrast to general hybrid flowshop scheduling, some characteristics which emerged in this industrial case have substantiated the complexity of the problem. It is summarized as follows.(1) In HTS, there are four parallel machines. Each machine can process a batch of jobs simultaneously. The method of loading job into these machines is unusual. It follows the principle that a new job can be loaded when one job is released. For each machine, only all the jobs which are loaded into the machine can be processed. It means that the start time of the batch of jobs is the loading time of the last loaded job of the machine. In this case, the capacity of each machine is five.(2) In PFS of this case, there are two machines. Each machine can install any module of the four modules for processing the workpieces with different sizes, and the setup time and working time of each module should be considered. Each module has a processing range and can be reused. The workpieces with different sizes can be dealt with under the processing range of the module. But for each module, it should not be continuously used exceeding its working time at one time. Therefore, it is better to make all the modules could be used near to their working time at each time and try to avoid the setup of modules at the two machines simultaneously.(3) In a general flowshop problem, buffers can be used to store jobs for waiting for the next process. However, in this case, the released jobs from HTS should be immediately transported to PFS because the workpieces will be affected with a large temperature difference. If PFS is not ready for a new job, the jobs must be blocked inside the machines although it is finished.In order to deal with the above special characteristics, in this paper, the clustering and genetic algorithm is designed to calculate the good solution for this two-stage hybrid flowshop problem. The clustering is used to group the jobs according to the processing ranges of the different modules of PFS. The genetic algorithm is used to schedule the optimal sequence of the grouped jobs for the HTS and PFS. The research will improve the productivity for the manufacturing companies with these two-stage hybrid flowshop problems.The rest of this paper is organized as follows. Section2 reviews the relevant literature. The mathematical model of the two-stage hybrid flowshop problem is established in Section 3. Section 4 presents analysis on the clustering algorithm of jobs. A case study which is used to demonstrate the efficiency and effectiveness of the designed genetic algorithm is proposed in Section 5. Finally, conclusions and recommendations for future work are summarized in Section 6.


## 2. Literature Review

Early researches majorly focused on mathematical methodologies and solution algorithms. Rahendran and Chaudhuri [1] propose a multistage parallel-processor flowshop problem with minimum flowtime. Based a hybrid three-stage flowshop problem, Riane et al. [2] propose an efficient heuristics to minimize makespan and branch and bound crossed with GA to solve hybrid flowshops. According to the literature about hybrid flow shop scheduling problems, Linn and Zhang [3] make a comprehensive survey. With the rapid development of information technology, computer technology and integrated manufacturing system, multi-processor task scheduling has come into focus. Oǧuz et al. [4] propose the concept of hybrid flowshop scheduling problems with multiprocessor task systems; for multiprocessor task scheduling in multistage hybrid flowshops, Ying and Lin [5] present an ant colony system approach. Alaykýran et al. [6] make in-depth research under the ant colony system approach and use an optimal ant colony algorithm to solve hybrid flow shop scheduling problems. Luo et al. [7] investigate a two-stage hybrid flowshop scheduling problem in a metal-working company and develop a genetic algorithm to obtain a near-optimal solution.The optimal algorithm for hybrid flowshop scheduling is always a difficulty. Taking into account complexity and efficiency of algorithm, many methods have been applied in the solution of hybrid flowshop scheduling problems. At early phase, Maccarthy and Liu [8], addressing the gap in scheduling research, made a review of optimization of heuristic methods in production scheduling. Chen [9] describes analysis of classes of heuristics for scheduling a two-stage flow shop with parallel machines at one stage. Wang and Zheng [10] present an effective hybrid heuristics for flow shop scheduling. Laha and Chakraborty [11] analyze the optimal methods based on the construction search. According to the real life, Rossi et al. [12] apply heuristics for scheduling a two-stage hybrid flowshop with parallel batching machines at a hospital sterilisation plant.Two scheduling situations are named no-wait and blocking scheduling when there are no buffer storages between stages. In no-wait scheduling (NWS), jobs must be processed from start to finish without any interruption either on or between machines. In blocking scheduling (BS), a job completed at a machine must wait there until the next machine gets ready. These problems are usual in various industries such as smart factory, high technology industry, and chemical processing industry and have taken substantial research attention. Cheng et al. [13] present a genetic algorithm for the multistage and parallel-machine scheduling problem with job splitting-A case study for the solar cell industry. Sirskandarajah [14] describes the performance of scheduling algorithms for no-wait flowshop with parallel machines. Caraffa et al. [15] use the genetic algorithm to search the minimum makespan in a blocking flowshop. Ruiz and Allahverdi [16] study no-wait flowshop with separate setup times to minimize maximum lateness. Liu et al. [17] propose an effective hybrid particle swarm optimization for no-wait flowshop scheduling; this hybrid particle swarm optimization has been verified, that is, a high-efficiency method. Combining with the blocking and no-wait scheduling together, Mascis and Pacciarelli [18] discuss the job-shop scheduling with blocking and no-wait constraints; survey indicates that the blocking scheduling and no-wait are paradoxical things. Luo et al. [19] study a hybrid flowshop scheduling with batch-discrete processors and machine maintenance in time windows.Although significant progress has been made in above researches, it is difficult to directly apply the relevant model and method to this case because of the characteristics described in Section1. Considering the problems faced in this case, the clustering model and genetic algorithm will be combined to solve this problem.


## 3. Mathematical Model

According to the two-stage (HTS and PFS) hybrid flowshop scheduling problem described in Section1, a mathematical model should be constructed in order to conduct further studies.Notations used through this paper are listed in notations section.Based on the notations, the mathematical scheduling model is formulated as follows:objective function(1)
E
=
Max
⁡
(
β
1
×
η
1
+
β
2
×
η
2
)
,
22
.
2
β
2
>
β
1
,
β
1
+
β
2
=
1
,
.
where,
(2)
η
1
=
∑
1
m
∑
1
i
P
i
m
∑
1
m
∑
1
i
P
i
m
+
∑
1
m
∑
1
i
B
i
m
,
η
2
=
∑
k
∑
i
(
ϖ
i
,
α
k
+
θ
i
,
α
k
)
∑
k
∑
i
(
ϖ
i
,
α
k
+
θ
i
,
α
k
)
+
∑
n
R
j
.As seen in (1), E is the efficiency of the two-stage hybrid flowshop scheduling problem. η
1 and η
2 represent the efficiency of HTS and PFS, respectively. β
1 and β
2 are the weighting factors of HTS and FPS; we set β
1
=
0.1 and β
2
=
0.9 because the FPS is the bottleneck. In η
1, ∑
1
m
∑
1
i
P
i
m is the total processing time of G
J and ∑
1
m
∑
1
i
B
i
m is the total blocking of the jobs in the HTS. In η
2, ∑
k
∑
i
(
ϖ
i
,
α
k
+
θ
i
,
α
k
) is the total processing time of the two machines, ∑
n
R
j is total waiting time in the PFS.Constraints of this problem are(3)
P
m
=
max
⁡
i
{
P
i
m
}
,
B
m
=
min
⁡
i
{
B
i
m
}
,
(4)
F
i
g
j
-
S
i
g
j
≥
P
m
,
if
B
m
=
0
,
inequality
is
“
=
”
,
(5)
S
i
+
1
,
α
λ
k
-
F
i
,
α
λ
k
≥
θ
i
,
α
k
,
(6)
∑
λ
V
i
,
α
λ
k
≤
ϖ
i
,
α
k
,
where functions (3) and (4) are the constraints of HTS, where P
m is the processing time constraint of each g
j
m, B
m is the blocking time constraint of each g
j
m. Functions (5) and (6) are the constraints of FPS; they are used to guarantee that each module has enough setup time and that each module does not work exceeding its nominal working time at each time of use.


## 4. Clustering and GA-Based Scheduling Method

### 4.1. Clustering Model

The clustering model is used to classify all jobs into multiple groups of size “c” according to the similarity of job parameters. In order to make the grouped jobs more significant for the next step—GA design, it is essential to analyze the importance of the parameters of the jobs.Two important parameters should be considered. The first is the size of the workpieces. The second is the processing time of the job in HTS.Let setV
s
=
{
v
1
,
v
2
,
…
,
v
m
} be the different values of size range according to the modules processing range of PFS.Let setV
PT
=
{
v
1
,
v
2
,
…
,
v
n
} be the different values of processing time of all the jobs.For each size ofV
s, each different value is a split node. The jobs firstly are classed into several groups at each value of v
i. Then, these grouped jobs are further grouped according to the value of V
PT.For the different processing time of each job, a cluster model is designed as follows.Step  1. Let G
=
{
g
1
,
g
2
,
…
,
g
g
} records each group (g
i) after the jobs are classed by all the values V
s
=
{
v
1
,
v
2
,
…
,
v
m
}, respectively. For each g
i, g
i
∈
G, it means there are “g” (the size of g
i) jobs in this group with the different processing time parameters.Step  2. Use a dynamic set G
J
i to record the result of the subgroups of g
i; the size of G
J
i is zero at the beginning.Step  2.1. Reclass the jobs of g
i using processing time parameters V
PT
=
{
v
1
,
v
2
,
…
,
v
n
} by means of the same method of size parameter in V
s.Step  2.2. Let T
G
i
=
{
t
g
1
i
,
t
g
2
i
,
…
,
t
g
t
i
} be a temp array to record each new group (t
g
t
i) of group g
i after being reclassed by different values of processing time {
g
p
1
…
,
g
p
g
}. For each t
g
t
i, rules should be obeyed to regroup the size of t
g
t
i. The rules can be seen in Table 1. Here, s is the size of t
g
t
i and c is a constant value of jobs that need to be simultaneously processed in the same machine.Table 1
The rules of regroup.
Condition
Regroup rules
s
≤
c
Thet
g
t
i is dynamically added to G
J
i
s
>
c
Use the operator of division to divide the size oft
g
t
i by c, and let a be the aliquot part and b the remainder. If b is equal to zero, the t
g
t
i will be decomposed into “a” groups and each group has “c” jobs. If b is not equal to zero, the t
g
t
i will be decomposed into “a” groups and another group consists of “b” jobs. The groups created during this process are also dynamically added to G
J
i.After the above steps,G
J
i consisted of many small groups and each group consists of “c” jobs according to the size and processing time parameters. Then, the formed G
J
i is ready for GA-based scheduling.


### 4.2. GA-Based Scheduling Method

The flows of designed GA-based scheduling method follow the standard flows of genetic algorithm. It includes the following main parts.


#### 4.2.1. Gene and Chromosome

As described in Section4.1, the “n” jobs have been grouped with the same size caccording to the size and processing time parameters. Therefore, the matrix G
J
=
{
g
j
1
,
g
j
i
,
…
,
g
j
m
} will be the important information to design genes.An integer-based method is used to form the genes and chromosomes. The genes consist of a pair of integers like (i-j), 1
≤
i
≤
m, 1
≤
j
≤
4; here m is the length of the set G
J and j is the corresponding module of PFS. Obviously, each gene includes a group with “c” jobs formed in clustering stage and the corresponding module used in PFS.Based on genes, the chromosome can be defined as a queue that consists of different genes and char “:”. The length of the chromosome is the sum of the different genes. And it is decided by the length of setG
J. For example, chromosome (1-2:3-3:2-1:5-4:6-1) consists of five genes and its length is five.


#### 4.2.2. Decoding Scheme

The decoding scheme is also designed according to the gene and chromosome. And the purpose is to interpret the meaning of the chromosome. The char “:” which appeared in chromosome is to connect the genes, and the integer (i-j) which appeared in chromosome presents a group (g
j
i) of jobs which is defined in G
J. The appearing order of i of (i-j) presents the processing order of each group (g
j
i) and will use the module “j” in the next stage. For example, the chromosome (1-2:3-3:2-1:5-4:6-1) means that there are five groups ({
g
j
1
,
g
j
3
,
g
j
2
,
g
j
5
,
g
j
6
}) of jobs which will be processed by {
m
2
,
m
3
,
m
1
,
m
4
,
m
1
}.


#### 4.2.3. Fitness Function

Fitness function is used to calculate the value of each individual in order to determine the performance of chromosomes of the entire population. In this case, the objective function (1) is used to be the fitness function to evaluate the chromosome.


#### 4.2.4. Design of Selection, Crossover, and Mutation Operators

Selection operator is used to select the optimal parents according to the fitness for generating new offspring.Crossover operator is used as main genetic operator and the performance depends on it. In this case, a multipoint crossover operator is designed to permute the job order as well as keep the legality of the generated chromosome.The proposed crossover operator takes two parents and creates two offsprings. It propagates the structure and subschedule into offspring from one parent. And then it completes the offspring with remaining jobs derived from another parent. The detailed steps can be seen in Algorithm1.Algorithm 1:Steps of crossover operator with multi-point.
Step  1.   Create two crossover points to form crossover-section.
Randomly select two parentsi and j.
Randomly create two integratea and b
,
a
<
b
;
a
,
b
∈
[
1
,
m
]
The genes froma to b of parentsi andjare the crossover-sections.
String
[
]
tempI= The genes from the ath to bth of the parent “i”
String[
]
tempJ= The genes from the ath to bth of the parent “j”
Step  2.   Use symbol “0” to replace the genes.
Find the genes oftempI in parent “j”
Use “0” to replace the genes of the parent “i”
String[
]
tempI0 = The new parent “i” with “0”
Find the genes oftempJ in parent “i”
Use “0” to replace the genes of the parent “j”
String[
]
tempJ0= The new parent “j” with “0”
Step  3.   Make “0” move to the crossover-section
FOR each new parent (tempI0; tempJ0) DO
Make the symbols “0” move from the both extremities to centre
until they reach the cross-section, namely froma to b
END FOR
String[
]
tempI1 = The new parent “i” with centre “0” from a to b
String[
]
tempJ1 = The new parent “j” with centre “0” from atob
Step  4.   Create new parents
Use tempJ to replace of the “0” froma to b of temI1
String[
]
parentI = new formed temI1
Use tempI to replace of the “0” froma to b of temJ1
String[
]
parentJ = new formed temJ1
Outputs: String [
]
parentI; parentJMutation operator just works on a single chromosome and generates offspring by altering one or more genes.In this research, mutation uses the replaced genes derived from the same chromosome. It is widely applied to general genetic algorithms. Compared to crossover operator, it may be simple. Firstly, choose one chromosome for mutation. Then, two random positions of the chosen chromosome are selected and then replace their genes. For example, assume the parent is (1-2:3-3:2-1:5-4:6-1:8-2:7-3:10-4); two mutation positions (i.e., 2, 6) are chosen randomly. Then replace the genes (i.e., 3-3, 8-2) in selected positions and get the offspring, namely, (1-2:8-2:2-1:5-4:6-1:3-3:7-3:10-4).


## 4.1. Clustering Model

The clustering model is used to classify all jobs into multiple groups of size “c” according to the similarity of job parameters. In order to make the grouped jobs more significant for the next step—GA design, it is essential to analyze the importance of the parameters of the jobs.Two important parameters should be considered. The first is the size of the workpieces. The second is the processing time of the job in HTS.Let setV
s
=
{
v
1
,
v
2
,
…
,
v
m
} be the different values of size range according to the modules processing range of PFS.Let setV
PT
=
{
v
1
,
v
2
,
…
,
v
n
} be the different values of processing time of all the jobs.For each size ofV
s, each different value is a split node. The jobs firstly are classed into several groups at each value of v
i. Then, these grouped jobs are further grouped according to the value of V
PT.For the different processing time of each job, a cluster model is designed as follows.Step  1. Let G
=
{
g
1
,
g
2
,
…
,
g
g
} records each group (g
i) after the jobs are classed by all the values V
s
=
{
v
1
,
v
2
,
…
,
v
m
}, respectively. For each g
i, g
i
∈
G, it means there are “g” (the size of g
i) jobs in this group with the different processing time parameters.Step  2. Use a dynamic set G
J
i to record the result of the subgroups of g
i; the size of G
J
i is zero at the beginning.Step  2.1. Reclass the jobs of g
i using processing time parameters V
PT
=
{
v
1
,
v
2
,
…
,
v
n
} by means of the same method of size parameter in V
s.Step  2.2. Let T
G
i
=
{
t
g
1
i
,
t
g
2
i
,
…
,
t
g
t
i
} be a temp array to record each new group (t
g
t
i) of group g
i after being reclassed by different values of processing time {
g
p
1
…
,
g
p
g
}. For each t
g
t
i, rules should be obeyed to regroup the size of t
g
t
i. The rules can be seen in Table 1. Here, s is the size of t
g
t
i and c is a constant value of jobs that need to be simultaneously processed in the same machine.Table 1
The rules of regroup.
Condition
Regroup rules
s
≤
c
Thet
g
t
i is dynamically added to G
J
i
s
>
c
Use the operator of division to divide the size oft
g
t
i by c, and let a be the aliquot part and b the remainder. If b is equal to zero, the t
g
t
i will be decomposed into “a” groups and each group has “c” jobs. If b is not equal to zero, the t
g
t
i will be decomposed into “a” groups and another group consists of “b” jobs. The groups created during this process are also dynamically added to G
J
i.After the above steps,G
J
i consisted of many small groups and each group consists of “c” jobs according to the size and processing time parameters. Then, the formed G
J
i is ready for GA-based scheduling.


## 4.2. GA-Based Scheduling Method

The flows of designed GA-based scheduling method follow the standard flows of genetic algorithm. It includes the following main parts.


### 4.2.1. Gene and Chromosome

As described in Section4.1, the “n” jobs have been grouped with the same size caccording to the size and processing time parameters. Therefore, the matrix G
J
=
{
g
j
1
,
g
j
i
,
…
,
g
j
m
} will be the important information to design genes.An integer-based method is used to form the genes and chromosomes. The genes consist of a pair of integers like (i-j), 1
≤
i
≤
m, 1
≤
j
≤
4; here m is the length of the set G
J and j is the corresponding module of PFS. Obviously, each gene includes a group with “c” jobs formed in clustering stage and the corresponding module used in PFS.Based on genes, the chromosome can be defined as a queue that consists of different genes and char “:”. The length of the chromosome is the sum of the different genes. And it is decided by the length of setG
J. For example, chromosome (1-2:3-3:2-1:5-4:6-1) consists of five genes and its length is five.


### 4.2.2. Decoding Scheme

The decoding scheme is also designed according to the gene and chromosome. And the purpose is to interpret the meaning of the chromosome. The char “:” which appeared in chromosome is to connect the genes, and the integer (i-j) which appeared in chromosome presents a group (g
j
i) of jobs which is defined in G
J. The appearing order of i of (i-j) presents the processing order of each group (g
j
i) and will use the module “j” in the next stage. For example, the chromosome (1-2:3-3:2-1:5-4:6-1) means that there are five groups ({
g
j
1
,
g
j
3
,
g
j
2
,
g
j
5
,
g
j
6
}) of jobs which will be processed by {
m
2
,
m
3
,
m
1
,
m
4
,
m
1
}.


### 4.2.3. Fitness Function

Fitness function is used to calculate the value of each individual in order to determine the performance of chromosomes of the entire population. In this case, the objective function (1) is used to be the fitness function to evaluate the chromosome.


### 4.2.4. Design of Selection, Crossover, and Mutation Operators

Selection operator is used to select the optimal parents according to the fitness for generating new offspring.Crossover operator is used as main genetic operator and the performance depends on it. In this case, a multipoint crossover operator is designed to permute the job order as well as keep the legality of the generated chromosome.The proposed crossover operator takes two parents and creates two offsprings. It propagates the structure and subschedule into offspring from one parent. And then it completes the offspring with remaining jobs derived from another parent. The detailed steps can be seen in Algorithm1.Algorithm 1:Steps of crossover operator with multi-point.
Step  1.   Create two crossover points to form crossover-section.
Randomly select two parentsi and j.
Randomly create two integratea and b
,
a
<
b
;
a
,
b
∈
[
1
,
m
]
The genes froma to b of parentsi andjare the crossover-sections.
String
[
]
tempI= The genes from the ath to bth of the parent “i”
String[
]
tempJ= The genes from the ath to bth of the parent “j”
Step  2.   Use symbol “0” to replace the genes.
Find the genes oftempI in parent “j”
Use “0” to replace the genes of the parent “i”
String[
]
tempI0 = The new parent “i” with “0”
Find the genes oftempJ in parent “i”
Use “0” to replace the genes of the parent “j”
String[
]
tempJ0= The new parent “j” with “0”
Step  3.   Make “0” move to the crossover-section
FOR each new parent (tempI0; tempJ0) DO
Make the symbols “0” move from the both extremities to centre
until they reach the cross-section, namely froma to b
END FOR
String[
]
tempI1 = The new parent “i” with centre “0” from a to b
String[
]
tempJ1 = The new parent “j” with centre “0” from atob
Step  4.   Create new parents
Use tempJ to replace of the “0” froma to b of temI1
String[
]
parentI = new formed temI1
Use tempI to replace of the “0” froma to b of temJ1
String[
]
parentJ = new formed temJ1
Outputs: String [
]
parentI; parentJMutation operator just works on a single chromosome and generates offspring by altering one or more genes.In this research, mutation uses the replaced genes derived from the same chromosome. It is widely applied to general genetic algorithms. Compared to crossover operator, it may be simple. Firstly, choose one chromosome for mutation. Then, two random positions of the chosen chromosome are selected and then replace their genes. For example, assume the parent is (1-2:3-3:2-1:5-4:6-1:8-2:7-3:10-4); two mutation positions (i.e., 2, 6) are chosen randomly. Then replace the genes (i.e., 3-3, 8-2) in selected positions and get the offspring, namely, (1-2:8-2:2-1:5-4:6-1:3-3:7-3:10-4).


## 4.2.1. Gene and Chromosome

As described in Section4.1, the “n” jobs have been grouped with the same size caccording to the size and processing time parameters. Therefore, the matrix G
J
=
{
g
j
1
,
g
j
i
,
…
,
g
j
m
} will be the important information to design genes.An integer-based method is used to form the genes and chromosomes. The genes consist of a pair of integers like (i-j), 1
≤
i
≤
m, 1
≤
j
≤
4; here m is the length of the set G
J and j is the corresponding module of PFS. Obviously, each gene includes a group with “c” jobs formed in clustering stage and the corresponding module used in PFS.Based on genes, the chromosome can be defined as a queue that consists of different genes and char “:”. The length of the chromosome is the sum of the different genes. And it is decided by the length of setG
J. For example, chromosome (1-2:3-3:2-1:5-4:6-1) consists of five genes and its length is five.


## 4.2.2. Decoding Scheme

The decoding scheme is also designed according to the gene and chromosome. And the purpose is to interpret the meaning of the chromosome. The char “:” which appeared in chromosome is to connect the genes, and the integer (i-j) which appeared in chromosome presents a group (g
j
i) of jobs which is defined in G
J. The appearing order of i of (i-j) presents the processing order of each group (g
j
i) and will use the module “j” in the next stage. For example, the chromosome (1-2:3-3:2-1:5-4:6-1) means that there are five groups ({
g
j
1
,
g
j
3
,
g
j
2
,
g
j
5
,
g
j
6
}) of jobs which will be processed by {
m
2
,
m
3
,
m
1
,
m
4
,
m
1
}.


## 4.2.3. Fitness Function

Fitness function is used to calculate the value of each individual in order to determine the performance of chromosomes of the entire population. In this case, the objective function (1) is used to be the fitness function to evaluate the chromosome.


## 4.2.4. Design of Selection, Crossover, and Mutation Operators

Selection operator is used to select the optimal parents according to the fitness for generating new offspring.Crossover operator is used as main genetic operator and the performance depends on it. In this case, a multipoint crossover operator is designed to permute the job order as well as keep the legality of the generated chromosome.The proposed crossover operator takes two parents and creates two offsprings. It propagates the structure and subschedule into offspring from one parent. And then it completes the offspring with remaining jobs derived from another parent. The detailed steps can be seen in Algorithm1.Algorithm 1:Steps of crossover operator with multi-point.
Step  1.   Create two crossover points to form crossover-section.
Randomly select two parentsi and j.
Randomly create two integratea and b
,
a
<
b
;
a
,
b
∈
[
1
,
m
]
The genes froma to b of parentsi andjare the crossover-sections.
String
[
]
tempI= The genes from the ath to bth of the parent “i”
String[
]
tempJ= The genes from the ath to bth of the parent “j”
Step  2.   Use symbol “0” to replace the genes.
Find the genes oftempI in parent “j”
Use “0” to replace the genes of the parent “i”
String[
]
tempI0 = The new parent “i” with “0”
Find the genes oftempJ in parent “i”
Use “0” to replace the genes of the parent “j”
String[
]
tempJ0= The new parent “j” with “0”
Step  3.   Make “0” move to the crossover-section
FOR each new parent (tempI0; tempJ0) DO
Make the symbols “0” move from the both extremities to centre
until they reach the cross-section, namely froma to b
END FOR
String[
]
tempI1 = The new parent “i” with centre “0” from a to b
String[
]
tempJ1 = The new parent “j” with centre “0” from atob
Step  4.   Create new parents
Use tempJ to replace of the “0” froma to b of temI1
String[
]
parentI = new formed temI1
Use tempI to replace of the “0” froma to b of temJ1
String[
]
parentJ = new formed temJ1
Outputs: String [
]
parentI; parentJMutation operator just works on a single chromosome and generates offspring by altering one or more genes.In this research, mutation uses the replaced genes derived from the same chromosome. It is widely applied to general genetic algorithms. Compared to crossover operator, it may be simple. Firstly, choose one chromosome for mutation. Then, two random positions of the chosen chromosome are selected and then replace their genes. For example, assume the parent is (1-2:3-3:2-1:5-4:6-1:8-2:7-3:10-4); two mutation positions (i.e., 2, 6) are chosen randomly. Then replace the genes (i.e., 3-3, 8-2) in selected positions and get the offspring, namely, (1-2:8-2:2-1:5-4:6-1:3-3:7-3:10-4).


## 5. Case Study

Two hundred jobs are selected to simulate the problems of the collaborative company and verify the effectiveness of the designed clustering and GA method. Table2 shows the parameters of the four models. Table 3 shows the information of the jobs (j
n), where the columns size and processing time are the initial data of the jobs, and the blocking time and waiting time are the calculated data according to the optimal solution gotten by the designed algorithm.Table 2
Parameters of the modules.
Module type
Processing range (cm)
Notational processing time (min)
Setup time (min)
Module 1
(30, 40)
300
20
Module 2
(40, 50)
280
20
Module 3
(50, 60)
270
40
Module 4
(60, 70)
260
40Table 3
Data of jobs.
j
n
Size (cm)
Processing time (min)
Blocking time (min)
Waiting time (min)
j
1
31
39
0
0
j
2
63
21
9
7
j
3
69
15
7
6
⋮
⋮
⋮
⋮
⋮
j
50
40
35
3
1
⋮
⋮
⋮
⋮
⋮
j
100
51
29
5
7
⋮
⋮
⋮
⋮
⋮
j
150
67
17
4
3
⋮
⋮
⋮
⋮
⋮
j
199
37
33
4
2
j
200
42
37
4
1Table4 shows the information of grouped jobs in HTS, where size range and processing time are the values of each group jobs (g
j
m), blocking time is the minimum blocking time of all the jobs in this group, and η
1 means the efficiency of HTS; it is calculated by
(7)
η
1
=
∑
1
m
∑
1
i
P
i
m
∑
1
m
∑
1
i
P
i
m
+
∑
1
m
∑
1
i
B
i
m
.Table 4
Data of grouped jobs in HTS.
G
J
Range of sizes (cm)
Processing time (min)
Blocking time (min)
η
1
g
j
1
30-31
40
0
88.31%
g
j
2
31-32
39
0
g
j
3
32-33
38
2
g
j
4
33-34
37
4
g
j
5
34-35
36
2
g
j
6
35-36
35
3
g
j
7
36-37
34
4
g
j
8
37-38
33
4
g
j
9
38-39
32
5
g
j
10
39-40
31
6
g
j
11
40-41
35
3
g
j
12
41-42
34
5
g
j
13
42-43
33
4
g
j
14
43-44
32
5
g
j
15
44-45
31
1
g
j
16
45-46
30
2
g
j
17
46-47
29
3
g
j
18
47-48
28
6
g
j
19
48-49
27
7
g
j
20
49-50
26
8
g
j
21
50-51
30
5
g
j
22
51-52
29
6
g
j
23
52-53
28
3
g
j
24
53-54
27
4
g
j
25
54-55
26
2
g
j
26
55-56
25
3
g
j
27
56-57
24
4
g
j
28
57-58
23
0
g
j
29
58-59
22
0
g
j
30
59-60
21
0
g
j
31
60-61
24
3
g
j
32
61-62
23
4
g
j
33
62-63
22
8
g
j
34
63-64
21
9
g
j
35
64-65
20
7
g
j
36
65-66
19
2
g
j
37
66-67
18
3
g
j
38
67-68
17
4
g
j
39
68-69
16
5
g
j
40
69-70
15
7Table5 shows the information of grouped jobs in PFS, where size range and processing time are the values of each group jobs (g
j
m); waiting time is actual waiting time of all the jobs in this group. Table 6 shows the scheduling result of the four modules in PFS, where ϖ
i
,
α
k is working time of Model α in machine (k), θ
i
,
α
k is the setup time of Model α in machine (k), i means the ith loading, and R
j is wait time of the machine j, which is equal the sum of waiting time of jobs in this machine minus the setup time of this machine. The efficiency of PFS is calculated by
(8)
η
2
=
∑
k
∑
i
(
ϖ
i
,
α
k
+
θ
i
,
α
k
)
∑
k
∑
i
(
ϖ
i
,
α
k
+
θ
i
,
α
k
)
+
∑
n
R
j
.Table 5
Data of grouped jobs in PFS.
G
J
Range of sizes (cm)
Processing time (min)
Waiting time (min)
g
j
1
30-31
30
0
g
j
2
31-32
27
0
g
j
3
32-33
25
3
g
j
4
33-34
23
4
g
j
5
34-35
21
1
g
j
6
35-36
19
2
g
j
7
36-37
17
2
g
j
8
37-38
16
2
g
j
9
38-39
15
3
g
j
10
39-40
13
5
g
j
11
40-41
29
1
g
j
12
41-42
26
3
g
j
13
42-43
24
1
g
j
14
43-44
22
3
g
j
15
44-45
20
0
g
j
16
45-46
18
0
g
j
17
46-47
16
0
g
j
18
47-48
15
2
g
j
19
48-49
14
4
g
j
20
49-50
12
5
g
j
21
50-51
28
6
g
j
22
51-52
26
7
g
j
23
52-53
23
5
g
j
24
53-54
21
6
g
j
25
54-55
19
2
g
j
26
55-56
17
3
g
j
27
56-57
16
4
g
j
28
57-58
15
0
g
j
29
58-59
13
0
g
j
30
59-60
11
0
g
j
31
60-61
27
4
g
j
32
61-62
25
6
g
j
33
62-63
23
5
g
j
34
63-64
21
7
g
j
35
64-65
19
0
g
j
36
65-66
17
0
g
j
37
66-67
16
0
g
j
38
67-68
14
3
g
j
39
68-69
12
4
g
j
40
69-70
11
6Table 6
Scheduling result of modules in PFS.
ϖ
1
,
α
1
ϖ
2
,
α
1
ϖ
1
,
α
2
ϖ
2
,
α
2
θ
1
,
α
1
θ
2
,
α
1
θ
1
,
α
2
θ
2
,
α
2
R
1
R
2
η
2
1
285
240
285
220
20
20
20
0
95
115
95.34%
2
275
275
230
205
20
20
20
20
3
190
270
260
220
40
0
40
40
4
185
220
260
260
40
40
40
40The result shows that the two stages have good efficiency. The efficiency of HTS is 88.31% and the efficiency of PFS is 95.34%. The efficiency of PFS is high, and each module can be used near to its notational processing time. Therefore, it is a conclusion that the computational solution is a suitable solution for this scheduling problem.


## 6. Conclusion

This paper introduces a clustering and genetic algorithm based method to solve the scheduling problem of a two-stage, HTS and PFS, hybrid flowshop problem. This problem is characterized by many constraints, such as batching operation, blocking environment, and setup time and working time limitations of modules. The clustering is used to group the jobs according to the processing ranges of the different modules of PFS. The genetic algorithm is used to schedule the optimal sequence of the grouped jobs for HTS and PFS. The designed algorithm is proven useful through a case study. Several advantages such as faster processing time, better utilization, and higher efficiency of HTS and PFS come out with this method.Currently, we only use the data simulation to verify the designed clustering and genetic algorithm. According to the further requirements of the collaborative company, this method should be improved for application. Furthermore, more practical experiences such as line balance of PFS will be considered and added to mathematical model. This will help to optimize the GA model and help to achieve better scheduling results for real-life manufacturing companies.



---

*Source: 167073-2014-03-27.xml*