An ant colony approach to operation sequencing optimization in process planning

Abstract

Computer-aided process planning is an important component for linking design and manufacturing in computer-aided design/computer-aided process planning/computer-aided manufacturing integrated manufacturing systems. Operation sequencing in computer-aided process planning is one of the most essential tasks. To solve the problem and acquire optimal process plans, operation sequencing is modeled as a combinatorial optimization problem with various constraints, and a novel modified ant colony optimization algorithm is developed to solve it. To ensure the feasibility of process plans, constrained relationships considered among operations are classified into two categories called precedence constraint relationships and clustering constraint relationships. Operation precedence graph based on constrained relationships is formed to get visual representation. To ensure good manufacturing economy, in the mathematical model for optimization, total weighted production cost or weighted resource transformation time related to machine changes, setup changes, tool changes, machines and tools is utilized as the evaluation criterion. To avoid local optimum and enhance global search ability, adaptive updating method and local search mechanism are embedded into the optimization algorithm. Case studies of three parts are carried out to demonstrate the feasibility and robustness of the modified ant colony optimization algorithm, and some comparisons between the modified ant colony optimization algorithm and previous genetic algorithm, simulated annealing algorithm, tabu search and particle swarm optimization algorithm are discussed. The results show that the modified ant colony optimization algorithm performs well in the operation sequencing problem.

Introduction

Computer-aided process planning (CAPP) is the bridge connecting computer-aided design (CAD) with computer-aided manufacturing (CAM). Process planning determines how to produce the designed products using available manufacturing resources economically and thus plays a major part in determining the cost of products and affects all factory activities. ¹ In order to obtain the process planning, the process planner derives some appropriate information from a design model such as the design profile, accuracy, surface roughness, material, and all of those information are defined as manufacturing features.^2,3 Based on the information, an instruction set should be prepared in the form of process plan, which includes the sequence, machines as well as tools to be used; cutting conditions for the individual processes and so on.^4–6 For a part with complex structures and numerous features, process planning is well known as a complicated decision-making process involving selecting machining operations for every feature and sequencing the aggregate of all the operations considering precedence constraints, choosing available manufacturing resources, determining setup plans, machining parameters and so on.^7–9 All the activities should be considered comprehensively to get an optimal plan so that total machining time or production cost could be sharply decreased and manufacturing efficiency could be greatly increased.

In the past few decades, two basic categories of CAPP called variant and generative have received a lot of attention. The basic principle of variant systems is to take advantage of the similarities between parts. Process planning of a new part is conducted by retrieving an existing plan belonging to a similar part stored in the system and then making some modifications. Generative systems are creating process automatically for a new part based on process knowledge databases and decision logics. As there are disadvantages in generating a plan for new features and influencing the process quality due to knowledge background in variant system,^10–12 a lot of generative systems have been developed to overcome these defects. In any CAPP system, selection of the operation sequence is a vital activity to make the machining economical, and in this article, we deal with process planning problem in generative systems.

To solve the problem of operation sequencing, lots of optimization algorithms have been developed and widely applied to determine the optimal sequences with good manufacturing practice and consistency of the desired functional specifications. These algorithms can be categorized as genetic algorithm (GA),^8,13–17 tabu search (TS),^18,19 simulated annealing (SA),^20–22 particle swarm optimization (PSO)^23,24 and ant colony optimization (ACO).^25,26

Kafashi ¹³ presented a generative system and GA approach to plan the given part. In their studies, the optimization methodology analysis constraints were tool approach direction (TAD), tolerance relation between features and feature precedence relations, and machining cost was used to measure the quality of a process plan quantitatively. Huang et al. ⁸ developed a hybrid graph and GA approach for process planning optimization. In their research, activities such as sequencing operations, selecting manufacturing resources and determining setup plans were considered to achieve the global optimal objective, and the total production cost was the evaluation criterion. Hua et al. ¹⁴ proposed a GA-based synthesis approach for machining scheme selection and operation sequencing optimization, and the fuzzy logic neural network, which contained the membership function of each machining operation to batch size, was presented to determine the priorities of alternative machining operations. Salehi and Tavakkoli-Moghaddam ¹⁵ generated the feasible sequences of operations based on the analysis of constraints, and using a GA, the optimized operation sequence and the optimized selection of the machine, cutting tool and TAD for each operation were obtained. Li et al. ¹⁶ developed a hybrid GA and SA, and in their research, the evaluation criterion of machining cost came from the combined strengths of machine costs (MCs), cutting tool costs (TCs), machine changes, tool changes and setup changes. Reddy ¹⁷ used GAs as a global search technique for a quick identification of optimal or near-optimal operation sequences in a dynamic planning environment. In the study, the sum of relative costs caused by machining parameter change, tool change, setup change and machine change was considered as the evaluation criterion. A precedence cost matrix was generated then for that application.

Lian et al. ¹⁸ proposed an optimization strategy of multi-dimensional tabu search (MDTS) algorithm for process planning; their research considered four dimensions of a process plan in parallel, namely, operation sequence, machine sequence, tool sequence and TAD sequence, and the total weighted cost was used as the evaluation criterion. Li et al. ¹⁹ took the problem as a constraint-based optimization problem; a TS-based approach was proposed to solve it effectively; in the optimization model, costs of the utilized machines and cutting tools, machine changes, tool changes, setups and departure from good manufacturing practices (penalty function) were the optimization evaluation criteria. Pandey et al. ²⁰ attempted to address the sequencing problem to an extent by developing operation sequencing rating index, which was the weighted sum of four indices: setup changeover index, tool changeover index, motion continuity index and loose precedence index. And the SA-based algorithm has been employed to determine the optimal or near-optimal operation sequence. Nallakumarasamy et al.^21,22 developed an intelligent CAPP system, and feasible sequences of operations are generated based on the precedence cost matrix and reward–penalty matrix using SA technique or super-hybrid GAs and SA technique. They considered relative costs caused by machine change, tool change, setup change and machining parameter change.

Guo et al.^23,24 developed the problem as a combinatorial optimization, and a modern evolutionary algorithm called the PSO algorithm has been employed and modified to solve it effectively, and the total cost or processing time was the evaluation criterion. Krishna and Rao ²⁵ presented the ant colony algorithm as a global search technique for the quick identification of the optimal operation sequence, and cost matrix composed of the various attributes such as machining parameter change, cutting tool change, setup change and machine tool change was taken into consideration. Liu et al. ²⁶ used ACO algorithm to deal with process planning; they took the problem as a Traveling Salesman Problem (TSP) problem; the costs for machining processes (including MC and TC) were converted to the weights of the cities; the costs for preparing processes (including machine changing, tool changing and setup changing) were converted to the “distance” between cities.

By reviewing the literatures listed above, a conclusion can be drawn: in acquiring optimal operation sequence by different algorithms, an operation with alternative machines, TADs and cutting tools should be treated as a basic element, and the production cost is considered frequently as the evaluation criteria. However, these can bring some problems:

1. An operation along with its accessories is an element; the search space will be very large, and the proposed algorithms may not find optimal solutions effectively. Meanwhile, the initial population of some algorithms such as GA and PSO is random and traditional ACO may come across local optimum, so it is necessary to design some operators to get global optimal solution.

2. Most of the proposed methods take the production costs related to machines, setups and cutting tools as evaluation criteria, so that the presupposition of optimizing the process is to get cost index or cost matrix. However, in a limited machining environment when all these are uncertain, some operators should be done to meet the practical workshop situations.

The main purpose of this study is to propose a method to solve the problems, which can be used to get feasible optimal solutions in operation sequencing. A modified ACO algorithm is used to get global optimal result and adapt to uncertain complex manufacturing environment. This article is organized into five sections. In the next section, the operation sequencing problem is represented, containing the analysis of constrained relationships among different operations, precedence relationships modeling and expression as well as the mathematical model for operation sequencing optimization. In the third section, details of the proposed sequencing algorithm based on modified ACO are described and a flowchart based on the algorithm is illustrated for application guidance. In the fourth section, three cases of getting optimal sequences are demonstrated and some comparisons between the results of the proposed algorithm and GA, SA, TS and PSO algorithms are presented. Finally, conclusions and further recommendations are pointed out in the last section.

Operation sequencing problem representation

Given a CAD part, to do process planning, the product geometric and manufacturing process information should be integrated by manufacturing features such as planes, pockets, holes and steps. Following that, the selection of machining operations, machines, TADs, cutting tools and cutting parameters needs to be done. Figure 1 shows representation of process planning of a part with m features. Each feature can be manufactured by one or more machining operations (n operations in total for machining the part). Each operation can be executed by several alternative plans because different candidates of machines, cutting tools and TADs can be chosen for this operation. The combination of different candidates for an operation can be a set; if op_i is the ith operation of the part, the combination plans belonging to op_i can be described as

$$\mathrm{plan}(o{p}_i)=\{o{p_i}_1,o{p_i}_2,\dots ,o{p_i}_{n_i}\},1⩽i⩽n$$

(1)

where op_ij is the jth plan for op_i, 0 ⩽ j ⩽ n_i and n_i is the number of combination plans of op_i. For operation op_i, there are n_i plans to be selected in real machining, but only one plan op_ij of the alternatives can be selected, and the machine, cutting tool and TAD of op_ij can be defined as

$$o{p}_{\mathrm{ij}}=\{{\mathrm{M}}_{\mathrm{ij}}{\mathrm{T}}_{\mathrm{ij}}\mathrm{TA}{\mathrm{D}}_{\mathrm{ij}}\}$$

(2)

where M _ij is the machine selected by op_ij, T _ij is the cutting tool selected by op_ij and TAD _ij is the TAD selected by op_ij.

Figure 1.

Representation of process planning.

From the analysis above, process planning for a part is a comprehensive and combinatorial problem. In this research, a process plan for a part is built up based on the following aspects:

1. The optimized sequence of the operations for the part.

2. The optimized selection of the machine, TAD and cutting tool for every operation.

3. The two aspects should be performed simultaneously.

To use the proposed ACO algorithm, as shown in Figure 1, each operation is defined as a set of applicable machines, TADs and tools, by which the operation can be performed; the details are listed in Table 1.

Table 1.

Class definition of an operation.

Class definition: an operation
Date type	Variable	Description
Int	op_id	ID of the operation
Int	M_id	ID of a machine to perform the operation
Int	T_id	ID of a cutting tool to perform the operation
Int	TAD_id	ID of a TAD to perform the operation
Int	Feature_id	ID of feature corresponding to the operation
Int[]	M_list[]	Machine candidates list for performing the operation
Int[]	T_list[]	Cutting tool candidates list for performing the operation
Int[]	TAD_list[]	TAD candidates list for performing the operation
Char*	op_name	Processing method name of the operation
specific_type	Cutting_parameters	Cutting parameters to perform the operation

TAD: tool approach direction.

Constrained relationships analysis in operation sequencing

Constrained relationships first should be precedence constraint relationships. A feasible operation sequence must comply with precedence constraints that come from geometrical and technological considerations.^23,24,27 The constraints imply precedence relationships to determine in what order to perform a set of selected operations. ⁸ In this research, the precedence constraints between operations are classified into eight types.

Datum constraint relationship

Datum faces as reference planes should be machined primarily to locate a part. If there are multiple finishing datums, they should be arranged based on the principles such as datum transformation sequence and gradual improvement of the machining accuracy.

Primary and secondary constraint relationship

It is suitable for the main features of the part such as faces and holes to be machined first in roughing and semi-finishing stage. Generally, minor features such as chamfer and keyway can be arranged between semi-finishing and finishing stages of main features.

Face and hole constraint relationship

Face should be machined prior to hole for some parts because the face can easily be the reference plane for machining the hole.

Processing stage constraint relationship

For the parts with high technical requirements, the surfaces should be machined from rough machining, semi-finishing to finish machining in order to achieve high machining quality.

Feature priorities constraint relationship

Feature priorities constraint relationship (FPCR) restrains the machining sequence of features. Child features such as some grooves and chamfers should be machined after parent features. When a face is not perpendicular to the axis of the hole, the hole feature should be machined first for convenient location.

Thin-wall constraint relationship

For some thin-wall components, to control deformation and ensure machining accuracy, thin-wall constraint relationship (TWCR) should be considered.

Fixed order constraint relationship of machining operation

Fixed order constraint relationships (FOCR) is usually determined by the fixed order of operations. For example, a typical sequence of machining a hole is drilling-boring and reaming. ²⁴

Material-removal constraint relationship

A material-removal constraint occurs when different material-removal sequences of features affect the cost or the quality of machining. For example, a step should be machined prior to the hole on it for achieving high machining efficiency (milling is faster than drilling) and surface quality.^19,24 In addition to precedence constraint relationships, to ensure machining accuracy and improve processing efficiency of parts, the process plan also needs some clustering constraints as follows:

Process centralization and decentralization constraint relationship

The process centralization and decentralization constraint relationship (PCDCR) influences the complexity of the process and affects resource utilization of machines, tools and setups in the machining. For the workpiece with large size and weight, the process should be arranged centrally considering difficult installation and transportation. Under PCDCR, processing activities under same resources should be centralized together to reduce the cost.

Tool approach direction constraint relationship

TAD is an important parameter to describe features, which directly influences the clamping results. TAD is a direction that cutting tools can reach without interference. For three-axis machine, there are six TADs: x, −x, y, −y, z and −z. In some cases, features such as slopes and inclined holes can define new TADs based on actual demand. When operations have not only one TAD to perform it, in operation sequencing, according to the type of the machines and the impact of TAD on the clamping, the operations with same TAD can be grouped together for good manufacturability.

Same datum constraint relationship

For two features with position accuracy requirements, if they both adopt another surface as the datum reference, to ensure higher position accuracy, they should be machined in a same setup. In operation sequencing, according to the datum relationship among features, operations with same datum should be arranged together and be machined in same setup.

In conclusion, precedence constraints are mandatory and must be met; clustering constraints generally do not need to be satisfied absolutely but violation of this kind of constraint will cost more and the concrete implementation can be guaranteed by the designed optimization goal. The mapping relations between an operation and constrained relationships containing precedence constraints and clustering constraints affecting operation sequencing are shown in Figure 2. For example, in determining primary and secondary constraint relationship, the attributes of feature such as accuracy class and surface roughness should be considered. In determining same datum constraint relationship, the attributes of feature such as feature type and datum information should be considered. When determining sequences between two operations, constraint relationships are converting into the corresponding attribute information. And by comparing with the two relevant attributes, the relationship between operations can be determined.

Figure 2.

Mapping relations between an operation and constrained relationships.

Precedence relationships modeling and expression

For precedence relations between operations, the directed graph is used for visual representation, which is described as operation precedence graph (OPG).

Definition 1

OPG is a directed graph; G_opg = (OP, A, OP_T); OP = {op₁,op₂,…, op_n} is a set of nodes between different operations of parts; $\mathrm{A}=\{〈o{p}_i,o{p}_{i\prime }〉|o{p}_i,o{p}_{i\prime }\in \mathrm{OP}\}$ represents a set of ordered arcs; for $\forall a\in \mathrm{A},a=〈o{p}_i,o{p}_{i\prime }〉$ , op_i is the starting node of a corresponding to operation i while op_i′ is the ending node of a corresponding to operation i′. $\mathrm{O}{\mathrm{P}}_{\mathrm{T}}:\mathrm{OP}\to \{\mathrm{and},\mathrm{or}\}$ is constraint function type of operations; for $\forall o{p}_i\in \mathrm{OP}$ , if OP_T(op_i) is “and,”op_i can be machined only when all operations before op_i are machined. If OP_T(op_i) is “or,”op_i can be machined when any one of operations before op_i is machined. In OPG, a solid line represents “and” and a dotted line represents “or.”Because computers are more adept at manipulating numbers than at recognizing pictures, it is standard practice to communicate the specification of a graph to a computer in matrix form. ²⁹ Based on the definition of OPG, precedence relation matrix P is defined as $(p_{\mathrm{ii}\prime }{)}_{m\times n}$

$$p_{\mathrm{ii}\prime }=\{\begin{array}{c}1o{p}_i\mathrm{is\; machined\; prior\; to}o{p}_{i\prime }\hfill \\ \multicolumn{1}{c}{0\mathrm{else}}\end{array}$$

(3)

where n is the total number of operations of the part; $1⩽i,i\prime ⩽n,i\ne i\prime$ ; the diagonal elements of the matrix are zero, that is p_ii = 0.

Following the characteristics of $(p_{\mathrm{ii}\prime }{)}_{m\times n}$ , some definitions are as follows

Definition 2

The sum of elements in each row of the matrix is defined as the number of constraint condition, which can be expressed as

$$U_{o{p}_i}=\sum _{i\prime =1}^N{p}_{\mathrm{ii}\prime }$$

(4)

Definition 3

The sum of elements in each column of the matrix is defined as the number of restrained condition, which can be expressed as

$$V_{o{p}_i}=\sum _{i=1}^N{p}_{\mathrm{ii}\prime }$$

(5)

From equations (4) and (5), we can get the following conclusions:

1. For operation op_i, if $U_{o{p}_i}\ne 0,V_{o{p}_i}=0$ , op_i will restrain other operations but not be restrained by other operations, so op_i should be machined prior to others, which can be the starting operation.

2. For operation op_i, if $U_{o{p}_i}=0,V_{o{p}_i}\ne 0$ , op_i will not restrain other operations but be restrained by other operations, so op_i should be machined later than others, which can be the ending operation.

3. For operation op_i, if $U_{o{p}_i}\ne 0,V_{o{p}_i}\ne 0$ , op_i will restrain and be restrained by other operations, so op_i should be machined in intermediate stage.

In all, OPG and precedence relation matrix are used to describe the precedence relations between op_i and op_i′; if op_i is prior to op_i′, then for $\forall j\mathrm{and}j\prime$ , op_ij should be arranged before op_i′j′.

Mathematical model for operation sequencing optimization

In operation sequencing, the machining sequences should be adjusted as far as possible not only to meet the constraints of precedence relations but also to meet the clustering constraints. In this article, production cost is used to measure the quality of a process plan. Production cost is composed of MCs, TCs, machine change costs (MCCs), setup change costs (SCCs) and tool change costs (TCCs).^8,19,24 If op_ij, op_i′j′ (i ≠ i′) are the choices of combination plans belonging to two adjacent operations op_i, op_i′ respectively, then the costs from machine changes, setup changes, tool changes, machines and tools are defined as follows.

MCC

When the machines for executing op_ij, op_i′j′ are different, which means the machine change between op_i and op_i′ has happened, MCC between op_i and op_i′ can be calculated as

$$\begin{array}{c}\mathrm{MC}{\mathrm{C}}_{\mathrm{iji}\prime j\prime }\hfill \\ ={\delta }_1({\mathrm{M}}_{\mathrm{ij}}\_\mathrm{ID}|o{p}_i,{\mathrm{M}}_{i\prime j\prime }\_\mathrm{ID}|o{p}_{i\prime })·\mathrm{MCCI}\hfill \\ =\mathrm{C}{\mathrm{m}}_{\mathrm{iji}\prime j\prime }·\mathrm{MCCI}\hfill \end{array}$$

(6)

where M _ij _ID|op_i, M_i′j′_ID|op_i′ represent machine ID to perform two adjacent operations, Cm_iji′j′ is the number of machine changes between op_i and op_i′, MCCI is the MCC index and ${\delta }_1(x,y)$ is the judgment function to decide machine changes between operations defined as

$${\delta }_1(x,y)=\{\begin{array}{c}1,x\ne y\hfill \\ \multicolumn{1}{c}{0,x=y}\end{array}$$

(7)

SCC

Setup changes are related to TADs and machines; when any one of TADs or machines for executing op_ij, op_i′j′ is changed, which means the setup change between op_i and op_i′ has happened, SCC between op_i and op_i′ can be calculated as

$$\begin{array}{l}{\mathrm{SCC}}_{iji\prime j^{\prime }}\\ =\left[{\delta }_1({\mathrm{M}}_{ij}\_\mathrm{ID}|o{p}_i,{\mathrm{M}}_{i^{\prime }{j}^{\prime }}\_\mathrm{ID}|o{p}_{i^{\prime }}),{\delta }_1({\mathrm{TAD}}_{ij}\_\mathrm{ID}|o{p}_i,{\mathrm{TAD}}_{i^{\prime }{j}^{\prime }}\_\mathrm{ID}|o{p}_{i^{\prime }})\right]\cdot \mathrm{SCCI}\\ ={\mathrm{Cs}}_{iji\prime j^{\prime }}\cdot \mathrm{SCCI}\end{array}$$

(8)

where TAD _ij _ID|op_i, TAD _ij _ID|op_i′ represent TAD ID of two adjacent operations, Cs_iji′j′ is the number of setup change between op_i and op_i′, SCCI is the SCC index and ${\delta }_2(x,y)$ is used to judge whether the setups are changed; when two operations are performed by same TAD and machine, the setup changes will not occur; other conditions such as same machine and different TADs, different machines and same TAD and different TADs and machines are considered as setup changes, so ${\delta }_2(x,y)$ is defined as

$${\delta }_2(x,y)=\{\begin{array}{c}0,x=y=0\hfill \\ \multicolumn{1}{c}{1,\mathrm{else}}\end{array}$$

(9)

TCC

Tool changes are related to tools and machines; when any one of tools or machines for executing op_ij, op_i′j′ is changed, which means the tool change between op_i and op_i′ has happened, TCC between op_i and op_i′ can be calculated as

$$\begin{array}{l}{\mathrm{TCC}}_{iji\prime j^{\prime }}\\ ={\delta }_2\left[{\delta }_1({\mathrm{M}}_{ij}\_\mathrm{ID}|o{p}_i,{\mathrm{M}}_{i^{\prime }{j}^{\prime }}\_\mathrm{ID}|o{p}_{i^{\prime }}),{\delta }_1({\mathrm{T}}_{ij}\_\mathrm{ID}|o{p}_i,{\mathrm{T}}_{i^{\prime }{j}^{\prime }}\_\mathrm{ID}|o{p}_{i^{\prime }})\right]\cdot \mathrm{TCCI}\\ ={\mathrm{Ct}}_{iji\prime j^{\prime }}\cdot \mathrm{TCCI}\end{array}$$

(10)

where T _ij _ID|op_i, T _ij _ID|op_i′ represent tool ID of two adjacent operations, Ct_iji′j′ is the number of setup changes between op_i and op_i′, TCCI is the TCC index and ${\delta }_3(x,y)$ is used to judge whether the tools are changed; when two operations are performed by the same tool and machine, the tool changes will not occur; other conditions such as same machine and different tools, different machines and same tool and different machines and tools are considered as tool changes, so ${\delta }_3(x,y)$ is defined as

$${\delta }_3(x,y)=\{\begin{array}{c}0,x=y=0\hfill \\ \multicolumn{1}{c}{1,\mathrm{else}}\end{array}$$

(11)

MC

M _ij is the machine selected to perform the op_ij, so MC of op_i can be calculated as

$$\mathrm{M}{\mathrm{C}}_{\mathrm{ij}}=\mathrm{MC}{\mathrm{I}}_{{\mathrm{M}}_{\mathrm{ij}}\_\mathrm{ID}|o{p}_i}$$

(12)

where $\mathrm{MC}{\mathrm{I}}_{{\mathrm{M}}_{\mathrm{ij}}\_\mathrm{ID}|o{p}_i}$ is the MC index for using the machine.

TC

T _ij is the cutting tool selected to perform the op_ij, so TC of op_i can be calculated as

$$\mathrm{T}{\mathrm{C}}_{\mathrm{ij}}=\mathrm{TC}{\mathrm{I}}_{{\mathrm{T}}_{\mathrm{ij}}\_\mathrm{ID}|o{p}_i}$$

where $\mathrm{TC}{\mathrm{I}}_{{\mathrm{T}}_{\mathrm{ij}}\_\mathrm{ID}|o{p}_i}$ is the TC index for using the tool.

Based on the definition above, the mathematical model for operation sequencing optimization is constructed, and the objective function in this article is defined as

$$\begin{array}{c}\multicolumn{1}{c}{min\to w_1\mathrm{MCCI}·\left(\sum _{i=1}^n\sum _{j=1}^{n_i}\sum _{\genfrac{}{}{0ex}{}{i\prime =1}{i\prime \ne i}}^n\sum _{j\prime =1}^{n_{i\prime }}{x}_{\mathrm{iji}\prime j\prime }\mathrm{C}{\mathrm{m}}_{\mathrm{iji}\prime j\prime }\right)}\\ +w_2\mathrm{SCCI}·(\sum _{i=1}^n\sum _{j=1}^{n_i}\sum _{\genfrac{}{}{0ex}{}{i\prime =1}{i\prime \ne i}}^n\sum _{j\prime =1}^{n_{i\prime }}{x_{\mathrm{iji}\prime j}}_{\prime }\mathrm{C}{\mathrm{s}}_{\mathrm{iji}\prime j\prime }+1)\hfill \\ +w_3\mathrm{TCCI}·\left(\sum _{i=1}^n\sum _{j=1}^{n_i}\sum _{\genfrac{}{}{0ex}{}{i\prime =1}{i\prime \ne i}}^n\sum _{j\prime =1}^{n_{i\prime }}{x}_{\mathrm{iji}\prime j\prime }\mathrm{C}{\mathrm{t}}_{\mathrm{iji}\prime j\prime }\right)\hfill \\ +w_4\left(\sum _{i=1}^n\sum _{j=1}^{n_i}{y}_{\mathrm{ij}}\mathrm{M}{\mathrm{C}}_{\mathrm{ij}}\right)+w_5\left(\sum _{i=1}^n\sum _{j=1}^{n_i}{y}_{\mathrm{ij}}\mathrm{T}{\mathrm{C}}_{\mathrm{ij}}\right)\hfill \end{array}$$

(13)

In order to simplify the description, the objective function can be defined as

$$\begin{array}{c}\multicolumn{1}{c}{min\to \mathrm{TWPC}}\\ =w_1\mathrm{MCCI}·\mathrm{Cm}+w_2\mathrm{SCCI}·\mathrm{Cs}\hfill \\ +w_3\mathrm{TCCI}·\mathrm{Ct}+w_4\mathrm{MC}+w_5\mathrm{TC}\hfill \\ =w_1\mathrm{TMCC}+w_2\mathrm{TSCC}·\mathrm{Cs}\hfill \\ +w_3\mathrm{TTCC}+w_4\mathrm{MC}+w_5\mathrm{TC}\hfill \end{array}$$

(14)

where TWPC represents the total weighted production cost; Cm, Cs and Ct represent the total number of machine changes, setup changes and tool changes, respectively; TMCC, TSCC, TTCC, MC and TC represent total machine change cost, total setup change cost, total tool change cost, machine cost and tool cost, respectively; w_1–w₅ are weights valued 0 or 1 corresponding to TMCC, TSCC, TTCC, MC and TC; they are defined as selectivity coefficients for users to decide the cost factors to be considered. When w_j(1 ⩽ j ⩽ 5) is set as 0, it means the cost factor j is not considered, or else the factor should be a prior consideration when w_j is 1.

The objective function is subject to the following restrictions:

1. There are n operations to be executed in the whole process of a part

   $$\sum _{i=1}^n\sum _{j=1}^{n_i}{y}_{\mathrm{ij}}=n,y_{\mathrm{ij}}\in \{0,1\}$$

   (15)

2. Only one plan is selected for an operation from its combination plans

   $$\sum _{j=1}^{n_i}{y}_{\mathrm{ij}}=1,i\in [1,n]$$

   (16)

3. There are n − 1 change costs between n operations added into TWPC

   $$\{\begin{array}{c}\sum _{i=1}^n\sum _{j=1}^{n_i}\sum _{\genfrac{}{}{0ex}{}{i\prime =1}{i\prime \ne i}}^n\sum _{j\prime =1}^{n_{i\prime }}{x}_{\mathrm{iji}\prime j\prime }=n-1\hfill \\ \multicolumn{1}{c}{x_{\mathrm{iji}\prime j\prime }\in \{0,1\}\mathrm{and}i\ne i\prime }\end{array}$$

   (17)

4. Each operation has at most one adjacent operation prior to it in final process result, and each operation has at most one adjacent operation after it in final process result

   $$\sum _{i=1}^n\sum _{j=1}^{n_i}{x}_{\mathrm{iji}\prime j}⩽1$$

   (18)
   $$\sum _{i\prime =1}^n\sum _{j\prime =1}^{n_{i\prime }}{x}_{\mathrm{iji}\prime j\prime }⩽1$$

   (19)

When $\sum _{i=1}^n\sum _{j=1}^{n_i}{x}_{\mathrm{iji}\prime j}=0$ that means $U_{o{p}_{i\prime }}\ne 0$ , $V_{o{p}_{i\prime }}=0$ and op_i′ is the first operation in machining process; when $\sum _{i\prime =1}^n\sum _{j\prime =1}^{n_i}{x}_{\mathrm{iji}\prime j}=0$ that means $U_{o{p}_{i\prime }}\ne 0,V_{o{p}_{i\prime }}=0$ and op_i is the ending operation in machining process.

In fact, considering that the number of machine changes, setup changes and tool changes can not only influence the cost but also affect the machining time, so in the limited situations especially when the cost index is uncertain, the total number of machine changes, setup changes and tool changes can be the main factors, then w₁ = w₂ = w₃ = 1, w₄ = w₅ = 0; MCCI, SCCI and TCCI now become the weights corresponding to the total number of machine changes, setup changes and tool changes, respectively; thus, the TWPC is changed to weighted resource transformation time (WRTT), and the objective function can be defined as

$$\begin{array}{c}\multicolumn{1}{c}{min\to \mathrm{WRTT}}\\ =\mathrm{MCCI}·\mathrm{Cm}+\mathrm{SCCI}·\mathrm{Cs}+\mathrm{TCCI}·\mathrm{Ct}\hfill \end{array}$$

(20)

where MCCI + SCCI + TCCI = 1.

Operation sequencing algorithm based on modified ACO

ACO proposed by Dorigo et al. ²⁸ is an algorithm with strong parallelism, which is a combination of distributed computing, positive feedback mechanism and greedy search algorithms. One of the underlying ideas of ACO is to use the equivalent of the pheromone trail used by the real ants as the medium for cooperation and communication among a colony of artificial ants. ²⁹ It has been applied successfully to solve different combinatorial problems.^{25,26,30–33} It has powerful ability of global searching for the optimal solution, but at the same time it can easily fall into local optimal solution and has poor local search ability, so in this article the traditional ant colony algorithm is improved to adapt to the operation sequencing.

According to the description of operation sequencing problems, to apply the ACO algorithm in the process plan optimization problem, some assumptions have to be done first.

1. The trajectory connecting the ant from the nest to the food source is a feasible process to the part, and the movement order of each ant should meet the precedence relations. The task of each ant is to produce a feasible process by adding a new operation to the current one at a time until all operations are selected.

2. Each ant from the nest corresponds to the first selected operations in OPG, and for these operations, $U_{o{p}_{i\prime }}\ne 0,V_{o{p}_{i\prime }}=0$ ; the ant includes information such as machines, TADs and tools. The food source corresponds to a process route.

3. The length of every trajectory from the ant’s nest to food source corresponds to the TWPC or resource transformation time.

Tabu criteria of ACO

The ant needs to determine whether related operations already exist in tabu list before its movement, and the operations belong to those which have already been processed. In each iteration, every operation can just be visited once and the moving process must comply with OPG and precedence relation matrix P. If tabu_k is the tabu list of ant k, after transition of ant k from one operation to another, the tabu_k will be updated, and the new visited operation should be deposited to its own tabu list; Figure 3(a)–(g) shows a sample of ant transition and update of tabu list. At the same time, the precedence relation constraint matrix is updated, and the corresponding row elements p_{ii′(1 ⩽ j ⩽ n)} are set to 0, which means the new visited operation has been executed and do not restrain the remaining operations.

Figure 3.

Transition of ant k and update of tabu_k sample: (a) tabu list update after the ant passes 1st operation, (b) tabu list update after the ant passes 2st operaion, (c) tabu list update after the ant passes 3rd operation, (d) tabu list update after the ant passes 6th operation, (e) tabu list update after the ant passes 5th operation, (f) tabu list update after the ant passes 4th operation and (g) tabu list update after the ant passes all operations.

Priorities of operation selection

As an ant chooses the next operation, the ant will iterate over all the alternative operations being filtered by tabu criteria. Before the selection, priorities between operations related to machines, setups and tools should be defined first; in the article, $d_{\mathrm{iji}\prime j\prime }$ is used to measure the priority between op_ij of op_i and op_i′j′ of op_i′, which is defined as

$$\begin{array}{c}\multicolumn{1}{c}{d_{\mathrm{iji}\prime j\prime }=w_1\mathrm{MC}{\mathrm{C}}_{\mathrm{iji}\prime j\prime }+w_2\mathrm{SC}{\mathrm{C}}_{\mathrm{iji}\prime j\prime }}\\ +w_3\mathrm{TC}{\mathrm{C}}_{\mathrm{iji}\prime j\prime }+w_4\mathrm{M}{\mathrm{C}}_{i\prime j\prime }+w_5\mathrm{T}{\mathrm{C}}_{i\prime j\prime }\hfill \end{array}$$

(21)

The smaller the $d_{\mathrm{iji}\prime j\prime }$ , the greater the possibility to be chosen for op_i′.

Modified transition probability

After the ant judges its tabu list and pheromone distribution, it will transfer to the next operation with a certain probability known as transition probability. Modified transition probability is based on pseudorandom proportional rules, and the transition probability of ant k movement from op_ij to op_i′j′ is expressed as

$$s=\{\begin{array}{c}\arg max\{{[{\tau }_{\mathrm{iji}\prime j\prime }(t)]}^{\alpha }·{[{\eta }_{\mathrm{iji}\prime j\prime }(t)]}^{\beta }\},\mathrm{if}q⩽q_0\hfill \\ \multicolumn{1}{c}{S,\mathrm{if}q>q_0}\end{array}$$

(22)

where q is a random variable evenly distributed in the interval [0, 1] and $q_0(0⩽q_0⩽1)$ ) is a parameter; the smaller the q₀,the higher the probability of making a random choice. ${\tau }_{\mathrm{iji}\prime j\prime }(t)$ is the pheromone value when op_ij moves to op_i′j′ in the route $〈o{p}_i,o{p}_{i\prime }〉$ ; in initialization, the pheromone level between every two operations is zero. $\alpha$ is the relative importance of pheromone level, and $\alpha =1$ . ${\eta }_{\mathrm{iji}\prime j\prime }(t)$ is a heuristic function, and in this article, ${\eta }_{\mathrm{iji}\prime j}=1/d_{\mathrm{iji}\prime j\prime }$ ; it evaluates the expectations moving from op_ij to op_i′j′; the smaller the $d_{\mathrm{iji}\prime j\prime }$ , the more the expectation. $\beta$ is the relative importance of heuristic function, and S is a random variable defined according to the distribution given as follows

$${P_{\mathrm{iji}″j″}}^k(t)=\{\begin{array}{c}\frac{{[{\tau }_{\mathrm{iji}\prime j\prime }(t)]}^{\alpha }·{[{\eta }_{\mathrm{iji}\prime j\prime }(t)]}^{\beta }}{\sum _{i″j″\in E_k}{[{\tau }_{\mathrm{iji}″j″}(t)]}^{\alpha }·{[{\eta }_{\mathrm{iji}″j″}(t)]}^{\beta }},\mathrm{if}i″j″\in E_k\hfill \\ \multicolumn{1}{c}{0,\mathrm{otherwise}}\end{array}$$

(23)

where E_k is an operation set that ant k can visit and $E_k=E-\mathrm{tab}{u}_k$ .

In the modified ant colony algorithm, adjustment of q₀ can prompt the algorithm to explore new paths and make the algorithm search areas around optimal path so far, so modified transition probability is a much more positive selection rule, which can have better development and utilization of the experience in ant searching.

Modified adaptive method of updating pheromone

All the artificial ants in ant colony algorithm have certain memories, and the residual pheromone value in the path will be evaporated gradually during iterations. In the modified ant colony algorithm, only an ant (the optimal ant up to now) is allowed to release the pheromone after each iteration, and global updating rule is as follows

$$\{\begin{array}{c}{\tau }_{\mathrm{iji}\prime j\prime }(t+n)=(1-\rho )·{\tau }_{\mathrm{iji}\prime j\prime }(t)+\rho {\Delta }_{{\tau }_{\mathrm{iji}\prime j\prime }}^{\mathrm{bs}}\hfill \\ \multicolumn{1}{c}{{\Delta }_{{\tau }_{\mathrm{iji}\prime j\prime }}^{\mathrm{bs}}=1/C^{\mathrm{bs}}}\\ \multicolumn{1}{c}{\forall (\mathrm{ij},i\prime j\prime )\in T^{\mathrm{bs}}}\end{array}$$

(24)

where ${\Delta }_{{\tau }_{\mathrm{ii}\prime }}^{\mathrm{bs}}$ is the newly increased pheromone value, $T^{\mathrm{bs}}$ is the best solution obtained in an iteration, $C^{\mathrm{bs}}$ is the distance of the optimal path corresponding to T^bs and $\rho (0⩽\rho ⩽1)$ is the evaporation rate. In the modified algorithm, the pheromone evaporation and release are all in the route of T^bs, which can effectively reduce the complexity of calculation.

In addition to the global pheromone updating rule, the modified algorithm also adopts a kind of local updating rule. After each ant passes one operation, the pheromone will be updated by applying the rule

$${\tau }_{\mathrm{iji}\prime j\prime }(t+n)=(1-\xi )·{\tau }_{\mathrm{iji}\prime j\prime }(t)+\xi {\tau }_0$$

(25)

where ${\tau }_0$ is the initial value of pheromone and $\xi$ is a parameter valued in [0, 1]. The role of local updating rule is that when the ant goes through $〈o{p}_i,o{p}_{i\prime }〉$ , the pheromone value ${\tau }_{\mathrm{iji}\prime j\prime }$ will be reduced, which can decrease the probability of the route chosen by the ants and increase the opportunities for the ants to explore new routes and avoid the algorithm into stagnant state.

Local search mechanism

During iterations, if the operation with the most transition probability is always selected, the algorithm will lose randomness and be caught into local optimum. To solve this problem, many ant systems are hybrid algorithms employing some kind of local optimization techniques such as 2-opt technique, TS and SA. ²⁵ In this research, local search mechanism of the roulette wheel approach (RWA) is adopted to select a machine, TAD and tool for each operation; the process is composed of the following steps:

• Step 1: generate a random number r, $0⩽r⩽1$ , k = 0, sp = s (s is the transition probability when ant k moves from op_ij to op_i′j′).

• Step 2: if sp ⩾ r, then turn to Step 4.

• Step 3: if k = k + 1, sp = sp + s, then turn to Step 2.

• Step 4: output the result and stop search.

Through RWA, M _ij , T _ij and TAD _ij for executing op_i can be selected, and then a set of operations will be exported to the ACO for operation sequencing optimization.

Flowchart based on the modified ant colony algorithm

Using the modified ant colony algorithm based on precedence constraint matrix and evaluation criterions, the optimal solution can be selected from different combination schemes; a flowchart of proposed approach based on modified ant colony algorithm is shown in Figure 4; the specific steps of the algorithm are as follows:

• Step 1: according to the constraints among operations, construct and input precedence relation matrix P; information of operations such as M_list, TAD_list and T_list are defined in Table 1. And set the number of ants m, initialize the number of iterations N = 0 and set the maximum number of iterations Nmax, tabu_k, α, β, q₀, ρ, ξ and so on. The initial tabu list tabu_k is set null.

• Step 2: determine the initial operations according to constraint matrix and put the ants into the positions satisfying $U_{o{p}_i}\ne 0,V_{o{p}_i}=0$ , then add the ant into tabu list and update tabu_k.

• Step 3: determine the alternative operations that the ants can move according to their tabu lists and precedence relation matrix P. Then calculate transition probability based on the pseudorandom proportional rule defined in equation (22) and select the operations including machines, TADs and tools by the local search mechanism of RWA and update tabu list.

• Step 4: update local pheromone by applying the rule defined in equation (25).

• Step 5: following the movement of the ants among operations, judge the tabu list; if it is full, turn to Step 6, or else turn to Step 3.

• Step 6: update local pheromone of all paths and update global pheromone of the current optimal result by equation (24).

• Step 7: calculate the TWPC or WRTT according to equations (6)–(20) and then update the current optimal sequencing result.

• Step 8: judge termination conditions; if satisfied, output global optimal process plan, or else, release tabu list and turn to Step 3.

Figure 4.

Flowchart of modified ant colony algorithm.

Case studies

To illustrate the proposed algorithm, three cases will be conducted. In the first case, the process plan is in a limited machining environment, the cost index is uncertain, the key parameters of the modified ACO are determined and the results between the modified ACO and traditional ACO are compared. The second and third cases are used to compare this method with GA, SA, PSO and TS to demonstrate the validity.

Case study 1

The first part (part 1, shown in Figure 5(a)) consists of 15 manufacturing features, which can be machined with 23 operations. The information of features, operations and applicable machines, TADs and tools are shown in Table 2; considering that machine tables can be rotated in the existing milling environment of the part, features of f₆, f₈, f₉ and f₁₀ can equivalently share the same TAD −a, and features of f₃ and f₄ can equivalently share the TAD −b. Precedence relations between the operations are shown in Table 3, and OPG of the part based on the precedence relations’ description in Table 3 is shown in Figure 5(b). Because it is in a limited machining environment, WRTT is the evaluation criterion; then w₁ = w₂ = w₃ = 1, w₄ = w₅ = 0; to do operation sequencing, if all the machines and tools are available, we set MCCI = 0.5, SCI = 0.3 and TCCI = 0.2.

Figure 5.

Case information and OPG of part 1: (a) a sample part with 15 machining features and (b) OPG of the part.

Table 2.

Features, operations and candidates’ information of part 1.

Features	F_name	op_name(op_id)	TAD_list[]	M_list[]	T_list[]
f 1	Planar surface	Rough turning (op1)	z	M1, M2, M3	T1, T2
f 2	Cylindrical surface	Rough turning (op2)	z	M1, M2, M3	T3, T4
f 3	External surface	Milling (op3)	−b	M4, M5	T5
f 4	Planar surface	Rough milling (op4)	−b	M4, M5	T6, T7
		Finish milling (op5)		M5
f 5	Spherical surface	Rough turning (op6)	−z	M1, M2, M3	T3, T4
		Finish turning (op7)		M3
f 6	Planar surface	Rough milling (op8)	−a	M4, M5	T6, T7
		Finish milling (op9)		M5
f 7	A through-hole	Center drilling (op10)	z, −z	M6, M7, M8	T8
		Twist drilling (op11)			T9
f 8	External surface	Milling (op12)	−a	M4, M5	T5
f 9	A chamfer	Milling (op13)	−a	M4, M5	T10
f 10	A groove	Rough milling (op14)	−a	M4, M5	T10, T11
		Finish milling (op15)		M5
f 11	A chamfer	Rough turning (op16)	z	M1, M2, M3	T1, T2
f 12	A chamfer	Rough turning (op17)	z	M1, M2, M3	T1
f 13	A hole	Center drilling (op18)	x	M6, M7, M8	T8
		Twist drilling (op19)			T12
f 14	A hole	Center drilling (op20)	−x	M6, M7, M8	T8
		Twist drilling (op21)			T13
f 15	Planar surface	Rough milling (op22)	−x	M4, M5	T6, T7
		Finish milling (op23)		M5

TAD: tool approach direction.

Table 3.

Precedence relations between operations of part 1.

Features	Operation (op_id)	Precedence relation description
f 1	op 1	f1 (op1) the datum and should be machined first
f 2	op 2	f2 (op2) is before f5 (op6, op7), f11 (op16) and f13 (op18, op19)
f 3	op 3	op3 is before f7 (op10, op11) for the material-removal constraint
f 4	op 4	op4 is before op5 for the fixed order of machining operations
	op 5	op5 is before f15 (op22, op23)
f 5	op 6	op6 is before op7 for the fixed order of machining operations
	op 7	op7 is before f8 (op12) and f3 (op3) for the feature priorities
f 6	op 8	op8 is before op9 for the fixed order of machining operations
	op 9	op9 is before f15 (op22, op23)
f 7	op 10	op10 is before op11 for the fixed order of machining operations
	op 11
f 8	op 12	f8 (op12) is before f10 (op14, op15) and f6 (op8, op9) for the feature priorities; op12 is before f7 (op10, op11) for the material-removal constraint
f 9	op 13
f 10	op 14	op14 is before op15 for the fixed order of machining operations
	op 15	op15 is before f9 (op13) for the feature priorities
f 11	op 16	f11 (op16) is before f10 (op14, op15)
f 12	op 17
f 13	op 18	op18 is before op19 for the fixed order of machining operations
	op 19	op19 is before f12 (op17) for the feature priorities
f 14	op 20	op20 is before op21 for the fixed order of machining operations
	op 21
f 15	op 22	op22 is before op23 for the fixed order of machining operations
	op 23

To determine key parameters of the modified ACO and verify the effectiveness of the proposed approach, the experiments are designed as follows.

Comparison of the two different approaches

In operation sequencing, the modified and traditional ACO are used, respectively, and the local search mechanism of them is RWA. Figure 6(a) shows the relations between running-time and execution-time/WRTT; when running 10 times in the same parameter settings, the execution times do not appear to be much different, but WRTT results show that the modified ACO has good performance. Meanwhile, Figure 6(b) shows the similar conclusion.

Figure 6.

Comparisons between modified and traditional ACO: (a) relations between running-time and execution-time/WRTT and (b) relations between iterations and WRTT.

How q₀, ξ and ρ influence the results

In the modified ACO, q₀, ξ and ρ play an important role for high-performance solution. To study their influences, other parameters are keep constant; set $\alpha =1,\beta =2,N_{max}=400,m=10$ . Then in the situation $\rho =0.1,\xi =0.1$ , Figure 7(a) and (b) shows the five iteration results using the modified ACO in which q₀ = 0.9 and 0.8, and the minimal WRTT is 7.1 and 7.2 and the corresponding number of iterations is 372 and 280. Figure 7(c) shows the five iteration results using the modified ACO in which $\rho =0.1,\xi =0.2$ and $q_0=0.9$ , the minimal WRTT is 7.3 and the corresponding number of iterations is 163. While Figure 7(d) shows the five iteration results using the modified ACO in which $\rho =0.2,\xi =0.1,q_0=0.9$ , the minimal WRTT is 7.3, and the corresponding number of iterations is 213. From these figures, it is shown that the minimal WRTT reduces with the increase in q₀ and raises with an increase in ξ or ρ. To get global optimal solution and avoid premature convergence, parameter setting in the situation of Figure 7(a) is a good choice; although it may need more iterations, better solutions can be acquired.

Figure 7.

Results in different parameter settings: (a) $\rho =\xi =0.1,q_0=0.9$ , (b) $\rho =\xi =0.1,q_0=0.8$ , (c) $\rho =0.1,\xi =0.2,q_0=0.9$ and (d) $\rho =0.2,\xi =0.1,q_0=0.9$ .

Obtaining the optimal process plans

The modified ACO has better performance than the traditional ACO; in the situation $\alpha =1,\beta =2,\rho =\xi =0.1,N_{max}=400,q_0=0.9$ and m = 10, two optimal process plans of part 1 are shown in Table 4.

Table 4.

Two optimal process plans of part 1.

Process plan 1
Order	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23
op_id	1	2	16	6	7	3	12	14	15	13	8	9	4	5	22	23	20	21	10	11	18	19	17
M_id	3	3	3	3	3	5	5	5	5	5	5	5	5	5	5	5	8	8	8	8	8	8	2
TAD	z	z	z	−z	−z	−b	−a	−a	−a	−a	−a	−a	−b	−b	−x	−x	−x	−x	−z	−z	x	x	z
T_id	2	3	1	4	4	5	5	10	10	10	6	6	6	6	6	6	8	13	8	9	8	12	1
Cm = 3, Cs = 10, Ct = 13, WRTT = 7.1
Process plan 2
Order	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23
op_id	1	2	16	6	7	3	4	5	12	14	15	13	8	9	22	23	10	11	20	21	18	19	17
M_id	3	3	3	3	3	5	5	5	5	5	5	5	5	5	5	5	8	8	8	8	8	8	1
TAD	z	z	z	−z	−z	−b	−b	−b	−a	−a	−a	−a	−a	−a	−x	−x	z	z	−x	−x	x	x	z
T_id	1	3	1	4	4	5	7	7	5	10	10	10	6	6	6	6	8	9	8	13	8	12	1
Cm = 3, Cs = 9, Ct = 15, WRTT = 7.2

TAD: tool approach direction; WRTT: weighted resource transformation time.

Case study 2

The second part (part 2, shown in Figure 8(a)) taken from Guo et al. ²⁴ consists of 11 manufacturing features, which can be machined with 14 operations. The relevant information of features, operations and applicable machines, TADs and tools are shown in Tables 5 and 6; precedence relations between the operations are shown in Table 7 and OPG of the part based on precedence relation description in Table 7 is shown in Figure 8(b). In this case, all the machines and tools are available, and w₁ = w₂ = w₃ = w₄ = w₅ = 1; TWPC is the evaluation criterion.

Figure 8.

Case information and OPG of part 2: (a) a sample part with 11 machining features and (b) OPG of the part.

Table 5.

Features, operations and candidates’ information of part 2.

Features	F_name	Op_name(op_id)	TAD_list[]	M_list[]	T_list[]
f 1	Planar surface	Milling (op1)	z	M2, M3, M4	T6, T7, T8
f 2	Planar surface	Milling (op2)	−z	M2, M3, M4	T6, T7, T8
f 3	A step	Milling (op3)	x, −x, y, −z	M2, M3, M4	T6, T7, T8
f 4	A step	Milling (op4)	x, −x, y, z	M1, M2, M3, M4	T2
f 5	A step	Milling (op5)	x, −x, −y, −z	M2, M3, M4	T6, T7, T8
f 6	A slot	Milling (op6)	x, −x, −y, z	M2, M3, M4	T7, T8
f 7	A slot	Milling (op7)	x, −x, −z	M2, M3, M4	T7, T8, T11
f 8	A slot	Milling (op8)	x, −x, −z	M2, M3, M4	T6, T7, T8, T11
f 9	A hole	Drilling (op9)	z, −z	M1, M2, M3, M4	T2, T3, T4
		Reaming (op10)		M2, M3, M4	T9
		Boring (op11)		M1, M2, M3, M4	T10
f 10	Four holes arranged as a replicated feature	Drilling (op12)	y, −y	M1, M2, M3, M4	T1
		Tapping (op13)		M2, M3, M4	T5
f 11	Four holes arranged as a replicated feature	Drilling (op14)	z, −z	M1, M2, M3, M4	T9

TAD: tool approach direction.

Table 6.

Available machining resources and costs for part 2.

Machines	MCI
M1 (drilling press)	10
M2, M3 (three-axis vertical milling machine)	40
M4 (CNC three-axis vertical milling machine)	100
M5 (boring machine)	60
Tools	TCI
T1 (drilling 1)	7
T2 (drilling 2)	5
T3 (drilling 3)	3
T4 (drilling 4)	8
T5 (tapping tool)	7
T6 (milling 1)	10
T7 (milling 2)	15
T8 (milling 3)	30
T9 (reaming tool)	15
T10 (boring tool)	20
T11 (slot cutter)	15
T12 (chamfer tool)	15
MCCI = 160, SCCI = 120, TCCI = 20

MCI: machine cost index; CNC: computer numerical control; TCI: tool cost index; MCCI: machine change cost index; SCCI: setup change cost index; TCCI: tool change cost index.

Table 7.

Precedence relations between operations of part 2.

Features	Operation (op_id)	Precedence relation description
f 1	op 1	f1 (op1) is the datum and should be machined first
f 2	op 2	f2 (op2) is before op3–op14 for datum constraint
f 3	op 3	op3 should be prior to op12–op14 for the material-removal constraint
f 4	op 4	op4 should be prior to op12–op14 for the material-removal constraint
f 5	op 5	op5 should be prior to op12–op14 for the material-removal constraint
f 6	op 6	op6 should be prior to op12–op14 for the material-removal constraint
f 7	op 7
f 8	op 8
f 9	op 9	op9 is before (op10 and op11); op10 is before op11 for the fixed order of machining operations; op9–op11 is before (op7 and op8) for datum constraint
	op 10
	op 11
f 10	op 12	op12 should be prior to op13 for the fixed order of machining operations
	op 13
f 11	op 14

In this case, the program will be repeatedly run for 10 times. Table 8 shows the optimal plan of part 2 with TWPC 1357, and the optimal process plan in the same condition for the same part reported in the work of Guo et al. ²⁴ is with the total production cost 1361. Table 9 shows the results’ comparison of the modified ACO, GA, SA and PSO of case 2; it can be seen that the proposed ACO is better than GA, SA and PSO in both best and mean TWPC.

Table 8.

An optimal process plan of part 2.

Order	1	2	3	4	5	6	7	8	9	10	11	12	13	14
op_id	1	2	3	5	9	10	11	8	7	6	4	14	12	13
M_id	2	2	2	2	2	2	2	2	2	2	2	2	2	2
TAD	z	−z	−z	−z	−z	−z	−z	−z	−z	z	z	z	y	y
T_id	6	6	6	6	3	9	10	7	7	7	2	9	1	5
Cm = 0, Cs = 4, Ct = 8, TMCC = 0, TSCC = 480, TTCC = 160, MC = 560, TC = 157, TWPC = 1357

TAD: tool approach direction; TMCC: total machine change cost; TSCC: total setup change cost; TTCC: total tool change cost; MC: machine cost; TC: tool cost; TWPC: total weighted production cost.

Table 9.

Result comparison of modified ACO, GA, SA and PSO of case 2.

Algorithm	Modified ACO	GA 24	SA 24	PSO 24
Best TWPC	1357	1381.0	1421.0	1361.0
Mean TWPC	1419	1459.4	1447.4	1430.0

ACO: ant colony optimization; GA: genetic algorithm; SA: simulated annealing; PSO: particle swarm optimization; TWPC: total weighted production cost.

Case study 3

To test the robustness of the algorithm, case study 3 (part 3, shown in Figure 9(a)) is taken from Guo et al. ²⁴ The part consists of 14 manufacturing features, which can be machined with 20 operations. The relevant information of features, operations and applicable machines, TADs and tools are shown in Tables 10 and 11; precedence relations between operations are shown in Table 12, and OPG of the part based on precedence relation description in Table 12 is shown in Figure 9(b). In this case, the results under two different conditions are studied: (1) all the machines and tools are available, w₁ = w₂ = w₃ = w₄ = w₅ = 1 and TWPC is the evaluation criterion. (2) All the machines and tools are available, and the MC, TSCC and TMCC are the main factors; w₃ = w₅ = 0, w₁ = w₂ = w₄ = 1; TWPC is the evaluation criterion.

Figure 9.

Case information and OPG of part 3: (a) a sample part with 14 machining features and (b) OPG of the part.

Table 10.

Features, operations and candidates’ information of part 3.

Features	F_name	op_name(op_id)	TAD_list[]	M_list[]	T_list[]
f 1	Planar surface	Milling (op1)	z	M2, M3	T6, T7, T8
f 2	Planar surface	Milling (op2)	−z	M2, M3	T6, T7, T8
f 3	Two pockets arranged as a replicated feature	Milling (op3)	x	M2, M3	T6, T7, T8
f 4	Four holes arranged as a replicated feature	Drilling (op4)	z, −z	M1, M2, M3	T2
f 5	A step	Milling (op5)	x, −z	M2, M3	T6, T7
f 6	A protrusion (rib)	Milling (op6)	y, −z	M2, M3	T7, T8
f 7	A boss	Milling (op7)	−a	M2, M3	T7, T8
f 8	A compound hole	Drilling (op8)	−a	M1, M2, M3	T2, T3, T4
		Reaming (op9)		M1, M2, M3	T9
		Boring (op10)		M3, M4	T10
f 9	A protrusion (rib)	Milling (op11)	−y, −z	M2, M3	T7, T8
f 10	A compound hole	Drilling (op12)	−z	M1, M2, M3	T2, T3, T4
		Reaming (op13)		M1, M2, M3	T9
		Boring (op14)		M3, M4	T10
f 11	Nine holes arranged as a replicated feature	Drilling (op15)	−z	M1, M2, M3	T1
		Tapping (op16)		M1, M2, M3	T5
f 12	A pocket	Milling (op17)	−x	M2, M3	T7, T8
f 13	A step	Milling (op18)	−x, −z	M2, M3	T6, T7
f 14	A compound hole	Reaming (op19)	z	M1, M2, M3	T9
		Boring (op20)		M3, M4	T10

TAD: tool approach direction.

Table 11.

Available machining resources and costs for part 3.

Machines	MCI
M1 (drilling press)	10
M2 (three-axis vertical milling machine)	40
M3 (CNC three-axis vertical milling machine)	100
M4 (boring machine)	60
Tools	TCI
T1 (drilling 1)	7
T2 (drilling 2)	5
T3 (drilling 3)	3
T4 (drilling 4)	8
T5 (tapping tool)	7
T6 (milling 1)	10
T7 (milling 2)	15
T8 (milling 3)	30
T9 (reaming tool)	15
T10 (boring tool)	20
MCCI = 160, SCCI = 100, TCCI = 20

MCI: machine cost index; CNC: computer numerical control; TCI: tool cost index; MCCI: machine change cost index; SCCI: setup change cost index; TCCI: tool change cost index.

Table 12.

Precedence relations between operations of part 3.

Features	Operation (op_id)	Precedence relation description
f 1	op 1	f1 (op1) is the datum and should be machined first
f 2	op 2	f2 (op2) is before f10 (op12, op13, op14) and f11 (op15, op16) for the material-removal constraint
f 3	op 3
f 4	op 4
f 5	op 5	f5 (op5) is before f4 (op4) and f7 (op7) for the datum and material-removal constraint
f 6	op 6	f6 (op6) is before f10 (op12, op13, op14) for the datum constraint
f 7	op 7	f7 (op7) is prior to f8 (op8, op9, op10) for the datum constraint
f 8	op 8	op8 is before (op9 and op10); op9 is before op10 for the fixed order of machining operations
	op 9
	op 10
f 9	op 11	f9 (op11) is before f10 (op12, op13, op14) for the datum constraint
f 10	op 12	op12 is before op13 and op14; op13 is before op14
	op 13	f10 (op12, op13, op14) is before f11 (op15, op16) for the datum constraint
	op 14	op12 is before f14 (op19, op20)
f 11	op 15	op15 is before op16 for the fixed order of machining operations
	op 16
f 12	op 17
f 13	op 18	f13 (op18) is before op4 and op17 for the material-removal constraint
f 14	op 19	op19 is before op20 for the fixed order of machining operations
	op 20

In condition 1, the program will be repeatedly run 10 times. Table 13 shows two optimal plans of part 3 with TWPC 2530, and the optimal process plan in the same condition for the same part reported in the work of Guo et al. ²⁴ with the total production cost 2535 is shown in Table 14. Table 15 shows an optimal plan in condition 2 of part 3 with TWPC 2090, and an optimal process plan in the same condition for the same part reported in the work of Huang et al. ⁸ with the total production cost 2120 is shown in Table 16. It can be seen that the proposed ACO can find better solutions.

Table 13.

Two optimal process plans of part 3 in condition 1.

Process plan 1
Order	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
op_id	1	3	2	5	18	6	11	12	13	19	17	7	8	9	20	14	10	15	16	4
M_id	2	2	2	2	2	2	2	2	2	2	2	2	2	2	4	4	4	1	1	1
TAD	z	x	−z	−z	−z	−z	−z	−z	−z	z	−x	−a	−a	−a	z	−z	−a	−z	−z	−z
T_id	6	6	6	6	6	7	7	3	9	9	7	7	3	9	10	10	10	1	5	2
Cm = 2, Cs = 10, Ct = 10, TMCC = 320, TSCC = 1000, TTCC = 200, MC = 770, TC = 240, TWPC = 2530
Process plan 2
Order	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
op_id	1	3	5	2	18	11	6	12	13	19	17	7	8	9	14	10	20	15	4	16
M_id	2	2	2	2	2	2	2	2	2	2	2	2	2	2	4	4	4	1	1	1
TAD	z	x	−z	−z	−z	−z	−z	−z	−z	z	−x	−a	−a	−a	−z	−a	z	−z	−z	−z
T_id	6	6	6	6	6	7	7	3	9	9	7	7	3	9	10	10	10	1	2	5
Cm = 2, Cs = 10, Ct = 10, TMCC = 320, TSCC = 1000, TTCC = 200, MC = 770, TC = 240, TWPC = 2530

TAD: tool approach direction; TMCC: total machine change cost; TSCC: total setup change cost; TTCC: total tool change cost; MC: machine cost; TC: tool cost; TWPC: total weighted production cost.

Table 14.

Optimal process plan of part 3 in condition 1 reported in Guo et al. ²⁴

Order	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
op_id	1	3	5	7	8	9	18	17	2	11	6	12	13	19	10	14	20	15	16	4
M_id	2	2	2	2	2	2	2	2	2	2	2	2	2	2	4	4	4	1	1	1
TAD	z	x	x	−a	−a	−a	−x	−x	−z	−z	−z	−z	−z	z	−a	−z	z	−z	−z	−z
T_id	7	7	7	7	3	9	7	7	7	7	7	3	9	9	10	10	10	1	5	2
Cm = 2, Cs = 10, Ct = 9, TMCC = 320, TSCC = 1000, TTCC = 180, MC = 770, TC = 265, TWPC = 2535

TAD: tool approach direction; TMCC: total machine change cost; TSCC: total setup change cost; TTCC: total tool change cost; MC: machine cost; TC: tool cost; TWPC: total weighted production cost.

Table 15.

Optimal process plan of part 3 in condition 2.

Order	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
op_id	1	18	17	11	6	2	12	13	19	5	3	7	8	9	20	14	10	15	16	4
M_id	2	2	2	2	2	2	2	2	2	2	2	2	2	2	4	4	4	1	1	1
TAD	z	−x	−x	−z	−z	−z	−z	−z	z	x	x	−a	−a	−a	z	−z	−a	−z	−z	−z
T_id	6	6	7	7	7	7	2	9	9	6	7	7	2	9	10	10	10	1	5	2
Cm = 2, Cs = 10, TMCC = 320, TSCC = 1000, MC = 770; TWPC = 2090

TAD: tool approach direction; TMCC: total machine change cost; TSCC: total setup change cost; MC: machine cost; TWPC: total weighted production cost.

Table 16.

Optimal process plan of part 3 in condition 2 reported in Huang et al. ⁸

Order	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
op_id	1	18	17	5	6	4	11	2	12	13	7	8	9	3	10	19	20	14	15	16
M_id	2	2	2	2	2	2	2	2	2	2	2	2	2	2	3	3	3	3	3	3
TAD	z	−x	−x	−z	−z	−z	−z	−z	−z	−z	−a	−a	−a	x	−a	z	z	−z	−z	−z
T_id	7	6	7	7	8	2	7	6	2	9	7	2	9	8	10	9	10	10	1	5
Cm = 1, Cs = 8, TMCC = 160, TSCC = 800, MC = 1160; TWPC = 2120

TAD: tool approach direction; TMCC: total machine change cost; TSCC: total setup change cost; MC: machine cost; TWPC: total weighted production cost.

Under conditions (1) and (2), Table 17 lists the best and mean TWPC achieved from 10 trials for part 3 by modified ACO, GA, SA, PSO and TS. It can be seen that the optimal process plan based on the modified ACO obtains lower best and mean TWPC than the results acquired by GA, SA, PSO and TS reported in the work of Li et al. ¹⁹ and Guo et al. ²⁴ Figure 10 shows optimization process based on 4000 iterations in condition 1 of the GA, SA, PSO and modified ACO for part 3; in the initial stage of the algorithms, the TWPC of GA falls faster than the SA, PSO and modified ACO. In the middle stage, GA converges while the TWPC of SA, PSO and modified ACO continue declining to get better solutions. And in the last stage, the modified ACO gets better result, which means the modified ACO are more robust to get optimal process plan.

Table 17.

Result comparison of modified ACO, GA, SA, PSO and TS of case 3.

	Algorithm	Modified ACO	GA 19	SA 19	PSO 24	TS 19
Condition (1)	Best TWPC	2530	2667	2535	2535	–
	Mean TWPC	2666	2796	2668.5	2680.5	–
Condition (2)	Best TWPC	2090	2220.0	2120.0	–	2120.0
	Mean TWPC	2115	2370.0	2287.0	–	2208.0

ACO: ant colony optimization; GA: genetic algorithm; SA: simulated annealing; PSO: particle swarm optimization; TS: tabu search; TWPC: total weighted production cost.

Figure 10.

Comparisons of the PSO, GA, SA and modified ACO for part 3.

Conclusion

In this article, an ACO-based approach for solving operation sequencing problem in CAPP has been developed. In order to obtain the optimal process plans, machining resources, constrained relationships among operations, setup plans determining and operation sequencing have been considered. The advantages of the proposed approach can be summarized as follows: (1) the approach can always acquire optimal or near-optimal process plans based on the TWPC. Through comparisons with other four algorithms, the proposed algorithm can get better results, and advantages of the approach are highlighted. (2) In condition of a limited machining environment especially when the cost index is uncertain, TWPC can be changed to WRTT, which can provide flexible optimization selection in practical workshop.

This article optimizes the sequences of operations limited to the considerations of machine changes, setup changes, tool changes, machines and tools. In the future, more research considering the optimization of the cutting parameters for each operation should be carried out in operation sequencing optimization. Meanwhile, the results of the proposed algorithm are related to key parameter settings of modified ACO, so at this point the conclusions are limited by computational experience, and more theoretical analysis should to be made. Regarding more complex parts, the features and constrained relationships are more complicated, which will greatly increase search space and computation time. Therefore, it should also be included in the future work to employ more efficient algorithm combined with ACO to improve operational efficiency and performance for more complex problems.