**M. Houshmand**

Department of Industrial Engineering, Sharif University of Technology, Tehran, Iran

D.M. Imani

Department of Industrial Engineering, Sharif University of Technology, Tehran, Iran

Department of Industrial Engineering, Sharif University of Technology, Tehran, Iran

D.M. Imani

Department of Industrial Engineering, Sharif University of Technology, Tehran, Iran

Selection and development of machining features are the core activity in process planning. Usually the machining features development is done by experts according to elementary volumes. Performing this process by experts develops a limited machining features and the optimum solution may be missed. In this study a new method is developed to generate machining features and analyzes them to extract feasible features. The feasible solution is based on technical limitation of parts without any expert’s judgments. Also it uses a set covering optimization technique to extract optimum one. Finally, the numerical results are presented and performance of the proposed method is tested by some candidate parts.

PDF Abstract XML References Citation

M. Houshmand and D.M. Imani, 2009. A Volume Decomposition Model to Determine Machining Features for Prismatic Parts. *Journal of Applied Sciences, 9: 1703-1710.*

**DOI:** 10.3923/jas.2009.1703.1710

**URL:** https://scialert.net/abstract/?doi=jas.2009.1703.1710

**INTRODUCTION **

Process planning plays an important role in optimal development and operation of manufacturing systems. It determines the sequence of operations and resources needed to manufacture a part and generates a plan for parts to be manufactured. The plan should minimize the manufacturing cost and delay as well as maximizing the rate of production and quality (Chang, 1994). Through this process raw materials are converted to finished goods by removing material volumes so called delta volume. Delta volume is volume of material that must be removed from stock and it is difference between part and stock (Ciurana *et al.*, 2003; Dereli and Filiz, 1999).

In last decade lots of efforts have been devoted to apply computer integrated manufacturing systems. Automation of process planning has been a major objective of researchers in this field. Till today, the work to generate machine and tool sequence for part machining is still done manually and is experience-based activity (Mascle *et al*., 2007; Alan *et al.*, 1998).

Process planning activities require a variety of human capability. These people called process planner (Kueng and Yuen, 2003). However, there are a few people who have enough experience to do process planning and even for single part they may develop different process plans.

Computer Aided Process Planning (CAPP) is seen as a communication agent between CAD and CAM. As a widely accepted idea, CAPP has to interpret the part in terms of features to play its role in domain of computer integrated manufacturing. Feature recognition is considered as a front-end to CAPP and plays a key role in CAD/CAM integration (Han *et al*., 2000). It is the process of converting CAD data of a part into a model of the machining activities that required producing the part. Many approaches are reported for feature recognition in literature such as hint-based approaches, graph-based approaches, knowledge-based approaches, volumetric decomposition approaches and other hybrid approaches.

Hint-based approaches are more successful in recognizing interacting features than the other existing approaches (Han *et al*., 1998; Ji *et al*., 1995). But they also have some shortcomings (Rahmani and Arezoo, 2007). As it is known that the principle of hint-based methods is to match traces left by the motion of a milling cutter with predefined features. A feature library does not include all tool traces and for some complex features it is difficult to find suitable traces (Mascle *et al*., 2007).

The graph pattern matching approach was first formalized by Joshi and Chang (1988). Techniques based on the graph matching algorithms have been used in many subsequent research efforts and recently incorporated into commercial process planning software. A main problem with the graph matching pattern matching approach is its difficulty to recognize intersecting features. While quite successful in recognizing isolated features, this approach reveals many difficulties when the face patterns of the part are altered due to feature interactions.

Volumetric decomposition approaches include convex-hull decomposition approaches (Ji *et al*., 1995; Kim and Wang, 2002) and cell-based decomposition approaches (Sakurai, 1995; Woo and Sakurai, 2002; Sridharan and Shah, 2004). Cell-based decomposition approaches decompose the delta volume of a part in to cells by extending the faces beyond its concave edges and then combining the cells in to volumes. Different combinations of cells results different features. Sakurai and Dave (1996) proposed to combine cells in to volumes called maximal volumes. They showed that multiple feature interpretations can be generated systematically. Also, they suggested that near optimal feature interpretation could be generated by sequencing the maximal volumes for machining using some machining rules. The maximal volume decomposition method (Sakurai and Dave, 1996) consists of two steps: decomposing of delta volume into cells and merging the cells into maximal volumes. The step of merging cells had the worst-case computational complexity (Woo and Sakurai, 2002). Various techniques were adopted to ease the combinatorial complexity. Yet the method still suffers from the combinatorial explosion for a delta volume that was decomposed into a large number of cells.

In this research, a new heuristic model is proposed to determine machining features as a phase of process planning procedure. To facilitate automation of process planning and solve combinatorial complexity of merging elementary volumes, the modified combination method (MCM) is adopted to develop MVs. Also it reduces efforts and time required by experts as well as consideration of all elementary volumes. It analyzes the feasibility of each machining feature (manufacturability and tool accessibility) by using dependency matrix. It thus makes a contribution for automation of process planning.

**PROBLEM DEFINITION**

The word feature signifies different meaning in different contexts depending on the specific domain. For example, in design it refers to a web or a notch section, while in manufacturing it refers to slots, holes and pockets, while in inspection it is used as a datum or reference on the part.

To develop a feasible process plan it requires interpreting part design data; selection of the manufacturing processes, machines, tools and fixtures; decomposition of the material volume (delta volume) to be removed; selection of machining features, generation of precedence constraints and sequencing machining features. Determination of Machining Features (MF) is critical activity in process planning. In the process of MF determination, one must develop candidate MF, where considering Elementary Volumes (EV) and technical constraints.

A machining feature is defined as a volume of material or a set of part faces that a process planner would consider machining with the same operation (Sridharan and Shah, 2004). Manufacturing features and machining features refer to different entity of a part. Manufacturing features are extracted from CAD data and refers to finished part features (Abouel and Kamrani, 2006), whereas, Machining features are referred to features that must be removed from stock to create finished part that include manufacturing features.

Part modeling and generation of elementary manufacturing features (elementary volumes or cells) are considered in past researches. To obtain final form of part that determined (usually by design engineer) in an engineering drawing, the delta volume (volume V in Fig. 1 ) must be removed from stock. This volume can be decomposed into volumes v_{1}, v_{2}, v_{3}, v_{4} and v_{5} (shown in Fig. 2) through drawing planes adjacent to all surface of the part. Solving the multi pass machining model results in one or more tool passes. It might be also viewed as generating additional planes such as p_{1} (shown in Fig. 3) for the volume to be removed. The planes decompose the volumes of v_{1}, v_{2}, v_{3}, v_{4} and v_{5} in to elementary volumes such as e_{1}, e_{2}, e_{3}, e_{4}, e_{5}, e_{6}, e_{7} and e_{8} (shown in Fig. 3). Finally machinable volumes must be developed through merging elementary volumes as canidate MVs that can generate various interpretations.

Cost of machined part can be defined as the summation of material costs, setup costs, tooling costs and operation costs (Lin *et al*., 1998). Material costs depend upon the cost of stock being used.

Fig. 1: | Volume V and part P |

Fig. 2: | Decomposition of delta volume V into v_{1}, v_{2}, v_{3}, v_{4} and v_{5} |

Fig. 3: | Segmentation of v_{1}, v_{2}, v_{3}, v_{4} and v_{5} into e_{1}, e_{2}, e_{3}, e_{4}, e_{5}, e_{6}, e_{7} and e_{8} |

Set up costs depend on how many setups are needed and fixturing methods used in each setup. Therefore, setup costs depend on how features are oriented in space and how they interact with each other. Tooling costs depends on tools being used. Therefore, tooling cost depends on machining feature types.

Operation costs depend on the time taken to machine various features and it depends on feature types, dimensions and tolerances.

Total manufacturing cost components are tool change cost, set-up cost, transportation cost, part batch size and machining costs (Han *et al*., 2001; Khoshnevis* et al*., 1999). Part handling includes loading (setup) and unloading of a part. For the case of manufacturing a particular part, costs for batch setup, part unloading and tooling are approximately constant. Machining cost can subdivide into costs for roughing and finishing.

Kusiak proposed an optimization model for machining features, tools and fixtures selection (Kusiak, 2000). The objective function of the model is:

(1) |

where, c_{j} is the cost of jth machining feature, p_{t} is the cost of using tth tool and k_{f} is the cost of using fth fixture. J is defined as set of all elementary machining features of the part, T is defined as set of available tools for machining the part and F is defined as set of available fixtures. There are upper limits of available tools and fixtures number in model. X_{j}, Y_{t} and Z_{f} are MFS selection, tool selection and fixture selection variables. They are zero/one decision variables. Constraints of the model are: removal all of elementary volumes, tools availability and fixture availability and zero/one constraints. Considering manufacturing environment, some constraints may be added or removed from the model.

In the knowledge based approach, models based on set covering technique is used to select optimal combination of machining features (Kusiak, 2000). The objective function of set covering model is:

(2) |

The important issue in any optimization models used for machining features selection is dependency of the model to machining feature development activities. The higher feasible machining feature developed, the better solution is achieved. Each machining feature is a set of elementary volumes to be removed. Therefore in the process of machining feature development, following criteria should be considered:

• | Feasibility of solution |

• | Cost minimization |

• | Removal of all elementary volumes |

• | Computational time |

**PROPOSED MODEL **

There are some limitations where candidates MFs are generated manually. There are: (i) limited number of generated feasible MFs that may result missing optimal solution, (ii) limited number of available experts and (iii) a time consuming activity. Considering that the quality of solution is depends on candidate MFs, a computer based solution to generate MFs is required. In this research, a new method is developed and coded to automate generation, assessment and selection processes of MFs. It determines machining features that must be machined and removed from stock to obtain the finished part. These processes are performed by using (i) modified combination procedure to generate Mfs, (ii) a rule-based assessment procedure to eliminate infeasible MFs and (iii) a set covering model with modified cost function to select the best combination of MFs.

The other feature of proposed model is that the user may reject selected MFs. In this case the model resolves the problem and generates another solution.

The general structure of the model is shown in Fig. 4.

**GENERATION OF MACHINING FEATURES ALTERNATIVES**

In the first step of Machining Feature Determination Problem (MFDP), candidate MFs should be generated systematically. The machining features are a set of elementary volumes. Thus In this step a combination procedure is used to generate canidate MFs.

Fig. 4: | General structure of the proposed model |

In general, the number of r combination from n elements is defined as:

(3) |

Where: r ≤ n

If n is defined as the number of EVs and r is defined as positive integer number, the C_{n}^{r} will present the number of MFs that are included in r EVs.

The various combinations of EVs should be considered in Machining Feature Determination Problem (MFDP). Thus the total number of all combination in MFDP is:

Total number of combinations (MFs) in MFDP = C _{n}^{1} + C_{n}^{2} +...+ C_{n}^{r} + C_{n}^{n} | (4) |

In large and complex MFDP, the numbers of all combinations that must be generated by the model will increase highly. Therefore, the computation time increases and its performance decrease. In order to improve method performance where a large and complex MFDP is considered, two modification rules are used in combination procedure. These two verification rules are:

**Rule 1:** According to MF definition, the maximum numbers of EVs that may generate candidate MFs is limited by technical constraint. The maximum number of EVs is defined by m where, m ≤ n. Therefore the combination procedure in the proposed method shouldn’t generate MFs having more than m EVs. Total number of MFs required to be generated through combination procedure is:

Total number of required MFs = C _{n}^{1} + C_{n}^{2}+...+ C_{n}^{m} | (5) |

Where: m ≤ n

This modification rule decreases highly the method computation time and increases model performance in large and complex MFDP.

**Rule 2:** Most of generated MFs by the model through combination procedure aren’t feasible. Feasible MFs are features that manufacturing systems can process them with existing technologies in a single set up. Thus the combination procedure should not generate MFs that are certainty infeasible. A rule-based expert system is embedded in the combination procedure recognizes in feasible MFs and will not let generation of them.

Based on two modification rules, the combination procedure generates MFs and constructs primary machining feature set (PMFS). The combination procedure with two modification rules is called modified combination procedure in this research.

**RULE-BASED ASSESSMENT PROCEDURE **

Lots of generated MFs through modified combination procedure may be infeasible because of technical constraints. Thus the model should assess the generated MFs and eliminate infeasible ones. This process is performed based on elementary volumes positions and technical dependency among them (machinability and accessibility).

Technical dependencies are defined by experts or knowledge-based approaches. Adjacency graph is used sto present dependency relationships among EVs. The nodes present EVs as defined by e’s and arcs present dependency relationships. Dependency information is defined as an attribute of EVs and determined by experts or knowledge based system in upstream phases. There are three states in dependency relationship. They are 0, 1 and S. If relationship between two elementary volumes for example e1 and e9 in Fig. 5 is zero, these elementary volumes can not make a feasible machining feature. If relationship between two elementary volumes for example e1 and e2 is one, these elementary volumes can make a feasible machining feature. If relationship between two elementary volumes for example e3 and e9 is S, They may make a feasible machining feature if a specific set of other EVs such as Ω (e3, e9) = (e7) exists in the current machining feature.

Fig. 5: | Part P with nine elementary volumes |

Fig. 6: | An example of part dependencies among elementary volumes in adjacency graph |

Thus feasibility of MV depends on sets of EVs that generate MF. If there are EVs with zero relation in MF, the MF will be infeasible. If there are EVs with S relation in a MF, it is feasible where Ω = (e_{i}, e_{k}) exists in the MF.

Part P is shown in Fig. 5 includes nine elementary volumes. Adjacency graph is depicted to represent dependency relationship among elementary volumes. Figure 6 shows a part of adjacency graph that is depicted for part P.

Dependency matrix may be obtained from adjacency graph. This matrix defines as D matrix and is symmetric. The D matrix for part P is shown in Fig. 7.

Assessment procedure to identify feasible MFs is designed and implemented in the model based on dependency relations. It is rule based procedure. Therefore D matrix is extracted and assessment procedure recognizes infeasible MFs and eliminates them from PMFS. After removing infeasible MFs from PMFS, candidate MFs set (CMFS) is obtained.

Fig. 7: | Dependency matrix |

**DETERMINE OPTIMAL MACHINING FEATURES**

The set covering model as an optimization model is used to select optimal combination of MFs from CMFS. Before the set covering model is presented, the following notation needs to be defined:

I | = | Set of all elementary volumes (elementary machining features) of the part |

J | = | Set of all candidate MFs |

selected, |

The set covering general model is:

(6) |

(7) |

(8) |

Equation 6 is objective function that minimizes the total removal cost. Equation 7 ensures that all EVs are removed from stock and is cover constraint. Equation 8 is zero/one constraint.

To calculate MFs removal cost (C_{j}), the model calculates MF volume as the sum of related EVs. If C is defined as the cost of unit volume removal and V_{j} is defined as volume of MF_{j}, the cost for each MF_{j} that defined as c_{j}, is calculated by following equation:

C _{j} = C* V_{j} | (9) |

Other cost elements such as setup cost are not considered in Eq. 9 and the total cost of process planning optimization in downstream phases such as sequencing phase may be increased. Thus the proposed method should use modified cost function in the optimal selection step. Modified Cost Function (MCF) is defined as:

(10) |

where, C_{j} obtained from Eq. 9. γ is defined as modified factor that is calculated from following equation:

(11) |

where, 0.1 ≤ Γ ≤ 0.4 and is defined as penalty factor that depends on part complexity so that wherever part complexity enhances, the Γ value will increase. μ is the number of CMFS elements.

Thus the proposed model is used set covering model with modified cost function Eq. 10. Modified cost function reduces the number of MFs in optimal selection step as possible. The set covering model with modified cost is called modified set covering model in this research.

The set covering model is constructed and solved as a final step of proposed method. The MFs are selected from CMFS by using this step. The software of proposed method has been implemented on a Pentium system in MATLAB7. The performance of proposed model is assessed through solving candidate parts.

**NUMERICAL RESULTS**

In order to assess the model performance, some candidate MF problems (for example part p1 and p2 Shown in Fig. 8 and 10 are solved by the proposed method. Basic data and the results given by the model are depicted in Fig. 9 and 11.

Solution time, Technical feasibility of selected MFs (SMF) and removal cost are important measure of method performance. It should be noted that the maximum number of EVs in a MF, m plays important role in modified combination procedure.

That means as m reduces, the computation time and costs will also reduce. To analyse the impact of m, part P1 is solved with varying m values from 2 to 10 without changing other parameters. The results are shown in Table 1.

As shown in Fig. 12 when parameter m is increased, the number of generated MFs is increased highly.

Fig. 8: | Part p1 |

Fig. 9: | Solution result for part p1 |

Fig. 10: | Part p2 |

Fig. 11: | Solution result for part p2 |

It reduces the model performance for complex parts with high elementary volumes (EVs).

Figure 13 shows the effect of increasing m on numbers of feasible MFs. It shows that the number of feasible MFs increases proportionally when m increases. It remains nearly constant when m reaches a specific value.

Table 1: | Analysis proposed method performance against m for part P1 |

Fig. 12: | Generated MFs against m |

Fig. 13: | Feasile MFs against m |

Fig. 14: | Solution costs against changes of parameter m |

Considering results of proposed model for different parts, it showed that where m > [n/2], the number of feasible MFs remains nearly constant.

Figure 14 shows the effect of m on modified cost function in the modified set covering model. Cost is decreased when m is increased. Results also show where m > [n/2], reduction of cost is observed rarely.

Fig. 15: | Solution time against of parameter m |

The results also show when m is increased, solution time of model increases (Fig. 15). This effect is happen because of increasing generated MFs.

Machining feature determination phase is very important in process planning. Usually machining features development is done by experts manually according to elementary volumes. There is some limitation in generation of candidate MFs manually, such as (i) limited number of generated feasible MFs that may result missing optimal solution, (ii) limitation in number of available experts and (iii) a time consuming activity. The quality of solution depends on candidate MFs. Therefore a computer based solution to generate MFs is required. Feature recognition technique such as decomposition methods still suffered from the combinatorial explosion for a delta volume that was decomposed into a large number of cells. In this paper, a new method is developed so that automates generation, assessment and selection process in MFDP for prismatic parts. The proposed method can generate primary machining feature set through modified combination procedure, assess and eliminate infeasible MFs through rule-based assessment-procedure and select optimal MFs through modified set covering model. Also it can generate other solutions that are interested by users.

The proposed method has good performance in machining feature determination problem and has shown a good performance in solution time and costs. Therefore the proposed model has advantages such as (i) decreasing expert’s role in MFDP, (ii) obtaining optimal solution, (iii) decreasing solution cost and time (iv)automation of process planning.

- Nasr, E.S.A. and Ali K. Kamrani, 2006. A new methodology for extracting manufacturing features from CAD systems. Comput. Ind. Eng., 51: 389-415.

Direct Link - Chang, P.C., 1994. A practical approach for parts scheduling with alternative process plans in automated manufacturing systems. Comput. Math. Applic., 28: 55-65.

CrossRefDirect Link - Ciurana, J., M.L. Garcia, R. Castero and M. Alberti, 2003. A system based on machined volumes to reduce the number of route sheets in process planning. Comput. Ind., 51: 41-50.

Direct Link - Dereli, T. and I.H. Filiz, 1999. Optimization of process planning functions by genetic algorithms. Comput. Ind. Eng., 36: 281-308.

CrossRef - Han, J.H., W.C. Regli and S. Brooks, 1998. Hint-based reasoning for feature recognition: Status report. Comput. Aided Des., 30: 1003-1007.

CrossRef - Han, J.H., M. Pratt and W.C. Regli, 2000. Manufacturing feature recognition from solid models: A status report. IEEE Trans. Robotics Automat., 16: 782-796.

CrossRefDirect Link - Han, J.H., M. Kang and H. Choi, 2001. STEP-based feature recognition for manufacturing cost optimization. Comput. Aided Des., 33: 671-686.

Direct Link - Ji, Q., M.M. Marefat and P.J. Lever, 1995. An evidential reasoning approach for recognizing shape features. Proceedings of the 11th Conference on Artificial Intelligence for Applications, February 20-23, 1995, IEEE Computer Society, USA., pp: 162-168.

Direct Link - Joshi, S. and T.C. Chang, 1988. Graph based heuristics for recognition of machined features from a 3-D solid model. Comput. Aided Des., 20: 58-66.

CrossRefDirect Link - Khoshnevis, B., D.N. Sormaz and J.Y. Park, 1999. An integrated process planning system using feature reasoning and space search-based optimization. IIE Trans., 31: 597-616.

Direct Link - Kim, Y.S. and E. Wang, 2002. Recognition of machining features for cast then machined parts. Comput. Aided Des., 34: 71-87.

CrossRefDirect Link - Kueng, K.W. and D. Yuen, 2003. An intelligent hierarchical work station control model. J. Mater. Process. Technol., 139: 134-139.

CrossRefDirect Link - Alan, C.L., L. Shou-Yee, D. Diganta and F.L. Wen, 1998. An integrated approach to determining the sequence of machining operations for prismatic parts with interacting features. J. Mater. Process. Technol., 73: 234-250.

CrossRefDirect Link - Mascle, C., H. Lu and R. Maranzana, 2007. Machining process planning using decomposition of delta volume. Proceedings of the International Symposium on Assembly and Manufacturing, July 22-25, 2007, IEEE Xplore London, pp: 106-111.

CrossRefDirect Link - Rahmani, K. and B. Arezoo, 2007. A hybrid hint-based and graph-based framework for recognition of interacting milling features. Comput. Ind., 58: 304-312.

CrossRefDirect Link - Sakurai, H., 1995. Volume decomposition and feature recognition: Part I-polyhedral objects. Comput. Aided Des., 27: 833-843.

CrossRefDirect Link - Sakurai, H. and P. Dave, 1996. Volume decomposition and feature recognition: Part II- curved objects. Comput. Aided Des., 28: 519-537.

CrossRef - Sridharan, N. and J.J. Shah, 2004. Recognition of multi axis milling features: Part I-topological and geometric characteristics. J. Comput. Inform. Sci. Eng., 4: 242-250.

CrossRefDirect Link - Woo, Y. and H. Sakurai, 2002. Recognition of maximal features by volume decomposition. Comput. Aided Des., 34: 195-207.

Direct Link