# Development of Automatic Assembly Sequence Generating System Based on the New Type of Parts Liaison Graph

Hong-Seok Park, Jin-Woo Park, Myon-Woong Park, Jae-Kwan Kim

► To cite this version:

Hong-Seok Park, Jin-Woo Park, Myon-Woong Park, Jae-Kwan Kim. Development of Automatic Assembly Sequence Generating System Based on the New Type of Parts Liaison Graph. 10th Product Lifecycle Management for Society (PLM), Jul 2013, Nantes, France. pp.540-549, 10.1007/978-3-642-41501-2_54. hal-01461904

HAL Id: hal-01461904

https://inria.hal.science/hal-01461904

Submitted on 8 Feb 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Development of Automatic Assembly Sequence Generating System based on the New Type of Parts Liaison Graph

Hong-Seok Park¹, Jin-Woo Park¹, Myon-Woong Park², Jae-Kwan Kim²

¹ School of Mechanical Engineering, University of Ulsan, South Korea

² Korea Institute of Science and Technology, South Korea

phosk@ulsan.ac.kr

**Abstract.** Nowadays in order to perform assembly process planning by using CAPP (Computer Aided Process Planning), researches to generate the assembly sequence have come under constant interest by many researchers and they are devoted to optimize the assembly sequence according to the novel approach such as Genetic Algorithm and the newly biology inspired principle such as ant colony optimizing method. In this paper, the developed assembly sequence generating system analyzes the relationship between assembled parts based on surface contacting information. Moreover, this system generates the new type of parts liaison graph for the assembly sequences via analyzed information such as common area between parts, related ratio and number of the connected parts. Finally, the optimized assembly sequence is generated logically through the parts liaison graph.

**Keywords:** Assembly Sequence, Liaison Graph, Related Ratio, Common Area

## 1 Introduction

In order to perform rapid process planning, various tools and methodologies are being used. Especially in order to achieve the automation of machining process planning, computer aided process planning (CAPP) is used by the information exchange and integration between design and machining process. And its technological level is in the maturity stage. Assembly process planning is forming 10%~30% in the whole manufacturing process and the computer aided technologies (CAx) are supporting to carry out the best assembly process plan. Nevertheless, the assembly process planning requires process planar to an enormous effort and time so far. The best assembly sequence generation for assembly process planning is an essential element because the assembly sequence concerns the correctness of process planning. Therefore, many researchers are devoted to optimize the assembly sequence by using various optimization methods.

The representation technology such as the liaison graph technique has been developed and used to represent the assembly sequence. As we know, Bourjault[1],
Homem de Mello and Sanderson[2] and De Fazio and Whitney[3] proposed the various graphs including precedence to generate the best assembly sequence such as relational model graph, directed graph, diamond graph, AND/OR graph and so on. From these graph techniques, hierarchical relation graph[4], skeleton graph[5] and etc. are introduced so far, however, most of the graph techniques do not generate precedence graph from the 3D CAD models automatically. It means that the precedence graph generation step using some geometry based relational model graphs is required additionally. Moreover, geometry based reasoning approach is prone to combinational explosion problem.

In order to reduce the searching space of assembly sequence planning for the complex product, the numerous intelligent algorithms have been developed and used to generate optimal assembly sequence such as genetic algorithms[6,7], artificial neural network[8], ant colony algorithm[9,10] and so on. Most of the optimization algorithms improve the processing efficiency via intelligent sequence combination. However the determination of assembly sequence depends on the initial conditions for a complex product and the influence of the parameters. According to this, part of the optimal solution often tends to converge and the sequence might be changed significantly because of the influence of parameters. In case of genetic algorithm, five stages for performing genetic algorithm can be identified: definition of genes, initial chromosomes, objective function, genetic operators and applied algorithm[11]. The parts of assembly model are considered as genes, therefore each chromosome has the feasible assembly sequences, however the initial chromosomes need to be given by the planner and not only the evaluation criteria but also the objective function for optimal sequence generation need to be set differently and variously for the assembly cases. It means that the engineering parameters such as cost, time, complexity, fits, direction, part type and so on have to be confirmed exactly to get the expected result.

This paper introduces the method of assembly sequence generation based on geometrical analyzing to overcome the shortcoming of the existing optimization methods. It means that the developed system analyzes the relationship between assembled parts based on contacting information such as common area, common volume. Furthermore, the new type of liaison graph, including the precedence between the parts is introduced to generate optimized assembly sequence. With this proposed liaison graph, the developed system generates the appropriate sequence of the product.

# 2 Method of Parts Relation Analyzing to Generate Assembly Sequence

## 2.1 Idea for Connected Condition Recognizing between Parts

The basic idea for recognizing connected condition between parts starts from combined shapes between two parts. Generally, one part has several geometric features, but not all of them are useful for assembly sequence generation. Because the
assembly happens at contact surface and two parts interacting with one another, geometrical features for assembling should be defined in pairs.

This fact derives that if there are two assembled parts, contact region always exists and this contact region is always same between these two assembled parts because of matched geometric features. In other words, the contact region between two assembled parts includes the matched geometric features. Based on this reason, this paper supposes that the common area of contact region which has geometric features can derive out the precedence between the assembled parts.

## 2.2 Connected Parts Analyzing

This paper defines RR (Related Ratio) in order to determine the relationship between the parts. RR is classified to RR<sub>CAR</sub> (Common Area Ratio) and RR<sub>CVR</sub> (Common Volume Ratio). RRs between the parts can be derived as the combination of ratio for the total area(volume) and the common area(volume) of each part (Eq. 1, Eq. 2).

The common area and common area ratio can be used to recognize the precedence between the assembled parts; moreover the common volume can be used to recognize the interference fit because some designers reflect the tolerances to the 3D models directly.

$$RR_{CAR} = \left( \frac{\text{CommonArea of A\&B}}{\text{Total Area of A}} + \frac{\text{CommonArea of A\&B}}{\text{Total Area of B}} \right) \times \frac{100}{2} \quad (1)$$

$$RR_{CVR} = \left( \frac{\text{CommonVolumeof A\&B}}{\text{Total Volumeof A}} + \frac{\text{CommonVolumeof A\&B}}{\text{Total Volumeof B}} \right) \times \frac{100}{2} \quad (2)$$

If the assembly depth between the parts is increased, RR will be increased based on Eq. 1 & Eq. 2(Fig. 1). RRs need to be calculated for every part for deriving the weighting factor to draw product liaison graph.

<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Related Ratio between two parts (a) Separated case: RR<sub>CAR</sub> = 0%, (b) Assembled case: RR<sub>CAR</sub> = 45%</figcaption></figure>
## 2.3 Calculation of Weighting Factor for Assembly Sequence

As preparation for the assembly sequence generation, the parts liaison is drawn and the liaison graph uses the weighting factors. The weighting factor is shown as Eq. 3 and it was prepared based on experiments and experiences with CA (Common Area), CV (Common Volume) and the count of connected parts of each part (n) are composed for Eq. 2.3 with RRs.

$$wf = \frac{e^{\left( \frac{\log_{RRCAR} CA + \log_{RRCVR} CV}{n} \right)}}{e^{\left( \frac{\log_{RRCAR} CA}{n} \right)} + e^{\left( \frac{\log_{RRCVR} CV}{n} \right)}} \quad (3)$$

This mathematical model considers the difficulty of assembly and the manufacturing cost indirectly. In some researches, the difficulty of assembly was derived based on log formulation [12,13] and the manufacturing cost was derived based on exponential formulation [14]. If the assembly depth is large i.e., common area and common volume is high, the assembly difficulty will be increased and the assemblability will be decreased. And if the assembly difficulty is high, the manufacturing cost will be increased. Based on this phenomenon, we use the log and exponential formulation with the RRs, CA, CV and the count of connected parts of each part. Fig. 2 shows the weighting factor variation of experiment between two parts in Fig. 1. The initial state of the experiment is the assembled condition and the final state of the experiment is the separated condition. The weighting factor was calculated during translation of part A from the initial state to the final state based on Eq. (3).

<figure><img src="image_3.png" /><figcaption>**Fig. 2.** Weighting factor variation during translation</figcaption></figure>

As a result, if there are two cases of assembled state such as large assembly depth(difficult) and small assembly depth(easy) for the same assembly parts, normally the easy assembly will be considered priorly.
# 3 Parts Liaison Graph Drawing based on Weighting Factor and Assembly Sequence Generation based on the Graph and the Rule

## 3.1 Node Adding/Deleting/Combining

In order to generate the assembly sequence, the parts liaison graph needs to be drawn by using analyzed information such as connected parts list and weighting factors. The parts liaison graph is drawn based on the order of adding nodes, deleting nodes and combining nodes. The base part is selected according to the highest volume, the highest area and the largest number of connected parts.

The base part node is placed at the center and then the connected parts of the base part are placed radially around the base part node in the higher order of weighting factor. Then, the duplicated nodes that represent the same part in the upper level will be deleted. After deleting the nodes, combining step is performed to combine the same nodes at the latest level. These 3 steps will be repeated to construct the liaison graph (Fig. 3).

<figure><img src="image_4.png" /><figcaption>Fig. 3. Drawing Method of the Parts Liaison Graph</figcaption></figure>

## 3.2 Rule of Assembly Sequence Generation based on the Parts Liaison Graph

Through the drawn parts liaison graph, the assembly sequence can be generated as follows:

1. The node of base part is the start point of the assembly sequence.
2. The normal nodes of part are added to the assembly sequence after previous nodes.
3. If a node faces the branch of a road, the direction of progression is the node which has higher weighting factor.
4. The node of fastener part i.e. bolt, nut, pin, screw and washer is not added to the assembly sequence at the first progress.

5. If a node faces the branch of a road again or if the progress is stopped, the passed nodes of fastener part are added to the assembly sequence.

6. If a node is connected with three or more normal parts, they can be a sub assembly. But, the fastener connected to sub assembly will not added in sub assembly construction

7. All nodes are added once in order to configure the graph

In a sub assembly, if any fastener is connected to sub assembly and any normal part of the sub assembly, the graph doesn't show the connection of fastener with normal part of the sub assembly although this fastener is added to the sub assembly.

# 4 Architecture of Assembly Sequence Generating System and its Implementation

## 4.1 System Architecture

The developed system architecture is shown in Fig. 4. The system architecture is configured with 4 interfaces such as the geometric data extraction, the part relation analysis, the parts liaison graph drawing, the assembly sequence generation. And several modules are consisted in each interface.

<figure><img src="image_5.png" /><figcaption>Fig. 4. Architecture of Assembly Sequence Generating System</figcaption></figure>
The interface of geometric data extraction can load the product which includes the sub parts. The object file format is STEP. After loading the files, this interface collects the area and volume of each part then this information is sent to the part relation analysis interface.

The interface of part relation analysis searches connected parts of each part and this interface calculates CA, RR<sub>CAR</sub>, CV, RR<sub>CVR</sub> and count of connected parts. These data are transferred to the weighting factor calculation module in order to derive the weighting factors of each part. After this progress, base part will be selected.

The interface of part liaison graph drawing displays for the product on the dialog view. This interface is configured with node adding module, node deleting module and node combining module. The linked node information supports to generate assembly sequence. The drawn graph transfers the node and link information to the assembly generation interface in order to create the sequence by using knowledge-based rule.

## 4.2 Design of User Interface and Implementation of the System

The main user interface is shown in Fig. 5. There are 9 main parts to get result such as 1. part loading, 2. analysis of relationship between the parts, 3. selection of base part, 4. assembly sequence generation, 5. product information tree, 6. display view, 7. liaison graph display panel, 8. liaison graph drawing, 9. sequence extraction.

<figure><img src="image_6.png" /><figcaption>Fig. 5. Implementation of the assembly sequence generation system</figcaption></figure>

User can click the part loading button to load and to display the product and then STEP files are loaded through the dialog box. After finishing the loading progress, the product is drawn at the display panel and collected data will be sent to the product information tree. If user clicks the relationship analysis button, the system analyzes and collects the whole necessary data. The color of product will be changed in
analyzing progress. After completion of analysis, the system sends the message to user to notice about completion and analysis data will be sent to the information tree. Then, the system selects the base part through the base part selection button and this information will also be sent to the information tree.

The parts liaison graph can be drawn at the liaison graph display panel which is created through the button of assembly sequence generation. This dialog box has the fastener part input button, graph drawing button. User can input the information of fastener part. Furthermore, graph drawing button will draw the parts liaison graph automatically. Finally, sequence extraction button will carry out the generated assembly sequence. VC++ 8.0 (VS2005) and OpenCASCADE6.5.2. are used to implement the system.

## 4.3 Result of Sequence Generation

In order to evaluate the developed system, the automotive oil pump is used (Fig. 6-(a)). The oil pump has 32 parts and its exploded view is on Fig. 6-(b). The part 26 is selected as a base part. Fig. 7 shows the generated parts liaison graph of this test product. And the generated sequence based on the previous rule is "26→5→7→6→SA1→8→9→10→11→12→3→2→24→15→17→18→20→22→23→25→13→16→19→21→14→SA2". The sub assembly sequence1 is generated as "27→33→31→28" and the sub assembly sequence2 is "1→29→30→4".

<figure><img src="image_7.png" /><figcaption>**Fig. 6.** Test product (a) assembled automotive oil pump product, (b) disassembled 32 parts of automotive oil pump product</figcaption></figure>
<figure><img src="image_8.png" /><figcaption>Fig. 7. Parts liaison graph of automotive oil pump product</figcaption></figure>

**5 Conclusion**

In this paper, the method of assembly sequence generation different from several
optimizing algorithm was introduced. In particular, the ideas of related ratio and the
weighting factor to draw the new type of parts liaison graph were derived. The parts
liaison graph was drawn based on the rules such as node adding, node deleting and
node combining to display as 2D structure. Finally, the assembly sequence was
generated based on the liaison graph information and the proposed rule. It is expected
that the proposed method and implemented system reduce the sequence planning
effort and the planning time.

**Acknowledgments.** This work was supported by the grant from the Industrial Core Technology Development Program (10033163) of the Ministry of Knowledge Economy of Korea.

**References**

1. Bourjault, A.: Computer-aided assembly process planning, Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, vol. 206, no. 1, pp. 61--66 (1992)

2. Homem de Mello, L., Sanderson, A.: AND/OR Graph Representation of Assembly Plans, IEEE Journal of Robotics and Automation, vol. 25, no. 2, pp. 188--199 (1990)
3. De Fazio, T.L., Whitney, D.E.: Simplified Generation of All Mechanical Assembly Sequences, IEEE Journal of Robotics and Automation, vol. 3, no. 6, pp. 640--658 (1987)

4. Niu, X., Ding, H. and Xiong, Y.: A hierarchical approach to generating precedence graphs for assembly planning, International Journal of Machine Tools & Manufacture, 43(14), pp. 1473-1486 (2003)

5. Demoly, F., et al.: Geometric skeleton computation enabling concurrent product engineering and assembly sequence planning, Computer-Aided Design, vol. 43, no. 12, pp. 1654--1673 (2011)

6. Dini, G., et al.: Generation of optimized assembly sequences using genetic algo-rithms, CIRP Annals-Manufacturing Technology, vol. 48, no. 1, pp. 17-20 (1999)

7. Marian, R. M., Luong, L. H.S. and Abhary, K.: A genetic algorithm for the op-timization of assembly sequences, Computers & Industrial Engineering, vol. 50, no. 4, pp. 503-527 (2006)

8. Chen, W. C., et al.: A three-stage integrated approach for assembly sequence planning using neural networks, Expert Systems with Applications, vol. 34, no. 3, pp. 1777-1786 (2008)

9. Failli, F. and Dini, G.: Ant colony systems in assembly planning : a new approach to sequence detection and optimization, In: the 2nd CIRP International Seminar on Intelligent Computation in Manufacturing Engineering, pp. 227--232 (2000)

10. Wang, J.F., Liu, L.H., Zhong, Y.F.: A novel ant colony algorithm for assembly sequence planning, The International Journal of Advanced Manufacturing Technology, vol. 48, no. 1, pp. 17--20 (2005)

11. Wang, L., Keshavarzmanesh, S., Feng, H.Y., Buchal, R.O.: Assembly process planning and its future in collaborative manufacturing: a review, The International Journal of Advanced Manufacturing Technology, vol. 41, issue 1-2, pp. 132--144 (2009)

12. Diaz-Calderon, A., Navin-Chandra, D., Khosla, P.: Measuring the difficulty of assembly tasks from tool access information, In: IEEE International Symposium on Assembly and Task Planning, pp. 1--7 (1995)

13. Park, H.S., Son, S.B.: A knowledge-based system for assembly process planning, Journal of the Korean Society of Precision Engineering, vol. 16, no. 5, pp. 29--39 (1999)

14. Kumar, M.S. and Stalin, B.: Optimum tolerance synthesis for complex assembly with alternative process selection using Lagrange multiplier method, International Journal of Advanced Manufacturing Technology, vol. 44, issue 3-4, pp. 405--411 (2009)