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 experiencebased 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 frontend 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 hintbased approaches, graphbased
approaches, knowledgebased approaches, volumetric decomposition approaches
and other hybrid approaches.
Hintbased 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 hintbased 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 convexhull decomposition approaches
(Ji et al., 1995; Kim and Wang,
2002) and cellbased decomposition approaches (Sakurai,
1995; Woo and Sakurai, 2002; Sridharan
and Shah, 2004). Cellbased 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 worstcase 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, setup 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:
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:
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 rulebased 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:
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 rulebased 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.
RULEBASED 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 knowledgebased 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:
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:
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:
where, C_{j} obtained from Eq. 9. γ is
defined as modified factor that is calculated from following equation:
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. 9: 
Solution result for part p1 

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.
CONCLUSION
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 rulebased assessmentprocedure 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.