# A Bottleneck Detection Algorithm for Complex Product Assembly Line Based on Maximum Operation Capacity

Authors: Dongping Zhao; Xitian Tian; Junhao Geng
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Because of the complex constraints in complex product assembly line, existing algorithms not always detect bottleneck correctly and they have a low convergence rate. In order to solve this problem, a hybrid algorithm of adjacency matrix and improved genetic algorithm (GA) was proposed. First, complex assembly network model (CANM) was defined based on operation capacity of each workstation. Second, adjacency matrix was proposed to convert bottleneck detection of complex assembly network (CAN) into a combinatorial optimization problem of max-flow. Third, an improved GA was proposed to solve this max-flow problem by retaining the best chromosome. Finally, the min-cut sets of CAN were obtained after calculation, and bottleneck workstations were detected according to the analysis of min-cut sets. A case study shows that this algorithm can detect bottlenecks correctly and its convergence rate is high.


---

## Body

## 1. Introduction

The study of bottlenecks in assembly line has been a subject of academic research for years. A bottleneck is defined as one of the workstations that limit the production rate of the entire assembly line because demand is far away from the capacity of the bottleneck either for some time or permanently [1, 2]. It may lead to situations where either an upstream workstation has finished processing items but cannot deliver them to a downstream workstation because that is still busy or to situations where a downstream workstation is idle and waiting for items to be delivered from an upstream workstation, which is still processing [3]. Further, bottlenecks may lead to two major problems in a production process. First, if the capacity of the assembly line is not sufficient to satisfy customers demand, the company may lose sales and customer goodwill. Secondly, if excess inventory accumulates in front of bottleneck workstations, additional inventory carrying costs are incurred. It is known that controlling bottleneck workstations smoothes the flow of materials in assembly line, which can improve customer satisfaction and reduce costs.Bottlenecks are almost certain to exist [4] because the existence of bottleneck is a major factor in assembly line performance and management [5, 6]. So it is important to improve bottlenecks. By improving it, we mean increasing the throughput capacity of the current bottleneck, which in turn permits greater throughput for the entire assembly line. That is, improvement at nonbottleneck workstations does not increase the system capacity. Many researchers have developed models that deal with controlling and managing bottleneck workstations. However, before a bottleneck can be improved, it must be located. Bottleneck analysis is of high interest in manufacturing operations, and in recent years a great deal of research has focused on the area of bottleneck detection [7]. Some research focused on how to detect bottlenecks in assembly line by using different methodologies, namely, analytical [8, 9], simulation [10], and empirical methods [11–13].Our review revealed nine basic approaches to detect bottlenecks in assembly line or other production systems. The nine approaches are given a short name in Table1 along with references to their use.Table 1
Methods for bottleneck detection.
Approaches
Reference
Longest queue
Lawrence and Buss 1994 [14]
Longest waiting time
Hsiao et al. 2010  [15]
Utilization
Hopp et al. 2002 [16]
Active period
Roser et al. 2001 [17]
Arrow
Kuo et al. 1996 [18]
Average waiting time
Faget et al. 2005 [19]
Inactive period
Sengupta et al. 2008 [20]
Turning point
Sengupta et al. 2008 [20]
Overall throughputEffectiveness (OTE)
Geng et al. 2014 [21]We described each of the nine approaches as follows.(
1) Longest Queue Method. The station having the greatest number of waiting jobs in queue for the largest proportion of the overall line processing period is the bottleneck. In practice, this method requires that queue lengths at all machines be compared at specified time intervals, for example, each time a job arrives at any resource queue, and that a running tabulation be maintained of the queue having maximum length at each point in time. A practical substitute is the maximum average queue length.(
2) Longest Waiting Time Method. The station where work waits longest, as measured by the maximum time a job spends in queue, is considered the bottleneck.(
3) Utilization Method. This method is also called the effective process time method. In serial production lines without reentry or yield loss, the arrival rate is the same at all stations, so the station having the highest utilization will be the station with the smallest effective production rate. Utilization is calculated for each resource in the line and the resource with the largest utilization percentage is considered the bottleneck.(
4) Active Period Method. This method measures the duration of the periods in which a station is active without interruption and calculates the average active period for each station. The machine which has the longest average active period is considered the bottleneck. Examples of active states are working and downtime; examples of inactive states are being starved or blocked. Consecutive active states are considered to be one active state.(
5) Arrow Method. This method derives its name from the practice of drawing arrows pointing left or right showing which stations have higher blocking and starving compared to adjacent stations and uses two related rules to locate the bottleneck.(
6) Average Waiting Time Method. The station where work waits longest, as measured by the average time a job spends in queue, is considered the bottleneck.(
7) Inactive Period Method. This method designates as the bottleneck the station with the minimum combined total time spent in inactive states.(
8) Turning Point Method. The “turning point” is the station where the trend of blockage and starvation changes from blockage being higher than starvation to starvation being higher than blockage. The total blockage plus starvation time of a “turning point” station is smaller than that for its two neighboring stations; that is, the “turning point” has the highest percentage of operating time plus downtime compared to its adjacent stations. For the special case that no turning point is found, if each station’s starvation is higher than its blockage, the first station is the bottleneck; else, if each station’s blockage is higher than its starvation, the last station is the bottleneck.(
9) OTE Method. This method is equivalent to utilization method in assembly lines.From the above analysis, these different approaches have been proposed to solve bottleneck detection in different production systems. However, there is much difficulty to detect bottleneck in complex product assembly line by these approaches because of the complex constraints and a large scale of calculation, and none of them has been based on maximum operation capacity of complex product assembly line. In this paper, we defined a CAN for complex product assembly line based on capacity of each workstation. In this way, we take the bottleneck detection into a problem of max-flow for CAN. Then, bottlenecks can be detected by solving the max-flow of the CAN.Ford and Fulkerson proposed the “max-flow/min-cut” algorithm in 1957 to solve the problem of max-flow for the networks [22]. This algorithm has more computational complexity in seeking augmented chain. Many scholars proposed a lot of improvements to the Ford-Fulkerson algorithm in the past few decades [23, 24]. It is efficient to use these algorithms to solve the max-flow problem when the size of network is small. But the efficiency becomes very low or even impossible when the size of network is great, especially for CAN. In other words, Ford-Fulkerson and its improved algorithms are only suitable to solve the problem of single-source and single-sink networks (solving multisource and multisink networks need to be transformed). Meanwhile, when the values of operation capacity in networks are irrational numbers, Ford-Fulkerson gives examples to show that labeling method did not stop in a limited step and sequence of the flow when calculation did not reach the max-flow [25].Many scholars are to solve max-flow problem with min-cut sets algorithm. The literature [26] proposed a matrix algorithm to solve the problem. Although matrix is applied in calculation to search min-cut sets, the capacity matrixes of cut sets need to calculate 2
m times (m is the number of intermediate nodes). So the computational efficiency is low. “Cut set matrix algorithm” is proposed by [27] based on the literature [26]. This algorithm reduces the amount of computation by using adjacency matrix. The essence of these algorithms is an enumerate method. When nodes of network are too many, such as m
=
20, the number of cut sets is 2
20
=
1058576. That is, the computational problems cannot be solved by enumerate method. Therefore, the common features of min-cut sets algorithms are only suitable for small-scale networks problem and powerless for large-scale networks problem. In this case, using GA to find the optimal solution has a great advantage.Penalty function is used to deal with constrains when we solve multiconstrain problem by GA in networks. But the probability of chromosomal failure is very large after crossover and mutation because constraints in CAN are too many and strict. Therefore, a hybrid algorithm of min-cut sets and an improved GA is proposed to solve max-flow problem for CAN in this paper. This algorithm avoids constraints completely of CAN and fully reflects the advantages of GA in solving large-scale portfolio optimization problems.The remainder of this paper is organized as follows: Section2 provides the max-flow/min-cut theorem and bottleneck definition. Section 3 provides the major assumptions, description of the problem with CAN, and mathematical model of the problem. Section 4 proposes the improved GA in detail. Section 5 is a numerical example. Section 6 is results and discussion, and Section 7 concludes the paper.


## 2. Basic Theory and Bottleneck Definition

Max-flow/min-cut theorem [28]: given a directed network D
=
(
V
,
A
), nodes in V can be divided into three parts: start nodes of cut set (denoted by V
s), end nodes of cut set (denoted by V
t), and the remaining nodes are called intermediate nodes. There is an arc capacity c
(
v
i
,
v
j
)
≥
0 (denoted by c
i
j) for each arc (
v
i
,
v
j
)
∈
A.For a directed networkD
=
(
V
,
A
), max-flow problem is to determine a feasible flow {
F
i
j
} on D, so that the flow v
(
f
) reaches maximum and satisfies
(1)
0
≤
F
i
j
≤
c
i
j
(
v
i
,
v
j
)
∈
A
,
∑
F
i
j
-
∑
F
j
i
=
{
v
(
f
)
(
i
=
s
)
,
0
(
i
≠
s
,
t
)
,
v
(
f
)
(
i
=
t
)
.According to max-flow/min-cut theorem, flow of max-flow fromV
s to V
t is equal to capacity of min-cut sets in any network. So, min-cut sets can be obtained by solving the max-flow. The total capacity of the network is affected significantly by the capacity of each cut set. In order to enhance the total capacity of the network, we must consider improving the capacity of each arc in min-cut sets. Therefore, arc in the min-cut set is a bottleneck of the entire network. It restricts the improvement of network performance.According to the above analysis, bottlenecks of complex product assembly line based on maximum operation capacity can be described as follows:(2)
CB
=
max
⁡
(
C
P
i
HC
)
i
=
1,2
,
…
,
n
,
where CB is bottlenecks of complex product assembly line, CP
i is operation capacity of min-cut set i for workstation, and HC is the entire operation capacity of assembly line, HC
=
∑
C
i.


## 3. Modeling of the Problem

### 3.1. Major Assumptions

The basic assumptions of the problem are characterized as follows.(1)
A homogenous product is assembled in an assembly line by assigningn tasks to m workstations (
n
⩾
m
).
(2)
The complex production assembly line with fixed number of workstations and no buffer is considered [29].
(3)
Taskk and task i can be assigned to the same workstation.
(4)
If taski is operated in workstation j, the required capacity c
i
j for task i is known because each workstation of the assembly line has been configured in this case. c
i
j can be determined by equipment, assembly process, and so on in every workstation, where c
i
j
≤
C; C is the globe capacity of the workstation.
(5)
Tasks must be assigned only once.
(6)
Only one task can be processed in each workstation at a time.


### 3.2. Description of the Problem with CANM

Through analysis for complexity production assembly line, we defined a CANM based on assembly precedence diagram and capacity of each workstation as Figure1, where⚪
x
i are the source nodes of CANM;
v
1
,
…
,
v
m are the nodes’ numbers;
① is the node/workstation;
→
c
i
j is the directed branch standing for the move of assembly tasks and c
i
j indicates operation capability of the workstation for this task;
⚪
y
i are the terminal nodes of CANM;
represents two tasks that can be operated in workstation 6 and operation capacities are c
1 and c
2;
means that after workstation 1, there are two new assembly tasks.Figure 1
Definition of complexity assembly network model (CANM).


### 3.3. Mathematical Modeling of the Problem

For a CAN, it can be written byG
=
(
V
,
A
). V is a set of all nodes in CAN. A is a set of directed branches in CAN. It stands for the move of assembly tasks. C is a set of branch capacity c
i
j. It indicates operation capability for the task on the coming workstation. The nodes set V can be divided into three parts: source nodes set, terminal nodes set, and intermediate nodes set. Let X be source nodes set (the start of CAN); Y is terminal nodes set (the end of CAN); W is intermediate nodes set. So there are some properties of CAN as follows.(1)
X
,
Y
,
W
⊂
G;
(2)
For the nodes setV
=
X
+
W
+
Y
=
{
x
1
,
x
2
,
…
,
x
p
;
v
1
,
v
2
,
…
,
v
m
;
y
1
,
y
2
,
…
,
y
q
};
(3)
X
∩
Y
=
∅
,
W
∩
Y
=
∅
,
X
∩
W
=
∅;
(4)
Each nodex
i in source nodes set X is a start node of CAN; each node y
i in terminal nodes set Y is an end node of CAN; each node v
k in intermediate nodes set W is not only a start node but also an end node of CAN.Let nodes setW
+
Y
=
{
x
1
,
x
2
…
,
x
p
;
v
1
,
v
2
,
…,v
m
;
y
1
,
y
2
,
…
,
y
q
} be columns; let nodes set X
+
W
=
{
x
1
,
x
2
,
…
,
x
p
;
v
1
,
v
2
,
…
,
v
m
} be rows. Then, adjacency matrix M
(
G
) of CAN is defined as follows: (3)
M
(
G
)
=
a
p
+
m
,
1
a
p
+
m
,
2
⋮
a
p
+
m
,
m
a
p
+
m
,
m
+
1
a
p
+
m
,
m
+
2
⋮
a
p
+
m
,
m
+
q
v
1
v
2
⋯
v
m
y
1
y
2
⋯
y
q
x
1
x
2
⋮
x
p
v
1
v
2
⋮
v
m
[
a
11
a
12
⋯
a
1
m
a
1
,
m
+
1
a
1
,
m
+
2
⋯
a
1
,
m
+
q
a
21
a
22
⋯
a
2
m
a
2
,
m
+
1
a
2
,
m
+
2
⋯
a
2
,
m
+
q
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
a
p
1
a
p
2
⋯
a
p
m
a
p
,
m
+
1
a
p
,
m
+
2
⋯
a
p
,
m
+
q
a
p
+
1,1
a
p
+
1,2
⋯
a
p
+
1
,
m
a
p
+
1
,
m
+
1
a
p
+
1
,
m
+
2
⋯
a
p
+
1
,
m
+
q
a
p
+
2,1
a
p
+
2,2
⋯
a
p
+
2
,
m
a
p
+
2
,
m
+
1
a
p
+
2
,
m
+
2
⋯
a
p
+
2
,
m
+
q
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
a
p
+
m
,
1
a
p
+
m
,
2
⋯
a
p
+
m
,
m
a
p
+
m
,
m
+
1
a
p
+
m
,
m
+
2
⋯
a
p
+
m
,
m
+
q
]
,where a
i
j
=
1 if directed branches (
v
i
,
v
j
)
∈
A. It means that assembly task is assigned to workstation v
j after a previous task was finished in workstation v
i; a
i
j
=
0 if directed branches (
v
i
,
v
j
)
∉
A. It means no assembly task is assigned to v
j after a previous task was finished in workstation v
i. In other words, there is no relationship between workstations v
i and v
j.For a directed branch(
v
i
,
v
j
)
∈
A, c
i
j is to indicate the operation capacity for a task in the workstation. Capacity matrix C
(
G
) is described as follows:(4)
C
(
G
)
=
c
p
+
m
,
1
c
p
+
m
,
2
⋮
c
p
+
m
,
m
c
p
+
m
,
m
+
1
c
p
+
m
,
m
+
2
⋮
c
p
+
m
,
m
+
q
v
1
v
2
⋯
v
m
y
1
y
2
⋯
y
q
x
1
x
2
⋮
x
p
v
1
v
2
⋮
v
m
[
c
11
c
12
⋯
c
1
m
c
1
,
m
+
1
c
1
,
m
+
2
⋯
c
1
,
m
+
q
c
21
c
22
⋯
c
2
m
c
2
,
m
+
1
c
2
,
m
+
2
⋯
c
2
,
m
+
q
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
c
p
1
c
p
2
⋯
c
p
m
c
p
,
m
+
1
c
p
,
m
+
2
⋯
c
p
,
m
+
q
c
p
+
1,1
c
p
+
1,2
⋯
c
p
+
1
,
m
c
p
+
1
,
m
+
1
c
p
+
1
,
m
+
2
⋯
c
p
+
1
,
m
+
q
c
p
+
2,1
c
p
+
2,2
⋯
c
p
+
2
,
m
c
p
+
2
,
m
+
1
c
p
+
2
,
m
+
2
⋯
c
p
+
2
,
m
+
q
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
c
p
+
m
,
1
c
p
+
m
,
2
⋯
c
p
+
m
,
m
c
p
+
m
,
m
+
1
c
p
+
m
,
m
+
2
⋯
c
p
+
m
,
m
+
q
]
,where the capacity of directed branch (
v
i
,
v
j
) is c
i
j if a
i
j
=
1; the capacity of the directed branch (
v
i
,
v
j
) is 0 if a
i
j
=
0.According to the definition of cut sets in network, if nodes setV is divided into two empty sets V
s and V
t and satisfies X
⊆
V
s, Y
⊆
V
t, then directed branch (
v
i
,
v
j
) is (separations V
s and V
t) called a cut set, where V
s is start nodes set of cut set and V
t is end nodes set of cut set.Cut set matrixK
t can be established according to capacity matrix C
(
G
). In capacity matrix C
(
G
), let corresponding rows of nodes in V
s be rows of cut set matrix K
t; let corresponding columns of nodes in V
t be columns of cut set matrix K
t. Assuming V
s contains source nodes set X and t intermediate nodes in CAN (t is the number of intermediate nodes; t
=
1,2
,
…
,
m). Then, cut set matrix K
t can be described by
(5)
K
t
=
(
c
i
j
)
(
p
+
t
)
×
(
q
+
m
-
t
)
.Then, the capacity of cut set matrixK
t is described as
(6)
C
t
=
∑
j
=
1
q
+
m
-
t
∑
i
=
1
p
+
t
c
i
j
.In a CAN, flow of max-flow fromX to Y is equal to the capacity of min-cuts set. Therefore, flow of max-flow or the maximum capacity of CAN as follows:
(7)
F
=
min
⁡
C
t
=
min
⁡
∑
j
=
1
q
+
m
∑
i
=
1
p
+
t
c
i
j
.From (5), we convert the problem of bottleneck detection for CAN to combinatorial optimization of nodes sets thought adjacency matrix and min-cut set method. The objective function of this combinatorial optimization is the maximum operation capacity.


## 3.1. Major Assumptions

The basic assumptions of the problem are characterized as follows.(1)
A homogenous product is assembled in an assembly line by assigningn tasks to m workstations (
n
⩾
m
).
(2)
The complex production assembly line with fixed number of workstations and no buffer is considered [29].
(3)
Taskk and task i can be assigned to the same workstation.
(4)
If taski is operated in workstation j, the required capacity c
i
j for task i is known because each workstation of the assembly line has been configured in this case. c
i
j can be determined by equipment, assembly process, and so on in every workstation, where c
i
j
≤
C; C is the globe capacity of the workstation.
(5)
Tasks must be assigned only once.
(6)
Only one task can be processed in each workstation at a time.


## 3.2. Description of the Problem with CANM

Through analysis for complexity production assembly line, we defined a CANM based on assembly precedence diagram and capacity of each workstation as Figure1, where⚪
x
i are the source nodes of CANM;
v
1
,
…
,
v
m are the nodes’ numbers;
① is the node/workstation;
→
c
i
j is the directed branch standing for the move of assembly tasks and c
i
j indicates operation capability of the workstation for this task;
⚪
y
i are the terminal nodes of CANM;
represents two tasks that can be operated in workstation 6 and operation capacities are c
1 and c
2;
means that after workstation 1, there are two new assembly tasks.Figure 1
Definition of complexity assembly network model (CANM).


## 3.3. Mathematical Modeling of the Problem

For a CAN, it can be written byG
=
(
V
,
A
). V is a set of all nodes in CAN. A is a set of directed branches in CAN. It stands for the move of assembly tasks. C is a set of branch capacity c
i
j. It indicates operation capability for the task on the coming workstation. The nodes set V can be divided into three parts: source nodes set, terminal nodes set, and intermediate nodes set. Let X be source nodes set (the start of CAN); Y is terminal nodes set (the end of CAN); W is intermediate nodes set. So there are some properties of CAN as follows.(1)
X
,
Y
,
W
⊂
G;
(2)
For the nodes setV
=
X
+
W
+
Y
=
{
x
1
,
x
2
,
…
,
x
p
;
v
1
,
v
2
,
…
,
v
m
;
y
1
,
y
2
,
…
,
y
q
};
(3)
X
∩
Y
=
∅
,
W
∩
Y
=
∅
,
X
∩
W
=
∅;
(4)
Each nodex
i in source nodes set X is a start node of CAN; each node y
i in terminal nodes set Y is an end node of CAN; each node v
k in intermediate nodes set W is not only a start node but also an end node of CAN.Let nodes setW
+
Y
=
{
x
1
,
x
2
…
,
x
p
;
v
1
,
v
2
,
…,v
m
;
y
1
,
y
2
,
…
,
y
q
} be columns; let nodes set X
+
W
=
{
x
1
,
x
2
,
…
,
x
p
;
v
1
,
v
2
,
…
,
v
m
} be rows. Then, adjacency matrix M
(
G
) of CAN is defined as follows: (3)
M
(
G
)
=
a
p
+
m
,
1
a
p
+
m
,
2
⋮
a
p
+
m
,
m
a
p
+
m
,
m
+
1
a
p
+
m
,
m
+
2
⋮
a
p
+
m
,
m
+
q
v
1
v
2
⋯
v
m
y
1
y
2
⋯
y
q
x
1
x
2
⋮
x
p
v
1
v
2
⋮
v
m
[
a
11
a
12
⋯
a
1
m
a
1
,
m
+
1
a
1
,
m
+
2
⋯
a
1
,
m
+
q
a
21
a
22
⋯
a
2
m
a
2
,
m
+
1
a
2
,
m
+
2
⋯
a
2
,
m
+
q
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
a
p
1
a
p
2
⋯
a
p
m
a
p
,
m
+
1
a
p
,
m
+
2
⋯
a
p
,
m
+
q
a
p
+
1,1
a
p
+
1,2
⋯
a
p
+
1
,
m
a
p
+
1
,
m
+
1
a
p
+
1
,
m
+
2
⋯
a
p
+
1
,
m
+
q
a
p
+
2,1
a
p
+
2,2
⋯
a
p
+
2
,
m
a
p
+
2
,
m
+
1
a
p
+
2
,
m
+
2
⋯
a
p
+
2
,
m
+
q
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
a
p
+
m
,
1
a
p
+
m
,
2
⋯
a
p
+
m
,
m
a
p
+
m
,
m
+
1
a
p
+
m
,
m
+
2
⋯
a
p
+
m
,
m
+
q
]
,where a
i
j
=
1 if directed branches (
v
i
,
v
j
)
∈
A. It means that assembly task is assigned to workstation v
j after a previous task was finished in workstation v
i; a
i
j
=
0 if directed branches (
v
i
,
v
j
)
∉
A. It means no assembly task is assigned to v
j after a previous task was finished in workstation v
i. In other words, there is no relationship between workstations v
i and v
j.For a directed branch(
v
i
,
v
j
)
∈
A, c
i
j is to indicate the operation capacity for a task in the workstation. Capacity matrix C
(
G
) is described as follows:(4)
C
(
G
)
=
c
p
+
m
,
1
c
p
+
m
,
2
⋮
c
p
+
m
,
m
c
p
+
m
,
m
+
1
c
p
+
m
,
m
+
2
⋮
c
p
+
m
,
m
+
q
v
1
v
2
⋯
v
m
y
1
y
2
⋯
y
q
x
1
x
2
⋮
x
p
v
1
v
2
⋮
v
m
[
c
11
c
12
⋯
c
1
m
c
1
,
m
+
1
c
1
,
m
+
2
⋯
c
1
,
m
+
q
c
21
c
22
⋯
c
2
m
c
2
,
m
+
1
c
2
,
m
+
2
⋯
c
2
,
m
+
q
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
c
p
1
c
p
2
⋯
c
p
m
c
p
,
m
+
1
c
p
,
m
+
2
⋯
c
p
,
m
+
q
c
p
+
1,1
c
p
+
1,2
⋯
c
p
+
1
,
m
c
p
+
1
,
m
+
1
c
p
+
1
,
m
+
2
⋯
c
p
+
1
,
m
+
q
c
p
+
2,1
c
p
+
2,2
⋯
c
p
+
2
,
m
c
p
+
2
,
m
+
1
c
p
+
2
,
m
+
2
⋯
c
p
+
2
,
m
+
q
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
c
p
+
m
,
1
c
p
+
m
,
2
⋯
c
p
+
m
,
m
c
p
+
m
,
m
+
1
c
p
+
m
,
m
+
2
⋯
c
p
+
m
,
m
+
q
]
,where the capacity of directed branch (
v
i
,
v
j
) is c
i
j if a
i
j
=
1; the capacity of the directed branch (
v
i
,
v
j
) is 0 if a
i
j
=
0.According to the definition of cut sets in network, if nodes setV is divided into two empty sets V
s and V
t and satisfies X
⊆
V
s, Y
⊆
V
t, then directed branch (
v
i
,
v
j
) is (separations V
s and V
t) called a cut set, where V
s is start nodes set of cut set and V
t is end nodes set of cut set.Cut set matrixK
t can be established according to capacity matrix C
(
G
). In capacity matrix C
(
G
), let corresponding rows of nodes in V
s be rows of cut set matrix K
t; let corresponding columns of nodes in V
t be columns of cut set matrix K
t. Assuming V
s contains source nodes set X and t intermediate nodes in CAN (t is the number of intermediate nodes; t
=
1,2
,
…
,
m). Then, cut set matrix K
t can be described by
(5)
K
t
=
(
c
i
j
)
(
p
+
t
)
×
(
q
+
m
-
t
)
.Then, the capacity of cut set matrixK
t is described as
(6)
C
t
=
∑
j
=
1
q
+
m
-
t
∑
i
=
1
p
+
t
c
i
j
.In a CAN, flow of max-flow fromX to Y is equal to the capacity of min-cuts set. Therefore, flow of max-flow or the maximum capacity of CAN as follows:
(7)
F
=
min
⁡
C
t
=
min
⁡
∑
j
=
1
q
+
m
∑
i
=
1
p
+
t
c
i
j
.From (5), we convert the problem of bottleneck detection for CAN to combinatorial optimization of nodes sets thought adjacency matrix and min-cut set method. The objective function of this combinatorial optimization is the maximum operation capacity.


## 4. Improved GA by Retaining the Best Chromosome

It cannot get all the min-cut sets of CAN by using standard GA and Ford-Fulkerson algorithm to solve the maximum flow problem. Mainly because(
1
) these algorithms are “premature convergence” to solve the problem for CAN (it convergences to local optimal solution rather than the global optimal solution); (
2
) the calculated value is swing near optimal solution after it achieved optimal solution because optimal chromosome is destroyed by crossover and mutation. Therefore, it needs to improve standard GA to solve combinatorial optimization of nodes sets for CAN. In this paper, GA is improved by retaining the best chromosome.Each node in theW can be or not be an element in V
s. This avoids complex constrains in combinatorial optimization compared with solved bottlenecks directly with GA. so there is no chromosomes failure and it can encode to compute directly. In this paper, fitness evaluation function is built basis on capacity matrix of cut sets. Capacity matrix of cut sets cannot be used directly as a fitness function because it changes constantly. So it needs to transform capacity matrix of cut sets to other form.


### 4.1. Coding

We take intermediate nodes for genes and use binary encoding rule. Each chromosome can be expressed as a code string shown in Figure2. Genes v
1
,
v
2
,
…
,
v
i
,
…
,
v
m in chromosome are an option of each intermediate node. 1 represents it being selected. It becomes a start node in V
s with source nodes set X; 0 represents it not being selected. It becomes an end node in V
t with terminal nodes set Y.Figure 2
Encoding rules.


### 4.2. Fitness Function

Fitness function can be constructed by objective evaluation function. Objective evaluation function is capacityC
t of cut set matrix K
t according to previous discussion. Therefore, objective evaluation function F
* can be described as
(8)
F
*
=
C
t
=
∑
j
=
1
q
+
m
∑
i
=
1
p
+
t
c
i
j
.The fitness is higher when objective function value is smaller, because max-flow is the capacity of min-cut set. Let fitness function be(9)
f
=
C
·
F
*
,
where C is a constant that is appropriately large.


### 4.3. Selection

The probability is chosen for an individuali as (8). We have
(10)
p
i
=
F
i
∑
i
=
1
M
F
k
,
where F
k is optimum value of individual i.The cumulative probability for each chromosome is(11)
q
i
=
∑
i
=
1
M
p
i
.Mating individuals are needed for multiple rounds of selection. Each mating generates a random number[
0
,
1
]. The random number can be used as a pointer to determine the alternative choice for individuals.Retaining the best chromosome was adopted in order to ensure that the best individual in current population can be retained as much as possible to the next generation during process of evolution. Assumea
(
t
) is the best individual in number t generation. In order to make good genes that can be inherited to the next generation, we use a
(
t
) instead of the worst individual in generation t
+
1. By using retention policies, the best individual is inherited to the next generation without being destroyed during crossover and mutation. This improved GA is convergent to the optimal solution with probability 1 when the best individual is found. Retaining the best chromosome making GA has the global convergence and may generate new individuals according to elite individuals which have a higher fitness.


### 4.4. Crossover and Mutation

Single-point crossover is common in GA. An intersection point is set randomly in encoded string of individuals. It forms two new offspring by partial interchange of two parent genes after the intersection point. Genes in groups are tending to single after crossover and selection. But these genes may not be the best genes. In other words, GA is easy to stay in some path sets of local convergence. This is so-called premature. Mutation operator can be improved premature in some cases.The basic position variation is used in this paper. One gene value is assigned randomly as a mutation operator (gene value becomes 1 by mutation if original genetic value is 0. on the contrary, gene value becomes 0 by mutation if original genetic value is 1).


### 4.5. Program of Improved GA

The program of improved GA for combinatorial optimization of CAN is as in Algorithm1.Algorithm 1:Solving the optimal value.
Input( ); % Parameter assignment
gen = 0; % Given initial value
Chrom = cribp; % Initial population structure
ObjV = fit( ); % The objective function is calculated
keep the best( ); % retaining the best chromosome
While
FitnV = ranking( ); % Distribution of fitness
SelCh = select( ); % Selection
SelCh = recombine( ); % Restructuring
SelCh = mut( ); % Variation
ObjVsel = fit( ); % The objective function is calculated
keep the best( ); % retaining the best chromosome
[Chrom ObjV] = reins (Chrom, SelCh, 1, 1ObjV, ObjVsel); % Insert new offspring population
keen = gen + 1; % Counter plus 1
End;
Output( ); %


## 4.1. Coding

We take intermediate nodes for genes and use binary encoding rule. Each chromosome can be expressed as a code string shown in Figure2. Genes v
1
,
v
2
,
…
,
v
i
,
…
,
v
m in chromosome are an option of each intermediate node. 1 represents it being selected. It becomes a start node in V
s with source nodes set X; 0 represents it not being selected. It becomes an end node in V
t with terminal nodes set Y.Figure 2
Encoding rules.


## 4.2. Fitness Function

Fitness function can be constructed by objective evaluation function. Objective evaluation function is capacityC
t of cut set matrix K
t according to previous discussion. Therefore, objective evaluation function F
* can be described as
(8)
F
*
=
C
t
=
∑
j
=
1
q
+
m
∑
i
=
1
p
+
t
c
i
j
.The fitness is higher when objective function value is smaller, because max-flow is the capacity of min-cut set. Let fitness function be(9)
f
=
C
·
F
*
,
where C is a constant that is appropriately large.


## 4.3. Selection

The probability is chosen for an individuali as (8). We have
(10)
p
i
=
F
i
∑
i
=
1
M
F
k
,
where F
k is optimum value of individual i.The cumulative probability for each chromosome is(11)
q
i
=
∑
i
=
1
M
p
i
.Mating individuals are needed for multiple rounds of selection. Each mating generates a random number[
0
,
1
]. The random number can be used as a pointer to determine the alternative choice for individuals.Retaining the best chromosome was adopted in order to ensure that the best individual in current population can be retained as much as possible to the next generation during process of evolution. Assumea
(
t
) is the best individual in number t generation. In order to make good genes that can be inherited to the next generation, we use a
(
t
) instead of the worst individual in generation t
+
1. By using retention policies, the best individual is inherited to the next generation without being destroyed during crossover and mutation. This improved GA is convergent to the optimal solution with probability 1 when the best individual is found. Retaining the best chromosome making GA has the global convergence and may generate new individuals according to elite individuals which have a higher fitness.


## 4.4. Crossover and Mutation

Single-point crossover is common in GA. An intersection point is set randomly in encoded string of individuals. It forms two new offspring by partial interchange of two parent genes after the intersection point. Genes in groups are tending to single after crossover and selection. But these genes may not be the best genes. In other words, GA is easy to stay in some path sets of local convergence. This is so-called premature. Mutation operator can be improved premature in some cases.The basic position variation is used in this paper. One gene value is assigned randomly as a mutation operator (gene value becomes 1 by mutation if original genetic value is 0. on the contrary, gene value becomes 0 by mutation if original genetic value is 1).


## 4.5. Program of Improved GA

The program of improved GA for combinatorial optimization of CAN is as in Algorithm1.Algorithm 1:Solving the optimal value.
Input( ); % Parameter assignment
gen = 0; % Given initial value
Chrom = cribp; % Initial population structure
ObjV = fit( ); % The objective function is calculated
keep the best( ); % retaining the best chromosome
While
FitnV = ranking( ); % Distribution of fitness
SelCh = select( ); % Selection
SelCh = recombine( ); % Restructuring
SelCh = mut( ); % Variation
ObjVsel = fit( ); % The objective function is calculated
keep the best( ); % retaining the best chromosome
[Chrom ObjV] = reins (Chrom, SelCh, 1, 1ObjV, ObjVsel); % Insert new offspring population
keen = gen + 1; % Counter plus 1
End;
Output( ); %


## 5. A Case Study on Simulation Example

There are 17 workstations in a complex product assembly line. The CAN is built according to assembly constraints and definition of CAN in Section3.2 as Figure 3.Figure 3
The CANM for complex product assembly line.Adjacency matrixM
(
G
) is created based on CAN as follows:(12)
M
(
G
)
=
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
v
9
v
10
v
11
v
12
v
13
v
14
v
15
v
16
v
17
y
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
v
9
v
10
v
11
v
12
v
13
v
14
v
15
v
16
v
17
y
x
0
x
1
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
v
9
v
10
v
11
v
12
v
13
v
14
v
15
v
16
v
17
x
0
x
1
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
v
9
v
10
v
11
v
12
v
13
v
14
v
15
v
16
v
17
[
1
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
1
1
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
1
0
1
0
1
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
1
1
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
1
1
1
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
1
1
1
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
1
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
1
1
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
1
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
1
]
.Capacity matrixC
(
G
) is created as follows:(13)
C
(
G
)
=
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
v
9
v
10
v
11
v
12
v
13
v
14
v
15
v
16
v
17
y
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
v
9
v
10
v
11
v
12
v
13
v
14
v
15
v
16
v
17
y
x
0
x
1
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
v
9
v
10
v
11
v
12
v
13
v
14
v
15
v
16
v
17
[
6
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
6
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
5
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
6
0
5
0
8
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
5
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
8
0
20
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
14
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
12
4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
6
5
8
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
16
0
5
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
8
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
5
8
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
20
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
20
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
20
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
]
.If the number of intermediate nodes ist, then the cut set matrix of t intermediate nodes is as follows:
(14)
K
t
=
(
c
i
j
)
(
2
+
t
)
×
(
18
-
t
)
.The capacityC
t of cut set matrix K
t is
(15)
C
t
=
∑
j
=
1
18
-
t
∑
i
=
1
2
+
t
c
i
j
.Therefore, according to the principle of the proposed algorithm, flow of max-flow fromX to Y is equal to the capacity of min-cut set (
v
i
,
v
j
), where v
i
⊂
V
s
,
v
j
⊂
V. Then, the maximum operation capacity of CAN is described as
(16)
F
=
min
⁡
C
t
=
min
⁡
(
∑
j
=
1
18
-
t
∑
i
=
1
2
+
t
c
i
j
)
.The number of intermediate nodes is 17 in this example and the number of cut sets of CAN reaches 217 = 131072 by algorithm [28]. In this case, the computational problems cannot be solved obviously. Using improved GA which is presented in this paper can solve the problem. We write programs of improved GA with Matlab according to Section 4.2. Relevant parameters are shown in Table 2.Table 2
Relevant parameters.
Parameters
Value
Chromosomes number of population
30
Maximum evolution algebra
200
Crossover probability
0.9
Mutation probability
0.05
Proportional of gap
10%


## 6. Results and Discussion

We detected bottlenecks for a complex product assembly line by the proposed algorithm. The CANM of this assembly line is shown in Figure3 and its simulation result is shown in Figure 4(a).Convergence curve of two different algorithms for the problem.
(a)
(b)From Figure4(a), the optimal value is reduced gradually with the increasing of the iterations in each generation group. Fitness value is convergence when evolved to 31 generations. Optimum fitness value is 74. That is, the maximum operation capacity is 74 of CAN. Optimal chromosome is listed as follows:
(17)
1
1
0
1
1
1
0
1
1
1
0
1
0
1
1Therefore, nodes inV
s are (
x
0
,
x
1
,
v
1
,
v
2
,
v
4
,
v
5
,
v
6
,
v
8
,
v
9
,
v
10
,
v
12
,
v
14
,
v
15
,
v
16
,
v
17
); nodes in V
t are (
v
3
,
v
7
,
v
11
,
v
13
,
y
). It shows that the min-cut sets of CAN are (
v
1
,
v
3
), (
v
2
,
v
3
), (
v
6
,
v
7
), (
v
5
,
v
7
), (
v
8
,
v
11
), (
v
9
,
v
11
), (
v
10
,
v
11
).Capacity of directed branches in each cut set is operation capacity of each workstation in CAN. The capacity of directed branches in cut sets is sensitive to overall operation capacity of CAN. Therefore, we can enhance the overall operation capacity of complex product assembly line by improve the capacity of min-cut sets. The influence of min-cut sets to the overall assembly line is shown in Table3 when capacity of each directed branch is increased 1%.Table 3
Influence of min-cut set to capacity of the overall assembly line.
Directed branches
C
i
j
C
i
j (after increase 1%)
F (after increase 1%)
Influence degree
v
1
,
v
3
2
2.02
73.98
2.70%
v
2
,
v
3
4
4.04
73.96
5.41%
v
6
,
v
7
8
8.08
73.92
10.81%
v
5
,
v
7
10
10.10
73.90
13.51%
v
9
,
v
1
1
5
5.05
73.95
6.76%
v
8
,
v
1
1
4
4.04
73.96
5.41%
v
10
,
v
1
1
16
16.16
73.84
21.62%From Table3, we can find that each min-cut set is influenced differently from the overall operation capacity of the assembly line. From (1), we can see that workstation 11 (v
11) has the maximum influence on CAN, and it is a bottleneck for complex product assembly line. Therefore, balancing rate and operation efficiency of assembly line can be improved to take measures on workstation 11.The proposed algorithm in this paper is effective to detect bottleneck for complex production assembly line. This hybrid algorithm of min-cut set and improved GA can solve problems not only difficult to calculate with enumeration algorithm but also impossible to solve multisource network with Ford-Fulkerson. In this case study of seventeen-workstation assembly line, the proposed algorithm in this paper performed quite well to detect bottlenecks. Then, we simulated this seventeen-workstation assembly line by some other methods in Table1, respectively. The longest queue method, the inactive period method, and the active period method all detected the bottleneck workstation 11 correctly. But the arrow method chose workstation 10 as the key bottleneck. When example is a five-workstation assembly line, the arrow method can also detect the workstation 11 as a key bottleneck correctly. The convergence curve of the longest queue method is shown in Figure 4(b). Compared with Figure 4(a), the optimal value is also 74 in the end. But this optimal value is convergence when it evolved to 98th generation. This new algorithm is effective to detect bottlenecks for a determined assembly line, in which the capacity c
i
j is known in each workstation. However, the algorithm is limited when the capacity c
i
j is variable.


## 7. Conclusion and Future Work

We have proposed and numerically validated a novel algorithm of bottlenecks detection in complex production assembly line based on maximum operation capacity. A case study on simulation example is presented to show efficiency and feasibility of the algorithm. This new algorithm has two advantages:(
1
) constraints of the CAN are avoided completely through adjacency matrix and min-cut sets. (
2
) It provides a feasible solution for GA to solve the problem of max-flow with multisource and multisink and take full advantages of simple program, fast convergence, and high computational efficiency of GA.Extending the algorithms into assembly network bottlenecks detection in which the operation capacity is variable is a very challenging mathematical task. This is beyond the scope of this paper and may be considered as a future work.



---

*Source: 258173-2014-05-19.xml*