Assembly sequence and path planning for monotone and nonmonotone assemblies with rigid and flexible parts

The Assembly Sequence and Path Planning (ASPP) problem deals with finding a proper sequence of parts to be assembled into a finished product and short assembly paths for each part. The problem is a combination of Assembly Sequence Planning (ASP) and Assembly Path Planning (APP) subproblems, which are both NP-complete and therefore intractable at large sizes. Nearly in all works on ASPP, it is assumed that planning is monotone (i.e., parts are moved only once, without considering intermediate placements) and each part is completely rigid. These are simplifying, yet limiting assumptions, since most assembled products like ships, aircraft, and automobiles are composed of rigid and flexible parts, and the generation of assembly sequence and path plans for most real-world products requires intermediate placement of parts to be taken into account. None of the existing works in the literature, however, have handled nonmonotone ASPP problems for rigid and flexible parts, and this issue remains largely untouched. In this paper, we present a new method called SPP-Flex for solving monotone and nonmonotone ASPP for rigid and flexible parts. SPP-Flex first utilizes a Directional Assembly Stress Matrix (DASM) for describing interference relations between all pairs of parts and the amounts of compressive stresses needed for assembling flexible parts and then obtains an initial tentative assembly sequence using a simple new greedy heuristic. Next, short assembly paths are iteratively computed and planned from initial to goal configurations of all parts using a novel sampling-based path planner called BXXT. If finding a free path for an active part fails due to obstruction of a previously assembled part, then such a part is identified, relocated, and its path replanned until the active part is moved to its final position. In case of failure again, if the part is flexible, through finite element analysis, it is determined if the part can still be assembled by undergoing elastic deformation. To evaluate the performance of the SPP-Flex and its components, two new products were designed and solved by four combinations of ASP and APP methods 20 times each, and the means and standard deviations of five performance criteria (total path length, total number of generated nodes and edges in the search tree, total number of collision (interference) checks, and total runtime) were calculated. Analysis of the computational results showed that the proposed greedy heuristic sequence planner together with the BXXT path planner/replanner outperformed other variations with at most 4.6% average gap in path length and 2.1% average gap in runtime compared to the best-found solution in all runs.     

Assembly sequence planning of rigid and flexible parts

Assembly sequence planning (ASP) is the process of computing a sequence of assembly motions for constituent parts of an assembled final product. ASP is proven to be NP-hard and thus its effective and efficient solution has been a challenge for the researchers in the field. Despite the fact that most assembled products like ships, aircrafts and automobiles are composed of rigid and flexible parts, no work exists for assembly/disassembly sequence planning of flexible parts. This paper lays out a theoretical ground for modeling the deformability of flexible assembly parts by introducing the concept of Assembly stress matrix (ASM) to describe interference relations between parts of an assembly and the amount of compressive stress needed for assembling flexible parts. Also, the Scatter Search (SS) optimization algorithm is customized for this problem to produce high-quality solutions by simultaneously minimizing both the maximum applied stress exerted for performing assembly operations and the number of assembly direction changes. The parameters of this algorithm are tuned by a TOPSIS-Taguchi based tuning method. A number of ASP problems with rigid and flexible parts were solved by the presented SS and other algorithms like Genetic and Memetic algorithms, Simulated Annealing, Breakout Local Search, Iterated Local Search, and Multistart Local Search, and the results and their in-depth statistical analyses showed that the SS outperformed other algorithms by producing the best-known or optimal solutions with highest success rates.     

基于成本和并行装配的装配序列有向图求解

针对虚拟装配中装配序列规划问题,引入了有向图来描述装配过程中的零件以及零件间的装配约束关系。结合装配成本、并行装配、装配经验优化了装配关系有向图的拓扑排序算法。提出了将装配方向变化次数作为衡量装配成本的一项重要指标。提出了将单次可装配的零件数量作为装配优先方向的参考依据。文章最后给出了装配序列生成的具体算法。     

A hybrid genetic algorithm for multi-objective product plan selection problem with ASP and ALB

Facing current environment full of a variety of small quantity customized requests, enterprises must provide diversified products for speedy and effective responses to customers’ requests. Among multiple plans of product, both assembly sequence planning (ASP) and assembly line balance (ALB) must be taken into consideration for the selection of optimal product plan because assembly sequence and assembly line balance have significant impact on production efficiency. Considering different setup times among different assembly tasks, this issue is an NP-hard problem which cannot be easily solved by general method. In this study the multi-objective optimization mathematical model for the selection of product plan integrating ASP and ALB has been established. Introduced cases will be solved by the established model connecting to database statistics. The results show that the proposed Guided-modified weighted Pareto-based multi-objective genetic algorithm (G-WPMOGA) can effectively solve this difficult problem. The results of comparison among three different kinds of hybrid algorithms show that in terms of the issues of ASP and ALB for multiple plans, G-WPMOGA shows better problem-solving capability for four-objective optimization.     

A General Framework for Assembly Planning: The Motion Space Approach

Assembly planning is the problem of finding a sequence of motions to assemble a product from its parts. We present a general framework for finding assembly motions based on the concept of motion space . Assembly motions are parameterized such that each point in motion space represents a mating motion that is independent of the moving part set. For each motion we derive blocking relations that explicitly state which parts collide with other parts; each subassembly (rigid subset of parts) that does not collide with the rest of the assembly can easily be derived from the blocking relations. Motion space is partitioned into an arrangement of cells such that the blocking relations are fixed within each cell. We apply the approach to assembly motions of several useful types, including one-step translations, multistep translations, and infinitesimal rigid motions. Several efficiency improvements are described, as well as methods to include additional assembly constraints into the framework. The resulting algorithms have been implemented and tested extensively on complex assemblies. We conclude by describing some remaining open problems. Received November 15, 1996; revised January 15, 1998.     

A hierarchical approach on assembly sequence planning and optimal sequences analyzing

Assembly sequence planning (ASP) is a critical technology that bridges product design and realization. Deriving and fulfilling of the assembly precedence relations (APRs) are the essential points in assembly sequences reasoning. In this paper, focusing on APRs reasoning, ASP, and optimizing, a hierarchical ASP approach is proposed and its key technologies are studied systematically. APR inferring and the optimal sequences searching algorithms are designed and realized in an integrated software prototype system. The system can find out the geometric APRs correctly and completely based on the assembly CAD model. Combined with the process APRs, the geometric and engineering feasible assembly sequences can be inferred out automatically. Furthermore, an algorithm is designed by which optimal assembly sequences can be calculated out from the immense geometric and engineering feasible assembly sequences. The case study demonstrates that the approach and its algorithms may provide significant assistance in finding the optimal ASP and improving product assembling.     

An integrated job shop scheduling and assembly sequence planning approach for discrete manufacturing

This paper proposes an integrated job shop scheduling and assembly sequence planning (IJSSASP) approach for discrete manufacturing, enabling the part processing sequence and assembly sequence to be optimized simultaneously. The optimization objectives are to minimize the total production completion time and the total inventory time of parts during production. The interaction effects between the job shop schedule and the assembly sequence plan in discrete manufacturing are analyzed, and the mathematical models including the objective functions and the constraints are established for IJSSASP. Based on the above, a non-dominated sorting genetic algorithm-II (NSGA-Ⅱ) with a hybrid chromosome coding mechanism is applied to solve the IJSSASP problem. Through the case studies and comparison tests for different scale problems, the proposed IJSSASP approach is verified to be able to improve the production efficiency and save the manufacturing cost of the discrete manufacturing enterprise more effectively.     

Automatic assembly path planning for wiring harness installations

The automotive industry of today is becoming more focused on electrified and hybrid solutions, where both conventional combustion engines and battery supplied electrical engines need to fit in an already densely packed vehicle. Many quality problems are related do flexible parts. In particular, the assembly of electric cables and wiring harnesses is difficult due to its concealed routing, multiple branching points, weights and the flexibility in the material. To avoid late detection of assembly problems, the assembly aspect must be considered early during conceptual design and production preparation with respect to both feasibility and ergonomics. Development of automatic path planning methods in virtual manufacturing tools supporting deformable parts is therefore highly motivated.     

Assembly sequence planning based on structure cells in open design

Advances in computer network technologies have enabled firms to increasingly utilize external resources to remain competitive. Based on the function-behavior-structure cell (FBSC) modeling and computer network technologies, consumers with design knowledge and experience, called co-designers in this research, can involve in the process of open design (OD) to share their requirements, experiences and knowledge. The structure cells (SCs) provided by the co-designers in OD and the relationships among them are critical for generating the optimal design scheme and assembly sequence planning. However, the existing assembly sequence planning (ASP) approaches mainly focus on identification of the assembly plan based on precedence relations of operations from the predefined parts in the design scheme without considering the utilization of resources available in OD. In this study, a new approach for ASP based on SCs in OD is proposed to tackle this problem. First, the assembly features of the SCs and their matching rules are described in OD, and an approach for calculating the matching intensity between SCs is developed for identifying the assembly relationships between SCs. The design scheme is generated according to the SCs and their assembly relationships. Second, the base part of the design scheme is determined by its correlation degree with other parts. The feasible assembly sequences are derived by reversing the disassembly sequences. As the increase of the number of parts in design scheme will result in the combinatorial explosion of feasible assembly sequences, a particle swarm optimization algorithm is presented to achieve the optimal assembly sequence. A case study is provided to demonstrate the feasibility and effectiveness of the proposed approach.     

A genetic algorithm for the optimisation of assembly sequences

This paper describes a Genetic Algorithm (GA) designed to optimise the Assembly Sequence Planning Problem (ASPP), an extremely diverse, large scale and highly constrained combinatorial problem. The modelling of the ASPP problem, which has to be able to encode any industrial-size product with realistic constraints, and the GA have been designed to accommodate any type of assembly plan and component. A number of specific modelling issues necessary for understanding the manner in which the algorithm works and how it relates to real-life problems, are succinctly presented, as they have to be taken into account/adapted/solved prior to Solving and Optimising (S/O) the problem. The GA has a classical structure but modified genetic operators, to avoid the combinatorial explosion. It works only with feasible assembly sequences and has the ability to search the entire solution space of full-scale, unabridged problems of industrial size. A case study illustrates the application of the proposed GA for a 25-components product.     

Accumulated risk of body postures in assembly line balancing problem and modeling through a multi-criteria fuzzy-genetic algorithm

Monotonous body postures during repetitive jobs negatively affect assembly-line workers with the developing of Work-related Musculoskeletal Disorders (WMSDs). Ergonomics specialists have offered auxiliary posture diversity to deal with the lack of varieties, especially for high-risk ones. Meanwhile, Assembly Line Balancing (ALB) problem has been recognized as a prior thinking to (re)configure assembly lines via the balancing of their tasks among their workstations. Some conventional criteria, cycle time and overall workload are often considered during the balancing. This paper presents a novel model of ALB problem that incorporates assembly worker postures into the balancing. In addition to the conventional ALB criteria, a new criterion of posture diversity is defined and contributes to enhance the model. The proposed model suggests configurations of assembly lines via the balancing; so that the assigned workers encounter the opportunities of changing their body postures, regularly. To address uncertainties in the conventional criteria, a fuzzy goal programming is used, and an appropriate genetic algorithm is developed to deal with the model. Various computational tests are performed on the different models made with combinations of the three criteria mentioned above. Comparing the pay-offs among the combinations, results show that well balanced task allocation can be obtained through the proposed model.     

Assembly features in modeling and planning

In recent years, features have been introduced in modeling and planning for manufacturing of parts. Such features combine geometric and functional information. Here it is shown that the feature concept is also useful in assembly modeling and planning. For modeling and planning of both single parts and assemblies, an integrated object-oriented product model is introduced. For specific assembly-related information, assembly features are used. Handling features contain information for handling components, connection features information on connections between components. A prototype modeling environment has been developed. The product model has been successfully verified within several analyses and planning modules, in particular stability analyses, grip planning, motion planning and assembly sequence planning. Altogether, feature-based product models for assembly can considerably help in both assembly modeling and planning, on the one hand by integrating single-part and assembly modeling, and on the other hand by integrating modeling and planning.     

Joint optimization of product tolerance design,process plan,and production plan in high-precision multi-product assembly

With the ever-increasing product variety faced by the manufacturing industry, investment efficiency can only be maintained by the application of multi-product assembly systems. In such systems, the product design, process planning, and production planning problems related to different products are strongly interconnected. Despite this, those interdependent decisions are typically made by different divisions of the company, by adopting a decomposed planning approach, which can easily result in excess production costs. In order to overcome this challenge, this paper proposes an integrated approach to solving the above problems, focusing on the decisions crucial for achieving the required tolerances in high-precision assembled products. The joint optimization problems related to product tolerance design and assembly resource configuration are first formulated as a mixed-integer linear program (MILP). Then, a large neighborhood search (LNS) algorithm, which combines classical mathematical programming and meta-heuristic techniques, is introduced to solve large instances of the problem. The efficiency of the method is demonstrated through an industrial case study, both in terms of computational efficiency and industrial effectiveness.     

A physically based approach with human–machine cooperation concept to generate assembly sequences

Assembly plan is considered one of the important stages to minimize the cost of manufacturer and to ensure the safety of assembly operation, the main problem of assembly sequence planning approach is how to reduce the deviation from the real manufacture conditions. In this paper, we have extensively investigated a novel approach to automatically generate the assembly sequences for industrial field, which is especially applied to other large-scale structures. A physically based assembly representation model includes not only the pre-determined basic assembly information, such as precedence relations between parts or subassemblies, geometric constraints, different assembly types, and also the dynamic real-time physical properties, such as the center position of gravity, the force strength of the part, et al. This representation model considered the influences on optimum sequences by assembly operations will be modified by the feedback from interactive virtual environment. Then, we select the safety, efficiency and complexity as the optimization objectives. A hybrid search approach may be used to find the optimum assembly sequence, which will be integrated into an interactive assembly virtual environment (IAVE). It means that the results of assembly interaction can be provided to update the assembly planning model as a feedback, by which the approach will take advantages of the immune memory for local optimum search. The user can adjust the assembly sequences with obvious good objective by interaction with IAVE to improve the performance of the search algorithm. We describe human–machine cooperation (HMC) method for ASP in this work, by which human also can play a pivotal role instead of pure soft-computing. A series of numerical experiments are done to validate the performance of the physically based approach (PBA) to generate assembly sequence, which shows the efficiency and the operability to guide the assembly work.     

Chaotic particle swarm optimization for assembly sequence planning

Assembly sequence planning of complex products is difficult to be tackled, because the size of the search space of assembly sequences is exponentially proportional to the number of parts or components of the products. Contrasted with the conventional methods, the intelligent optimization algorithms display their predominance in escaping from the vexatious trap. This paper proposes a chaotic particle swarm optimization (CPSO) approach to generate the optimal or near-optimal assembly sequences of products. Six kinds of assembly process constraints affecting the assembly cost are concerned and clarified at first. Then, the optimization model of assembly sequences is presented. The mapping rules between the optimization model and the traditional PSO model are given. The variable velocity in the traditional PSO algorithm is changed to the velocity operator (vo) which is used to rearrange the parts in the assembly sequences to generate the optimal or near-optimal assembly sequences. To improve the quality of the optimal assembly sequence and increase the convergence rate of the traditional PSO algorithm, the chaos method is proposed to provide the preferable assembly sequences of each particle in the current optimization time step. Then, the preferable assembly sequences are considered as the seeds to generate the optimal or near-optimal assembly sequences utilizing the traditional PSO algorithm. The proposed method is validated with an illustrative example and the results are compared with those obtained using the traditional PSO algorithm under the same assembly process constraints.     

虚拟装配工艺技术研究

虚拟装配技术是未来制造领域中的一项重要技术,它使得人们可以通过直接操作的方式完成产品设计、产品维修培训、零件设计验证、装配工艺规划等内容。     

Assembly and Disassembly: An Overview and Framework for Cooperation Requirement Planning with Conflict Resolution

Assembly, one of the oldest forms of industrial production, and its twin area, disassembly, have enjoyed tremendous modernization in the era of the information revolution. New enabling technologies, including prominent examples such as virtual CAD, Design for Assembly and Disassembly (DFAD), robotic and intelligent assembly, and Flexible Assembly (FA), are now becoming commonplace. This article reviews some of the newer solutions, and an extended framework for Cooperation Requirement Planning (ECRP) in robotic assembly/disassembly is developed. Recent research under the PRISM program at Purdue University to enable ECRP and other relevant projects is presented. The challenges to researchers in this field, in adapting these solutions to the emerging environment of global and local supply networks are also discussed.     

面向机器人装配设计与规划的集成框架

本文针对面向机器人装配的产品设计与装配规划中的关键问题,分析实际产品设计与 装配规划的一般过程,提出了将面向机器人装配的产品设计与装配规划进行系统集成的框架 ,并对系统的各个模块的功能和实现作了研究探讨,通过在工程实践中的应用验证了其正确 性和有效性．     

A repository for design, process planning and assembly

This paper provides an introduction to the Design, Planning and Assembly Repository available through the National Institute of Standards and Technology (NIST). The goal of the Repository is to provide a publically accessible collection of 2D and 3D CAD and solid models from industry problems. In this way, research and development efforts can obtain and share examples, focus on benchmarks, and identify areas of research need. The Repository is available through the World Wide Web at URL http://www.parts.nist.gov/parts.     

Multi-criteria decision making for assembly line balancing

Assembly line balancing often has significant impact on performance of manufacturing systems, and is usually a multiple-objective problem. Neither an algorithmic nor a procedural assembly line balancing methodology is usually effective in solving these problems. This article proposes a data envelopment analysis (DEA) approach to solve an assembly line balancing problem. A computer-aided assembly line balancing tool as Flexible Line Balancing software is used to generate a considerable number of solutions alternatives as well as to generate quantitative decision-making unit outputs. The quantitative performance measures were considered in this article. Then DEA was used to solve the multiple-objective assembly line balancing problem. An illustrative example shows the effectiveness of the proposed methodology.