1 Introduction

The general assumption of majority of flow-shop applications is that the sequencing of the jobs relies on buffers, otherwise they are considered as intermediate storage between machines. The no-wait flow-shop scheduling problem (NWFSP) with makespan criterion is considered in this paper. In NWFSP, each job has to be processed from the first machine to the last without any interruption and the job sequence is unique on all machines. In addition, each machine can handle no more than one job at a time and each job has to visit each machine exactly once. Therefore, the start of a job on the first machine may be delayed in order to meet the no-wait requirement. Given that the release time of all jobs is zero and set-up time on each machine is included in the processing time, the no-wait flow-shop problem is to schedule jobs that minimize the makespan over all jobs. The no-wait flow shop scheduling problem has important applications in modern industry. It has an extensive background in industrial applications, including steel production, mining, logistics, chemical industry and food processing. For example, in steel factories, to avoid cooling and defects in steel, the liquid steel undergoes a chain of operations such as molding into ingots, unmolding, and soaking. Similarly, in the food processing, the canning operation must be operated after cooking operations immediately to ensure freshness (Hall and Sriskandarajah 1996). A comprehensive survey on the research and application of no-wait flow-shop scheduling problem can be found in Hall and Sriskandarayah’s review paper (Hall and Sriskandarajah 1996). In addition, Bagchi et al. (2006) showed that it can be transformed into the asymmetric traveling salesman problem (ATSP) and presented some no-wait and blocking scheduling models.

In the operation research literature, many elegant mathematical models and methods have been developed to deal with the real-world problems. Some exact approaches have been proposed to unravel the problems optimally that have the limitation of solving only small-sized problems.

On the other hand, heuristics which are based on polynomial time algorithms are the most suitable methods for solving large scheduling problems. In general, heuristics attain good solutions in a reasonable time interval. Additionally, in the recent years meta-heuristics with techniques such as bee colony algorithm (Khorramizadeh and Riahi 2015), genetic algorithm (GA) (Guo et al. 2005), memetic algorithm (MA) (Frutos and Tohmé 2013), particle swarm optimization (PSO) (Marinakis et al. 2009), Electromagnetism-like Mechanism (SEM) (Bonyadi and Li 2010), and ant colony optimization (ACO) (Riahi and Kazemi 2015) have been developed to generate competitive results for many combinatorial optimization problems.

In the recent years, several ant colony algorithms have developed for various kinds of problems including the scheduling problem. Kashan and Karimi (2008) proposed two ACO algorithms with two different visibility functions for total weighted tardiness single machine environment with formation of processing batches. To minimize total completion time in a no-wait two-machine flow-shop, Shyu et al. (2004) designed some specific features including a heuristic for initializing the initial pheromone, a hybrid state transition rule and a hybrid local search. Li et al. (2011) dealt with the minimization of the sum of completion time in a sequence-dependent setups permutational flowshop. The authors used a time-limited dynamic programming algorithm to perform a post-optimization strategy. Mirabi (2011) proposed an ant colony optimization technique for the sequence-dependent flowshop scheduling problem. The proposed algorithm contained a new pheromone initialization procedure and a local search method. Rui et al. (2014) presented an ant colony algorithm to solve the integrated job shop scheduling problem with tool flow in flexible manufacturing system. Huang et al. (Huang et al. 2015) proposed a no-wait FSMP problem with time window constraint which a new ant colony optimization (ACO), known as ant colony optimization with flexible update (ACOFU), is presented to solve the problem. The results show that ACOFU is superior to ACO when applied to small-scale problems. Recently, due to these insights, ACO is selected to solve this problem based on its ability and performance in solving scheduling problems. This is our incentive to employ ACO for solving the presented research problem.

On the other side, however SA usually is considered as one of the best algorithms that applied as a local search to improve the quality of solutions (Jolai et al. 2013; Wang et al. 2011; Xiao et al. 2015; Elmi et al. 2011; Mirsanei et al. 2011), a wide range of research on the literature review indicates that research with hybridization of ACO and SA is very rare. Behnamian et al. (2009) considered a scheduling problem with parallel machine and setup times. The authors combined ACO algorithm with the VNS and SA to balance exploration and exploitation.

In this paper, we develop an effective hybrid ant colony algorithm where the new approach to simulated annealing as a local search algorithm is presented as an improvement phase. To show its performance, we use another method based on one popular method, VNS, as a local search in proposed ACO. In addition, based on the main characteristics of the considered problem, we propose a new approach for global update that takes advantage of increasing diversity by a probability criterion. The computational comparison demonstrated the effectiveness of the presented hybrid ACO algorithm and shows that our algorithm is able to provide competitive results in reasonable CPU times and our new simulated annealing method has a better performance than VNS algorithm for a local search.

This paper is structured as follows: the no-wait flow shop problem is described Sect. 2. Section 3 introduced new ant colony optimization algorithm, whereas the experimentation is given in Sect. 4. The paper is concluded in Sect. 5.

2 The no-wait flowshop scheduling problem

In this Section, we first define the NWFSP with a makespan criterion. Then, we review the relevant literature.

2.1 Problem formulation

The NWFSP can be defined as: a set of jobs is available for processing on machines. Each job has a sequence of operations. Each machine can process one job at a time and each job must be performed only on one machine at a time. All jobs must be completed without interruption and the jobs should not wait to be scheduled between two successive machines. The problem is finding a schedule in a way that the processing order of jobs is the same on each machine and the maximum completion time is minimized.

The following notations are used to formulate the no-wait flow-shop problems:

n :

Number of jobs,

m :

Number of machines,

pij :

Processing time for the job i on the machine j

p[i]j :

Processing time for the job in the position i on the machine j

d ik :

Minimum delay between the start of job \( i \) and job \( k \)on the first machine due to the no-wait restriction,

C[i] :

The completion time of the job located on position \( i \)

The minimum delay time \( d_{ik} \) and completion time \( C_{\left[ i \right]} \) can be calculated using the following equations:

$$ d_{ik} = p_{i1} + \hbox{max} \left\{ {\mathop {\hbox{max} }\limits_{2 \le j \le m} \left( {\mathop \sum \limits_{l = 2}^{j} p_{il} - \mathop \sum \limits_{l = 1}^{j - 1} p_{kl} } \right), 0} \right\} $$
(1)
$$ C_{\left[ 1 \right]} = \mathop \sum \limits_{j = 1}^{m} p_{\left[ 1 \right]j} $$
(2)
$$ C_{\left[ i \right]} = \mathop \sum \limits_{l = 2}^{i} d_{{\left[ {l - 1} \right]\left[ l \right]}} + \mathop \sum \limits_{j = 1}^{m} p_{\left[ i \right]j i = 2,3,..,n} $$
(3)

So, the maximum completion time (makespan) can be obtained as follows:

$$ C_{\hbox{max} } = \mathop {\hbox{max} }\limits_{1 \le i \le n} \left\{ {C_{\left[ i \right]} } \right\}.$$
(4)

2.2 Literature review

According to Garay and Johnson (1979), the no-wait flow-shop scheduling problem is NP-hard. Therefore, heuristic procedures due to their polynomial time complexity are preferred as the most suitable optimization methods to solve these scheduling problems. Important heuristics for the no-wait flowshop to minimize the makespan are slope index (Bonney and Gundry 1976), Minimum covering level (MCL) (King and Spachis 1980), Raj (Gangadharan and Rajendran 1994), Framinan-Nagano heuristic (FN) (Framinan et al. 2010), Fast composite heuristic (FCH) (Li and Wu 2008), Li-Wang-Wu heuristic (LWW) (Li et al. 2008) and Laha-Chakraborty heuristic (LCH) (Laha and Chakraborty 2009).

In addition, it has been examined by some researchers applying different meta-heuristics. Aldowaisan and Allahverdi (2003) designed methods based on simulated annealing and genetic algorithm. Schuster and Framinan (2003) implemented a variable neighborhood search algorithm (VNS) and a hybrid algorithm GASA to solve the no-wait job shop scheduling problems. Grabowski and Pempera (2005) presented five heuristic algorithms for NWFSP, where three Tabu Search (TS) based algorithms (TS, TS + M, TS + MP) were developed by using the TS with multi-moves and the other were based on descending search (DS) and descending search with multi-moves (DS + M). Revealed by experimental results, these tabu search methods outperform the VNS and the GASA. Liu et al. (2007) proposed an effective algorithm based on hybrid particle swarm optimization (HPSO) and Nawaz-Enscore-Ham (NEH) heuristic (Nawaz et al. 1983) to minimize makespan. Pan et al. (2008) presented a DPSO algorithm for the NWFSP. They also hybridized the variable neighborhood descent (VND) algorithm and discrete particle swarm optimization (DPSO) to further enhance its searching ability. The results show that the presented algorithm was effectiveness and is better than other algorithms both heuristic and meta-heuristic in the literature.

Pan et al. (2008) applied an improved iterated greedy algorithm (IIGA) to solve NWFSP. In that paper, they introduced a speed-up method for insert neighborhood and a new heuristic algorithm based on NEH heuristic algorithm. In 2009, Qian et al. (2009) proposed a hybrid differential evolution (HDE) approach with a new local search to solve NWFSP. Tseng and Lin (2010) proposed a hybrid GA (HGA), which hybridizes a GA and a novel local search scheme which combines two local search methods: the Insertion Search (IS) and a novel local search method called the Insertion Search with Cut-and-Repair (ISCR). Samarghandi and ElMekkawy (2012) proposed a hybrid TS and PSO algorithm and utilized a new coding and decoding technique to improve its efficiency. Ding et al. (2015) proposes a Tabu-mechanism improved iterated greedy (TMIIG) algorithm with a Tabu reconstruction strategy which improves the exploitation ability of the algorithm and leads to better performance.

3 Description of the proposed ACO algorithm

In this section, we described the proposed ACO algorithm for the no-wait flowshop scheduling problem. The ACO algorithm is utilized to generate initial scheduling. Then the ACO solutions are improved by using a new local search method. The explanations of these algorithms are as follows:

The ACO meta-heuristics algorithm, was introduced by Colorni et al. (1991) for the first time, and has been successfully applied to a large number of combinatorial optimization problems. This algorithm is inspired by the behavior of real ants in finding the shortest path from a food source to the nest.

In ACO algorithm a feasible solution is usually shown as a path in a graph. In NWFSP, the graph of the problem is shown with a complete graph where the vertices correspond to the activities. Each sequence of scheduling the jobs can be shown as a directed path which includes all the vertices in the graph of the problem. Therefore, finding a feasible solution lead to find such directed path.

According to previous studies, ACO can work effectively to find good solutions in scheduling problems if it benefits from effective local search and constructive pheromone updating rule. This inspired us to develop a new ACO to solve no-wait flowshop problem. Flowshop scheduling problem can be regarded as a hard optimization problem. As a result, simple ACO with traditional pheromone updating trail and completely random search methods to find following values may not perform efficiently in an appropriate time. Consequently, the ACO developed in this paper has been benefited of a new approach to Global update of pheromone trail and applies effective local search based on a new simulated annealing algorithm.

The general structure of the proposed ACO algorithm is then represented as follows (the details are presented in the remainder of this section):

Step 1. Set parameter; generate an initial solution and initialize the pheromone trails

Step 2. While the termination condition is not met, do the following:

Step 2.1 For each ant in the colony, do:

  a. Construct a solution by repeatedly applying the transition rule

  b. Apply the pheromone local update rule;

Step 2.2. Find the best solution generated in step 2.1 and improve the solution quality by the local search;

Step 2.3. Modify the pheromone trails according to the global updating rule;

Step 2.4. Update the minimum and maximum trail bounds, and limit the pheromone trails.

Step 3. Return the best solution found.

3.1 Pheromone initialization

\( \tau_{ij} \) is considered as the intensity of assigning ith job in jth position. This desirability is changed during the running of the ACO algorithm. So, there is a pheromone value for every job \( i \) for every feasible position \( j \) that can be updated at each iteration of ACO algorithm.

In this paper, like PACO proposed by Rajendran and Ziegler (2004), an initial differential setting of the trail intensities is considered. In this paper we consider an upper bound τ max and a lower bound τ min for the trail pheromone that calculated by the following formulas:

$$ \tau_{max} = \left( {\left( {1 - \rho } \right)Z_{best} } \right)^{ - 1} $$
(5)
$$ \tau_{min} = \beta \tau_{max} $$
(6)

where Z best denotes the best makespan obtained so far and \( \rho (0 \le \rho \le 1) \) is the parameter of the algorithm and for initially, it equals the makespan of Rajendran’s heuristic (1993), so, the initial pheromone are chosen as \( \tau_{ij} = \tau_{\hbox{max} } = \left( {\left( {1 - \rho } \right)Z_{best} } \right)^{ - 1} \) for all i and j.

The Raj heuristic is a variant of the NEH heuristic (1983) that is regarded as the best heuristic for the flow shop. It has three phases which are explained as follows:

  1. Step 1

    Calculate the value of \( {\text{T}}\left( {\text{i}} \right) \) defined by Eq. (7) for each job i. Then, obtain a sequence π = (π 1, π 2, …π i , …π n ) by sorting jobs according to their increasing \( {\text{T}}\left( {\text{i}} \right) \)

    $$ T\left( i \right) = \sum _{j = 1}^{m} \left[ {\left( {m - j + 1} \right)t_{ij} } \right] $$
    (7)
  2. Step 2

    The first two jobs of π are taken, and the two possible subsequences of these two jobs are evaluated, and then select the better one as the current sequence s. Set k = 2.

  3. Step 3

    Set k = k + 1. Take the kth job of π and insert it into p (p ∊ [1, k − 1]) possible positions of the current sequence s; we obtain p subsequences. Select the subsequence with the minimum makespan as the current sequence s for the next generation. Repeat this step until all jobs are sequenced, and the final sequence is found.

3.2 Make feasible solution

A set of artificial ants is initially created. Each ant starts with an empty sequence and then successively appends an unscheduled job to the partial sequence until a feasible solution is constructed (or all jobs are scheduled). In choosing the next job j to be appended after job i, the ant applies the following state transition rule:

$$ j = \left\{ {\begin{array}{*{20}l} {\arg \hbox{max} \left( {\tau_{ij}} \right),} & {if\;q \le q_{0} } \\ {S,} & {otherwise} \\ \end{array} } \right. $$
(8)

q is a random number uniformly distributed in [0,1], and q 0 is a parameter between 0 and 1. If q ≤ q 0, the unscheduled job j with maximum value is placed after job i; otherwise, a job is chosen according to S. the random variable S is selected according to the probability distribution given in Eq. 9.

$$ P_{ij}^{k} = \frac{{\tau_{ij} }}{{\mathop \sum \nolimits_{{j \in N_{j}^{k} }} \tau_{ij} }} ,\quad i \in N_{j}^{k} $$
(9)

where N k j is the set of unscheduled jobs.

3.3 Local update of pheromone trail

To avoid premature convergence, a local trail update is performed. The local update reduces the pheromone amount of a new component so that the following ants have a less probability to choose this job in the same place. This is achieved by the following local updating rule:

$$ \tau_{ij}^{new} = \left( {1 - \rho } \right)\tau_{ij}^{old} + \frac{\rho }{{C_{\hbox{max} }^{k} }} $$
(10)

where \( \rho \left( {0 \le \rho \le 1} \right) \) is the parameter of the algorithm. And C k max is the makespan of the complete sequence of ant k.

3.4 Local search

Once a complete sequence of jobs has been generated by all ants, the performance quality of the solution is improved by means of a local search procedure. In this paper, two algorithms are proposed based on the simulated annealing algorithm and variable neighborhood search method are used for the local search.

3.4.1 A variable neighborhood search for the local search

VNS (Mladenovi´c and Hansen 1997) is a stochastic algorithm in which, first, a set of neighborhood structures N k \( \left( {k = 1, . . . , n} \right) \) are defined. Then, each iteration of the algorithm is composed of three steps: shaking, local search, and change.

In this paper, a modified variable neighborhood search (VNS) that is incorporated into Liu and Liu (2013) algorithm as a hybrid strategy is used. In Liu and Liu (2013), they used two neighborhood structures called swap and insert local search respectively. Insert move that operates on sequence of jobs π and removes the job π(x) from its original position x, and next insert it in a position y in π, whereas Swap move in which the jobs π(x) and π(y), \( x \ne y \), are interchanged in some positions x and y in π. In presented VNS, each job is considered for possible insertion in all other positions after considering all possible swaps of pairs of job’s positions. At used VNS, the best individual of ants is selected as the seed permutation. In fact, searching neighborhood for the best local optimum is repeated with first neighborhood structure until no improvement appears: the seed permutation is updated if the new solution is better than the seed permutation and search is continued; otherwise the neighborhood is changed, and search is continue with second neighborhood structure until no possible improvement.

3.4.2 The simulated annealing (SA) as a local search

SA is one of the most popular meta-heuristics for addressing combinatorial optimization problems over the past two decades.

SA method differs from the most local search heuristics because it uses two or more neighborhoods, instead of one, in its structure. In particular, they are based on the principle of systematic change of neighborhood during the search. A standard SA algorithm begins with generating an initial random solution. Then, iteratively produce a neighbor solution. The new solution will be accepted as the new current solution if it has a lower or equal cost; otherwise its acceptance is based on a probability function. The process is repeated until the termination condition is satisfied (Low et al. 2004).

In presented SA, in order to increase the quality of the solution, some neighborhood generation structures are used and to increase the searching speed of the proposed SA, some additional termination criteria are presented.

To start the procedure, SA generates an initial solution as the incumbent solution and after that SA proceeds in several iterations. After setting parameter, at each iteration, a random neighbor is generated. Moves that improve the objective function are always accepted. Otherwise, the neighbor is selected with a given probability that depends on the current temperature and the amount of degradation \( \Delta E \) of the objective function. \( \Delta E \) represents the difference in the objective value between the current solution and the generated neighboring solution. As the algorithm progresses, the probability that such moves are accepted decreases.

In our algorithm, contrast to the most other studies in literature (Ying et al. 2012; Dai et al. 2013; Rabiee et al. 2014) that just use temperature, T, as a stopping criterion, some additional termination criteria are presented. In this paper, the proposed SA is similar to the SA developed by Low (2005). The main difference between the proposed SA and those developed by Low (2005) is that in proposed algorithm, to increase the quality of solution and the speed of algorithm, different termination criteria have been considered. This difference allows the algorithm to find the final solution from fairly diversified solutions and relies more on solutions with good qualities. In addition, we’ve used a Moving List (ML) that is empty first (ML ← ∅) and after insertion and swap operators, find the eight operators that result in the smallest amount of makespan. Put these eight operators in ML.

For more clarification algorithms, steps are explained in Algorithm 1.

figure a

Based on the generic SA algorithm, the details of the proposed SA algorithm for the no-wait flow shop scheduling problem are given below.

3.4.2.1 Initial solution and neighborhood

The best randomly solution generated by ants is used as an initial solution. Given a sequence S, a new sequence can be obtained for S using one of the swap or insertion operations described in the proposed VNS algorithm.

3.4.2.2 Move acceptance

In order to escape from local minima, the probabilistic acceptance of a non-improving neighbor is used. The probability of accepting a non-improving neighbor is proportional to the temperature T and inversely proportional to the change of the objective function \( \Delta E \). So that, the probability of replacing one solution with its neighbor, when \( \Delta E > 0 \), is e −∆E/T. In fact, the non-improving solution will be accepted if L, a random number between zero and one, was lower than e −∆E/T.

3.4.2.3 Cooling schedule

The cooling schedule temperature T k has a great impact on the success of the SA optimization algorithm. It decrease after each iteration according to the formula T k  = β * T k − 1, where 0 < β < 1.

3.4.2.4 Termination conditions

In this paper, stopping criteria may be used are the following:

  • Reaching a final temperature T k (if T k is lower than a pre-specified final temperature).

  • Achieving a predetermined number of iterations with improvement in the best found solution.

  • Reaching a fixed number of iterations that solutions are accepted with probability acceptance.

4 Global update of pheromone trail

The global updating rule is applied after all ants generate their solutions and the local search applied. Unlike most other studies that apply global update just on the best solution so far Ahmadizar (2012), Xu et al. (2012), in this paper, based on the idea of SA algorithm, global update is applied for all of ML’s solutions with a probabilistic acceptance. The pheromone trails are modified according to the following global updating rule to make the search more directed:

$$ \tau_{ij}^{new} = \left\{ {\begin{array}{*{20}l} {\rho \tau_{ij}^{old} + \Delta \tau_{ij} } & {for\;all\;solutions\;in\;moving\;List} \\ {\rho \tau_{ij}^{old} } & {Otherwise } \\ \end{array} } \right. $$
(11)

where \( \Delta \tau_{ij} \) is controlled by probability criterion.

That is, if

$$ C_{max}^{{ML_{i} }} = C_{max}^{best} or\;exp\left( { - \Delta C/R} \right) > rand\left( {0,1} \right) $$
(12)
$$ \Delta \tau_{ij} = \frac{1}{{C_{max}^{{ML_{i} }} }} $$
(13)

In above equation, R is a constant and \( \Delta C = C_{max}^{{ML_{i} }} - C_{max}^{best} \) where \( C_{max}^{{ML_{i} }} \) is the makespan of the \( ML_{i} \left( {i = 1, \ldots ,8} \right) \) solution and \( C_{max}^{best} \) is the best makespan obtained so far. If criterion is not satisfied \( \Delta \tau_{ij} = 0 \).

With proposed procedure, the immature homology can be effectively avoided and the diversity of solutions in later iterations increased as well.

After modifying the pheromone trail intensities according to the above global updating rule, upper bound and lower bound are updated Then, any pheromone trail out of this range (τ max and τ min ) should be adjusted, so, in case of τ new ij  > τ max or τ new ij  < τ min , the τ new ij is set to τ max or τ min respectively.

5 Computational result comparisons

The proposed modified ant colony optimization algorithm is implemented in Delphi 7.0. Tests are run on a dual core 3.6 GH, CPU with 2 GB memory.

All of the parameters in this study were determined experimentally. The parameter settings for the presented SS are listed in Table 1.

Table 1 Parameter settings for the ACO–SA algorithm
Full size table

We conducted experiments on 29 benchmark problems which consists of eight problems (car1, car2… car8) provided by Carlier (1978) and 21 problems provided by Reeves (1995). As the optimal solution is unknown for the larger instances, the performance of the proposed algorithm is evaluated with a distance from the Rajendran heuristic algorithm (1994). \( t \) denotes the average CPU time (in second) of 20 runs (R = 20).

The performance in this paper, to report the statistics based on the percentage of relative deviations from Rajendran, they were denoted as RAJ. To be more specific percentage relative difference (PRD) was computed as follows:

$$ PRD = \frac{{\left( {M_{i} - M_{ref} } \right)}}{{M_{ref} }} \times 100 $$
(14)

where M i and M ref , were the makespan generated by algorithms and the reference makespan generated by RAJ.

The proposed algorithms are compared with 7 other heuristics which can be seen in Table 2. TS, TS + M and TS + MP are three local search algorithms based on several variants of descending search and tabu search algorithms employed by Garbowski and Pempera (2005), the VNS and GA-SA of Schuster and Framinan (2003), HPSO represents the results of Liu et al. (2007), HGA of Tseng and Lin (2010) and TS/PSO of the Samarghandi and ElMekkawy (2012). Due to the fact that the computational time consumed by these tested algorithms generally does not exceed one second on average, time consumption is not the main issue for this problem. Consequently, we conclude that the proposed ACO–SA algorithm can outperform these advanced algorithms for the NWFSP in minimizing the makespan.

Table 2 Results of best algorithms
Full size table

The comparison is based on the instances of Carlier and reeves. Table 2 shows the experimental results for the nine algorithms in comparison. As shown in Tables 2, our ACO–SA algorithm is competitive with all both local search-based algorithms and population-based algorithms. In fact, Analysis of Table 2 reveals that the searching quality of proposed ACO–SA is superiorly relative to other algorithms with respect of quality of solutions. As can be observed in the Table 2, the total average of RPD by the proposed ACO–SA algorithm is −4.85, which is superior to the corresponding values of −3.81, −1.2, −4.52, −4.76, −4.74, −4.6, −4.82 and −4.67 obtained by the VNS, GASA, TS, TS + M, TS + MP, HPSO, HGA and TS/PSO, respectively. By comparing our algorithm with HGA that have a better performance than others, in 6 instances, it has a better results than ours. However, in these instances solutions were close. But in 6 instances, our algorithm has a superiority than HGA algorithm.

In addition, for proving the efficiency of presented SA and its importance in proposed algorithm, we used VNS as another method of local search. Table 3 summarizes the computational results for our algorithm without any local search, ACO-VNS and ACO–SA algorithms.

Table 3 Results of proposed algorithms
Full size table

In addition, it is observed from Table 3 that the ACO–SA has better performance than ACO-VNS in both CPU times and the quality of solutions, besides it has a significant effect on our algorithm. It is clear that the new approach for simulated annealing as a local search and hybridization with ACO increases its quality of searching and decreases its CPU Times especially in large size benchmarks rather than VNS.

The comparison results of Tables 2 and 3 prove that our algorithm without local search (ACO) is competitive and better than some local search-based algorithms (GASA, DS, DS + M). In addition, we can see that the ACO-VNS is competitive as well compared to other algorithms in literature.

In the procedure, there is a parameter includes ρ, which may has great effect on the performance of the presented ACO–SA algorithm. Therefore, we further investigate the effect of ρ by experiments. We vary ρ from 0.1 to 0.9. The contrastive results are presented in Fig. 1. From Fig. 1, different percent of average PRD values was showed based on different values of ρ produce that revealed this fact that the parameter ρ affects the searching quality of the presented algorithm. Indeed, presented algorithm had its best performance when the parameter ρ is equal to 0.8 due to its minimum average PRD value.

Fig. 1
figure 1

Effect of the parameter \( \varvec{\rho} \)

Full size image

On the other hand, we evaluate another experiment to test the performance of the proposed algorithm on the 110 problems presented by Taillard (1993). The results of algorithms after 10 runs are given in Table 4. Due to the efficiency of ACO-VNS based on its results in Table 3, we compare our algorithm with this algorithm in this experiment. Results show that proposed algorithm, ACO–SA, is effective and has reliable performance.

Table 4 Results of proposed algorithms on Taillard’s benchmark problems
Full size table

In order to prove the efficiency of our algorithm, we evaluated it with respect to the total flowtime criterion. Fink and Voß (2003) presented some construction methods and meta-heuristics for the no-wait flowshop scheduling problem with the total flowtime criterion. The benchmark experimentation results have been given in Table 5. The results are presented as each the job instance sizes. The average, minimum and maximum were given. ACO–SA has 10 independent replications for each instance and outcomes have been given in Table 6. According to the results, ACO–SA has better performance than F&V algorithm, due to an average PRD of −0.5405.

Table 5 Summarized results of F&V
Full size table
Table 6 Computation comparison of ACO–SA with F&V
Full size table

6 Conclusion and future work

In the current research, a no-wait flow-shop scheduling problem (NWFSP) for minimizing the makespan was discussed. This problem is known to be strongly NP-hard. In this paper, ant colony algorithm with the simulated annealing as a local search method are proposed to solve this problem. Unlike most of other reported population-based algorithms in the literature, the proposed ACO–SA algorithm is simple and easy to implement and replicate. The evaluation of the proposed methods was carried out against the 8 best performing methods from the literature. Statistical analyses and extensive experimental demonstrate the efficiency of the proposed ACO–SA algorithm owing to an average PRD of −4.85. In order to prove the efficiency of our algorithms, we use another method based on VNS for local search phase. The computational results are indicated that hybridization ACO with SA is viable and reliable method and really competitive and provides promising computational results. As the future work, other neighborhood’s structures can be applied in SA algorithm. In addition, the proposed algorithm can be used to solve the NWFSP with set-up times, maintenance of machines and transportation times. Furthermore, combining ACO with other local search-based algorithms such as Iterated local search or tabu search algorithm is possible research method.