# Evolution Balancing of the Small-Sized Wheel Loader Assembly Line

Authors: Rongshen Lai; Liang Hou; Yongming Wu
Journal: Shock and Vibration
 (2015)

---

## Abstract

Assembly line balancing not only directly determines production efficiency but also influences precision and quality of key assemblies or even the overall performance of final products. Driven by market demand and development of science and technology, product family must evolve constantly, which necessitates frequent adjustment and rebalancing of product family assembly line (PFAL). In order to maintain production efficiency, improve assembly quality and precision, and reduce costs for adjustment, the evolution balancing problem of PFAL for small-sized wheel loader is solved in this paper. Firstly, the evolution balancing model of PFAL is put forward. Then, with minimizing the number of workstations, the in-station and between-station load indexes and adjustment costs, and maximizing relevancy between activities as optimization objectives, meanwhile regarding product platform planning, modularity design and the critical chain technology in concurrent engineering as constraint conditions, the evolution balancing problem of PFAL is optimized using improved genetic algorithm (IGA). Finally, the whole analysis procedure is demonstrated by the small-sized wheel loader PFAL case study and the effectiveness of the proposed method
is verified.


---

## Body

## 1. Introduction

In most construction machinery manufacturing enterprises, assembly is the last link of production involving many operations and complex processes and has become the core technology. Born in Ford Motor Company, assembly line has greatly improved labor productivity and opened the prelude to modern mass production. However, frequent assembly line adjustment, such as changes of operating personnel, assembly equipment, and material flow, would decrease assembly precision and quality of final products, which further increases difficulty of noise and vibration control [1], faults diagnosis [2–4], bending, and vibration analysis of structural parts, also influences the overall performance of such as suspension systems [5], universal joint in steering handling mechanism [6], and rotated shafts [7].With customer demand for personalized and diversified product models, such as different requirements for power, safety, comfortableness, and energy conservation, mixed model assembly lines (MMALs) gradually replace the conventional single model assembly lines (SMALs) and become the mainstream assembly mode in the industry of construction machinery. Proposed by Salveson in the 1950s [8], assembly line balancing problem (ALBP) in essence is a combinatorial optimization problem of rationally assigning assembly tasks into workstations and meanwhile minimizing differences of operation time between workstations. ALBP can be divided into two categories, both of which are typical NP-hard problems [9, 10]: given the cycle time, minimizing the number of workstations and given the number of workstations, minimizing the cycle time.Many researchers heretofore have launched in-depth studies on assembly line balancing problem (ALBP), especially on the mixed-model assembly line balancing problem (MMALBP) mainly owing to the capability of MMAL of “producing the needed products in needed quantity at needed time” to effectively improve enterprise competitiveness. Scholl and Becker [11] carried out a comprehensive survey of simple assembly line balancing problem (SALBP) research with a special emphasis on exact and heuristic solution procedures of SALBP. Regarding MMALBP, Merengo et al. [12] analyzed some typical problems of manual, mixed-model assembly lines and presented new balancing methodologies pursuing the common goals of minimizing the rate of incomplete jobs in paced lines and in moving lines or the probability of blocking/starvation events (in unpaced lines) and reducing WIP. Haq et al. [13] dealt with mixed-model assembly line balancing to minimize the number of workstations by incorporating a hybrid genetic algorithm approach which used the solution from the modified ranked positional method as the initial solution to reduce the search space within the global space, thereby reducing search time. Bukchin and Rabinowitch [14] relaxed the restriction that a task that is common to multiple models must be assigned to a single station and developed an optimal solution procedure based on a backtracking branch-and-bound algorithm to minimize the sum of stations and task duplication costs. Özcan and Toklu [15] presented a new mathematical model minimizing the number of mated-stations as the primary objective and the number of stations as a secondary objective for a given cycle time and introduced a simulated annealing algorithm for the mixed-model two-sided assembly line balancing problem. Akpınar et al. [16, 17] proposed a hybrid genetic algorithm sequentially hybridizing Kilbridge and Wester Heuristic, Phase-I of Moodie and Young method and Ranked Positional Weight Technique to solve mixed model assembly line balancing problem of type I with objectives of minimizing the number of workstations, maximizing the workload smoothness between and within workstations. Aiming at stochastic environment of MMALs, Xu and Xiao [18] provided min-max related and a-worst scenario based robust criteria to formulate corresponding optimization models and introduced robust optimization approaches to balance mixed model assembly lines with uncertain task times and daily model mix changes by scenario planning. Yagmahan [19] considered operation time variations together with the number of stations, the line efficiency, and the smooth production to formulate the mixed-model assembly line balancing problem and proposed a more efficient and effective multiobjective ant colony optimization (MOACO) algorithm to solve this problem. Manavizadeh et al. [20] presented a multiobjective genetic algorithm (MOGA) to solve MMALBP in response to different market demands considering cycle time (CT) and the number of stations simultaneously and minimizing capital costs of designing multiple assembly lines and carried out a comparison between six multiobjective evolutionary algorithms (MOEA) to determine the best method for specific situation. Most recently, aiming at the balancing problem of product family assembly line (PFAL), Hou et al. [21] established a balancing model for PFAL and simultaneously proposed an improved dual-population genetic algorithm to solve product family assembly line balancing problem (PFALBP) with minimizing the number of stations, minimizing the load indexes between stations and within each station and maximizing task-related degree are used as optimization objectives optimization objectives.The related research aforementioned is the basis of assembly line planning and also the key of assembly line balancing. However, most studies are limited to analyzing single-model or mixed-model assembly line balancing problems from static point of view, and research on dynamic evolution process of assembly line is rare, especially the lack of evolution balancing research on modular product family assembly line which is typical in construction machinery manufacturing enterprises. Assembly line evolution would certainly induce adjustment costs, and product family design techniques such as platform, modularity, and commonality would also affect allocation of assembly tasks and assembly line balancing, therefore, aiming at the small-sized wheel loader product family and in order to better guide enterprises to implement product family assembly line planning and innovation we address the dynamic planning of evolution balancing for PFAL based on analysis of product family evolution. Firstly, relation between external influencing factors of product family evolution and assembly line evolution is selectively analyzed. Then, in order to improve assembly efficiency and optimize the assembly line, the precedence graph of assembly tasks is converted into AOE-net by specific rules; the critical tasks and critical path are identified using critical chain technology. Finally, in this paper minimizing the number of workstations, minimizing in-station and between-station load indexes, maximizing task correlation, and minimizing adjustment costs are set as the optimization objectives; the design techniques such as product platform and modularity and critical chain technology are introduced into the evolution balancing model of PFAL, and the evolution balancing problem of PFAL is optimized using improved dual-population genetic algorithm to realize dual objectives of improving assembly efficiency and reducing adjustment costs.


## 2. Evolution Balancing Process of PFAL for SWL

Driven by customer demand, core technology, and market competition, product families evolve constantly [22], which is mainly embodied in the replacement of modules or components and variation in module partition on microscopic level, such as the frame system module in small-sized wheel loader evolving from 915 to 916B and to 918 and 918Te; and embodied in the change of product family architecture and configuration difference of product variants on macroscopic level; as shown in Figure 1. There are two situations in the evolution process of product family: gradual improvement and abrupt change. The former includes adjustment of production quantity for different product variants and operations such as addition, removal, modification, and innovation on variant/unique modules in order to accommodate customer requirement differences in function or performance or to implement continuous improvement in product cost or quality, while the latter is mainly due to the emergence of new technology, material, or process which promotes core technology upgrading of product platform or product family.Figure 1
Evolution of small-sized wheel loader.Product family evolution propels incessant renewal and adjustment of its assembly line. Change of product mix ratio in different periods of time or operation time variation of assembly tasks in new product variants leads the existing balancing scheme to be no longer valid; in other words, when new products are introduced or operation time of tasks changes, the tasks should be reassigned to maintain load balancing of assembly line, which is defined as evolution balancing problem of assembly line in this paper. Product family assembly line planning must be able to rapidly and efficiently respond to the dynamic evolution of product family such as adding, removing, and upgrading modules and changes of various planning elements such as cost and new technology introduction and fully consider the influence of dynamic quantity change of variant products, task addition or removal, operation time variation, and different solutions of module partition on task assignment and assembly line balancing schemes. In all, product family assembly line must realize balancing in the coevolution process with product family; namely, evolution balancing as shown in Figure2, share assembly resources between product variants and even generational products to the greatest extent and provide high quality and low cost individualized products in the shortest possible time and reduce the adjustment costs of assembly line [23, 24].Figure 2
Evolution balancing process of PFAL.


## 3. Evolution Balancing Model of PFAL for SWL

In this paper, we focus on the evolution balancing process of modular product family assembly line, where the modular product family refers to a group/series of products oriented to specific market segmentation derived by adding, removing or replacing the variant or unique modules based on product platform. To demonstrate the concepts of product platform and modularity, a simplified example is shown in Figure3, where the working device is shared by different models and the extinct accessory modules with standard interface can realize specific functions.Figure 3
Example of product platform and modularity.Product platform and modularity play an important role in product family development, configuration, production, and so on. Generally, manufacturing enterprises achieve product diversification and customization by means of addition, deletion, and/or modification operations onto variant or unique functional modules and meanwhile try to keep the product platform constant; hence the product platform and key functional modules possess the characteristic of relative higher stability; in other words, the product platform and key functional modules would remain unchanged in the product family evolution process with much higher probability. We take the relative higher stability of product platform and key functional modules into consideration in evolution balancing planning process with the purpose of realizing assembly line balancing as well as minimizing adjustment costs.In addition, we pay attention to improving assembly efficiency while balancing the assembly line. The critical tasks in assembly process have larger space for improvement and restrict/determine the overall assembly efficiency, and the duration of critical tasks and even the tasks themselves are with relative lower stability compared with product platform and key functional modules; in other words, the duration of critical tasks change frequently and/or greatly and the critical tasks themselves are likely to be replaced by some other tasks. Therefore, we treat critical tasks as flexible planning constraints in the evolution balancing optimization model of PFAL.


### 3.1. Product Platform/Modularity

Modularity is a prevailing design method based on product functional analysis, in which functional modules are divided according to specific criteria and different products are configured through module selection and combination to meet diversified market demand [25]. Modular design supports mass customization with costs close to that of mass production and finds the best balancing point between product variety, cost, and performance; in essence, it is the process of product structure analysis and restructuring. Principle of module division is to make components in some module with strong correlation, while the components between modules with little correlation. Modular design technique has an important influence on the balancing planning of PFAL, which mainly manifested that correlation between the assembly tasks for a certain module is strong; enterprises usually assemble key functional modules in advance and strictly assign the tasks strongly correlated to some specific functional module into the same station. In this paper, we define task correlation and tend to assign tasks with higher correlation into the same station to reflect the practical assembly situations.Product platform is defined as “a set of subsystems and interfaces developed to form a common structure from which a stream of derivative products can be efficiently developed and produced” [26], which is an effective development strategy to improve external diversity and reduce internal differentiation by means of adding, deleting, and/or replacing one or several modules based on platform to derive a family of products and meet customers’ diversified needs. Once the product platform is determined, it will generally be relatively stable in the gradual evolution process of product family. Therefore, in the evolution balancing planning process of PFAL, the platform-related assembly tasks should be assigned into fixed stations rather than influenced by variations of other tasks, which is conductive to reducing adjustment costs.Modular product family can be represented by a hierarchical model, as shown in Figure4, where the functional modules are categorized into common modules, optional modules, and unique modules. Within the same functional module, there are several module instances with favorable interchangeability, and designers can configure different product variants to meet diversified customer requirements by specific selection and combination mechanism. As in small-sized wheel loader product family, according to the technological capacity in the cooperating company, the braking system module is shared by all the variants in the product family, so it is defined as the common module. In order to meet different requirements for power, the company purchases different power systems such as ZH4100G2, LR4A3-G84X1Q, and LR4B3-G84X4Q, as shown in Figure 1, so the power system module is defined as the variant or optional module.Figure 4
Hierarchical model of modular product family.


### 3.2. Critical Chain Technique

AOE-net (Activity on Edge net) represents the sequence of production activities by directed edges and is mainly utilized to estimate the completion time of the whole project and to search the critical path, by shortening the time of which the efficiency of the entire project would be improved. Therefore, the activities in PFAL could be shown as an AOE-net.AOE-net is a weighted directed acyclic graph, where the vertices denote events, the arcs, and the corresponding weights denote activities and their duration, respectively. An AOE net including nine events (v
1
,
v
2
,
…
,
v
9) and eleven activities (a
1
,
a
2
,
…
,
a
11) is shown in Figure 5. The whole process has one and only one starting vertex v
1 and end vertex v
9; that is, the net has only one vertex with zero in-degree and only one vertex with zero out-degree. The occurrence of an event means the preceding activity has (activities have) been completed and the subsequent activity (activities) can begin. For example, the occurrence of event v
6 means activities a
5 and a
6 have been completed and activities a
8 and a
9 can be carried out next, and the duration of activity a
1 is four units of time.Figure 5
AOE-net.The main research issues of AOE-net include the following: (1) how much time at least is required to complete the whole project and (2) what are the key activities affecting the project progress. In an AOE-net, part of the activities can be performed simultaneously, and the shortest possible time for completing the whole project is the sum of weighted time in the longest path from the starting vertex to the end vertex, that is, the sum of duration required by the activities on the longest path which is, therefore, defined as the critical path.Assuming the starting point isv
1, the length of the longest path from v
1 to v
i is called the earliest starting time (EST) of the event v
i which determines the earliest starting time of activities represented by arcs starting with vertex v
i. Here we use e
(
i
) to denote the earliest starting time (EST) and l
(
i
) to represent the latest starting time (LST) of the activity a
i, where LST means the latest time to start the activity a
i on the premise of not delaying the whole project and the difference (l
(
i
)
-
e
(
i
)) between ES and LS denotes the spare time (namely, time remaining/surplus) of the activity a
i. When the time remaining/surplus equals zero, the activity a
i has no spare time indicating it is a critical activity. Consequently, the critical activities constitute a critical path and it is important for the progress of the whole project to improve efficiency of the critical activities, while the early completion of the noncritical activities cannot speed up the progress of the project.In Figure5, the critical path from v
1 to v
9 is v
1
→
v
3
→
v
6
→
v
8
→
v
9 with the length 18 which indicates that EST is 18, while EST of a
7 is 6 and LST is 16, which implies that postponing or starting the activity ahead of time by 10 units of time would not influence the progress of the whole project. Hence it is the key for improving the project progress or efficiency to analyze the critical path or activities.The core of acquiring the critical path is to seek out the critical activitya
i meeting the requirement of l
(
i
)
=
e
(
i
). To simplify analysis, we define the earliest and latest starting time of event v
i as v
e
(
i
) and v
l
(
i
), respectively. Supposing the activity a
i is represented by the arc between vertex v
j and v
k and the time needed is T
j
k, then the critical activity a
i needs to meet the following requirements:(1)
e
i
=
v
e
j
,
l
i
=
v
l
k
-
T
j
k
.The algorithm to acquire the critical path or activities is shown as follows:(1)
constructing and initializing an AOE-net containingn vertexes;
(2)
starting from the vertexv
1 and setting v
e
(
1
)
=
0 and then successively calculating EST v
e
(
i
) of all the rest vertexes by topology algorithm: if the number of vertexes in the some obtained topological sequence is less than n, which means a loop exists in the net, then it is impossible to acquire the critical path and the algorithm terminates, shifting to step (3), otherwise;
(3)
starting from the end vertexv
n and setting v
l
(
n
)
=
v
e
(
n
) and then successively calculating LST v
l
(
i
)  (1
≤
i
≤
n
-
1) of all the rest events by topology algorithm;
(4)
according tov
l
(
i
) and v
e
(
i
) of each event (vertex), calculating EST e
(
i
) and LST l
(
i
) of activity a
i, if e
(
i
)
=
l
(
i
), then a
i is the critical activity;
(5)
determining the critical activities and path according to the results in step (4) and the algorithm terminates.


### 3.3. Optimization Objectives

Based on the mathematical model of product family [21], we study both product family assembly line balancing and evolution planning comprehensively. The main objective of PFAL evolution planning is to minimize change of assembly line while maximizing product assembly capability, that is, tradeoff between minimization of adjustment costs and maximization of productivity. We suppose that the existing assembly line has already balanced and needs adjustment owing to the influences of external factors such as customer requirements, product functions or quantities, materials, and technologies. The adjustment costs in evolution balancing process include costs induced by adjustment of tools, equipment, and labors, and the objective of minimizing adjustment costs I is represented in the following:(2)
I
=
α
Δ
Nu
m
s
+
β
Δ
Nu
m
p
+
γ
Δ
T
total
+
δ
Δ
T
idle
+
ε
Δ
T
cycle
⁡
+
ϕ
Δ
L
+
φ
Δ
Nu
m
w
,where Nu
m
s, Nu
m
p, T
total, T
idle, T
cycle
⁡, L, and Nu
m
w, respectively, denote total number of stations, total number of assembly workers, total time of assembly, idle time, cycle time, logistical cost, and total number of tasks, while α, β, γ, δ, ε, ϕ, φ signify the degree of influence of each index on adjustment costs and are determined on the basis of the practical situations of enterprises and expert experiences. According to (2), the objective of minimizing adjustment costs is met only when variations of all indexes mentioned above reach their lowest.Aiming at the optimization problem for PFAL evolution balancing, the optimization objective of evolution balancing is determined by synthesizing the four balancing objectivesZ proposed in [21] and the evolution objective of minimizing adjustment costs I, as shown in (3). Besides, the influences of product family design and critical chain techniques on assembly line evolution balancing are translated into constraint conditions and introduced into the optimization model of PFAL evolution balancing, and the evolution balancing problem is optimized by the dual-population genetic algorithm proposed in [21]:(3)
P
min
⁡
=
μ
Z
+
η
I
,where μ, η are coefficients for dimension adjustment.


### 3.4. Improved Dual-Population Genetic Algorithm

Product family mixed-model assembly line balancing is a typical NP-hard problem with many influencing factors and complicated constraints, the number of task combination increases exponentially with the number of tasks and it is difficult to solve this type of problem using traditional optimization methods, which makes genetic algorithm one of the best choices. Therefore, in this paper we adopt the dual-population genetic algorithm proposed in literature [21] to solve the optimization problem of product family assembly line. The process of this algorithm is shown in Figure 6 and the main characteristics are concluded as follows:(1)
using real number encoding method, where each gene stands for one task and the encoding length equals the total number of tasks;
(2)
adopting single-point crossover mode as shown in Figure7 and the mutation operation process as shown in Figure 8.Figure 6
Process of dual-population genetic algorithm.Figure 7
Process of crossover.Figure 8
Process of mutation.


### 3.5. Evolution Balancing Optimization Process

The evolution planning process of PFAL based on product family design and critical chain techniques is shown in Figure9 and can be implemented in the following steps.Figure 9
Evolution planning model of PFAL.Step 1.
Based on the comprehensive precedence graph of product family, we determine that the task sequence meets the precedence order using topological sorting algorithm, convert the precedence graph into AOE-net, and then seek out the critical tasks and critical path by critical chain algorithm.Step 2.
We determine constraints and objectives of the evolution balancing optimization problem. Besides the constraints in the load balancing model, we add two constraints: assigning platform-related tasks to fixed stations and assigning critical tasks to flexible stations. The optimization objectives include minimizing number of stations, in-station and between-station load index and adjustment cost, and maximizing task correlation.Step 3.
We assign the tasks to stations using improved dual-population genetic algorithm and obtain the optimal assignment results of PFAL evolution balancing problem.


## 3.1. Product Platform/Modularity

Modularity is a prevailing design method based on product functional analysis, in which functional modules are divided according to specific criteria and different products are configured through module selection and combination to meet diversified market demand [25]. Modular design supports mass customization with costs close to that of mass production and finds the best balancing point between product variety, cost, and performance; in essence, it is the process of product structure analysis and restructuring. Principle of module division is to make components in some module with strong correlation, while the components between modules with little correlation. Modular design technique has an important influence on the balancing planning of PFAL, which mainly manifested that correlation between the assembly tasks for a certain module is strong; enterprises usually assemble key functional modules in advance and strictly assign the tasks strongly correlated to some specific functional module into the same station. In this paper, we define task correlation and tend to assign tasks with higher correlation into the same station to reflect the practical assembly situations.Product platform is defined as “a set of subsystems and interfaces developed to form a common structure from which a stream of derivative products can be efficiently developed and produced” [26], which is an effective development strategy to improve external diversity and reduce internal differentiation by means of adding, deleting, and/or replacing one or several modules based on platform to derive a family of products and meet customers’ diversified needs. Once the product platform is determined, it will generally be relatively stable in the gradual evolution process of product family. Therefore, in the evolution balancing planning process of PFAL, the platform-related assembly tasks should be assigned into fixed stations rather than influenced by variations of other tasks, which is conductive to reducing adjustment costs.Modular product family can be represented by a hierarchical model, as shown in Figure4, where the functional modules are categorized into common modules, optional modules, and unique modules. Within the same functional module, there are several module instances with favorable interchangeability, and designers can configure different product variants to meet diversified customer requirements by specific selection and combination mechanism. As in small-sized wheel loader product family, according to the technological capacity in the cooperating company, the braking system module is shared by all the variants in the product family, so it is defined as the common module. In order to meet different requirements for power, the company purchases different power systems such as ZH4100G2, LR4A3-G84X1Q, and LR4B3-G84X4Q, as shown in Figure 1, so the power system module is defined as the variant or optional module.Figure 4
Hierarchical model of modular product family.


## 3.2. Critical Chain Technique

AOE-net (Activity on Edge net) represents the sequence of production activities by directed edges and is mainly utilized to estimate the completion time of the whole project and to search the critical path, by shortening the time of which the efficiency of the entire project would be improved. Therefore, the activities in PFAL could be shown as an AOE-net.AOE-net is a weighted directed acyclic graph, where the vertices denote events, the arcs, and the corresponding weights denote activities and their duration, respectively. An AOE net including nine events (v
1
,
v
2
,
…
,
v
9) and eleven activities (a
1
,
a
2
,
…
,
a
11) is shown in Figure 5. The whole process has one and only one starting vertex v
1 and end vertex v
9; that is, the net has only one vertex with zero in-degree and only one vertex with zero out-degree. The occurrence of an event means the preceding activity has (activities have) been completed and the subsequent activity (activities) can begin. For example, the occurrence of event v
6 means activities a
5 and a
6 have been completed and activities a
8 and a
9 can be carried out next, and the duration of activity a
1 is four units of time.Figure 5
AOE-net.The main research issues of AOE-net include the following: (1) how much time at least is required to complete the whole project and (2) what are the key activities affecting the project progress. In an AOE-net, part of the activities can be performed simultaneously, and the shortest possible time for completing the whole project is the sum of weighted time in the longest path from the starting vertex to the end vertex, that is, the sum of duration required by the activities on the longest path which is, therefore, defined as the critical path.Assuming the starting point isv
1, the length of the longest path from v
1 to v
i is called the earliest starting time (EST) of the event v
i which determines the earliest starting time of activities represented by arcs starting with vertex v
i. Here we use e
(
i
) to denote the earliest starting time (EST) and l
(
i
) to represent the latest starting time (LST) of the activity a
i, where LST means the latest time to start the activity a
i on the premise of not delaying the whole project and the difference (l
(
i
)
-
e
(
i
)) between ES and LS denotes the spare time (namely, time remaining/surplus) of the activity a
i. When the time remaining/surplus equals zero, the activity a
i has no spare time indicating it is a critical activity. Consequently, the critical activities constitute a critical path and it is important for the progress of the whole project to improve efficiency of the critical activities, while the early completion of the noncritical activities cannot speed up the progress of the project.In Figure5, the critical path from v
1 to v
9 is v
1
→
v
3
→
v
6
→
v
8
→
v
9 with the length 18 which indicates that EST is 18, while EST of a
7 is 6 and LST is 16, which implies that postponing or starting the activity ahead of time by 10 units of time would not influence the progress of the whole project. Hence it is the key for improving the project progress or efficiency to analyze the critical path or activities.The core of acquiring the critical path is to seek out the critical activitya
i meeting the requirement of l
(
i
)
=
e
(
i
). To simplify analysis, we define the earliest and latest starting time of event v
i as v
e
(
i
) and v
l
(
i
), respectively. Supposing the activity a
i is represented by the arc between vertex v
j and v
k and the time needed is T
j
k, then the critical activity a
i needs to meet the following requirements:(1)
e
i
=
v
e
j
,
l
i
=
v
l
k
-
T
j
k
.The algorithm to acquire the critical path or activities is shown as follows:(1)
constructing and initializing an AOE-net containingn vertexes;
(2)
starting from the vertexv
1 and setting v
e
(
1
)
=
0 and then successively calculating EST v
e
(
i
) of all the rest vertexes by topology algorithm: if the number of vertexes in the some obtained topological sequence is less than n, which means a loop exists in the net, then it is impossible to acquire the critical path and the algorithm terminates, shifting to step (3), otherwise;
(3)
starting from the end vertexv
n and setting v
l
(
n
)
=
v
e
(
n
) and then successively calculating LST v
l
(
i
)  (1
≤
i
≤
n
-
1) of all the rest events by topology algorithm;
(4)
according tov
l
(
i
) and v
e
(
i
) of each event (vertex), calculating EST e
(
i
) and LST l
(
i
) of activity a
i, if e
(
i
)
=
l
(
i
), then a
i is the critical activity;
(5)
determining the critical activities and path according to the results in step (4) and the algorithm terminates.


## 3.3. Optimization Objectives

Based on the mathematical model of product family [21], we study both product family assembly line balancing and evolution planning comprehensively. The main objective of PFAL evolution planning is to minimize change of assembly line while maximizing product assembly capability, that is, tradeoff between minimization of adjustment costs and maximization of productivity. We suppose that the existing assembly line has already balanced and needs adjustment owing to the influences of external factors such as customer requirements, product functions or quantities, materials, and technologies. The adjustment costs in evolution balancing process include costs induced by adjustment of tools, equipment, and labors, and the objective of minimizing adjustment costs I is represented in the following:(2)
I
=
α
Δ
Nu
m
s
+
β
Δ
Nu
m
p
+
γ
Δ
T
total
+
δ
Δ
T
idle
+
ε
Δ
T
cycle
⁡
+
ϕ
Δ
L
+
φ
Δ
Nu
m
w
,where Nu
m
s, Nu
m
p, T
total, T
idle, T
cycle
⁡, L, and Nu
m
w, respectively, denote total number of stations, total number of assembly workers, total time of assembly, idle time, cycle time, logistical cost, and total number of tasks, while α, β, γ, δ, ε, ϕ, φ signify the degree of influence of each index on adjustment costs and are determined on the basis of the practical situations of enterprises and expert experiences. According to (2), the objective of minimizing adjustment costs is met only when variations of all indexes mentioned above reach their lowest.Aiming at the optimization problem for PFAL evolution balancing, the optimization objective of evolution balancing is determined by synthesizing the four balancing objectivesZ proposed in [21] and the evolution objective of minimizing adjustment costs I, as shown in (3). Besides, the influences of product family design and critical chain techniques on assembly line evolution balancing are translated into constraint conditions and introduced into the optimization model of PFAL evolution balancing, and the evolution balancing problem is optimized by the dual-population genetic algorithm proposed in [21]:(3)
P
min
⁡
=
μ
Z
+
η
I
,where μ, η are coefficients for dimension adjustment.


## 3.4. Improved Dual-Population Genetic Algorithm

Product family mixed-model assembly line balancing is a typical NP-hard problem with many influencing factors and complicated constraints, the number of task combination increases exponentially with the number of tasks and it is difficult to solve this type of problem using traditional optimization methods, which makes genetic algorithm one of the best choices. Therefore, in this paper we adopt the dual-population genetic algorithm proposed in literature [21] to solve the optimization problem of product family assembly line. The process of this algorithm is shown in Figure 6 and the main characteristics are concluded as follows:(1)
using real number encoding method, where each gene stands for one task and the encoding length equals the total number of tasks;
(2)
adopting single-point crossover mode as shown in Figure7 and the mutation operation process as shown in Figure 8.Figure 6
Process of dual-population genetic algorithm.Figure 7
Process of crossover.Figure 8
Process of mutation.


## 3.5. Evolution Balancing Optimization Process

The evolution planning process of PFAL based on product family design and critical chain techniques is shown in Figure9 and can be implemented in the following steps.Figure 9
Evolution planning model of PFAL.Step 1.
Based on the comprehensive precedence graph of product family, we determine that the task sequence meets the precedence order using topological sorting algorithm, convert the precedence graph into AOE-net, and then seek out the critical tasks and critical path by critical chain algorithm.Step 2.
We determine constraints and objectives of the evolution balancing optimization problem. Besides the constraints in the load balancing model, we add two constraints: assigning platform-related tasks to fixed stations and assigning critical tasks to flexible stations. The optimization objectives include minimizing number of stations, in-station and between-station load index and adjustment cost, and maximizing task correlation.Step 3.
We assign the tasks to stations using improved dual-population genetic algorithm and obtain the optimal assignment results of PFAL evolution balancing problem.


## 4. SWL Case Study

### 4.1. Evolution Balancing of PFAL

In this section, the assembly line of small-sized wheel loader product family in some international enterprise [21] is restudied to verify the effectiveness and feasibility of the proposed evolution balancing model of PFAL. The small-sized wheel loader is a typical modular product family, which concludes frame system module, braking system module, driving system module, cab module, and so on, as shown in Figure 10. Different modules have one or more module instances, so the company can configure hundreds of wheel loader models to meet customer needs. Unavoidably, the functional or performance requirements of customers in different period of time changes abruptly, so the corresponding assembly line needs frequent adjustment which induces considerable cost. To lower or control the adjustment cost in product family evolution process.Figure 10
Modular architecture of small-sized wheel loader.The characteristics and relevant parameters of the assembly line of the small-sized wheel loader product family are described as follows.(1)
The product family contains three series of products (916, 918, and 920T), which are assembled on the same line. The daily work time is 560 units of time and the demand quantities of 916, 918, and 920T are 2, 4, and 1, respectively; thus the cycle time CT equals 80 units of time(
=
560
/
(
2
+
4
+
1
)
).
(2)
According to the precedence of assembly task, the duration of tasks, and the demand quantity of each variant, the comprehensive precedence graph can be constructed [27] and converted into the precedence relation table as shown in Table 1, including 30 tasks and the corresponding operation time (duration).
(3)
When operation time of a certain task is greater than CT in the assembly process, increasing the number of operators is more conducive to making operation time less than CT.
(4)
Certain correlation exists between tasks and grouping tasks with good/better correlation into the same station will bring convenience and operability to the whole assembly line. By investigation and survey in enterprise and the empirical knowledge of domain experts, correlation values between 2 of 30 tasks are shown in Table2 while the task correlation not listed in the table all equals zero.Table 1
Precedence relation between assembly tasks.
Task
A1
A2
A3
A4
A5
A6
A7
A8
A9
A10
Predecessor(s)
—
—
—
A1, A2, A3
A4
A5
A6
A6
—
—
Duration
41
42
40
39
39
48
36
36
28
30
Operators assigned
5
6
4
10
14
2
3
1
1
1
Task
A11
A12
A13
A14
A15
A16
A17
A18
A19
A20
Predecessor(s)
—
A6, A9,  A10, A11
A12
A13
A13
A13
A13
A14, A15,  A16, A17
A18
A18
Duration
35
14
13
12
15
18
15
5
8
7
Operators assigned
1
1
1
1
1
1
1
1
1
1
Task
A21
A22
A23
A24
A25
A26
A27
A28
A29
A30
Predecessor(s)
A18
A19, A20,  A21
A22
A18, A23
A23
A18
A25, A26
A23
A23
A23
Duration
7
7
11
23
17
4
8
24
22
31
Operators assigned
1
1
1
1
1
1
1
1
1
1Table 2
Correlation between tasks.
Task
Task
Correlation
Task
Task
Correlation
A1
A2
0.8
A15
A18
0.6
A1
A3
0.5
A16
A17
0.7
A1
A4
0.1
A17
A18
0.6
A1
A5
0.1
A19
A20
0.5
A2
A3
0.7
A19
A21
0.5
A2
A4
0.7
A19
A22
0.5
A3
A4
0.8
A19
A23
0.5
A4
A5
0.8
A20
A21
0.5
A4
A6
0.4
A21
A22
0.8
A5
A6
0.5
A21
A23
0.5
A6
A7
0.1
A22
A23
0.7
A6
A12
0.8
A25
A26
0.7
A7
A8
0.5
A25
A27
0.7
A9
A12
0.8
A26
A27
0.4
A10
A12
0.8
A28
A29
0.4
A11
A12
0.8
A28
A30
0.4
A14
A15
0.7
A29
A30
0.4According to the precedence relation between tasks as shown in Table1 and the transformation rules of AOE-net, the AOE-net of the 30 assembly tasks is constructed as shown in Figure 11.Figure 11
AOE-net of related tasks.Using the introduced algorithm of critical chain in Section3.2, the relevant times such as EST, LST, and spare time and critical activities whose EST is equal to LST are acquired as shown in Table 3.Table 3
Relevant times in AOE-net.
Task
A1
A2
A3
A4
A5
A6
A7
A8
A9
A10
LST
41
41
80
80
119
167
274
274
167
167
EST
41
41
40
80
119
167
203
203
28
30
Spare time
0
0
40
0
0
0
71
71
139
137
Task
A11
A12
A13
A14
A15
A16
A17
A18
A19
A20
LST
167
181
194
212
212
212
212
217
225
225
EST
35
181
194
206
209
212
212
217
225
224
Spare time
132
0
0
6
3
0
0
0
0
1
Task
A21
A22
A23
A24
A25
A26
A27
A28
A29
A30
LST
225
232
243
274
266
260
274
274
274
274
EST
224
232
243
255
260
221
260
267
267
274
Spare time
1
0
0
19
6
39
14
7
7
0Four critical chains are found out and listed in Table4, by shortening the duration of critical tasks on which would greatly improve assembly efficiency.Table 4
Relevant tasks on the critical chain.
Critical chain 1
A1
A4
A5
A6
A12
A13
A16
A18
A19
A22
A23
A30
Critical chain 2
A2
A4
A5
A6
A12
A13
A16
A18
A19
A22
A23
A30
Critical chain 3
A1
A4
A5
A6
A12
A13
A17
A18
A19
A22
A23
A30
Critical chain 4
A2
A4
A5
A6
A12
A13
A17
A18
A19
A22
A23
A30Via investigation in cooperative enterprise and modularity analysis, among all tasks of the 916, 918, and 920T assembly line, the tasks involved in loader platform and certain modules are shown in Table5. Adding the constraints mentioned above into the improved genetic algorithm [21], the number of stations, in-station and between-station loads, and correlation between activities are optimized, meanwhile, the evolution-related objectives such as minimizing variations of quantity of operators, cycle time, and material flows are taken into consideration, and the optimization results are shown in Table 6.Table 5
Relevant tasks for certain modules.
Module
Relevant tasks
Module A
1, 2, 4, 5
Module B
6, 10, 12
Module C
14, 15, 17
Module D
16, 18, 19, 21
Module E
20, 22, 23, 26, 28, 29Table 6
Planning results of assembly line evolution.
Station
Task
Balancing indexes
1
1, 9
(1) Nine stations(2) Between-station load: 21 (3) In-station load: 5.1
(4) Correlation of tasks: 4.9
2
2, 10
3
3, 11
4
4, 5
5
6, 12, 13
6
7, 14, 15, 17
7
8, 16, 18, 19, 21
8
20, 22, 23, 26, 28
9
25, 27, 29, 30


### 4.2. Performance Analysis

To further demonstrate the effectiveness of the proposed planning model for PFAL evolution in this paper, the results are compared with those of load balancing model [21] as shown in Table 7.Table 7
Comparison of planning results.
Model
Station
Task
Balancing indexes
Evolution assumptions
Adjustment cost
Load balancing model
1
1, 10
(1) Number of stations: 9(2) Between-station load: 18
(3) In-station load: 4.5 (4) Correlation of tasks: 4.8
(1) Deleting task 7 (unique task)(2) Deleting task 21 (unique task) (3) Adding one new task in station 8 (4) Adding one new task after deleting task 7
5
+
6
+
7
+
5
=
23
2
2, 9
3
3, 11
4
4, 5
5
6, 12, 13
6
7, 16, 18, 19, 20
7
8, 14, 15, 17
8
21, 22, 23, 24, 26, 28
9
25, 27, 29, 30
Evolution balancing model
1
1, 9
(1) Number of stations: 9(2) Between-station load: 21 (3) In-station load: 5.1 (4) Correlation of tasks: 4.9
4
+
5
+
6
+
4
=
19
2
2, 10
3
3, 11
4
4, 5
5
6, 12, 13
6
7, 14, 15, 17
7
8, 16, 18, 19, 21
8
20, 22, 23, 26, 28
9
25, 27, 29, 30It is observed from the table that, after adding constraints related to product family design and critical chain techniques, the optimized number of stations is still 9, but the between-station and in-station indexes have higher values, which indicates that the optimization result is not superior to that of when only considering load balancing. However, not only load balancing of PFAL but also its evolution process is evolved in this paper. Through analysis of labor cost variation induced by assembly line adjustment based on different balancing models (load balancing model or evolution balancing model), it is not difficult to find that, if the load balancing model adopted, then the adjustment cost is 23 units of labor cost, while if we use the evolution balancing model proposed in this paper, the adjustment cost is 19 units of labor cost.Owing to individualization of customer requirement and shorter lifecycle of seasonal product family, adjustment or evolution balancing of PFAL becomes increasingly frequent; hence the benefits of evolution balancing model are much more considerable. Therefore, when dealing with assembly line balancing oriented to product family evolution process, we should not only consider loader balancing but also treat evolution planning as one more important optimization objective.


## 4.1. Evolution Balancing of PFAL

In this section, the assembly line of small-sized wheel loader product family in some international enterprise [21] is restudied to verify the effectiveness and feasibility of the proposed evolution balancing model of PFAL. The small-sized wheel loader is a typical modular product family, which concludes frame system module, braking system module, driving system module, cab module, and so on, as shown in Figure 10. Different modules have one or more module instances, so the company can configure hundreds of wheel loader models to meet customer needs. Unavoidably, the functional or performance requirements of customers in different period of time changes abruptly, so the corresponding assembly line needs frequent adjustment which induces considerable cost. To lower or control the adjustment cost in product family evolution process.Figure 10
Modular architecture of small-sized wheel loader.The characteristics and relevant parameters of the assembly line of the small-sized wheel loader product family are described as follows.(1)
The product family contains three series of products (916, 918, and 920T), which are assembled on the same line. The daily work time is 560 units of time and the demand quantities of 916, 918, and 920T are 2, 4, and 1, respectively; thus the cycle time CT equals 80 units of time(
=
560
/
(
2
+
4
+
1
)
).
(2)
According to the precedence of assembly task, the duration of tasks, and the demand quantity of each variant, the comprehensive precedence graph can be constructed [27] and converted into the precedence relation table as shown in Table 1, including 30 tasks and the corresponding operation time (duration).
(3)
When operation time of a certain task is greater than CT in the assembly process, increasing the number of operators is more conducive to making operation time less than CT.
(4)
Certain correlation exists between tasks and grouping tasks with good/better correlation into the same station will bring convenience and operability to the whole assembly line. By investigation and survey in enterprise and the empirical knowledge of domain experts, correlation values between 2 of 30 tasks are shown in Table2 while the task correlation not listed in the table all equals zero.Table 1
Precedence relation between assembly tasks.
Task
A1
A2
A3
A4
A5
A6
A7
A8
A9
A10
Predecessor(s)
—
—
—
A1, A2, A3
A4
A5
A6
A6
—
—
Duration
41
42
40
39
39
48
36
36
28
30
Operators assigned
5
6
4
10
14
2
3
1
1
1
Task
A11
A12
A13
A14
A15
A16
A17
A18
A19
A20
Predecessor(s)
—
A6, A9,  A10, A11
A12
A13
A13
A13
A13
A14, A15,  A16, A17
A18
A18
Duration
35
14
13
12
15
18
15
5
8
7
Operators assigned
1
1
1
1
1
1
1
1
1
1
Task
A21
A22
A23
A24
A25
A26
A27
A28
A29
A30
Predecessor(s)
A18
A19, A20,  A21
A22
A18, A23
A23
A18
A25, A26
A23
A23
A23
Duration
7
7
11
23
17
4
8
24
22
31
Operators assigned
1
1
1
1
1
1
1
1
1
1Table 2
Correlation between tasks.
Task
Task
Correlation
Task
Task
Correlation
A1
A2
0.8
A15
A18
0.6
A1
A3
0.5
A16
A17
0.7
A1
A4
0.1
A17
A18
0.6
A1
A5
0.1
A19
A20
0.5
A2
A3
0.7
A19
A21
0.5
A2
A4
0.7
A19
A22
0.5
A3
A4
0.8
A19
A23
0.5
A4
A5
0.8
A20
A21
0.5
A4
A6
0.4
A21
A22
0.8
A5
A6
0.5
A21
A23
0.5
A6
A7
0.1
A22
A23
0.7
A6
A12
0.8
A25
A26
0.7
A7
A8
0.5
A25
A27
0.7
A9
A12
0.8
A26
A27
0.4
A10
A12
0.8
A28
A29
0.4
A11
A12
0.8
A28
A30
0.4
A14
A15
0.7
A29
A30
0.4According to the precedence relation between tasks as shown in Table1 and the transformation rules of AOE-net, the AOE-net of the 30 assembly tasks is constructed as shown in Figure 11.Figure 11
AOE-net of related tasks.Using the introduced algorithm of critical chain in Section3.2, the relevant times such as EST, LST, and spare time and critical activities whose EST is equal to LST are acquired as shown in Table 3.Table 3
Relevant times in AOE-net.
Task
A1
A2
A3
A4
A5
A6
A7
A8
A9
A10
LST
41
41
80
80
119
167
274
274
167
167
EST
41
41
40
80
119
167
203
203
28
30
Spare time
0
0
40
0
0
0
71
71
139
137
Task
A11
A12
A13
A14
A15
A16
A17
A18
A19
A20
LST
167
181
194
212
212
212
212
217
225
225
EST
35
181
194
206
209
212
212
217
225
224
Spare time
132
0
0
6
3
0
0
0
0
1
Task
A21
A22
A23
A24
A25
A26
A27
A28
A29
A30
LST
225
232
243
274
266
260
274
274
274
274
EST
224
232
243
255
260
221
260
267
267
274
Spare time
1
0
0
19
6
39
14
7
7
0Four critical chains are found out and listed in Table4, by shortening the duration of critical tasks on which would greatly improve assembly efficiency.Table 4
Relevant tasks on the critical chain.
Critical chain 1
A1
A4
A5
A6
A12
A13
A16
A18
A19
A22
A23
A30
Critical chain 2
A2
A4
A5
A6
A12
A13
A16
A18
A19
A22
A23
A30
Critical chain 3
A1
A4
A5
A6
A12
A13
A17
A18
A19
A22
A23
A30
Critical chain 4
A2
A4
A5
A6
A12
A13
A17
A18
A19
A22
A23
A30Via investigation in cooperative enterprise and modularity analysis, among all tasks of the 916, 918, and 920T assembly line, the tasks involved in loader platform and certain modules are shown in Table5. Adding the constraints mentioned above into the improved genetic algorithm [21], the number of stations, in-station and between-station loads, and correlation between activities are optimized, meanwhile, the evolution-related objectives such as minimizing variations of quantity of operators, cycle time, and material flows are taken into consideration, and the optimization results are shown in Table 6.Table 5
Relevant tasks for certain modules.
Module
Relevant tasks
Module A
1, 2, 4, 5
Module B
6, 10, 12
Module C
14, 15, 17
Module D
16, 18, 19, 21
Module E
20, 22, 23, 26, 28, 29Table 6
Planning results of assembly line evolution.
Station
Task
Balancing indexes
1
1, 9
(1) Nine stations(2) Between-station load: 21 (3) In-station load: 5.1
(4) Correlation of tasks: 4.9
2
2, 10
3
3, 11
4
4, 5
5
6, 12, 13
6
7, 14, 15, 17
7
8, 16, 18, 19, 21
8
20, 22, 23, 26, 28
9
25, 27, 29, 30


## 4.2. Performance Analysis

To further demonstrate the effectiveness of the proposed planning model for PFAL evolution in this paper, the results are compared with those of load balancing model [21] as shown in Table 7.Table 7
Comparison of planning results.
Model
Station
Task
Balancing indexes
Evolution assumptions
Adjustment cost
Load balancing model
1
1, 10
(1) Number of stations: 9(2) Between-station load: 18
(3) In-station load: 4.5 (4) Correlation of tasks: 4.8
(1) Deleting task 7 (unique task)(2) Deleting task 21 (unique task) (3) Adding one new task in station 8 (4) Adding one new task after deleting task 7
5
+
6
+
7
+
5
=
23
2
2, 9
3
3, 11
4
4, 5
5
6, 12, 13
6
7, 16, 18, 19, 20
7
8, 14, 15, 17
8
21, 22, 23, 24, 26, 28
9
25, 27, 29, 30
Evolution balancing model
1
1, 9
(1) Number of stations: 9(2) Between-station load: 21 (3) In-station load: 5.1 (4) Correlation of tasks: 4.9
4
+
5
+
6
+
4
=
19
2
2, 10
3
3, 11
4
4, 5
5
6, 12, 13
6
7, 14, 15, 17
7
8, 16, 18, 19, 21
8
20, 22, 23, 26, 28
9
25, 27, 29, 30It is observed from the table that, after adding constraints related to product family design and critical chain techniques, the optimized number of stations is still 9, but the between-station and in-station indexes have higher values, which indicates that the optimization result is not superior to that of when only considering load balancing. However, not only load balancing of PFAL but also its evolution process is evolved in this paper. Through analysis of labor cost variation induced by assembly line adjustment based on different balancing models (load balancing model or evolution balancing model), it is not difficult to find that, if the load balancing model adopted, then the adjustment cost is 23 units of labor cost, while if we use the evolution balancing model proposed in this paper, the adjustment cost is 19 units of labor cost.Owing to individualization of customer requirement and shorter lifecycle of seasonal product family, adjustment or evolution balancing of PFAL becomes increasingly frequent; hence the benefits of evolution balancing model are much more considerable. Therefore, when dealing with assembly line balancing oriented to product family evolution process, we should not only consider loader balancing but also treat evolution planning as one more important optimization objective.


## 5. Conclusions

(1) Based on discussion of product family evolution process and its influencing factors, the dynamic evolution process of PFAL (coevolution of product family and its assembly line) is analyzed and illustrated by the case of SWL product family; combined with characteristics of PFAL and its balancing research status, the evolution balancing problem of PFAL is focused on in this paper.(2) Product platform/key functional modules (such as the working device module or platform) change with a very small probability in product family evolution process and it is the key to raise efficiency of critical tasks (such as assembling accessory module instances) for improvement of the overall assembly efficiency; therefore, influences of the product family design techniques and critical chain technology on task assignment and assembly line balancing are discussed comprehensively and translated into constraint conditions in the evolution balancing model of PFAL.(3) The evolution balancing problem of PFAL is optimized using an intelligent evolutionary algorithm (dual-population GA) and, compared with the traditional load balancing model, results of the SWL case show that, in the constant evolution process of product family, adjustment costs of PFAL reduce significantly using the evolution balancing model with other indicators largely unchanged, which generates considerable economic benefits for enterprises.(4) The research on evolution balancing focuses on the issue of assembly line adjustment when the current assembly line has already balanced but was disturbed by external dynamic factors with more planning constraints and much more difficulty. Therefore, how to fully consider all factors such as tradeoff between load balancing indicators and adjustment costs, analysis of other adjustment costs besides labor cost, and so on and then to establish an objective model more precisely for the PFAL evolution balancing is an interesting perspective, in which further research is needed.



---

*Source: 213159-2015-10-25.xml*