# A Novel Assembly Line Balancing Method Based on PSO Algorithm

Authors: Xiaomei Hu; Yangyang Zhang; Ning Zeng; Dong Wang
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Assembly line is widely used in manufacturing system. Assembly line balancing problem is a crucial question during design and management of assembly lines since it directly affects the productivity of the whole manufacturing system. The model of assembly line balancing problem is put forward and a general optimization method is proposed. The key data on assembly line balancing problem is confirmed, and the precedence relations diagram is described. A double objective optimization model based on takt time and smoothness index is built, and balance optimization scheme based on PSO algorithm is proposed. Through the simulation experiments of examples, the feasibility and validity of the assembly line balancing method based on PSO algorithm is proved.


---

## Body

## 1. Introduction

With the progress and development of science and technology, manufacturing has transformed from the simple process documented by individual behavior and single machine to the complicated one conducted by manufacture system composed of many manufacture components [1]. Assembly line is an effective combination of man and machine, and it is the most widely used production mode in the manufacturing industry. The advanced manufacturing models, such as Flexible Automation Manufacturing, Agile Manufacturing, JIT Manufacturing, and Networked-Manufacturing, are constantly emerging. Manufacturing technology develops towards systematical, flexible, integrated, reconfigurable, networked, intelligent, green renewable, and other directions [2]. The transformation of manufacturing mode and manufacturing technology has influenced the manufacturing system planning, design, operation, and management deeply.Manufacturing enterprises mainly produce in the continuous production line with multiple and fine-sorted process. Fine-sorted work forms are used in the assembly production. On the one hand, it improves the proficiency of operators and the efficiency of production; on the other hand, it also causes each assembly process not to be able to consume the same time in theory and reality. Load unbalance in assembly line can lead to workpiece accumulation and even the termination of production line [3–6]. Assembly line balancing is to equalize all the assembly processes by adjusting the work load of each process to make the job time of each process as close as possible. Balancing assembly line is beneficial to enhance the work efficiency of operator and equipment and reduce the consumption of single product working hours [7–9]. Therefore, the study of the assembly line balancing problem has important theoretical value and practical significance.At present, some studies aim to solve the line balancing problem. Chartlton uses mathematical analysis method and proposes the branch and bound method to solve the assembly line balancing [10]. Gao and Sun put forward a measure of action analysis improvement to improve the production rate of balance by reducing the operation time [11]. With the deepening of the research, the intelligent algorithm is considered to solve the production line balance problem recently. Chen and Zhang propose improved ant colony algorithm, and the ant scheme generation measuring method is given to compute homework allocation plan [12], and the research on line balancing problem with certain station numbers is also carried on [13]. However, there have been few researches on multiobjective optimization of production line balance problem nowadays. Takt time and smoothness index are two important indicators to measure the assembly line balancing. Takt time is referring to the interval time of completing the same two products continuously and smoothness index is a measurement index of the discrete state of location homework time distribution.Multiobjective optimization of production line balancing problem is studied in this paper. The integrated optimal function of takt time and smoothness index is defined, and a novel optimization method of assembly line balancing based on PSO algorithm is proposed since the PSO algorithm has the advantage of high solution speed, high solution quality, and good robustness [14].


## 2. The Mathematical Model of Assembly Line Balancing Problem

### 2.1. The Description of the Assembly Line Balancing Problem

#### 2.1.1. The Main Parameters of Production Line Balancing Problem

The main parameters of production line balancing problem are represented as follows [15].(1) Job Element and Standard Work Time. Job element divides assemble into unit operations, and these unit operations cannot or need not be divided in general. Standard work time is the time to complete an operation of a job element. Job element and standard work time are one to one correspondence relation. 1,2
,
3
,
…
,
n express the job elements and t
j is the standard work time of job element j.(
2
) Production Line Balancing Rate
P. Production line balancing rate P is the expression of the balance of the whole or part of production lines and continuous condition. It is an important index to measure the production line balancing. It can be defined as
(1)
P
=
∑
j
=
1
n
t
j
m
*
max
⁡
(
T
i
)
.
In (1), t
j is the expression of standard work time of the j job elements, n represents the number of the work elements, m represents the number of total stations in assembly lines, T
i represents the work time in the i station, and max
⁡
(
T
i
) represents the biggest station operating time, namely, the bottleneck station time.(
3
) Takt Time
T
T. Takt time TT is the work time between two consecutive products or batches. It can be defined as
(2)
TT
=
Tw
Q
.
In (2), Tw represents the total effective work time in the plan period and Q represents the production quantity in the plan period.(
4
) Smoothness Index
S
I. Smoothness index is the evaluation of time distribution of discrete conditions of the whole or part of the production line. It represents the deviation degree of operation time between each station in the whole or part of the production line. The greater the value of SI, the greater the homework time distribution of production line location deviation. It can be defined as
(3)
SI
=
∑
i
=
1
m
(
TT
-
T
i
)
2
m
.(
5
) The Precedence Relations Diagram and Relationship Matrix. The precedence relations diagram is a directed graph G without a loop. It expresses the process sequence of job elements in graphic method according to the priority constraints:
(4)
G
=
(
E
,
P
)
.
In (4), node E is a set of job elements:
(5)
E
=
{
1,2
,
3
,
…
,
n
}
.
Arc
P represents the successive relationship sets between assembly work in the graph.Relationship matrixM is the matrix transformed by the priority constraints based on precedence relations diagram. The conversion relationship between the precedence relations diagram and relationship matrix can be expressed as follows.WhenM
i
j
=
1, the job element i is the first operation before the job element j. At this time, the station of the job element i must be arranged before the job element j [16]. The precedence relations diagram of a simple assembly line with eight operating elements is shown in Figure 1. And its relationship matrix is shown in
(6)
M
=
[
0
1
1
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
]
.Figure 1
Precedence relations diagram.


#### 2.1.2. The Classification of the Line Balancing Problem

There are three kinds of line balancing problem.(1)
The objective function of the first kind assembly line balancing problem is to maximize the production line balancing rateP with certain takt time TT. It is equivalent to minimizing the number of stations m with certain takt time. It can be expressed as
(7)
max
⁡
P
=
∑
j
=
1
n
t
j
m
*
max
⁡
(
T
i
)
×
100
⟺
min
⁡
m
.
(2)
The objective function of the second kind assembly line balancing problem is to maximize the production line balancing rateP with certain station number m. It is equivalent to minimizing the takt time TT with certain location numbers m. It can be expressed as
(8)
max
⁡
P
=
∑
j
=
1
n
t
j
m
*
max
⁡
(
T
i
)
×
100
⟺
min
⁡
TT
.
(3)
The objective function of the third kind assembly line balancing problem is to minimize the smoothness indexSI with certain takt time TT and station numbers m. It can be expressed as
(9)
min
⁡
SI
=
∑
i
=
1
m
(
TT
-
T
i
)
2
m
.The general description of the assembly line balancing problem with certain station numbers is shown as follows [17].Assume that the assembly line is expressed with a given directed graph without a loopG
=
(
E
,
P
); assembly line balancing problem with certain station numbers m can be described to confirm the division {
S
k
∣
k
=
1,2
,
3
,
…
,
m
} in E
=
{
1,2
,
3
,
…
,
n
} on the premise of successive relationship.


### 2.2. A Multiobjective Optimization Model

According to the classification description of the assembly line balancing problem, three kinds of assembly line balancing problems belong to optimization problem in fact [18]. Optimizing a certain goal in the process of actual assembly individually may cause the neglect of relevance of balance goals. As a result, the optimization results are often not accord with the actual situation of assembly process [19]. In this paper, the fitness function f
1 and the objective function min
⁡
f
1 are constructed to realize the comprehensive optimal goals of the takt time TT and smooth index SI in assembly lines in consideration that the layout of assembly line and the station number certain m is fixed.Fitness function is defined as(10)
f
1
=
b
1
*
TT
+
b
2
*
SI
.Constraint conditions are as follows:(11)
TT
=
max
⁡
(
T
i
)
,
(
i
=
1,2
,
…
,
m
)
,
(12)
S
i
∩
S
j
=
Ø
,
(
i
≠
j
,
i
,
j
=
1,2
,
…
,
m
)
,
(13)
E
=
⋃
k
=
1
m
S
k
,
(
k
=
1,2
,
…
,
m
)
,
(14)
T
(
S
k
)
⩽
TT
,
(
k
=
1,2
,
…
,
m
)
,
(15)
if
M
i
j
=
1
,
i
⊂
A
x
,
j
⊂
A
y
;
then
x
≤
y
,
M
=
(
M
i
j
)
n
×
n
.The fitness functionf
1 takes advantage of the linear weighted average model of takt time TT and smoothness index SI in assembly line. The first part of f
1 is used to evaluate the balance of assembly line and the second part of f
1 is used to evaluate the speed of assembly line production. b
1 and b
2 are weight value, and b
1
+
b
2
=
1. Specific values can also be used according to the specific situation.In the constraint conditions,n and m are constant; n is the number of job elements; m is the number of location. In (12), there is no overlap between the different stations, because the same job elements could only be distributed in one location. In (13), all the job elements should be assigned [20]. In (14), the maximum operation time of station is the takt time. Formula (15) is used to establish the distribution relations of job elements on the basis of precedence relation matrix.


### 2.3. The Solution of the Assembly Line Balancing Problem

Two distribution solutions are applied to solve the objective functionmin
⁡
f
1.(1)
To solve a problem, a production line balancing problem with certain station numbers, a series of classification schemes of job elements{
S
k
∣
k
=
1,2
,
3
,
…
,
m
} with smaller takt time from job elements set E
=
{
1,2
,
3
,
…
,
n
} are concluded. A kind of coding based on two-dimensional particle is proposed to express and update the arrangement of operating elements.
(2)
According to classification schemes of job elementsS
k in step one, each value of smooth index in job element arrangement scheme is calculated and the classification scheme of job elements {
S
k
∣
k
=
1,2
,
3
,
…
,
m
} with minimum value of objective function min
⁡
f
1 is taken as the optimal arrangement scheme.


## 2.1. The Description of the Assembly Line Balancing Problem

### 2.1.1. The Main Parameters of Production Line Balancing Problem

The main parameters of production line balancing problem are represented as follows [15].(1) Job Element and Standard Work Time. Job element divides assemble into unit operations, and these unit operations cannot or need not be divided in general. Standard work time is the time to complete an operation of a job element. Job element and standard work time are one to one correspondence relation. 1,2
,
3
,
…
,
n express the job elements and t
j is the standard work time of job element j.(
2
) Production Line Balancing Rate
P. Production line balancing rate P is the expression of the balance of the whole or part of production lines and continuous condition. It is an important index to measure the production line balancing. It can be defined as
(1)
P
=
∑
j
=
1
n
t
j
m
*
max
⁡
(
T
i
)
.
In (1), t
j is the expression of standard work time of the j job elements, n represents the number of the work elements, m represents the number of total stations in assembly lines, T
i represents the work time in the i station, and max
⁡
(
T
i
) represents the biggest station operating time, namely, the bottleneck station time.(
3
) Takt Time
T
T. Takt time TT is the work time between two consecutive products or batches. It can be defined as
(2)
TT
=
Tw
Q
.
In (2), Tw represents the total effective work time in the plan period and Q represents the production quantity in the plan period.(
4
) Smoothness Index
S
I. Smoothness index is the evaluation of time distribution of discrete conditions of the whole or part of the production line. It represents the deviation degree of operation time between each station in the whole or part of the production line. The greater the value of SI, the greater the homework time distribution of production line location deviation. It can be defined as
(3)
SI
=
∑
i
=
1
m
(
TT
-
T
i
)
2
m
.(
5
) The Precedence Relations Diagram and Relationship Matrix. The precedence relations diagram is a directed graph G without a loop. It expresses the process sequence of job elements in graphic method according to the priority constraints:
(4)
G
=
(
E
,
P
)
.
In (4), node E is a set of job elements:
(5)
E
=
{
1,2
,
3
,
…
,
n
}
.
Arc
P represents the successive relationship sets between assembly work in the graph.Relationship matrixM is the matrix transformed by the priority constraints based on precedence relations diagram. The conversion relationship between the precedence relations diagram and relationship matrix can be expressed as follows.WhenM
i
j
=
1, the job element i is the first operation before the job element j. At this time, the station of the job element i must be arranged before the job element j [16]. The precedence relations diagram of a simple assembly line with eight operating elements is shown in Figure 1. And its relationship matrix is shown in
(6)
M
=
[
0
1
1
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
]
.Figure 1
Precedence relations diagram.


### 2.1.2. The Classification of the Line Balancing Problem

There are three kinds of line balancing problem.(1)
The objective function of the first kind assembly line balancing problem is to maximize the production line balancing rateP with certain takt time TT. It is equivalent to minimizing the number of stations m with certain takt time. It can be expressed as
(7)
max
⁡
P
=
∑
j
=
1
n
t
j
m
*
max
⁡
(
T
i
)
×
100
⟺
min
⁡
m
.
(2)
The objective function of the second kind assembly line balancing problem is to maximize the production line balancing rateP with certain station number m. It is equivalent to minimizing the takt time TT with certain location numbers m. It can be expressed as
(8)
max
⁡
P
=
∑
j
=
1
n
t
j
m
*
max
⁡
(
T
i
)
×
100
⟺
min
⁡
TT
.
(3)
The objective function of the third kind assembly line balancing problem is to minimize the smoothness indexSI with certain takt time TT and station numbers m. It can be expressed as
(9)
min
⁡
SI
=
∑
i
=
1
m
(
TT
-
T
i
)
2
m
.The general description of the assembly line balancing problem with certain station numbers is shown as follows [17].Assume that the assembly line is expressed with a given directed graph without a loopG
=
(
E
,
P
); assembly line balancing problem with certain station numbers m can be described to confirm the division {
S
k
∣
k
=
1,2
,
3
,
…
,
m
} in E
=
{
1,2
,
3
,
…
,
n
} on the premise of successive relationship.


## 2.1.1. The Main Parameters of Production Line Balancing Problem

The main parameters of production line balancing problem are represented as follows [15].(1) Job Element and Standard Work Time. Job element divides assemble into unit operations, and these unit operations cannot or need not be divided in general. Standard work time is the time to complete an operation of a job element. Job element and standard work time are one to one correspondence relation. 1,2
,
3
,
…
,
n express the job elements and t
j is the standard work time of job element j.(
2
) Production Line Balancing Rate
P. Production line balancing rate P is the expression of the balance of the whole or part of production lines and continuous condition. It is an important index to measure the production line balancing. It can be defined as
(1)
P
=
∑
j
=
1
n
t
j
m
*
max
⁡
(
T
i
)
.
In (1), t
j is the expression of standard work time of the j job elements, n represents the number of the work elements, m represents the number of total stations in assembly lines, T
i represents the work time in the i station, and max
⁡
(
T
i
) represents the biggest station operating time, namely, the bottleneck station time.(
3
) Takt Time
T
T. Takt time TT is the work time between two consecutive products or batches. It can be defined as
(2)
TT
=
Tw
Q
.
In (2), Tw represents the total effective work time in the plan period and Q represents the production quantity in the plan period.(
4
) Smoothness Index
S
I. Smoothness index is the evaluation of time distribution of discrete conditions of the whole or part of the production line. It represents the deviation degree of operation time between each station in the whole or part of the production line. The greater the value of SI, the greater the homework time distribution of production line location deviation. It can be defined as
(3)
SI
=
∑
i
=
1
m
(
TT
-
T
i
)
2
m
.(
5
) The Precedence Relations Diagram and Relationship Matrix. The precedence relations diagram is a directed graph G without a loop. It expresses the process sequence of job elements in graphic method according to the priority constraints:
(4)
G
=
(
E
,
P
)
.
In (4), node E is a set of job elements:
(5)
E
=
{
1,2
,
3
,
…
,
n
}
.
Arc
P represents the successive relationship sets between assembly work in the graph.Relationship matrixM is the matrix transformed by the priority constraints based on precedence relations diagram. The conversion relationship between the precedence relations diagram and relationship matrix can be expressed as follows.WhenM
i
j
=
1, the job element i is the first operation before the job element j. At this time, the station of the job element i must be arranged before the job element j [16]. The precedence relations diagram of a simple assembly line with eight operating elements is shown in Figure 1. And its relationship matrix is shown in
(6)
M
=
[
0
1
1
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
]
.Figure 1
Precedence relations diagram.


## 2.1.2. The Classification of the Line Balancing Problem

There are three kinds of line balancing problem.(1)
The objective function of the first kind assembly line balancing problem is to maximize the production line balancing rateP with certain takt time TT. It is equivalent to minimizing the number of stations m with certain takt time. It can be expressed as
(7)
max
⁡
P
=
∑
j
=
1
n
t
j
m
*
max
⁡
(
T
i
)
×
100
⟺
min
⁡
m
.
(2)
The objective function of the second kind assembly line balancing problem is to maximize the production line balancing rateP with certain station number m. It is equivalent to minimizing the takt time TT with certain location numbers m. It can be expressed as
(8)
max
⁡
P
=
∑
j
=
1
n
t
j
m
*
max
⁡
(
T
i
)
×
100
⟺
min
⁡
TT
.
(3)
The objective function of the third kind assembly line balancing problem is to minimize the smoothness indexSI with certain takt time TT and station numbers m. It can be expressed as
(9)
min
⁡
SI
=
∑
i
=
1
m
(
TT
-
T
i
)
2
m
.The general description of the assembly line balancing problem with certain station numbers is shown as follows [17].Assume that the assembly line is expressed with a given directed graph without a loopG
=
(
E
,
P
); assembly line balancing problem with certain station numbers m can be described to confirm the division {
S
k
∣
k
=
1,2
,
3
,
…
,
m
} in E
=
{
1,2
,
3
,
…
,
n
} on the premise of successive relationship.


## 2.2. A Multiobjective Optimization Model

According to the classification description of the assembly line balancing problem, three kinds of assembly line balancing problems belong to optimization problem in fact [18]. Optimizing a certain goal in the process of actual assembly individually may cause the neglect of relevance of balance goals. As a result, the optimization results are often not accord with the actual situation of assembly process [19]. In this paper, the fitness function f
1 and the objective function min
⁡
f
1 are constructed to realize the comprehensive optimal goals of the takt time TT and smooth index SI in assembly lines in consideration that the layout of assembly line and the station number certain m is fixed.Fitness function is defined as(10)
f
1
=
b
1
*
TT
+
b
2
*
SI
.Constraint conditions are as follows:(11)
TT
=
max
⁡
(
T
i
)
,
(
i
=
1,2
,
…
,
m
)
,
(12)
S
i
∩
S
j
=
Ø
,
(
i
≠
j
,
i
,
j
=
1,2
,
…
,
m
)
,
(13)
E
=
⋃
k
=
1
m
S
k
,
(
k
=
1,2
,
…
,
m
)
,
(14)
T
(
S
k
)
⩽
TT
,
(
k
=
1,2
,
…
,
m
)
,
(15)
if
M
i
j
=
1
,
i
⊂
A
x
,
j
⊂
A
y
;
then
x
≤
y
,
M
=
(
M
i
j
)
n
×
n
.The fitness functionf
1 takes advantage of the linear weighted average model of takt time TT and smoothness index SI in assembly line. The first part of f
1 is used to evaluate the balance of assembly line and the second part of f
1 is used to evaluate the speed of assembly line production. b
1 and b
2 are weight value, and b
1
+
b
2
=
1. Specific values can also be used according to the specific situation.In the constraint conditions,n and m are constant; n is the number of job elements; m is the number of location. In (12), there is no overlap between the different stations, because the same job elements could only be distributed in one location. In (13), all the job elements should be assigned [20]. In (14), the maximum operation time of station is the takt time. Formula (15) is used to establish the distribution relations of job elements on the basis of precedence relation matrix.


## 2.3. The Solution of the Assembly Line Balancing Problem

Two distribution solutions are applied to solve the objective functionmin
⁡
f
1.(1)
To solve a problem, a production line balancing problem with certain station numbers, a series of classification schemes of job elements{
S
k
∣
k
=
1,2
,
3
,
…
,
m
} with smaller takt time from job elements set E
=
{
1,2
,
3
,
…
,
n
} are concluded. A kind of coding based on two-dimensional particle is proposed to express and update the arrangement of operating elements.
(2)
According to classification schemes of job elementsS
k in step one, each value of smooth index in job element arrangement scheme is calculated and the classification scheme of job elements {
S
k
∣
k
=
1,2
,
3
,
…
,
m
} with minimum value of objective function min
⁡
f
1 is taken as the optimal arrangement scheme.


## 3. The Assembly Line Balance Optimization Algorithm Based on PSO

### 3.1. Particle Swarm Optimization Algorithm

(1)
The basic idea of particle swarm optimization: the particle swarm optimization was first put forward in 1995 by the American social psychologist J. Kennedy and electrical engineer R. Eberhart on the basis of the study of the behavior of birds group in the early time [21]. PSO treats each individual as a particle which has no weight and volume in n dimensional search space and the particle flies at a certain speed in the search space. The speed is dynamically adjusted based on the flying experience of individual and group.
(2)
The basic mathematical model of PSO algorithm [22–24].In the n dimensional space, X
i
=
(
x
i
1
,
x
i
2
,
…
,
x
i
n
) express a current position of particle i.V
i
=
(
v
i
1
,
v
i
2
,
…
,
v
i
n
) express that the speed v
i is the current speed of particle i.P
i
=
(
p
i
1
,
p
i
2
,
…
,
p
i
n
) express the best experiencing position of particle i; namely, P
i has the smallest fitness.Assume thatf
(
x
) is the minimized objective function, the best position of particle i is calculated as follows:
(16)
P
i
(
t
+
1
)
=
{
P
i
(
t
)
f
(
P
i
(
t
)
)
≤
f
(
X
i
(
t
+
1
)
)
X
i
(
t
+
1
)
f
(
P
i
(
t
)
)
>
f
(
X
i
(
t
+
1
)
)
.Assume that the number of particles iss in population; all particles have experienced the best position P
g
(
t
); then
(17)
P
g
(
t
)
∈
{
P
0
(
t
)
,
…
,
P
g
(
t
)
}
∣
f
(
P
g
(
t
)
)
hiihh
=
min
⁡
{
f
(
P
0
(
t
)
)
,
…
,
f
(
P
s
(
t
)
)
}
.
PSO algorithm basic solving equations are as follows [25, 26].Speed evolution equation is shown as(18)
V
i
(
t
+
1
)
=
w
V
i
(
t
)
+
c
1
r
1
(
p
i
(
t
)
-
x
i
(
t
)
)
+
c
2
r
2
(
p
g
(
t
)
-
X
i
(
t
)
)
.
Position evolution equation is shown as
(19)
X
i
(
t
+
1
)
=
X
i
(
t
)
+
V
i
(
t
+
1
)
.In (18), c
1 and c
2 are the acceleration constant, which take the value in [
0,2
].  r
1 and r
2 both are a random number between 1 and 2; w is inertia coefficient between 0 and 1 and it has the ability of keeping inertia expansion of particle movement to explore new areas.


### 3.2. Parameter Setting of PSO

The parameters of particle swarm optimization algorithm include population quantityN, the number of iterations G, inertia weight w, accelerated constant c, and the initial position and velocity of each particle.


### 3.3. Coding of Assembly Line Balancing Problem

The most important job is to code in order to solve the assembly line balancing problem using PSO algorithm. There are many coding methods for the scheduling problem. Among the numerous coding methods, coding based on workpiece, coding based on machine, and coding based on operation are used in the optimization problem frequently [27–29].In view of the particularity of assembly line balancing problem, as well as the limitations of general coding method, a coding method based on job elements is adopted in this paper. AOV-net coding basic ideas are used to encode the precedence relations diagram of job element [30].The basic steps of AOV-net basic coding are as follows.(1)
Output the node which has no precursors in AOV-net table.
(2)
Remove the selected node and the arc which takes the selected node as starting point form the map; the rest of the vertices still constitute the AOV-net.
(3)
Repeat(
1
) and (
2
) until outputting all the nodes, the vertex sequencing is a topological sort.Since the precedence relations diagram of job element contains two parts, namely, job element and standard work time, a two-dimensional particle expressive method is proposed [31]. Assume the total number of job elements are N; a two-dimensional particle with length N is created: the first dimension corresponds the order of job elements; the second dimension corresponds standard work time t
i
(
i
=
1,2
,
3
,
…
,
N
) of each job element, and each job element has a corresponding standard work time. If the order of job element changes, the arrangement of standard work time also changes.The precedence relations diagram of an assembly line with ten job elements is shown in Figure2.Figure 2
Precedence relations diagram with ten job elements.Two particles are coded and shown in Tables1 and 2.Table 1
The code of particle one.
Job element
1
2
3
4
5
6
7
9
8
10
Standard work time (t
i)
1.3
0.9
1.8
1.1
0.9
1.2
1.3
2.0
1.8
1.1Table 2
The code of particle two.
Job element
1
3
4
2
6
5
7
9
8
10
Standard work time (t
i)
1.3
1.8
1.1
0.9
1.2
0.9
1.3
2.0
1.8
1.1


### 3.4. The Particle Updating Formula of PSO Algorithm

The particle updating formula is defined as(20)
X
i
(
t
+
1
)
=
c
2
⊗
g
{
c
1
⊗
g
[
w
⊗
h
x
,
y
(
X
i
(
t
)
)
,
p
B
i
(
t
)
]
,
g
B
i
(
t
)
}
.
In (20), X
i
(
t
+
1
) express the positions of particle i in the t iterations.c
1 and c
2 are the acceleration constant, and w is the inertia coefficient. Moreover, their values are between 0 and 1. h
x
,
y
(
X
i
(
t
)
) express the exchange of the x component and the y component. x and y are two different random integers between 1 and n (the number of job elements). p
B
i
(
t
) is the best position of particle i in t iterations. g
B
i
(
t
) is the best position of group in t iterations.The formula (20) includes three parts.The first part is the updating of particle position:(21)
V
i
(
t
)
=
w
⊗
h
x
,
y
(
X
i
(
t
)
)
=
{
h
x
,
y
(
X
i
(
t
)
)
rand
(
)
<
w
X
i
(
t
)
rand
(
)
≥
w
.The second part is the adjustment of the particlep
B
i
(
t
) based on its best position:
(22)
F
i
(
t
)
=
c
1
⊗
g
(
V
i
(
t
)
,
p
B
i
(
t
)
)
=
{
g
(
V
i
(
t
)
,
p
B
i
(
t
)
)
rand
(
)
<
c
1
V
i
(
t
)
rand
(
)
≥
c
1
.The third part is the adjustment of the particle based on the best positiong
B
i
(
t
) in the group:
(23)
X
i
(
t
+
1
)
=
c
2
⊗
g
(
F
i
(
t
)
,
g
B
i
(
t
)
)
=
{
g
(
F
i
(
t
)
,
g
B
i
(
t
)
)
rand
(
)
<
c
2
F
i
(
t
)
rand
(
)
≥
c
2
.
rand
(
) is a random uniform distribution number. The meaning of function g
(
V
i
(
t
)
,
p
B
i
(
t
)
) is the adjustment of particles according to its best position in the i iteration. The specific implementation processes are as follows.(1)
Whenrand
(
)
⩾
c
1, F
i
(
t
)
=
V
i
(
t
).
(2)
When rand(
)
<
c
1, execute g
(
V
i
(
t
)
,
p
B
i
(
t
)
). Take p
B
i
t
(
t
) as the best position in the i iteration; n is the number of job elements. An integer from 1 to n is randomly selected to make p
B
i
t
(
t
) be divided into two sets {
S
(
1
)
i
,
j
}, {
S
(
2
)
i
,
j
}.
(3)
An expressive method of two-dimensional particle is adopted to update the arrangement of job elements.x
1
,
j
(
t
) express the job elements arrangement of V
i
(
t
) and z
1
,
l
(
t
) expresses the new arrangement F
i
(
t
). Take l
=
1, j
=
1.
(4)
Ifx
1
,
j
(
t
)
∈
S
(
1
)
1
,
j, z
1
,
l
(
t
)
=
x
1
,
j
(
t
); if p
B
i
(
t
)
∈
S
(
2
)
1
,
j, z
i
,
l
(
t
)
=
p
B
i
(
t
), l
=
l
+
1, j
=
j
+
1.
(5)
Ifl
=
n, output z
i
,
l
(
t
) and F
i
(
t
)
=
z
i
,
l
(
t
).
(6)
The formulag
(
F
i
(
t
)
,
g
B
i
(
t
)
) expresses the adjustment of particle i according to the optimal particle g
B
i
(
t
) in group, and specific operation is the same as the function g
(
V
i
(
t
)
,
p
B
i
(
t
)
).
(7)
If the new particleX
i
(
t
+
1
) can satisfy the relationship matrix, this iteration is successful.


### 3.5. The Specific Steps of PSO Algorithm

The specific steps of PSO algorithm are as follows.(1)
Algorithm initialization: set the initialization parametersw
,
c
1
,
c
2
,
b
1
,
b
2, confirm the number of iterations G, and generate N initialized population.
(2)
The initialization ofp
B
i
(
t
) and g
B
i
(
t
): p
B
i
(
t
) is the local optimal particle and g
B
i
(
t
) is the best particle in N population. Take the N population which is generated initially as p
B
i
(
t
), and calculate each particle's fitness according to the objective function min
⁡
f
1 to confirm g
B
i
(
t
).
(3)
Use a part of the best particlep
B
i
(
t
) instead of a part of the carrier particle in the current iteration population in order to ensure the diversity of population during iteration.
(4)
InG iterations, update each particle's position according to the particle update formula, calculate the takt time of each particle, select these particles with small takt time, and calculate their smoothness index. Determine the value of the new p
B
i
(
t
) and g
B
i
(
t
) according to the fitness function min
⁡
f
1 and complete the update of p
B
i
(
t
) and g
B
i
(
t
).
(5)
End the iteration and output the result afterG iterations.The operation process of assembly line balancing problem based on PSO algorithm is shown in Figure 3.Figure 3
The operation process of assembly line balancing problem based on PSO algorithm.


## 3.1. Particle Swarm Optimization Algorithm

(1)
The basic idea of particle swarm optimization: the particle swarm optimization was first put forward in 1995 by the American social psychologist J. Kennedy and electrical engineer R. Eberhart on the basis of the study of the behavior of birds group in the early time [21]. PSO treats each individual as a particle which has no weight and volume in n dimensional search space and the particle flies at a certain speed in the search space. The speed is dynamically adjusted based on the flying experience of individual and group.
(2)
The basic mathematical model of PSO algorithm [22–24].In the n dimensional space, X
i
=
(
x
i
1
,
x
i
2
,
…
,
x
i
n
) express a current position of particle i.V
i
=
(
v
i
1
,
v
i
2
,
…
,
v
i
n
) express that the speed v
i is the current speed of particle i.P
i
=
(
p
i
1
,
p
i
2
,
…
,
p
i
n
) express the best experiencing position of particle i; namely, P
i has the smallest fitness.Assume thatf
(
x
) is the minimized objective function, the best position of particle i is calculated as follows:
(16)
P
i
(
t
+
1
)
=
{
P
i
(
t
)
f
(
P
i
(
t
)
)
≤
f
(
X
i
(
t
+
1
)
)
X
i
(
t
+
1
)
f
(
P
i
(
t
)
)
>
f
(
X
i
(
t
+
1
)
)
.Assume that the number of particles iss in population; all particles have experienced the best position P
g
(
t
); then
(17)
P
g
(
t
)
∈
{
P
0
(
t
)
,
…
,
P
g
(
t
)
}
∣
f
(
P
g
(
t
)
)
hiihh
=
min
⁡
{
f
(
P
0
(
t
)
)
,
…
,
f
(
P
s
(
t
)
)
}
.
PSO algorithm basic solving equations are as follows [25, 26].Speed evolution equation is shown as(18)
V
i
(
t
+
1
)
=
w
V
i
(
t
)
+
c
1
r
1
(
p
i
(
t
)
-
x
i
(
t
)
)
+
c
2
r
2
(
p
g
(
t
)
-
X
i
(
t
)
)
.
Position evolution equation is shown as
(19)
X
i
(
t
+
1
)
=
X
i
(
t
)
+
V
i
(
t
+
1
)
.In (18), c
1 and c
2 are the acceleration constant, which take the value in [
0,2
].  r
1 and r
2 both are a random number between 1 and 2; w is inertia coefficient between 0 and 1 and it has the ability of keeping inertia expansion of particle movement to explore new areas.


## 3.2. Parameter Setting of PSO

The parameters of particle swarm optimization algorithm include population quantityN, the number of iterations G, inertia weight w, accelerated constant c, and the initial position and velocity of each particle.


## 3.3. Coding of Assembly Line Balancing Problem

The most important job is to code in order to solve the assembly line balancing problem using PSO algorithm. There are many coding methods for the scheduling problem. Among the numerous coding methods, coding based on workpiece, coding based on machine, and coding based on operation are used in the optimization problem frequently [27–29].In view of the particularity of assembly line balancing problem, as well as the limitations of general coding method, a coding method based on job elements is adopted in this paper. AOV-net coding basic ideas are used to encode the precedence relations diagram of job element [30].The basic steps of AOV-net basic coding are as follows.(1)
Output the node which has no precursors in AOV-net table.
(2)
Remove the selected node and the arc which takes the selected node as starting point form the map; the rest of the vertices still constitute the AOV-net.
(3)
Repeat(
1
) and (
2
) until outputting all the nodes, the vertex sequencing is a topological sort.Since the precedence relations diagram of job element contains two parts, namely, job element and standard work time, a two-dimensional particle expressive method is proposed [31]. Assume the total number of job elements are N; a two-dimensional particle with length N is created: the first dimension corresponds the order of job elements; the second dimension corresponds standard work time t
i
(
i
=
1,2
,
3
,
…
,
N
) of each job element, and each job element has a corresponding standard work time. If the order of job element changes, the arrangement of standard work time also changes.The precedence relations diagram of an assembly line with ten job elements is shown in Figure2.Figure 2
Precedence relations diagram with ten job elements.Two particles are coded and shown in Tables1 and 2.Table 1
The code of particle one.
Job element
1
2
3
4
5
6
7
9
8
10
Standard work time (t
i)
1.3
0.9
1.8
1.1
0.9
1.2
1.3
2.0
1.8
1.1Table 2
The code of particle two.
Job element
1
3
4
2
6
5
7
9
8
10
Standard work time (t
i)
1.3
1.8
1.1
0.9
1.2
0.9
1.3
2.0
1.8
1.1


## 3.4. The Particle Updating Formula of PSO Algorithm

The particle updating formula is defined as(20)
X
i
(
t
+
1
)
=
c
2
⊗
g
{
c
1
⊗
g
[
w
⊗
h
x
,
y
(
X
i
(
t
)
)
,
p
B
i
(
t
)
]
,
g
B
i
(
t
)
}
.
In (20), X
i
(
t
+
1
) express the positions of particle i in the t iterations.c
1 and c
2 are the acceleration constant, and w is the inertia coefficient. Moreover, their values are between 0 and 1. h
x
,
y
(
X
i
(
t
)
) express the exchange of the x component and the y component. x and y are two different random integers between 1 and n (the number of job elements). p
B
i
(
t
) is the best position of particle i in t iterations. g
B
i
(
t
) is the best position of group in t iterations.The formula (20) includes three parts.The first part is the updating of particle position:(21)
V
i
(
t
)
=
w
⊗
h
x
,
y
(
X
i
(
t
)
)
=
{
h
x
,
y
(
X
i
(
t
)
)
rand
(
)
<
w
X
i
(
t
)
rand
(
)
≥
w
.The second part is the adjustment of the particlep
B
i
(
t
) based on its best position:
(22)
F
i
(
t
)
=
c
1
⊗
g
(
V
i
(
t
)
,
p
B
i
(
t
)
)
=
{
g
(
V
i
(
t
)
,
p
B
i
(
t
)
)
rand
(
)
<
c
1
V
i
(
t
)
rand
(
)
≥
c
1
.The third part is the adjustment of the particle based on the best positiong
B
i
(
t
) in the group:
(23)
X
i
(
t
+
1
)
=
c
2
⊗
g
(
F
i
(
t
)
,
g
B
i
(
t
)
)
=
{
g
(
F
i
(
t
)
,
g
B
i
(
t
)
)
rand
(
)
<
c
2
F
i
(
t
)
rand
(
)
≥
c
2
.
rand
(
) is a random uniform distribution number. The meaning of function g
(
V
i
(
t
)
,
p
B
i
(
t
)
) is the adjustment of particles according to its best position in the i iteration. The specific implementation processes are as follows.(1)
Whenrand
(
)
⩾
c
1, F
i
(
t
)
=
V
i
(
t
).
(2)
When rand(
)
<
c
1, execute g
(
V
i
(
t
)
,
p
B
i
(
t
)
). Take p
B
i
t
(
t
) as the best position in the i iteration; n is the number of job elements. An integer from 1 to n is randomly selected to make p
B
i
t
(
t
) be divided into two sets {
S
(
1
)
i
,
j
}, {
S
(
2
)
i
,
j
}.
(3)
An expressive method of two-dimensional particle is adopted to update the arrangement of job elements.x
1
,
j
(
t
) express the job elements arrangement of V
i
(
t
) and z
1
,
l
(
t
) expresses the new arrangement F
i
(
t
). Take l
=
1, j
=
1.
(4)
Ifx
1
,
j
(
t
)
∈
S
(
1
)
1
,
j, z
1
,
l
(
t
)
=
x
1
,
j
(
t
); if p
B
i
(
t
)
∈
S
(
2
)
1
,
j, z
i
,
l
(
t
)
=
p
B
i
(
t
), l
=
l
+
1, j
=
j
+
1.
(5)
Ifl
=
n, output z
i
,
l
(
t
) and F
i
(
t
)
=
z
i
,
l
(
t
).
(6)
The formulag
(
F
i
(
t
)
,
g
B
i
(
t
)
) expresses the adjustment of particle i according to the optimal particle g
B
i
(
t
) in group, and specific operation is the same as the function g
(
V
i
(
t
)
,
p
B
i
(
t
)
).
(7)
If the new particleX
i
(
t
+
1
) can satisfy the relationship matrix, this iteration is successful.


## 3.5. The Specific Steps of PSO Algorithm

The specific steps of PSO algorithm are as follows.(1)
Algorithm initialization: set the initialization parametersw
,
c
1
,
c
2
,
b
1
,
b
2, confirm the number of iterations G, and generate N initialized population.
(2)
The initialization ofp
B
i
(
t
) and g
B
i
(
t
): p
B
i
(
t
) is the local optimal particle and g
B
i
(
t
) is the best particle in N population. Take the N population which is generated initially as p
B
i
(
t
), and calculate each particle's fitness according to the objective function min
⁡
f
1 to confirm g
B
i
(
t
).
(3)
Use a part of the best particlep
B
i
(
t
) instead of a part of the carrier particle in the current iteration population in order to ensure the diversity of population during iteration.
(4)
InG iterations, update each particle's position according to the particle update formula, calculate the takt time of each particle, select these particles with small takt time, and calculate their smoothness index. Determine the value of the new p
B
i
(
t
) and g
B
i
(
t
) according to the fitness function min
⁡
f
1 and complete the update of p
B
i
(
t
) and g
B
i
(
t
).
(5)
End the iteration and output the result afterG iterations.The operation process of assembly line balancing problem based on PSO algorithm is shown in Figure 3.Figure 3
The operation process of assembly line balancing problem based on PSO algorithm.


## 4. The Results of Simulation and Analysis

### 4.1. Operating Environment

The configuration of computer is CPU Intel Core i7, CPU Clock Speed 2.60 GHz, internal storage 12.00 GB, and windows 7 operating system. Matlab is used to realize the PSO algorithm.


### 4.2. Example  1

Take a simple assembly line with 12 job elements and 5 stations as an example. The precedence relations diagram is shown in Figure4, and the relationship matrix is shown in (24). The PSO algorithm, Manual Balance Search algorithm, and Tabu Search algorithm are used to optimize the assembly line and the optimization results are compared in Table 3. The parameters used in PSO algorithm are as follows: population N
=
5; iteration number G
=
100; w
=
0.5; c
1
=
0.8; c
2
=
0.8; w
1
=
0.5; w
2
=
0.5. One has the following:
(24)
M
=
[
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
]
.Table 3
The comparison of assembly line balancing result in Example  1.
Station
PSO
Manual Balance Search
Tabu Search algorithm
Job
TimeT
j
Job
TimeT
j
Job
TimeT
j
Elementj
Elementj
Elementj
1
1, 3
0.90
1, 2
0.6
1, 2, 4
0.70
2
2, 5, 4
0.80
3, 4
0.8
3, 6
0.70
3
8, 6
0.71
5, 6, 7
0.73
5, 8
0.90
4
10, 7
0.70
8, 9
0.87
7, 10
0.81
5
9, 11, 12
0.89
10, 11, 12
1.0
9, 11, 12
0.89
TT
0.90
1.0
0.90
P
88.8%
80%
88.8%
SI
0.1313
0.2407
0.1328
f
1
0.5157
0.6204
0.5164Figure 4
Precedence relations diagram with 12 job elements.From Table3, PSO algorithm has the smallest fitness f
1, takt time TT, smoothness index SI, and the largest balance rate P, which shows the effectiveness of PSO algorithm.


### 4.3. Example  2

In the APXV9R20B antenna assembly shop, there are 8 work stations in each assembly line, and there are 28 job elements during the assembly of antenna. The job element of antenna assembly and standard work time is shown in Table4. The precedence relations diagram of antenna relationship matrix with 28 job elements is shown in Figure 5. The relationship matrix is in the following:(25)
M
=
[
0
1
1
0
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
]
.Table 4
The job element of antenna assembly.
Operation sequence
Number job element
Standard work time (s)
1
Put the chassis on the assembly line and clean
3.4
2
Install the high frequency oscillator
6.96
3
Install the wall components
5.29
4
Install the input cable components
2.58
5
Install the high frequency isolation
12.13
6
Install the low frequency isolation
3.9
7
Install high frequency isolation block
4.2
8
Install low frequency oscillator
10.46
9
Low frequency cable wiring
6.12
10
High frequency cable wiring
10
11
Install low frequency ground plate
12.59
12
The high frequency oscillator cable welding to the oscillator
21.8
13
Install high frequency ground plate
12.98
14
Install the low frequency oscillator cable in place
9.29
15
Install low frequency switching
4.38
16
Low frequency cable welding and cleaning
28.29
17
Install the high frequency oscillator cable in place
8.43
18
The high frequency cable welding and cleaning
22.66
19
Place the low frequency phase shifter components
1.76
20
Place the high frequency phase shifter components
1.63
21
Install low frequency flat
6.14
22
Install high frequency flat
4.97
23
Low frequency plate welding
26.9
24
High frequency plate welding
33.43
25
Install phase shift
11.63
26
Fixed the guide box and the front panel
5.23
27
The support installation
3.07
28
Install support
7.37Figure 5
Precedence relations diagram with 28 job elements.The parameters used in PSO algorithm are as follows: populationN
=
50; iteration number G
=
300; w
=
0.5; c
1
=
0.8; c
2
=
0.8; w
1
=
0.5; w
2
=
0.5.By the optimization of PSO algorithm, Manual Balance Search algorithm, and Tabu Search algorithm, the time and job elements in each work station are shown in Figures6, 7, and 8. Their assembly line balancing comparison result is shown in Table 5.Table 5
The 28 job elements assembly balancing comparison result.
Station
PSO
Manual Balance Search
Tabu Search algorithm
Job
TimeT
j
Job
TimeT
j
Job
TimeT
j
Elementj
Elementj
Elementj
1
1, 5, 3, 2, 8
38.24
1, 2, 3, 4, 5, 6, 7
38.46
1, 2, 3, 4, 8, 10
38.69
2
4, 10, 12
34.38
8, 9, 10, 11
39.17
6, 7, 9, 12
36.02
3
9, 14, 15, 11
32.38
12, 13, 14
44.07
11, 13, 14
34.86
4
13, 18
35.64
15, 16, 17
41.7
15, 16, 19
35.03
5
16, 21, 19
36.79
18, 19, 20, 21, 22
37.16
17, 18, 20, 21
38.86
6
17, 20, 23
36.96
23
26.9
22, 24
38.4
7
24, 22
38.40
24
33.43
23, 25
38.53
8
7, 25, 6, 27, 26, 28
35.40
25, 26, 27, 28
27.3
5, 26, 27, 28
27.8
TT
38.40
44.07
38.86
P
93.81%
81.74%
92.70%
SI
3.035
9.988
4.491
f
1
20.72
27.03
21.68Figure 6
The optimization result of manual balance search.Figure 7
The optimization result of Tabu Search algorithm.Figure 8
The optimization result of PSO algorithm.According to Table5, balance optimization scheme based on PSO algorithm is the best scheme in contrast with Manual Balance Search and Tabu Search algorithm, because it has the smallest takt time TT, smoothness index SI, and the largest balance rate P.


## 4.1. Operating Environment

The configuration of computer is CPU Intel Core i7, CPU Clock Speed 2.60 GHz, internal storage 12.00 GB, and windows 7 operating system. Matlab is used to realize the PSO algorithm.


## 4.2. Example  1

Take a simple assembly line with 12 job elements and 5 stations as an example. The precedence relations diagram is shown in Figure4, and the relationship matrix is shown in (24). The PSO algorithm, Manual Balance Search algorithm, and Tabu Search algorithm are used to optimize the assembly line and the optimization results are compared in Table 3. The parameters used in PSO algorithm are as follows: population N
=
5; iteration number G
=
100; w
=
0.5; c
1
=
0.8; c
2
=
0.8; w
1
=
0.5; w
2
=
0.5. One has the following:
(24)
M
=
[
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
]
.Table 3
The comparison of assembly line balancing result in Example  1.
Station
PSO
Manual Balance Search
Tabu Search algorithm
Job
TimeT
j
Job
TimeT
j
Job
TimeT
j
Elementj
Elementj
Elementj
1
1, 3
0.90
1, 2
0.6
1, 2, 4
0.70
2
2, 5, 4
0.80
3, 4
0.8
3, 6
0.70
3
8, 6
0.71
5, 6, 7
0.73
5, 8
0.90
4
10, 7
0.70
8, 9
0.87
7, 10
0.81
5
9, 11, 12
0.89
10, 11, 12
1.0
9, 11, 12
0.89
TT
0.90
1.0
0.90
P
88.8%
80%
88.8%
SI
0.1313
0.2407
0.1328
f
1
0.5157
0.6204
0.5164Figure 4
Precedence relations diagram with 12 job elements.From Table3, PSO algorithm has the smallest fitness f
1, takt time TT, smoothness index SI, and the largest balance rate P, which shows the effectiveness of PSO algorithm.


## 4.3. Example  2

In the APXV9R20B antenna assembly shop, there are 8 work stations in each assembly line, and there are 28 job elements during the assembly of antenna. The job element of antenna assembly and standard work time is shown in Table4. The precedence relations diagram of antenna relationship matrix with 28 job elements is shown in Figure 5. The relationship matrix is in the following:(25)
M
=
[
0
1
1
0
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
]
.Table 4
The job element of antenna assembly.
Operation sequence
Number job element
Standard work time (s)
1
Put the chassis on the assembly line and clean
3.4
2
Install the high frequency oscillator
6.96
3
Install the wall components
5.29
4
Install the input cable components
2.58
5
Install the high frequency isolation
12.13
6
Install the low frequency isolation
3.9
7
Install high frequency isolation block
4.2
8
Install low frequency oscillator
10.46
9
Low frequency cable wiring
6.12
10
High frequency cable wiring
10
11
Install low frequency ground plate
12.59
12
The high frequency oscillator cable welding to the oscillator
21.8
13
Install high frequency ground plate
12.98
14
Install the low frequency oscillator cable in place
9.29
15
Install low frequency switching
4.38
16
Low frequency cable welding and cleaning
28.29
17
Install the high frequency oscillator cable in place
8.43
18
The high frequency cable welding and cleaning
22.66
19
Place the low frequency phase shifter components
1.76
20
Place the high frequency phase shifter components
1.63
21
Install low frequency flat
6.14
22
Install high frequency flat
4.97
23
Low frequency plate welding
26.9
24
High frequency plate welding
33.43
25
Install phase shift
11.63
26
Fixed the guide box and the front panel
5.23
27
The support installation
3.07
28
Install support
7.37Figure 5
Precedence relations diagram with 28 job elements.The parameters used in PSO algorithm are as follows: populationN
=
50; iteration number G
=
300; w
=
0.5; c
1
=
0.8; c
2
=
0.8; w
1
=
0.5; w
2
=
0.5.By the optimization of PSO algorithm, Manual Balance Search algorithm, and Tabu Search algorithm, the time and job elements in each work station are shown in Figures6, 7, and 8. Their assembly line balancing comparison result is shown in Table 5.Table 5
The 28 job elements assembly balancing comparison result.
Station
PSO
Manual Balance Search
Tabu Search algorithm
Job
TimeT
j
Job
TimeT
j
Job
TimeT
j
Elementj
Elementj
Elementj
1
1, 5, 3, 2, 8
38.24
1, 2, 3, 4, 5, 6, 7
38.46
1, 2, 3, 4, 8, 10
38.69
2
4, 10, 12
34.38
8, 9, 10, 11
39.17
6, 7, 9, 12
36.02
3
9, 14, 15, 11
32.38
12, 13, 14
44.07
11, 13, 14
34.86
4
13, 18
35.64
15, 16, 17
41.7
15, 16, 19
35.03
5
16, 21, 19
36.79
18, 19, 20, 21, 22
37.16
17, 18, 20, 21
38.86
6
17, 20, 23
36.96
23
26.9
22, 24
38.4
7
24, 22
38.40
24
33.43
23, 25
38.53
8
7, 25, 6, 27, 26, 28
35.40
25, 26, 27, 28
27.3
5, 26, 27, 28
27.8
TT
38.40
44.07
38.86
P
93.81%
81.74%
92.70%
SI
3.035
9.988
4.491
f
1
20.72
27.03
21.68Figure 6
The optimization result of manual balance search.Figure 7
The optimization result of Tabu Search algorithm.Figure 8
The optimization result of PSO algorithm.According to Table5, balance optimization scheme based on PSO algorithm is the best scheme in contrast with Manual Balance Search and Tabu Search algorithm, because it has the smallest takt time TT, smoothness index SI, and the largest balance rate P.


## 5. Conclusion

The assembly line balancing problem is a key question in the field of assembly line design and management. The PSO algorithm is applied to solve the assembly line balancing problem with optimization goals smoothness index SI and takt time TT. The simulation results show that the PSO algorithm can optimize assembly line balancing problem with the highest assembly line balance rate and the smallest discrete conditions than the other two methods, which shows the effectiveness of the algorithm. However, in the PSO algorithm, particles are easy to lose diversity and lead to premature after several iterations. Therefore, the study of combining PSO algorithm with other algorithms to overcome the defects in the PSO algorithm is the focus of study in the future.



---

*Source: 743695-2014-04-30.xml*