# A Novel Parallel Assembly Sequence Planning Method for Complex Products Based on PSOBC

Authors: Yanfang Yang; Miao Yang; Liang Shu; Shasha Li; Zhiping Liu
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

Parallel assembly sequence planning (PASP) greatly impacts on efficiency of assembly process. In traditional methods, large scale of matrix calculation still limits efficiency of PASP for complex products. A novel PASP method is proposed to address this issue. To avoid matrix calculation, the synchronized assembly Petri net (SAPN) is firstly established to describe the precedence relationships. Associated with the SAPN model, the PASP process can be implemented via particle swarm optimization based on bacterial chemotaxis (PSOBC). Characterized by an attraction-repulsion phase, PSOBC not only prevents premature convergence to a high degree, but also keeps a more rapid convergence rate than standard particle swarm optimization (PSO) algorithm. Finally, feasibility and effectiveness of the proposed method are verified via a case study. With different assembly parallelism degrees, optimization results show that assembly efficiency of the solution calculated by PSOBC method is 9.0%, 4.2%, and 3.1% better than the standard PSO process.


---

## Body

## 1. Introduction

ASP is one of the important parts of industrial manufacturing, which is able to provide fast and high efficiency guidelines for equipment assembly. High efficiency of ASP directly determines enterprise profit. However, ASP is usually difficult due to the large number of equipment components (assembly operations) and complicated priorities/constraints relations among components.Usually ASP can be treated as an NP-hard problem [1], which is generally solved to maximize the multiple benefits during the assembly process [2]. There are several challenges remaining to construct efficient and comprehensive ASP, one of which is the modeling problem. To optimize ASP, the precedence relationships among every individual component need to be investigated. A number of methods have been developed to meet various requirements in the ASP optimization. AND/OR graph model was firstly developed by De Mello et al. [3], and it has been widely employed in assembly sequence generation researches. Precedence matrix was built and embodied into Petri net to generate the reachability graph by Yang et al. [4]. Similar assembly direction matrix, interference matrix, and sequence-relation matrix were introduced to generate optimal assembly sequence for eccentric milling machine in [5]. Such matrix method contributes to generation and acquisition of production information, and it is usually straightforward and easy to be implemented. However, due to the large number of equipment components and the complicated constrains, the size of precedence matrix is generally very large. Computational burden will limit the optimization process. To increase ASP efficiency, some other advanced methods were introduced and developed, e.g., weighted precedence graph [6], assembly tree [7], layout-based hierarchical graph [8], and part concatenation method [9–11]. In these methods, the weighted assembly graph reduces the complexity of ASP through considering qualitative and quantitative constraints. By using the assembly tree method, generation of feasible and stable sequences can be implemented through the recursive construction and stability criteria. Part concatenation method is robust and able to address ASP problem by considering all necessary assembly predicates. However, such models are still matrix based. Not only is enormous human calculation required to investigate complex products, but also human error would occur with a large probability. To address this problem, a SAPN model is developed to describe the operations, priorities, and constraints in assembly process. Each transition is associated with the predecessors by using assembly synchronizers, which illustrates the precedence relationships. The transition status is updated in each assembly operation and the assembility can be identified by the status checking.ASP optimization could be implemented when the assembly model is developed. Generally, ASP can be categorized into two types, the SASP and the PASP. The assembly operations of SASP are constructed in series and are easy to be implemented. Since all the operations need to follow a linear sequence, the efficiency is limited. Assembly operations of PASP can be performed in parallel and the efficiency can be increased. However, it is still challenging to assemble complex equipment with PASP. To increase efficiency and correctness, the PASP needs to be optimally designed. Moreover, optimization of PASP needs to be subjected to strict predetermined constraints.Heuristic algorithm is an effective way to solve optimization problem with constraints. Typical methods include genetic algorithm [12–14], PSO [15, 16], ant colony optimization algorithm [17, 18], and other evolutionary algorithms [19–21]. GA is a nonlinear estimation method that generates solutions to optimization problems using techniques inspired by natural evolution [22]. To tackle ASP of complex products, a chaotic PSO approach to generate the optimal or near-optimal assembly sequences of products was developed in [23]. Generally, heuristic searching needs to be implemented with numerical iterations. The coding rules and heuristic rules under predetermined constraints are important to construct the efficient searching. Like what has been discussed, most of the ASP models and the coding rules are matrix based. The searching/iteration performance is limited due to the matrix calculations. We have developed the SAPN model to describe the operations, priorities, and constraints in the assembly process. Coding rules of PSOBC such as position, velocity, and diversity function are represented with index vectors instead of matrix. The consequent efficiency can be increased.As for the heuristic rules design, the prematurity phenomenon is the major problem that needs to be addressed. The searching result could be attracted to the local optima if the heuristic rules are designed improperly. Inspired by the phenomenon of chemotaxis in bacteria colonies, PSOBC was proposed to improve the performance of standard PSO [24]. Characterized by an attraction-repulsion phase, PSOBC not only prevents premature convergence to a high degree, but also keeps a more rapid convergence rate than standard PSO. This algorithm has been successfully used in areas like CO2 emission problem [25] and hydropower stations operations [26]. The global and local search performance could be well balanced when the particle swarm diversity is properly controlled. Here we use a similar PSOBC framework to solve the PASP problem based on the proposed SAPN model. The diversity function is built up to avoid population prematurity. Feasibility and effectiveness of the proposed method are also verified via a case study. Optimization results have been compared with standard PSO method under different DPAs.


## 2. Establishment and Analysis of SAPN

### 2.1. Basic Petri Net

Definition 1.
(Petri net). LetN = (P, T, F) be the basic Petri net which should satisfy the following three conditions:(1)
P ∪ T ≠ Ø ∧ P ∩ T = Ø,(2)
F ⊆ P × T ∪ T × P,(3)
dom (F) ∪ cod (F) = P ∪ T.
Here “×” is the Cartesian product, domF=x∃y:x,y∈F, and codF=y∃x:x,y∈F. Condition (3) is defined to ensure that there is no isolated place, transition, or arc in the Petri net.


### 2.2. Symbols in SAPN

Definition 2.
(synchronizer). Letp=T1,T2,a1,a2 be a synchronizer, where ∀ti1∈T1, ti2∈T2:p=ti1•=ti2•, wti1,p=a2, wp,ti2=a1, T1=t11,t12,…,t1m1, T2=t21,t22,...,t2m2, 1≤a1≤m1=T1, and 1≤a2≤m2=T2.
The scheme of the defined synchronizer is shown in Figure1. The SAPN consists of a set of synchronizers corresponding to different assembly status. The synchronizers are used to illustrate the parallel and selective relations of each assembly operation, including the corresponding precedence relationships.Figure 1
Scheme of synchronizer.Definition 3.
(SAPN). Let SAPN =(P, T, F, W, M, PT, TM) be the synchronized assembly Petri net consisting of assembly synchronizers. Places, transitions, arcs, and other tuples are integrated in the net. Detailed explanation of these tuples is given as follows:P = {pj}, (j = 1, 2, …, m) represents the assembly status, and m is the amount of the places.T = {ti}, (i = 1, 2, …, n) represents the assembly operations, and n is the amount of the transitions.F = {fk}, (k = 1, 2, …, l) represents the directed arcs between transitions and places, and l is the amount of the arcs.W = {wk}: F ⟶ {1, 2, 3, …} represents the weight functions associated with arcs. The weight functions determine the amount of the required tasks for a place to transform into another one. The weight functions should be assigned based on number of the arcs which share the same input/output place in the corresponding synchronizer. For example, there are m1 arcs between T1 and p sharing the same output place p in Figure 1, so the weight functions of these arcs should be both assigned as m1. Also the weight functions of p’s output arcs should be both assigned as m2 according to similar recursion.M = {mi}: T ⟶ {0, 1, 2} represents the markings associated with transitions. Here M is defined to represent the transition status. In the assembly process, the marking M is a piecewise constant vector and the values are dependent on the transition status based on the following rules:(1)mi=0,tiis fired,1,tiis fireable,2,tiis unfireable, while it has’t been fired.PT=pti2:T⟶ti1,i1,i2=1,2,…,n represents the precedence relationships among equipment components. The element pti2 in PT is defined to collect the preceding transitions of ti1. In others words, if ∃p=T1,T2,a1,a2:ti2∈T1∧ti1∈T2, then the transitions in T1 are the predecessors of the transitions in T2.TM = {tmi}:T represents operation times of the transitions.


### 2.3. Construction of SAPN

This subsection introduces construction approach of SAPN through the following steps.Step 1: Generate transitions for each necessary assembly operation.Step 2: Assigntms, ms, and pts to each corresponding transition.Step 3: Generate the starting place, the ending place, and the places between each transition and its predecessors.Step 4: Integrate the duplicated input places of each transition.Step 5: Generate the directed arcs from predecessors to the corresponding places and from the places to the corresponding successors.Step 6: Assign the weight function to each arc.SAPN model can be constructed through the detailed steps mentioned above. Step 1 and Step 2 generate the fundamental transitions. Generation of the corresponding places is processed in Step 3 and Step 4. Since SAPN is oriented to the complex products, the elements in SAPN are unavoidably large. Therefore, the integration process in Step 4 somewhat reduces the scale of SAPN model. Step 5 and Step 6 generate and assign the arcs, which link the elements in each synchronizer.


### 2.4. Analysis of Assembility

A transition which is fireable must satisfy the condition that its preceding transitions have all been fired in the synchronizer. Assembility of each component can be determined from the precedence relationships and the status, i.e.,PT and M. The necessary and sufficient condition of ti1 being fireable is given as below:(2)mi1=1.Equation (2) can also be rewritten as(3)∀ti2∈pti1:∑mi2=0∧mi1≠0.It is seen from (3) that ti1 is fireable when its preceding transitions have all been fired; namely, mi2=0. Analysis of assembility is necessary in the sequence optimization process to avoid violation of precedence relationships.


## 2.1. Basic Petri Net

Definition 1.
(Petri net). LetN = (P, T, F) be the basic Petri net which should satisfy the following three conditions:(1)
P ∪ T ≠ Ø ∧ P ∩ T = Ø,(2)
F ⊆ P × T ∪ T × P,(3)
dom (F) ∪ cod (F) = P ∪ T.
Here “×” is the Cartesian product, domF=x∃y:x,y∈F, and codF=y∃x:x,y∈F. Condition (3) is defined to ensure that there is no isolated place, transition, or arc in the Petri net.


## 2.2. Symbols in SAPN

Definition 2.
(synchronizer). Letp=T1,T2,a1,a2 be a synchronizer, where ∀ti1∈T1, ti2∈T2:p=ti1•=ti2•, wti1,p=a2, wp,ti2=a1, T1=t11,t12,…,t1m1, T2=t21,t22,...,t2m2, 1≤a1≤m1=T1, and 1≤a2≤m2=T2.
The scheme of the defined synchronizer is shown in Figure1. The SAPN consists of a set of synchronizers corresponding to different assembly status. The synchronizers are used to illustrate the parallel and selective relations of each assembly operation, including the corresponding precedence relationships.Figure 1
Scheme of synchronizer.Definition 3.
(SAPN). Let SAPN =(P, T, F, W, M, PT, TM) be the synchronized assembly Petri net consisting of assembly synchronizers. Places, transitions, arcs, and other tuples are integrated in the net. Detailed explanation of these tuples is given as follows:P = {pj}, (j = 1, 2, …, m) represents the assembly status, and m is the amount of the places.T = {ti}, (i = 1, 2, …, n) represents the assembly operations, and n is the amount of the transitions.F = {fk}, (k = 1, 2, …, l) represents the directed arcs between transitions and places, and l is the amount of the arcs.W = {wk}: F ⟶ {1, 2, 3, …} represents the weight functions associated with arcs. The weight functions determine the amount of the required tasks for a place to transform into another one. The weight functions should be assigned based on number of the arcs which share the same input/output place in the corresponding synchronizer. For example, there are m1 arcs between T1 and p sharing the same output place p in Figure 1, so the weight functions of these arcs should be both assigned as m1. Also the weight functions of p’s output arcs should be both assigned as m2 according to similar recursion.M = {mi}: T ⟶ {0, 1, 2} represents the markings associated with transitions. Here M is defined to represent the transition status. In the assembly process, the marking M is a piecewise constant vector and the values are dependent on the transition status based on the following rules:(1)mi=0,tiis fired,1,tiis fireable,2,tiis unfireable, while it has’t been fired.PT=pti2:T⟶ti1,i1,i2=1,2,…,n represents the precedence relationships among equipment components. The element pti2 in PT is defined to collect the preceding transitions of ti1. In others words, if ∃p=T1,T2,a1,a2:ti2∈T1∧ti1∈T2, then the transitions in T1 are the predecessors of the transitions in T2.TM = {tmi}:T represents operation times of the transitions.


## 2.3. Construction of SAPN

This subsection introduces construction approach of SAPN through the following steps.Step 1: Generate transitions for each necessary assembly operation.Step 2: Assigntms, ms, and pts to each corresponding transition.Step 3: Generate the starting place, the ending place, and the places between each transition and its predecessors.Step 4: Integrate the duplicated input places of each transition.Step 5: Generate the directed arcs from predecessors to the corresponding places and from the places to the corresponding successors.Step 6: Assign the weight function to each arc.SAPN model can be constructed through the detailed steps mentioned above. Step 1 and Step 2 generate the fundamental transitions. Generation of the corresponding places is processed in Step 3 and Step 4. Since SAPN is oriented to the complex products, the elements in SAPN are unavoidably large. Therefore, the integration process in Step 4 somewhat reduces the scale of SAPN model. Step 5 and Step 6 generate and assign the arcs, which link the elements in each synchronizer.


## 2.4. Analysis of Assembility

A transition which is fireable must satisfy the condition that its preceding transitions have all been fired in the synchronizer. Assembility of each component can be determined from the precedence relationships and the status, i.e.,PT and M. The necessary and sufficient condition of ti1 being fireable is given as below:(2)mi1=1.Equation (2) can also be rewritten as(3)∀ti2∈pti1:∑mi2=0∧mi1≠0.It is seen from (3) that ti1 is fireable when its preceding transitions have all been fired; namely, mi2=0. Analysis of assembility is necessary in the sequence optimization process to avoid violation of precedence relationships.


## 3. Principles of Sequence Optimization

In this section, PSOBC framework is developed to solve the PASP problem. The algorithm alternates between phases of attraction and repulsion. Once the diversity of population is too high, the individuals will be congregated by attraction force to explore better solution. If the diversity of population is too low, the individuals will be dispersed by repulsion force to ensure better convergence. Thus the sequence optimization can be efficiently performed.


### 3.1. Problem Statement

Here we use a simple example to illustrate the principles of PASP. The parallel assembly scheme is shown in Figure2. It is assumed that there are 3 manipulators and 13 individual parts of equipment. The length of each rectangle in Figure 2 represents the assembly time of the corresponding part. Three manipulators are employed and five assembly steps are involved in the process. During the process, time represents the operation time of the whole assembly process. To improve efficiency, the goal of sequence planning is set to minimize the assembly time, time. DPA can be defined to describe the biggest number of components or parts to be assembled simultaneously, i.e., the amount of the manipulators. According to the definition, the DPA of the example in Figure 2 is 3.Figure 2
Scheme of parallel assembly.To improve assembly performance, time study is considered to minimize assembly time. The objective function is given in the following formulation:(4)mintime=∑s=1Stimes.In (4), times represents operation time of the subassembly s and time represents the whole assembly time.


### 3.2. Coding Rules

In this subsection, coding rules for PASP problem are proposed according to its features. The rules include particle position, particle velocity, fitness function, and diversity function. Since matrix calculation is avoided, calculation process would be in high efficiency and effectiveness.Definition 4.
(particle position). Let the particle positionXd be a parallel sequence, which is expressed by a vector as below:(5)Xd=xd1xd2…xdi…xdn.
Sincexdi represents subassembly index of transition ti, it is supposed to be an integer.Definition 5.
(particle velocity). Let the particle velocityVd be the updating rule for the particles, which is represented by another vector as below:(6)Vd=vd1vd2…vdi…vdn.
Sincevdi represents the updating rule for transition ti of particle Xd, vdi is supposed to be a real number.Definition 6.
(fitness function). Let the fitness function be the formulation to evaluate particle positions as expressed in(7)FTX=Ct−∑s=1Stimes+δpFps+δlFls.
In (7), Ct is a constant defined to convert minimization to maximization. Assembly time is considered in the fitness function to optimize assembly efficiency, while the two penalty factors/functions are used to, respectively, investigate precedence relationships and parallel principles.
To calculate the fitness function, the first step is decodingX into parallel assembly sequence based on its definition, while the second step is calculating each times, Fp (s), and Fl (s). times is the max operation time in subassemblys. Fp (s) equals the number of unfireable transitions in subassembly s, i.e., the marking values of the transitions equal 2 according to analysis of assembility in the synchronizer (3). After calculating each Fp (s), marking values of transitions in the subassembly should be set as 0, and marking values of the unfired transitions in SDPN should be set as 1 if their preceding transitions have all been fired, or the values remain equal to 2. Fl (s) equals 0 if operation number of subassembly s is less than DPA, or it equals DPA minus operation number.Definition 7.
(diversity of population). Let the diversity of population be the formulation shown in (8) to evaluate the average distance between all particles.(8)FdPl=1LPl∑d=1Pl∑i=1nxdi−x¯i2.
In (8), Pl is the population size, while x¯i is the mean subassembly indices of ti in the population. Diversity function is formulated to detect premature convergence, and then attraction/repulsion phase can be implemented to improve algorithm performance.


### 3.3. Algorithm Optimization

LetVdg be the velocity of particle d in generation g, and Xdg be the position of particle d in generation g. The PSOBC algorithm should be implemented with the following equations:(9)Vdg+1=ω×Vdg+clr1×Bid−Xdg+cgr2Bgd−Xdg,(10)Xdg+1=Xdg+Vdg+1,(11)Vdg+1=ω×Vdg−clr1×Wid−Xdg−cgr2Wgd−Xdg.In attraction phase, (9) and (10) should be exerted to optimize solutions with the principle of approaching local/global best positions. In repulsion phase, (10) and (11) should be exerted to improve convergence with the principle of escaping from local/global worst positions. The calculating rules of (9)∼(11) are proposed as below.(12)Xd1±Xd2=V=xd11±xd21xd12±xd22…xd1n±xd2n,(13)k×Vd=V=kvdkvd…kvd,(14)Vd1±Vd2=V=vd11±vd21vd12±vd22…vd1n±vd2n,(15)Xd+Vd=X=xd1+vd1xd2+vd2…xdi+vdi…xdn+vdn.Sincexs are integers and vs are real numbers, the elements in X should be both rounded to integers after calculation using (15).


## 3.1. Problem Statement

Here we use a simple example to illustrate the principles of PASP. The parallel assembly scheme is shown in Figure2. It is assumed that there are 3 manipulators and 13 individual parts of equipment. The length of each rectangle in Figure 2 represents the assembly time of the corresponding part. Three manipulators are employed and five assembly steps are involved in the process. During the process, time represents the operation time of the whole assembly process. To improve efficiency, the goal of sequence planning is set to minimize the assembly time, time. DPA can be defined to describe the biggest number of components or parts to be assembled simultaneously, i.e., the amount of the manipulators. According to the definition, the DPA of the example in Figure 2 is 3.Figure 2
Scheme of parallel assembly.To improve assembly performance, time study is considered to minimize assembly time. The objective function is given in the following formulation:(4)mintime=∑s=1Stimes.In (4), times represents operation time of the subassembly s and time represents the whole assembly time.


## 3.2. Coding Rules

In this subsection, coding rules for PASP problem are proposed according to its features. The rules include particle position, particle velocity, fitness function, and diversity function. Since matrix calculation is avoided, calculation process would be in high efficiency and effectiveness.Definition 4.
(particle position). Let the particle positionXd be a parallel sequence, which is expressed by a vector as below:(5)Xd=xd1xd2…xdi…xdn.
Sincexdi represents subassembly index of transition ti, it is supposed to be an integer.Definition 5.
(particle velocity). Let the particle velocityVd be the updating rule for the particles, which is represented by another vector as below:(6)Vd=vd1vd2…vdi…vdn.
Sincevdi represents the updating rule for transition ti of particle Xd, vdi is supposed to be a real number.Definition 6.
(fitness function). Let the fitness function be the formulation to evaluate particle positions as expressed in(7)FTX=Ct−∑s=1Stimes+δpFps+δlFls.
In (7), Ct is a constant defined to convert minimization to maximization. Assembly time is considered in the fitness function to optimize assembly efficiency, while the two penalty factors/functions are used to, respectively, investigate precedence relationships and parallel principles.
To calculate the fitness function, the first step is decodingX into parallel assembly sequence based on its definition, while the second step is calculating each times, Fp (s), and Fl (s). times is the max operation time in subassemblys. Fp (s) equals the number of unfireable transitions in subassembly s, i.e., the marking values of the transitions equal 2 according to analysis of assembility in the synchronizer (3). After calculating each Fp (s), marking values of transitions in the subassembly should be set as 0, and marking values of the unfired transitions in SDPN should be set as 1 if their preceding transitions have all been fired, or the values remain equal to 2. Fl (s) equals 0 if operation number of subassembly s is less than DPA, or it equals DPA minus operation number.Definition 7.
(diversity of population). Let the diversity of population be the formulation shown in (8) to evaluate the average distance between all particles.(8)FdPl=1LPl∑d=1Pl∑i=1nxdi−x¯i2.
In (8), Pl is the population size, while x¯i is the mean subassembly indices of ti in the population. Diversity function is formulated to detect premature convergence, and then attraction/repulsion phase can be implemented to improve algorithm performance.


## 3.3. Algorithm Optimization

LetVdg be the velocity of particle d in generation g, and Xdg be the position of particle d in generation g. The PSOBC algorithm should be implemented with the following equations:(9)Vdg+1=ω×Vdg+clr1×Bid−Xdg+cgr2Bgd−Xdg,(10)Xdg+1=Xdg+Vdg+1,(11)Vdg+1=ω×Vdg−clr1×Wid−Xdg−cgr2Wgd−Xdg.In attraction phase, (9) and (10) should be exerted to optimize solutions with the principle of approaching local/global best positions. In repulsion phase, (10) and (11) should be exerted to improve convergence with the principle of escaping from local/global worst positions. The calculating rules of (9)∼(11) are proposed as below.(12)Xd1±Xd2=V=xd11±xd21xd12±xd22…xd1n±xd2n,(13)k×Vd=V=kvdkvd…kvd,(14)Vd1±Vd2=V=vd11±vd21vd12±vd22…vd1n±vd2n,(15)Xd+Vd=X=xd1+vd1xd2+vd2…xdi+vdi…xdn+vdn.Sincexs are integers and vs are real numbers, the elements in X should be both rounded to integers after calculation using (15).


## 4. Case Study

In this paper, a metallurgical reducer is taken as an example to verify the feasibility and the efficiency of the proposed method. The DPAs are selected as 2, 3, and 4, respectively. The explosive diagram of the reducer is shown in Figure3, including 50 components in total. The main parts of the reducer are gears, boxes, caps, bears, shafts, lubricating rings, and eccentric sleeves.Figure 3
Explosive diagram of the metallurgical reducer.


### 4.1. Establishing SAPN

Based on the reducer structure, the places, transitions, arcs, and other tuples in SAPN= (P, T, F, W, M, PT, TM) are established in Section 2.3. Structure diagram of the SAPN is built as shown in Figure 4. In the net model, P is the set of places defined to represent component status. p1 and p49 are the starting and ending places. T is the set of transitions, representing the assembly operations. Definitions of the transitions in the SAPN model are given in Table 1. F is the set of arcs, representing flow relations between transition and place. W is the set of weights associated with the arcs. The weight functions are assigned based on the definition mentioned in Section 2.2. For example, weight functions of the arcs between p2 and t2, p5 and t5, and p28 and t28 are assigned as 1, while weight function of the arcs between p29 and t41 is assigned as 3. M is the set of markings associated with transitions. Precedence relationships are illustrated in PT to analyze the component assembility. TM is the set of assembly times associated with each assembly operation.Figure 4
SAPN model of the reducer.Table 1
Detailed definitions of transitions in the SAPN.
TTargeted partNo.PTTMMTTargeted partNo.PTTMMt1NullNull∅02t26Lubricating ring 341{t18, t23}1.82t2Bear 1218{t1}1.92t27Bear 43{t1}2.12t3Bear 1145{t1}1.62t28Bear 39{t1}2.12t4Eccentric sleeve 544{t1}2.12t29Bear 247{t24}2.12t5Spline20{t1}1.82t30Lock 333{t1}1.22t6Eccentric sleeve 424{t2}2.12t31Bear 139{t18}1.42t7Bear 1015{t1}1.32t32Lubricating ring 242{t26}1.52t8Bear 917{t1}1.32t33Sleeve 32{t27}2.12t9Gear 723{t1}1.32t34Sleeve 210{t1}3.82t10Gear 622{t1}1.32t35Eccentric sleeve 28{t28}2.12t11Bear 836{t1}2.12t36Lubricating ring 14{t1}1.52t12Lubricating ring 427{t1}3.82t37Gear 17{t1}3.12t13Sleeve 329{t3, t4}1.72t38Sleeve 16{t1}3.82t14Inner splined sleeve19{t5}2.82t39Eccentric sleeve 146{t29}2.32t15End cap 413{t6}2.12t40Lock 234{t30}1.92t16Gear 514{t7, t8}3.12t41Middle box11{t31, t24, t39}2.12t17Gear 425{t1}3.62t42Lock 132{t25}1.62t18Gear 321{t9, t10}3.52t43Input shaft43{t31, t32}4.22t19Bear 738{t11}2.12t44Output shaft 15{t33}7.22t20Blank cap 226{t12}0.92t45End cap 337{t33}0.91t21Gear 230{t13}3.82t46End cap 337{t39, t32, t41}0.91t22Bear 631{t1}1.92t47End cap 212{t1}0.91t23Bear 540{t1}2.12t48End cap 135{t40}1.81t24Intermediate shaft16{t14∼t19}9.52t49Upper box49{t42, t43}4.11t25Output shaft 228{t20∼t22}12.12t50Oil collecting hood1{t44}1.61It is seen from Table1 that large size of matrices would be generated if the matrix-based method was adopted for metallurgical reducer ASP design, which would be complex and difficult to implement. This problem can be addressed through the proposed PASP framework.


### 4.2. Population Initialization

Based on the heuristic mechanism of PSOBC, population initialization is required for the sequence optimization. The stages of population initialization can be structured as a flow chart represented in Figure5. Detailed explanation of the initialization procedure is given in the following steps.Step 1: Obtain the precedence relationships and the initial status of the components fromPT and M. Build IP (an empty set of particles position) as the initial population.Step 2: Build a new particle positionPDS (an empty set of transitions).Step 3: Build a new set of all fireable transitionsRTS based on analysis of assembility.Step 4: Build a new assembly stepDS (an empty set of transitions). If nr (the amount of transitions in RTS) exceeds DPA, randomly push 1∼DPA assembly operations into DS. Otherwise, push all the operations form RTS into DS. Update status and marking of the transitions in DS, and push the transitions from DS into PDS.Step 5: Remove the fired transitions inRTS based on PT and M.Step 6: Ifnr is positive, return to step 4. Otherwise, encode PDS into a particle position (an index vector) and push it into IP; return to step 7.Step 7: Ifnp (the amount of particles) exceeds the population size nt, output the initial population IP and end. Otherwise, return to step 3.Figure 5
Flow chart of population initialization.In the C# environment, the population sizent is set as 50 and the DPAs are set as 2, 3, and 4, respectively. The three initial populations are exported after running the initialization codes. According to the biologically inspired mechanism of PSOBC, the initial population is the origin for the bacterial evolution.The key procedure of PASP is the sequence optimization process implemented to find the optimal solution. Main stages of heuristic optimization can be structured as another flow chart represented in Figure6. Detailed explanation of the procedure is illustrated in the following steps.Figure 6
Flow chart of sequence optimization.


### 4.3. Generation of the Optimal Sequences

The key procedure of PDSP is the sequence optimization process implemented to find the optimal solution. Main stages of heuristic optimization can be structured as another flow chart represented in Figure6. Detailed explanation of the procedure is illustrated in the following steps:Step 1: Input the initial population from initialization process. Set phase as “attraction.”Step 2: Update the current best and worst particle position for individuals and the whole population.Step 3: If the phase is “attraction,” calculate the new velocity and position for each particle using (9) and (10). Otherwise, calculate using (10) and (11).Step 4: Calculate diversity function of the population. If premature convergence occurs, set the phase as “repulsion” and return tostep 6. Otherwise, return to step 5.Step 5: Calculate diversity function of the population. If premature convergence is escaped, set the phase as “attraction” and return tostep 6.Step 6: If the termination condition is satisfied, decode the optimal solution and end. Otherwise, return tostep 2.In the optimization procedure, the parameters are set asδp = δl = 5, itnmax = 150, cl = cg = 2, dh = 0.1, and dl = 0.001, and ω will linearly decrease from 1 to 0 during the searching process. Here, the parameters are set not only based on the features of PASP problem and PSOBC algorithm, but also referring to researches in [25, 26].


### 4.4. Discussions and Comparisons

Three different simulations are conducted to verify the proposed method when DPAs are settled as 2, 3, and 4, respectively. The proposed PSOBC simulations have been compared with standard PSO method in Figure7. To keep consistency, the simulation parameters including learning factor, penalty factors, and inertia factor are chosen as the same in both PSOBC and PSO for different DPAs. In Figure 7(a), DPAs are both settled as 2. For PSO simulation, the assembly time is 81.5 seconds. The assembly time of PSOBC method is 74.8 seconds. Compared to the standard PSO, the efficiency is increased by 9.0%. Detailed explanation of 2-DPA assembly sequence is given in Table 2.Figure 7
Optimization results and comparison. (a) Optimization result with 2-DPD. (b) Optimization result with 3-DPD. (c) Optimization result with 4-DPD.
(a)(b)(c)Table 2
Parallel assembly sequence of 2-DPA.
Subassembly indexSubassemblyTargeted parts1(17, 20)Bear 9 and spline2(23, 15)Gear 7 and bear 103(22, 36)Gear 6 and bear 84(21, 14)Gear 13 and gear 55(40, 18)Gear 7 and bear 126(45, 24)Bear 11 and eccentric sleeve 47(38, 13)Bear 7 and end cap 48(19, 27)Inner splined sleeve9(41, 44)Lubricating ring 3 and eccentric sleeve 510(26, 29)Blank cap 211(31)Bear 612(30, 25)Gear 2 and gear 413(28, 16)Output shaft and intermediate shaft14(32, 3)Lock 1 and bear 415(42, 47)Lubricating ring 2 and bear 216(39)Bear 117(46, 6)Eccentric sleeve 1 and sleeve 118(33, 9)Lock 3 and bear 319(34, 8)Lock 2 and eccentric sleeve 220(7)Gear 121(43, 10)Input shaft and sleeve 222(2)Sleeve 323(11, 4)Middle box and lubricating ring 124(12, 37)End cap 2 and end cap 325(5, 49)Output shaft 1 and upper box26(1, 35)Oil collecting hood27(48)Blank cap 1In Figure7(b), DPAs are both settled as 3. It is seen that the assembly time of PSO is 62.1 seconds while the assembly time of PSOBC is 59.6 seconds. Compared to the standard PSO, the assembly efficiency is increased by 4.2%. The optimal sequence carried out by PSOBC method is given in Table 3 when DPA is set as 3.Table 3
Parallel assembly sequence of 3-DPA.
Subassembly indexSubassemblyTargeted parts1(44, 45, 18)Eccentric sleeve 5, bear 11, and bear 122(29, 27, 23)Sleeve 3, lubricating ring 4, and gear 73(26, 21, 22)Blank cap 2, gear 3, and gear 64(9, 3, 31)Bear 3, bear 4, and bear 65(6, 24, 20)Sleeve 1, eccentric sleeve 4, and spline6(15, 17, 19)Bear 10, bear 9, and inner splined sleeve7(7, 2, 36)Gear 1, sleeve 3, and bear 88(30, 38, 25)Gear 2, bear 7, and gear 49(4, 8)Lubricating ring 1 and eccentric sleeve 210(14, 10, 13)Gear 5, sleeve 2, and end cap 411(39, 40)Bear 1 and bear 512(5, 28, 16)Output shaft 113(32, 42, 46)Lock 1, lubricating ring 2, and eccentric sleeve 114(43, 11, 34)Input shaft, middle box, and lock 215(49, 1, 37)Upper box, oil collecting hood, and end cap 316(35, 12, 48)End cap 1, end cap 2, and blank cap 1In Figure7(c), DPAs are both settled as 4. Through standard PSO method, assembly time of the solution is 59.1 seconds. The assembly time by using PSOBC is 57.3 seconds. The assembly efficiency is increased by 3.1%. The optimized sequence carried out by PSOBC is given in Table 4.Table 4
Parallel assembly sequence of 4-DPA.
Subassembly indexSubassemblyTargeted parts1(27, 17)Lubricating ring 4 and bear 92(26, 15, 20, 18)Blank cap 2, bear 10, spline, and bear 123(19, 36, 24)Inner splined sleeve, bear 8, and eccentric sleeve 44(38, 45, 44, 31)Bear 7, bear 11, eccentric sleeve 5, and bear 65(23, 29, 4, 22)Gear 7, sleeve 3, lubricating ring 1, and gear 66(30, 21, 14)Gear 2, gear 3, and gear 57(25, 13)Gear 4 and end cap 48(28, 16)Output shaft 2 and intermediate shaft9(7, 3, 47, 40)Gear 1, bear 4, bear 2, and bear 510(46, 2, 39, 41)Eccentric sleeve 1, sleeve 3, bear 1, and lubricating ring 311(9, 42, 32, 11)Bear 3, lubricating ring 2, lock 1, and middle box12(8, 33, 43)Eccentric sleeve 2, lock 3, and input shaft13(34, 6, 10)Lock 2, sleeve 1, and sleeve 214(49, 37, 5)Upper box, end cap 3, and output shaft 115(35, 1, 48, 12)End cap 1, oil collecting hood, blank cap 1, and end cap 2Based on the optimization results and comparison, the following conclusions can be drawn:(1)
Due to implementation of SAPN model, the PASP problem can be effectively and efficiently solved for complex products, while huge matrix calculation is avoided and possibility of human error is reduced.(2)
Compared with the standard PSO algorithm, premature convergence can be effectively prevented through repulsion operation. The solution of PASP problem can be further optimized.


## 4.1. Establishing SAPN

Based on the reducer structure, the places, transitions, arcs, and other tuples in SAPN= (P, T, F, W, M, PT, TM) are established in Section 2.3. Structure diagram of the SAPN is built as shown in Figure 4. In the net model, P is the set of places defined to represent component status. p1 and p49 are the starting and ending places. T is the set of transitions, representing the assembly operations. Definitions of the transitions in the SAPN model are given in Table 1. F is the set of arcs, representing flow relations between transition and place. W is the set of weights associated with the arcs. The weight functions are assigned based on the definition mentioned in Section 2.2. For example, weight functions of the arcs between p2 and t2, p5 and t5, and p28 and t28 are assigned as 1, while weight function of the arcs between p29 and t41 is assigned as 3. M is the set of markings associated with transitions. Precedence relationships are illustrated in PT to analyze the component assembility. TM is the set of assembly times associated with each assembly operation.Figure 4
SAPN model of the reducer.Table 1
Detailed definitions of transitions in the SAPN.
TTargeted partNo.PTTMMTTargeted partNo.PTTMMt1NullNull∅02t26Lubricating ring 341{t18, t23}1.82t2Bear 1218{t1}1.92t27Bear 43{t1}2.12t3Bear 1145{t1}1.62t28Bear 39{t1}2.12t4Eccentric sleeve 544{t1}2.12t29Bear 247{t24}2.12t5Spline20{t1}1.82t30Lock 333{t1}1.22t6Eccentric sleeve 424{t2}2.12t31Bear 139{t18}1.42t7Bear 1015{t1}1.32t32Lubricating ring 242{t26}1.52t8Bear 917{t1}1.32t33Sleeve 32{t27}2.12t9Gear 723{t1}1.32t34Sleeve 210{t1}3.82t10Gear 622{t1}1.32t35Eccentric sleeve 28{t28}2.12t11Bear 836{t1}2.12t36Lubricating ring 14{t1}1.52t12Lubricating ring 427{t1}3.82t37Gear 17{t1}3.12t13Sleeve 329{t3, t4}1.72t38Sleeve 16{t1}3.82t14Inner splined sleeve19{t5}2.82t39Eccentric sleeve 146{t29}2.32t15End cap 413{t6}2.12t40Lock 234{t30}1.92t16Gear 514{t7, t8}3.12t41Middle box11{t31, t24, t39}2.12t17Gear 425{t1}3.62t42Lock 132{t25}1.62t18Gear 321{t9, t10}3.52t43Input shaft43{t31, t32}4.22t19Bear 738{t11}2.12t44Output shaft 15{t33}7.22t20Blank cap 226{t12}0.92t45End cap 337{t33}0.91t21Gear 230{t13}3.82t46End cap 337{t39, t32, t41}0.91t22Bear 631{t1}1.92t47End cap 212{t1}0.91t23Bear 540{t1}2.12t48End cap 135{t40}1.81t24Intermediate shaft16{t14∼t19}9.52t49Upper box49{t42, t43}4.11t25Output shaft 228{t20∼t22}12.12t50Oil collecting hood1{t44}1.61It is seen from Table1 that large size of matrices would be generated if the matrix-based method was adopted for metallurgical reducer ASP design, which would be complex and difficult to implement. This problem can be addressed through the proposed PASP framework.


## 4.2. Population Initialization

Based on the heuristic mechanism of PSOBC, population initialization is required for the sequence optimization. The stages of population initialization can be structured as a flow chart represented in Figure5. Detailed explanation of the initialization procedure is given in the following steps.Step 1: Obtain the precedence relationships and the initial status of the components fromPT and M. Build IP (an empty set of particles position) as the initial population.Step 2: Build a new particle positionPDS (an empty set of transitions).Step 3: Build a new set of all fireable transitionsRTS based on analysis of assembility.Step 4: Build a new assembly stepDS (an empty set of transitions). If nr (the amount of transitions in RTS) exceeds DPA, randomly push 1∼DPA assembly operations into DS. Otherwise, push all the operations form RTS into DS. Update status and marking of the transitions in DS, and push the transitions from DS into PDS.Step 5: Remove the fired transitions inRTS based on PT and M.Step 6: Ifnr is positive, return to step 4. Otherwise, encode PDS into a particle position (an index vector) and push it into IP; return to step 7.Step 7: Ifnp (the amount of particles) exceeds the population size nt, output the initial population IP and end. Otherwise, return to step 3.Figure 5
Flow chart of population initialization.In the C# environment, the population sizent is set as 50 and the DPAs are set as 2, 3, and 4, respectively. The three initial populations are exported after running the initialization codes. According to the biologically inspired mechanism of PSOBC, the initial population is the origin for the bacterial evolution.The key procedure of PASP is the sequence optimization process implemented to find the optimal solution. Main stages of heuristic optimization can be structured as another flow chart represented in Figure6. Detailed explanation of the procedure is illustrated in the following steps.Figure 6
Flow chart of sequence optimization.


## 4.3. Generation of the Optimal Sequences

The key procedure of PDSP is the sequence optimization process implemented to find the optimal solution. Main stages of heuristic optimization can be structured as another flow chart represented in Figure6. Detailed explanation of the procedure is illustrated in the following steps:Step 1: Input the initial population from initialization process. Set phase as “attraction.”Step 2: Update the current best and worst particle position for individuals and the whole population.Step 3: If the phase is “attraction,” calculate the new velocity and position for each particle using (9) and (10). Otherwise, calculate using (10) and (11).Step 4: Calculate diversity function of the population. If premature convergence occurs, set the phase as “repulsion” and return tostep 6. Otherwise, return to step 5.Step 5: Calculate diversity function of the population. If premature convergence is escaped, set the phase as “attraction” and return tostep 6.Step 6: If the termination condition is satisfied, decode the optimal solution and end. Otherwise, return tostep 2.In the optimization procedure, the parameters are set asδp = δl = 5, itnmax = 150, cl = cg = 2, dh = 0.1, and dl = 0.001, and ω will linearly decrease from 1 to 0 during the searching process. Here, the parameters are set not only based on the features of PASP problem and PSOBC algorithm, but also referring to researches in [25, 26].


## 4.4. Discussions and Comparisons

Three different simulations are conducted to verify the proposed method when DPAs are settled as 2, 3, and 4, respectively. The proposed PSOBC simulations have been compared with standard PSO method in Figure7. To keep consistency, the simulation parameters including learning factor, penalty factors, and inertia factor are chosen as the same in both PSOBC and PSO for different DPAs. In Figure 7(a), DPAs are both settled as 2. For PSO simulation, the assembly time is 81.5 seconds. The assembly time of PSOBC method is 74.8 seconds. Compared to the standard PSO, the efficiency is increased by 9.0%. Detailed explanation of 2-DPA assembly sequence is given in Table 2.Figure 7
Optimization results and comparison. (a) Optimization result with 2-DPD. (b) Optimization result with 3-DPD. (c) Optimization result with 4-DPD.
(a)(b)(c)Table 2
Parallel assembly sequence of 2-DPA.
Subassembly indexSubassemblyTargeted parts1(17, 20)Bear 9 and spline2(23, 15)Gear 7 and bear 103(22, 36)Gear 6 and bear 84(21, 14)Gear 13 and gear 55(40, 18)Gear 7 and bear 126(45, 24)Bear 11 and eccentric sleeve 47(38, 13)Bear 7 and end cap 48(19, 27)Inner splined sleeve9(41, 44)Lubricating ring 3 and eccentric sleeve 510(26, 29)Blank cap 211(31)Bear 612(30, 25)Gear 2 and gear 413(28, 16)Output shaft and intermediate shaft14(32, 3)Lock 1 and bear 415(42, 47)Lubricating ring 2 and bear 216(39)Bear 117(46, 6)Eccentric sleeve 1 and sleeve 118(33, 9)Lock 3 and bear 319(34, 8)Lock 2 and eccentric sleeve 220(7)Gear 121(43, 10)Input shaft and sleeve 222(2)Sleeve 323(11, 4)Middle box and lubricating ring 124(12, 37)End cap 2 and end cap 325(5, 49)Output shaft 1 and upper box26(1, 35)Oil collecting hood27(48)Blank cap 1In Figure7(b), DPAs are both settled as 3. It is seen that the assembly time of PSO is 62.1 seconds while the assembly time of PSOBC is 59.6 seconds. Compared to the standard PSO, the assembly efficiency is increased by 4.2%. The optimal sequence carried out by PSOBC method is given in Table 3 when DPA is set as 3.Table 3
Parallel assembly sequence of 3-DPA.
Subassembly indexSubassemblyTargeted parts1(44, 45, 18)Eccentric sleeve 5, bear 11, and bear 122(29, 27, 23)Sleeve 3, lubricating ring 4, and gear 73(26, 21, 22)Blank cap 2, gear 3, and gear 64(9, 3, 31)Bear 3, bear 4, and bear 65(6, 24, 20)Sleeve 1, eccentric sleeve 4, and spline6(15, 17, 19)Bear 10, bear 9, and inner splined sleeve7(7, 2, 36)Gear 1, sleeve 3, and bear 88(30, 38, 25)Gear 2, bear 7, and gear 49(4, 8)Lubricating ring 1 and eccentric sleeve 210(14, 10, 13)Gear 5, sleeve 2, and end cap 411(39, 40)Bear 1 and bear 512(5, 28, 16)Output shaft 113(32, 42, 46)Lock 1, lubricating ring 2, and eccentric sleeve 114(43, 11, 34)Input shaft, middle box, and lock 215(49, 1, 37)Upper box, oil collecting hood, and end cap 316(35, 12, 48)End cap 1, end cap 2, and blank cap 1In Figure7(c), DPAs are both settled as 4. Through standard PSO method, assembly time of the solution is 59.1 seconds. The assembly time by using PSOBC is 57.3 seconds. The assembly efficiency is increased by 3.1%. The optimized sequence carried out by PSOBC is given in Table 4.Table 4
Parallel assembly sequence of 4-DPA.
Subassembly indexSubassemblyTargeted parts1(27, 17)Lubricating ring 4 and bear 92(26, 15, 20, 18)Blank cap 2, bear 10, spline, and bear 123(19, 36, 24)Inner splined sleeve, bear 8, and eccentric sleeve 44(38, 45, 44, 31)Bear 7, bear 11, eccentric sleeve 5, and bear 65(23, 29, 4, 22)Gear 7, sleeve 3, lubricating ring 1, and gear 66(30, 21, 14)Gear 2, gear 3, and gear 57(25, 13)Gear 4 and end cap 48(28, 16)Output shaft 2 and intermediate shaft9(7, 3, 47, 40)Gear 1, bear 4, bear 2, and bear 510(46, 2, 39, 41)Eccentric sleeve 1, sleeve 3, bear 1, and lubricating ring 311(9, 42, 32, 11)Bear 3, lubricating ring 2, lock 1, and middle box12(8, 33, 43)Eccentric sleeve 2, lock 3, and input shaft13(34, 6, 10)Lock 2, sleeve 1, and sleeve 214(49, 37, 5)Upper box, end cap 3, and output shaft 115(35, 1, 48, 12)End cap 1, oil collecting hood, blank cap 1, and end cap 2Based on the optimization results and comparison, the following conclusions can be drawn:(1)
Due to implementation of SAPN model, the PASP problem can be effectively and efficiently solved for complex products, while huge matrix calculation is avoided and possibility of human error is reduced.(2)
Compared with the standard PSO algorithm, premature convergence can be effectively prevented through repulsion operation. The solution of PASP problem can be further optimized.


## 5. Conclusions

A novel PASP optimization method is developed for complex product in this paper. A SAPN model is proposed to describe the precedence relationships in the assembly process, while huge matrix calculation is avoided and possibility of human error is reduced. To optimize PASP problem, a PSOBC method is developed along with the SAPN model. Verifications show that assembly time of the optima calculated using the proposed method is 9.0%, 4.2%, and 3.1% better than the standard PSO algorithm when the DPA is 2, 3, and 4, respectively. Assembly time of the three optimal sequences is 74.8 seconds, 59.6 seconds, and 57.3 seconds, separately. Parallel assembly process can be optimally planned by using the proposed method.



---

*Source: 7848329-2020-05-26.xml*