Reducing search space of optimization algorithms for determination of machining sequences by consolidating decisive agents

Abstract

One of the main objectives of computer-aided process planning is to determine the optimum machining sequences and setups. Among the different methods to implement this task, it can be named the constrained optimization algorithms. The immediate drawback of these algorithms is usually a large space needed to be searched for the solution. This can easily hinder the convergence of the solution and increase the possibility of getting trapped in the local minima. A novel approach has been developed in this work with the objective of reducing the search space. It is based on consolidating the decisive factors influencing the consecutive features. This helps prevent creation of sequences which need the change of setup, machine tool, and cutting tool. The proposed method has been applied to three different optimization methods, including genetic, particle swarm, and simulated annealing algorithms. It is shown that these algorithms with reduced search spaces outperform those reported in the literature, with respect to the convergence rate. The best results are found in the genetic algorithm from the viewpoint of the obtained solution and the convergence rate. The worst results belong to the particle swarm algorithm in connection with the strategy of generating new solutions.

Introduction

Determination of feature machining sequences (FMSs), operation sequencing, and setup planning are vital steps in computer-aided process planning (CAPP) systems. The initial information for setup planning and FMS determination includes the workpiece machining features, tool access directions (TADs), machining rules, and candidate machine and cutting tools. To specify the operation sequences, candidate operations for machining each feature should also be determined.^1,2

The methods for FMS or operation machining sequence (OMS) and setup determination by the researchers are divided into two general categories. In the first category, the researchers introduce novel concepts, such as the enriched machining feature (EMF)^3,4 and employ analytical approaches, such as the graph theory^5,6 and permutation method,^7–9 for setup and FMS determination. In the second category, the researchers assume the setup planning and FMS determination as a constrained optimization problem which can be solved by heuristic algorithms, such as the genetic algorithm (GA), particle swarm optimization (PSO), simulated annealing (SA), and ant colony (AC).

Salehi and Bahreininejad ¹⁰ used GA for FMS optimization. They employed the operation precedence graph (OPG) to generate the initial population and used the ordered crossover. They do not change the manufacturing resources (MRs). It should be noted that the machine tools, cutting tools, and TADs are loosely denoted by MRs. Huang et al. ¹¹ employed the GA and OPG techniques for FMS determination. Su et al. ¹² used GA with a modified technique for the generation of initial population. They proved the inadequacy of previous methods in the generation of initial population; then, they proposed a novel technique. Chen et al. ¹³ combined a Hopfield network with SA for setup and FMS determination and sequence energy calculation. They used the penalty method to apply the machining rules. Ma et al. ¹⁴ also employed SA algorithm. Their algorithm starts with a feasible sequence. The new operation sequence is acceptable provided that it follows the machining rules. Guo et al. ¹⁵ determined the OMS using the PSO algorithm. They employed the crossover, adjacent swapping, and the MR shifting to escape the local minima. Kafashi et al. ¹⁶ also used the PSO for setup planning. They generated various sequences by PSO and determined the setups by changing the TAD in sequential operations. Miljković and Petrović ¹⁷ applied PSO for process planning. They considered several alternative operations for a single feature. Krishna and Rao ¹⁸ used the AC optimization algorithm for FMS determination. They, however, excluded the machine and cutting tools in their work. Liu et al. ¹⁹ considered one operation with several MRs. Then, the AC algorithm was used for OMS determination. Hu et al. ²⁰ also employed the AC algorithm for OMS optimization. They considered the machining rules and moved the ants by the OPG. Wang et al. ²¹ considered the MRs as in Liu et al. ¹⁹ Other researchers employed algorithms, such as the tabu search (TS) and bat algorithm (BA) for similar purposes.^22,23

Search space reduction leads to faster optimization algorithms and less possibility of getting trapped into the local minima. In this work, a novel approach is proposed for considering the MRs. The proposed approach is implemented for GA, PSO, and SA algorithms. This approach is based on MR intersection (MRs are assumed as mathematical sets) to avoid unnecessary assessments. This leads to decreased costs and less endeavor for setup planning during the optimization process. In this article, analytical formulation has been developed to manipulate the commonly used cost function.

Manufacturing information for FMS and setup determination

In this article, the approach proposed by Manafi et al. ²⁴ is employed to specify the TAD. The machining features are identified using the graph-based method. The technological rules (TRs) and geometrical rules (GRs) considered in this work are as follows: ⁹

• $\mathrm{T}{\mathrm{R}}_1$ : If the locating/clamping surface required for the feature ${\mathrm{F}}_1$ is removed as the feature ${\mathrm{F}}_2$ is machined, then the feature ${\mathrm{F}}_1$ should be machined before ${\mathrm{F}}_2$ .

• $\mathrm{T}{\mathrm{R}}_2$ : If the surface necessary for positioning the cutting tool of feature ${\mathrm{F}}_1$ is eliminated by machining the feature ${\mathrm{F}}_2$ , then ${\mathrm{F}}_1$ machining is prior to ${\mathrm{F}}_2$ machining.

• $\mathrm{T}{\mathrm{R}}_3$ : If some surfaces of the feature ${\mathrm{F}}_1$ are the reference surfaces for the feature ${\mathrm{F}}_2$ , then ${\mathrm{F}}_1$ machining has priority to ${\mathrm{F}}_2$ machining.

• $\mathrm{T}{\mathrm{R}}_4$ : Assume the feature ${\mathrm{F}}_1$ is machined. If this leads to larger deformations of the workpiece while the feature ${\mathrm{F}}_2$ is being machined, then ${\mathrm{F}}_2$ should be machined before ${\mathrm{F}}_1$ .

• $\mathrm{T}{\mathrm{R}}_5$ : If two features produce burr in each other while being machined and the burr removal of feature ${\mathrm{F}}_1$ is more challenging than feature ${\mathrm{F}}_2$ , then ${\mathrm{F}}_1$ machining is prior to ${\mathrm{F}}_2$ machining.

• $\mathrm{G}{\mathrm{R}}_1$ : If the features ${\mathrm{F}}_1$ and ${\mathrm{F}}_2$ have geometrical surface interference and ${\mathrm{F}}_1$ is the base feature, then ${\mathrm{F}}_2$ is machined after ${\mathrm{F}}_1$ .

• $\mathrm{G}{\mathrm{R}}_2$ : If the features ${\mathrm{F}}_1$ and ${\mathrm{F}}_2$ have volumetric interference and the number of constituting surfaces of feature (NCSF) of ${\mathrm{F}}_1$ is larger than its standard NCSF, then ${\mathrm{F}}_1$ is machined before ${\mathrm{F}}_2$ .

This work benefits from the feature precedence matrix (FPM) representation ²⁵ which is suitable for both computer systems and process planners.

In this work, it is assumed that only one machining operation is required for each feature. Hence, the ith operation is specific to machining the ith feature; therefore, the word “feature” is completely representative of “operation” and is used in the rest of this article. The candidate cutting tools and machine tools are specified by the process planner.

FMS and setup determination by the optimization algorithms

In optimization algorithms, one or a set of FMSs are randomly produced such that the machining rules are followed. Then, the MRs of each feature are randomly selected among the candidate MRs. The optimization algorithm then iteratively enhances these solutions.

A suitable cost function (C) is defined with the aim of minimizing the manufacturing costs

$$\begin{array}{c}\multicolumn{1}{c}{C=C_{\mathrm{MT}}+C_{\mathrm{CT}}+n_{\mathrm{MTC}}\times C_{\mathrm{MTC}}+n_{\mathrm{CTC}}}\\ \multicolumn{1}{c}{\times C_{\mathrm{CTC}}+n_{\mathrm{SC}}\times C_{\mathrm{SC}}}\end{array}$$

(1)

where $C_{\mathrm{MT}}$ denotes the total costs of the machine tools, $C_{\mathrm{CT}}$ represents the total cutting tool cost, $n_{\mathrm{MTC}}$ is the number of machine tool changes, $C_{\mathrm{MTC}}$ is the cost of machine tool change, $n_{\mathrm{CTC}}$ denotes the number of cutting tool changes, $C_{\mathrm{CTC}}$ is the cost of cutting tool change, $n_{\mathrm{SC}}$ designates the number of setup changes, and $C_{\mathrm{SC}}$ is the cost for each setup change.

GA

The GA generates the FMS solutions according to the following procedure:

• Step 1. Get the workpiece manufacturing information such as the features and TADs.

• Step 2. Get the GA parameters such as the main population, crossover $(P_{\mathrm{C}})$ , and the mutation probability $(P_{\mathrm{M}})$ .

• Step 3. Generate random solutions for the main population; then, evaluate and save the solutions as the main population.

• Step 4. Do the following steps:

• Step 4.2. Apply the mutation on the generated children and assess the results (based on the mutation probability).

• Step 4.3. Add the results to the main population.

• Step 4.4. Separate some members of the resulting population such that a new main population as large as the initial main population (Step 2) is created.

• Step 4.5. End the algorithm if the convergence condition is satisfied; otherwise, go to Step 4.1 and follow the procedure.

The manner by which the initial random population is generated, the way the crossover and mutation are applied, and the parents and the next generation are selected considerably affects the GA. Based on the literature, the method proposed by Su et al. ¹² for the generation of the random main population and the tournament selection^10–12 is superior to other methods. Crossover and mutation are employed to generate new solutions. In crossover, only the FMS varies and the MRs are assumed unchanged. The preferred crossover technique, namely the ordered crossover, has been proposed by Lee et al. ¹ The preferred MR change technique has been proposed by Su et al. ¹²

Modified particle swarm optimization

The procedure by which PSO determines the FMS is as follows:

• Step 1. Get the manufacturing information of the workpiece such as the features and TADs.

• Step 2. Get the PSO parameters such as the number of particles, crossover probability, mutation probability, and adjacent swapping parameters.

• Step 3. Assign and assess the initial random position and velocity of the particles.

• Step 4. Do the following steps:

• Step 4.2. Calculate and evaluate the new positions of the particles (new solutions).

• Step 4.3. Change and assess the position and velocity of the particles by crossover (based on the crossover probability).

• Step 4.4. Change and assess the particles’ MR by mutation (based on the mutation probability).

• Step 4.5. Modify the particle’s velocity and position by adjacent swapping (based on the adjacent swapping probability).

• Step 4.6. End the algorithm provided that the convergence condition is satisfied; otherwise, go to Step 4.1.

As the PSO is designed for continuous environments, it requires “encoding” and “decoding” for discrete environments. Once the position of the particles has changed, the FMS should be specified by decoding. Regarding the particles’ positions, the FMS is specified and the MRs remain fixed. According to the literature, the solutions resulted in this step are not satisfactory and the mutation, crossover, and adjacent swapping are also employed to generate more appropriate solutions.^15,16 Recently, Miljković and Petrović ¹⁷ have defined velocity and position for the MRs so that they could also be enhanced.

The initial position and velocity of the particles are randomly specified. A value in [0, 1] range is assigned for the particle’s position. The particle’s velocity is represented by a value in [−1, 1] range. The position and velocity in the iteration Itr are then updated as follows

$$\begin{array}{l}{V}_{\mathrm{j}}^{\left(\mathrm{Itr}\right)}=w\times V_{\mathrm{j}}^{\left(\mathrm{Itr}-1\right)}+c_{1}r\left({\mathrm{best}}_1{P}_{,\mathrm{j}}-X_{\mathrm{j}}^{\left(\mathrm{Itr}-1\right)}\right)\\ +c_1{r}_1\left(G_{\mathrm{best}}-X_{\mathrm{j}}^{\left(\mathrm{Itr}-1\right)}\right)\end{array}$$

(2)

$$X_{\mathrm{j}}^{\left(\mathrm{Itr}\right)}=X_{\mathrm{j}}^{(\mathrm{Itr}-1)}+V_{\mathrm{j}}^{\left(\mathrm{Itr}\right)}$$

(3)

where w represents the velocity weight, $c_1$ the individual learning rate, $c_2$ the social learning rate, and $r_1$ and $r_2$ are two random numbers in the [0, 1] range. The best position experienced by the particle j for which the minimum cost function value is resulted is designated by $P_{\mathrm{best},\mathrm{j}}$ . The best position experienced so far by all particles is indicated by $G_{\mathrm{best}}$ . The weight w is reduced by the damping factor $w_{\mathrm{damp}}$ .

SA

Despite the above algorithms, the SA algorithm starts with a single random solution. The steps of this algorithm are as follows:

• Step 1. Get the manufacturing information of the workpiece such as the features and TADs.

• Step 2. Get the SA parameters such as the initial temperature and the Markov chain parameters.

• Step 3. Generate and evaluate a random solution.

• Step 4. Do the following steps:

• Step 4.1.2. Get the new solution based on the Boltzmann probability distribution function.

Step 4.2. Decrease the algorithm temperature.

Step 4.3. End the program if the convergence condition is satisfied; otherwise, go to Step 4.1.

In this algorithm, new solutions are generated through shifting, MR change, and adjacent swapping. The machining rules may not be followed when a new solution is resulted by shifting and adjacent swapping. Therefore, the results are always modified so that they follow the machining rules. In the literature,^1,14 only one solution is generated at constant temperature; in other words, the Markov chain of 1 is assumed. However, it would be more appropriate to generate and evaluate several solutions at a constant temperature. ²⁶

In SA, the new solution is received based on the probability $e^{-\frac{C_{\mathrm{new}}-C_{\mathrm{current}}}{T}}$ where $C_{\mathrm{new}}$ and $C_{\mathrm{current}}$ , respectively, denote the new and current cost function values. T represents the algorithm temperature and is calculated as follows ¹

$$T={\alpha }^{\mathrm{Itr}}\times T_0$$

(4)

where $\alpha$ is the cooling rate and $T_0$ is the initial temperature.

A new procedure for MR determination

The costs of the setup and MR changes can be avoided if the MRs of features are intersected. This article suggests a method for MR intersection and employs common MRs of the features. As mentioned earlier, one reason for the enlarged search space of the optimization algorithms is the existence of numerous MRs for single features. The rationale for MR intersection, therefore, is to reduce the search space by avoiding the generation of non-optimal solutions.

N features are assumed in the workpiece. Hence, the generated sequences consist of N steps and one of the features is machined in each step. The machining steps are denoted by S $(\mathrm{S}=1,2,\dots ,N)$ . In Step S, there are several candidate machine tools, cutting tools, and TADs which are shown by ${\mathrm{L}}_{\mathrm{CMT},\mathrm{S}}$ , ${\mathrm{L}}_{\mathrm{CCT},\mathrm{S}}$ , and ${\mathrm{L}}_{\mathrm{CTAD},\mathrm{S}}$ , respectively. Only one machine tool, cutting tool, and TAD should be determined for the Step S among the candidate elements. The selected machine tool, cutting tool, and TAD are represented by $\mathrm{M}{\mathrm{T}}_{\mathrm{S}}$ , $\mathrm{C}{\mathrm{T}}_{\mathrm{S}}$ , and $\mathrm{TA}{\mathrm{D}}_{\mathrm{S}}$ , respectively.

The procedure of generating random solutions in optimization algorithms is explained below. First, an FMS is generated. Then, the MRs of each feature are selected among the candidate MRs. In previous methods, the MRs of each feature were randomly selected among the candidate MRs. In this article, a machining step is randomly selected and the MRs of the feature which is machined in this step are randomly chosen among the candidate MRs for that feature. Let the selected machining step be denoted by m. The MRs of the features which are machined after the Step m $(\mathrm{S}>\mathrm{m})$ are determined based on the candidate MRs common to the preceding feature. The MRs of the features which are machined before the Step m $(\mathrm{S}<\mathrm{m})$ are determined based on the candidate MRs common to those of the next feature. The mathematical relations used to specify the machine tool, cutting tool, and TAD at each machining step are given below

$$\mathrm{M}{\mathrm{T}}_{\mathrm{S}}=\{\begin{array}{cc}{\mathrm{L}}_{\mathrm{CMT},\mathrm{S}}\cap \mathrm{M}{\mathrm{T}}_{\mathrm{S}+1}\hfill & \mathrm{S}<\mathrm{m}\hfill \\ \multicolumn{1}{c}{\mathrm{Randomly}\mathrm{select}\mathrm{a}\mathrm{machine}\mathrm{tool}\mathrm{from}\mathrm{set}{\mathrm{L}}_{\mathrm{CMT},\mathrm{S}}}& \mathrm{S}=\mathrm{m}\hfill \\ \multicolumn{1}{c}{{\mathrm{L}}_{\mathrm{CMT},\mathrm{S}}\cap \mathrm{M}{\mathrm{T}}_{\mathrm{S}-1}}& \mathrm{S}>\mathrm{m}\hfill \end{array}$$

(5)

$$\mathrm{C}{\mathrm{T}}_{\mathrm{S}}=\{\begin{array}{cc}{\mathrm{L}}_{\mathrm{CCT},\mathrm{S}}\cap \mathrm{C}{\mathrm{T}}_{\mathrm{S}+1}\hfill & \mathrm{S}<\mathrm{m}\hfill \\ \multicolumn{1}{c}{\mathrm{Randomly}\mathrm{select}\mathrm{a}\mathrm{cutting}\mathrm{tool}\mathrm{from}\mathrm{set}{\mathrm{L}}_{\mathrm{CCT},\mathrm{S}}}& \mathrm{S}=\mathrm{m}\hfill \\ \multicolumn{1}{c}{{\mathrm{L}}_{\mathrm{CCT},\mathrm{S}}\cap \mathrm{C}{\mathrm{T}}_{\mathrm{S}-1}}& \mathrm{S}>\mathrm{m}\hfill \end{array}$$

(6)

$$\mathrm{TA}{\mathrm{D}}_{\mathrm{S}}=\{\begin{array}{cc}{\mathrm{L}}_{\mathrm{CTAD},\mathrm{S}}\cap \mathrm{TA}{\mathrm{D}}_{\mathrm{S}+1}\hfill & \mathrm{S}<\mathrm{m}\hfill \\ \multicolumn{1}{c}{\mathrm{Randomly}\mathrm{select}\mathrm{a}\mathrm{TAD}\mathrm{from}\mathrm{set}{\mathrm{L}}_{\mathrm{CTAD},\mathrm{S}}}& \mathrm{S}=\mathrm{m}\hfill \\ \multicolumn{1}{c}{{\mathrm{L}}_{\mathrm{CTAD},\mathrm{S}}\cap \mathrm{TA}{\mathrm{D}}_{\mathrm{S}-1}}& \mathrm{S}>\mathrm{m}\hfill \end{array}$$

(7)

Assume an FMS as in Figure 1. The MRs of each feature are to be specified. In this example, only the machine tool of each feature is determined. The cutting tool and TAD also follow the same procedure. As stated previously, a machining step is randomly selected (here, the third step (m = 3)). It is assumed that the machine tool ${\mathrm{M}}_3$ is randomly chosen among the candidate machine tools of the feature ${\mathrm{F}}_5$ for the present machining step (m = 3). Then, the machine tools of the previous and next features are specified (equation (5)).

Figure 1.

Specifying machine tool for FMS.

In Figure 1, for example, the feature ${\mathrm{F}}_3$ is machined in the second step (m = 2) which satisfies $\mathrm{S}<\mathrm{m}$ . In this case, the machine tool specified for the second step is the result of the intersection between the machine tools of Steps 3 and 2. Hence, the machine tool ${\mathrm{M}}_3$ is also specified for Step 2. If there is no common machine tool for a specific step, the corresponding MR is selected randomly. The machining Step 4, in Figure 1, has no machine tool in common with its previous step (m = 3); therefore, a machine tool is randomly selected among the candidate machine tools ${\mathrm{M}}_1$ and ${\mathrm{M}}_4$ .

Once the random solutions are generated, the MR type changes through the optimization process so as to create FMSs with different MRs. It should be noted that the MR of each feature is previously determined, but the MR types of some features change in this phase.

The MR variation method, in this work, differs from those of the literature. The proposed method employs the intersection techniques as follows. First, a specific machining step is randomly chosen (the Step m). Then, an MR of the machine tools, cutting tools, and TAD is selected to be changed later. The variations are only applied to the selected MR. Next, the MR of the Step m is excluded from the candidate MRs. Then, an MR is selected randomly from the remaining MRs. After the Step m $(\mathrm{S}>\mathrm{m})$ , the MRs are chosen through intersection. Figure 2 shows an example of FMS generation through MR change. In this example, among three MRs of machine tool, cutting tool, and TAD, the machine tool is selected to be changed. The corresponding mathematical relation for the machine tool change is as follows

$$\mathrm{M}{\mathrm{T}}_{\mathrm{S}}=\{\begin{array}{cc}\mathrm{Randomly}\mathrm{select}\mathrm{a}\mathrm{machine}\mathrm{tool}\mathrm{from}\mathrm{set}{\mathrm{L}}_{\mathrm{CMT},\mathrm{S}}-\mathrm{M}{\mathrm{T}}_{\mathrm{S}}\hfill & \mathrm{S}=\mathrm{m}\hfill \\ \multicolumn{1}{c}{{\mathrm{L}}_{\mathrm{CMT},\mathrm{S}}\cap \mathrm{M}{\mathrm{T}}_{\mathrm{S}-1}}& \mathrm{S}>\mathrm{m}\hfill \end{array}$$

(8)

Figure 2.

An example of MR change.

An equation similar to equation (8) is used to change the cutting tool and TAD. It should be noted that a null ${\mathrm{L}}_{\mathrm{CMT},\mathrm{S}}-\mathrm{M}{\mathrm{T}}_{\mathrm{S}}$ set means that only one candidate machine tool exists for the machining Step S. In this case, the MR of the Step m remains unchanged.

As previously mentioned, MR variation is applied to only one of the MRs of the TAD, machine tool, and cutting tool; in other words, all MR types do not vary simultaneously. A variation probability is assigned to variation of each MR. This probability specifies the MR which undergoes changes. The variation probability for the machine tool, cutting tool, and TAD is, respectively, designated by $P_{\mathrm{MTC}}$ , $P_{\mathrm{CTC}}$ , and $P_{\mathrm{TADC}}$ . Most features have a specific TAD; however, several machine tools and cutting tools are available to machine a feature. Therefore, the variation probability of TAD should be less than that of the other MRs $(P_{\mathrm{TADC}}<P_{\mathrm{MTC}},P_{\mathrm{TADC}}<P_{\mathrm{CTC}})$ . The variation probabilities of the MRs are defined on the basis of the existing MRs of workshop and trial-and-error. One of the MRs is also chosen by the roulette wheel for change. The random selection phase of TAD occurs among multi-TAD features. In this way, the TAD of multi-TAD features is taken into account. Most features are unidirectional and their direction does not affect the TAD of multi-TAD features. Hence, for random TAD selection, multi-TAD features have priority to unidirectional ones.

Case study

The algorithms and procedures stated in previous sections are applied in this section. The main characteristics of these algorithms are summarized in Table 1. Considering all necessary parameters, the conventional MR determination methods are replaced by the proposed method and the results are evaluated. The convergence condition is defined as 40,000 function evaluations. The parameters listed in Table 1 are chosen based on trial-and-error.

Table 1.

The characteristics and parameters of optimization algorithms.

Algorithm’s name	GA		Modified PSO		SA
No. of solution	Population = 200		Swarm = 100		1
Create random solution	Edge selection-based encoding strategy		Edge selection-based encoding strategy		Edge selection-based encoding strategy
Create new solution			Swarm positions
	Crossover (PC)	Crossover Li et al. (PC1)	Crossover (PC)	Crossover Li et al. (PC1)
		Crossover Su et al. (PC2)		Crossover Su et al. (PC2)	Shift (Ps)
	Mutation (PM)	Adjacent swapping (PAS)	Adjacent swapping (PAS)		Adjacent swapping (PAS)
		Manufacturing resource change (PMRC)	Manufacturing resource change (PMRC)		Manufacturing resource change (PMRC)
Repair method	Li et al.’s repair method		Li et al.’s repair method		Li et al.’s repair method
Selection method	Tournament selection (next generation and select parents)		Randomly select parents		–
Algorithm parameters	P C = 0.8 (PC1 = 0.5, PC2 = 0.5)		P C = 0.2 (PC1 = 0.5, PC2 = 0.5)		P S = 0.3
	P M = 0.2 (PAS = 0.5, PMRC = 0.5)		P AS = 0.2		P AS = 0.3
	Tournament size = 4		P MRC = 0.6		P MRC = 0.4
			c 1 = c2 = 1.4962		T 0 = 10000
			w = 1.5, wdamp = 0.98		c = 0.9
					Markov chain = 200

GA: genetic algorithm; PSO: particle swarm optimization; SA: simulated annealing.

The workpiece depicted in Figure 3 is used to evaluate the proposed method. The manufacturing information is summarized in Table 2. In this table, the machine tools are represented by ${\mathrm{M}}_{\mathrm{i}}$ and the cutting tools by ${\mathrm{T}}_{\mathrm{i}}$ . The numbers in the GR and TR columns indicate the features which are prior to the specified feature for machining. Let the numbers in the GR column of feature ${\mathrm{F}}_1$ be 32, 33, and 37. This means that feature ${\mathrm{F}}_1$ has to be machined only when the features 32, 33, and 37 have been machined. This rule also holds for the machining rules of TR.

Figure 3.

The workpiece.

Table 2.

Manufacturing information of the workpiece.

ID	Type	TAD	GR	TR	Machine tools	Cutting tools
1	Thru slot	+x, ±z	32, 33, 37	18, 19	M3, M4, M5	T11
2	Thru slot	+y, ±z	32, 34, 37		M3, M4, M5	T11
3	Blind slot	+y	34		M3, M4, M5	T9
4	Blind slot	+y	34		M3, M4, M5	T9
5	Blind slot	+y	34		M3, M4, M5	T9
6	2-side pocket	−x, +y, −z	32, 34, 35		M3, M4, M5	T6, T7, T8
7	2-side pocket	−x, +y, +z	34, 35, 37		M3, M4, M5	T6, T7, T8
8	3-side pocket	+z	14, 37		M3, M4, M5	T5, T6
9	3-side pocket	−z	15, 32		M3, M4, M5	T5, T6
10	3-side pocket	−y, +z	36, 37		M3, M4, M5	T7, T8
11	3-side pocket	−y, −z	32, 36		M3, M4, M5	T7, T8
12	3-side pocket	−x	16, 35		M3, M4, M5	T5, T6
13	4-side pocket	−y	36		M3, M4, M5	T5, T6
14	4-side pocket	+z	37		M3, M4, M5	T7, T8
15	4-side pocket	−z	32		M3, M4, M5	T7, T8
16	4-side pocket	−x	35		M3, M4, M5	T7, T8
17	4-side pocket	−a	31		M3, M4, M5	T5, T6
18	4-side pocket	−y	36		M3, M4, M5	T7, T8
19	Thru hole	−y	2, 18		M1, M2, M3, M4, M5	T3, T4
20	Thru hole	±y	3, 13		M1, M2	T3, T4
21	Blind hole	−y	13	20	M1, M2	T1, T2
22	Blind hole	−y	13	20	M1, M2	T1, T2
23	Blind hole	−y	13	20	M1, M2	T1, T2
24	Blind hole	−y	13	20	M1, M2	T1, T2
25	Blind hole	−a	17		M1, M2	T3, T4
26	Blind hole	−a	17		M1, M2	T3, T4
27	Blind hole	−a	17		M1, M2	T1, T2
28	Blind hole	−a	17		M1, M2	T1, T2
29	Blind hole	−a	17		M1, M2	T1, T2
30	Blind hole	−a	17		M1, M2	T1, T2
31	Face	−a, −x, −y, ±z		32, 33, …, 37	M3, M4, M5	T10
32	Face	−z, ±x, ±y			M3, M4, M5	T10
33	Face	+x, ±y, ±z			M3, M4, M5	T10
34	Face	+y, ±x, ±z			M3, M4, M5	T10
35	Face	−x, ±y, ±z		1, 33	M3, M4, M5	T10
36	Face	−y, ±x, ±z		33, 34	M3, M4, M5	T10
37	Face	+z, ±x, ±y			M3, M4, M5	T10

TAD: tool access direction; GR: geometrical rules; TR: technological rule.

In Table 2, the drilling machines are denoted by M₁ and M₂ and the milling machines are represented by M₃, M₄, and M₅. T₁ and T₂ are small-sized drilling tools, T₃ and T₄ are drilling tools, T₅ and T₆ are small-sized end cutters, T₇ and T₈ are end cutters, T₉ is the slot cutter, T₁₁ is the big-sized slot cutter, and T₁₀ represents the face cutter tool.

The costs for the machine tool, cutting tool, machine tool change, cutting tool change, and setup change are listed in Table 3.

Table 3.

The costs for the machine tool, cutting tool, machine tool change, cutting tool change, and setup change.

Cutting tool cost
T1	T2	T3	T4	T5	T6	T7	T8	T9	T10	T11
8	6	10	12	18	20	30	35	15	18	30
Machine tool costs					Change costs
M1	M2	M3	M4	M5	Machine tools		Cutting tools		Setups
10	15	40	50	100	160		20		100

Due to the random nature of the optimization algorithms, each algorithm is run 30 times. The results are listed in Table 4. As previously mentioned, all three MRs do not vary simultaneously, rather one of them changes based on the variation probability. In this case study, the number of machine tools and cutting tools for each feature are close to each other (Table 2). The same variation probability is, therefore, considered for the machine tools and cutting tools. The variation probability of TAD $(P_{\mathrm{TADC}})$ , machine tool $(P_{\mathrm{MTC}})$ , and cutting tool $(P_{\mathrm{CTC}})$ are considered to be 0.1, 0.45, and 0.45, respectively, chosen by trial-and-error.

Table 4.

The results for 30 runs of GA, MPSO, and SA algorithms.

	Number of runs	Algorithm’s name	Worst cost	Best cost	Mean cost	Standard deviation cost	Best process planning
							Setups	MT change	CT change
Previousmethod	30	GA	4463	3597	3909.3	221.8	12	1	22
	30	MPSO	6123	4988	5619	303.4	14	6	28
	30	SA	4104	3420	3720.3	195.6	10	1	22
Proposed method	30	GA	3711	3361	3437.3	79.7	10	1	21
	30	MPSO	4372	3502	3949.7	203.2	10	1	26
	30	SA	3876	3361	3496.7	163.5	10	1	21

MT: machine tool; CT: cutting tool; GA: genetic algorithm; MPSO: modified particle swarm optimization; SA: simulated annealing.

As it is seen in Table 4, the proposed MR determination method has enhanced the outcome of the optimization algorithms, including the statistical results and the optimal solution. The number of setups, machine tool change, and cutting tool change are similar or close to each other in the obtained FMS in all the three algorithms. It is concluded that the proposed procedure can be implemented in these algorithms. The convergence rate curves of these algorithms are illustrated in Figure 4. The convergence of the optimization algorithms with the conventional and proposed MR determination techniques can be seen in Figure 4(a) and (b), respectively. The convergence curves represent the average results for 30 runs. Although the convergence behavior of both proposed and conventional MR determination methods has some similarities, they considerably differ in two factors. The first factor is the initial cost function value. As it can be seen, the initial cost function value for the conventional methods is close to 9000 (Figure 4(a)). But, the initial cost function value for the proposed method amounts to only 6000. In other words, superior initial solutions are obtained and trivial non-optimal solutions are not generated. The second dissimilarity is the convergence rate which is noticeably better for the proposed algorithm. For enhanced illustration, the convergence curves are shown in terms of the algorithm type in Figure 5. The convergence of the GA with the conventional and proposed MR determination techniques is depicted in Figure 5(a). The enhancement of the convergence rate can be seen in all three algorithms.

Figure 4.

Comparison of convergence curves of optimization algorithms using (a) conventional techniques and (b) the proposed technique for MR determination.

Figure 5.

Comparing convergence curves of (a) GA, (b) MPSO, and (c) SA algorithms.

As is seen in Figure 4(a) and Table 4, the best results for MR determination with conventional method belongs to the SA algorithm where the convergence rate is slower than the GA. The SA outperforms the GA in four statistical factors listed in Table 4. If the proposed MR determination technique is employed, the performance of the GA in finding the optimal solution will resemble that of SA, but the GA outperforms the SA in three statistical factors of worst value, average value, and standard deviation of the cost functions. Lower standard deviation in GA shows that closer results are obtained from all 30 runs. Therefore, the best performance from the viewpoint of statistical results and the convergence rate belongs to GA with the proposed MR determination technique.

Although the proposed MR determination technique has enhanced the MPSO results, it still has the worst performance compared to other algorithms. The cost function value of the initial solutions does not considerably differ from that of the final solutions (Figure 5(b)) for the MPSO algorithm; in other words, fewer enhancements are seen in MPSO solutions. Therefore, the MPSO strategy in generating new solutions is weak compared to its counterparts.

Figure 6 depicts the FMS outcome of the GA and SA algorithms. The number of setups is specified based on this FMS. As it can be noticed, these two optimal solutions have slight differences with identical cost function values. These differences can affect the performance of the optimization algorithms. In the MPSO algorithm, for example, the best position of the particles highly affects the new position of all particles. Hence, the variations of the optimal FMS with fixed cost function values can result in continuous variation of the particle movements, so that the algorithm converges to no unique optimal solution.

Figure 6.

The optimal solutions of (a) GA and (b) SA algorithms.

One difference of the optimal solutions in Figure 6 lies in setup 5 where the features F₁₀, F₁₁, F₁₃, F₁₈, and F₁₉ are placed in different sequences in one setup. This happens due to the lack of GR and TR in these features. In this case, the machining priority is for the feature with the most machining volume. In optimization algorithms, however, this priority either cannot be applied to the features without inter-related rules or it requires auxiliary algorithms.

It should be noted that the number of setups is not optimized, but it is specified based on the FMS. Although taking the setup change costs into account can reduce the number of setups, it cannot guarantee setup minimization. Consider an example in which one setup can be separated into two different setups with less machining costs. This may seem favorable, but it can also increase the machining errors and necessitate the tolerance analysis so that the workpiece tolerances are followed. Due to similar reasons and existence of several optimal solutions (Figure 6), an appropriate cost function has to be defined for setup planning.

Conclusion

Determination of setup and machining sequence is a major part of CAPP. Various methods, including the optimization algorithms, have already been proposed by the researchers for this purpose. In this work, three optimization procedures, including the GA, SA, and PSO algorithms, have been studied. These algorithms suffer from large search space. One reason for this large space is various MRs for a single machining feature. Hence, a method based on MR intersection has been proposed for reducing the search space. This method avoids trivial non-optimal solutions in which unnecessary cutting tool, machining tool, and setup change costs are involved. The proposed method has been tested on the above-mentioned algorithms. The results prove the enhanced performance of these algorithms. The MR determination method has enhanced the outcome of the optimization algorithms, including the statistical results and the optimal solution. It is concluded that the proposed procedure can be implemented in these algorithms. The best and the worst performances were observed in the GA and PSO, respectively.