1 Introduction

Computer-aided process planning (CAPP) is an important link between computer-aided design (CAD) and computer-aided manufacturing. The main task of CAPP is to transform the part design specifications from CAD system into the process plan for manufacturing the parts in the shopfloor. Process planning (PP) as the main function of any CAPP system is critical to reduce the processing time or the production cost of parts in machining industry. The main steps of PP comprise operation selection, resource allocation, and operation sequencing [1]. Operation sequencing (OS) is the last and most crucial step for obtaining a feasible process plan observing the precedence constraints and achieving the expected aim [1]. In the era of Industry 4.0, OS is frequently encountered owing to the rapid change of customized products. Therefore, efficient and effective methods for OS are of great importance for fabricating customized parts. This paper focuses on OS problem, which is similar to the PP problem mentioned in [1, 2]. The task of OS is to decide the sequence of machining operations and select machine tool, tool access direction (TAD), and cutting tool for every operation. A good sequence of operations can reduce the cost/time in the production process [3].

Due to the NP-hard essence of OS problem and the complexity resulting from precedence constraints among operations, it is difficult to design exact approaches to solve mid-to-large-scale OS/PP problems. Therefore, various metaheuristic algorithms (MAs) including genetic algorithm (GA), ant colony optimization (ACO), and particle swarm optimization (PSO) have been utilized to find near-optimal solutions in a limited time. As we all known, solution encoding is critical to MAs and is directly related to search-space size. Almost all of previous works [4,5,6] merged the operation sequence with corresponding candidate manufacturing resources for solution encoding, which makes the search space very large. For that encoding, the search-space size is bounded by (n!∙mn), where n is the number of operations and m is the number of candidate resources for every operation. It is shown that the MAs have more chance to hit global optimums for a relatively small search space [7]. Given any operation sequence, if we can find the corresponding optimal resource allocation with minimal machining cost, we can focus on searching operation sequences, which will dramatically reduce search-space size. If we only encode the feasible operation sequences (FOSs) which satisfy the precedence constraints of operations, the resultant search-space size is bounded by (n!). Except for the strategy of reducing search space, another common strategy to improve the MAs is combining them with the local search to enhance global search ability. Path-relinking (PR) can be used as such a local search, which performs well in many combinatorial optimization problems [8,9,10]. Originally, PR is an alternative way like crossover to generate a new solution by connecting the paths of two high-quality solutions. In this study, PR serving as local search is used to enhance a basic GA, which explores paths between elitist solutions found by GA.

To our best knowledge, few studies combine PR with MAs to solve OS problems. In this paper, we made one of the first attempts to solve OS/PP problem by incorporating PR into the widely used MA named GA, and to perform the search within a relatively small search space which is composed of all FOSs. A new GA with PR has been proposed to solve the OS problem, which is compared with state-of-the-art algorithms including ACO, PSO, two recent GAs, and a recent exact method [1] to verify its effectiveness.

The remainder of this paper is as follows. Section 2 presents the related literature review. Section 3 describes the OS problem. Section 4 introduces the proposed PR-GA. Section 5 reports the computational and comparison results. Section 6 gives conclusion and future research.

2 Literature review

2.1 Metaheuristic algorithms for OS

Owing to the NP-hard essence of OS problem, the exact methods based on mathematical models [1] are applicable to small-to-middle-sized OS problems. Various MAs have been utilized to tackle mid-to-large-scale OS problems, which include GA [11,12,13], simulated annealing (SA) [14, 15], tabu search [16], ant colony optimization (ACO) [2, 5], and particle swarm optimization (PSO) [3, 17, 18]. Some relatively new MAs including honey bee mating optimization [4], cuckoo search [19], and water drop algorithm [20] have also been applied to OS problem. In addition, some hybrid MAs [19, 21,22,23,24,25] have also been utilized to solve the OS/PP problem.

Among aforementioned MAs, GA is the first one applied to the OS problem. In recent years, GA has been frequently used and shown competitive performance [26, 27] for solving OS problems. In this study, the GA is adopted and enhanced for solving OS problem. In the following, we focus on the review of application of GA to OS problems.

2.2 Genetic algorithms for OS

To solve OS problems by the MA such as the GA, the treatment of precedence constraints of operations is critical [16, 27]. Different encoding and constraint handling methods have been developed [6, 16, 27]. So far, there are many works on application of GA to OS problems.

Usher and Bowden [11] and Yip-Hoi and Dutta [12] made early attempts to solve OS problem by GA. They encoded the operation sequences indirectly based on feature precedence graph, and designed crossover and mutation to keep the feasibility of sequences. Zhang et al. [28] represented the solution by a string including operation sequence and related machining resource to minimize total cost. They designed a cyclic crossover for altering operation sequences and uniform mutations for changing TADs, machines, and tools, so as to involve solutions in feasible solution space. Unlike previous GAs’ searching in feasible solution space, some researcher adopted penalty method to handle precedence constraints. Reddy [29] developed a GA to find the optimal operation sequence with minimal cost from a given cost matrix. They penalized the unfeasible operation sequences produced by mutation. Ding et al. [30] adopted the same encoding method as in [29] and used the penalty method to remove unfeasible solutions resulting from crossover and mutation. Salehi and Tavakkoli-Moghaddam [31] employed the penalty method to eliminate the unfeasible sequences produced by swap mutation. Differing from above penalty method, repair procedure for unfeasible solution are preferred by some researchers. Li et al. [21] proposed a hybrid GA and SA for OS problem, and developed a repair procedure to fix unfeasible operation sequences produced by the mutation. Mohapatra et al. [32] considered multiple-objective optimization of OS problem, and devised a repair procedure to fix the FOS generated by crossover. Huang et al. [33] developed another hybrid GA-SA for OS in a dynamic workshop environment, and utilized a stochastic topological sort method to fix the unfeasible operation sequences produced by genetic operators.

In recent years, the prevailing constraint-handling method is directly searching in feasible solution space associated with FOSs by special devised genetic operators. As aforementioned, Usher and Bowden [11] and Yip-Hoi and Dutta [12] adopted indirect encoding of FOS. By contrast, Zhang et al. [28] encoded a FOS directly by a string and recorded machines, tools, and TADs for every operation in the chromosome. Yun and Moon [34] directly recorded the FOS by a permutation which is obtained by topological sorting (TS) procedure, and devised the moon crossover along with the insert mutation to alter chromosomes. Yun and Moon [34] have indicated that the GA with direct encoding of FOS is better than the GA with priority-based indirect encoding of FOS. Yun et al. [24] extended the GA [34] by adding an iterative hill climbing as adaptive local search method to handle complicated precedence constraints. Yin et al. [35] adopted direct encoding of FOS and used the same crossover operator as Reddy [29] to obtain the best operation sequence with the minimal sum of carbon emission and cost. Su et al. [25] proposed a hybrid GA with local search to optimize process plan for turning machine tool, and employed order crossover and fragment mutation to involve FOSs. Su et al. [26] developed an edge selection (ES)-based encoding strategy and related order crossover to ensure the feasibility of chromosomes in which a FOS is directly represented by a permutation. In addition, a greedy-fashion mutation was developed to change and optimize the manufacturing resources for every operation. Dou et al. [6] presented an improved GA with a fragment crossover and an adaptive fragment mutation, together with a new elitist-based crossover strategy, to evolve chromosomes in feasible solution space. Falih and Shammari [27] developed a constrained permutation algorithm to generate optimized FOSs, and then devised a mixed crossover operator including three-string crossover and order crossover to involve operation sequences. The crossover for FOS and the mutation for resources both maintain the feasibility of chromosomes. Luo et al. [36] proposed a hybrid algorithm combining GA and variable neighborhood search for process sequencing optimization, in which the GA is used to find best solution among different neighborhood spaces. The designed crossover and mutation makes GA search in feasible solution space. The characteristics of GAs for OS problem in the past decade are presented in Table 1.

Table 1 Recent works of application of GA to OS problem
Full size table

From above review, it can be seen that different encodings and related genetic operators are proposed to handle the precedence constraints of operations. There are three main ways to handle the precedence constraints. One way is utilizing additional repair procedure to fix operation sequences violating precedence constraints [21, 32, 33, 37]. Another way is adopting penalty method to eliminate unfeasible sequences [30, 31, 37]. One convenience of previous two ways is that the crossover and the mutation for permutation can be directed adopted to evolve the chromosomes of GA. However, the penalty method suffers from relatively large search space including unfeasible solution space, while additional repair method requires more computation time and reduce the search efficiency.

In recent years, most of researchers [6, 24,25,26,27, 36] prefer the constraint-satisfaction way which ensures GA searching in feasible solution space by genetic operators specially designed. One merit of constraint-satisfaction way is that search-space size is relatively small, and therefore, the chance of hitting global optimum is relatively high for the GA which is essentially a stochastic search algorithm. That method is also adopted in the PR-GA presented in this paper. Except for constraint-handling, existing works of GAs for OS problem have shown that the GA combining with local searches such as iterative hill climbing [24] and SA [21, 23, 24, 33] have promising performance for the OS problem with complicated precedence constraints or large-sized problem. In this paper, an effective local search named path-relinking has been embedded into the GA.

2.3 Path-relinking

PR was first proposed by Glover [37] as a scatter search technique. PR is an enhanced strategy that explores better solutions connecting the paths between a pair of reference solutions. PR performed well in solving many difficult problems, such as the project scheduling [38], the unconstrained binary quadratic optimization problem [9], the cluster travel salesman problem [39], and the multiple-level warehouse layout problem [8]. The works [8, 38, 39] both combined GRASP with PR, and employed PR to improve elite solutions found by GRASP. Zhang and Lai [8] combined PR with GA for the multiple-level warehouse layout problem, and utilized PR as either replacing crossover of GA or improving the global search ability of GA (function as a local search). Muritiba et al. [40] proposed a PR with tabu search for the capacitated centered clustering problem, and uses the PR as a local search.

In the field of operation and management of manufacturing system, Reeves and Yamada [41] applied the PR to GA to solve the flowshop sequencing problem (FSP), where the PR is as an alternative of crossover or mutation. Yang et al. [10] have taken PR as algorithm framework to solve the two-sided assembly line balancing problem. They utilized multi-neighborhood-based PR algorithm repeatedly to generate new offspring solutions, and adopted a local search to optimize the newly generated offspring solutions.

To the authors’ best knowledge, the PR has been seldom applied to OS problem. This paper embeds the PR into the GA process in order to strengthen the exploitation of intermediate solutions.

2.4 Research gaps and contributions

Although different MAs have been proposed for solving different OS problems, the encoding along with corresponding precedence constraint handling and the evolution/update mechanism of MAs remain to be explored, so as to improve global search ability. According to above review, among the precedence constraint handling methods of existing GAs, the constraint-satisfaction method is observed to exhibit the merit of small size of search space and promising performance. Another observation is that the local search is an effective way to improve GA’s performance with respect to solution quality. The last observation is that some researchers tried to avoid tuning GA’s parameters, e.g., mutation rate, by adaptive mutation rate, so as to reduce the effect of GA parameters on GA’s performance. For solving complex or mid-to-large OS problems by GA based on constraint-satisfaction method, however, there are still open questions as follows:

  1. (1)

    What are promising encoding method and related suitable genetic operators?

  2. (2)

    How to eliminate the effect of GA parameters such as crossover or mutation rates on the performance of GA for solving OS problem?

  3. (3)

    How to combine a suited local search with the GA so as to balance computation efficiency and global search ability?

To explore answers to above questions, this paper designs a path-relinking GA (PR-GA) to solve the OS problem in CAPP. For the purpose of comparison, the features of the proposed PR-GA are summarized in Table 1. The main contributions of this paper are as follows. First, we only encoded the FOS as GA’s chromosome to reduce search space, and proposed a graph algorithm with polynomial-time complexity to identify minimal-cost machining resources for a given FOS. Second, we proposed a new GA evolution framework in which the Hamming distance is used as the judgment for individual crossover or mutation, which avoids tuning mutation and crossover rates. Third, we incorporated path-relinking into GA to improve the global search ability. The effectiveness and superiority of the PR-GA are verified by comparing with state-of-the-art algorithms such as ACO, PSO two recent GAs, and a newly developed exact method [1] based on mixed integer linear programing (MILP) model.

3 Problem statement

3.1 Operation sequencing problem

The operation sequencing is the core function of any generative CAPP system which is a bridge linking design and manufacturing of the parts. In the CAPP system, OS have to be resolved after recognition of operations for a part based on part machining features. The task of OS is to determine the sequence of operations observing the precedence constraints among machining features, and to decide manufacturing resources for each operation in the operation sequence. The aim of OS under consideration is to reduce the total machining cost.

As aforementioned, the treatment of precedence constraints of operations that come from geometrical and technological considerations is critical to solve OS problems by the MA. An operation precedence graph (OPG) is utilized to depict the precedence constraints of operations. OPG is a directed graph in which each node represents an operation, as shown in Fig. 1. If there is an arc starting with node i and ending to node j in the digraph, it means that node i should be processed before node j. An operation sequence that satisfies the precedence constraints of operations is called a FOS. For any feasible process plan, the operation sequence must be a FOS.

Fig. 1
figure 1

Operation precedence graphs of two parts

Full size image

As for selecting manufacturing resources for every operation of a FOS, there are usually several optional machine tools, cutting tools, and related TADs and setups. A setup is a set of operations machined on a machine tool using the same TAD. After designating the machine tool, the cutting tool, and the TAD for every operation in a FOS, a process plan for machining a part is determined.

3.2 Objective function

The goal of OS here is to find the process plan with the minimal machining cost. Here, the machining cost can be either monetary cost or time cost. For the purpose of comparison, the widely used computing model of machining cost [1, 18, 26] is adopted, which comprise five components: machine utilization cost, tool utilization cost, machine change cost, tool change cost, and setup change cost. The following notations are introduced to compute the machining cost:

N:

Number of operations.

M:

Number of available machine tools.

T:

Number of available cutting tools.

op[i]:

Operation i, i = 1,2 …, N

op[i].MID:

ID of optional machine for operation i.

op[i].TID:

ID of optional tool for operation i.

op[i].AID:

ID of optional TAD for operation i.

CM[m]:

Cost index of machine tool m, m = 1,2 …, M

CT[t]:

Cost index of cutting tool t, t = 1,2 …, T

CS:

Cost index of setup.

CMC:

Cost index of machine change.

CTC:

Cost index of tool change.

MCCI:

Machine-change cost index.

TCCI:

Tool-change cost index.

SCI:

Setup cost index.

For the purpose of comparison, we assume that MCCI, TCCI, and SCI are the same for each machine change, each tool change, and each setup, respectively, as did in existing works [6, 26, 27]. In fact, the following proposed PR-GA are applicable for the situations that the MCCI, TCCI, and SCI are different for each machine change, each tool change, and each setup.

To calculate relevant costs, the following comparison operator is utilized, where both X and Y are integers representing the IDs of manufacturing resources such as machines and tools.

$$\phi_1(X,Y)=\left\{\begin{array}{l}1,X\neq Y\\0,X=Y\end{array},\phi_2(X,Y)\right.=\left\{\begin{array}{lc}0,&X=Y=0\\1,\,&\,\,\text{other}\end{array}\right.$$
(1)
  1. (1)

    The total machine cost (TMC): total cost of the machine tools utilized in a process plan, and is computed as follows:

    $$TMC=\sum_{i=1}^{N}CM\left[op\left[i\right].MID\right]$$
    (2)
  2. (2)

    The total tool cost (TTC): total cost of the cutting tools utilized in a process plan, and is computed as follows:

    $$TTC=\sum_{i=1}^{N}CT[op[i].TID]$$
    (3)
  3. (3)

    The total machine change cost (TMCC): TMCC equals MCCI multiplying the number of machine changes (NMC).

    $$NMC=\sum_{i=1}^{N-1}{\phi }_{1}(op[i].MID,op[i+1].MID)$$
    (4)
    $$TMCC=NMC\times CMC$$
    (5)
  4. (4)

    The total tool change cost (TTCC): TTCC equals TCCI multiplying the number of tool changes (NTC).

    $$NTC=\sum_{i=1}^{N-1}{\phi }_{2}\{{\phi }_{1}(op[i].MID,op[i+1].MID),{\phi }_{1}(op[i].TID,op[i+1].TID)\}$$
    (6)
    $$TTCC=NTC\times CTC$$
    (7)
  5. (5)

    The total setup cost (TSC): TSC equals SCI multiplying the number of setups (NS).

    $$NS=1+\sum_{i=1}^{N-1}{\phi }_{2}\{{\phi }_{1}(op[i].MID,op[i+1].MID),\text{\hspace{0.17em}}{\phi }_{1}(op[i].AID,op[i+1].AID)\}$$
    (8)
    $$TSC=NS\times CS$$
    (9)

On the basis of above costs, the machining cost is computed as follows:

$$TC={\omega }_{1}TMC+{\omega }_{2}TTC+{\omega }_{3}TMCC+{\omega }_{4}TSC+{\omega }_{5}TTCC$$
(10)

where ω1 ~ ω5 are the weights of corresponding cost terms.

4 Genetic algorithm with path-relinking

4.1 Encoding of solution

The process plan to be determined for machining the parts includes two portions. One is the sequence of operations, i.e., the FOS. The other is the resources used for each operation, including the machine, the tool, and the TAD. To find the ‘optimal’ process plan by GAs, almost all researchers directly encode the sequence of operations and the corresponding resources of every operation. Naturally, the sequence of operations and the resources corresponding to each operation evolve together during the search process of GAs.

In this study, we only encode the FOS of the process plan by a permutation of n numbers in the PR-GA, as shown in Fig. 2(b). Then, we devise a graph algorithm to find the resources for each operation with minimal cost for a given FOS. In this way, the uncertainty of resources assignment for every operation resulting from the stochastic search essence of GA is eliminated. Moreover, the search space size of the proposed PR-GA is dramatically reduced comparing to existing GAs which directly search the operation sequences and related resources. It is believed that the MAs such as the GAs have more chance to hit global optimums for a relatively small search space.

Fig. 2
figure 2

An example of OS solution

Full size image

Based on above permutation encoding of FOS, the initial population are randomly generated by the TS procedure [34] for OPG which ensures every permutation a FOS.

4.2 Graph algorithm for finding minimal-cost resources for given sequences

Given a FOS, a graph model along with related dynamic programming procedure, called graph algorithm hereinafter, is developed to find the optimal resource assignment. An example is used to illustrate the graph algorithm.

Example: Given an operation sequence: OP1- > OP2- > OP3, the alternative machines, tools, and TADs for each operation are shown in the following Fig. 2(a). According to the information in Fig. 2(a), the solution graph model as shown in Fig. 2(c) can be constructed.

The graph model shown in Fig. 2(c) contains the midpoints and two virtual nodes. Each midpoint carries the information of machine, tool, and TAD selected in the operation step. All midpoints are listed by combining the machines, tools, and TADs that can be selected for each operation. The midpoint is layered according to the order of the operation, representing all possible resource choices of the operation.

Assuming that there are n operations in the FOS, and there are p kinds of machines, q kinds of tools, and w kinds of TADs for each operation (in previous example, p, q, are w are all less than 5), the procedure of building graph model is as follows:

Procedure: Graph-model building

  • Step 1. For each operation i (1,2…,n), initialize midpoints for all possible resource selections. All midpoints are listed by combining the machines, tools, and TADs that can be selected for each operation. Initialize i = 1;

  • Step 2. Connect the midpoints at layer i and layer i + 1 pair by pair (i = 1, …, n), and compute the weight of each edge.

  • Step 3. Let i = i + 1; if i < n, go to step 2;

  • Step 4. Connect the virtual start point with middle points for operation 1;

  • Step 5. Connect middle points for operation n with the virtual end point.

In above step 1, without loss of generality, we assume that there are K = p × q × w midpoints for each operation. In steps 2 and 4, the weight of each edge is defined as the sum of MC, TC, MCCI, TCCI, and SCI at the right node of the edge, and the three exchange costs MCCI, TCCI, and SCI are determined by comparing the machine, the tool, and the TAD at both nodes of the edge. In step 5, the weights of edges are set as zero. From above procedure, we know that the complexity of the modeling stage is nK + 2 K + (n − 1) K2, i.e., O(nK2).

By constructing the graph model, the problem of finding a given operation sequence’s minimal machining cost becomes the problem of finding the shortest path between two virtual nodes. The Dijkstar algorithm and dynamic programming algorithm are widely used algorithms for finding shortest path on digraph. Here, the idea of dynamic programming (DP) is applied to recursively step by step to find the path with minimal cost from the start node to the end node owing to DP’s efficiency on the special digraph constructed by graph-model building procedure.

The recurrence formula is as follows:

$$\mathrm{Cos}{\text{t}}[i+1]=\mathrm{Cost}[i]+\mathrm{min}\{edge[i,i+1]\}$$
(11)

Cost[i] represents the minimal cost of recurring to the i-th layer and edge[i, i + 1] represents the weight of all edges connecting the i-th layer and the (i + 1)-th layer. This formula shows that the minimal cost of the (i + 1)-th layer is equal to the sum of the minimal cost of the i-th layer and the minimal weight connecting the i-th layer and the (i + 1)-th layer. Note that Cost[0] = 0. Formally, the procedure of DP is as follows, where Ki is the number of nodes for the i-th layer:

figure a

Note that Ki is bounded by K, and therefore, the complexity of computing Cost[i] is K2. Then, the total computation complexity of the DP procedure is O(nK2). Note that the computation complexity of the Dijkstar algorithm is O(n2K2), where nK is the number of nodes on the digraph.

In summary, the complexity of the whole graph algorithm is O(nK2) + O(nK2), i.e., O(nK2). Thus, the graph algorithm with a polynomial-time complexity is able to find the minimal-cost resources for a given FOS efficiently.

4.3 Framework of path-relinking GA

GA is a biological evolutionary computing model that imitates the natural selection and genetics mechanism of Darwin’s theory of evolution. It is a method that simulates the natural evolution process to search for the optimal solution. In GA, each individual is actually a chromosome carrying genes. The chromosomes in the population produce new individuals through the process of crossover and mutation. New individuals form a new population representing a new solution set.

The evolutionary process of GA makes the offspring population more adaptable to the environment than the predecessor. The approximate optimal solution can be obtained by decoding the optimal individual in the last-generation population. In order to improve the GA, the PR is added to search for local solutions while the population is evolving. The flow chart of PR-GA is shown in Fig. 3, and detailed procedure is as follows:

Fig. 3
figure 3

Flow-chart of PR-GA

Full size image
figure b

Because the graph algorithm is added, the GA is dedicated to searching promising FOSs. A new genetic algorithm framework is constructed. PR is added to perform a more detailed search near the local optimal solution. The Hamming distance is used as the judgment of individual crossover and mutation, instead of using probability. The parameter of Dmin decides the operator of crossover or mutation. Here, Dmin is set as the half length of the FOS, i.e., 0.5n. In the PR-GA, the parameter Px is set as 0.5, which ensures identical chance of implementing genetic operators (crossover and mutation) or path-relinking operation.

The crossover and mutation process have been changed to adapt the precedence constraints between the operations, which are introduced as follows.

4.4 Genetic operator

4.4.1 Crossover operator

The traditional crossovers for permutations such as PMX crossover and order crossover are likely to violate the precedence constraints between operations. Therefore, in order to avoid infeasible solutions, a crossover that can guarantee precedence constraints is adopted [6]. When the Hamming distance between the current individual and the best one is not less than half of the chromosome length, the current individual is considered to evolve toward the best. So, the crossover between the current individual Xi(t) and the best individual Xr as the reference is performed.

The process of the crossover in this study is the same as the fragment crossover [6]. An offspring Xi(t + 1) is derived from two feasible parents Xi(t) and Xr, which is always feasible.

4.4.2 Mutation operator

The mutation is to avoid premature convergence to the local optimum and increase the diversity of the population. For the current problem, simply swapping or reversing the positions of the two operations usually makes the sequence infeasible. A method similar to crossover is used for the mutation of individuals, and the reference sequence is a randomly generated feasible sequence. The condition for mutation is that the Hamming distance between the individual and the best is less than half of the chromosome length. For the small Hamming distance, it is considered that the current individual is too similar to the best value, which is not conducive to the diversity of the population. A feasible sequence is randomly generated, and it is used as a reference sequence to guide individuals to perform mutation operations as follows:

Procedure: Mutation

  • Step 1. Produce a feasible offspring Xi(t + 1) randomly.

  • Step 2. Randomly generate x and y positions (x < y).

  • Step 3. Xi(t) and Xi(t + 1) are crossed in [x, y].

  • Step 4. Output offspring Xi(t + 1) with adjusted fragment.

4.5 Path-relinking operation

PR is to generate a new solution by connecting the paths of two high-quality solutions (two parent solutions). PR mainly includes two steps. One step is to construct a path connecting the two parent solutions. The solutions at the beginning and the end of the path are called the initial solution and the guiding solution, respectively, and the other solutions in the middle of the path are called intermediate solutions. Another step is to select a solution from the constructed path as a reference solution for further improvement.

An example for a part with seven operations is used to explain the PR process, and is illustrated in Fig. 4. As shown in Fig. 4, the PR process is to traverse the initial solution from front to back, and then compare the corresponding positions of the initial solution and the guiding solution. If they are different, find out the current position of i in the guiding solution and exchange them; if they are the same, continue to traverse the initial solution until the end. Note that the initial solution can always become the guiding solution by finite exchanges (bounded by n). For example, the first position 1 of the init in Fig. 4 is the same as that of the guide, so continue to traverse next position. The second position (2) of the init is different from that (3) of the guide. Find the position of 2 in the guide (the 5th position) and exchange it (2) with the gene in the 5th position (5) of the init, then we obtain the mid 1–5-3–4-2–6-7. Now, the second position (5) of the mid differs from that (3) of the guide. Find the position of 5 in the guide (the 6th position) and exchange it (5) with the gene in the 6th position (6) of the mid, then we obtain the mid 1–6-3–4-2–5-7, and so on.

Fig. 4
figure 4

A PR based on exchange

Full size image

Only exchange can produce the intermediate solutions. As shown in Fig. 4, four exchanges were performed in this example. The last time the sequence returned to the guide, so three intermediate solutions were generated. The PR is based on exchange, using the method of sequential return from the initial to the guide. The time complexity of each PR is O(n). The detailed PR process is as follows:

figure c

A new framework structure is created by adding PR operations in the GA process. Individuals in the population have a probability of 0.5 to perform PR operations. The exchange-based PR can find better values near the local optimal solution and perform a more detailed search on the solution space. The combination of local search and random search can get a better solution to the problem.

5 Case studies

In this section, we carried out computational comparison versus five OS cases for machining parts, so as to show the effectiveness and the merits of the PR-GA.

5.1 Statements of cases

In this study, three widely used OS cases based on two prismatic parts adopted from Guo et al. [3], Li et al. [16], and Hu et al. [5] are selected. The geometric features and machining information for part 1 and part ANC-101 are provided in the Appendix. The OPGs of part 1 and ANC-101 are shown in Fig. 1 (a) and (b), respectively. For part 1, the value of SCI is 120, while the value of SCI is 100 for part ANC-101.

The first case named case 1 is the OS problem for part 1, and the second and the third cases are for part ANC-101. Case 1 is the common case in [3] and [5], Case 2 is identical with that in [5], and Case 3 is the common case in [16] and [17]. The sole difference between case 2 and case 3 is that the optional cutting tools for operation 6, which are C7 and C8 in case 2 but C6, C7, and C8 in case 3. That difference results in different optimal solutions for case 2 and case 3.

For above three cases, the following two conditions of different objective functions are adopted:

  1. (a)

    All machines and tools are available, and ω1 ~ ω5 are set as 1;

  2. (b)

    All machines and tools are available, and ω2 = ω5 = 0, ω1 = ω3 = ω4 = 1.

Hereinafter, we denote the case U with condition v by case U(v). For example, case 2(b) means the case 2 with condition (b).

The fourth case used to verify the advantage of the PR-GA is adopted from [1] and originally from Jin and Zhang [42], which is called case 4 hereinafter. The part in case 4 called part 2 fabricated from a rectangular block has 11 features and 17 operations. Please refer to Table 1 in [42] for details.

The last case is adopted from [27] and [33] for PP problem, which is called case 5 hereinafter. The part in case 5 named part 3 has 28 features and 46 operations. For easy reference, the geometric features, the OPG, and machining information for part 3 are provided in the Appendix.

5.2 Configurations of algorithms

To verify relative merits of the PR-GA, we compared it with the SA [16], the CPSO [3], the ACO [5], the MPSO and the FSDPSO [18], the ESGA [26], and the CPAGA [27]. It is well known that the parameters of MAs affect their performance. The two common parameters of concerned MAs are the population size NP and the number of maximum generations NM. Those two parameters are usually determined empirically by the dimensionality and perceived difficulty of the problem addressed. The values of NP and NM are 5000 and 200 in the CPSO, 20 and 500 in the ACO, 2000 and 500 in the MPSO, and 1000 and 500 in the FSDPSO, respectively, which are adopted from corresponding papers. In the PR-GA, the NP is set as 100 and the NM is 200 by a pilot study for cases 1–5. The algorithm parameters of PR-GA are fixed as Px = 0.5 and Dmin = 0.5n.

The computation tests were implemented on a personal computer with Intel i7 5500U 2.4-GHz CPU and 8-GB memory. The PR-GA were code and implemented in Visual C +  + 2010. Ten trials were executed for case 1, case 2, and case 3, respectively, and the running results were collected.

Before the comparative computational experiments, we test the effectiveness of PR-GA itself. In order to verify the effect of path-relinking on the entire algorithm, the GA with path-relinking denoted by PR-GA and the GA without path-relinking denoted by GA are tested for case 2(a) and case 3(a). The results are shown in Table 2, and the convergence curves of PR-GA and GA for case 2(a) are shown in Fig. 5. From the metrics shown in Table 2, it can be seen that the path-relinking plays an important role in strengthening the global local search ability and speeding up the search process. Clearly, the PR-GA outperforms the GA with respect to solution quality and convergence speed. In the following computation study, we adopted the PR-GA and compared it with other algorithms.

Table 2 Computational comparison between PR-GA and GA
Full size table
Fig. 5
figure 5

Comparison between the PR-GA and the GA without PR for case 2(a)

Full size image

5.3 Computational results and analysis

Firstly, the best solutions obtained by the PR-GA were compared with those obtained by existing MAs in order to verify the PR-GA’s effectiveness. For case 1(a), an optimal process plan of part 1 with total cost of 1357 is obtained, and the optimal FOS is 1–2-3–5-9–10-11–7-8–6-4–14-12–13. The ACO [5] and the FSDPSO [18] identified the optimal process plan with the same total cost of 1357, while the CPSO [3] and the SA [16] found the optimal process plans with the total cost of 1361 and with the total cost of 1421, respectively. For case 2(a), an optimal process plan with total cost of 2530 is listed in Table 3, which outperforms the optimal process plan with the total cost of 2535 found by the SA and the CPSO. The ACO, the ESGA, and the FSDPSO identified the optimal process plans with the same total cost 2530. For case 3(a), the process plan with total cost of 2525 obtained by the PR-GA is shown in Table 4. The HBMO [5], the ACO, the MPSO, and the FSDPSO found the optimal process plan with the same total cost of 2525, whereas the TS obtained the optimal process plan with the total cost of 2537. The best costs of solutions obtained by each algorithm are listed in Table 5 for cases 1, 2, and 3. From the best costs for condition (b) listed in Table 5, it can be observed that the PR-GA finds the same best solution as that obtained by the FSDPSO for every case. In summary, the PR-GA is able to find best solutions found so far for cases 1, 2, and 3, and is not worse than the state-of-the-art algorithms including FSDPSO, ESGA, and CPAGA with respect to solution quality. Clearly, the PR-GA is an effective MA to solve OS problem.

Table 3 An optimal process plan of case 2(a)
Full size table
Table 4 An optimal process plan of case 3(a)
Full size table
Table 5 The computational comparison of three cases
Full size table

Next, we compared mean costs of best solutions obtained by the PR-GA with those obtained by state-of-the-art algorithms, so as to show the merits of the PR-GA. The mean costs of best solutions obtained by each algorithm are provided in Table 5 for cases 1, 2, and 3. The average computation times of the PR-GA for all cases are shown in Table 6. For case 1, ten trials of the PR-GA hit best cost 1357 in all 10 independent runs. From Table 5, we find that the PR-GA is better than the SA and the CPSO in mean cost, and is better than the ACO and the FSDPSO for mean cost versus case 1(a). For case 2(a), it can be seen that the PR-GA and the CPAGA are better than the SA and the CPSO, the ACO, the ESGA, and the FSDPSO for mean cost, while the PR-GA is competitive to the CPAGA for mean cost. Nine trials out of ten trails hit the best cost of 2530 in the PR-GA for case 2(a), as shown in Fig. 5(a). Note that the number of fitness evaluations of the PR-GA is 50,000, which is one-tenth of that of the FSDPSO (500,000 fitness evaluations). From Table 5, it can be seen that the PR-GA is better than the TS, the HBMO, the ACO, the MPSO, and the FSDPSO with regard to mean cost versus case 3(a). From the mean costs for condition (b) shown in Table 5, it can be seen that the PR-GA finds the same mean cost as that obtained by the FSDPSO and the CPAGA for every case. In conclusion, the PR-GA is the best one for solving the three cases among all mentioned algorithms with respect to average solution quality.

Table 6 The computational time of PR-GA and some available algorithms
Full size table

Subsequently, we compared the best solution found by the PR-GA with that obtained by solving MILP model [1] and that obtained by a DP-like heuristic [42] versus case 4 for part 2. In Table 7, the best solution found by the PR-GA for case 4 is the same optimal production time with that obtained by solving the MILP model of feature-based representation [1]. As can be seen in Table 7, the solution found by the PR-GA is superior to the solution found by the DP-like heuristic [42]. Note that the computation time of PR-GA for case 4 is 0.312 s, which is far less than the computation time reported in [1]. In conclusion, the computation results of PR-GA in case 4 show the promising global search ability of PR-GA.

Table 7 The comparison of best solutions for case 4
Full size table

Lastly, we compared the best solution found by the PR-GA with that obtained by the recent CPAGA [27] versus case 5 for part 3. The number of operations in case 5 is the largest one among five cases, and case 5 is the most changeable case. The best solution found by the PR-GA for case 5 is presented in Table 8, which with cost 4098 is better than the best solution with cost 4299 found by the CPAGA. The best cost and mean cost of ten runs for case 5 are listed in Table 5. From the data shown in Table 5, it is clear that the solutions of PR-GA are better than those of the GA-SA [33] with respect to best cost, and are better than those of the CPAGA with respect to best cost and mean cost. In summary, for case 5 with part 3, the PR-GA outperforms existing GAs for solution quality.

Table 8 Best solution found by the PR-GA of condition 1 of case 5 for part 3
Full size table

From the computation times listed in Table 6, it is clear that the PR-GA is very efficient for solving OS problems. Note that the computation times listed in Table 6 are obtained by computers with different computing powers. However, we can deduce that the PR-GA is efficient and is promising among the concerned GAs.

It is worth mentioning that the PR-GA is free from tuning GA parameters such as crossover and mutation rates. Note that Px and Dmin as main parameters of PR-GA are fixed as 0.5 and 0.5*n, respectively. The PR-GA’s promising computational results of four cases show the robustness of the new GA framework based the fixed parameters Px and Dmin.

The superiority of the PR-GA exhibited in above computational experiments lies in the reduction of search space by the graph algorithm and the well exploitation ability of PR around promising FOSs. The introduction of the graph algorithm able to find the minimal cost resources for a given FOS eliminates the effort and the need to update the resources for each FOS. Therefore, the PR-GA only focuses on the search of FOSs, which greatly reduces search-space size, and improves global search ability of the PR-GA. Another reason is the introduction of path-relinking for extensively local search of FOSs.

Considering the promising computational efficiency, robust global search ability, and the robustness of algorithm parameters shown in previous four cases, the proposed PR-GA seems a promising alternative MA for solving OS problem in practice.

6 Conclusion and future work

In this paper, a novel GA named PR-GA is proposed to solve the OS problem, which is based on a graph algorithm for finding the minimal cost resources associated with a given FOS and a path-relinking mechanism for searching promising FOSs. The proposed graph algorithm with polynomial-time complexity is able to find the resource assignments with minimal cost for a given FOS, thereby avoiding the update of the resources in the search process. The introduction of graph algorithm to PR-GA eliminates the randomness of search optimal resources for a given FOS, and reduces the search space of the PR-GA. Furthermore, a new GA evolution framework has been proposed in this paper. The Hamming distance is used as the basis for crossover or mutation, instead of using the traditional crossover rate and mutation rate as the criterion, thereby avoiding parameter tuning of crossover and mutate rates. In this paper, path-relinking is applied to the proposed PR-GA as local search to enhance global search ability. The computational results indicate that the PR-GA outperforms existing CPSO, MPSO, ACO, FSDPSO, ESGA, and CAPGA with respect to solution quality. Moreover, the PR-GA is able to find the same exact global optimum as that obtained by solving a recent MILP model of a representative OS case. In addition, the PR-GA can find the optimum within one second, while the exact method takes about 1 h to find the optimum. Comparative study for five cases of three parts shows that the PR-GA has promising global search ability, and is a good choice to solve the OS problems efficiently.

In this study, the PR-GA is limited to solve the single-objective OS problem. Next, the PR-GA can be extended to solve the multi-objective OS/PP problems considering the objectives of minimizing cost/time and reducing carbon emission. In the future, the PR-GA needs to be extended to solve more complex PP problems such as integrated process planning and scheduling problem.