A new discrete double-population firefly algorithm for assembly sequence planning

Abstract

Assembly sequence planning is a critical step of assembly planning in product digital manufacturing. It is a combinational optimization problem with strong constraints. Many studies devoted to propose intelligent algorithms for efficiently finding a good assembly sequence to reduce the manufacturing time and cost. Considering the unfavorable effects of penalty function in the traditional algorithms, a new discrete firefly algorithm is proposed based on a double-population search mechanism for the assembly sequence planning problem. The mechanism can guarantee the population diversity and enhance the local and global search capabilities by using the parallel evolution of feasible and infeasible solutions. All parts composed of the assembly are assigned as the firefly positions, and the corresponding movement direction and distance of each firefly are defined using vector operations. Three common objectives, including assembly stability, assembly polymerization and change number of assembly direction, are taken into account in the fitness function. The proposed approach is successfully applied in a real-world assembly sequence planning case. The sizes of feasible and infeasible populations are adequately discussed and compared, of which the optimal size combination is used for initializing the firefly algorithm. The application results validate the feasibility and effectiveness of the discrete double-population firefly algorithm for solving assembly sequence planning problem.

Keywords

Assembly sequence planning double-population search firefly algorithm assembly direction assembly stability

Introduction

Assembly planning is an important part of process planning in a digital manufacturing system, which generally consists of assembly modeling, assembly sequence planning (ASP) and assembly path planning.¹ ASP is the core step which largely determines the assembly cost and efficiency of a product.^2,3 The traditional ASP methods are experience-based methods or accurate calculation methods.⁴ Complex product assembly will bring out combinatorial explosion because exponential growth relationships generally exist between assembly sequence number and part number.^5,6 These methods cannot work out the optimum solution for solely relying on experiences or perhaps have too high computational complexities for generating the global optimum solution.⁷

Many recent studies tried to apply different intelligent algorithms for automated solving of the ASP problem. Cem⁸ presented a neural network which has three layers with recurrent structure for analyzing assembly sequences of assembly systems. Chen et al.⁹ proposed an artificial neural network algorithm to transform the assembly geometrical constraints into the assembly precedence relationships for overcoming the combination explosion problems. Ong et al.¹⁰ presented a simulated annealing algorithm for the ASP problem, which has strong local search ability. However, its global search ability and total operational efficient are not high for the ASP of complex products. Lazzerini and Marcelloni¹¹ and Guan et al.¹² used genetic algorithm (GA) for identifying the optimum assembly sequence. In order to solve the ASP problem more efficiently using GA, Lu et al.¹³ developed a multi-objective GA and established different fitness functions through a fuzzy weight distribution algorithm. Zhou et al.¹⁴ proposed a bacterial chemotaxis (BC)–based GA, of which BC can keep the diversity of populations during algorithm evolution process. Furthermore, Xing and Wang¹⁵ proposed a new social radiation algorithm (SRA) for assembly operation optimization of autobody based on a linear variation analysis model. The results show that the optimization performance of SRA is better than that of the standard GA.

Swarm intelligence algorithms have the characteristics of higher operation simplicity, more appropriate for parallel processing and higher robustness, which have also been applied to the ASP fields. Wang et al.¹⁶ applied the ant colony optimization algorithm to solve the assembly sequence. Particle swarm optimization (PSO) algorithm has powerful global search ability and convergence efficiently. Wang et al.¹⁷ tried to use PSO algorithm to solve the ASP of complex products under multiple stations and achieved good results. Lv and Lu¹⁸ presented an ASP approach with a discrete PSO algorithm. However, the optimization results of the discrete PSO are easily affected by the individual optimal fitness value. Zhang et al.¹⁹ proposed an immune PSO algorithm to solve ASP of a certain type of product, of which objective function is the combination of geometric feasibility and coherence. The manufacturing and assembly operations for producing a product may be distributed at different plants in a collaborative manufacturing system. Considering this issue, Tseng et al.²⁰ presented a multi-plant ASP model integrating ASP and plant assignment using a PSO algorithm. All the applications showed a good optimization performance of swarm intelligence algorithms in the ASP fields.

Firefly algorithm (FA) is a latest achievement in the swarm intelligent fields. FA is more efficient and has higher success rate than the GA and PSO algorithm on finding the global optimal solution as well as the local solution simultaneously and effectively through different experiments.²¹ Moreover, FA is simple and easy to carry out, which does not need adjustment of many parameters. The algorithm has been successfully applied in the combinatorial optimization problems, for example, optimization of product family design²² and ASP,²³ which demonstrate its great potentials in solving the nondeterministic polynomial-time (NP)-hard problems.

The ASP problem has strong constraints,²⁴ and the existing swarm intelligence algorithms generally use penalty functions to deal with these constraints during their evolution process.^13,17,23 The penalty function cannot fully consider the treatment of constraint boundary and choice difficulty of penalty factor, which have great negative impacts on searching the global optimum solution as follows:

The methods do not adequately consider the handling of constraint boundaries. However, many optimal solutions are located near the boundaries for the practical problems. The infeasible solutions near the optimal solution help identify the optimal solution for these kinds of problems.

The infeasible sequences are in the inferior position without effective evolution during the evolution process because of the existence of penalty function. That can result in the decrease in population diversity so that the algorithm is easy to converge to local optimization.

Penalty factor is difficult to choose for penalty function. The algorithm is easy to converge to local optimum solution if the factor is too large, while the result may not be an optimal solution of the original problem if the factor is too small.

Considering the above-mentioned issues, a new discrete double-population FA is proposed based on the quantization of assembly feasibility constraints, which can fully incorporate the total values of feasible and infeasible populations and effectively guarantee the diversity of population during the search process of optimal solution. A population saves the individuals with feasible solutions and FA is used to search the optimal feasible solution step by step. Another population saves the individuals with infeasible solutions, and the best infeasible solutions (the individuals with best fitness values and minimum constraint violation) are constantly added into the feasible solution swarm during the FA iteration process. The mechanism can ensure corresponding evolution for the infeasible solution and guarantee the diversity of population, where it is not easy to fall into the local optimization. On the other hand, the evolution of infeasible solution enhances the search ability of the algorithm and improves its efficiency. Furthermore, discrete coding mode is used in the FA for considering the characteristics of ASP. Fitness function in the algorithm is established using three general objectives: assembly stability, assembly polymerization and change number of assembly direction.

This article is organized as follows. The basic principles of FA are summarized in the next section. The third section develops a double-population search mechanism based on the discussion of ASP constraints. In the fourth section, a new discrete double-population FA is proposed for the ASP problem. In the fifth section, an ASP case study is provided to illustrate the proposed algorithm. Conclusions are then presented in the final section.

Basic principles

Firefly itself has some biological flashing mechanisms, which can perceive the flashing intensities and frequencies of other fireflies within a certain range for determining the existence and attractiveness of the partners or prey. Yang²⁵ proposed the FA according to the characteristics of firefly. The algorithm consists of two important issues: light intensity and attractiveness. Firefly brightness is affected or determined by the fitness function of its location. Brightness indicates the quality of firefly location and determines the movement direction of firefly. Attractiveness is proportional to brightness, which determines the movement distance of the firefly. All fireflies move toward these individuals with higher brightness and attractiveness and the optimal solution can be achieved ultimately.

Definition 1

In the standard algorithm, the light intensity of firefly has a monotonous exponential relationship with the distance of another individual

I = I_{0} \times e^{- γ r_{ij}}

(1)

where $I_{0}$ is the original light intensity of firefly; $γ$ is a fixed light absorption coefficient, which can make the light intensity to decrease with the increase in the spatial distance; and $r_{ij}$ is the spatial distance between firefly i and firefly j, which can be expressed using the Cartesian distance between any two individuals.

Definition 2

The attractiveness of a firefly is proportional to the light intensity seen by the adjacent fireflies. The attractiveness of any individual can be defined as follows

β = β_{0} \times e^{- γ r_{ij}^{2}}

(2)

where $β_{0}$ is the original attractiveness.

Definition 3

When the firefly is attracted by another more attractive (relative higher light intensity) firefly, the update formula of its location is given as follows

x_{i} = x_{i} + β (x_{j} - x_{i}) + α (rand - 0.5)

(3)

where $x_{i}$ and $x_{j}$ are the spatial locations of the ith firefly and jth firefly, respectively; $0 \leq α \leq 1$ , which is the step parameter; rand belongs to $[0, 1]$ , which is the randomization parameter of uniform distribution; and $α (rand - 0.5)$ is the disturbance during the update process.

The solution space of the standard FA belongs to the unconstrained and continuous real number domain, while the solution space of ASP belongs to the strong constrained and discrete integer domain. In order to make FA appropriate for solving the ASP problem, the following two issues need to be addressed: how to deal with the strong constraints and discreteness of ASP. A double-population search mechanism is used to deal with the strong constraint problem, where the constraints can be described by interference matrix and quantified by assembly direction set. ASP discreteness can be handled by coding firefly individual location and defining discrete operations of FA.

Double-population search mechanism

ASP constraints

ASP is a combinational optimization problem with strong constraints, of which the aim is to identify the feasible assembly sequence with the optimal fitness under satisfying a variety of constraints. For acquiring the optimal or suboptimal assembly sequence $S = {s_{1}, s_{2}, \dots, s_{n}}$ of the assembly consisted of n parts $A = {c_{1}, c_{2}, \dots, c_{n}}$ , the two critical issues are given as follows:

Geometric feasibility of assembly sequence. Geometric feasibility is a strong constraint of assembly sequence. Assembly sequence is possible to be optimized only when it satisfies the geometry constraints.

Assembly sequence optimization. The fitness function of assembly sequence optimization is constituted by a series of indexes. Only when the sequence has an optimal fitness value, the feasible sequence is deemed as the optimal one.

Assembly geometric constraint is the geometric interference on a part due to the existence of another part during the assembly process. The violation of the assembly geometric constraints among the parts will inevitably result in the assembly interference so that the assembly cannot be completed. For facilitating the feasibility identification of the assembly sequence and the derivation of feasible assembly direction during the assembly process, the usual interference matrix of assembly $I_{d_{k}} = [I_{ij}^{d_{k}}]_{n \times n}$ is used

I_{d_{k}} = [\begin{matrix} \begin{matrix} c_{1} & c_{2} & \dots & c_{n} \\ c_{1} & I_{11}^{d_{k}} & I_{12}^{d_{k}} & \dots & I_{1 n}^{d_{k}} \\ c_{2} & I_{21}^{d_{k}} & I_{22}^{d_{k}} & \dots & I_{2 n}^{d_{k}} \\ ⋮ & ⋮ & ⋮ & I_{ij}^{d_{k}} & ⋮ \\ c_{n} & I_{n 1}^{d_{k}} & I_{n 2}^{d_{k}} & \dots & I_{nn}^{d_{k}} \end{matrix}] \end{matrix}

(4)

where n is the part number of an assembly; $d_{k} = + X, + Y, + Z$ expresses the positive directions of X, Y and Z in Cartesian coordinate system; and $I_{ij}^{d_{k}}$ expresses the interference on part j when part i assembles along the direction $d_{k}$ ; if there is interference, $I_{ij}^{d_{k}} = 1$ ; otherwise, $I_{ij}^{d_{k}} = 0$ . Obviously, the interference situation on part j when part i assembles along the forward direction of the axis is equal to that of part i when part j assembles along the negative direction of the axis. For an assembly, interference matrix of three forward directions just needs to be established and the matrix of three negative directions can be obtained using matrix transpose.

Assembly directions are generally divided into six directions in the Cartesian coordinate system

d_{k} = {d_{1}, d_{2}, d_{3}, d_{4}, d_{5}, d_{6}} = {+ X, - X, + Y, - Y, + Z, - Z}

(5)

$V_{k} (c_{i}) (k = 1, 2, \dots, 6)$ is defined as the sum of interference values between part $c_{i}$ and other assembled parts when the part assembles along the direction $d_{k}$ . Set ${c_{1}, c_{2}, \dots, c_{i - 1}}$ as the assembled part sequence before assembling part $c_{i}$ . Feasible assembly direction of part $c_{i}$ can be formulated as follows

V_{k} (c_{i}) = \sum_{j = 1}^{i - 1} I_{c_{j} c_{i}}^{d_{k}}

(6)

Based on the definition, the part $c_{i}$ can be assembled along the direction $d_{k}$ if $V_{k} (c_{i}) = 0$ . ${c_{1}, c_{2}, \dots, c_{i - 1}, c_{i}}$ is the feasible assembly sequence if a value in $V_{k} (c_{i})$ $(k = 1, 2, \dots, 6)$ is 0, where part $c_{i}$ can be assembled along the feasible direction in $D_{f} (c_{i}) = {d_{k} | V_{k} (c_{i}) = 0}$ . Otherwise, the sequence is infeasible.

Double-population search mechanism

The study proposes a new double-population cooperative search mechanism for solving the ASP problem. A population saves the individuals with feasible solutions and FA is used to search the optimal feasible solution step by step. Another population saves the individuals with infeasible solutions, and the best infeasible solutions (the individuals with best fitness values and minimum constraint violation) are constantly added into the feasible solution swarm during the FA iteration process. The mechanism can ensure corresponding evolution for the infeasible solution and guarantee the diversity of population, where it is not easy to fall into the local optimization. On the other hand, the evolution of infeasible solution enhances the search ability of the algorithm and improves its efficiency. The two populations are defined as follows.

Definition 4

Set $U_{fs} = {1, 2, \dots, n_{1}}$ as the population of feasible solutions if and only if individuals $1, 2, \dots, n_{1}$ are feasible solutions.

Definition 5

Set $U_{ifs} = {1, 2, \dots, n_{2}}$ as the population of infeasible solutions if and only if individuals $1, 2, \dots, n_{2}$ are infeasible solutions.

The above two populations are saved assembly sequences which can be expressed as follows.

Definition 6

Set $x_{i} = (x_{i, 1}, x_{i, 2}, \dots, x_{i, j}, \dots, x_{i, n})$ as the possible locations of any individual i, where $x_{i, j} \in {1, 2, \dots, n}$ ; $x_{i, j}$ expresses the jth element of individual i and n is the total dimension of individual i. If the individual i does not emerge any interference according to equation (4), the individual is feasible solution, namely, feasible sequence. Otherwise, it is infeasible solution.

In the iteration process in the FA algorithm, some appropriate individuals (i.e. assembly sequences) in the infeasible population should be chosen into the feasible population. The process is dependent on choice function which is defined as follows.

Definition 7

The appropriate individuals in infeasible population $U_{ifs}$ are directly chosen into the feasible population $U_{fs}$ using choice function. The choice function is expressed by the formula

S (x_{i}) = λ f (x_{i}) + μ g (x_{i})

(7)

where $f (x_{i})$ is the fitness function of FA and $g (x_{i})$ is the constraint violation which can be expressed using interference number. Set $g (x_{i}) = \sum_{j = 1}^{n} V_{k} (x_{i, j})$ , and the interference number along the k direction can be calculated for the sequence based on equation (4). $λ$ and $μ$ are the weight coefficients. Individuals in the infeasible population have smaller choice; function values show that their fitness is better and their constraint violations are smaller. And the individuals have greater probabilities to be selected into the feasible population.

The simple operation flow of the double-population search mechanism is given as follows:

Step 1. Define feasible population $U_{fs}$ and infeasible population $U_{ifs}$ .

Step 2. Implement an iteration operation for the individuals in $U_{fs}$ , and the new location feasibilities of individuals are judged using Definition 6. The infeasible solutions (assume their number as k) among new individuals are assigned into $U_{ifs}$ and the feasible solutions remain in $U_{fs}$ .

Step 3. Calculate choice function $S (x_{i})$ of all individuals in $U_{ifs}$ using Definition 7, and the k better infeasible solutions are directly assigned into $U_{fs}$ .

Step 4. Judge whether the algorithm satisfies the stop conditions. If it is not satisfied, the algorithm goes to Step 2; otherwise, stop the algorithm and output the current optimal solution.

A new double-population FA

Besides solving the strong constraints in solution space, problem mapping mechanism and solution-generating mechanism must also be determined when using FA to solve the ASP problem. The operations of attractiveness and position in the standard FA are all real value calculation, which is suitable for solving the continuous problems. However, ASP belongs to the discrete problem. Related operations of the firefly individual location, attractiveness and location update must be redefined.

Discrete FA

FA is similar to PSO on the optimization principle. Location coding with related operations can be similarly defined using the PSO coding mode in the discrete sequencing space.^23,24,26

1. The position of firefly i. Set ordered arrangement of all parts composed of the assembly as the firefly position vector. Position vector of the ith firefly individual can be expressed as follows

X_{i} = (x_{i, 1}, x_{i, 2}, \dots, x_{i, j}, \dots, x_{i, n})

(8)

where $x_{i, j} \in {1, 2, \dots, n}$ is the order number of part and n is the part number of the assembly. If $j \neq k$ , $x_{i, j} \neq x_{i, k}$ .

2. Subtraction of the positions. This is $x_{j} - x_{i}$ in equation (3), of which the aim is to judge the movement direction of firefly i attracted by firefly j. A direction vector $D_{i} = (d_{i, 1}, d_{i, 2}, \dots, d_{i, k}, \dots, d_{i, n})$ is defined for firefly i. Set $X_{j} = (x_{j, 1}, x_{j, 2}, \dots, x_{j, k}, \dots, x_{j, n})$ , $X_{i} = (x_{i, 1}, x_{i, 2}, \dots, x_{i, k}, \dots, x_{i, n})$ and then $D_{i} = X_{j} Θ X_{i}$ , where $d_{i, k}$ is determined as follows: if $x_{i, k} = x_{j, k}$ , $d_{i, k} = 0$ ; otherwise, $d_{i, k} = x_{j, k}$ .

3. Multiplication of the directions. This is $β \times (x_{j} - x_{i})$ in equation (3), where $β$ is the step length. Both the multiplication and the disturbance $α \times (rand - 0.5)$ in equation (3) control the movement distance of firefly i from its original location to firefly j along the direction $D_{i}$ . Movement direction vector and distance of the firefly i are synthesized into a velocity vector $V_{i}$ as follows

V_{i} = β \otimes D_{i} \oplus α \times (r a n d - 0.5) = {\begin{matrix} D_{i} & β \geq α (r a n d - 0.5) \\ 0 & β < α (r a n d - 0.5) \end{matrix}

(9)

4. Addition of the location and velocity. This is the location update of firefly i in equation (3). The new location firefly i in the (t + 1)th iteration is identified by multiplying its location and the velocity vector (including the direction and movement distance) in the tth iteration

X_{i}^{t + 1} = X_{i}^{t} \oplus V_{i}^{t}

(10)

During the update process of firefly positions, if the kth element $v_{i, k}^{t} = 0$ in the velocity vector $V_{i}^{t}$ , the kth element $x_{i, k}^{t}$ remains unchanged in the position vector $X_{i}^{t}$ ; otherwise, exchange the part numbers of $x_{i, k}^{t}$ and $v_{i, k}^{t}$ in $X_{i}^{t}$ with each other.

Fitness function

Optimization objective of ASP is usually to save cost and improve the assembly quality. Three common objectives in the ASP field are used to establish the fitness function, which include assembly stability, assembly polymerization and change number of assembly direction:^1,14,23

1. Assembly stability. Assembly stability is that comprehensive ability of the assembled parts or sub assembly to maintain their internal assembly relationships under the action of gravity. Connection matrix $C = {(c_{i j})}_{n \times n}$ and support matrix $C = (c_{ij})_{n \times n}$ are defined in order to quantifying assembly stability of a feasible sequence, where $c_{ij}$ and $s_{ij}$ are the mapping values of connection relationship and support relationship for adjacent parts, respectively. $c_{ij} = 2$ , $c_{ij} = 1$ and $c_{ij} = 0$ represent stable connection, contact connection and non-connection, respectively. If there is support relationship, $s_{ij} = 1$ ; otherwise, $s_{ij} = 0$ .

A principle can be given to judge whether the assembly relationship between part i and part j is stable. If i and j is stable connection ( $c_{ij} = 2$ ), the assembly operation is deemed as stable. If i and j is contact connection or non-connection ( $c_{ij} = 1$ or $c_{ij} = 0$ ), another assessment should be implemented to judge whether there is a support relationship. If it is $s_{ij} = 1$ , the assembly operation is still deemed stable; otherwise, the assembly operation is unstable. Set $n_{c}$ as the number of unstable operations in assembly sequence, where the smaller the $n_{c}$ , the better the assembly sequence.

2. Assembly polymerization. Assembly polymerization is the degree of integrated completion for assembly operations. Higher polymerization means higher assembly efficiency. The polymerization can be usually quantified using the change number of assembly tools. The change number can be identified using cumulative calculation by judging whether the assembly tool is the same for the two adjacent parts. $n_{t}$ represents the polymerization, where the smaller the $n_{t}$ , the higher the polymerization and the better assembly sequence.

3. Change number of assembly direction. The decrease in change number can reduce the clamping times of the assembly or the number of reversing operations. This can save the assembly cost and improve the assembly efficiency. The change number can be quantified by using the above-mentioned feasible assembly direction set $D_{f} (c_{i})$ .

Assume $S = {c_{1}, c_{2}, \dots, c_{j}, c_{j + 1}, \dots, c_{n}}$ is an assembly sequence and calculate the feasible assembly direction set. If $⋂_{i = 1}^{j} D_{f} (c_{i}) \neq \emptyset$ , the assembly direction does not need to be changed during the assembly process of parts $c_{1}, c_{2}, \dots, c_{j}$ . If $⋂_{i = 1}^{j} D_{f} (c_{i}) \neq \emptyset$ and $⋂_{i = 1}^{j + 1} D_{f} (c_{i}) = \emptyset$ , the assembling direction needs to be changed one time when assembling the part $c_{j + 1}$ . Analogously, change number $n_{d}$ of any assembly can be calculated based on the method, where $0 \leq n_{d} < n - 1$ . The smaller the $n_{d}$ , the better the assembly sequence.

The fitness function of the double-population FA can be identified by weighted summing of the three indexes

f (s) = w_{1} n_{c} + w_{2} n_{t} + w_{3} n_{d}

(11)

where $w_{1}$ , $w_{2}$ and $w_{3}$ are the weight coefficients of the three indexes, respectively.

The discrete double-population FA process

The double-population FA process for ASP is shown in Figure 1. The specific steps are given as follows:

Step 1. Set the initial parameters of the double-population FA

The iteration variable $t = 0$

The maximum iteration number T

The initial population size N ( $N = n_{1} + n_{2}$ )

The FA parameters: light absorption coefficient $γ$ , the biggest attraction $β_{0}$ and the step factor $α$

Index weights of fitness function $w_{1}$ , $w_{2}$ and $w_{3}$

Step 2. Initialize the feasible population $U_{fs}$ and the infeasible population $U_{ifs}$

The feasibility of each individual (i.e. assembly sequence) can be judged using Definition 6, which is inserted into the corresponding populations $U_{fs}$ and $U_{ifs}$ , respectively. The individual number in the two populations should be ensured $n_{1}$ and $n_{2}$ , respectively.

The locations of $n_{1}$ individuals can be initialized through equation (8). Assign the smallest fitness individual as b and its fitness as F.

Step 3. Search in the feasible population $U_{fs}$ using the FA

A firefly moves to the firefly with smallest fitness within its vision scope. Its position is updated using equation (10) until each firefly accomplishes a movement, namely, an iteration operation is completed.

New location fitness values of these individuals can be calculated using equation (11). Record the individual i with the optimal fitness and its fitness value $f_{min}$ during the iteration process and set $b = i$ , $F = f_{min}$ .

The feasibility of new location is judged for each individual. If the new individuals are all feasible solutions, go to Step 5. If there are k infeasible solutions, these solutions are added into the infeasible population $U_{ifs}$ and go to Step 4.

Step 4. Calculate the choice function for the infeasible population $U_{ifs}$

The choice function can be calculated using equation (7) for $n_{2} + k$ fireflies in $U_{ifs}$ . The k individuals with minimum fitness are added into the feasible population $U_{fs}$ . And go to Step 3 for continuing to implement the FA.

Other infeasible solutions remain until calculating their choice function for the next iteration.

Step 5. The FA is circularly implemented from Step 3 to Step 4 until the stop conditions. Output the optimal firefly individual b with its fitness F, as well as the optimal fitness and average fitness of each generation.

Step 6. Decode the optimal location of the outputted firefly and get the optimal assembly sequence.

Figure 1.

FA process using double population.

Case study

The proposed double-population FA is applied in a real-world ASP case of a manufacturing enterprise. The assembly explosion diagram is shown in Figure 2, which has 16 important parts after simplifying related standard parts. In particular, the accessories (e.g. fasteners) can be ignored in the planning process which does not have direct impacts on assembly sequence.

Figure 2.

Assembly exploded diagram.

The 16 parts assemble along the coordinate axes $\pm X, \pm Y, \pm Z$ . The optimization objectives are assembly stability, assembly polymerization and change number of assembly direction. Set the weights in fitness function as $w_{1} = 0.45$ , $w_{2} = 0.25$ and $w_{3} = 0.30$ , respectively. These weights are identified according to the expert experiences. Generally, different applications may have different weights for the fitness function according to assembly engineering condition and environment. Interference matrices are I_+X, I_+Y and I_+Z, for all parts along the coordinate axes +X, +Y and +Z in the assembly sequence. Three interference matrices in the negative direction can be derived from the three positive matrices. The assembly tools of the 16 parts are given in Table 1, which includes three tool types. Different values for the FA parameters have direct impacts on the final FA performance. Through experience analysis and comparison, FA parameters are defined as $γ = 0.004$ , $β_{0} = 1$ and $α = 1.5$ .

Table 1.

Assembly tools of the 16 parts.

No.	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
Tool types	T1	T1	T1	T1	T2	T2	T2	T2	T1	T1	T3	T1	T2	T2	T2	T2

Effects of population size on the FA

The FA uses cooperative search strategy of double populations including feasible population $U_{fs}$ and infeasible population $U_{ifs}$ , where their population sizes are $n_{1}$ and $n_{2}$ , respectively. The two populations store some feasible and infeasible assembly sequences (i.e. individuals) in the iteration process. The optimal population sizes in the case can be identified through the impact testing of different population sizes on the algorithm.

1. Identify $n_{1}$ for the feasible population $U_{fs}$

$n_{1}$ is set as 20, 50, 100, 150 and 200, respectively, in order to investigate its influences on the FA under fixing other parameters and weight coefficients of fitness function. The FA runs 20 times for the different initial populations to record the average fitness values. The simulation results are given in Table 2 and Figure 3, where $n_{r}$ is the algorithm running number under different population sizes, $n_{s}$ is the suboptimal assembly sequence after running 20 times for the algorithm (suboptimal sequence refers to the sequences of which fitness is less than 4) and t is a single execution time of the algorithm.

Table 2.

Simulation results under different population sizes.

Population size $n_{1}$	20	50	100	150	200
Running time $n_{r}$	20	20	20	20	20
Suboptimal sequence $n_{s}$	1	3	10	14	16
Running time $t / s$	0.6	3.1	6.9	11.2	18.2

Figure 3.

Average fitness of different population sizes under 20 operations.

Seen from Table 2, the number of suboptimal sequences for the 20 running is in an upward trend, while a single execution time also increases with the increasing size of initial population. Seen from Figure 3, the identified optimal sequence is the local optimization when the population size is 20 or 50, while the fitness of optimal assembly sequence will be reduced accordingly when increasing the population size. The suboptimal assembly sequences increase, but the fitness of the optimal sequence is not changed when the population size increases from 100 to 200.

2. Identify $n_{2}$ for the feasible population $U_{ifs}$

The effects of infeasible population $U_{ifs}$ are to increase population diversity and prevent the algorithm to run into a local optimization through picking the “excellent” infeasible solutions into the feasible population. The following two sets of parameters are used to test the effects of $n_{2}$ on the algorithm: set $n_{2}$ as 0, 20 and 50 when $n_{1}$ is 50 and 100, respectively. The simulation results are given in Table 3 and Figures 4 and 5.

Table 3.

Simulation results with different populations.

$n_{1}$	50			100
$n_{2}$	0	10	50	0	10	50
Running time $n_{r}$	20	20	20	20	20	20
Suboptimal sequence $n_{s}$	3	12	13	10	18	18
Running time $t / s$	3.1	12.4	24.5	6.9	31.2	48.6

Figure 4.

Simulation results under feasible population size n₁ = 50.

Figure 5.

Simulation results under feasible population size n₁ = 100.

Suboptimal sequences increase significantly and the fitness of algorithm convergence decreases significantly when adding $n_{2}$ by comparing the simulation results in Table 3 and Figure 4. The reason is that the FA is not easy to fall into local optimization with the effects of infeasible solutions. It can be found that the effects on algorithm convergence are not obvious, while running time increases significantly when $n_{2}$ changes from 10 to 50. Choice functions of all individuals in $n_{2}$ must be calculated and judged during each iteration process, which results in the increase in running time.

It is evident that the average fitness of each generation has a local wave phenomenon when adding $n_{2}$ from Figures 4 and 5. For example, the fitness function value is 7 in the 42nd iteration, while the fitness function value is 11 in the 43rd iteration when $n_{2} = 50$ as shown in Figure 4. The added infeasible solutions that may have higher fitness values cause local augment of average fitness during each iteration operation. This reflects the diversity of population. However, average fitness is always in the overall declining trend, and eventually, the algorithm converges to the optimal solution.

FA application

Set the feasible population size $n_{1} = 100$ , the infeasible population size $n_{2} = 10$ and fix the other parameters based on the above experimental results. The double-population FA is successfully applied in the ASP case. The global optimal fitness is $f = 1.65$ , where assembly stability $n_{c} = 0$ , assembly polymerization $n_{t} = 3$ and changing time of assembly direction $n_{d} = 3$ . The optimization results and the optimal assembly sequence are finally given in Figure 6 and Table 4.

Figure 6.

Running results of the double-population FA.

Table 4.

The optimal assembly sequence.

Assembly sequence S	11	12	10	9	16	14	13	15	8	6	7	5	3	4	2	1
Assembly tool T	T3	T1	T1	T1	T2	T2	T2	T2	T2	T2	T2	T2	T1	T1	T1	T1
Assembly direction $d_{k}$	+X	+X	+X	+X	−Y	−Y	−Y	+Z	+Z	+Z	+Z	+X	+X	+X	+X	+X

The assembly sequence S = {11-12-10-9-16-14-13-15-8-6-7-5-3-4-2-1} is the optimal sequence using the double-population FA. It is found that the assembly sequence S satisfies geometric feasibility, where its assembly time is shortest and its assembly efficiency is highest through repeated trials in the workshop. Finally, the sequence is designated as the practical assembly sequence of these parts in process department for guiding the workshop manufacturing.

Conclusion

In the field of process planning, ASP is a combinational optimization problem, which comprises of various constraints. A new discrete double-population FA is developed to implement ASP, which can overcome the disadvantages of the penalty function present in the traditional swarm intelligent algorithms. An application case is used to show that the proposed FA converges effectively to reach its optimum solution.

The main functions are outlined below:

For standardized description of ASP, assembly constraints are described and quantified using an assembly interference matrix and an assembly direction set.

A double-population search mechanism (including feasible and infeasible populations) is proposed to deal with the strong constraints of ASP. This is crucial for avoiding the establishment of the penalty function.

For solving a problem pertaining to ASP, the discrete double-population FA is proposed. This is based on the redefinition of the coding mode and the operations of the standard FA.

The proposed FA is applied in a real-world ASP setting for the validation of its feasibility and performance. The optimal size combination of feasible and infeasible populations for initializing the FA is identified by comparing the different sizes of the two populations.

Further work would consider the improvement of the evolutionary strategy for the two populations to make the FA more efficient and stable to solve the ASP problem. Other evaluation indices will be added into the fitness function and the effects of different optimization methods will be considered in the ASP. Moreover, ASP of multiple assemblies of one product in different locations and adjacent constraints with other assemblies can be further explored.

Footnotes

Acknowledgements

The authors express their sincere appreciation to the anonymous referees for their helpful comments to improve the quality of the paper.

Declaration of Conflicting Interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: The project was supported by National Natural Science Foundation of China (Nos 51205242, 51205247, 51405281) and Shanghai Science and Technology Innovation Action Plan (No. 1311110 2900).

References

Rosen

Wang

. Cloud-based design and manufacturing: a new paradigm in digital manufacturing and design innovation. Comput Aided Design 2014; 59: 1–14.

Rashid

MFF

Hutabarat

Tiwari

A review on assembly sequence planning and assembly line balancing optimization using soft computing approaches. Int J Adv Manuf Tech 2012; 59: 335–349.

Zhao

Wang

CX.

Knowledge-based approach to assembly sequence planning for wind-driven generator. Math Probl Eng 2013; 2013: 908316 (7 pp.).

Somayé

Ellips

Review and taxonomies of assembly and disassembly path planning problems and approaches. Comput Aided Design 2015; 67–68: 58–86.

Zhao

Hong

Zhao

. Research on assembly sequence planning method for large-scale assembly based on an integrated assembly model. Proc IMechE, Part B: J Engineering Manufacture 2012; 226: 733–744.

Moultrie

Maier

AM.

A simplified approach to design for assembly. J Eng Design 2014; 25(1–3): 44–63.

Zhen

Huang

. Assembly sequence planning of quayside container crane based on improved immune algorithm. J Appl Sci 2013; 13(22): 4922–4928.

Cem

Design of an artificial neural network for assembly sequence planning system. Int J Ind Eng: Theory 2008; 15(1): 92–103.

Chen

Tai

Deng

. A three-stage integrated approach for assembly sequence planning using neural networks. Expert Syst Appl 2008; 34(3): 1777–1786.

10.

Ong

Ding

Nee

AYC

. Hybrid GA and SA dynamic set-up planning optimization. Int J Prod Res 2002; 40(18): 4697–4719.

11.

Lazzerini

Marcelloni

A genetic algorithm for generating optimal assembly plans. Artif Intell Eng 2002; 14: 319–329.

12.

Guan

Liu

Zhong

YF.

A concurrent hierarchical evolution approach to assembly process planning. Int J Prod Res 2002; 40(14): 3357–3374.

13.

Wong

Fuh

JYH

. An enhanced assembly planning approach using a multi-objective genetic algorithm. Proc IMechE, Part B: J Engineering Manufacture 2006; 220(2): 255–272.

14.

Zhou

Zheng

Yan

. A novel hybrid algorithm for assembly sequence planning combining bacterial chemotaxis with genetic algorithm. Int J Adv Manuf Tech 2011; 52: 715–724.

15.

Xing

Wang

YS.

Assembly operation optimization based on social radiation algorithm for autobody. Adv Mech Eng 2014; 2014: 854637 (7 pp.).

16.

Wang

Liu

Zhong

YF.

A novel ant colony algorithm for assembly sequence planning. Int J Adv Manuf Tech 2005; 25: 1137–1143.

17.

Wang

Sun

Multi station assembly sequence planning based on particle swarm optimization algorithm. J Mech Eng 2012; 48(9): 155–162.

18.

An assembly sequence planning approach with a discrete particle swarm optimization algorithm. Int J Adv Manuf Tech 2010; 50(5–8): 761–770.

19.

Zhang

Liu

LY.

Research on a kind of assembly sequence planning based on immune algorithm and particle swarm optimization algorithm. Int J Adv Manuf Tech 2014; 71: 795–808.

20.

Tseng

Chen

Huang

FY.

A particle swarm optimization algorithm for multi-plant assembly sequence planning with integrated assembly sequence planning and plant assignment. Int J Prod Res 2010; 48(10): 2765–2791.

21.

Yang

XS.

Firefly algorithms for multimodal optimization. In: Watanabe

Zeugmann

(eds) Stochastic algorithms: foundations and applications. Berlin; Heidelberg: Springer, 2009, pp.169–178.

22.

Yuan

JJ.

Optimal design for scale-based product family based on multi-objective firefly algorithm. Comput Integr Manuf 2012; 18(8): 1801–1809.

23.

Zeng

Zhang

. Research on assembly sequence planning based on firefly algorithm. J Mech Eng 2013; 49(11): 177–184.

24.

Gao

Zhang

. Discrete electromagnetism-like mechanism algorithm for assembly sequences planning. Int J Prod Res 2014; 52(12): 3485–3503.

25.

Yang

XS.

Nature-inspired metaheuristic algorithms. Frome: Luniver Press, 2011.

26.

. A hybrid assembly sequence planning approach based on discrete particle swarm optimization and evolutionary direction operation. Int J Adv Manuf Tech 2013; 68: 617–630.