# Supplier Selection and Production Planning by Using Guided Genetic Algorithm and Dynamic Nondominated Sorting Genetic Algorithm II Approaches

Authors: H. S. Wang; C. H. Tu; K. H. Chen
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Through the global supply chain (SC), numerous firms participate in vertically integrated manufacturing, and industrial collaboration and cooperation is the norm. SC management activities, such as delivery time, quality, and defect rate, are characterized by uncertainty. Based on all of the aforementioned factors, this study established a multiobjective mathematical model, integrating the guided genetic algorithm (Guided-GA) and the nondominated sorting genetic algorithm II (NSGA-II), developed in previous studies, to improve the mechanisms of the algorithms, thereby increasing the efficiency of the model and quality of the solution. The mathematical model was used to address the problems of supplier selection, assembly sequence planning, assembly line balancing, and defect rate, to enable suppliers to respond rapidly to sales orders. The model was empirically tested using a case study, showing that it is suitable for assisting decision makers in planning production and conducting SS according to sales orders, enabling production activities to achieve maximum efficiency and the competitiveness of firms to improve.


---

## Body

## 1. Introduction

Through the global supply chain (SC), numerous firms participate in vertically integrated manufacturing, and industrial collaboration and cooperation is the norm. Tan [1] indicated that supply chain management (SCM) is conducted through collaboration and integration among manufacturers throughout the production process, from obtaining raw materials to distributing finished goods and providing services. Zouggari and Benyoucef [2] determined that the supplier selection (SS) is a crucial issue in SCM. Al-e-Hashem et al. [3] considered aggregate production planning. Rashid et al. [4] determined that assembly line balancing (ALB) and assembly sequence planning (ASP) are critical for identifying an optimal solution. Chang et al. [5] indicated that, because customer-oriented marketing is a trend, production patterns are characterized by small volumes and wide varieties, and research and development (R&D) assembly planning considerations can improve production efficiency. Chutima and Chimklai [6] determined that ALB can be performed to reduce production costs, reduce work-in-process (WIP) inventory, and improve the reliability of delivery. SCM activities, such as delivery time, quality, and defect rate, are characterized by uncertainty. This study considered defect rate to enhance the solution quality.Based on all of the aforementioned factors, this study established a multiobjective mathematical model, integrating the guided genetic algorithm (Guided-GA) proposed by Tseng [7] and the nondominated sorting genetic algorithm II (NSGA-II) developed by Deb et al. [8] to improve the mechanisms of the algorithms, thereby increasing the efficiency of the model and quality of the solution.In the case analyzed in this study, a plant receiving a sales order must address SS, ASP, ALB, and defect rate problems. The multiobjective mathematical model was built into a decision-making system, increasing the efficiency of the decision-making process and enhancing overall competitiveness (Figure1).Figure 1
Schematic multiobjective optimization model.The goal of this study was to establish a multiobjective mathematical model that provides a rapid response to a sales order. The mathematical model was used to address the problems of SS, ASP, ALB, and defect rate. This study provides a useful approach for researchers and practitioners attempting to solve complex multiobjective problems. This approach involved applying the Guided-GA to identify the optimal solution and subsequently using the NSGA-II to establish a multiobjective optimization model. The NSGA-II was developed by Luo et al. [9], who proposed the concept of using dynamic crowding distance to improve the quality of solutions and, ultimately, to determine the optimal combinations for production planning with suppliers. A multiobjective algorithm was implemented using Visual C++ and the results were analyzed using a practical scenario simulation.


## 2. Literature Review

### 2.1. Supplier Selection

Customer demand is constantly changing and market competition is more intense than it was in the past. Products and services must be rapidly integrated to satisfy customer needs. Vertical integration of the SC is a critical factor of competition. The development of SS and relationships is a vital topic in SCM. Wadhwa and Ravindran [10] considered SS to be a multicriteria problem involving various factors. Sawik [11] emphasized that price, product quality, and reliability of delivery time are the critical factors for SS. Liao and Rittscher [12] indicated that cost, quality, delivery, and flexibility are critical decision factors for SS. Weber et al. [13] determined price, quality, and delivery time to be the critical factors. This study used the critical factors for delivery time as criteria for determining the optimal supplier portfolio.


### 2.2. Product Assembly Problem

Customer demand is rapidly changing; assembly plants must quickly respond to orders and deliver products. Dynamic production planning and product assembly are crucial topics. Product assembly involves assembly model construction and ASP. Assembly model construction is conducted during the product design stage, when a planner must consider the assembly process and resource characteristics. Su [14] determined that ASP is a connection between product design and product manufacturing that enhances the efficiency and reliability of product manufacturing. Wang et al. [15] proposed that ASP improves factory resource use as well as the layout cost and efficiency of assembly lines. Performing ASP effectively reduces production costs and production time and increases production activity rate.


### 2.3. Assembly Line Balance

Assembly line layout investment costs account for a high proportion of the overall manufacturing cost. Topaloglu et al. [16] indicated that assembly line machines and equipment must operate constantly to provide maximum productivity, enabling long-term capital investments to succeed. Sotskov et al. [17] determined that ALB is a critical issue when building a new production line. Rashid et al. [4] stated that ASP and ALB are critical procedures for optimizing the assembly process, and Erel and Sarin [18] proposed that ALB efficiency and balance delay are vital measures; the formulas for which are provided as follows:(1)
LBE
=
∑
t
i
N
·
t
m
a
x
×
100
%
,
Balance  Delay
=
1
-
LBE
,where t
i is the cycle time of workstation i and N is the total number of production lines at all workstations.Becker and Scholl [19] introduced the single-model line and mixed-model or multimodel line. If an assembly line produces a variety of products, it is a mixed-model line or a multimodel line, as shown in Figure 2.Figure 2
Single-model line, mixed-model line, and multimodel line.In the case analyzed in this paper, the assembly line was a mixed-model line. The number of workstations in each assembly line was fixed to enable the optimal production cycle time to be determined.


### 2.4. Guided Genetic Algorithms

Because the complexity of the solving process increases as the number of parts or constraints increases, several researchers have used genetic algorithms (GAs) to determine the optimal assembly sequence by arranging the genetic code in a manner suitable for ASP [7]. Dini et al. [20] and Marian et al. [21] proposed using a GA to solve ASP problems. Simulated annealing (SA) algorithms have been used frequently; Hong and Cho [22] proposed using an SA algorithm to identify an ASP solution, and Shan et al. [23] determined that using GA and SA algorithms in solving ASP problems produces premature convergence and inefficient solutions.Recent studies such as Chen et al. [24] have used neural networks to solve an ASP problem. Wang and Liu [25] proposed chaotic particle swarm optimization (CPSO) approaches to improve solving efficiency and the degree of convergence.This study used the Guided-GA proposed by Tseng [7] to solve ASP problems, which involved searching a solution space to meet solution constraints. In the Guided-GA, guided crossover and guided mutation concepts are applied between crossover and mutation steps, yielding a more favorable solving performance than that of traditional GA.


### 2.5. Multiobjective Genetic Algorithms

Because multiobjective problems are crucial topics, researchers have developed various multiobjective algorithms to solve these problems. Schaffer [26] proposed a multiobjective evolutionary algorithm called the vector evaluated genetic algorithm. Hajela and Lin [27] proposed a GA that includes a weighting concept. However, more calculus mechanisms are developed to complete multiobjective algorithms.Srinivas and Deb [28] developed the NSGA by increasing the scope of the solution to determine the optimal solution. Deb et al. [8] developed the NSGA-II by adding a crowding distance sorting mechanism to the NSGA to improve the calculation mechanism. The NSGA-II has been widely used to solve various problems. Lin and Yeh [29] combined the NSGA-II with the TOPSIS method to solve a computer networking problem, and Rezaei and Davoodi [30] used the NSGA-II to solve an SS problem. This study used the NSGA-II to solve SS and production planning problems and adopted the dynamic crowding distance proposed by Luo et al. [9] to increase the diversity of solutions.


## 2.1. Supplier Selection

Customer demand is constantly changing and market competition is more intense than it was in the past. Products and services must be rapidly integrated to satisfy customer needs. Vertical integration of the SC is a critical factor of competition. The development of SS and relationships is a vital topic in SCM. Wadhwa and Ravindran [10] considered SS to be a multicriteria problem involving various factors. Sawik [11] emphasized that price, product quality, and reliability of delivery time are the critical factors for SS. Liao and Rittscher [12] indicated that cost, quality, delivery, and flexibility are critical decision factors for SS. Weber et al. [13] determined price, quality, and delivery time to be the critical factors. This study used the critical factors for delivery time as criteria for determining the optimal supplier portfolio.


## 2.2. Product Assembly Problem

Customer demand is rapidly changing; assembly plants must quickly respond to orders and deliver products. Dynamic production planning and product assembly are crucial topics. Product assembly involves assembly model construction and ASP. Assembly model construction is conducted during the product design stage, when a planner must consider the assembly process and resource characteristics. Su [14] determined that ASP is a connection between product design and product manufacturing that enhances the efficiency and reliability of product manufacturing. Wang et al. [15] proposed that ASP improves factory resource use as well as the layout cost and efficiency of assembly lines. Performing ASP effectively reduces production costs and production time and increases production activity rate.


## 2.3. Assembly Line Balance

Assembly line layout investment costs account for a high proportion of the overall manufacturing cost. Topaloglu et al. [16] indicated that assembly line machines and equipment must operate constantly to provide maximum productivity, enabling long-term capital investments to succeed. Sotskov et al. [17] determined that ALB is a critical issue when building a new production line. Rashid et al. [4] stated that ASP and ALB are critical procedures for optimizing the assembly process, and Erel and Sarin [18] proposed that ALB efficiency and balance delay are vital measures; the formulas for which are provided as follows:(1)
LBE
=
∑
t
i
N
·
t
m
a
x
×
100
%
,
Balance  Delay
=
1
-
LBE
,where t
i is the cycle time of workstation i and N is the total number of production lines at all workstations.Becker and Scholl [19] introduced the single-model line and mixed-model or multimodel line. If an assembly line produces a variety of products, it is a mixed-model line or a multimodel line, as shown in Figure 2.Figure 2
Single-model line, mixed-model line, and multimodel line.In the case analyzed in this paper, the assembly line was a mixed-model line. The number of workstations in each assembly line was fixed to enable the optimal production cycle time to be determined.


## 2.4. Guided Genetic Algorithms

Because the complexity of the solving process increases as the number of parts or constraints increases, several researchers have used genetic algorithms (GAs) to determine the optimal assembly sequence by arranging the genetic code in a manner suitable for ASP [7]. Dini et al. [20] and Marian et al. [21] proposed using a GA to solve ASP problems. Simulated annealing (SA) algorithms have been used frequently; Hong and Cho [22] proposed using an SA algorithm to identify an ASP solution, and Shan et al. [23] determined that using GA and SA algorithms in solving ASP problems produces premature convergence and inefficient solutions.Recent studies such as Chen et al. [24] have used neural networks to solve an ASP problem. Wang and Liu [25] proposed chaotic particle swarm optimization (CPSO) approaches to improve solving efficiency and the degree of convergence.This study used the Guided-GA proposed by Tseng [7] to solve ASP problems, which involved searching a solution space to meet solution constraints. In the Guided-GA, guided crossover and guided mutation concepts are applied between crossover and mutation steps, yielding a more favorable solving performance than that of traditional GA.


## 2.5. Multiobjective Genetic Algorithms

Because multiobjective problems are crucial topics, researchers have developed various multiobjective algorithms to solve these problems. Schaffer [26] proposed a multiobjective evolutionary algorithm called the vector evaluated genetic algorithm. Hajela and Lin [27] proposed a GA that includes a weighting concept. However, more calculus mechanisms are developed to complete multiobjective algorithms.Srinivas and Deb [28] developed the NSGA by increasing the scope of the solution to determine the optimal solution. Deb et al. [8] developed the NSGA-II by adding a crowding distance sorting mechanism to the NSGA to improve the calculation mechanism. The NSGA-II has been widely used to solve various problems. Lin and Yeh [29] combined the NSGA-II with the TOPSIS method to solve a computer networking problem, and Rezaei and Davoodi [30] used the NSGA-II to solve an SS problem. This study used the NSGA-II to solve SS and production planning problems and adopted the dynamic crowding distance proposed by Luo et al. [9] to increase the diversity of solutions.


## 3. Research Methodology

### 3.1. Assumptions

In this paper, the assumptions for SS and production planning are described as follows:(1)
A single assembly plant, multiproduct, single-period SS model, and production planning are considered as a range.
(2)
SS criteria are the delivery time for the main selection criteria.
(3)
Each part may be purchased from various suppliers, and the low and high limits of the supplier’s production capacity are considered to prevent a shortage of production.
(4)
Assembly plant without capacity constraints.
(5)
The numbers of workstations and assembly sequences are known.
(6)
The supplier delivers complete batches; no partial batches are delivered.
(7)
Parts are allocated according to the work order before production begins.
(8)
Assembly sequence plans, each product route, and the bill of material (BOM) are known.
(9)
Common parts can substitute each other when assembly patterns, the assembly direction, and assembly machines are the same.
(10)
The transfer time between workstations is ignored.
(11)
Multiple products are produced using a mixed assembly line.


### 3.2. Procedure

This study developed a mathematical model for conducting SS and ASP based on the Guided-GA and NSGA-II. The research process is introduced sequentially as follows.(1) Phase 1: Data Preprocessing. Data were acquired from parts, supplier, and assembly manufacturing databases. The parts database contained data on all parts, the BOM, combined priority relationships, and the combined priority relationship matrix field. The supplier database contained data on parts and supplier relationships, production capacity, high and low capacity constraints, delivery time, and production time. The assembly manufacturing database contained data on assembly time, product demand for workstations and machine resources, production defect rates, and loss rates. These three databases were used to determine SS and ASP solutions.(2) Phase 2: Model and Rule Design. Delivery time was used to appraise the suppliers in SS; the supplier with the shortest delivery time was selected. ASP was conducted based on the BOM. Routing and combined priority relationships were obtained from the part-BOM database to calculate an optimal solution. Assembly planning was performed based on assembly time, resource demand, loss rate, and defect rate, which were acquired from the assembly manufacturing database to calculate an optimal solution. This study integrated the various dimensions to build a multiobjective mathematical model.(3) Phase 3: Implementation. Programming was performed using the Visual C++ language, and a multiobjective mathematical model was implemented. Finally, the results and solutions are discussed. The detailed procedure is shown in Figure 3.Figure 3
Research procedure.


### 3.3. Multiobjective Mathematical Model

In this section, we define mathematical parameters and develop a mathematical formula.


#### 3.3.1. Definition of Mathematical Parameters

I
: total number of parts,
i
,
j: parts index number; i
=
1,2
,
3
,
…
I; j
=
1,2
,
3
,
…
,
I,
X: total products,
x: product index number; x
=
1,2
,
3
,
…
,
X,
K: total number of workstations,
k: workstations index number; k
=
1,2
,
3
,
…
,
K,
M: total number of assembly relations,
S: total number of assembly sequence,
S
1
,
S
2: assembly sequence index number; s
1
=
1,2
,
3
,
…
,
S; s
2
=
1,2
,
3
,
…
,
S,
m
,
n: assembly relations index number; m
=
1,2
,
3
,
…
,
M; n
=
1,2
,
3
,
…
,
M,
V
i: total number of suppliers for parts i,
v: suppliers index number for parts i; v
=
1,2
,
3
,
…
,
V
i,
P
x
i
v: supplier v for parts i for product x,
P
A
x
i
v: the quantity of supplier v purchase parts i for product x,
X
m
k: assembly relations index number m assigned to workstation index number k,
A
D
x: total number of demand for product x,
O
m
n
s
1: under assembly sequence s
1, operation between assembly relations index number m with assembly relations index number n,
Y
m
k
s
1: under assembly sequence s
1, assembly relations index number m assigned to workstation index number k,
O
T
m
n: the operation time between assembly relations index number m and assembly relations index number n,
P
T
i
v: the total time of supplier v to produce parts i,
T
T
i
v: the total time of supplier v delivery parts i to assembly plant,
S
R
x: defect rate of product x in assembly plant,
L
C
v: supplier lower limit production capacity,
U
C
v: supplier higher limit production capacity,
C
S
m: an operation collection of assembly relations m,
O
D
x: order demand of product x,
T
T
T: total delivery time,
F
T: total order fulfillment time,
C
T: assembly line production time,
W: assembly line performance assigned to workstation to assemble,
P
x
i
v: P
x
i
v = {
1, selected supplier v to purchase parts i for product x; 0, o
t
h
e
r
w
i
s
e
},
x
m
k: x
m
k = {
1, assembly relations index number m assigned to workstation k; 0, o
t
h
e
r
w
i
s
e
},
O
m
n
S
1: O
m
n
S
1 = {
1, under assembly sequence s
1, to assemble m and n; 0, o
t
h
e
r
w
i
s
e
},
Y
m
k
S
1: Y
m
k
S
1 = {
1, under assembly sequence s
1, m assigned to workstation k; 0, o
t
h
e
r
w
i
s
e
}.


#### 3.3.2. Description of Mathematical Formulas

In this study, the order fulfillment time and assembly line performance were used in the objective formulas. Supply and demand constraints, assembly sequence constraints, supplier capacity constraints, and resource constraints were considered in the constraint formulas. The objective formulas and constraint formulas are described as follows.(i) Objective Formulas(1) Minimization of Total Order Fulfillment Time. The sum of the total assembly time and total supplier delivery time was minimized using (2) as follows:(2)
Minimize  FT
=
TMT
+
TTT
.For smooth operation of the assembly line, the total assembly time for all workstations was calculated using the maximum assembly time, as shown in(3)
T
M
T
=
∑
k
=
1
K
Max
⁡
∑
s
1
=
1
S
∑
m
=
1
M
∑
n
=
1
N
∑
x
=
1
X
O
m
n
s
1
Y
m
k
s
1
O
T
m
n
A
D
x
.We assumed that all parts are prepared according to the work order before production begins. The total delivery time was calculated based on each product mapping supplier list to select the maximum delivery time, using(4)
TTT
=
Max
⁡
T
T
i
v
P
x
i
v
∣
∀
i
,
∀
v
.(2) Maximization of Assembly Line Performance. To enable the smooth operation of assembly line production activities, the total assembly time for all products in all workstations was calculated and expressed as a percentage value by using(5)
Max
⁡
W
=
∑
s
1
=
1
S
∑
m
=
1
M
∑
n
=
1
N
∑
k
=
1
K
∑
x
=
1
X
O
m
n
s
1
Y
m
k
s
1
O
T
m
n
A
D
x
CT
×
100
%
.(ii) Constraint Formulas(1) Supply and Demand Constraint. The defective quantity and fulfillment of each order quantity are subtracted from each product demand quantity as follows:(6)
A
D
x
-
S
R
x
·
A
D
x
=
O
D
x
,
∀
x
.(2) Supplier Capacity Constraint. Purchase quantity is determined according to the supplier’s production capacity for each part, constrained by high and low limits, as shown in(7)
L
C
v
≤
∑
x
=
1
X
P
A
x
i
v
≤
U
C
v
or
P
A
x
i
v
=
0
.(3) Combination Relationship Constraint. Assembly is determined based on the assembly sequence and the relationship between the priorities of each combination by using(8)
Y
m
k
s
1
s
1
≥
Y
n
k
s
1
s
1
,
∀
k
;
∀
m
,
∀
n
∈
C
S
m
.(4) Routing Rule Constraint. For production planning, assembly assigned to each workstation is conducted by following a routing rule, the various assembly relationships, as follows:(9)
Y
m
k
s
1
k
≥
Y
n
k
s
1
k
,
∀
k
;
∀
m
,
∀
n
∈
C
S
m
.(5) Workstation Constraint 1. The quantity of workstations is less than the total number of workstations in the assembly plant, as expressed in(10)
∑
k
=
1
K
k
Y
m
k
s
1
≤
K
,
∀
m
.(6) Workstation Constraint 2. Each job is assigned to one workstation and assignments cannot be repeated, as shown in(11)
∑
k
=
1
K
Y
m
k
s
1
=
1
,
∀
m
,
∀
s
.(7) Other Constraint 1. Purchase quantity is a positive integer or equal to zero, as shown in(12)
P
A
x
i
v
∈
Z
+
,
∀
i
,
∀
v
,
∀
x
.(8) Other Constraint 2. Total purchase quantity is equal to the total of the parts of demand quantity, the total demand for all products, as shown in(13)
∑
v
=
1
V
i
P
x
i
v
P
A
x
i
v
=
A
D
x
,
∀
i
,
∀
x
.


### 3.4. Integrated Guided-GA and Dynamic NSGA-II

This study adopted the Guided-GA proposed by Tseng [7] and the NSGA-II proposed by Deb et al. [8] to develop an integrated multiobjective model for determining an optimal solution. The concept of dynamic crowding distance proposed by Luo et al. [9] and the diagram of Plato frontline distribution were also integrated into the model to increase uniformity and diversity, producing an integrated algorithm called the Guided-D-NSGA-II.


#### 3.4.1. Guided-D-NSGA-II Procedure

The detailed procedure of the Guided-D-NSGA-II is shown in Figure4.Figure 4
Guided-D-NSGA-II procedure.A detailed step-by-step description of the algorithm is presented as follows.Step 1 (population coding).
Population codes are divided into three substeps. Substep  1 is ASP coding. Genetic values represent the various product assembly relationships and must comply with constraints (8) and (9). Substep 2 is SS coding and use of real-coded. Genetic values represent the purchases of each supplier and must meet constraints (6), (7), (12), and (13). Substep 3 is ALB coding. Genetic values represent the production quantity of each workstation and must comply with constraints (10) and (11). The population structure is shown in Figure 5.Figure 5
Diagram of gene coding.Step 2 (generating the initial population).
The initial generation is performed based on demand quantity and the constraints of the mathematical model. Defect rate is considered in demand quantity, and the constraints of each combination relationship and priority are considered in ASP. The supplier’s capacity constraints are considered in SS; if the purchase quantity exceeds the supplier’s capacity, another supplier is randomly selected to fulfill the order. The constraints of workstations are considered in ALB.Step 3 (calculating the value of the objective formula).
The initial population is generated into the two objective formulas. Objective formulas (2) are calculated by (3) and (4), and the objective formula (5) is calculate by (3).Step 4 (sorting nondominated solutions).
Nondominated solutions are used for sorting and as a basis for judging the merit population. After a reproduction step, objective formulas for each population and for nondominated solutions sorting are calculated.
First, the population for which the dominated solution is zero is identified. This population is called the first frontline population and is also known as nondominated solutions. The other populations are called dominated solutions; all of the dominated solutions are identified from the remaining population and are defined as the second frontline population. This process is conducted repeatedly until all of the populations are sorted. The sorting process is shown in Figure6.
Figure6(a) indicates that points A–E constituted the first frontline population because they could not dominate each other. Points F–I were then sorted to confirm the absence of the population domination among them and were defined as the second frontline population. Figure 6(b) shows the sorting of all populations.Figure 6
Diagram of nondominated sorting.
(a)
(b)Step 5 (calculating crowding distance).
The first through third frontline populations are sorted in Step4, and all population crowding distances become the size of a reproduction probability basis. Population density is a concept of crowding distance. If the distance between populations is short and the indicated density is high, the reproduction probability is low; if the distance is long and the indicated density is low, reproduction probability is high. Crowding distance is calculated as follows to obtain a uniform population distribution:(14)
C
D
i
=
1
r
∑
k
=
1
r
f
k
i
+
1
-
f
k
i
-
1
i
=
1,2
,
3
,
…
,
j
-
1
,where C
D
i is the crowding distance of i populations, r is the number of the objective formula, k is one value of the objective formula, i is the number of populations, j is the last frontline population, and f
k
i
+
1 and f
k
i
-
1 are population (i
+
1) and population (i
-
1) of the objective formula value k. In each frontline, the distribution of both sides populations is crowded and the distance is set to infinity, as shown in Figure 7.
Luo et al. [9] indicated that crowding distance calculations are deficient. Figure 8 shows that Population B had a gap of f
1 and f
2 that was wider than that of Population F; therefore, the crowding distance of Population B was shorter than that of Population F. A comparison of the crowding distances of Populations B and F indicates that Population F is more favorable than Population B; however, Population B is more favorable than Population F.
Based on this deficiency, Luo et al. [9] proposed the dynamic crowding distance equation:(15)
DCD
i
=
CD
i
log
⁡
1
/
V
i
.
The termV
i is calculated using CD
i equation (15) as shown in(16)
V
i
=
1
r
∑
k
=
1
r
f
k
i
+
1
-
f
k
i
-
1
-
CD
i
2
.
Equation (16) shows the objective formula gap of a neighboring population; when a gap is wider, the probability of reproduction is higher. Calculating the distance with dynamic crowding improves the uniformity and diversity of the population.Figure 7
Diagram of crowding distance.Figure 8
Traditional crowding distance from the uneven distribution.Step 6 (reproduction).
The purpose of reproduction is to identify a favorable population for the crossover step. We used binary tournament selection to identify the elite population according to the following two criteria:(1)
If two frontline populations differ, the lower frontline population is used in the reproduction procedure.
(2)
If two frontline populations are the same, the population with the longer crowding distance is used in the reproduction procedure.Step 7 (crossover).
Genetic codes are exchanged during the crossover procedure, yielding a new, improved generation of children that retain certain features of the previous population. The crossover step was conducted using the two following methods.
(1) Guided Crossover. Guided crossover increased ASP solution efficiency, as shown in Figure 9.
As shown in Figure9, Step 1 of guided crossover involved electing two populations for crossover. Two parents randomly generate each retention block, retention block size, and starting position, and two retention block gene codes are copied to new parent generations in the same position. In addition, the nonretention blocks of gene codes of two populations are copied to the new population. The crossover process must be completed according to the constraints described in (8) and (9).
(2) One-Point Crossover. One-point crossover was used for SS and ASP; the process is shown in Figures 10 and 11.
For SS, Substep1 involves randomly selecting two populations to cross over; Substep 2 entails randomly selecting the parts purchase quantity for the genetic code to be exchanged; the crossover process is completed in Substep 3 according to the SS constraints in (7), (12), and (13).Figure 9
Diagram of guided crossover.Figure 10
Supplier selection by one-point crossover.Figure 11
Assembly line balancing by one-point crossover.For ALB, Substep1 involves randomly selecting two populations to cross over; Substep 2 entails randomly selecting a cutoff point to create crossover blocks and subsequently exchanging the genetic code of the crossover blocks from two populations; the ALB crossover process is completed in Substep 3 according to the ALB constraints in (10) and (11).Step 8 (mutation).
Mutation is the key process of evolution. If a new generation feature does not develop, a local optimum cannot be achieved. The mutation step was conducted using the following two methods.
(1) Guided Mutation. Guided mutation is performed to increase the solution efficiency of ASP; the process is shown in Figure 12.
As shown in Figure12, Substep 1 involves randomly selecting a population to mutate. Substep 2 entails randomly selecting a cutoff point to create a genetic mutation. Substep 3 from mutation genetic starts to search; if a genetic value is identified and the genetic mutation has a combined priority relationship, set the genetic value as a junction point. Substep 4 involves moving a genetic mutation to the junction point of the previous position; the original genetic mutation location is sequentially moved forward. The mutation process is performed according to the constraints in (8) and (9).
(2) Two-Point Mutations. Two-point mutations were used in SS and ALB evaluations; the process is shown in Figures 13 and 14.
For SS, Substep1 involves randomly selecting a population of parts to mutate; this population has several related suppliers. In Substep 2, based on this population of parts, a supplier is randomly selected as a cutoff point that becomes the mutation point. In Substep 3, mutation is performed based on supplier capacity constraints. Substep 4 is conducted to validate the demand and supplier capacity constraints; if demand cannot be fulfilled, the next supplier is used as the mutation point. The mutation process must be conducted according to the SS constraints in (7), (12), and (13).
For ALB, Substep1 involves randomly selecting a workstation as a population to mutate according to workstation assembly constraints. Because each assembly must be assigned to a workstation and match the assembly quantity, Substep 2 involves randomly selecting another workstation as a population to mutate to balance the constraint. The mutation process must be completed according to the workstation constraints in (10) and (11).Figure 12
Diagram of guided mutation.Figure 13
Supplier selection by two-point mutation.Figure 14
Assembly line balancing by two-point mutation.Step 9 (elite retention policy).
An elite retention policy is established to retain the elite genetic mutations from evolution; the process is shown in Figure15.
As shown in Figure15, the current generation merger population (P
t) and offspring population (Q
t) then get the 2
N population. Substep 1 involves sorting the 2
N population according to nondominated solutions and dynamic crowding distance calculations. In Substep 2, 50% of the population is retained; if the frontline is the same when sorted, comparisons are based on the dynamic crowding distance. In the solving process, the same frontline and the same population are not repeatedly retained to prevent the local optimum from being achieved.Figure 15
Elitism retention strategy.Step 10 (validation according to stop conditions).
When the number of generations is met and counting is finished, the process is stopped; if not, the process is restarted beginning with Step3.Step 11 (optimal production strategies).
When the desired number of generations is met, the optimal solutions for ASP, SS, and ALB, as well as the mathematical models for minimizing the total order fulfillment time and maximizing assembly line performance, are obtained.


## 3.1. Assumptions

In this paper, the assumptions for SS and production planning are described as follows:(1)
A single assembly plant, multiproduct, single-period SS model, and production planning are considered as a range.
(2)
SS criteria are the delivery time for the main selection criteria.
(3)
Each part may be purchased from various suppliers, and the low and high limits of the supplier’s production capacity are considered to prevent a shortage of production.
(4)
Assembly plant without capacity constraints.
(5)
The numbers of workstations and assembly sequences are known.
(6)
The supplier delivers complete batches; no partial batches are delivered.
(7)
Parts are allocated according to the work order before production begins.
(8)
Assembly sequence plans, each product route, and the bill of material (BOM) are known.
(9)
Common parts can substitute each other when assembly patterns, the assembly direction, and assembly machines are the same.
(10)
The transfer time between workstations is ignored.
(11)
Multiple products are produced using a mixed assembly line.


## 3.2. Procedure

This study developed a mathematical model for conducting SS and ASP based on the Guided-GA and NSGA-II. The research process is introduced sequentially as follows.(1) Phase 1: Data Preprocessing. Data were acquired from parts, supplier, and assembly manufacturing databases. The parts database contained data on all parts, the BOM, combined priority relationships, and the combined priority relationship matrix field. The supplier database contained data on parts and supplier relationships, production capacity, high and low capacity constraints, delivery time, and production time. The assembly manufacturing database contained data on assembly time, product demand for workstations and machine resources, production defect rates, and loss rates. These three databases were used to determine SS and ASP solutions.(2) Phase 2: Model and Rule Design. Delivery time was used to appraise the suppliers in SS; the supplier with the shortest delivery time was selected. ASP was conducted based on the BOM. Routing and combined priority relationships were obtained from the part-BOM database to calculate an optimal solution. Assembly planning was performed based on assembly time, resource demand, loss rate, and defect rate, which were acquired from the assembly manufacturing database to calculate an optimal solution. This study integrated the various dimensions to build a multiobjective mathematical model.(3) Phase 3: Implementation. Programming was performed using the Visual C++ language, and a multiobjective mathematical model was implemented. Finally, the results and solutions are discussed. The detailed procedure is shown in Figure 3.Figure 3
Research procedure.


## 3.3. Multiobjective Mathematical Model

In this section, we define mathematical parameters and develop a mathematical formula.


### 3.3.1. Definition of Mathematical Parameters

I
: total number of parts,
i
,
j: parts index number; i
=
1,2
,
3
,
…
I; j
=
1,2
,
3
,
…
,
I,
X: total products,
x: product index number; x
=
1,2
,
3
,
…
,
X,
K: total number of workstations,
k: workstations index number; k
=
1,2
,
3
,
…
,
K,
M: total number of assembly relations,
S: total number of assembly sequence,
S
1
,
S
2: assembly sequence index number; s
1
=
1,2
,
3
,
…
,
S; s
2
=
1,2
,
3
,
…
,
S,
m
,
n: assembly relations index number; m
=
1,2
,
3
,
…
,
M; n
=
1,2
,
3
,
…
,
M,
V
i: total number of suppliers for parts i,
v: suppliers index number for parts i; v
=
1,2
,
3
,
…
,
V
i,
P
x
i
v: supplier v for parts i for product x,
P
A
x
i
v: the quantity of supplier v purchase parts i for product x,
X
m
k: assembly relations index number m assigned to workstation index number k,
A
D
x: total number of demand for product x,
O
m
n
s
1: under assembly sequence s
1, operation between assembly relations index number m with assembly relations index number n,
Y
m
k
s
1: under assembly sequence s
1, assembly relations index number m assigned to workstation index number k,
O
T
m
n: the operation time between assembly relations index number m and assembly relations index number n,
P
T
i
v: the total time of supplier v to produce parts i,
T
T
i
v: the total time of supplier v delivery parts i to assembly plant,
S
R
x: defect rate of product x in assembly plant,
L
C
v: supplier lower limit production capacity,
U
C
v: supplier higher limit production capacity,
C
S
m: an operation collection of assembly relations m,
O
D
x: order demand of product x,
T
T
T: total delivery time,
F
T: total order fulfillment time,
C
T: assembly line production time,
W: assembly line performance assigned to workstation to assemble,
P
x
i
v: P
x
i
v = {
1, selected supplier v to purchase parts i for product x; 0, o
t
h
e
r
w
i
s
e
},
x
m
k: x
m
k = {
1, assembly relations index number m assigned to workstation k; 0, o
t
h
e
r
w
i
s
e
},
O
m
n
S
1: O
m
n
S
1 = {
1, under assembly sequence s
1, to assemble m and n; 0, o
t
h
e
r
w
i
s
e
},
Y
m
k
S
1: Y
m
k
S
1 = {
1, under assembly sequence s
1, m assigned to workstation k; 0, o
t
h
e
r
w
i
s
e
}.


### 3.3.2. Description of Mathematical Formulas

In this study, the order fulfillment time and assembly line performance were used in the objective formulas. Supply and demand constraints, assembly sequence constraints, supplier capacity constraints, and resource constraints were considered in the constraint formulas. The objective formulas and constraint formulas are described as follows.(i) Objective Formulas(1) Minimization of Total Order Fulfillment Time. The sum of the total assembly time and total supplier delivery time was minimized using (2) as follows:(2)
Minimize  FT
=
TMT
+
TTT
.For smooth operation of the assembly line, the total assembly time for all workstations was calculated using the maximum assembly time, as shown in(3)
T
M
T
=
∑
k
=
1
K
Max
⁡
∑
s
1
=
1
S
∑
m
=
1
M
∑
n
=
1
N
∑
x
=
1
X
O
m
n
s
1
Y
m
k
s
1
O
T
m
n
A
D
x
.We assumed that all parts are prepared according to the work order before production begins. The total delivery time was calculated based on each product mapping supplier list to select the maximum delivery time, using(4)
TTT
=
Max
⁡
T
T
i
v
P
x
i
v
∣
∀
i
,
∀
v
.(2) Maximization of Assembly Line Performance. To enable the smooth operation of assembly line production activities, the total assembly time for all products in all workstations was calculated and expressed as a percentage value by using(5)
Max
⁡
W
=
∑
s
1
=
1
S
∑
m
=
1
M
∑
n
=
1
N
∑
k
=
1
K
∑
x
=
1
X
O
m
n
s
1
Y
m
k
s
1
O
T
m
n
A
D
x
CT
×
100
%
.(ii) Constraint Formulas(1) Supply and Demand Constraint. The defective quantity and fulfillment of each order quantity are subtracted from each product demand quantity as follows:(6)
A
D
x
-
S
R
x
·
A
D
x
=
O
D
x
,
∀
x
.(2) Supplier Capacity Constraint. Purchase quantity is determined according to the supplier’s production capacity for each part, constrained by high and low limits, as shown in(7)
L
C
v
≤
∑
x
=
1
X
P
A
x
i
v
≤
U
C
v
or
P
A
x
i
v
=
0
.(3) Combination Relationship Constraint. Assembly is determined based on the assembly sequence and the relationship between the priorities of each combination by using(8)
Y
m
k
s
1
s
1
≥
Y
n
k
s
1
s
1
,
∀
k
;
∀
m
,
∀
n
∈
C
S
m
.(4) Routing Rule Constraint. For production planning, assembly assigned to each workstation is conducted by following a routing rule, the various assembly relationships, as follows:(9)
Y
m
k
s
1
k
≥
Y
n
k
s
1
k
,
∀
k
;
∀
m
,
∀
n
∈
C
S
m
.(5) Workstation Constraint 1. The quantity of workstations is less than the total number of workstations in the assembly plant, as expressed in(10)
∑
k
=
1
K
k
Y
m
k
s
1
≤
K
,
∀
m
.(6) Workstation Constraint 2. Each job is assigned to one workstation and assignments cannot be repeated, as shown in(11)
∑
k
=
1
K
Y
m
k
s
1
=
1
,
∀
m
,
∀
s
.(7) Other Constraint 1. Purchase quantity is a positive integer or equal to zero, as shown in(12)
P
A
x
i
v
∈
Z
+
,
∀
i
,
∀
v
,
∀
x
.(8) Other Constraint 2. Total purchase quantity is equal to the total of the parts of demand quantity, the total demand for all products, as shown in(13)
∑
v
=
1
V
i
P
x
i
v
P
A
x
i
v
=
A
D
x
,
∀
i
,
∀
x
.


## 3.3.1. Definition of Mathematical Parameters

I
: total number of parts,
i
,
j: parts index number; i
=
1,2
,
3
,
…
I; j
=
1,2
,
3
,
…
,
I,
X: total products,
x: product index number; x
=
1,2
,
3
,
…
,
X,
K: total number of workstations,
k: workstations index number; k
=
1,2
,
3
,
…
,
K,
M: total number of assembly relations,
S: total number of assembly sequence,
S
1
,
S
2: assembly sequence index number; s
1
=
1,2
,
3
,
…
,
S; s
2
=
1,2
,
3
,
…
,
S,
m
,
n: assembly relations index number; m
=
1,2
,
3
,
…
,
M; n
=
1,2
,
3
,
…
,
M,
V
i: total number of suppliers for parts i,
v: suppliers index number for parts i; v
=
1,2
,
3
,
…
,
V
i,
P
x
i
v: supplier v for parts i for product x,
P
A
x
i
v: the quantity of supplier v purchase parts i for product x,
X
m
k: assembly relations index number m assigned to workstation index number k,
A
D
x: total number of demand for product x,
O
m
n
s
1: under assembly sequence s
1, operation between assembly relations index number m with assembly relations index number n,
Y
m
k
s
1: under assembly sequence s
1, assembly relations index number m assigned to workstation index number k,
O
T
m
n: the operation time between assembly relations index number m and assembly relations index number n,
P
T
i
v: the total time of supplier v to produce parts i,
T
T
i
v: the total time of supplier v delivery parts i to assembly plant,
S
R
x: defect rate of product x in assembly plant,
L
C
v: supplier lower limit production capacity,
U
C
v: supplier higher limit production capacity,
C
S
m: an operation collection of assembly relations m,
O
D
x: order demand of product x,
T
T
T: total delivery time,
F
T: total order fulfillment time,
C
T: assembly line production time,
W: assembly line performance assigned to workstation to assemble,
P
x
i
v: P
x
i
v = {
1, selected supplier v to purchase parts i for product x; 0, o
t
h
e
r
w
i
s
e
},
x
m
k: x
m
k = {
1, assembly relations index number m assigned to workstation k; 0, o
t
h
e
r
w
i
s
e
},
O
m
n
S
1: O
m
n
S
1 = {
1, under assembly sequence s
1, to assemble m and n; 0, o
t
h
e
r
w
i
s
e
},
Y
m
k
S
1: Y
m
k
S
1 = {
1, under assembly sequence s
1, m assigned to workstation k; 0, o
t
h
e
r
w
i
s
e
}.


## 3.3.2. Description of Mathematical Formulas

In this study, the order fulfillment time and assembly line performance were used in the objective formulas. Supply and demand constraints, assembly sequence constraints, supplier capacity constraints, and resource constraints were considered in the constraint formulas. The objective formulas and constraint formulas are described as follows.(i) Objective Formulas(1) Minimization of Total Order Fulfillment Time. The sum of the total assembly time and total supplier delivery time was minimized using (2) as follows:(2)
Minimize  FT
=
TMT
+
TTT
.For smooth operation of the assembly line, the total assembly time for all workstations was calculated using the maximum assembly time, as shown in(3)
T
M
T
=
∑
k
=
1
K
Max
⁡
∑
s
1
=
1
S
∑
m
=
1
M
∑
n
=
1
N
∑
x
=
1
X
O
m
n
s
1
Y
m
k
s
1
O
T
m
n
A
D
x
.We assumed that all parts are prepared according to the work order before production begins. The total delivery time was calculated based on each product mapping supplier list to select the maximum delivery time, using(4)
TTT
=
Max
⁡
T
T
i
v
P
x
i
v
∣
∀
i
,
∀
v
.(2) Maximization of Assembly Line Performance. To enable the smooth operation of assembly line production activities, the total assembly time for all products in all workstations was calculated and expressed as a percentage value by using(5)
Max
⁡
W
=
∑
s
1
=
1
S
∑
m
=
1
M
∑
n
=
1
N
∑
k
=
1
K
∑
x
=
1
X
O
m
n
s
1
Y
m
k
s
1
O
T
m
n
A
D
x
CT
×
100
%
.(ii) Constraint Formulas(1) Supply and Demand Constraint. The defective quantity and fulfillment of each order quantity are subtracted from each product demand quantity as follows:(6)
A
D
x
-
S
R
x
·
A
D
x
=
O
D
x
,
∀
x
.(2) Supplier Capacity Constraint. Purchase quantity is determined according to the supplier’s production capacity for each part, constrained by high and low limits, as shown in(7)
L
C
v
≤
∑
x
=
1
X
P
A
x
i
v
≤
U
C
v
or
P
A
x
i
v
=
0
.(3) Combination Relationship Constraint. Assembly is determined based on the assembly sequence and the relationship between the priorities of each combination by using(8)
Y
m
k
s
1
s
1
≥
Y
n
k
s
1
s
1
,
∀
k
;
∀
m
,
∀
n
∈
C
S
m
.(4) Routing Rule Constraint. For production planning, assembly assigned to each workstation is conducted by following a routing rule, the various assembly relationships, as follows:(9)
Y
m
k
s
1
k
≥
Y
n
k
s
1
k
,
∀
k
;
∀
m
,
∀
n
∈
C
S
m
.(5) Workstation Constraint 1. The quantity of workstations is less than the total number of workstations in the assembly plant, as expressed in(10)
∑
k
=
1
K
k
Y
m
k
s
1
≤
K
,
∀
m
.(6) Workstation Constraint 2. Each job is assigned to one workstation and assignments cannot be repeated, as shown in(11)
∑
k
=
1
K
Y
m
k
s
1
=
1
,
∀
m
,
∀
s
.(7) Other Constraint 1. Purchase quantity is a positive integer or equal to zero, as shown in(12)
P
A
x
i
v
∈
Z
+
,
∀
i
,
∀
v
,
∀
x
.(8) Other Constraint 2. Total purchase quantity is equal to the total of the parts of demand quantity, the total demand for all products, as shown in(13)
∑
v
=
1
V
i
P
x
i
v
P
A
x
i
v
=
A
D
x
,
∀
i
,
∀
x
.


## 3.4. Integrated Guided-GA and Dynamic NSGA-II

This study adopted the Guided-GA proposed by Tseng [7] and the NSGA-II proposed by Deb et al. [8] to develop an integrated multiobjective model for determining an optimal solution. The concept of dynamic crowding distance proposed by Luo et al. [9] and the diagram of Plato frontline distribution were also integrated into the model to increase uniformity and diversity, producing an integrated algorithm called the Guided-D-NSGA-II.


### 3.4.1. Guided-D-NSGA-II Procedure

The detailed procedure of the Guided-D-NSGA-II is shown in Figure4.Figure 4
Guided-D-NSGA-II procedure.A detailed step-by-step description of the algorithm is presented as follows.Step 1 (population coding).
Population codes are divided into three substeps. Substep  1 is ASP coding. Genetic values represent the various product assembly relationships and must comply with constraints (8) and (9). Substep 2 is SS coding and use of real-coded. Genetic values represent the purchases of each supplier and must meet constraints (6), (7), (12), and (13). Substep 3 is ALB coding. Genetic values represent the production quantity of each workstation and must comply with constraints (10) and (11). The population structure is shown in Figure 5.Figure 5
Diagram of gene coding.Step 2 (generating the initial population).
The initial generation is performed based on demand quantity and the constraints of the mathematical model. Defect rate is considered in demand quantity, and the constraints of each combination relationship and priority are considered in ASP. The supplier’s capacity constraints are considered in SS; if the purchase quantity exceeds the supplier’s capacity, another supplier is randomly selected to fulfill the order. The constraints of workstations are considered in ALB.Step 3 (calculating the value of the objective formula).
The initial population is generated into the two objective formulas. Objective formulas (2) are calculated by (3) and (4), and the objective formula (5) is calculate by (3).Step 4 (sorting nondominated solutions).
Nondominated solutions are used for sorting and as a basis for judging the merit population. After a reproduction step, objective formulas for each population and for nondominated solutions sorting are calculated.
First, the population for which the dominated solution is zero is identified. This population is called the first frontline population and is also known as nondominated solutions. The other populations are called dominated solutions; all of the dominated solutions are identified from the remaining population and are defined as the second frontline population. This process is conducted repeatedly until all of the populations are sorted. The sorting process is shown in Figure6.
Figure6(a) indicates that points A–E constituted the first frontline population because they could not dominate each other. Points F–I were then sorted to confirm the absence of the population domination among them and were defined as the second frontline population. Figure 6(b) shows the sorting of all populations.Figure 6
Diagram of nondominated sorting.
(a)
(b)Step 5 (calculating crowding distance).
The first through third frontline populations are sorted in Step4, and all population crowding distances become the size of a reproduction probability basis. Population density is a concept of crowding distance. If the distance between populations is short and the indicated density is high, the reproduction probability is low; if the distance is long and the indicated density is low, reproduction probability is high. Crowding distance is calculated as follows to obtain a uniform population distribution:(14)
C
D
i
=
1
r
∑
k
=
1
r
f
k
i
+
1
-
f
k
i
-
1
i
=
1,2
,
3
,
…
,
j
-
1
,where C
D
i is the crowding distance of i populations, r is the number of the objective formula, k is one value of the objective formula, i is the number of populations, j is the last frontline population, and f
k
i
+
1 and f
k
i
-
1 are population (i
+
1) and population (i
-
1) of the objective formula value k. In each frontline, the distribution of both sides populations is crowded and the distance is set to infinity, as shown in Figure 7.
Luo et al. [9] indicated that crowding distance calculations are deficient. Figure 8 shows that Population B had a gap of f
1 and f
2 that was wider than that of Population F; therefore, the crowding distance of Population B was shorter than that of Population F. A comparison of the crowding distances of Populations B and F indicates that Population F is more favorable than Population B; however, Population B is more favorable than Population F.
Based on this deficiency, Luo et al. [9] proposed the dynamic crowding distance equation:(15)
DCD
i
=
CD
i
log
⁡
1
/
V
i
.
The termV
i is calculated using CD
i equation (15) as shown in(16)
V
i
=
1
r
∑
k
=
1
r
f
k
i
+
1
-
f
k
i
-
1
-
CD
i
2
.
Equation (16) shows the objective formula gap of a neighboring population; when a gap is wider, the probability of reproduction is higher. Calculating the distance with dynamic crowding improves the uniformity and diversity of the population.Figure 7
Diagram of crowding distance.Figure 8
Traditional crowding distance from the uneven distribution.Step 6 (reproduction).
The purpose of reproduction is to identify a favorable population for the crossover step. We used binary tournament selection to identify the elite population according to the following two criteria:(1)
If two frontline populations differ, the lower frontline population is used in the reproduction procedure.
(2)
If two frontline populations are the same, the population with the longer crowding distance is used in the reproduction procedure.Step 7 (crossover).
Genetic codes are exchanged during the crossover procedure, yielding a new, improved generation of children that retain certain features of the previous population. The crossover step was conducted using the two following methods.
(1) Guided Crossover. Guided crossover increased ASP solution efficiency, as shown in Figure 9.
As shown in Figure9, Step 1 of guided crossover involved electing two populations for crossover. Two parents randomly generate each retention block, retention block size, and starting position, and two retention block gene codes are copied to new parent generations in the same position. In addition, the nonretention blocks of gene codes of two populations are copied to the new population. The crossover process must be completed according to the constraints described in (8) and (9).
(2) One-Point Crossover. One-point crossover was used for SS and ASP; the process is shown in Figures 10 and 11.
For SS, Substep1 involves randomly selecting two populations to cross over; Substep 2 entails randomly selecting the parts purchase quantity for the genetic code to be exchanged; the crossover process is completed in Substep 3 according to the SS constraints in (7), (12), and (13).Figure 9
Diagram of guided crossover.Figure 10
Supplier selection by one-point crossover.Figure 11
Assembly line balancing by one-point crossover.For ALB, Substep1 involves randomly selecting two populations to cross over; Substep 2 entails randomly selecting a cutoff point to create crossover blocks and subsequently exchanging the genetic code of the crossover blocks from two populations; the ALB crossover process is completed in Substep 3 according to the ALB constraints in (10) and (11).Step 8 (mutation).
Mutation is the key process of evolution. If a new generation feature does not develop, a local optimum cannot be achieved. The mutation step was conducted using the following two methods.
(1) Guided Mutation. Guided mutation is performed to increase the solution efficiency of ASP; the process is shown in Figure 12.
As shown in Figure12, Substep 1 involves randomly selecting a population to mutate. Substep 2 entails randomly selecting a cutoff point to create a genetic mutation. Substep 3 from mutation genetic starts to search; if a genetic value is identified and the genetic mutation has a combined priority relationship, set the genetic value as a junction point. Substep 4 involves moving a genetic mutation to the junction point of the previous position; the original genetic mutation location is sequentially moved forward. The mutation process is performed according to the constraints in (8) and (9).
(2) Two-Point Mutations. Two-point mutations were used in SS and ALB evaluations; the process is shown in Figures 13 and 14.
For SS, Substep1 involves randomly selecting a population of parts to mutate; this population has several related suppliers. In Substep 2, based on this population of parts, a supplier is randomly selected as a cutoff point that becomes the mutation point. In Substep 3, mutation is performed based on supplier capacity constraints. Substep 4 is conducted to validate the demand and supplier capacity constraints; if demand cannot be fulfilled, the next supplier is used as the mutation point. The mutation process must be conducted according to the SS constraints in (7), (12), and (13).
For ALB, Substep1 involves randomly selecting a workstation as a population to mutate according to workstation assembly constraints. Because each assembly must be assigned to a workstation and match the assembly quantity, Substep 2 involves randomly selecting another workstation as a population to mutate to balance the constraint. The mutation process must be completed according to the workstation constraints in (10) and (11).Figure 12
Diagram of guided mutation.Figure 13
Supplier selection by two-point mutation.Figure 14
Assembly line balancing by two-point mutation.Step 9 (elite retention policy).
An elite retention policy is established to retain the elite genetic mutations from evolution; the process is shown in Figure15.
As shown in Figure15, the current generation merger population (P
t) and offspring population (Q
t) then get the 2
N population. Substep 1 involves sorting the 2
N population according to nondominated solutions and dynamic crowding distance calculations. In Substep 2, 50% of the population is retained; if the frontline is the same when sorted, comparisons are based on the dynamic crowding distance. In the solving process, the same frontline and the same population are not repeatedly retained to prevent the local optimum from being achieved.Figure 15
Elitism retention strategy.Step 10 (validation according to stop conditions).
When the number of generations is met and counting is finished, the process is stopped; if not, the process is restarted beginning with Step3.Step 11 (optimal production strategies).
When the desired number of generations is met, the optimal solutions for ASP, SS, and ALB, as well as the mathematical models for minimizing the total order fulfillment time and maximizing assembly line performance, are obtained.


## 3.4.1. Guided-D-NSGA-II Procedure

The detailed procedure of the Guided-D-NSGA-II is shown in Figure4.Figure 4
Guided-D-NSGA-II procedure.A detailed step-by-step description of the algorithm is presented as follows.Step 1 (population coding).
Population codes are divided into three substeps. Substep  1 is ASP coding. Genetic values represent the various product assembly relationships and must comply with constraints (8) and (9). Substep 2 is SS coding and use of real-coded. Genetic values represent the purchases of each supplier and must meet constraints (6), (7), (12), and (13). Substep 3 is ALB coding. Genetic values represent the production quantity of each workstation and must comply with constraints (10) and (11). The population structure is shown in Figure 5.Figure 5
Diagram of gene coding.Step 2 (generating the initial population).
The initial generation is performed based on demand quantity and the constraints of the mathematical model. Defect rate is considered in demand quantity, and the constraints of each combination relationship and priority are considered in ASP. The supplier’s capacity constraints are considered in SS; if the purchase quantity exceeds the supplier’s capacity, another supplier is randomly selected to fulfill the order. The constraints of workstations are considered in ALB.Step 3 (calculating the value of the objective formula).
The initial population is generated into the two objective formulas. Objective formulas (2) are calculated by (3) and (4), and the objective formula (5) is calculate by (3).Step 4 (sorting nondominated solutions).
Nondominated solutions are used for sorting and as a basis for judging the merit population. After a reproduction step, objective formulas for each population and for nondominated solutions sorting are calculated.
First, the population for which the dominated solution is zero is identified. This population is called the first frontline population and is also known as nondominated solutions. The other populations are called dominated solutions; all of the dominated solutions are identified from the remaining population and are defined as the second frontline population. This process is conducted repeatedly until all of the populations are sorted. The sorting process is shown in Figure6.
Figure6(a) indicates that points A–E constituted the first frontline population because they could not dominate each other. Points F–I were then sorted to confirm the absence of the population domination among them and were defined as the second frontline population. Figure 6(b) shows the sorting of all populations.Figure 6
Diagram of nondominated sorting.
(a)
(b)Step 5 (calculating crowding distance).
The first through third frontline populations are sorted in Step4, and all population crowding distances become the size of a reproduction probability basis. Population density is a concept of crowding distance. If the distance between populations is short and the indicated density is high, the reproduction probability is low; if the distance is long and the indicated density is low, reproduction probability is high. Crowding distance is calculated as follows to obtain a uniform population distribution:(14)
C
D
i
=
1
r
∑
k
=
1
r
f
k
i
+
1
-
f
k
i
-
1
i
=
1,2
,
3
,
…
,
j
-
1
,where C
D
i is the crowding distance of i populations, r is the number of the objective formula, k is one value of the objective formula, i is the number of populations, j is the last frontline population, and f
k
i
+
1 and f
k
i
-
1 are population (i
+
1) and population (i
-
1) of the objective formula value k. In each frontline, the distribution of both sides populations is crowded and the distance is set to infinity, as shown in Figure 7.
Luo et al. [9] indicated that crowding distance calculations are deficient. Figure 8 shows that Population B had a gap of f
1 and f
2 that was wider than that of Population F; therefore, the crowding distance of Population B was shorter than that of Population F. A comparison of the crowding distances of Populations B and F indicates that Population F is more favorable than Population B; however, Population B is more favorable than Population F.
Based on this deficiency, Luo et al. [9] proposed the dynamic crowding distance equation:(15)
DCD
i
=
CD
i
log
⁡
1
/
V
i
.
The termV
i is calculated using CD
i equation (15) as shown in(16)
V
i
=
1
r
∑
k
=
1
r
f
k
i
+
1
-
f
k
i
-
1
-
CD
i
2
.
Equation (16) shows the objective formula gap of a neighboring population; when a gap is wider, the probability of reproduction is higher. Calculating the distance with dynamic crowding improves the uniformity and diversity of the population.Figure 7
Diagram of crowding distance.Figure 8
Traditional crowding distance from the uneven distribution.Step 6 (reproduction).
The purpose of reproduction is to identify a favorable population for the crossover step. We used binary tournament selection to identify the elite population according to the following two criteria:(1)
If two frontline populations differ, the lower frontline population is used in the reproduction procedure.
(2)
If two frontline populations are the same, the population with the longer crowding distance is used in the reproduction procedure.Step 7 (crossover).
Genetic codes are exchanged during the crossover procedure, yielding a new, improved generation of children that retain certain features of the previous population. The crossover step was conducted using the two following methods.
(1) Guided Crossover. Guided crossover increased ASP solution efficiency, as shown in Figure 9.
As shown in Figure9, Step 1 of guided crossover involved electing two populations for crossover. Two parents randomly generate each retention block, retention block size, and starting position, and two retention block gene codes are copied to new parent generations in the same position. In addition, the nonretention blocks of gene codes of two populations are copied to the new population. The crossover process must be completed according to the constraints described in (8) and (9).
(2) One-Point Crossover. One-point crossover was used for SS and ASP; the process is shown in Figures 10 and 11.
For SS, Substep1 involves randomly selecting two populations to cross over; Substep 2 entails randomly selecting the parts purchase quantity for the genetic code to be exchanged; the crossover process is completed in Substep 3 according to the SS constraints in (7), (12), and (13).Figure 9
Diagram of guided crossover.Figure 10
Supplier selection by one-point crossover.Figure 11
Assembly line balancing by one-point crossover.For ALB, Substep1 involves randomly selecting two populations to cross over; Substep 2 entails randomly selecting a cutoff point to create crossover blocks and subsequently exchanging the genetic code of the crossover blocks from two populations; the ALB crossover process is completed in Substep 3 according to the ALB constraints in (10) and (11).Step 8 (mutation).
Mutation is the key process of evolution. If a new generation feature does not develop, a local optimum cannot be achieved. The mutation step was conducted using the following two methods.
(1) Guided Mutation. Guided mutation is performed to increase the solution efficiency of ASP; the process is shown in Figure 12.
As shown in Figure12, Substep 1 involves randomly selecting a population to mutate. Substep 2 entails randomly selecting a cutoff point to create a genetic mutation. Substep 3 from mutation genetic starts to search; if a genetic value is identified and the genetic mutation has a combined priority relationship, set the genetic value as a junction point. Substep 4 involves moving a genetic mutation to the junction point of the previous position; the original genetic mutation location is sequentially moved forward. The mutation process is performed according to the constraints in (8) and (9).
(2) Two-Point Mutations. Two-point mutations were used in SS and ALB evaluations; the process is shown in Figures 13 and 14.
For SS, Substep1 involves randomly selecting a population of parts to mutate; this population has several related suppliers. In Substep 2, based on this population of parts, a supplier is randomly selected as a cutoff point that becomes the mutation point. In Substep 3, mutation is performed based on supplier capacity constraints. Substep 4 is conducted to validate the demand and supplier capacity constraints; if demand cannot be fulfilled, the next supplier is used as the mutation point. The mutation process must be conducted according to the SS constraints in (7), (12), and (13).
For ALB, Substep1 involves randomly selecting a workstation as a population to mutate according to workstation assembly constraints. Because each assembly must be assigned to a workstation and match the assembly quantity, Substep 2 involves randomly selecting another workstation as a population to mutate to balance the constraint. The mutation process must be completed according to the workstation constraints in (10) and (11).Figure 12
Diagram of guided mutation.Figure 13
Supplier selection by two-point mutation.Figure 14
Assembly line balancing by two-point mutation.Step 9 (elite retention policy).
An elite retention policy is established to retain the elite genetic mutations from evolution; the process is shown in Figure15.
As shown in Figure15, the current generation merger population (P
t) and offspring population (Q
t) then get the 2
N population. Substep 1 involves sorting the 2
N population according to nondominated solutions and dynamic crowding distance calculations. In Substep 2, 50% of the population is retained; if the frontline is the same when sorted, comparisons are based on the dynamic crowding distance. In the solving process, the same frontline and the same population are not repeatedly retained to prevent the local optimum from being achieved.Figure 15
Elitism retention strategy.Step 10 (validation according to stop conditions).
When the number of generations is met and counting is finished, the process is stopped; if not, the process is restarted beginning with Step3.Step 11 (optimal production strategies).
When the desired number of generations is met, the optimal solutions for ASP, SS, and ALB, as well as the mathematical models for minimizing the total order fulfillment time and maximizing assembly line performance, are obtained.


## 4. Case Study

### 4.1. Case Description

This paper presents the case of a faucet assembly plant. When receiving customer orders, demand must tap 1,000 P1, P2, and P3 products. The faucet assembly factory had four workstations for production.The three faucet products were composed of 30 parts; some of which were common parts. P1, P2, and P3 had 8 common parts, and P1 and P2 had 3 common parts. P1 and P3 and P2 and P3 each had 1 common part; each part was provided by 5 suppliers. Product P1 consisted of 18 parts, divided into 9 combinations of relationships; Product P2 consisted of 15 parts, divided into 8 combinations of relationships; Product P3 consisted of 18 parts, divided into 9 combinations of relationships. The combinations and relationships of the three products are shown in Figure16.Figure 16
Priority of each product assembly sequence.


### 4.2. Experimental Design

This study used the Guided-D-NSGA-II algorithm to determine the optimal efficiency of production. The parameters were population (N), generation (G), crossover rate (Cr), and mutation rate (Mr). The experiment was designed to determine the optimal combination of parameters.Tripathi et al. [31] set N
=
100 when implementing NSGA-II, whereas Li [32] set N
=
200. Rojas et al. [33] set C
r
=
{
0.4,0.5,0.6,0.7,0.8
}, and Rojas et al. [33] set M
r
=
{
0.05,0.1,0.15,0.2
}.Based on the suggestions provided in the literature, we setN as 100 and 200, Cr as 0.4 and 0.6, Mr as 0.1 and 0.2, and G as 100 and 200.To determine solution efficiency, Tsai et al. [34] proposed using the maximum spread (MS), Schaffer [26] used the number of Pareto solutions (NPS), and van Veldhuizen and Lamount [35] used the error ratio (ER). The MS and ER values are calculated using(17)
MS
=
∑
m
=
1
M
max
n
i
=
1
⁡
f
m
i
-
min
n
i
=
1
⁡
f
m
i
2
,
ER
=
∑
i
=
1
n
e
i
n
.The algorithm was implemented 10 times for each parameter combination, and the average MS indicators are calculated and organized in Table1.Table 1
MS average value of each parameter combination table.
Crossover rate (Cr)
Mutation rate (Mr)
Generation (G)
100
200
Population (N)
100
200
100
200
0.4
0.1
518940
1186920
1214120
2300060
0.2
1428260
2113560
1864640
2269960
0.6
0.1
815860
1490580
2376220
1188200
0.2
1136360
790160
1599800
1476180G and N were fixed to observe results of varying the MS C
r and Mr. The four bold data in Table 1 show that, in Case 1, N
=
100, G
=
100, C
r
=
0.4, and Mr = 0.2, in Case 2, N
=
100, G
=
200, Cr = 0.6, and Mr = 0.1, in Case 3, N
=
200, G
=
1000, Cr = 0.4, and Mr = 0.2, and, in Case 4, N
=
200, G
=
200, Cr = 0.4, and Mr = 0.1. The algorithm was implemented 10 times, using Cases 1–4, and the values of NPS and ER were calculated and organized in Tables 2 and 3.Table 2
NPS average value of each parameter combination table.
Case  1
Case  2
Case  3
Case  4
NPS
12.6
33.4
54.2
136.2Table 3
ER average value of each parameter combination table.
Case  1
Case  2
Case  3
Case  4
ER
0.874
0.666
0.729
0.319In Tables2 and 3, the NPS and ER values were the most favorable in Case 4; therefore, we used N
=
200,G
=
200, Cr = 0.4, and Mr = 0.1 as the algorithm parameters.


### 4.3. Case Study Results

To achieve the multiple objectives of this study, the parameters in Case4 were used to compute one of the five optimal solutions, which are shown in Table 4.Table 4
The multiobjective target.
Optimal solution
Minimization of total order fulfillment time
Maximization of assembly line performance
1
11452800
97.05
2
14752800
99.35
3
13955000
98.87
4
12531300
98.52
5
14744200
99.35The third most favorable solution in Table4 was used to determine the optimal supplier portfolio and production decisions, as shown in Table 5.Table 5
Optimal supplier and purchase planning.
Purchase quantity
Supplier
1
2
3
4
5
Parts
I
1
0
0
1786
1500
0
I
2
0
0
1786
2000
0
I
3
1286
0
2000
0
0
I
4
0
0
1786
1500
0
I
5
1286
0
2000
0
0Table5 lists parts I
1
–
I
5 of suppliers and the purchase quantity portfolio; the results were determined according to the capacity constraints of suppliers and assembly constraints to fulfill demand.Table6 lists the three products and the workstation distribution of assembly sequences. The products were assembled according to assembly and workstation constraints. To measure ALB performance, Erel and Sarin [18] proposed using line balancing efficiency (LBE) and balance delay, which are calculated using(18)
LBE
=
∑
t
i
N
·
t
m
a
x
×
100
%
,
(19)
Balance  Delay
=
1
-
LBE
.Table 6
Product and workstation of assembly sequence.
Product
Workstation 1
Workstation 2
Workstation 3
Workstation 4
P
1
C
6
→
C
3
→
C
4
C
5
C
7
→
C
2
→
C
1
C
8
→
C
9
P
2
C
2
→
C
4
→
C
3
C
5
C
7
→
C
6
→
C
1
C
8
P
3
C
5
→
C
2
C
8
→
C
4
→
C
1
→
C
6
C
3
C
7
→
C
9
ProductionCycle time
2325
2425
2550
2600Table6 shows that when using (18) the production cycle time, the LBE value was 95.1%; a higher LBE value indicates higher efficiency. The balance delay was 4.9%. In general, the balance delay was less than 5% better efficiency. The LBE and balance delay values show that the workstations were assigned to meet ALB criteria, facilitating smooth production at individual workstations and increasing production efficiency.The two-dimensional coordinate diagram in Figure17 shows the solution distribution.Figure 17
The optimal solution distribution by using Guided-D-NSGA-II.Figure17 shows that the results of the proposed Guided-D-NSGA-II algorithm provided clear, diverse solutions for the distribution of the Plato frontline, indicating that the dynamics of crowding distance were effective.


## 4.1. Case Description

This paper presents the case of a faucet assembly plant. When receiving customer orders, demand must tap 1,000 P1, P2, and P3 products. The faucet assembly factory had four workstations for production.The three faucet products were composed of 30 parts; some of which were common parts. P1, P2, and P3 had 8 common parts, and P1 and P2 had 3 common parts. P1 and P3 and P2 and P3 each had 1 common part; each part was provided by 5 suppliers. Product P1 consisted of 18 parts, divided into 9 combinations of relationships; Product P2 consisted of 15 parts, divided into 8 combinations of relationships; Product P3 consisted of 18 parts, divided into 9 combinations of relationships. The combinations and relationships of the three products are shown in Figure16.Figure 16
Priority of each product assembly sequence.


## 4.2. Experimental Design

This study used the Guided-D-NSGA-II algorithm to determine the optimal efficiency of production. The parameters were population (N), generation (G), crossover rate (Cr), and mutation rate (Mr). The experiment was designed to determine the optimal combination of parameters.Tripathi et al. [31] set N
=
100 when implementing NSGA-II, whereas Li [32] set N
=
200. Rojas et al. [33] set C
r
=
{
0.4,0.5,0.6,0.7,0.8
}, and Rojas et al. [33] set M
r
=
{
0.05,0.1,0.15,0.2
}.Based on the suggestions provided in the literature, we setN as 100 and 200, Cr as 0.4 and 0.6, Mr as 0.1 and 0.2, and G as 100 and 200.To determine solution efficiency, Tsai et al. [34] proposed using the maximum spread (MS), Schaffer [26] used the number of Pareto solutions (NPS), and van Veldhuizen and Lamount [35] used the error ratio (ER). The MS and ER values are calculated using(17)
MS
=
∑
m
=
1
M
max
n
i
=
1
⁡
f
m
i
-
min
n
i
=
1
⁡
f
m
i
2
,
ER
=
∑
i
=
1
n
e
i
n
.The algorithm was implemented 10 times for each parameter combination, and the average MS indicators are calculated and organized in Table1.Table 1
MS average value of each parameter combination table.
Crossover rate (Cr)
Mutation rate (Mr)
Generation (G)
100
200
Population (N)
100
200
100
200
0.4
0.1
518940
1186920
1214120
2300060
0.2
1428260
2113560
1864640
2269960
0.6
0.1
815860
1490580
2376220
1188200
0.2
1136360
790160
1599800
1476180G and N were fixed to observe results of varying the MS C
r and Mr. The four bold data in Table 1 show that, in Case 1, N
=
100, G
=
100, C
r
=
0.4, and Mr = 0.2, in Case 2, N
=
100, G
=
200, Cr = 0.6, and Mr = 0.1, in Case 3, N
=
200, G
=
1000, Cr = 0.4, and Mr = 0.2, and, in Case 4, N
=
200, G
=
200, Cr = 0.4, and Mr = 0.1. The algorithm was implemented 10 times, using Cases 1–4, and the values of NPS and ER were calculated and organized in Tables 2 and 3.Table 2
NPS average value of each parameter combination table.
Case  1
Case  2
Case  3
Case  4
NPS
12.6
33.4
54.2
136.2Table 3
ER average value of each parameter combination table.
Case  1
Case  2
Case  3
Case  4
ER
0.874
0.666
0.729
0.319In Tables2 and 3, the NPS and ER values were the most favorable in Case 4; therefore, we used N
=
200,G
=
200, Cr = 0.4, and Mr = 0.1 as the algorithm parameters.


## 4.3. Case Study Results

To achieve the multiple objectives of this study, the parameters in Case4 were used to compute one of the five optimal solutions, which are shown in Table 4.Table 4
The multiobjective target.
Optimal solution
Minimization of total order fulfillment time
Maximization of assembly line performance
1
11452800
97.05
2
14752800
99.35
3
13955000
98.87
4
12531300
98.52
5
14744200
99.35The third most favorable solution in Table4 was used to determine the optimal supplier portfolio and production decisions, as shown in Table 5.Table 5
Optimal supplier and purchase planning.
Purchase quantity
Supplier
1
2
3
4
5
Parts
I
1
0
0
1786
1500
0
I
2
0
0
1786
2000
0
I
3
1286
0
2000
0
0
I
4
0
0
1786
1500
0
I
5
1286
0
2000
0
0Table5 lists parts I
1
–
I
5 of suppliers and the purchase quantity portfolio; the results were determined according to the capacity constraints of suppliers and assembly constraints to fulfill demand.Table6 lists the three products and the workstation distribution of assembly sequences. The products were assembled according to assembly and workstation constraints. To measure ALB performance, Erel and Sarin [18] proposed using line balancing efficiency (LBE) and balance delay, which are calculated using(18)
LBE
=
∑
t
i
N
·
t
m
a
x
×
100
%
,
(19)
Balance  Delay
=
1
-
LBE
.Table 6
Product and workstation of assembly sequence.
Product
Workstation 1
Workstation 2
Workstation 3
Workstation 4
P
1
C
6
→
C
3
→
C
4
C
5
C
7
→
C
2
→
C
1
C
8
→
C
9
P
2
C
2
→
C
4
→
C
3
C
5
C
7
→
C
6
→
C
1
C
8
P
3
C
5
→
C
2
C
8
→
C
4
→
C
1
→
C
6
C
3
C
7
→
C
9
ProductionCycle time
2325
2425
2550
2600Table6 shows that when using (18) the production cycle time, the LBE value was 95.1%; a higher LBE value indicates higher efficiency. The balance delay was 4.9%. In general, the balance delay was less than 5% better efficiency. The LBE and balance delay values show that the workstations were assigned to meet ALB criteria, facilitating smooth production at individual workstations and increasing production efficiency.The two-dimensional coordinate diagram in Figure17 shows the solution distribution.Figure 17
The optimal solution distribution by using Guided-D-NSGA-II.Figure17 shows that the results of the proposed Guided-D-NSGA-II algorithm provided clear, diverse solutions for the distribution of the Plato frontline, indicating that the dynamics of crowding distance were effective.


## 5. Conclusion

In a globalized competitive environment with highly customized products, assembly plants must respond quickly to demand. SCM and production management are key factors of competition. We constructed a multiobjective optimization model to assist decision makers in planning production according to sales orders.The multiobjective optimization model was empirically tested using the case of a faucet assembly plant. The results showed that the integrated multiobjective algorithm, the Guided-D-NSGA-II, is suitable for solving multiobjective problems, and all of the solutions were determined according to constraints. ALB was achieved to increase production efficiency in an assembly plant, as shown in Figure17. The Guided-D-NSGA-II yielded results that clearly converged to the Plato frontline and provided decision makers with diverse solutions.We built a multiobjective optimization model that assists decision makers in planning production and conducting SS according to sales orders, enabling production activities to achieve maximum efficiency and the competitiveness of firms to improve. Finally, this paper provides the following suggestions for future research:(1)
SS can be extended to multiple periods and the due date of parts can be increased to explore the inventory impact of SS.
(2)
The supply of parts and the numbers of suppliers can be changed.
(3)
Factors of multi-assembly-plant production planning, such as how to split sales orders to each assembly plant and the resulting additional assembly constraints, can be discussed.
(4)
The effect of various selection criteria, such as reliability, quality, and service level, on SS can be studied.



---

*Source: 260205-2015-08-04.xml*