Application of genetic algorithm to computer-aided process planning in preliminary and detailed planning

Computer-aided process planning (CAPP) is an important interface between computer-aided design (CAD) and computer-aided manufacturing (CAM) in the computer integrated manufacturing (CIM) environment. A good process plan of a part is built up based on two elements: (1) optimized sequence of the operations of the part; and (2) optimized selection of the machine, cutting tool and tool access direction (TAD) for each operation. On the other hand, two levels of planning in the process planning is suggested: (1) preliminary and (2) secondary and detailed planning. In this paper for the preliminary stage, the feasible sequences of operations are generated based on the analysis of constraints and using a genetic algorithm (GA). Then in the detailed planning stage, using a genetic algorithm again which prunes the initial feasible sequences, the optimized operations sequence and the optimized selection of the machine, cutting tool, and TAD for each operation are obtained. By applying the proposed GA in two levels of planning, the CAPP system can generate optimal or near-optimal process plans based on a selected criterion. A number of case studies are carried out to demonstrate the feasibility and robustness of the proposed algorithm. This algorithm performs well on all the test problems, exceeding or matching the solution quality of the results reported in the literature for most problems. The main contribution of this work is to emerge the preliminary and detailed planning, implementation of compulsive and additive constraints, optimization sequence of the operations of the part, and optimization selection of machine, cutting tool and TAD for each operation using the proposed GA, simultaneously.     

Intelligent Programming of CNC Turning Operations using Genetic Algorithm

CAD/CAM systems are nowadays tightly connected to ensure that CAD data can be used for optimal tool path determination and generation of CNC programs for machine tools. The aim of our research is the design of a computer-aided, intelligent and genetic algorithm(GA) based programming system for CNC cutting tools selection, tool sequences planning and optimisation of cutting conditions. The first step is geometrical feature recognition and classification. On the basis of recognised features the module for GA-based determination of technological data determine cutting tools, cutting parameters (according to work piece material and cutting tool material) and detailed tool sequence planning. Material, which will be removed, is split into several cuts, each consisting of a number of basic tool movements. In the next step, GA operations such as reproduction, crossover and mutation are applied. The process of GA-based optimisation runs in cycles in which new generations of individuals are created with increased average fitness of a population. During the evaluation of calculated results (generated NC programmes) several rules and constraints like rapid and cutting tool movement, collision, clamping and minimum machining time, which represent the fitness function, were taken into account. A case study was made for the turning operation of a rotational part. The results show that the GA-based programming has a higher efficiency. The total machining time was reduced by 16%. The demand for a high skilled worker on CAD/CAM systems and CNC machine tools was also reduced. Received: September 2004 / Accepted: September 2005     

Application of ant colony optimization algorithm in process planning optimization

One objective of process planning optimization is to cut down the total cost for machining process, and the ant colony optimization (ACO) algorithm is used for the optimization in this paper. Firstly, the process planning problem, considering the selection of machining resources, operations sequence optimization and the manufacturing constraints, is mapped to a weighted graph and is converted to a constraint-based traveling salesman problem. The operation sets for each manufacturing features are mapped to city groups, the costs for machining processes (including machine cost and tool cost) are converted to the weights of the cities; the costs for preparing processes (including machine changing, tool changing and set-up changing) are converted to the ‘distance’ between cities. Then, the mathematical model for process planning problem is constructed by considering the machining constraints and goal of optimization. The ACO algorithm has been employed to solve the proposed mathematical model. In order to ensure the feasibility of the process plans, the Constraint Matrix and State Matrix are used in this algorithm to show the state of the operations and the searching range of the candidate operations. Two prismatic parts are used to compare the ACO algorithm with tabu search, simulated annealing and genetic algorithm. The computing results show that the ACO algorithm performs well in process planning optimization than other three algorithms.     

A constraint-based operation sequencing for a knowledge-based process planning

Process planning is a decision-making process. Decisions on machining operations for a particular feature have to be made on various independent conditions such as which operation should be performed with which tools and under what cutting parameters. An integrated knowledge-based CAPP system called ProPlanner has been developed. The system has five modules namely information acquisition, feature recognition, machining operation planning and tool selection, set-up planning, and operation sequencing. Most process-planning systems do not produce alternative process plans. Usually, a fixed sequence created by a process plan is not necessarily the best possible sequence. Therefore, the aim should be to generate all possible operation sequences and use some optimality criteria to obtain the best sequence for the given operating environment. This paper presents an efficient heuristic algorithm, belongs to the system's operation sequencing module, for finding near-optimal operation sequences from all available process plans in a machining set-up. The costs of the various machining schemes are calculated and the machining scheme with the lowest cost is chosen. All feasible cutting tools are identified for each particular feature and the corresponding machining operations. This process is repeated for all the features in the machining set-up. All possible feature sequence combinations allowed by the current feature constraints are then generated. Appropriate cutting tools are identified and assigned to different operations. The feature sequence with the smallest number of tool changes is adopted.     

Process planning for Floor machining of 2½D pockets based on a morphed spiral tool path pattern

This work proposes a process planning for machining of a Floor which is the most prominent elemental machining feature in a 2½D pocket. Traditionally, the process planning of 2½D pocket machining is posed as stand-alone problem involving either tool selection, tool path generation or machining parameter selection, resulting in sub-optimal plans. For this reason, the tool path generation and feed selection is proposed to be integrated with an objective of minimizing machining time under realistic cutting force constraints for given pocket geometry and cutting tool. A morphed spiral tool path consisting of G¹ continuous biarc and arc spline is proposed as a possible tool path generation strategy with the capability of handling islands in pocket geometry. Proposed tool path enables a constant feed rate and consistent cutting force during machining in typical commercial CNC machine tool. The constant feed selection is based on the tool path and cutting tool geometries as well as dynamic characteristics of mechanical structure of the machine tool to ensure optimal machining performance. The proposed tool path strategy is compared with those generated by commercial CAM software. The calculated tool path length and measured dry machining time show considerable advantage of the proposed tool path. For optimal machining parameter selection, the feed per tooth is iteratively optimized with a pre-calibrated cutting force model, under a cutting force constraint to avoid tool rupture. The optimization result shows around 32% and 40% potential improvement in productivity with one and two feed rate strategies respectively.     

Process planning for Floor machining of 2½D pockets based on a morphed spiral tool path pattern

This work proposes a process planning for machining of a Floor which is the most prominent elemental machining feature in a 2½D pocket. Traditionally, the process planning of 2½D pocket machining is posed as stand-alone problem involving either tool selection, tool path generation or machining parameter selection, resulting in sub-optimal plans. For this reason, the tool path generation and feed selection is proposed to be integrated with an objective of minimizing machining time under realistic cutting force constraints for given pocket geometry and cutting tool. A morphed spiral tool path consisting of G¹ continuous biarc and arc spline is proposed as a possible tool path generation strategy with the capability of handling islands in pocket geometry. Proposed tool path enables a constant feed rate and consistent cutting force during machining in typical commercial CNC machine tool. The constant feed selection is based on the tool path and cutting tool geometries as well as dynamic characteristics of mechanical structure of the machine tool to ensure optimal machining performance. The proposed tool path strategy is compared with those generated by commercial CAM software. The calculated tool path length and measured dry machining time show considerable advantage of the proposed tool path. For optimal machining parameter selection, the feed per tooth is iteratively optimized with a pre-calibrated cutting force model, under a cutting force constraint to avoid tool rupture. The optimization result shows around 32% and 40% potential improvement in productivity with one and two feed rate strategies respectively.     

Using Hopfield neural networks for operational sequencing for prismatic parts on NC machines

A numerical control (NC) machine is accurate and expensive equipment that provides us with flexible and reliable operations. However, many process planners only use their instinct in planning operational sequencing and do not minimize non-cutting time. In this paper, the sequencing task is formulated as constrained optimization problems to generate efficient machining of a part for NC machines. Factors in this study include part and table orientations and feature grouping for same cutting tools. First, this proposed method finds the minimum part orientations to cover all part features in order to reduce the most time consuming setups. Then it finds the minimum table orientations needed based on the accessibility of parts features in each part orientation. Most importantly, the preliminary sequence is refined by including feature precedence relationship and feature clustering for tools and tool approaching directions that will reduce tool re-orientation and tool changing time. Due to potential conflicts of constraints for sequencing optimization from the imbedding of precedence relationships, the soft computing ability of neural networks must be utilized in this refining procedure. This paper models the problem that allows an analogy to be conducted between finding the best operation sequence and minimizing the energy function of a Hopfield neural network. Finally, a spindle cover is used as an example to illustrate the implementation of the proposed method.     

Drilling reconfigurable machine tool selection and process parameters optimization as a function of product demand

Special purpose machines (SPMs) are customized machine tools that perform specific machining operations in a variety of production contexts, including drilling-related operations. This research investigates the effect of optimal process parameters and SPM configuration on the machine tool selection problem versus product demand changes. A review of previous studies suggests that the application of optimization in the feasibility analysis stage of machine tool selection has received less attention by researchers. In this study, a simulated model using genetic algorithm is proposed to find the optimal process parameters and machine tool configuration. During the decision-making phase of machine tool selection, unit profit is targeted as high as possible and is given by the value of the following variables: SPM configuration selection, machining unit assignment to each operation group, and feed and cutting speed of all operations. The newly developed model generates any random chromosome characterized by feasible values for process parameters. Having shown how the problem is formulated, the research presents a case study which exemplifies the operation of the proposed model. The results show that the optimization results can provide critical information for making logical, accurate, and reliable decisions when selecting SPMs.     

DPP: An agent-based approach for distributed process planning

A changing shop floor environment characterized by larger variety of products in smaller batch sizes requires creating an intelligent and dynamic process planning system that is responsive and adaptive to the rapid adjustment of production capacity and functionality. In response to the requirement, this research proposes a new methodology of distributed process planning (DPP). The primary focus of this paper is on the architecture of the new process planning approach, using multi-agent negotiation and cooperation. The secondary focus is on the other supporting technologies such as machining feature-based planning and function block-based control. Different from traditional methods, the proposed approach uses two-level decision-making—supervisory planning and operation planning. The former focuses on product data analysis, machine selection, and machining sequence planning, while the latter considers the detailed working steps of the machining operations inside of each process plan and is accomplished by intelligent NC controllers. By the nature of decentralization, the DPP shows promise of improving system performance within the continually changing shop floor environment.     

Process planning optimization for parallel drilling of blind holes using a two phase genetic algorithm

Determining the optimal process parameters and machining sequence is essential in machining process planning since they significantly affect the cost, productivity, and quality of machining operations. Process planning optimization has been widely investigated in single-tool machining operations. However, for the research reported in process planning optimization of machining operations using multiple tools simultaneously, the literature is scarce. In this paper, a novel two phase genetic algorithm (GA) is proposed to optimize, in terms of minimum completion time, the process parameters and machining sequence for two-tool parallel drilling operations with multiple blind holes distributed in a pair of parallel faces and in multiple pairs of parallel faces. In the first phase, a GA is used to determine the process parameters (i.e., drill feed and spindle speed) and machining time for each hole subject to feed, spindle speed, thrust force, torque, power, and tool life constraints. The minimum machining time is the optimization criterion. In the second phase, the GA is used to determine the machining sequence subject to hole position constraints (i.e., the distribution of the hole locations on each face is fixed). The minimum operation completion time is the optimization criterion in this phase. Simulation results are presented to demonstrate the effectiveness of the proposed algorithm in solving the process planning optimization problem for parallel drilling of blind holes on multiple parallel faces. In order to evaluate the performance of proposed algorithm, the simulation results are compared to a methodology that utilizes the exhaustive method in the first phase and a sorting algorithm.     

Cooperation Requirements Planning (CRP) for multiprocessors: Optimal assignment and execution planning

Cooperation is considered an essential attribute of intelligent multi-machine systems. It enhances their flexibility and reliability. Cooperation Requirement Planning (CRP) is the process of generating a consistent and coordinated global execution plan for a set of tasks to be completed by a multi-machine system based on the task cooperation requirements and interactions. CRP is divided into two steps: CRP-I which matches the task requirements to machine and system capabilities to generate cooperation requirements. It also generates task precedence, machine operation, and system resource constraints. CRP-II uses the cooperation requirements and various constraints to generate a task assignment and coordinated and consistent global execution plan. The global execution plan specifies an ordered sequence of actions and the machine sets that execute them such that the assigned tasks are successfully completed, all the constraints are resolved, and the desired performance measure optimized.In this paper, we describe the CRP-II methodology based on the concepts of planning for multiple goals with interactions. Each task is considered to be a goal, and the CRP-I process is viewed as generating alternate plans and associated costs to accomplish each goal. Five different interactions are specified between the various plans: action combination, precedence relation, resource sharing, cooperative action, and independent action. The CRP-II process is viewed as selecting a plan to satisfy each goal and resolving the interactions between them. A planning strategy is proposed which performs plan selection and interaction resolution simultaneously using a best-first search process to generate the optimal global plan.     

Using genetic algorithms in process planning for job shop machining

This paper presents a novel computer-aided process planning model for machined parts to be made in a job shop manufacturing environment. The approach deals with process planning problems in a concurrent manner in generating the entire solution space by considering the multiple decision-making activities, i.e., operation selection, machine selection, setup selection, cutting tool selection, and operations sequencing, simultaneously. Genetic algorithms (GAs) were selected due to their flexible representation scheme. The developed GA is able to achieve a near-optimal process plan through specially designed crossover and mutation operators. Flexible criteria are provided for plan evaluation. This technique was implemented and its performance is illustrated in a case study. A space search method is used for comparison     

Dealing with feature interactions for prismatic parts in STEP-NC

Determining the precedence of machining features is a critical issue in feature-based process planning. It becomes more complex when geometric interaction occurs between machining features. STEP-NC, the extension of STEP (ISO 10303) standard developed for CNC controllers, is a feature-based data model. It represents all the geometric and topological product data minus feature interactions. In this paper, machining precedence of interactive and non-interactive STEP-NC features is discussed. Local and global precedence of machining features are defined on the basis of geometric constraints, such as geometric interaction of features and feature approach face and technological constraint such as access direction of the cutting tool. A software tool has been developed to visualize the STEP-NC part model and to generate the graphs of feature interaction and feature precedence. The output can be then used to augment the STEP-NC data in order to generate the optimal sequence of operations.     

An integrated intelligent process planning system (IIPPS) for machining

A key component of computer integrated manufacturing (CIM) is computer aided process planning (CAPP). Process planning in machining involves the determination of the cutting operations and sequences, the selection of machine tools and cutting tools, the calculation of machining parameters, and the generation of CNC part programs. Industrial structures in Norway are defined as small and medium-sized companies. The important fact is how well these companies use high technologies and resources in order to improve their production efficiency, product quality, and company competition in international markets. The concept of an integrated intelligent system (IIS) is created for this purpose. A prototype system, the integrated intelligent process planning system (IIPPS), is described for machining; it was developed on the basis of an IIS and constructed using three levels of effort: (1) AutoCAD, (2) dBASE III and (3) KnowledgePro. The system may be utilized not only by a process plann ing engineer in a company, but also by students of mechanical or industrial engineering.     

Optimization of multi-task turning operations under minimal tool waste consideration

Most of the literatures on machining economics problems tend to focus on single cutting operations. However, in reality most parts that need to be machined require more than one operation. In addition, machining technology has been developed to the point that a single computer numerical control (CNC) machine is capable of performing multiple operations, even simultaneously, employing multiple spindles and cutting tools. When several operations are performed on a CNC turning machine, various tools are required for the cutting operations. Determining the life of these cutting tools under different machining conditions is an arduous task for the operators. They usually replace the tools based on their experience or according to the specific cutting tool handbook. Frequent tool replacements may result in wasted tools and tool utilization, while infrequent tool replacements may result in poorly machined parts. In this study we propose a mathematical model in which several different turning operations (turning, drilling, and parting) with proper constraints are performed. The issue of tool replacement is taken into account in the proposed cutting model. In addition, an evolutionary strategy (ES)-based optimization approach is developed to optimize the cutting conditions of the multiple turning-related operations while taking into account the minimizing unit cost criteria under the economical tool replacement strategy.     

Block assembly planning in shipbuilding using case-based reasoning

A process planning system using case-based reasoning (CBR) is developed for block assembly in shipbuilding. A block assembly planning problem is modeled as a constraint satisfaction problem where the precedence relations between operations are considered constraints. In order to find similar cases, we propose two similarity coefficients for finding similar cases and for finding similar relations. Due to the limited number of operation types, the process planning system first matches the parts of the problem and those of the case-based on their roles in the assembly, and then it matches the relations related to the matched part–pairs. The parts involved in more operations are considered first. The process planning system is applied to simple examples for verification and comparison. An interface system is also developed for extracting information from CAD model, for preparing data for process planning, and for visually verifying the assembly sequence.     

Petri net techniques for process planning cost estimation

The problem under consideration is the cost estimation of operation sequencing for nonlinear process planning, i.e. taking into consideration processing alternatives. In order to determine overall costs for feasible process plans, we take into account in our Petri net model of manufacturing process planning the costs caused by machine, setup and tool changing in addition to the pure operation cost. We present two modelling and cost estimation techniques based on Petri nets. Both are based on a new Petri net model: the PP-net (Process Planning net) which represents manufacturing knowledge in the form of precedence constraints and incorporates the cost of machining operation in each operation transition. The first method is based on building a complex Petri net called PPC-system (Process Planning Cost system) by integrating the PP-net and separate Petri nets describing the costs of machine, setup and tool changing. The second method proceeds in the cost calculation by attaching a specific data structure to each PP-net transition which describes the associated machine, setup and tool for the operation modelled by that transition. We apply the developed methods and calculate the optimum process plan to an industrial case study of a mechanical workpiece of moderate complexity.     

A unified aggregation and relaxation approach for stress-constrained topology optimization

In this paper, we propose a unified aggregation and relaxation approach for topology optimization with stress constraints. Following this approach, we first reformulate the original optimization problem with a design-dependent set of constraints into an equivalent optimization problem with a fixed design-independent set of constraints. The next step is to perform constraint aggregation over the reformulated local constraints using a lower bound aggregation function. We demonstrate that this approach concurrently aggregates the constraints and relaxes the feasible domain, thereby making singular optima accessible. The main advantage is that no separate constraint relaxation techniques are necessary, which reduces the parameter dependence of the problem. Furthermore, there is a clear relationship between the original feasible domain and the perturbed feasible domain via this aggregation parameter.     

Pallet operation sequencing based on network part program logic

CAPP systems play a relevant role in aiding planners during setup planning, operation sequencing and pallet configuration activities. The support and automation granted by these techniques, together with the use of non-linear process planning logic, lead to a reduction in the planning time and costs, thus making manufacturers more competitive. This paper presents an approach that integrating process and production planning leads to the definition at the shop-floor level of the optimal operation sequence to machine all of the workpieces on a pallet using a four-axis machine tool. Part programs of non-production movements for each possible sequence of two operations are automatically generated at the shop-floor level and are simulated to obtain the non-production time. The complete sequence of operations is then defined on the basis of the minimisation of the estimated non-production time. This minimisation is performed using a mathematical model that defines a good sequence of operations. Four algorithms are adopted to analyse the proposed solution and to reduce the gap from optimality. The approach is tested on some cases taken from literature and on a real case. The real case was provided by a company that produces mechanical components. The obtained results underline a reduction on production and planning time, and consequently an increment in the company profit.     

蚁群算法求解带约束火焰切割路径优化问题

火焰切割路径优化的主要目的是控制切割路径不当引起的热变形误差并对路径长度寻优。通过零件位置关系动态定义切割过程中的可选打孔点集合,将热变形约束条件量化;引入虚拟结点并定义距离矩阵,将路径规划转化为动态描述的TSP问题;基于蚁群算法提出约束条件下增大解空间的方法和信息素更新策略。实验结果表明,改进后的蚁群算法能够有效控制问题的规模并且得到更高质量的解,对热变形约束条件下的数控火焰切割路径优化有较好的效果和实用性。