计算机辅助工艺设计（CAPP）是计算机集成制造（CIM）系统的重要组成部分。
一个好的计划可以通过优化得到的两个元素，即，操作顺序和机加工参数，刀具和工具的访问方向（TAD）为每个操作。
本文提出了一种新的工艺规划，考虑不同尺寸的问题在平行的优化策略。
一个多维的禁忌搜索（MDTS）基于该策略的算法来优化工艺方案的四个维度，即，操作序列（OperSeq），机序列（MacSeq），刀具序列（ToolSeq）和工具方法的方向顺序（TADSeq），顺序和反复。
为了提高其效率和稳定性，禁忌搜索，这是纳入到的建议MDTS 算法，用于优化工艺方案的每个组件，和不同的组件的一些邻居策略给出了禁忌搜索算法。
的建议MDTS算法来与不同数量的从文献和现有的算法，如遗传算法相比操作测试四个部分（GA），模拟退火（SA），禁忌搜索（TS）和粒子群优化（PSO）。
实验结果表明，该算法的性能优于这些算法在解决方案的质量和效率。
1 IntroductionComputer-aided process planning (CAPP) is an essential component of computer integrated manufacturing (CIM) system [1]. It links Computer Aided Design (CAD) andComputer Aided Manufacturing (CAM) by transforming a product design into a set of instructions (machines, tool,setups, etc.) [2]. During the past three decades, CAPP hasreceived much attention from researchers and numerous CAPP systems have been reported. These developed systems can be generally classified into two categories: variant system and generative system. The variant system utilizes group technology to store a standard part for each part family that is characterized by similarities in manufacturing methods. Process plans for a new part are created by recalling, identifying and retrieving an existing plan developed for a similar part stored in the system and then making necessary modifications. In contrast, generation of process plans in a generative system is based on decision logics,formulae, heuristic reasoning and the newly emerged artificial intelligence (AI) technologies. The generative system is attractive for companies with multi-varieties and small-batch products because process plan for a new part can be generated from scratch consistently and automatically. Although variant systems are more mature and widely adopted in industry, they suffer the deficiency in generating processplans of new product with many new features or structures, and labor under the disadvantage that the knowledge back-ground of a process planner greatly influences the quality of process plans [3–9]. In the last few decades, a significant number of generative systems have been developed to overcome these deficiencies, and this paper deals with the process planning problem in generative systems.Process planning in a generative system is concerned with conducting two major activities, namely, operation selection and operation sequencing, simultaneously. Operation selection is the act of determining necessary operations for each extracted feature of a given part to be machined and selecting suitable machine, cutting tool and tool access direction (TAD) for each operation based on the available manufacturing resources. Operation sequencing refers to the determination of optimal operation sequence under predefined precedence constraints among operations. Optimization of process planning requires solving these two sub- problems simultaneously. Liu et al. [10] modeled process planning as a constraint-based traveling salesman problem, which indicates thatoptimization of process planning is combinatorially intractable and efficient optimization strategy as well as search algorithm is necessary. The existing literature witnessed emerging applications of optimizationalgorithms to process planning problems in recent years. However, little efforts were made on the improvement of optimization strategy for process planning problem. In this paper, a novel optimization strategy is proposed to address the process planning problem and tabu search (TS) is utilized as the search algorithm to obtain optimal or near-optimal solutions in reasonable computational time. The arrangement of this paper is as follows. Section 2 reviews the existing researches on process planning problem. Section 3 formulates the process planning problem anddifferentiates the optimization strategy proposed in this paper from the existing approaches. The multi-dimensional tabu search algorithm is explained in detail in Section 4 and experiments are presented in Section 5. Conclusions are drawn in Section 6.2 Related workThe process planning problem has been extensively studied in recent years and numerous approaches, including heuristic and metaheuristic algorithms, have been proposed to obtain optimal or near-optimal solutions. Lee et al.[11] suggested optimal and heuristic branch and fathoming algorithms that could give optimal and near-optimal solutionsrespectively. Lee et al. [12] presented three iterative algorithms to solve the operation selection and operation sequencing iteratively until optimal and near-optimal solutions were obtained. In recent years, many metaheuristic algorithms have been applied to process planning problemdue to their superiority in solving combinatorial optimization problems. These algorithms can be categorized as genetic algorithm (GA) [13–21], simulated annealing (SA) [22, 2, 23], tabu search (TS) [24, 25], particle swarm optimization (PSO) [26] and ant colony optimization (ACO) [10].Zhang et al. [13] studied the process planning problem in job shop manufacturing environment and presented a CAPP model that considers various decision making activities simultaneously. GA was selected to obtain near-optimal process plans through specially designed genetic operators. Qiao et al. [14] used GA to optimize the operation sequencefor prismatic parts and four types of process planning rules were considered, namely, precedence rules, clustering rules, adjacent order rules and optimization rules. Alam et al. [16] reported a GA application in a real CAPP system named IMOLD_CAPP for the manufacture of injection moulds. Ding et al. [17] provided an optimization strategy for process planning based on multiple objectives and GA was incorporated with neural network and analytical hierarchical process to facilitate the definition of a globally optimized fitness function. Li et al. [18] studied the process planning problem in distributed manufacturing environments and GA was applied to generate optimal or near-optimal process plans. Hua et al. [20] proposed a GA-based synthesis approach for machining scheme selection and operation sequencing optimization. Salehi and Tavakkoli-Moghaddam [21] divided the process planning into preliminary planning and secondary and detailed planning. The aim of preliminary planning was to generate several feasible operation sequences using GA. Then in the detailed planning stage, the optimized operation sequence and the optimized selection of the machine, tool, and TAD for each operation were obtained using GA again.Ma et al. [2] described an approach that modeled the constraints of process planning problems in a concurrent manner and SA was developed to search for the optimal solution. Li et al. [22] developed a hybrid GA and SA approach to solve the process planning problem with constraints. The GA was carried out in the first stage to generate some good process plans. After that, the SA algorithm was employed to search for alternative optimal or near-optimal process plans based on a few plans selected from the process plans obtained in the first stage. Ma et al. [23] presented a CAPP system based on GA and SA. The developed system provided flexible optimizationcriteria that could satisfy the various needs from different job-shops and/or job-batches. Lee et al. [24] proposed 6 local search heuristics based on SA and TS to obtain good solutions for practically-sized process planning problems within a reasonable amount of computational time. Li et al. [25] developed and embedded a hybrid constraint-handling method in the TS-based optimization algorithm to conduct the search efficiently in a large-size constraint-based space. In their optimization model, costs of the utilized machines and cutting tools, machine changes, tool changes, setups and departure from good manufacturing practices (penalty function) are the optimization evaluation criteria. Guo et al. [26] implemented a PSO approach for optimization of operation sequencing in process planning. Initial process plans were formed and encoded into particles of the PSO algorithm which ‘flew’intelligently in the search space to achieve the best solution. New operators were developed to help PSO explore the search space comprehensively and avoid being trapped into local optima. Most recently, Liu et al.[10] proposed an ACO approach for the optimization of process planning. Firstly, the process planning problem is mapped to a weighted graph and is converted to a constraint-based travelling salesman problem. Then, the mathematical model for process planning problem is constructed by considering the machining constraints and goal of optimization. The ACO algorithm was employed to solve the mathematical model. Results of process planning are feasible process plans that are defined by a sequence of operations and various machining parameters (only machine, tool and TAD are considered in this paper) for each operation. In other words, a process plan has different dimensions. For the process planning problem studied in this paper, process plans have operation dimension and various parameter dimensions (machine dimension, tool dimension and TAD dimension). Operation dimension refers to the operation sequence by which a product is manufactured. And each parameter dimension refers to the parameter sequence selected for each operation. An examination of the existing literature listed above reveals that the algorithms developed for process planning follow the same optimization strategy: an operation together with its machining parameters (machine, tool and TAD) is treated as the basic element to be manipulated by various algorithms which aim at obtaining optimal operation sequence as well as optimal machining parameters for each operation. This optimization strategy is simple and straightforward to encode a process plan to a solution in an algorithm. However, it suffers from the following drawbacks: firstly, since operation and its machining parameters are integrated as a basic unit, algorithms could only search in the solution space of operation dimension. In other words, problem-specific operators must be designed to explore the solution space of machining parameters dimensions of each operation; secondly, there generally exist several machining parameters for each operation, the efficiency of algorithms that are designed for optimizing operation’s machining parameters deteriorates greatly when the number of parameters increases. Different form the existing optimization strategy that operates on the operation dimension of a process plan, this paper proposes a novel strategy that manipulates on operation dimension as well as machining parameters dimensions. Under this optimization strategy, TS is adopted as an underlying search algorithm that is responsible for search in each dimension of the process planning problem. The optimization strategy is further explained in Section 3 using an illustrative example and TS is elaborated in Section 4.3 Process planning problem3.1 Problem definition and illustration using an example part Process planning is concerned with solving two interrelated problems, namely, operation selection and operation sequencing, simultaneously. Operation selection refers to the determination of necessary operations for each manufacturing feature and the selection of machine, tool and TAD for each operation, while operation sequencing is the act of determining an optimal operations sequence subject to predefined precedence constraints among machine features. Process planning is NP-hard due to the numerous possibilities of operation sequence, alternative machining resources for each operation and the existence of complex precedence constraintsamong operations. A prismatic part taken from Zhang et al. [13] is used here to illustrate the process planning problem. This part consists of 5 machining features that could be mapped into 5 operations. The example part is shown in Figure 1 and the available machining resources are given in Table 1.Table 1 shows that there are 5 operations to be conducted for the prismatic part and there exist alternative machining resources for each operation. For example, operation 5 (milling) has one alternative machine (M1), two alternative tools (T2, T6) and two alternative TADs (+z, +y). In addition, the precedence constraints generally exist amongoperations of a process plan. They mainly come from geometric and manufacturing interactions between features as well as technological requirements to produce every feature with the best possible accuracy [13]. These interactions and technological requirements could be summarized as fixture interactions, tool interactions, datum interactions, thin-wall interactions, feature priorities, material-removal interactions and fixed order of machining operations [22]. The precedence constraints for the example part are given as follows: F1 must be drilled before F2, F2 must be machined before F4 and F4 must be drilled before F3. A feasible operation sequence (1, 5, 2, 4, 3) is shown in T able 2. In Table 2, each element in position i of the first row represents the i th operation of the final process plan and each element in the same position of the rest three rows indicates the selected machine, tool and TAD for the i th operation respectively.3.2 The proposed optimization strategyThe process plan shown in Table 2 is used in this section to further describe the proposed optimization strategy. Itcan be seen from Table 2 that a process plan is determined by different dimensions, namely, operation dimension and parameter dimensions (machine dimension, tool dimension and TAD dimension). In traditional optimization strategy developed for process planning, the three parameter dimensions are incorporated into the operation dimension to facilitate optimization of operation dimension. The existing optimization strategy encodes the process plan in Table 2 into a solution in metaheuristic algorithms as [(1, 2, 1, y), (5, 1, 6, +y), (2, 1, 2, +z), (4, 2, 3, z), (3, 1, 4, +y)]. Thefirst element of this encoding scheme represents an operation of the process plan and the rest elements indicate machining parameters of each operation. The existing optimization strategy tries to obtain optimal solutions in the operation dimension, that is, optimal operation sequence. Parameter dimensions are optimized to adapt to operation dimension. The optimization strategy proposed in this paper treats each dimension equally and optimizes different dimensions respectively. The encoded solution of the process plan in Table 2 under our new optimization strategy is [(1, 3,5, 4, 2), (2, 1, 1, 2, 1), (1, 2, 4, 3, 6), (y, +z, +y, z, +y)]. The encoding scheme will be fully explained in the following sections. It is easy to find the differences between the two encoded solutions using different optimization strategies. The optimization strategy considers the four dimensions of process planning equally. We name the four dimensions as operation sequence (OperSeq), machine sequence (MacSeq), tool sequence (ToolSeq) and TAD sequence (TADSeq). The optimization strategy proposed in this paper is based on the separate and iterative optimization of these four dimensions. In other words, in each iteration, the four dimensions are optimized to local optima sequentially and when one dimension is under optimization, theother three dimensions remain unchanged. These four Table 2 A feasible process plan of the example part Operation 1 5 2 4 3Machine 2 1 1 2 1Tool 1 6 2 3 4TAD y +y +z z +ydimensions construct a complete solution of the process planning problem at hand and each dimension cooperates with other dimensions to evaluate its fitness. 3.3 Optimization objectives In this paper, the total weighted cost (TWC) is employed to calculate the fitness of a process plan. The TWC consists of machine cost (MC), tool cost (TC), machine change cost (MCC), tool change cost (TCC) and setup change cost (SCC). Definitions of these costs are provided in Li, et al. [22] and therefore omitted here. The fitness function is computed by [22]1 2 3 4 5TWC w MC w TC w MCC w TCC w SCC, where ( 1, 2, ,5) iw i are the weights for different costs.3.4 Constraints-handling algorithmDue to the existence of various precedence constraints among operations, operation sequence that is generated randomly or manipulated by some search operators may be infeasible. This paper adopts the constraints-handling algorithm proposed by Tseng [27] to adjust infeasible solutions into feasible ones. This algorithm firstly constructs a binary-tree structure based on the precedence relationships among operations. And the feasible solution is obtained by inorderly traversing the binary tree. Notations used in the algorithm are [27]: P, operation sequence; g h, operation inthe hth position of P; r, root node point; l, leaf node point. Details of the constraints adjusting algorithm are described as follow:Step 1. Set h = 2.Step 2. Set gl’s corresponding operation at root nodepoint R.Step 3. Set gh’s corresponding operation at leaf node point l, and decide the precedence relationship of r and l.(1) If pr,l= 1, operation l should be machined before operation r.(a) If r’s left child node point is not empty, then set r’s leftnode point at the new root node point r and repeat Step 3.(b) If r’s left child node point is empty, then insert l at r’sleft node point. Set h = h +1 and go to Step 4.(2) If pr,l= 0, there is no precedence constraints betweenoperations r and l.(a) If r’s right node child node point is not empty, thenset r’s right node point at the new root node point r and goto Step 3.(b) If r’s right child node point is empty, then insert l atr’s right node point. Set h = h +1, and got to Step 4.Step 4. If h = m, go to Step 5; otherwise go to Step 2.Step 5. List feasible solutions according to the inordertraversal rank and stop the algorithm.4 The proposed multi-dimensional tabu search(MDTS) algorithm4.1 The rationaleIn recent years, metaheuristic algorithms have been extensively studied to solve various combinatorial optimization problems. Due to their combinatorial intractability, process planning has attracted researchers to employ metaheuristic algorithms to obtain optimal or near-optimal solutions with reasonable computational cost. As previous section indicates, solution to the process planning problem consists offour dimensions, namely, OperSeq, MacSeq, ToolSeq and TADSeq. Traditional optimization strategy mainly operates on the OperSeq and thus lacks efficiency in exploring Mac-Seq, ToolSeq and TADSeq. However, study of Moriarty and Miikkulainen [28] indicates that several parallel searches for different dimensions of the solution are more efficient than a single search for the entire solution. Metaheuristic algorithms designed based on this hypothesis include symbiotic evolutioanry algorithm (SEA) [29] and endosymbiotic evoluitoanry algorithm (EEA) [30] and have been sucessfully applied to address some scheduling problems including mixed model assembly balancing and sequencing [31], integrated process planning and scheduling [29], process planning [32] and mixed-model U-lines balancing and sequencing [30]. In both SEA and EEA, a separate population is maitained throughout the optimization process for each part of the solution to the problem at hand and additional efforts must be made to design specific cooperations among populations. In addition, maintenance of separate population for each solution component requires more computational time. Based on the above analysis, this paper proposes a multi-dimensional tabu search (MDTS) algorithm to address the process planning problem. The advantage of the proposed MDTS is twofold. First, a single individual is maintained for each dimension of the solution, which could greatly shorten the compuotational time; second, tabu search is utilized to optimize each of the four components, which ensures the efficiency and effectiveness of the proposed MDTS algorithm. Details of the proposedMDTS algorithm are described in the following sections. 4.2 The overall procedure of the MDTS algorithm In the proposed MDTS algorithm, we use OperSeq, MacSeq, ToolSeq and TADSeq to represent the individualmaintained for each component of the solution to the process planning problem. Initially, each individual is generated randomly and assigned to a fitness value. Note that in the problem considered here, the fitness of each individual equals the TWC that is calculated by combining the four individuals to form an entire solution. The overall procedure of the MDTS algorithm is depicted by Figure 2. Procedures of the proposed MDTS algorithm could also be depicted using the following pseudo-code:1) If the termination criterion is not met, repeat the following steps:2) Apply TS to optimize OperSeq and keep MacSeq, ToolSeq and TADSeq unchanged.3) Apply TS to optimize MacSeq and keep OperSeq, ToolSeq and TADSeq unchanged.4) Apply TS to optimize ToolSeq and keep OperSeq, MacSeq and TADSeq unchanged.5) Apply TS to optimize TADSeq and keep OperSeq, MacSeq and ToolSeq unchanged.Note that Figure 2 describes a single iteration of the MDTS algorithm and each oval in Figure 2 indicates one or more steps of tabu search. To be specific, at each iteration one or more steps of tabu search are executed to move one solution dimension (OperSeq, MacSeq, ToolSeq and TAD-Seq) to its neighborhoods. While one dimension progresses, it cooperates with other dimensions to calculate and update its fitness. For example, when the fitness of OperSeq is to be calculated, MacSeq, ToolSeq and TADSeq are selected to cooperate with OperSeq to construct a complete solution.Note that while one dimension is under optimization, the other three dimensions remain unchanged. This process is carried out sequentially for all the solution components. When all the solution components are updated, a cycle completes. The cycle is repeated until the stopping criterion is satisfied. The workflow of the proposed MDTS algorithm is given below and shown in Figure 3.Step 1. Initialize a process plan by randomly generating its OperSeq, MacSeq, ToolSeq and TADSeq. Set the maxi-mum iteration number MaxIter = N and the current iteration CurrIter = 0.Step 2. Initialize a separate tabu list for OperSeq, MacSeq, ToolSeq and TADSeq respectively.Step 3. Conduct the following steps sequentially:a) OperSeq′= TabuSearch (OperSeq, NumOper).b) MacSeq′= TabuSearch (MacSeq, NumMac).c) ToolSeq′= TabuSearch (ToolSeq, NumTool).d) TADSeq′= TabuSearch (TADSeq, NumTAD).e) CurrIter = CurrIter+1.Step 4. If CurrIter>MaxIter, then stop. Otherwise, go toStep 2.In the procedure described above, the function of TabuSearch (parameter 1, parameter 2) is the tabu search algorithm that is used to optimize the four dimensions of process planning problem. TabuSearch (abbreviation for tabu search) receives two parameters, namely, parameter 1 for the individual to be optimized and parameter 2 for the number of steps to be conducted and returns the optimized individual. Note that, tabu search could be replaced by other efficient heuristic algorithms to construct new algorithms. Details of tabu search are elaborated in the next subsection.4.3 The tabu search algorithm The proposed MDTS algorithm employs tabu search to explore the search space of OperSeq, MacSeq, ToolSeq andTADSeq sequentially and iteratively. The tabu search implemented in the proposed MDTS algorithm takes the forms: output=TabuSearch (parameter 1, parameter 2); parameter 1 represents the individual to be optimized; parameter 2 is the number of steps that tabu search is executed. The word “Output”in Figure 4 represents the optimized individual for parameter 1. Details of the tabu search algorithm are described as fol-lows and in Figure 4. Step 1. Assign parameter 1 to the current solution (Curr- Sol). Take parameter 2 as the maximal number of steps (MaxIter) that tabu search will be executed. Let iter = 0. Step 2. Evaluate currentsolution’s fitness by combining it with the other three individuals to form an entire process plan. Assign the current solution to elite solution (EliteSol).Step 3. Generate Nsnumber of neighborhood solutions of the current solution. Evaluate their corresponding fitness by combining each of them with the other three individuals. Choose the best neighborhood solution as the candidatesolution (CandSol). Step 4. If the candidate solution CandSol is better than the elite solution EliteSol, replace the current CurrSol and elite solution EliteSol with the candidate solution CandSol. Add CandSol into the tabu list. Then go to Step 6; otherwise go to Step 5Step 5. If the candidate solution CandSol already exists in the current individual’s tabu list, choose the best neighborhood solution that is not in the tabu list as the candidate solution. Add the candidate solution CandSol to the tabu list and use it to replace the current solution.Step 6. Let iter = iter + 1. If iter>parameter 2, return the current solution CurrSol as the Output. Otherwise, go to Step 3.4.4 Encoding schemeThe process plan given in Table 2 is used here to elaborate the encoding scheme. The encoded process plan is shown in Table 3. The first row in Table 3 indicates the operation number of the process plan. Each column represents an operation with its corresponding machine, tool and TAD. Note that OperSeq indicates the position of an operation in a process plan. For example, operations 1–5 locate in the 1, 3, 5, 4, 2 of the process plan given inTable 2, so the OperSeq is made up of (1, 3, 5, 4, 2). MacSeq, ToolSeq and TADSeq store the information of the operation that the operation number indicates.4.5 Neighborhood structures4.5.1 Neighborhood structure of OperSeqThe neighborhood structure of OperSeq includes Insert and Swap proposed by Li et al. [22]. Insert is to pick one element in the OperSeq randomly and insert it into another position. Swap means to exchange the position of two randomly selected elements of OperSeq. These two neighborhood structures are depicted in Figure 5.4.5.2 Neighborhood structure of MacSeq, ToolSeq andTADSeqThe same neighborhood structure named “single pointmutation”is applied to MacSeq, ToolSeq and TADSeq toobtain neighborhood solutions. It involves selecting a random element from MacSeq, ToolSeq and TADSeq and replaces it with another candidate value. The neighborhood structure of MacSeq, ToolSeq and TADSeq is shown in Figure 6.5 ExperimentsIn this section, the performance and search capability of the proposed MDTS are validated using four parts taken from literature. Parameters of the proposed MDTS algorithm include size of tabu list (Ns), number of steps for OperSeq,MacSeq, ToolSeq and TADSeq (NOper , Nmac, Ntool and N TAD)and maximal number of iteration (MaxIter). Preliminary experiments showed that the following setting provides good results: Ns= 20, Noper= 5, Nmac= Ntool=NTAD= 10 and MaxIter = 200.5.1 Experiment 1A prismatic part (Part 1) taken from Li et al. [22] is firstly used to test the proposed algorithm. Part 1 consists of 14 manufacturing features and 20 operations. Computational experiments are conducted under the following two conditions to demonstrate the advantages of the proposed MDTS to the existing approaches in literature including GA, SA, TS and PSO.1) All machines and tools are available, and w1-w5 in the equation given in Section 3.3 are set as 1.2) All machines and tools are available, and w2=w5=0,w1=w3=w4=1.Under conditions (1) and (2) described in Table 4, 50independent trials were conducted to evaluate the proposed MDTS lgorithm’s performance for Part 1. Table 4 lists the computational results of MDTS, GA, SA, TS on Part 1 under two different conditions. Comparison of MDTS with PSO under condition (1) is also presented. For each algorithm under each condition, 50 trials were conducted to obtain the mean objective value, maximum objective value and minimum objective value. From the observations of Table 4 under conditions (1) and (2), our proposed algorithm has obtained lower mean, maximum and minimum costs. Figure 7 illustrates the optimization process of the proposed MDTS and GA, SA, TS. It can be seen from the figure that GA is prone to local optima in the early stage, SA performs better than GA and TS is superior to both GA and SA. The proposed MDTS outperformed GA, SA and TS both in computational time and efficiency.5.2 Experiment 2The second part used by Li et al. [25] consists of 14 features and 14 operations. Two conditions are considered for studies on this part. 1) All machines and tools are available, and w1w5 in theequation given in Section 3.3 are set as 1.2) All machines and tools are available, and w2=w5=0,w1=w3=w4=1.Table 5 lists the computational results in terms of mean objective value, maximum objective value and minimum objective value of 50 runs. The results of MDTS are based on 50 independent runs with randomly generated initial plan. Results of GA, SA and TS are obtained from Li et al. [25]. It can be seen from Table 5 that results obtained by the proposed MDTS with that obtained previously by Li et al. [25] for the lowest machining cost under conditions (1) and (2) are the same; but the mean and maximum machining costs under both conditions obtained by our proposed MDTS outperform GA, SA and TS. Figure 7 Comparison of MDTS with GA, SA and TS. 5.3 Experiment 3 The third part presented by Ma et al. [2] consists of 9 features and 13 operations. The following two conditions are considered for studies on Part 3.1) All machines and tools are available;2) M2 is down.Computational results of MDTS and SA under the two conditions are listed in Table 6. Table 6 shows that the proposed MDTS algorithm can find better solutions in both conditions.5.4 Experiment 4。
