Introduction

Machining round holes with varies sizes in metal stock is one of the most common operations in the manufacturing industry. Hole-making operations such as drilling, reaming, tapping, and punching compose a large portion of machining processes for many industrial parts such as dies, plastic injection mold manufacturing and digital T/R modules for radar, where the machining process of a hole consists of several individual operations with different machining tools. In printed circuit board drilling, only one tool and one operation is needed to drill each hole. However, with many other industrial parts like a plastic injection mould, it may have many holes of various diameters, surface finishes, tolerances, and possibly different depths; in such cases, several tools with different diameters may be needed to finish one hole. A hole may or may not be completed depending on the hole diameter, tool geometry, and surface quality specifications. A relatively large hole may not be able to be finished with a single tool. A pilot hole may have to be drilled first using a tool of smaller diameter and enlarge subsequently using larger tools to its final size. Where necessary, additional cutting tools may be needed for reaming or tapping.

In drilling different holes specifications, the common practice in the industry is to complete all operations on the holes that require the current tool before switching to the next tool. This practice is common because the tool switching time is often longer than the tool positioning time. The path of each individual tool is commonly solved as separate travelling salesman problem (TSP) and the tours are executed one after another with tool switching between each tour. However, the repeated movement of the worktable to drill all the holes that requires the current tool is not optimal. On the other hand, the movement of the worktable can be minimized by completing a hole using several tools of different diameters before moving to the next hole. This in turn would lead to excessive tool switches.

According to the research of Merchant (1985), the non-cutting time take on average 70 % of the total time in the manufacturing process. Therefore, efforts in planning the holes machining sequence in order to shorten the tool positioning time and the tool switching time in a machining process is of key issues. This can lead to significant reduction in machining time and increase the efficiency of hole-making process, which directly improves productivity of manufacturing system. As a result, the problem of finding the best sequence for the drilling operation has drawn attention of numerous researchers.

Many works have been reported for minimizing the productive time by optimizing the cutting parameters (Kolahan and Liang 2000; Dereli et al. 2001), type of tool paths to be involved (Yao and Gupta 2004), tool selection and tool sequencing (Zhang and Ge 2009), however, very limited number of researchers have considered non-productive time. Literatures on drilling route optimization problem can be traced back to the year 1996 where Kolahan and Liang (1996) presented a case study with variable holes sizes. Kolahan and Liang (1996) also applied tabu search approach to minimize the cost in hole making processes by optimizing tool travel scheduling, tool switch scheduling, tool selection, and machining speed specification. The algorithm was tested for the job size of 50, 100, 150, and 200 nodes with stopping limit of \(600s\) and showed good results especially for the large size jobs.

Ghaiebi and Solimanpur (2007) dealt with the optimization of hole-making operations in conditions where a hole may need several tools to get completed. The objective was to minimize the summation of tool airtime and tool switch time. The objective was affected by the sequence through which each operation of each hole was done. The problem was formulated as a 0–1 non-linear mathematical model. An ant algorithm was developed to solve the proposed mathematical model. An illustrative example showed the application of the algorithm to optimize the sequence of hole-making operations in a typical industrial part. The author’s assumption was that a hole is made in multiple passes each of which need a particular tool and the machining process can be started from any point. A minimum path search algorithm using genetic algorithm (GA) was developed by Oysu and Bingul (2007) for the tool-path optimization. The algorithm successfully optimized the number of retraction points together with total airtime.

Most of the researcher’s formulated hole-making problem is similar to that of travelling salesman problem (TSP) in which each city (hole) in a tour (sequence of operations) must be visited only once. Liu et al. (2013) formulated the mathematical model for process planning problem by considering the selection of machining resources, operations sequence optimization and the manufacturing constraints, mapping them to a weighted graph and converted it to a constraint-based travelling salesman problem. The operation sets for each manufacturing features are mapped to city groups, the costs for machining processes (including machine cost and tool cost) are converted to the weights of the cities; the costs for preparing processes (including machine changing, tool changing and set-up changing) are converted to the ’distance’ between cities. Solving the TSP means finding the route with minimal total cost, which is known to be an NP-hard problem (Nguyen et al. 2007). The time required for the optimal analysis to derive the shortest path of a TSP using an analytic method increases exponentially as the problem complexity increases. However, this problem is more complicated than TSP as, unlike the classical TSP, multiple visits of a hole may be needed for holes to be machined with several different tools. In addition to that, a hole needs to be drilled with different tools in a specific order and the switching time for a tool to another tool depends on the current tool and the tool of interest. For this reason, heuristics and metaheuristics are often used in more recent studies.

Biologically-inspired algorithms are one of the main categories of metaheuristic algorithms. The power and beauty of these algorithms comes from the ability to emulate the best features in nature, namely by selecting the fittest in biological systems through natural selection over millions of years of evolution via two important characteristics: the selection of the fittest, and the adaptation to the environment. Statistically, these characteristics can be classified as intensification and diversification (Blum and Roli 2003; Gazi and Passino 2004; Yang 2010a). Intensification intends to improve the existing solutions in a local region by exploiting the current good solutions, while diversification makes sure that the algorithm can explore the search space more efficiently, often via randomization (Yang and Deb 2010). A good trade-off between diversification and intensification will often lead to a more efficient algorithm (Yang 2010a).

Various bio-inspired optimization algorithms have been presented in literature. Among the most popular algorithms are genetic algorithms (Goldberg 1989), tabu search (Glover 1986), particle swarm optimization (Eberhart and Kennedy 1995), ant colony optimization (Dorigo and Di Caro 1999), differential evolution (Storn and Price 1995), cuckoo search (Yang and Deb 2009), hunting search (Oftadeh et al. 2010), and bat algorithm (Yang 2010b). The cuckoo search (CS) developed by Yang and Deb (2009) is based on the obligate brood-parasitic behavior of some cuckoo species in combination with the Lévy flight behavior of some birds and fruit flies. The preliminary studies on the CS appears to be very promising and could outperform existing algorithms in solving optimization problems (Gandomi et al. 2012). CS algorithm was successfully applied for solving manufacturing optimization problems (Yildiz 2013) and for optimization of sequence in printed circuit board holes drilling problems (Lim et al. 2012).

In recent years, bio-inspired algorithms and its variants have been applied widely to solve many combinatorial optimization problems (Yang et al. 2013). For example, Gandomi et al. (2013) presented a chaos-enhanced accelerated particle swarm optimization algorithm to solve three engineering problems. Sayadi et al. (2012) presented discrete firefly algorithm (DFA) to solve the manufacturing cell formation optimization problem. Li et al. (2003) applied a tabu-enhanced genetic algorithm approach for assembly process planning problem. Ho and Ji (2004) presented a hybrid genetic algorithm to optimize the sequence of component placements on a printed circuit board. Prakash et al. (2008) proposed an adaptive hierarchical ant colony optimization to solve the traditional machine loading problem in flexible manufacturing systems. Arnaout (2013) introduced a three-stage ant colony optimization algorithm for location allocation problem with an unknown number of facilities. Li et al. (2012) investigated two-tool parallel drilling process plan optimization problem using two phase GA. In the first phase, the GA is used to determine the optimal process parameters satisfying all constraints such as drill feed, spindle speed, thrust force, torque, power and tool life, and the minimum machining time is the optimization criteria. In the second phase, the GA is used to determine the operation completion time and machining sequence. The minimum operation completion time is the optimization criteria in this phase. Yang and Deb (2013) presented multi-objective cuckoo search algorithm for design optimization problems.

For many continuous optimization problems, cuckoo search can find the desired solutions very efficiently. However, sometimes, some difficulty may arise, which is true for all nature-inspired algorithms when the appropriate solutions could not be found for some other optimization problems. This is consistent with the so-called No Free Lunch theorem (Wolpert and Macready 1997). To circumvent this theorem, hybridization has been applied to optimization algorithms for solving a given set of problems. These hybridized algorithms are the combination of components from two or three algorithms which performs more efficiently than their parent algorithms.

In line with this, cuckoo search has been hybridized with other optimization algorithms, machine learning techniques, heuristics, etc. Hybridization can take place in almost every component of the cuckoo search (Fister et al. 2014). For example, initialization procedure, evaluation function, moving function and others have all been tried by many researches. A hybrid CS/GA algorithm was developed to solve global optimization problems (Ghodrati and Lotfi 2012) and reliability-redundancy optimization problems (Kanagaraj et al. 2013), hybrid CS/PSO was developed for solving global optimization problems (Ghodrati and Lotfi 2012), a hybrid cuckoo search via Lévy flights for the permutation flow shop scheduling problems (Li and Yin 2013) and fuzzy assisted hybrid cuckoo search algorithm for multi-objective scheduling problems (Chandrasekaran and Simon 2012) have been applied and showed promising results. It is also found that genetic algorithms can be hybridized with many algorithms such as particle swarm optimization; more specifically, may involve the use of generic operators to modify some components of another algorithm (Yang and Koziel 2011). In this paper a hybrid of cuckoo search and genetic algorithm (CSGA) is proposed to find the optimal sequence of hole-making process. The performance of the hybrid CSGA is demonstrated with small and large size problem instances which can significantly reduce the non-cutting time of hole-making process.

The remainder of this paper is organized as follows. A brief description of hole making problem is presented in “Hole-making sequence optimization problem” section. The proposed hybrid CSGA developed in this study is described in “Proposed cuckoo search-genetic algorithm” section. The verification of the algorithm detail is given in “Algorithm verification” section. The details of computational experiments used to test the performance of CSGA are discussed in “Computational experience” section. Finally, the results from the study are summarized in the last section.

Hole-making sequence optimization problem

When drilling a group of holes on a workpiece using a computer numberical control (CNC) drilling machine, the machine table is driven back and forth in the \(x-y\) directions so that each hole is to be drilled in its designed position. Many times, several cutting tool is needed to machine a hole to the specific size and tolerance; this means that there is also a need for the turret lathe to be rotated back and forth. The optimum drilling sequence can minimize the total table and turret lathe movements, thus shorten the no-cutting time and lengthen working life of the table’s driving system as well as the turret lathe.

The drilling operation can be divided into three parts: the drilling of the holes, the positioning of the worktable, and the switching of the cutting tool. The total operation time for the drilling process is simply the sum of the machining time, the positioning time, and the tool switching time. Since machining time is decided by the CNC program, hence minimizing the positioning time and the tool switching time reduces the total operation time for the drilling process. This can only be achieved by optimizing the sequence of drilling.

The distance between two holes are often considered to be rectilinear or Euclidean. The rectilinear distance between two points, say \(i\) and \(j\) of coordinates \((x_i, y_i)\) and \((x_j, y_j)\), respectively, can be calculated with the following equation:

$$\begin{aligned} d^R_{ij} = |x_i-x_j|+|y_i - y_j| \end{aligned}$$
(1)

The movement of the worktable in the \(x\) and \(y\) directions are realized using stepper motors (Onwubolu and Clerc 2004). By considering this machine characteristics, the problem to be solved here is to find a sequence in which the holes are to be drilled such that the worktable positioning time is minimized. The time needed for the worktable to position itself depends strongly on the machine characteristics. In practice, usually, this travelling time cannot be computed exactly. Travelling consists of three phases: accelerating the worktable, running at full speed, slowing down to a complete stop. For small distances, full speed may not be reached and we may have anomalies in the sense that a farther position can be reached faster than a nearer position. Even if a timing function is available it may be not accurate and it will be so complicated that its evaluation takes too long for large problem instances (where we cannot store a distance matrix). Therefore one has to be satisfied with making reasonable approximations on the true movement time. In this paper, the gears are taken to rotate at the constant speed at all times. The formula to calculate the positioning time for the worktable to move from point \(i\) to point \(j\) is as follows:

$$\begin{aligned} t_{(i,j)} = \sum {\frac{|x_i - x_j|}{v_x}} + \sum {\frac{|y_i - y_j|}{v_y}} \end{aligned}$$
(2)

where \(v_x\) and \(v_y\) are the linear velocities of the worktable in the \(x\) and \(y\) directions, respectively. To further simplify the problem, both \(v_x\) and \(v_y\) are taken to be the same, \(v_x = v_y = v\)

$$\begin{aligned} t_{(i,j)} = \frac{1}{v} \left( \sum {|x_i - x_j|} + \sum {|y_i - y_j|}\right) \end{aligned}$$
(3)

Hence, minimizing of the positioning time is simply minimizing the total distance travelled by the worktable, which is represented by the Eq. 1.

However, in optimizing the sequence of drilling, not only the distance travelled by the worktable should be considered; the tool switching time should also be considered. The sequence of drilling should be chosen such that a balance between the positioning time and the tool switching time can be achieved, whereby the total operation time is minimized.

Mathematical formulation

The mathematical model of this hole-making sequence optimization problem is being modeled by Ghaiebi and Solimanpur (2007). Suppose the operation \(j\) of hole \(i\) is done in order \(k\). If so, the variable \(x_{ij}^{k}\) will be equal to 1. Now, if processing of operation \(j'\) of hole \(i'\) takes place in order \(k + 1\), the variable \(x_{i' j'}^{k+1}\) will be equal to 1. By these assumptions, the tool has to move from hole \(i\) to hole \(i'\). Therefore, the corresponding positioning time can be mathematically modeled as \(a_{ii'}x_{ij}^{k}x_{i' j'}^{k+1}\). The total positioning time taking all the movements into consideration can be determined by

$$\begin{aligned} \mathop {\sum \limits _{i=1}^{I}\sum \limits _{j=1}^{n_i}\sum \limits _{i'=1}^{I}\sum \limits _{j'=1}^{n_{i'}}\sum \limits _{k=1}^{N-1}}_{i'\ne i}a_{ii'}x_{ij}^{k}x_{i' j'}^{k+1} \end{aligned}$$
(4)

where \(I\) is the total number of holes, \(N\) is the total number of operations, and \(n_i\) is the number of operations for holes \(i\).

Let us then assume that the tool required for doing operation \(j\) of hole \(i\) is different from the one needed for doing operation \(j'\) of hole \(i'\). If so, the parameter \(\delta (T_{ij}, T_{i'j'})\) will be equal to 1, where \(T_{ij}\) is the tool required for operation \(j\) of hole \(i\). If the time required to switch from the tool used for making operation \(j\) of hole \(i\) into the tool required for the operation \(j'\) of hole \(i'\) is denoted by \(s_{ij, i' j'}\), this time can be mathematically modeled as \(s_{ij, i' j'} \delta (T_{ij}, T_{i' j'})x_{ij}^{k}x_{i' j'}^{k+1}\). The total tool switching time can then be calculated by

$$\begin{aligned} \sum \limits _{i=1}^{I}\sum \limits _{j=1}^{n_i}\sum \limits _{i'=1}^{I}\sum \limits _{j'=1}^{n_{i'}}\sum \limits _{k=1}^{N-1}s_{ij, i' j'} \delta (T_{ij}, T_{i' j'})x_{ij}^{k}x_{i' j'}^{k+1} \end{aligned}$$
(5)

Consequently, the objective function of the proposed zero-one mathematical programming model is expressed as follows:

Minimize:

$$\begin{aligned}&\mathop {\sum \limits _{i=1}^{I}\sum \limits _{j=1}^{n_i}\sum \limits _{i'=1}^{I}\sum \limits _{j'=1}^{n_{i'}}\sum \limits _{k=1}^{N-1}}_{i'\ne i}a_{ii'}x_{ij}^{k}x_{i' j'}^{k+1} \nonumber \\&+ \sum \limits _{i=1}^{I}\sum \limits _{j=1}^{n_i}\sum \limits _{i'=1}^{I}\sum \limits _{j'=1}^{n_{i'}}\sum \limits _{k=1}^{N-1}s_{ij, i' j'} \delta (T_{ij}, T_{i' j'})x_{ij}^{k}x_{i' j'}^{k+1} \end{aligned}$$
(6)

Subject to:

$$\begin{aligned}&\!\!\!\sum \limits _{k=1}^{N}x_{ij}^{k} = 1, \quad i = 1,2,\ldots ,I, \quad j = 1,2,\ldots ,n_i \end{aligned}$$
(7)
$$\begin{aligned}&\!\!\!\sum \limits _{i=1}^{I}\sum \limits _{j=1}^{n_i}x_{ij}^{k} = 1, \quad k = 1,2,\ldots ,N \end{aligned}$$
(8)
$$\begin{aligned}&\!\!\!x_{ijk} \le \sum \limits _{k'=k+1}^{N}x_{i,j+1,}^{k'} = 1, \quad i = 1,2,\ldots ,I, \nonumber \\&\quad i = 1,2,\ldots ,n_i-1 \end{aligned}$$
(9)
$$\begin{aligned}&\!\!\! x_{ij}^{k} \in \{0,1\} \quad \forall i,j,k \end{aligned}$$
(10)

Constraints 7 ensure that each operation of each hole is assigned to only one position in the sequence. Similarly, Constraints 8 guarantee that only one operation is assigned to each position of the sequence. Constraints 9 represent the precedence of operations of each hole. Lastly, Constraints 10 confine the decision variables into zero-one values.

Proposed cuckoo search-genetic algorithm

Yang and Deb (2009) developed the CS optimization algorithm which was inspired by the obligate brood parasitism of some cuckoo species by laying their eggs in the nests of other host birds (often other species). Sometimes the host birds engage in direct conflict with the intruding cuckoos. If a host bird discovers that the eggs do not belong to it, it will either kick these alien eggs out from the nest or simply abandon its nest and build a new nest elsewhere.

The algorithm of the original CS is then governed by three rules (Yang and Deb 2009):

  1. 1.

    Each cuckoo lays one egg at a time and selects a nest randomly.

  2. 2.

    The best nest with the highest quality egg can pass onto the new generations.

  3. 3.

    The number of host nests is fixed, and the egg laid by a cuckoo can be discovered by the host bird with a probability \(p_a\).

However, several behaviors of cuckoo birds were not taken into account in the original CS implementation. Firstly, the original CS failed to consider the mating of cuckoo birds. Secondly, the evolution of cuckoo birds to improve adaptation was also not considered. To reduce eggs discrimination by the host birds, cuckoo birds evolve to lay eggs that mimics the eggs of certain species of host birds (Davies et al. 1989). In some cases, the young cuckoo can even mimic the begging call of the young hosts. Studies have also shown that when there is a lack of suitable nests, parasitized nests can be parasitized the second time by another cuckoo. Since only one cuckoo is ever reared per nest, it pays for the second cuckoo to remove the first cuckoo’s egg because the earlier laid egg is likely to hatch first (Davies and Brooke 1988). All these behaviors serve as an inspiration in the hybridizing of CS with GA. In the original CS (for continuous space), Lévy flights and random walks are used to generate new solutions. In solving combinatorial problems (discrete integers solution), the GA operators take the place of both Lévy flights and the random walks. More specifically, the crossover operator takes the place of the Lévy flights, and the mutation operator takes the place of the random walk.

The proposed hybridized CSGA as shown in Fig. 1 can be summarized as follows:

  1. 1.

    Cuckoos mate with one another and chromosomal crossover occurs between them.

    Fig. 1
    figure 1

    Pseudocode of cuckoo search-genetic algorithm

    Full size image
  2. 2.

    Cuckoos lay eggs in other host birds’ nests and compete with each other. Only the best eggs will survive.

  3. 3.

    Cuckoos evolve by mutation to lay eggs that mimic the host’s.

  4. 4.

    Low quality eggs are rejected by host birds.

Solution representation

In this hybrid CSGA, each cuckoo bird represents a solution in the current generation, and cuckoo eggs represent the newly generated solutions in that generation (either by crossover or mutation). The solution is represented through a vector of integers in which each integer in the solution vector corresponds to a hole to be machined. Each point \(i\) to be machined is numbered with a unique number beginning from 1 with an increment of 1 until all the points are numbered. \(i\) is repeated for \(n_i\) times in the solution and therefore the length of the solution depends on the total number of operations needed to complete the hole-making process. For \(k\) number of holes that requires \(n_i\) number of operation for each hole \(i\), the solution is:

$$\begin{aligned} x = (x_1, \ldots , x_N) \end{aligned}$$
(11)

where each element in \(x\) represents the hole to be machined and

$$\begin{aligned} N = \sum \limits _{i=1}^{k} n_i \end{aligned}$$
(12)

Let us consider a simple 3 holes problem, numbered as 1, 2 and 3, as shown in Fig. 2. Hole 1 requires one operation, hole 2 requires two operations, and hole 3 requires three operations to complete the hole-making process. Using Eqs. 11 and 12, the length of the solution is 6. Suppose in the simple 3 holes problem illustrated, the 3 holes are needed to be finished with the following cutting tool in the following order:

  • Hole 1 - Twist drill bit

    Fig. 2
    figure 2

    A simple three holes problem

    Full size image

  • Hole 2 - Center drill bit \(\rightarrow \) Twist drill bit

  • Hole 3 - Center drill bit \(\rightarrow \) Twist drill bit \(\rightarrow \) Reamer

A solution sequence or vector of 3-2-1-2-3-3 would means that the first operation for hole 3, hole 2, and hole 1 is done one after another using the corresponding cutting tool. The second operation for hole 2 is then followed after, and then last two operations of hole 3 with the corresponding cutting tool. The meaning of the solution summarized in Fig. 3.

Fig. 3
figure 3

Solution interpretation

Full size image

Due to the constrains of the order of cutting tools, for the solution sequence or vector 3-2-1-2-3-3, it is understood that the “ 3 ” that appears first means that the hole will be drilled with a center drill bit. It follows that the second appearing “ 3 ” refers to the drilling of hole 3 using a twist drill bit and the third with a reamer. This rule also applies to all other holes. Thus, in the representation of solution, there is no need to specify the cutting tool used in the operation.

Initial population

The initial population is generated randomly. One possible way is to first generate a valid solution vector by listing the hole number from the first hole to the last hole. Where a hole needs more than one operations, the hole number repeatedly listed according to the number of operations required. As for the simple example shown in Fig. 2, the solution vector would be 1-2-2-3-3-3. After the valid solution vector is generated, the initial population can be easily generated by randomizing the order of the elements in the vector.

Crossover operator

Before carrying out the crossover operator, the order of the solutions are randomized to allow cuckoos to mate with a more diversify population. Then the parent cuckoo birds are split into pairs. Two cuckoo eggs are reproduced from the two parent cuckoos.

The two-point crossover technique was adopted. Two points, \(i\) and \(j\), are randomly selected for each pair of parents. Everything between the two points is swapped between the two parents, generating two eggs. Using the 3 holes problem as an example again, when \(i = 4,\,j = 6\):

figure a

However, most of the time the crossover requires some repair work to be done. In the reparation work, the excess genes are first identified. From the valid solution vector generated in “Initial population” section the number of occurrences for each hole number can be determined. The children’s genes are compared with the valid solution vector. All the hole numbers in the children solution vector that has a number of occurrence that exceeds that of the same hole number in valid solution vector is identified. These excess genes are randomly removed from the chromosome until the number of occurrences of all hole numbers in the children solution vector do not exceed the number of occurrence of the same hole number. These excess genes are deleted from the chromosome that are apart of the swapped genes.

The children chromosomes are once again compared with the valid solution vector. This time, all the hole numbers in the children solution vector that has a number of occurrence that is less than that of the same hole number in valid solution vector is identified. These missing genes are added to the chromosomes in a random order right after the swapped genes until the number of occurrences of all hole numbers are matched. The illustration of the reparation work is as follows:

figure b

Mutation operator

In the mutation operation, each cuckoo egg mutates on its own. To allow small variations in the solution, a simple 2-opt moves proposed by Croes (1958) is used:

figure c

Rotation strategy

After each generation, the genes of all the cuckoo birds are rotated randomly. This rotation strategy serves as a simple way to diversify the search without introducing significant additional computational cost.

figure d

Elitism

Each time after the crossover, mutation, and rotation strategy, a form of elitism is performed to ensure that the best solutions are selected and maintained in the population. This procedure is summarized with the following equation:

$$\begin{aligned} x_{i,t+1}= \left\{ \begin{array}{ll} y_i &{} \quad \text {if } F(y_i) > F(x_{i,t}) \\ x_{i,t} &{} \quad \text {otherwise} \end{array} \right. \quad i = 1, 2, \ldots , N \end{aligned}$$
(13)

where \(y\) is the newly obtained solution, \(x\) is the current solution, and \(t\) is the generation number.

Algorithm verification

To verify the performance of CSGA, the algorithm will be used to solve the example part in Fig. 4 proposed by Ghaiebi and Solimanpur (2007). The position and size of various holes are indicated in Fig. 5. The \(x\) and \(y\) coordinates for the holes are taken from Ghaiebi and Solimanpur (2007). In this problem, there are a total of 5 drill bits with different sizes and 1 reamer used. The tool and its respective diameter is shown in Table 1. Depending on the what the current tool is, the time needed to switch to a certain tool varies and they are asymmetrical. The switching time for the tool is given in Table 2.

Fig. 4
figure 4

Solid model of example part

Full size image
Fig. 5
figure 5

Position of the holes on the example part

Full size image
Table 1 Cutting tool diameter
Full size table
Table 2 Tool switching times in minutes
Full size table

Since each hole is of different size, each hole has to be drilled several times with different set of cutting tools. To solve this problem, the tool required and the sequence of the passes for each holes are shown in Table 3. In this problem, it is taken that the speed of the worktable to be \(v=1 m\,min^{-1}\) and that tool 1 is currently in use in the spindle. The initial position of the cutting tool is at the coordinate (0, 0) at the bottom-left corner of the workpiece.

Table 3 Sequence of cutting tools needed to machine the holes
Full size table

In solving this problem, the number of cuckoos is set to 100 and the generation number is set to 1000. The CS by Lim et al. (2012) was also applied to compare the performance of CSGA and CS. The algorithms were made to run 25 times and the statistical results for CSGA and CS are summarized in Table 4.

Table 4 Statistical results of CSGA and CS for the example part
Full size table

The numerical results and the solutions obtained by ACO (Ghaiebi and Solimanpur 2007), PSO (Hsieh et al. 2011a), IA Hsieh et al. 2011b, CS and CSGA is shown in Table 5, where the column ‘Algo’ indicates the algorithm used to solve the problem, the column ‘Obj’ denotes the objective function value associated with the solution, which is the total operation time, the column ‘PT’ and ‘ST’ shows the positioning time and the switching time, respectively, and the ‘Sequence of operation’ shows the solution found by the respective algorithms in the format of (hole, tool). The 5 solutions obtained by CSGA and CS in Table 5 are the best 5 solutions in the 25 runs.

Table 5 Sequence of cutting tools needed to machine the holes
Full size table

As pointed out by Hsieh et al. (2011b), the objective function value of the solution provided by Ghaiebi and Solimanpur (2007) is 8.88 min and not 7.58 min as claimed in their paper. CSGA arrived at its best solution of 6.10 min twice and the calculation of the objective function value is as follows:

  • \(\text {Positioning Time}= [(13)+7+12+7+7+12+7+7+12+12+7+0+7+12+7+20 +7+12+7+7+0+8+12+8+0+8+12+8+12+12+32+12+0+12+32+12+(8)]/100 = 3.70\)

  • \(\text {Switching Time} = 0.2+0.2+0.6+0.8+0.2+0.4 = 2.40\)

  • \(\text {Total Operation Time} = 3.70 + 2.40 = 6.10\)

where the time in brackets denotes the time to move from the initial position to the first hole, and the time to move from the last hole back to the initial position. Figure 6 shows the convergence plot of the solution.

Fig. 6
figure 6

The best solution of CSGA over 1000 generations

Full size image

It is clear from Table 5 the proposed CSGA performs astonishingly well when compared to ACO, PSO, IA, and CS. The 5 best solutions obtained by CSGA are better than all the solutions obtained by the other algorithms. The 25 independent runs of CSGA return solutions with an average objective function value of 6.216, which is, by itself, better than the best solutions obtained by ACO, PSO, IA, and CS. It can thus be concluded that CSGA is a more efficient algorithm.

Computational experience

The performance of the proposed CSGA was further evaluated through comparing it with ACO proposed by Ghaiebi and Solimanpur (2007), the IA by Hsieh et al. (2011b) and CS by Lim et al. (2012) for the travelling salesman problem. The TSP problem was made to be easily reproducible. The arrangement of holes for the problem is considered as follows:

  • The number of rows in the workpiece is \(\lfloor \sqrt{I}\rfloor \) (floor of \(\sqrt{I}\)), where \(I\) is the total number of holes.

  • The center to center distance of adjacent holes in each direction is assumed to be 2 cm.

For example, the position of holes in the workpiece when N = 10 is shown in Fig. 7. As seen in this figure, the number of rows is \(\lfloor \sqrt{10}\rfloor = 3\).

Fig. 7
figure 7

Position and numbering of the 10 holes in the workpiece

Full size image

In solving this TSP problems, the number of holes considered were 5, 10, 15, 20, 25, 50, 100, 200, 500 and 1000.

We have implemented CSGA using MATLAB\(\circledR \) R2012a under 64-bit Linux Mint 14: Nadia operating system. Experiments are conducted on a desktop with Intel\(\circledR \) Core\(^{\mathrm{TM}}\) i7-2600 CPU @ 3.40 GHz x 4, and 12 GB of RAM. In each case study, 25 independent runs of the algorithms are carried out with a population number of 2.

The experimental results of the CSGA algorithm are compared with ACO, IA, and CS in Table 6. The results for ACO and IA are obtained from Ghaiebi and Solimanpur (2007) and Hsieh et al. (2011b), respectively, while the results for CS and CSGA are obtained through experiments. For all the test problems compared, CSGA and IA obtained equally good solutions. In terms of timings, it can be seen from Table 6 that ACO, CS, and CSGA performs equally well when \(N=5\) and \(N=10\). For \(N=15\) and \(N=20\), both ACO, CS, and CSGA obtained the optimal result and all three algorithms have very close timings. However, for \(N=25\) and \(N=50\), CSGA significantly outperform ACO and CS both in terms of both optimality and timings.

Table 6 Comparison of the experimental results of CSGA with ACO, IA, and CS
Full size table

The graphical solutions for the best sequences for the larger size problems obtained by CSGA are shown in Figs. 8, 9, 10 and 11, while the complete experimental results are summarized in Table 7, where the first column ‘N’ shows the number of holes, the column ‘Best’ shows the length of the best solution found by the algorithm, the column ‘Mean’ gives the average solution length of the 25 independent runs of the algorithm, while the column ‘Worst’ denotes the worst solution length obtained of 25 independent runs, the column ‘SD’ denotes the standard deviation of the solutions over 25 runs, and the column ‘Time’ shows the average time in seconds for 25 runs. In the Tables 6 and 7, the best results are presented in boldface. As the problem size grows the superiority of CSGA over CS becomes more apparent and overwhelming. For \(N=1000\) the best results obtained by CSGA is almost 3 times smaller than CS in addition to a near tenfold reduction in computational time.

Fig. 8
figure 8

The best sequence obtained for \(N=100\) by CSGA

Full size image
Fig. 9
figure 9

The best sequence obtained for \(N=200\) by CSGA

Full size image
Fig. 10
figure 10

The best sequence obtained for \(N=500\) by CSGA

Full size image
Fig. 11
figure 11

The best sequence obtained for \(N=1000\) by CSGA

Full size image
Table 7 Comparison of statistical results of CS and CSGA for TSP
Full size table

Figure 12 shows the convergence plot of the TSP problem with \(N=50\) and \(N=200\) obtained by CS and CSGA. It can be observed that CSGA converges quicker than CS and the prolonged generations of CSGA thereafter are just to slightly converge the solution further. It is evident that CSGA not only obtain better results, it also has a faster convergence speed when compared to CS.

Fig. 12
figure 12

The best solution by CSGA and CS

Full size image

Discussion and conclusion

In this paper, the hybrid CSGA was proposed by incorporating the evolutionary strategies of GA with the breeding behavior of cuckoos. By embedding the GA’s operators such as crossover and mutation into the standard CS imitates the real life behavior of cuckoo birds. The success or failure of population based algorithms depends on its ability to establish proper trade-off between exploration and exploitation. Since both GA and CS are population based algorithms, while developing the hybrid CSGA, more attention is given to the two major components of the algorithm: intensification and diversification, or exploitation and exploration (Blum and Roli 2003). The superior performance of CSGA can be explained by the balance between the exploration and exploitation ability of the algorithm. It is also partly due to the fact that the CSGA maintains the Lamarckian property of the solution (Gen and Cheng 2000). Having Lamarckian property in the solutions will ensure meaningful crossover between parent cuckoo birds.

The efficacy of the algorithm should also be attributed to the exploratory search in the 2-point crossover. In complex problems such as the hole-making problem addressed in this paper, many algorithms easily fall into a local minima. The vastly diversifying search of the 2-point crossover allows the CSGA to extensively search the solution space that would otherwise not be searched by the standard search strategies employed for the standard TSP. While exploring the solution space, the crossover of the cuckoo birds still retain partial identity of the parent cuckoo bird rather than blindly searching for better solutions. The mutation of the cuckoo eggs further improves the performance of the algorithm in contributing to the local search of the solution space by making small but logical changes in the genes. In addition, the rotation strategy applied at the end of every generation aids to the search for the global minimum with minimal computational cost, and further reducing the possibility of a premature convergence at a local minima. Some form of elitism strategy is used in CSGA to ensure that best solutions are always carried forward to the next generation.

Besides that, the proposed CSGA is designed in such a way that there is virtually no parameters to be fine tuned; it has only two basic parameters: the population size and the generation number. The balance between the exploration and exploitation ability of the algorithm can simply be adjusted by the population size and the generation number. A larger number of cuckoos will increase the diversifying ability, while increasing the generation number improves the intensification ability of the algorithm. With this in mind, the population size can simply be chosen based on the size and complexity of the problem. The stopping criterion of the optimization algorithm can then be chosen for a balance between time and solution quality desired by the user. The user can either set the maximum number of generations, or stop the algorithm if no change in solution was made after a certain number of generations.These unique characteristics of CSGA make the algorithm easy to implement and apply and will potentially be the attractive optimization technique for practical engineering optimization problems.

In hole-making operations, to search the best path to complete all the holes is a complex problem, in which random paths may lead to much waste in non-productive time. A 12 holes problem with different hole sizes is considered in this paper. A set of problem instances was also chosen to cover a wide spectrum of typical problem sizes, namely 5–1000 holes evenly distributed. In all the problems considered, CSGA prevailed at a level well above all algorithms compared. As a comparison between CSGA and its parent algorithm, the original CS uses Lévy flights and random walk to generate new solutions for the next iterations. In continuous space problems, these techniques are effective. However, dealing with discrete solutions with these techniques unnecessarily increases the computational cost. CSGA, which uses GA operators, are quick and there is no need to encode and decode the solutions. Thus, in solving combinatorial problems, CSGA surpasses CS in terms of efficiency.

Future works can emphasize on extending the application of this optimization technique to other complex combinatorial engineering optimization problems such as the redundancy allocation problem, the container loading problem, and the job shop scheduling problem.