An effective hybrid graph and genetic algorithm approach to process planning optimization for prismatic parts

Computer-aided process planning is an important interface between computer-aided design and computer-aided manufacturing in computer-integrated manufacturing environments. In this paper, the complicated process planning is modeled as a combinatorial optimization problem with constraints, and a hybrid graph and genetic algorithm (GA) approach has been developed. The approach deals with process planning problems in a concurrent manner by simultaneously considering activities such as sequencing operations, selecting manufacturing resources, and determining setup plans to achieve the global optimal objective. Graph theory accompanied with matrix theory, as the basic mathematical tool for operation sequencing, is embedded into the main frame of GA. The precedence constraints between operations are formulated in an operation precedence graph (OPG). The initial population composed of all feasible solutions is generated by an elaborately designed topologic sort algorithm to the OPG. A modified crossover operator guaranteeing only feasible offspring generated is used, two types of mutation strategies are adopted, and a heuristic algorithm is applied to adjust the infeasible plan generated by the mutation operator to the feasible domain. A case study has been carried out to demonstrate the feasibility and efficiency of the proposed approach.     

多工位装配序列粒子群优化算法

针对传统单工位装配序列求解上的不足,将粒子群算法应用于多工位多目标装配序列优化的求解,提出一种面向复杂多工位产品的装配序列优化方法。采用优先序列图(Assembly precedence graph,APG)来描述零件间的优先约束关系,构建优先关系矩阵、装配干涉矩阵、工位能力表和装配信息表,描述装配部件干涉及工位之间的关系;给出粒子群算法编码体系和装配关系算法模型表达方法;综合考虑装配操作成本、装配工具更换成本和装配夹装变更成本和运输成本的影响,提出有工程意义的适应度函数的表达式;根据APG生成随机的可行初始装配序列,并利用粒子群算法(Particle swarm algorithm,PSO)对装配序列和装配工位进行优化。以飞机起落架装配序列规划实例验证多工位粒子群装配序列优化算法有效性。     

Selecting optimal tools for arbitrarily shaped pockets

As a result of slicing a 3D part into 2D pockets for generating tool paths, pockets are becoming more commonly used. When a pocket is machined, the question of which of the many feasible tools for cutting the pocket is best always arises. Will cutting be more efficient if multi-tools are used? Will the algorithm to choose the optimal tools be timesaving enough? This paper presents a method in which an upper bound O(N) is used to choose the optimal cutting tool combination, where N is the number of feasible tools available. The proposed method is quick and sufficient for computer-aided process planning (CAPP) and computer-aided manufacturing (CAM) environments.     

Integrated setup planning and operation sequencing (ISOS) using genetic algorithm

Process planning is an essential component for linking design and manufacturing process. Setup planning and operation sequencing are two most important functions in the implementation of CAD/CAPP/CAM integration. Many researches solved these two problems separately. Considering the fact that the two functions are complementary, it is necessary to integrate them more tightly so that performance of a manufacturing system can be improved economically and competitively. This paper presents a generative system and genetic algorithm (GA) approach to process plan the given part. The proposed approach and optimization methodology analysis constraints such as TAD?(tool?approach?direction), tolerance relation between features and feature precedence relations to generate all possible setups and operations using workshop resource database. Tolerance relation analysis has a significant impact in setup planning for obtaining the part accuracy. Based on technological constraints, the GA algorithm approach, which adopts the feature-based representation, simultaneously optimizes the setup plan and sequence of operations using cost indices. Case studies show that the developed system can generate satisfactory results in optimizing the integrated setup planning and operation sequencing in feasible condition.     

Object-oriented and fuzzy-set-based approach for set-up planning

Set-up planning is not only a key element of computer-aided process planning (CAPP), but also a key factor for the integration of CAPP with computer-aided fixture planning (CAFP) and production planning and scheduling (PPS). In this work, an object-oriented and fuzzy-set-based approach is developed for set-up planning. Object-oriented technology is employed to represent set-up planning knowledge and generate alternative set-ups which can respond to the dynamic manufacturing resource and facilitate the CAPP/PPS integration. Based on fuzzy-set theory, a fuzzy evaluation function is proposed to produce optimal set-ups. Combined with a real project, a set-up planning system is developed to generate alternative and optimal set-up plans for the machining of prismatic parts.     

Optimal Disassembly Sequence Using Genetic Algorithms Considering Economic and Environmental Aspects

In this paper, a genetic algorithm (GA)-based approach for an optimal disassembly sequence considering economic and environmental aspects is presented. All feasible disassembly sequences are generated by a disassembly tree or an AND/OR graph. Using the disassembly precedence and the disassembly value matrix, a disassembly sequence is optimised. The precedence of disassembly is determined through a disassembly tree or an AND/OR graph and the value of disassembly is induced by considering both economic and environmental aspects in the disassembly, recycling, and disposal phases. Economic and environmental factors can be compared by the same measure through converting environmental factors into economic cost. To solve the disassembly sequence problem, a heuristic algorithm based on GAs is developed. The proposed GA can search for and dynamically explore the disassembly node through the highest disassembly value, keeping their precedence in order to identify an optimal disassembly sequence. It can also help to explore the search space, and an optimal solution can be obtained by applying the optimisation criteria. A refrigerator is used as an example to illustrate the procedure.     

An approach to multi-criteria assembly sequence planning using genetic algorithms

This paper focuses on multi-criteria assembly sequence planning (ASP) known as a large-scale, time-consuming combinatorial problem. Although the ASP problem has been tackled via a variety of optimization techniques, these techniques are often inefficient when applied to larger-scale problems. Genetic algorithm (GA) is the most widely known type of evolutionary computation method, incorporating biological concepts into analytical studies of systems. In this research, an approach is proposed to optimize multi-criteria ASP based on GA. A precedence matrix is proposed to determine feasible assembly sequences that satisfy precedence constraints. A numerical example is presented to demonstrate the performance of the proposed algorithm. The results of comparison in the provided experiment show that the developed algorithm is an efficient approach to solve the ASP problem and can be suitably applied to any kind of ASP with large numbers of components and multi-objective functions.     

Java-based computer-aided process planning

This investigation addresses distributed environments for computer-aided process planning (CAPP) over a network. The Java 2 Enterprise Edition (J2EE) standard using Java is applied to implement cross-platform and distributed computing architecture, thus reducing the system loading during manufacturing process planning. The product-oriented standard, standard exchange of product (STEP), model data is applied to define a robust data model that associates product, shape, and feature definitions and provides the mechanisms for data exchange, sharing, and integration with other engineering systems, such as computer-aided design (CAD) and computer-aided manufacturing (CAM). STEP AP224 is engaged to define the machining features of machined products in the proposed CAPP system. The life cycle of a product from design to sale, and especially the period of manufacturing, can be greatly shortened; the cost of manufacturing can be reduced and the quality of the product can be improved using the proposed CAPP system.     

A hybrid genetic algorithm for integrated process planning and scheduling problem with precedence constraints

Process planning and scheduling are two important functions in a modern manufacturing system. Although integrating decisions related to these functions gives rise to a hard combinatorial problem, due to the impressive improvement in system performance which is resulted through this integration, developing effective methods to solve this problem is of great theoretical and practical importance. In this research, after formulating the integrated process planning and scheduling problem as a mathematical program, we propose a hybrid genetic algorithm (GA) for the problem. In the proposed algorithm, problem-specific genetic operators are designed to enhance the global search power of GA. Also, a local search procedure has been incorporated into the GA to improve the performance of the algorithm. The model considers precedence relations among job operations, based on which feasible process plans for each job can be represented implicitly. A novel neighborhood function, considering the constraints of a flexible job shop environment and nonlinear precedence relations among operations, is presented to speed up the local search process. In experimental study, the performance of the proposed algorithm has been evaluated based on a number of problems adopted from the literature. The experimental results demonstrate the efficiency of the proposed algorithm to find optimal or near-optimal solutions.     

基于智能水滴算法的装夹规划方法

针对计算机辅助工艺设计中的装夹规划问题,提出一种基于智能水滴算法的装夹规划方法。通过对加工特征进行分析来定义零件的操作单元及其约束关系,构建装夹规划的模型。将零件的各个操作单元与智能水滴算法中流动路径的各个节点相关联,利用水滴所携带的泥土量来表征操作单元之间的相似度,以此来构建智能水滴算法的适应度函数。在经过操作单元顺序约束矩阵所筛选出的可行解空间内进行迭代求解,通过水滴多次冲刷路径中的泥土量来筛选最优解,解码后获得了最优的装夹规划方案。以典型零件的装夹规划为例,验证了该方法的有效性和可行性。     

计算机辅助几何可行装配顺序推理及其优化分析

针对装配优先关系分析、几何可行装配顺序推理以及最优几何可行装配顺序选择3个层次的问题,提出了一种系统化的分析方法——几何约束分析方法。该方法从装配体中各个零件之间的约束方向分析出发,可以自动求解出正确和完备的装配优先关系在装配优先关系的约束下,可以计算出所有的几何可行装配顺序规划;并从操作空间大、装配方便角度出发,设计出几何可行装配顺序优选算法,可以从大量的几何可行装配顺序中求解出几何性能最佳的装配顺序规划。应用具体实例分析演示了几何约束分析方法在计算机中的实现过程,并证实了该方法的实用性和有效性。     

A multi-plant assembly sequence planning model with integrated assembly sequence planning and plant assignment using GA

In a multi-plant collaborative manufacturing system, the manufacturing operations and assembly operations for producing a product can be distributed at different plants at various locations. The components are assembled with assembly operations performed in a multi-plant assembly sequence. In this research, a multi-plant assembly sequence planning model is presented by integrating (1) assembly sequence planning, and (2) plant assignment. In assembly sequence planning, the components and assembly operations are sequenced according to the assembly constraints and assembly cost objectives. In plant assignment, the components and assembly operations are assigned to the suitable plants to achieve multi-plant cost objectives. The feasible assembly sequences are generated using the developed graph-based models of assembly precedence graphs and matrices. A genetic algorithm (GA) method is presented to evaluate the multi-plant assembly sequences with an objective of minimizing the total of assembly operational costs and multi-plant costs. The main contribution lies in the new model for multi-plant assembly sequence planning and the new GA encoding scheme for simultaneous assembly sequence planning and plant assignment. Example products are tested and discussed. The test results show that the presented method is feasible and efficient for solving the multi-plant assembly sequence planning problem.     

Computer aided geometric feasible assembly sequence planning and optimizing

Assembly sequence planning (ASP) is the foundation of the assembly process planning and design for assembly (DFA). In ASP, geometric feasibility is the prerequisite in the valid assembly sequences searching. The assembly precedence relations’ (APRs) deriving and fulfilling are the essential tasks in the geometric feasible assembly sequence planning. In this paper, a systematical approach called geometric constraint analysis (GCA) is proposed and the corresponding software system is developed and integrated with CAD system. Using this system, only with a few mouse clicks on CAD draft, assembly precedence relations (APRs) can be derived correctly and completely. Then, all the geometric feasible assembly sequences can be inferred out automatically. Moreover, an optimal algorithm is designed and realized in the GCA method, by which, the most optimal assembly sequence in terms of the operation convenience can be found out from the immense geometric feasible sequences. An erratum to this article can be found at     

Optimisation of operations sequence in CAPP using an ant colony algorithm

Computer-aided process planning (CAPP) forms an important interface between Computer-aided design (CAD) and Computer-aided manufacturing (CAM). It is concerned with determining the sequence of individual manufacturing operations required to produce a product as per technical specifications given in the part drawing. Any sequence of manufacturing operations that is generated in a process plan cannot be the best possible sequence every time in a changing production environment. As the complexity of the product increases, the number of feasible sequences increases exponentially, and there is a need to choose the best among them. This paper presents an application of a newly developed metaheuristic called the ant colony algorithm as a global search technique for the quick identification of the optimal operations sequence by considering various feasibility constrains. A couple of case studies are taken from the literature to comparing the results obtained by the proposed method.     

Computer-aided process planning for NC tool path generation of complex shoe molds

This paper presents a computer aided process planning (CAPP) system for numerical control tool path generation of complex shoe molds. This CAPP system includes both the automation of auxiliary boundary curve generation and machining strategies. The automation of auxiliary boundary curve generation and machining strategies make tool path generation more accurately and efficiently. Traditional shoe mold making is a very tedious process. Even with the utilization of computer-aided design and computer-aided manufacturing (CAD/CAM), the CAM process requires long hours of tool path programming and debugging. It would also take a long time to calculate (sometimes several hours) the tool path for complex athletic footwear. In order to reduce the tool path editing and programming time, this paper proposes the use of CAPP to reduce processing time and increase efficiency. It is difficult, if not impossible, to develop a generic CAPP system that can generate a process plan to solve general production problems. However, it is quite possible to capture the domain knowledge of a certain production process and embed that knowledge into a CAPP system. We prove, by using such a system, that a very complicated process planning problem can be overcome by a knowledge-based CAPP approach. With such an approach, the traditional manufacturing process of shoe molds can be converted to an automatic manufacturing process with the CAPP system. In fact, shoe molds for real production have been created using the developed CAPP system, demonstrating the effectiveness of this approach. In this paper, we show that several complex and different shoe molds and their machining strategies were automatically planned by the proposed CAPP system. The result of a comparison between the CAPP system with the traditional approach is presented and discussed.     

基于遗传算法的发动机箱体工艺路线优化

针对发动机箱体,提出了基于遗传算法和约束矩阵的工艺路线优化方法。通过对箱体特征的定义和分类,确定了特征加工的优先关系,自动生成了工艺规划的约束矩阵。在计算机辅助工艺过程设计（CAPP）平台中,定义了缸孔、瓦孔和通水孔等关键部件的加工工艺。按照提出的工艺路线优化方法,进一步优化了发动机箱体的工艺路线。     

产品装配顺序的层次化推理方法研究

提出一种装配优先关系分类模型，将装配顺序规划过程中的各种装配优先关系分为几种优先关系，确定性工艺优先关系和模糊性工艺优先关系3类。并在此基础上，提出层次化装配顺序推理方法，分别从装配顺序的几何可行性、工艺可行性和工艺优良性3个层次，对装配顺序进行递进推理，最终得到性能优良的装配顺序。开发的产品装配分析软件原型系统－－PAAS可以对复杂产品的装配顺序规划进行有效的分析和优化。     

Imperialist competitive algorithm for assembly sequence planning

Automated generation of all feasible assembly sequences for a given product is highly desirable in manufacturing industry. Many research studies in the past decades described efforts to find more efficient algorithms for assembly sequence planning. Imperialist competitive algorithm for assembly sequence planning is presented in this paper. Population individuals called countries are in two types: colonies and imperialists that all together form some empires. Each assembly sequence is encoded into the country. The proposed algorithm is tested and compared with genetic algorithm and particle swarm optimization. Results show that imperialist competitive algorithm can improve the quality in solution searching and upgrade the opportunity to find optimal or near-optimal solution for assembly sequence planning.     

基于自适应蚁群算法的工艺路线优化

针对计算机辅助工艺设计中最优方案选择,提出一种以制造资源更换率最低为目标的自适应蚁群优化方法(Adaptive ant colony algorithm,AACA)。通过分析零件特征,根据精度要求对制造特征进行分解,提出加工元概念。加工元被定义为特定的制造特征、加工阶段、加工方法、制造资源、装夹位置的集合,工艺路线的确定被转换为对加工元的优化顺序安排问题。以制造特征之间的几何位置约束,各加工阶段的先后顺序约束为基本元素,构造加工元优选约束矩阵,给出基于优选约束矩阵的加工元优选原则。在加工元优先顺序约束和可用制造资源的共同约束下,将缩短加工周期、提高加工质量和降低加工成本的综合目标表达为制造资源更换率最低,进行优化目标函数的数学建模。指出加工元优化排序可类比旅行商问题,并选择AACA进行优化求解。实例分析表明提出的方法可以可靠和有效地得到符合生产实际的工艺路线。     

对基于割集的拆卸序列求解算法的一种改进

基于割集的拆卸序列求解算法是拆卸序列自动规划的主要方法,基于割集的拆卸序列求解算法要解决的关键问题是组合复杂性问题。从降低算法的时间复杂度出发,在前人研究的基础上提出一种直接生成符合优先关系要求的割集的算法,减少了不必要的割集的生成,进一步降低了算法的时间复杂度。