INTRODUCTION
In a flowshop problem, a set of jobs must be processed on a number of
sequential machines, each job has to be processed on all machines and
the processing routes of all jobs are the same. In the general (nonpermutation)
case of the flowshop scheduling problem, the sequence of jobs on each
machine may be different from the sequence of jobs on another machine.
In the permutation case, these sequences are the same for all machines.
It is proved that the permutation flow shop does not necessarily provide
an optimal solution (Liao et al., 2006). These people show that
the performance of nonpermutation schedules is better than that of permutation
schedules. In general, when there are more than three machines, permutation
schedules are no longer dominant (Koulamas, 1998). In comparison with
the permutation schedules, the performance of nonpermutation schedules
may be considerable if the problems have nonregular performance measures
like maximum tardiness or weighted mean tardiness (Liao et al.,
2006). The nonpermutation schedules may provide much better solutions
in such situations. However, almost all existing researches have focused
on permutation schedules and there is a lack of sufficient analysis on
nonpermutation scheduling problems in the literature (Cheng et al.,
2000).
As the problem size grows bigger, identifying the best permutation schedule
itself becomes quite difficult. Obviously, finding an optimal solution
when sequence changes are permitted is more complex and difficult (Pugazhendhi
et al., 2002). In the literature, heuristic methods have usually
been used to solve the nonpermutation flowshop scheduling problems. Some
of them are Jain and Meeran (2002) and Koulamas (1998).
Two widely used objectives in the literature are the makespan and the
total flowtime, which are based on the completion times. The literature
abounds with numerous and very different techniques for the permutation
flowshop scheduling problem with these objectives. Ruiz and Maroto (2005)
have presented an extensive review and evaluation of many heuristics and
metaheuristics for the permutation flowshop scheduling problem with the
makespan criterion. Varadharajan and Chandrasekharan (2005) consider the
bicriteria permutation flowshop scheduling problem with the objectives
of minimizing the makespan and total flowtime of jobs and present a MultiObjective
Simulatedannealing Algorithm (MOSA) for solving the problem. Rajendran
and Hans (2004) have recently presented two ant colony algorithms (MMMAS
and PACO) for solving the permutation flowshop scheduling problem with
the objectives of makespan and total flowtime. The solutions of their
methods are the best results obtained so far on only one mainframe. We
show that the method proposed in this paper can obtain better solutions
than the MMMAS and PACO. A similar work has been done by Vallada and
Ruben (2008) for the makespan criterion. Their research is a state of
the art on the literature about the permutation flowshop scheduling problem
with makespan. They propose cooperative metaheuristic methods for the
problem. They use the island model where each island runs an instance
of the algorithm. We compare our method with the best solutions of this
cooperative metaheuristic (with 12 islands) and show that our solutions
are close to those reported by Vallada and Ruben (2008) but they have
used simultaneously 12 processors.
In this study, we consider the mmachine njob flowshop scheduling problem
with the objective functions of the makespan and the total flowtime separately.
We assume that the ready times of all the jobs are equal to zero. Therefore,
the total flowtime is equal to the total completion time. We develop an
ACO algorithm to solve the permutation case of the problem. The permutation
solution of the proposed ACO algorithm is then improved by a nonpermutation
local search. Therefore, the end solution of the method may be a nonpermutation
schedule. In order to evaluate the performance of the proposed metaheuristic,
we implement the method for the benchmark problems of Taillard (1993)
and present the results of the computational experiments. Finally, the
conclusion remarks of this study are presented at the end to summarize
the contribution of the study.
AN ACO ALGORITHM FOR SOLVING THE PROBLEM
Liao et al. (2006) show that there is little improvement made
by nonpermutation schedules over permutation schedules with respect to
the completiontime based criteria such as makespan and total flowtime.
Therefore, the proposed ACO algorithm is designed for generating only
the permutation sequences. However, we store n` best permutation solutions
of the ant colony procedure and then improve all of them by a rapid nonpermutation
local search. Storing best solutions for improving them may have an important
role to increase the performance of the method. The steps of the proposed
ant colony algorithm are as follows. Let z* be the objective function
of the best sequence obtained so far (BS). I, K are the number of jobs
and the number of machines respectively.
Step 1 (finding a seed permutation schedule): The algorithm uses
a constructive method to find an initial permutation schedule. We use
the NEH heuristic (Nawaz et al., 1983) to generate an initial permutation
sequence for the objective of minimizing the makespan and a heuristic
proposed by Woo and Yim (1998) to generate an initial permutation sequence
for the objective of minimizing the total flowtime of jobs. These heuristics
are powerful methods for solving a permutation flowshop scheduling problem
(Ruiz and Concepcion, 2005; Woo and Yim, 1998).
Step 2 (first local search): The first local search is done using
the pairwise exchanges (Allahverdi, 2003), on the sequence as follows.
We keep n1 best solutions.
21) 
Let: counter = 1, n = 1, 
22) 
Imprv = 0, 
23) 
For y_{1} = 1 (1) (I1) :
For y_{2} = (y_{1}+1) (1) I : 
Replace the job in the position y_{1} with the job in the position
y_{2} without changing the positions of the other jobs. If the
objective function of the resulted permutation sequence is less than or
equal to z*, do the following settings:
• 
Set the resulted sequence to δ_{n} and its objective
function to z* 
• 
n = n+1, 
• 
Imprv = 1, 
Otherwise, replace again the job in the position y_{1} with the
job in the position y_{2}.
24) 
counter = counter+1, 
25) 
If counter_{ }= C_{1} and Imprv=1, go to step 22, 

Else go to step 3 
Step 3 (second local search): All of n sequences obtained from
the previous section are improved by the second local search. This search
is done based on the shift neighborhood method (Osman and Potts, 1989),
which is defined by removing a job at one position and putting it to another
position. The local search continues until no new improvement occurs.
Let n_{0} = max (0, n1001). The steps of this local search are
as follows:
31) 
Let: counter = 1, 
32) 
Imprv = 0, 
33) 
For y_{1} = 1 (1) I : 

For y_{2} = 1 (1) I (y_{2} ≠ y_{1}): 
Remove the job at the position y_{1} and put it to the position
y_{2} in the sequence .
If the objective function of the resulted permutation sequence is less
than or equal to z*, do the following settings:
• 
Set the resulted sequence to δ* and its objective function
to z*, 
• 
Imprv = 1, 
Otherwise, put again the job in its first position (y_{1}),
34) 
counter = counter+1, 
35) 
If counter_{ }= C_{2} and Imprv=1, go to step 32, 

Else go to step 36, 
36) 
n_{0} = n_{0}+1, 
37) 
If n_{0}<n go to step 31. 
The best permutation sequence obtained from this step is now considered
as a seed sequence for the ant colony algorithm which is started from
the next step.
Step 4 (setting pheromones): Let f_{ij} be the pheromone
trail intensity (or desire) of setting job i in position j in a sequence.
Initially f_{ij}`s are calculated as follows:
We consider also F_{ij} as the sum of the pheromones from position
1 to position j (Rajendran and Ziegler, 2004). It may be interpreted as
the desire of setting job i at a position less than or equal to j and
calculated as follows:
Step 5 (construction of an ant sequence): Different methods were
tested to generate an ant sequence (AS) from the values of the pheromones
(Dorigo and Stützle, 2004). Finally, we chose the following method
for it provided better performance.
For j = 1 (1) I do:
• 
Select the following job for the j`th position of the ant sequence,
if it is not scheduled so far, 

• 
The job with the biggest F_{ij} with the probability α_{1},


• 
The job with the second biggest F_{ij} with the probability
α_{2}, 

• 
The job with the third biggest F_{ij} with the probability
α_{3}, 

• 
The job with the fourth biggest F_{ij} with the probability
α_{4}, 
• 
If no job has selected for j`th position of the ant sequence,
among nonscheduled jobs, select one with maximum F_{ij}. 
We chose the α_{i}`s such that α_{i} = 2 α_{i+1}
and obviously, Σα_{i} = 1. That is, α_{1}
= 8/15, α_{2} = 4/15, α_{3} = 2/15 and α_{4}
= 1/15.
Step 6 (local searches): Use local search procedures of steps
2 and 3 for n_{0} = n1.
Step 7 (updating pheromones and best sequence): BS is updated
if the objective value of AS is less than that of BS. The pheromones
are also updated as follows to take into account the new best solution.
In the above relation, A is the evaporation rate (we set A = 0.9), z
is the objective value of AS and d_{1} is calculated from the
following relation:
B is a parameter which sets the importance of the improvement (we set
B = 2). F_{ij}`s are also updated as follows:
To explain the above pheromone settings, suppose that job i is assigned
to position j in BS and f_{ij} is set to 1+3/z*. Nonpromising
ant sequences get pheromone value of 1/z in each iteration and therefore,
missing randomly BS in the pheromone settings may occur after at least
three iterations. The lower pheromones instead of 1+3/z*, for example
1+2/z*, may increase the probability of missing randomly BS and higher
pheromones may lead to cumulate the pheromones in BS and so the promissing
sequences may not be considered, even if we contact with them in some
ants. However we have used d_{1} parameter for decreasing the
probability of occurring this situation. It means that if we find a sequence
AS which is better than BS, the phromones of that AS will be increased
in comparison with the regular increment of phromones. The value of this
increment is proportional to the amount of difference between the objectives
of AS and BS.
Step 8 (stop criterion): Stop criterion can be defined either
by an upper bound on the number of iterations (ants), or by an upper bound
on the computational time. Stop if selected stopping criterion is met,
otherwise go to step 5.
Step 9 (nonpermutation local search): Several best permutation
schedules are kept for the nonpermutation local search. In this step,
all of them are subjected to the following improvement algorithm:
A better solution is searched in the neighborhood of the current solution and
the process stops when no improvement is found. A neighbor of a solution is
obtained by a pairwise exchange of two jobs on the k first machines or on the
k last machines, for k = 1 to K. The pairs consists of two jobs, the positions
of which are not further than 2: A job of rank j is tested for an exchange with
the job of rank (j+1) and the job of rank (j+2).
In the above local search, each job can violate the permutation condition
in the amount of at most 2 positions, i.e. if y_{ij}, j = 1, 2,
…, K is the position of j`th operation of job i on machine j, then
we have:
The first reason for the above choice is that, intuitively, the permutation
violation of more than 2 jobs may not be very promising. The second one
is that the purpose of this algorithm is to improve a permutation solution
rapidly. This can help us to improve a larger number of solutions. For
example, if we have the pair (1, 2) and 4 machines, the following replacements
are tested:
Description of the algorithm: The above algorithm starts with
an initial permutation schedule. This initial schedule is then improved
by two local searches to obtain a seed sequence for starting the ant colony
procedure. The first local search is based on the pairwise exchanges
and it can generate and store n1 sequences which are denoted by δ_{s};
s = 1, 2, …., n1 and subscript s demonstrates the rank of the corresponding
sequence with respect to the value of objective function. So if we have
two sequences: δ_{s1} and δ_{s2} and s_{1}<s_{2},
then the objective value of δ_{s1} is greater than or equal
to the objective value of δ_{s2}. This local search continues
until counter reaches to its upper bound (C_{1}+1) or no improvement
occurs in the current search. Therefore, the search will be repeated at
most C_{1} times. In step 3, at most 1000 best sequences [starting
from n_{0} = max(0, n1001)] among n sequences obtained from step
2 are selected and improved by the second local search. This local search
is based on the shift neighborhood. The value of n may be very large and
the memory error may be occurred, because the program should store n sequences.
To prevent this error, we can consider an upper bound (say UP) for n by
adding the following condition before the statement n = n+1:
If n = UP, then n = 0
The second local search continues until counter reaches to its upper
bound (C_{2}+1) or no improvement occurs in the current search.
COMPUTATIONAL EXPERIMENTS
Here, we describe the computational experiments used in order to evaluate
the effectiveness of the proposed metaheuristic method. The programs have
been coded in C++. The platform of our experiments is a personal computer
with a PentiumIV 1700 MHZ CPU and 512 MB RAM. The maximum number of ants
for each problem, is 10000 and maximum running time of ACO algorithm for
each problem is I(K/2)90 m sec (Vallada and Ruiz, 2008). The maximum running
time of nonpermutation local search is set to 10 sec for all problems.
We have also considered C_{1} = C_{2} = 50 for consideration
of the computational time. To compare the solutions of the proposed method
with some other methods, we have used the standard benchmark problems
of Taillard (1993). We have compared our solutions with the solutions
of two recent works which are Rajendran and Hans (2004) and Vallada and
Ruben (2008). The numerical results are shown in Table 13.
We have reported both of the permutation solutions obtained from the ACO
algorithm (in the column of PRMUT in the Table) and the nonpermutation
solutions obtained from the nonpermutation local search (in the column
of NONPRMUT in the Tables).
Table 1: 
The results of the computational experiments for the
objective of makespan 

Table 2: 
The results of the computational experiments for the
objective of total flowtime 

Table 3: 
The results of the computational experiments for
the objective of the total flowtime (end solutions) 

To calculate the mean relative percentage
increase in total flowtime, shown in Table 2, we have
considered the best solution among those of four methods (BES), (LR),
MMMAS, PACO and our method) as the best upper bound for the corresponding
problem. From the results, it can be seen that the proposed ant colony
method demonstrates better performance than the other methods for both
objectives.
CONCLUSION
In this study, we have developed an effective ACO algorithm to solve
the permutation flowshop scheduling problem. The permutation solutions
of this ACO algorithm are then improved by a nonpermutation local search.
Numerical experiments have been designed and performed to demonstrate
the potential applicability of the proposed method. The results have shown
that the proposed metaheuristic algorithm is clearly superior to the other
proposed metaheuristics.