Expert Systems with Applications 39 (2012) 8149 8161
Contents lists available at SciVerse ScienceDirect
Expert Systems with Applications
journal homepage: www.elsevier.com/locate/eswa
New VNS heuristic for total flowtime flowshop scheduling problem
a,Ń! b b
Wagner Emanoel Costa , Marco César Goldbarg , Elizabeth G. Goldbarg
a
Programa de Pós-Graduaçćo em Sistemas e Computaçćo, UFRN/CCET/PPGSC  Campus, Universitário Lagoa Nova, Natal, RN, Brazil
b
Departamento de Informática e Matemática Aplicada, UFRN/CCET/DIMAp  Campus, Universitário Lagoa Nova, Natal, RN, Brazil
a r t i c l e i n f o a b s t r a c t
Keywords: This paper presents a new Variable Neighborhood Search (VNS) approach to the permutational flowshop
Flowshop
scheduling with total flowtime criterion, which produced 29 novel solutions for benchmark instances of
Scheduling
the investigated problem. Although many hybrid approaches that use VNS do exist in the problems
Total flowtime
literature, no experimental study was made examining distinct VNS alternatives or their calibration. In this
Heuristics
study six different ways to combine the two most used neighborhoods in the literature of the problem,
VNS
named job interchange and job insert, are examined. Computational experiments were carried on instances
of a known dataset and the results indicate that one of the six tested VNS methods, named VNS4, is quite
effective. It was compared to a state-of-the-art evolutionary approach and statistical tests applied on the
computational results indicate that VNS4 outperforms its competitor on most benchmark instances.
Ó 2012 Elsevier Ltd. All rights reserved.
1. Introduction pletion time of p1 on machine r, 1 < r6m, as the completion time
of p1 on the previous machine, C(p1, r 1), plus the processing
In the permutational flowshop scheduling problem, there is a time of job p1 on machine r, t1,r.
set of jobs J = {1, 2,. . ., n}. Each of n jobs has to be processed by a
Cðp1;1Þźtp1;1 ð2Þ
set of m machines M = {1, 2,. . .,m}, sequentially from the first ma-
Cðp1;rÞźCðp1;r 1Þþtp1;r 8r2f2;. . .;mgð3Þ
chine to the last, in the same order. Each job j requires tjr units of
time on machine r. Each machine can process at most one job at
Eqs. (4) and (5) evaluate the completion times for each job pi,
any given time, and it cannot be interrupted. Each job is available
1at time zero and can be processed by at most one machine in any
time of the previous job on the first machine, C(pi 1,1), with the
given time. Here the focus is to find the permutation of jobs
processing time of pi, ti,1. For all remaining machines, 1 < r6m,
P ={p1,p2,. . .,pn}, such that the total completion time of jobs,
completion time of job pi, C(pi, r), 1 < i6n, depends on two factors.
named total flowtime (TFT), is minimized. Eq. (1) expresses math-
First, the time on which job pi concludes its processing on the pre-
ematically the concept of total flowtime of a given permutation, P,
vious machine, r 1, and therefore becomes available to be pro-
where C(pi, m) stands for the completion time of job in position i of
cessed on machine r. Second, machine r can process job pi only, if
P, pi. According to Rajendran and Ziegler (1997), TFT is an impor-
r has finished processing the previous job, pi 1. If machine r has
tant objective in many real life manufacturing systems, for it min-
not concluded the previous job, pi 1, then the processing of job pi
imizes holding costs.
will start after machine r concludes job pi 1. Eq. (5) expresses both
factors and defines the completion time, C(pi, r), 1 < i6n and
1n
X
between C(pi,r 1) and C(pi 1,r).
TFTðPÞź Cðpi;mÞð1Þ
iź1
Cðpi;1ÞźCðpi 1;1Þþtpi;1 8i2f2;. . .;ngð4Þ
The values of C(pi, m) can be evaluated using Eqs. (2) (5). Eqs.
Cðpi;rÞźmaxfCðpi;r 1Þ;Cðpi 1;rÞgþtpi;r 8i
(2) and (3) define the completion time relative to the first job in
permutation P, p1. Eq. (2) defines the completion time of the first
2f2;. . .;ng 8r2f2;. . .;mgð5Þ
job, p1, on the first machine as time required to complete its pro-
cessing, t1,1. It provides a base case for (3) which defines the com- Due to the fact that the decision problem associated with TFT is NP-
Complete in the strong sense when m P 2(Graham, Lawler, Lenstra,
& Kan, 1979), many heuristic approaches have been proposed to
Ń!
Corresponding author. Tel.: [phone].
this problem such as constructive methods (Framinan, Leisten, &
E-mail addresses: [e-mail] (W.E. Costa), [e-mail] (M.C.
Goldbarg), [e-mail] (E.G. Goldbarg). Ruiz-Usano, 2002; Liu & Reeves, 2001; Nagano & Moccellin, 2007;
0957-4174/$ - see front matter Ó 2012 Elsevier Ltd. All rights reserved.
doi:10.1016/j.eswa.2012.01.152
8150 W.E. Costa et al. / Expert Systems with Applications 39 (2012) 8149 8161
Rajendran, 1993; Rajendran & Ziegler, 1997), local search methods only some constructive methods in literature, and metaheuristic ap-
(Dong, Huang, & Chen, 2009; Liu & Reeves, 2001) genetic algorithms proaches that constitute the current state-of-the-art of the problem.
(Nagano, Ruiz, & Lorena, 2008; Tseng & Lin, 2009; Xu, Xu, & Gu, The method of Rajendran and Ziegler (1997) evaluates the lower
2011; Zhang, Li, & Wang, 2009a), ant colonies (Rajendran & Ziegler, bound for each job available for assignment, and creates, m different
2004; Zhang, Li, Wang, & Zhu, 2009b), particle swarm optimization solutions by changing as many machines as were considered in eval-
(Jarboui, Ibrahim, Siarry, & Rebai, 2008; Tasgetiren, Liang, Sevkli, & uating the lower bound. For instance, the first solution was con-
Gencyilmaz, 2007, 2007), bee colony optimization (Tasgetiren, Pan, structed by sorting the jobs, in the non-decreasing order, by the
Suganthan, & Chen, 2010), hybrid discrete differential evolutionary weighted sum of the processing times of all m machines. The
algorithm (Tasgetiren et al., 2010), VNS and EDA-VNS (Jarboui, weights are defined in such a way that one unit of processing time
Eddaly, & Siarry, 2009). of a machine, r = j, has greater impact than one unit of time of subse-
From the cited approaches, the works of Zhang et al. (2009a), quent machines, r > j. Eq. (6) shows the formula for the unweighted
Tseng and Lin (2009), Jarboui et al. (2009), Tasgetiren et al. total flowtime. The equation for the weighted total flowtime is
(2010) and Xu et al. (2011) are the ones which produced the cur- slightly different, but the weighted case is not the topic of discussion
rent state-of-art results. in this work. The processing time of the first machine is deleted, and
A significant number among the state-of-art approaches com- the jobs re-sorted considering only the processing times of the m 1
bine two neighborhoods, named job insert and job interchange, machines. This procedure is repeated, by deleting data from one ma-
in an internal VND procedure. The two neighborhoods are com- chine at each iteration until the last solution is created, when only
bined in the same order in the works of Zhang et al. (2009a), Tas- the processing time of the last machine is taken into account. The
getiren et al. (2010) and Xu et al. (2011). Within flowshop s best solution among the m created ones is then submitted to a local
literature, the only work to test distinct ways to combine these search procedure using job insert neighborhood.
neighborhoods is Pan, Tasgetiren, and Liang (2008), where a hybrid
m
X
heuristic, particle swarm with VND, is devised for the no-wait
ðm rþ1ÞTri j2f1;. . .;mgð6Þ
flowshop problem. The experiments of Pan et al. (2008), test the
rźj
hybridization of a PSO algorithm with two VND approaches, one
The method H(1) (Liu & Reeves, 2001) weights down two crite-
starting with job insert and the other starting with job interchange.
ria: weighted sum of machine idle time (IT) and artificial flowtime
Both of them create all neighboring solutions before deciding to
(AT). The idle time criterion for selecting job i when k jobs were al-
which solution to migrate. The results point out that the use of
ready selected (ITik), is defined by Eq. (7), where wrk is calculated
job interchange as the initial neighborhood provides the best per-
with Eq. (8). When the difference between C(i, r 1) and C(pk, r)
formance on the tested instances of the no-wait flowshop. So far no
is positive, means machine r is idle. The weights, as defined in
study has been reported, for classical flowshop with total flowtime
Eq. (8), stress that idle times on early machines are undesirable,
criterion, examining distinct combinations of neighborhoods.
for they delay the remaining jobs. Such stress is stronger if there
The present study examines six distinct combinations of the
are many unscheduled jobs (small value of k), but it becomes weak
two most common neighborhoods structures for the permuta-
when the number k of scheduled jobs increases.
tional flowshop scheduling using total flowtime criterion.
m
X
Although, in the problem s literature, the use of VNS is common,
ITikź wrkmaxfCði;r 1Þ Cðpk;rÞ;0gð7Þ
the results of the experiments performed on instances of the suite
rź2
created by Taillard (1993) suggested that, the most profitable com-
m
bination of job interchange and job insert local search, is distinct wrkź ð8Þ
rþkðm rÞ=n 2
from the combination of such local searches in literature. Consider-
ing that this new combination is a novel VNS for flowshop TFT, two The artificial flowtime (ATik) of a candidate job i after k jobs
questions arise: How does the new VNS perform when it is com- were schedule refers to the TFT value obtained after including
pared to state-of-the-art methods? Can current state-of-the-art unscheduled job i, plus the time of an artificial job placed at the
methods benefit from using the new combination? end of the job sequence. The processing time of the artificial job
To address those questions, the novel VNS, labeled VNS4 is com- on each machine is equal to the average processing time of all
pared with two other approaches, one named AGA and the other unscheduled jobs, excluding job i, on the corresponding machine.
named V4AGA. AGA is a genetic algorithm hybridized with VNS Both criteria, ITik and ATik are combined according to Eq. (9).
(Xu et al., 2011), which was claimed by its authors as superior algo-
fikźðn k 2ÞITikþATik ð9Þ
rithm when compared to other state-of-the-art methods. V4AGA is
a novel hybrid approach proposed here, that replaces the VNS used Also, Liu and Reeves (2001) propose a class of constructive heu-
in AGA by the one developed in this study. This experiment ristics named H(x), where x is an integer, 16x6n. Each variant
resulted in 34 novel solutions, 29 of then generated by VNS4. differs in the number of solutions it produces which is given by
The remaining of this paper is organized as follows. Section 2 x. While H(1) produces only one solution, H(2) produces two solu-
reports a brief review of literature. Section 3 describes the VNS ap- tions and so on. These methods create new solutions by changing
proaches as well as the describes the job insert and job interchange the initial job. Once the greedy criterion used in these heuristics
neighborhoods, the different ways to combine them and parame- is adaptive, different initial jobs produce different solutions. H(1)
ters tested in the experiments. Section 4 reports the experiments uses the job with the best value according to the greedy criterion
to determine which combination of neighborhoods performs best, as the initial job. H(2) creates two solutions using each of the
using a subset of instances from Taillard (1993). Section 5 de- two best evaluated jobs as the initial job. Thus, the first solution
scribes the computational experiments and results obtained by generated by H(2) is exactly the same as the one generated by
applying VNS4, AGA and V4AGA over all 120 instances of the data H(1). The second solution uses the second best job as the initial
set. Section 6 presents some conclusions. job. A special case is H(n/10) which uses the same principle, pro-
ducing n/10 solutions with the best n/10 initial jobs. The work of
2. Literature review Liu and Reeves (2001) also proposes the use of job interchange lo-
cal search to further improve the greedy solution obtained.
This section reviews some methods proposed for PFSP with TFT Framinan et al. (2002) define a queue based on the sum of the
criterion. Because the PFSP literature is vast this review is limited to processing times of each job. The job at the top of the queue is
W.E. Costa et al. / Expert Systems with Applications 39 (2012) 8149 8161 8151
inserted in the best possible position in the partial solution. Later Rajendran and Ziegler (2004) propose two ant colonies for the
the inserted job can be interchanged with any other job in the par- problem, they are named MMAS and PACO. They apply three iter-
tial solution in order to minimize the current value of the total ations of job at index local search once a solution has been fully
flowtime. Nagano and Moccellin (2007) create the queue in the constructed. MMAS and PACO differ on how the probabilities are
same way as in Framinan and Leisten (2003). The algorithm itera- assigned to unscheduled jobs in constructing the solution. MMAS
tively removes the first job in the queue and places it at the end of adopts uniform distribution for the best five options, whereas
the partial solution. Local search methods, job insert and inter- PACO assigns distinct probabilities to the five best options. The
change, are then applied over the partial sequence to minimize to- ant colony named SACO, Zhang et al. (2009b), starts using uniform
tal flowtime. probability distribution and evolves the probabilities of the phero-
The iterated local search proposed by Dong et al. (2009) adopts mones using Kullback Leibler divergence, (see Zhang et al., 2009b,
the job at index neighborhood created by Rajendran and Ziegler for further details).
(2004). This neighborhood consists of job insert moves; the order The PSO of Tasgetiren et al. (2007) use a real representation of
in which neighboring solutions are created depends on of the best solution and a rule is used to decode the real representation into
solution found so far. In Dong et al. (2009) each time the local a permutational representation. The particles move towards the
search procedure gets trapped in local optima, a perturbation is best global point and visit the best previous position. A variable
performed over the solution and local search resumed. In this case, neighborhood descent (VND) approach (using interchange and
the perturbation involves six randomly interchanging adjacent job insert neighborhoods) is defined and applied to the best solu-
jobs in the solution. tion in the population of each generation. The PSO of Liao, Tseng,
The hybrid genetic algorithm (HGA) of Zhang et al. (2009a) ap- and Luarn (2007) represents a solution using a discrete binary ma-
plies a data mining procedure over its population, creating a table trix B, where job i is assigned to position j if the entry bij = 1. The
that maps jobs to positions and counts the   good  solutions in a gi- velocity represents probabilities of changes within B. This PSO uses
ven association job/position. An assignment procedure creates a two local searches (interchange and job insert) but limits the
solution that will be used during crossover operations to preserve neighborhood size. Depending on the jobs positions, the search
building blocks in the new solutions. Solutions obtained after procedure considers only movements within a distance of 12 posi-
crossover are submitted to local searches (with job insert and tions (e.g. a job in the first position cannot be inserted in position
interchange neighborhoods). The HGLS (hybrid genetic with local 14 or above, nor can it be interchanged with another job placed in
search) of Tseng and Lin (2009) uses an orthogonal crossover oper- position 14 or above). The PSO of Jarboui et al. (2008) uses the per-
ator to recombine solutions. New solutions are submitted to two mutation representation and applies a simulated annealing meth-
local searches that use the job insert neighborhood. One local od to optimize solutions whose TFT is within 2% of the best TFT
search method is driven to minimize total flowtime, whereas the value obtained so far.
other looks for minimizing idle times. The latter is used to escape The VNS of Jarboui et al. (2009) uses two neighborhoods: job in-
local optima, and then minimization of TFT is resumed. The asyn- sert and interchange. First, the procedure starts using job inter-
chronous genetic algorithm, AGA (Xu et al., 2011), has a population change. Once this neighborhood fails to improve the current
of 40 solutions, one of them generated using H(n/m) heuristic, solution, it migrates to insert neighborhood and keeps using job
where n/m are created using the H criterion, followed by inter- insert moves until no further improvement can be reached, when
change local search, the other 39 are randomly generated. At each it reverts to using job interchange. If both neighborhoods fail to
iteration, the evolution process submits a solution to E-VNS (an further improve the solution further, the VNS makes a copy of
specific VNS approach), crossover and E-VNS a second time. If the best solution found, applies the random interchange move to
all individual in population have the same TFT value, the popula- it, and resumes optimization using job interchange neighborhood.
tion is restarted, by random generating 38 individuals, keeping The algorithm alternates between the two neighborhoods until
the best solution in the current pool of solutions and inserting both of them fail to improve the current solution.
the solution generated by H(n/m) again. The E-VNS uses job insert EDA-VNS (Jarboui et al., 2009) is a hybrid evolutionary ap-
local search and job interchange. When using job insert local proach. It uses a population of 10 solutions from which a subset
search, a job pi is randomly selected. E-VNS will attempt to re-in- Q of three solutions is selected. A probabilistic model is con-
sert pi on a different position j, also randomly selected. If such at- structed based on Q which is used to generate new solutions. If a
tempt improves current solution, the new solution is accepted new solution is better than the worst solution in the population,
and a new iteration of job insert occurs, selecting another random the new one replaces the worst solution. There is a probability of
job to be re-inserted. E-VNS executes 50 iterations of job insert. applying VNS over a solution. Such probability is related to objec-
After them, 50 iterations of job interchange occurs, where the tive function: the closer the value is to the best found total flow-
jobs to be interchanged are randomly selected, if any improve- time value the better are the chances that VNS will be applied
ment is achieved the solution is accepted and E-VNS resumes over a solution. The closer the value of a given solution is to the
job insert local search. The number of times job insert can be re- best flowtime value found so far, the better the chances of applying
sumed is limited by a value, randomly selected each time E-VNS VNS over a solution. The changes decrease exponentially for farther
is called, between 10 and 60, therefore is possible to E-VNS to ter- from the minimum of 1%.
minate not trapped in a local optima. AGA uses a two point cross- Tasgetiren et al. (2010) propose two approaches for TFT: a bee
over defined in Murata, Ishibuchi, and Tanaka (1996). The pair of colony optimization (name DABC) and a hybrid evolutionary ap-
parents used in crossover is randomly selected. The crossover proach (hDDE). There is a population of ten bees in DABC, each
chooses two random points, s and t, of a parent, the block of jobs one executing one of three activities. In the first activity, namely
within the index (pi, s6i6t) are copied to their respective posi- employed bee phase, the bee exploits its current solution by ran-
tions in a new solution, the remaining positions are filled follow- domly choosing between three methods: job insert, interchange
ing the job order on the second parent. Such crossover is applied and iterated greedy neighborhood, Ruiz and Stützle (2007). Once
twice for each pair of parents creating 2 new solutions. In each a neighborhood is chosen, it is further improved by using VND.
iteration, the crossover operator is applied repeatedly, until 40 In the second activity, namely onlooker phase, the bee migrates
new solutions are created, replacing the previous population. to another solution, randomly picking two solutions from the other
E-VNS is applied over the new solutions. AGA stops if a time limit bees and keeping the better one. Then, the bee creates a neighbor
of 0.4 n m seconds is reached. of the chosen solution, using the same schemes from employed
8152 W.E. Costa et al. / Expert Systems with Applications 39 (2012) 8149 8161
bee, and applies a VND composed of job insert, followed by inter- initialization methods are tested in Section 4. The remaining of this
change afterwards. The VND procedure keeps using interchange section is devoted to items 3 and 4, describing the neighborhoods
until no further improvement is possible then migrates to inter- and the tested VNS approaches.
change, until no further improvement is possible. The VND mi- Considering the particular case of permutational flowshop with
grates between insert and interchange until a local minimum, TFT criterion, two local search methods are repeatedly used in lit-
common to both neighborhoods is found. In the third activity, erature. They are job insert local search, also referred as shift local
namely scout, the bee generates two random solutions, keeps the search, and the job interchange local search, (Jarboui et al., 2009;
worse one and applies the iterated greedy move over it. The algo- Tasgetiren et al., 2010; Xu et al., 2011; Zhang et al., 2009a).
rithm hDDE also uses a population with 10 individuals. Its solution The neighborhood used in job insert is defined as follows, let
representation is discrete. Mutation is done by a random insert or PA ={pA1,pA2,. . .,pAn} be a solution for the PFSP. Solution
interchange move. The crossover operator takes a muted individual PB ={pB1,pB2,. . .,pBn} is in the job insert neighborhood of solution
and combines it with a non-mutated solution. For a given position PA if given two indices s and t, s < t one of the two possibilities is
pos, the crossover picks a random number c within [0,1]. If c is true, either pBs = pAt, and "c, s6c < t, pBc = pAc+1, or pBt = pAs, and
smaller than the constant CR = 0.9, the value from the mutated "d, s < d6t, pBd = pAd 1. Fig. 1 illustrates the job insert neighbor-
solution fills position pos, otherwise the value for pos comes from hood, PA = {1, 2, 7, 4, 5,6, 3}, s =2, t = 6 and PB = {1,7, 4, 5, 6, 2, 3}.
the non-mutated one. There is 1% probability of applying VNS (in- On Fig. 1, job 2 (in black) occupies the second position in the start-
sert and interchange moves only) over an individual. The iterated ing solution. A neighbor solution is generated moving job 2 to the
greedy procedure is applied only over the best individual of the sixth position and shifting the jobs between the third and sixth
population. Crossover and mutation rates are 90% and 20%, positions of the starting solution.
respectively. In the interchange neighborhood, two jobs exchange positions.
The results produced by AGA (Xu et al., 2011), DABC (Tasgetiren Solution PB ={pB1,pB2,. . .,pBn} is a neighbor of PA ={pA1,-
et al., 2010), hDDE (also in Tasgetiren et al., 2010), VNS, EDA-VNS pA2,. . .,pAn} if given two indices s and t, s  t, pAs = pBt, pAt = pBs
(Jarboui et al., 2009), HGA (Zhang et al., 2009a) and HGLS (Tseng and "c, c  s, t, pAc = pBc. Fig. 2 illustrates two neighbors,
& Lin, 2009) are used as references for the experiments presented PA = {1,2,7,4,5,6,3} and PB = {1,6,7,4,5,2,3}, where s = 2 and t =6.
here, once these methods present the best results over flowshop The Algorithms 1 6 describe how to implement local search
instances created by Taillard, as far as the authors knowledge con- methods based on the above described neighborhoods, Algorithms
cerns. These instances have been used as test set for flowshop TFT 7 12 refer to six VNS implementations combining both neighbor-
and are used here on the computational experiments to assess the hoods in distinct ways. The VNS of Algorithm 7 is the one used
proposed approach performance in comparison to the state-of-the- in Zhang et al. (2009a), VNS5 (Algorithm 12) combines the neigh-
art methods. borhoods as Tasgetiren et al. (2010) do. Algorithm 12 has the same
structure of the VNS used in work by Jarboui et al. (2009). The
other three VNS are novel approaches proposed and under exam
3. Variable Neighborhood Search  VNS in this paper.
Algorithm 1 implements the task of, given a job pi, creating all
VNS is a meta-heuristic created by Hansen and Mladenović possible neighbors by re-inserting pi in a different position. The
(1997) for the p-median problem. In a recent review (Hansen, procedure receives a solution P and the index of a position. Ini-
Mladenović, & Pérez, 2008), the creators define VNS as   . . . a meta- tially a temporary copy, named P0, of solution P is made in line
heuristic which systematically exploits the idea of neighborhood 1. The procedure continues by shifting the job pi to a different po-
change, both in descent to local minima and in escape from the val- sition j, (i  j), lines 2 to 11. If the new solution (P0) is better than
leys which contain them  . the original (P), then, P is updated and the procedure finishes,
Because of its simplicity and efficiency, VNS is often hybridized lines 5 to 7. Otherwise, the shift is reversed by the command In-
with other heuristics in order to find solutions of higher quality. sert(P0, j, i) (line 9). The procedure continues to loop until all n
VNS has few parameters, at the same time, it has a record of good positions, except position i, are examined.
results in many problems including flowshop. The approaches pre-
sented by Jarboui et al. (2009), VNS and EDA-VNS, are examples of
how VNS can be effective by itself or hybridized with an evolution-
ary approach.
Some decisions that have to be made in order to implement a
VNS algorithm are:
1. An initial solution.
2. A perturbation scheme, named Shake procedure, used to escape
local optima common to multiple neighborhoods;
Fig. 1. Example of a movement using job insert neighborhood. Job 2, in black, is
moved from the second position to the sixth, creating a neighbor solution. Jobs in
3. A set of local search neighborhoods;
between the second and sixth position, in gray, are shifted during the process.
4. A scheme to define when to change the neighborhood.
The first two items are simple to solve. Initial solution can be
generated randomly or with a greedy procedure. The work of Dong
et al. (2009) tested many greedy heuristics as sources for initial
solutions for a local search method, when compared with other
greedy approaches. They concluded that H heuristics proposed by
Liu and Reeves (2001) produced the best results among the tested
methods. Therefore, H heuristics are used to create initial solutions
in the methods described in Section 4. The second item, Shake, can
Fig. 2. Example of a movement using interchange neighborhood. Job 2, in black, is
be easily implemented using a number of random moves from a
moved from the second position to the sixth, creating a neighbor solution. Jobs in
iven neighborhood, as suggested by Hansen et al. (2008). Different between the second and sixth position, in gray, are shifted during the process.
W.E. Costa et al. / Expert Systems with Applications 39 (2012) 8149 8161 8153
Algorithm 1. Job-insert-pi(P, i) Algorithm 4. Reduced-Interchange(P)
1: P0 P 1: improve False
2: for j =1 to n do 2: P0 P
3: if i  j then 3: Current_Flow TFT
4: Insert(P0,i, j) 4: for i =1 to n 1 do
5: if TFP(P0) 6: P P0 6: if TFT(P) 7: return P 7: improve True
8: end if 8: end if
9: Insert(P0,j, i) 9: end for
10: end if 10: return improve
11: end for
12: return P
The complete local searches are depicted in Algorithms 5 and 6.
In Algorithm 5, named Job-Insert-LS(P, time_limit), the procedure
Reduced-JI(P) is continuously executed, as long it returns the true
Algorithm 2 creates neighbors using the interchange neigh- value and the running time has not exceeded the time limit. The
borhood. The procedure receives a solution P and the index of
procedure Job-Insert-LS(P, time_limit) will continuously explore
a position. With these two arguments it constructs neighboring
the insert neighborhood until, either no further improvement is
solutions, by interchanging job pi with job pj, j > i. Initially a
possible, or the time limit is reached. The Algorithm 6, Job-Inter-
temporary copy, named P0, of solution P is made in line 1.The
change-LS(P,time_; limit) procedure, explores the job interchange
loop, from line 2 to line 9, creates and exams the interchange
neighborhood until no further improvement is possible as well as
neighbors. In line 3, job pi changes its positions with job pj. If
limit for the execution time. In both procedures an initial solution
this change improves the original solution, P, then P is updated
is provided, as well the time limit constraint.
and the procedure returns, lines 4 to 7. Otherwise, the change is
Algorithm 5. Job-Insert-LS(P, time_limit)
reversed, line 8.
1: condition True
Algorithm 2. Interchange-pi(P, i) 2: while conditionand within time_limit do
3: condition Reduced-JI (P)
1: P0 P
4: end while
2: for j = i +1to n do
5: returnP
3: Interchange(P0, i, j)
4: if TFP(P0) 5: P P0
6: return P
Algorithm 6. Job-Interchange-LS(P, time_limit)
7: end if
1: condition True
8: Interchange(P0, j, i)
2: while condition and within time_limit do
9: end for
3: condition Reduced-Interchange(P)
10: return P
4: end while
5: return P
The Algorithms 3 and 4 are reduced local search methods. For
The VNS of Algorithm 7, named VNS1, explores both neighbor-
each job pi, they apply either Job-insert-pi(P, i) or the Inter-
hoods fully. First it explores job insert, once it reaches a local optima,
change-pi(P, i) procedure. They conclude after applying their
there is a neighborhood change to job interchange. VNS1 continues
respective neighborhoods over all positions. Algorithm 3, named
applying interchange moves until no further improvements can be
Reduced-JI(P), uses Job-insert-pi(P, i) procedure. If the Job-
found. At this point the procedure exams if the current solution is
insert-pi(P, i) procedure improves the current solution, it returns
the best one so far and updates the best solution if it is the case, line
a True value otherwise it returns False. Similarly, Algorithm 3,
6. The procedure then copies the best solution found during the
named Reduced-Interchange (P), uses Interchange-pi(P, i) proce-
search, and disturbs it with shake, introducing random modifica-
dure. Reduced-Interchange(P) will return True only if it improves
tions into P in order to escape local optima. After it, the procedure
the current solution, P.
restarts from job insert local search, in line 9. Otherwise the proce-
dure returns the best solution found (Best_Solution), line 10.
Algorithm 3. Reduced-JI (P)
Algorithm 7. VNS1(P)
1: improve False
2: P0 P
1: P Initial_Sol
3: Current_Flow TFT
2: Best_Solution P
4: for i =1 ton do
3: repeat
5: Job-insert-pi(P, i)
4: Job-Insert-LS (P, time_limit)
6: if TFT(P) 5: Job-Interchange-LS (P, time_limit)
7: improve True
6: Update_Best_Solution(P)
8: end if
7: P Best_Solution
9: end for
8: Shake(P)
10: return improve
9: until time limit is reached
10: return Best_Solution
8154 W.E. Costa et al. / Expert Systems with Applications 39 (2012) 8149 8161
The VNS2, Algorithm 8, is very similar to VNS1, the difference
Algorithm 10. VNS4(P, time_limit,Initial_Sol)
lies on the order neighborhoods are examined. VNS2 firstly ex-
1: P Initial_Sol
plores interchange neighborhoods and later migrates to job insert
2: Best_Solution P
(lines 4 and 5).
3: repeat
4: condition True
Algorithm 8. VNS2(P)
5: while condition and within time_limit do
1: P Initial_Sol
6: Job-Interchange-LS(P, time_limit)
2: Best_Solution P
7: condition Reduced-JI(P)
3: repeat
8: end while
4: Job-Interchange-LS(P, time_limit)
9: Update_Best_Solution(P)
5: Job-Insert-LS(P, time_limit)
10: P Best_Solution
6: Update_Best_Solution(P)
11: Shake(P)
7: P Best_Solution
12: until time limit is reached
8: Shake(P)
13: return Best_Solution
9: until time_limit is reached
10: return Best_Solution
VNS5, Algorithm 11, starts applying job insert until no further
improvement is possible, then it starts job interchange. It continues
using job interchange until a local minimum is found, in this case
The main difference between Algorithms 9 and 10, to VNS1 and
the procedure, different from VNS1, resumes job insert local search.
VNS2 heuristics, is the use of reduced local searches procedures,
The Shake procedure is called only if a local minimum common to
Algorithms 3 and 4. The third VNS approach, Algorithm 9, starts
both neighborhoods is found. In terms of pseudo-code it was ex-
fully exploring job insert, when it fails to improve the current solu-
pressed using an inner loop, line 6, two Boolean variables (named
tion, it calls Reduced-Interchange (P) which is equivalent to one
condition1 and condition2), and four if tests (lines 8, 12, 16, 20).
iteration of interchange local search. If this single iteration finds
The variable textitcondition1 in tested in line 8, only if the variable
an improvement over current solution P, the VNS resumes job in-
has a true value job insert local search is executed. The variable con-
sert local search. In terms of pseudo-code, this is expressed from
dition2 is used similarly to variable condition1, but related to job
lines 5 to 8. The repeat loop starting on line 3 is equivalent to
interchange local search. Initially both variables, condition1 and
the repeat loops of Algorithms 7 and 8. Within this loop, there is
condition2, are set to True, lines 4 and 5. The while loop of line 6
a Boolean variable named condition, initially set to True so an inner
is executed only if at least one of the two variable stores a true value
while loop can iterate, lines 4 and 5. Job insert local search is ap-
and there is time to continue the search. Once the local search fin-
plied, line 6, when it stops on a local optima, an iteration of inter-
ishes, condition1 receives false. It will continue to be false until
change is applied, line 7. If this single iteration improves the
either job interchange improves the current solution (then the if
quality of P, Reduced-Interchange (P) will return true, this will lead
statement of line 20 will be satisfied) or if both procedures no long-
the algorithm back to job insert local search, for variable condition
er improve the current solution, exiting the inner while to the re-
will be true. If the interchange iteration fails, then, condition will be
peat loop where condition1 and condition2 receive the true value.
false, terminating while loop. In this case VNS3 exams if a new best
The use of condition2 follows the same logic. When condition2 holds
solution was found, line 9. P receives a copy of the current best
a true value, the statements within the if statement of line 16 exe-
solution, line 10. The shake procedure acts over P, line 11, and if
cute job interchange local search and set condition2 as false. The
the time limit was not reached, the local search is resumed, other-
variable condition2 is set to True only if job insert improves the cur-
wise the procedure terminates returning the best solution found so
rent solution (line 12), or in the beginning of a new iteration of the
far, line 13.
main loop, lines 4 and 5. When the procedure exits the inner while
loop,if a new best solution has arisen, it is updated in line 24, the
Algorithm 9. VNS3(P, time_limit)
current solution, P, is set to the best solution found and is submit-
ted to Shake procedure (line 26).
1: P Initial_Sol
The sixth VNS, VNS6 is depicted in Algorithm 12. The only dif-
2: Best_Solution P
ference between VNS5 and VNS6 is that the former starts using
3: repeat
job insert local search, whereas the latter starts using job inter-
4: condition True
change local search, line 9. The remaining of Algorithm 12 is sim-
5: while condition and within time_limit do
ilar to Algorithm 11. This concludes the description of VNS
6: Job-Insert-LS(P, time_limit)
approaches to be examined on Section 4.
7: condition Reduced-Interchange(P)
8: end while
Algorithm 11. VNS5(P, time_limit, Initial_Sol)
9: Update_Best_Solution(P)
10: P Best_Solution
1: P Initial_Sol
11: Shake(P)
2: Best_Solution P
12: until time limit is reached
3: repeat
13: return Best_Solution
4: condition1 True
5: condition2 True
6: while (condition1 or condition2) and within time_limit do
7: current_flowtime TFT(P)
VNS4, Algorithm 10, is analogous to VNS3. Algorithm 10 starts
8: if condition1 then
exploring interchange until no further improvement is possible,
9: Job-Insert-LS(P, time_limit)
line 6. Then, Reduced-JI(P) is used, a single iteration of job insert
10: condition1 False
neighborhood. If this iteration improves the current solution, the
algorithm resumes the interchange local search.
W.E. Costa et al. / Expert Systems with Applications 39 (2012) 8149 8161 8155
instances (Taillard, 1993). The number of jobs is in the set
11: end if
{20, 50, 100, 200, 500} and the number of machines in {5, 10, 20}.
12: if TFT(P) The subset utilized in the experiments reported in this section com-
13: condition2 True
prises the five first test cases of each group of 50 and 100 jobs of Tail-
14: end if
lard s dataset, making a total of 30 instances. Twenty independent
15: current_flowtime TFT(P)
executions of each algorithmic version are performed for each in-
16: if condition2 then
stance; therefore there will be 600 (six hundred) data points col-
17: Job-Interchange-LS(P, time_limit)
lected for each version under test. The tests were executed on a
18: condition2 False
Core 2  Quad 2.4 GHz (Q6600), 1 GB RAM.
19: end if
The methodology transforms the results obtained during trials
20: if TFT(P) into relative percentage deviation (RPD) using Eq. (10), where
21: condition1 True
BestSolution refers to the lowest TFT found in any experiment on
22: end if
the same instance. Because RPD is a dimensionless value resultant
23: end while 24: Update_Best_Solution(P)
from a normalization procedure, the RPDs from different instances
25: P Best_Solution
are comparable. The Shapiro Wilk test (Conover, 1980) indicates
26: Shake(P)
that many options tested have a non-normal distribution (p-value
27: until time limit is reached
smaller than 10 3), therefore Kruskal Wallis test (Conover, 1980),
28: return Best_Solution
a non-parametric counterpart of ANOVA, is applied over results. If
the Kruskall Wallis test applied over data points out evidence that
some options are different from the others (i.e. p-value smaller
than 0.05), the parameter with the smallest median RPD value is
Algorithm 12. VNS6(P, time_limit, Initial_Sol)
considered the best one among the tested options. The median is
1: P Initial_Sol
used instead of using arithmetic mean of RPDs, as the median is
2: Best_Solution P
a non-parametric indicator, whereas arithmetic mean is an indica-
3: repeat
tor for normal distributions.
4: condition1 True
5: condition2 True
HeuristicSolution BestSolution
RPDð%Þź100 ð10Þ
6: while (condition1or condition2) and within time_limit do
BestSolution
7: current_flowtime TFT(P)
Initially the VNS parameters are defined as follows:
8: if condition1 then
9: Job-Interchange-LS (P, time_limit)
1. Initial solution randomly generated;
10: condition1 False
2. The Shake procedure is defined as two random job interchange
11: end if
moves;
12: if TFT(P) 3. Time limit set to 0.4 n m seconds.
13: condition2 True
14: end if
15: current_flowtime TFT(P)
4.1. Neighborhood order
16: if condition2 then
17: Job-Insert-LS(P, time_limit)
The first decision to be made concerns is which VNS procedure
18: condition2 False
presents the best behavior. The best one is adopted in the experi-
19: end if
ments. The Kruskal Wallis test suggests differences among differ-
20: if TFT(P) ent procedures tested, p-value smaller than 10 3. Table 1
21: condition1 True
summarizes the results, reporting the RPD median value of each
22: end if
option. As stated earlier, the median is the criterion used to define
23: end while
which parameter value is the best one, in this case it means that
24: Update_Best_Solution(P)
VNS4 was considered the best option among the tested VNS proce-
25: P Best_Solution
dures (indicated in bold face in Table 1).
26: Shake(P)
27: until time limit is reached
4.2. Shake  perturbation strength
28: return Best_Solution
The next parameter to be examined is the Shake procedure. The
VNS of Jarboui et al. (2009) uses one interchange move as Shake.
They do not report any experiment to calibrate this parameter.
4. Calibration experiments The work of Dong et al. (2009) tested multiple numbers of inter-
change moves, and their results indicated that four to seven inter-
This section reports experiments done to calibrate the following change moves were appropriate when using only job insert local
parameters of the proposed algorithms: neighborhood order and search.
change strategy, Shake mechanism and initial solution method. The
six VNS procedures, described in Section 3, are tested in Section 4.1.
Table 1
The Shake procedure is implemented using a number k of random
RPD s median for different VNS approaches.
job insert moves. In Section 4.2 up to 20 different values of k are tested.
VNS approaches
Section 4.3 reports the results of the comparison between six different
methods utilized to create the initial solution, one random and five oth- Technique VNS1 VNS2 VNS3
Median  RPD(%) 0.671894 0.663554 0.503719
ers using the criterion of Liu and Reeves (2001).
Technique VNS4 VNS5 VNS6
A subset of Taillard s instances is used in the experimentation.
Median  RPD(%) 0.461363 0.685505 0.493171
The complete dataset contains 120 randomly generated
8156 W.E. Costa et al. / Expert Systems with Applications 39 (2012) 8149 8161
Table 2
equals to 0.21). Under these circumstances, the decision of what
RPD s median for different number of job insert moves, used as Shake procedure.
method to choose does not depend on the median of RPDs.
Once a decision cannot be made based on the median, we
Number of insert moves k
decided to choose the heuristic H(n/m) once it is used in AGA
k =1 k =2 k =3 k =4 k =5
and this algorithm is compared to VNS4.
RPD(%) 0.531533 0.547817 0.532402 0.522590 0.550798
k =6 k =7 k =8 k =9 k =10
This concludes the calibration experiments. The final version of
RPD(%) 0.535054 0.538884 0.561393 0.570443 0.534179
VNS uses the following parameters.
k =11 k =12 k =13 k =14 k =15
RPD(%) 0.524655 0.545517 0.543708 0.469627 0.472480
1. Initialization method: H(n/m);
k =16 k =17 k =18 k =19 k =20
RPD(%) 0.481483 0.477755 0.478360 0.532989 0.532077 2. Shake procedure: 14 random job insert moves;
3. Local search methods: Job Interchange and Insert
4. Neighborhood change scheme: VNS4 procedure;
This experiment deals with the number of job insert moves, k,
The next section reports the results obtained in tests performed
used in Shake. The experiment varies k from one up to twenty,
with VNS4 applied to 120 Taillard s benchmark instances. Those
16k620. Again Kruskal Wallis test points out differences when
results are compared to the ones obtained by the best approaches
the value k varies (p-value smaller than 10 3). The medians are
from literature, as far as the authors knowledge concerns, and
summarized in Table 2. They indicate that Shake procedures com-
with state-of-art method AGA presented by Xu et al. (2011).
posed of less than 14 moves or greater than 18 moves are not
among the best options. Although, the results with 146k618
produce very similar results, the value k = 14 is selected, as it is
5. Computational experiments
the one with the lowest RPD median.
The proposed VNS algorithm was implemented in C++ on a Core
4.3. Initialization method 2  Quad 2.4 GHz (Q6600), 1 GB RAM, using Gnu C++ compiler. The
experiments were performed on all 120 instances from the Tail-
This subsection deals with different initialization methods. The lard s benchmark (Taillard, 1993). Thirty independent executions
tests were restricted to heuristics using the criterion of Liu and Re- were performed for each instance. The stopping criterion adopted
eves (2001). The heuristics tested are H(1), H(2), H(n/10), H(n/m), in the experimentation was a maximum processing time of
and H(n). Random generated solutions are also testes as initial 0.4 n m seconds, for it is the same used in recent works of
solution. Heuristic H(n/m) is described in Xu et al. (2011). Jarboui et al. (2009), Tasgetiren et al. (2010) and Xu et al. (2011).
The analysis of the results, using Kruskal Wallis, did not detect The results achieved by VNS4 are compared with the one
a significant difference between initialization methods (p-value obtained by AGA (Xu et al., 2011), and V4AGA. There are two
Table 3
Summaries of results for instances with 50 jobs. Minimum value (Min), average (Avg), maximum (Max) and standard deviation (S.D.) included.
Instance Best Algorithm VNS4 AGA V4AGA
Min Average Max S.D. Min Average Max S.D. Min Average Max S.D.
50 05 1 64803 HGLS 64803 64917.17 65083 68.20 64817 64891.40 64982 44.58 64803 64857.47 64922 27.27
50 05 2 68051 hDDE 68083 68203.10 68396 84.77 68095 68174.50 68262 43.89 68059 68131.50 68215 36.62
50 05 3 63162 hDDE 63195 63384.40 63563 97.13 63241 63420.07 63627 101.91 63195 63335.47 63540 98.53
50 05 4 68241 HGLS 68241 68535.43 68730 104.56 68241 68441.37 68627 97.98 68241 68408.17 68566 83.68
50 05 5 69360 hDDE 69392 69561.20 69699 74.99 69466 69554.27 69639 48.28 69414 69517.47 69632 47.36
50 05 6 66841 hDDE 66865 67056.77 67263 85.08 66961 67020.67 67091 36.01 66841 66958.27 67100 70.34
50 05 7 66253 AGA 66273 66427.77 66635 91.98 66271 66356.37 66445 55.77 66261 66311.27 66415 45.74
50 05 8 64365 hDDE 64381 64591.50 64845 91.89 64359w 64472.13 64663 71.64 64359w 64426.40 64536 51.58
50 05 9 62981 HGLS 63062 63145.63 63224 43.02 62981 63104.43 63202 53.63 62981 63086.40 63172 54.08
50 05 10 68811 HGLS 68884 69137.87 69394 116.76 68929 69097.27 69267 90.01 68951 69072.37 69174 62.55
50 10 1 87143 hDDE 88100 88215.20 88313 83.87 87225 87683.20 87976 172.24 87252 87584.43 87779 119.14
50 10 2 82820 HGLS 83042 83270.27 83681 134.98 83059 83249.00 83631 136.11 82954 83239.27 83523 182.55
50 10 3 79987 HGLS 80069 80328.17 80657 143.39 80092 80363.73 80570 104.07 80080 80211.80 80432 88.57
50 10 4 86466 HGLS 86600 86915.70 87181 147.52 86534 86883.10 87117 133.85 86579 86828.60 87028 101.90
50 10 5 86391 HGLS 86655 86861.60 87183 142.23 86623 86864.17 87157 145.89 86579 86770.13 86943 121.82
50 10 6 86682 HGLS 86840 87027.40 87412 137.64 86740 86970.60 87375 133.34 86643w 86831.20 87156 129.36
50 10 7 88811 HGLS 89020 89409.67 89809 194.72 88778w 89293.90 89629 213.78 89009 89260.57 89468 140.36
50 10 8 86839 HGLS 86848 87138.33 87503 172.76 86926 87171.00 87658 148.89 86940 87199.73 87481 135.38
50 10 9 85548 HGLS 85555 86015.67 86355 181.96 85659 86008.40 86214 131.82 85679 86018.03 86276 154.17
50 10 10 87998 DABC 88214 88529.40 89020 208.17 87998 88388.53 88817 199.79 88169 88419.67 88715 135.63
50 20 1 125831 VNS 125852 126401.00 127008 347.63 125831 126379.83 126796 290.90 125831 126169.67 126697 222.01
50 20 2 119247 EDA-VNS 119270 119637.80 120253 256.40 119274 119538.60 120060 189.66 119247 119438.57 119681 121.76
50 20 3 116459 HGLS 116792 117177.93 117766 242.84 116645 117070.77 117526 207.20 116536 116959.63 117289 175.41
50 20 4 120766 HGLS 120972 121506.13 122081 252.66 120766 121193.93 121739 197.52 120770 120986.00 121288 118.56
50 20 5 118405 AGA 118636 119090.23 119575 208.72 118460 118850.60 119204 204.86 118391w 118718.57 119104 174.95
50 20 6 120703 hDDE 120792 121283.33 121634 203.47 120791 121167.70 121637 195.25 120758 121028.03 121500 177.51
50 20 7 123018 HGLS 123237 123834.53 124542 361.20 123058 123648.00 124062 211.61 123068 123406.27 123801 166.22
50 20 8 122520 HGLS 122708 123245.87 123772 267.82 122703 123099.73 123504 236.94 122532 122949.00 123350 187.54
50 20 9 121872 HGLS 121872 122450.57 123170 259.21 122073 122348.37 122853 189.58 121872 122220.20 122610 202.43
50 20 10 124079 hDDE 124182 124712.00 125463 278.86 124361 124720.70 125116 199.90 124225 124552.73 124912 159.74
Table 4
Summaries of results for instances with 100 jobs. Minimum value (Min), average (Avg), maximum (Max) and standard deviation (S.D.) included.
Instance Best Algorithm VNS4 AGA V4AGA
Min Average Max S.D. Min Average Max S.D. Min Average Max S.D.
100 05 1 253926 AGA 254271 254706.53 255098 208.58 254540 255160.57 256202 385.33 255153 255572.20 255932 227.49
100 05 2 242886 AGA 243170 243739.10 244155 263.09 243452 244344.97 244970 386.67 244106 244796.97 245164 247.81
100 05 3 238280 AGA 238452 238802.57 239161 164.77 239223 239498.87 239982 191.65 239341 239777.87 240105 205.38
100 05 4 228169 AGA 228494 228845.23 229248 224.78 228321 228900.80 229323 272.37 228995 229551.30 229917 210.57
100 05 5 240810 AGA 241008 241557.30 242156 290.44 241261 241879.40 242407 289.48 242097 242393.73 242663 156.36
100 05 6 232876 AGA 233277 233771.77 234203 256.52 233655 234287.63 234832 313.86 234389 234793.77 235099 201.41
100 05 7 240918 hDDE 240874w 241449.47 241873 210.38 241402 241944.13 242556 319.73 241807 242120.83 242570 170.58
100 05 8 231716 hDDE 231782 232267.30 232962 268.89 232224 232850.90 233517 304.65 232578 233157.57 233449 220.94
100 05 9 248679 AGA 248652w 249283.93 249885 278.50 249455 250167.23 251145 429.17 250032 250386.80 250814 209.20
100 05 10 243518 AGA 243822 244396.67 245120 305.24 243933 244493.73 244963 290.31 244386 244890.00 245224 223.24
100 10 1 300201 hDDE 299999w 301055.93 302238 581.99 301032 302020.80 302941 563.27 302014 302761.10 303342 317.73
100 10 2 275298 AGA 275989 276894.57 278107 519.09 276270 277873.57 279732 778.99 277664 278560.20 279296 419.59
100 10 3 288707 AGA 289505 290715.23 292016 675.35 290021 291220.03 292411 630.67 290687 291935.37 292652 439.06
100 10 4 302635 AGA 303502 305109.30 306632 882.36 303583 305185.20 306365 786.02 304301 305459.60 306206 416.54
100 10 5 285643 AGA 285692 286403.43 286992 289.53 286184 287938.87 288780 660.70 288115 288620.47 289050 234.09
100 10 6 271475 AGA 271822 272750.17 273594 398.40 272664 273816.37 274845 543.08 273294 274349.37 274973 375.09
100 10 7 280921 hDDE 281312 282428.20 283607 594.47 281496 282708.73 283968 669.32 282082 283432.13 284233 445.00
100 10 8 292471 AGA 292636 294095.27 295093 596.41 292883 294923.17 296263 766.20 294566 295386.53 295963 410.33
100 10 9 303742 hDDE 303594w 305259.17 307273 900.34 304500 305558.27 306757 520.74 305489 306146.80 306890 419.66
100 10 10 293147 hDDE 293053w 293624.73 294517 389.47 293131 294539.33 295471 526.38 295392 296268.03 297161 395.12
100 20 1 368590 AGA 368262w 370046.03 371804 906.79 368598 371452.33 373315 959.83 372010 372622.20 373363 383.44
100 20 2 374086 AGA 374723 376116.30 377507 618.01 373335w 377392.30 378755 997.34 376929 378711.57 379632 615.16
100 20 3 372057 hDDE 372837 374393.87 376397 859.68 373847 375444.73 376829 726.87 374684 376034.27 376932 520.16
100 20 4 374205 DABC 375507 377226.90 378564 847.29 376192 377947.50 380017 787.75 377819 379621.23 380950 618.38
100 20 5 370646 hDDE 371103 372902.90 374756 894.64 371960 374128.13 376779 1050.33 374044 374984.07 376037 461.24
100 20 6 373689 DABC 375059 376932.07 379932 1060.72 375410 377131.97 378480 729.37 376335 378033.10 379355 673.44
100 20 7 375188 DABC 375530 377536.27 379501 950.55 376622 378723.20 380847 1084.92 378661 379948.67 380980 586.44
100 20 8 386803 hDDE 386147w 388428.87 390065 998.69 388188 389809.80 391039 780.63 389099 390638.33 391393 489.97
100 20 9 377113 DABC 376635w 378624.40 379864 818.57 377506 379892.90 381867 1000.86 379735 380934.53 381890 602.27
100 20 10 380725 DABC 381850 383113.17 384542 727.59 381640 383924.33 385650 932.78 383704 385025.60 386109 526.09
W.E. Costa et al. / Expert Systems with Applications 39 (2012) 8149 8161
8157
Table 5
Summaries of results for instances with 200 or more jobs. Minimum value (Min), average (Avg), maximum (Max) and standard deviation (S.D.) included.
Instance Best Algorithm VNS4 AGA V4AGA
Min Average Max S.D. Min Average Max S.D. Min Average Max S.D.
200 10 1 1049830 AGA 1054656 1057543.60 1059668 1183.72 1055059 1057977.37 1062645 1652.53 1056691 1058526.27 1060164 878.67
200 10 2 1036427 AGA 1041239 1043194.37 1044955 1029.91 1046307 1049223.63 1051620 1306.58 1047212 1050751.73 1052940 1417.53
200 10 3 1048993 AGA 1048561w 1051289.33 1052709 955.17 1055058 1058518.80 1061652 1893.19 1055560 1059119.90 1061595 1310.35
200 10 4 1033110 AGA 1035709 1039703.17 1042419 1816.05 1038221 1043010.20 1045352 1629.51 1041728 1044950.77 1047220 1388.64
200 10 5 1038288 AGA 1037392w 1042944.30 1046322 1401.31 1044582 1048216.20 1050798 1666.36 1045074 1047949.60 1051097 1326.77
200 10 6 1011864 AGA 1010243w 1015037.87 1018330 2200.57 1012577 1014715.53 1017524 1352.38 1016286 1019580.43 1022676 1307.90
200 10 7 1059727 AGA 1058211w 1062100.80 1064875 1469.44 1061660 1065440.47 1069826 2174.52 1066134 1068513.00 1070790 1375.17
200 10 8 1048299 AGA 1046284w 1048404.33 1049503 693.26 1053464 1055184.67 1055244 324.98 1054335 1055199.23 1055244 171.94
200 10 9 1026137 AGA 1026701 1029059.87 1031123 1114.47 1032283 1038196.93 1041745 2330.34 1032086 1037533.10 1040065 1532.57
200 10 10 1035409 AGA 1035763 1038808.60 1041619 1710.37 1040107 1044485.00 1048501 2062.30 1042530 1045444.87 1047191 1255.55
200 20 1 1234223 AGA 1231266w 1234531.57 1237772 1642.25 1239042 1246325.00 1255010 3461.88 1241475 1244061.77 1247595 1374.39
200 20 2 1253715 AGA 1249948w 1255873.40 1262029 2827.70 1258086 1262431.17 1268098 2601.77 1254848 1258739.20 1262450 1632.53
200 20 3 1273570 AGA 1272659w 1278632.23 1283811 2528.13 1282691 1286911.50 1291336 2157.02 1279039 1281892.13 1284783 1423.27
200 20 4 1243223 AGA 1245410 1252900.37 1256618 2725.10 1255058 1258748.13 1263589 2158.10 1255161 1258850.37 1261803 1877.63
200 20 5 1231608 AGA 1229946w 1232333.27 1235308 1675.72 1236728 1243420.93 1248240 2494.61 1235025 1240992.80 1245901 2279.10
200 20 6 1231235 AGA 1230942w 1234829.03 1238945 2087.75 1241208 1245126.10 1250903 2513.39 1238380 1242331.67 1246591 1522.84
200 20 7 1248109 AGA 1247268w 1249825.53 1252136 1461.53 1256251 1260687.60 1264656 2116.23 1254281 1258977.77 1262241 1766.54
200 20 8 1248110 AGA 1249994 1256256.23 1261005 2983.53 1260078 1264553.40 1270582 2261.72 1256926 1259611.47 1262518 1260.70
200 20 9 1237168 AGA 1233099w 1238289.37 1241732 2259.30 1242994 1248213.60 1254083 2225.21 1243613 1247900.00 1251473 1977.71
200 20 10 1250596 AGA 1255584 1259114.37 1265328 2071.26 1266536 1269592.03 1273434 1789.75 1261324 1264965.87 1268892 1914.18
500 20 1 6718965 AGA 6707778w 6717094.47 6720035 2988.98 6730350 6741399.40 6752384 6649.11 6752936 6752936.00 6752936 0.00
500 20 2 6841013 AGA 6827845w 6841021.37 6845619 4136.83 6862064 6872985.77 6884756 5857.50 6855359 6875904.53 6895356 11100.42
500 20 3 6743171 AGA 6730079w 6736537.90 6738500 2072.85 6807611 6818359.70 6832014 6202.82 6787804 6809057.87 6839387 12659.43
500 20 4 6802933 AGA 6748315w 6752778.73 6754596 1665.27 6810530 6831271.43 6842594 6912.98 6812323 6847534.43 6870660 13778.23
500 20 5 6737370 AGA 6708168w 6713007.40 6714732 1641.71 6781620 6793516.23 6806130 6253.00 6781815 6806261.73 6836943 12816.03
500 20 6 6738575 HGA 6734810w 6745499.40 6749510 3091.21 6777530 6777530.00 6777530 0.00 6777530 6777530.00 6777530 0.00
500 20 7 6691468 AGA 6701864 6716096.40 6721695 5158.40 6773789 6778006.57 6778152 796.57 6756862 6772691.77 6778152 6883.54
500 20 8 6790270 AGA 6777529w 6781793.80 6784628 2363.96 6799366 6811204.33 6834007 7852.54 6808222 6838811.10 6848602 10851.18
500 20 9 6715549 AGA 6714308w 6726322.23 6729076 3003.76 6766456 6780304.20 6790198 6451.00 6749807 6769745.17 6787560 10319.70
500 20 10 6760926 AGA 6755838w 6758477.83 6759219 992.84 6821787 6836192.50 6845923 6492.97 6777091 6825545.30 6842772 15268.49
8158
W.E. Costa et al. / Expert Systems with Applications 39 (2012) 8149 8161
W.E. Costa et al. / Expert Systems with Applications 39 (2012) 8149 8161 8159
Table 6
differences between AGA and V4AGA. First, the fact the latter uses
p-Values from Kruskal Wallis test over instances with 50 jobs and the median values
VNS4 instead of E-VNS. VNS4 is applied only to solutions created
obtained by each method.
during crossover, in this case no Shake procedure is used. Second,
Instance p-Value In favor of VNS4 AGA V4AGA
AGA uses E-VNS which is bounded in number of iterations,
whereas VNS4 ends by finding a local minimum common to both
50 05 1 p <10 3 V4AGA 64922.00 64885.50 64844.50
neighborhoods, therefore VNS4 is likely to consume more process- 50 05 2 p <10 3 V4AGA 68205.50 68167.00 68128.00
50 05 3 0.011 V4AGA 63393.50 63417.00 63340.50
ing time than E-VNS, and might harm the performance of V4AGA
50 05 4 p <10 3 V4AGA 68548.00 68468.50 68428.00
on large instances. The authors of Xu et al. (2011) kindly provided
50 05 5 0.008 V4AGA 69570.50 69563.00 69521.00
the source code of their method.
50 05 6 p <10 3 V4AGA 67053.00 67019.00 66959.00
From the 30 instances with n = 20, algorithm VNS4 achieved the 50 05 7 p <10 3 V4AGA 66440.00 66370.00 66291.00
50 05 8 p <10 3 V4AGA 64589.00 64458.00 64407.00
best known solution of 20 instances with convergence rate 100%.
50 05 9 p <10 3 V4AGA 63149.00 63104.50 63072.50
AGA heuristic achieved the best known solution of 29 instances
50 05 10 0.062  69118.00 69094.00 69087.50
on all trials. The exception was on instance identifier 4 with
n = 20 and m = 10, with 95% of convergence. V4AGA converged to
50 10 1 p <10 3 V4AGA 88225.00 87702.00 87589.00
50 10 2 0.860  83241.50 83231.00 83262.00
the optimum on 100% of its independent executions.
50 10 3 p <10 3 V4AGA 80299.00 80364.00 80223.50
A summary of the results for the remaining instances (90 in-
50 10 4 0.043 V4AGA 86907.50 86913.00 86849.00
stances with n P 50) are summarized on Tables 3 5. Each line of
50 10 5 0.033 V4AGA 86858.50 86853.00 86774.00
these tables shows the name of the instance (Instance), which is
50 10 6 p <10 3 V4AGA 87002.50 86952.00 86829.50
denoted by n m and an identifying number, the best solution re- 50 10 7 0.009 V4AGA 89428.00 89338.00 89261.00
50 10 8 0.171  87095.00 87164.00 87223.00
ported in literature (Best), the algorithm that produced the best
50 10 9 0.883  86042.50 86031.50 86049.00
solution (Algorithm), the minimum (Min), average (Ave), maxi-
50 10 10 0.037 AGA 88494.00 88384.00 88421.00
mum (Max) and standard deviation (S.D.) recorded after 30 execu-
tions by each tested method. Novel solutions are indicated by a star
50 20 1 0.006 V4AGA 126449.50 126422.00 126116.50
symbol (w) next to the value. The best average and minimum val- 50 20 2 0.007 V4AGA 119614.00 119524.50 119399.50
50 20 3 0.002 V4AGA 117150.50 117061.00 116950.00
ues found during experimentation are indicated in bold face. For
50 20 4 p <10 3 V4AGA 121511.00 121199.00 120973.50
the 30 instances with n = 50 jobs (Table 3), the approach V4AGA
50 20 5 p <10 3 V4AGA 119036.50 118909.00 118742.50
achieves the highest number of minimum solutions, 18 in total,
50 20 6 p <10 3 V4AGA 121287.00 121170.00 121060.50
three of them novel solutions. V4AGA has the best average on 27 50 20 7 p <10 3 V4AGA 123818.50 123637.00 123420.00
50 20 8 p <10 3 V4AGA 123283.50 123139.50 122964.50
cases. AGA achieves 10 minimum solutions, two of them are novel
50 20 9 p <10 3 V4AGA 122455.50 122287.50 122262.00
solutions (one of them is a novel solution that both AGA and
50 20 10 0.004 V4AGA 124699.00 124700.50 124558.00
V4AGA found), and achieves the best average in two cases. VNS4
obtains the smallest minima in 10 cases one of them tied with both
AGA and V4AGA. VNS4 has the best average in one case. In the set
of instances with n = 100 jobs (Table 4), VNS4 has the highest num-
ber of minimum solutions, 27 in total, eight of them novel ones.
Table 7
VNS4 exhibited the best average value for all 30 instances. AGA
p-Values from Kruskal Wallis test over instances with 100 jobs and the median
achieves the minimum solution in three cases, one of them is a no-
values obtained by each method.
vel solution. A similar trend was observed on instances with
Instance p-Value In favor of VNS AGA V4AGA
n P 200 (Table 5), where VNS4 has the smallest minimum solution
in all 30 cases, 21 of them novel solutions, and has the best average 100 05 1 p <10 3 VNS4 254682.00 255180.50 255578.00
100 05 2 p <10 3 VNS4 243769.50 244404.50 244816.00
in 29 cases.
100 05 3 p <10 3 VNS4 238814.50 239493.50 239815.50
The results obtained by the three tested approaches are also
100 05 4 p <10 3 VNS4 228853.00 228914.50 229583.00
examined using the Kruskal Wallis test. However it is used slightly
100 05 5 p <10 3 VNS4 241600.00 241862.50 242391.00
different from the way it was used in Section 4. Instead of trans-
100 05 6 p <10 3 VNS4 233748.50 234293.50 234820.50
forming all the results into RPD values, and then applying Krus- 100 05 7 p <10 3 VNS4 241445.50 241974.50 242070.00
100 05 8 p <10 3 VNS4 232229.00 232873.00 233226.50
kal Wallis test over all results, the test is applied for each
100 05 9 p <10 3 VNS4 249365.00 250185.50 250377.50
instance with n P 50 jobs, and if, for a given instance, the test indi-
100 05 10 p <10 3 VNS4 244398.00 244521.00 244937.00
cates evidence of differences between the compared methods
(p-value60.05), the median value of each method is used to dis- 100 10 1 p <10 3 VNS4 301098.00 302107.50 302741.00
100 10 2 p <10 3 VNS4 276793.50 277805.00 278626.50
cern the performances of the tested approaches. Because here the
100 10 3 p <10 3 VNS4 290654.00 291242.50 292010.50
interest is to rank the methods, therefore the analysis of statistical
100 10 4 0.184  304804.50 305163.50 305498.50
results includes comments regarding how many time each method
100 10 5 p <10 3 VNS4 286335.50 288263.00 288645.50
has the best median and the second best median. Considering the
100 10 6 p <10 3 VNS4 272691.00 273905.00 274389.00
instances with n = 20 jobs, AGA and V4AGA are tied in all instances, 100 10 7 p <10 3 VNS4 282331.50 282773.00 283517.00
100 10 8 p <10 3 VNS4 294153.50 295090.00 295475.00
and for ten of them there is enough evidence that both methods
100 10 9 p <10 3 VNS4 305224.00 305590.50 306165.00
are superior in performance than VNS4. For one case V4AGA is
100 10 10 p <10 3 VNS4 293511.00 294543.00 296250.50
found superior than AGA.
Tables 6 8 show the statistical test results for each instance.
100 20 1 p <10 3 VNS4 370015.00 371537.50 372589.50
100 20 2 p <10 3 VNS4 375976.00 377477.50 378745.00
Each line of these tables show the name of the instance (Instance),
100 20 3 p <10 3 VNS4 374279.50 375545.00 376074.00
the p-value obtained by Kruskal Wallis, if the p-value is significant
100 20 4 p <10 3 VNS4 377512.00 377949.00 379701.00
it is followed by the name of the method with the smallest
100 20 5 p <10 3 VNS4 373076.50 374277.00 375016.00
median, and finally the median values achieved by each algorithm.
100 20 6 p <10 3 VNS4 376916.00 377004.00 378104.50
According to results in Table 6, there are 26 instances where 100 20 7 p <10 3 VNS4 377459.00 378741.50 379965.50
100 20 8 p <10 3 VNS4 388597.50 389961.50 390731.50
Kruskal Wallis indicates evidence of significant differences
100 20 9 p <10 3 VNS4 378597.50 379922.50 381012.50
between methods. Within these 26 instances, V4AGA presents
100 20 10 p <10 3 VNS4 383143.50 384011.00 385009.50
the best median values in 25 cases, and in one case AGA presents
8160 W.E. Costa et al. / Expert Systems with Applications 39 (2012) 8149 8161
Table 8
p-Values from Kruskal Wallis test over instances with 200 or more jobs and the median values obtained by each method.
Instance p-Value In favor of VNS4 AGA V4AGA
200 10 1 0.013 VNS4 1057561.00 1058092.00 1058429.00
200 10 2 p <10 3 VNS4 1043161.00 1049210.50 1051053.00
200 10 3 p <10 3 VNS4 1051303.50 1058430.00 1059215.00
200 10 4 p <10 3 VNS4 1039624.00 1043125.50 1044921.50
200 10 5 p <10 3 VNS4 1042911.00 1048112.50 1047838.00
200 10 6 p <10 3 AGA 1014857.00 1014549.00 1019746.00
200 10 7 p <10 3 VNS4 1062187.00 1065169.00 1068497.50
200 10 8 p <10 3 VNS4 1048525.50 1055244.00 1055244.00
200 10 9 p <10 3 VNS4 1029121.50 1038602.50 1037567.00
200 10 10 p <10 3 VNS4 1038920.00 1044654.50 1045752.50
200 20 1 p <10 3 VNS4 1234608.50 1246449.00 1244176.50
200 20 2 p <10 3 VNS4 1255518.00 1262339.00 1258745.50
200 20 3 p <10 3 VNS4 1278374.00 1286676.50 1281564.50
200 20 4 p <10 3 VNS4 1253130.00 1258941.50 1258977.00
200 20 5 p <10 3 VNS4 1232183.00 1243482.50 1240938.50
200 20 6 p <10 3 VNS4 1234752.50 1245244.50 1242230.50
200 20 7 p <10 3 VNS4 1249897.50 1260995.50 1259046.50
200 20 8 p <10 3 VNS4 1256663.50 1264530.50 1259458.50
200 20 9 p <10 3 VNS4 1238698.00 1248343.00 1247948.00
200 20 10 p <10 3 VNS4 1259135.50 1269884.00 1265131.00
500 20 1 p <10 3 VNS4 6718172.50 6741940.00 6752936.00
500 20 2 p <10 3 VNS4 6841999.50 6873072.00 6874949.50
500 20 3 p <10 3 VNS4 6736986.50 6817652.50 6805891.50
500 20 4 p <10 3 VNS4 6753284.50 6831773.50 6847538.50
500 20 5 p <10 3 VNS4 6713215.50 6793042.00 6804557.50
500 20 6 p <10 3 VNS4 6745774.50 6777530.00 6777530.00
500 20 7 p <10 3 VNS4 6718134.00 6778152.00 6775344.50
500 20 8 p <10 3 VNS4 6782198.00 6811714.50 6841730.50
500 20 9 p <10 3 VNS4 6727208.00 6780167.00 6770592.50
500 20 10 p <10 3 VNS4 6758935.00 6836878.00 6828256.50
the best median. AGA presents the best medians in 22 cases, and statistic methods pointed out differences, favoring VNS4. VNS4
VNS4 has the second best value in 4 cases. For instances with produced 29 novel solutions for the benchmark. The new VNS
n = 100 jobs, the results are shown in Table 7, the Kruskal-Wallis also has the best average and median values of most instances
test indicates significant differences on 29 cases, in all of them with n P 100;
VNS4 is the method presenting the best values for median. AGA The two methods developed in this study, VNS4 and V4AGA, are
has better median values than V4AGA on all 29 cases. A similar competitive with state-of-art methods, for both were capable of
behavior was observed in Table 8,where results for instances with producing novel solutions, besides statistical tools favored these
n P 200 jobs are shown. The Kruskal Wallis test points out differ- two methods on particular cases.
ences on all 30 instances. Among those instances, VNS4 presents
the best median on 29 cases, the second best in one case. AGA pre- 6. Conclusions
sents the best result on one instance and the second best on 14
cases, two of them tied with V4AGA, whereas V4AGA has the sec- This work presented a new VNS approach, VNS4, to optimize to-
ond best median on 16 cases, including the ones it ties with AGA. tal flowtime in a permutational flowshop environment, among the
Overall, from the set of 90 instances, there are 85 cases where a results reported there are 34 novel solutions for Taillard s bench-
significant difference was pointed out by statistical analysis, on mark instances, 29 of them produced by VNS4, contributing to
display in Tables 6 8. On these 85 instances, VNS4 has the best the state-of-the-art of the problem. The design of VNS4 considered
median in 58 cases, and the second best in 5 cases; AGA has the some factors, namely neighborhood order, Shake procedure and
best median on 2 cases and the second best on 65 cases, including initial solution. Statistical analyses were conducted to define the
ties. Whereas V4AGA has the best median value in 26 cases, the proper value for each factor, resulting in a VNS different from other
second best on 17 cases. VNS approaches reported in the literature of the problem. There-
A few remarks on the relative performance of the three tested fore two questions were raised: how this new VNS performs in
methods, given the results shown in Tables 3 8, are: comparison with state-of-the-art methods of the problem? Would
current state-of-art hybrid methods benefit, having their perfor-
V4AGA exhibits better performance than VNS4 and AGA on mance improved, with the use of VNS4?
cases with n650 jobs. AGA presented better median values To address the stated questions, experiments comparing VNS4,
for a large number of instances with n P 100, 35 in total. There- AGA and V4AGA were conducted over 120 benchmark instances.
fore, one can conclude that hybridization of AGA with VNS4 Where, AGA is one current state-of-the-art method, and V4AGA
(V4AGA) was beneficial on small to medium cases, but not nec- is a novel approach created by replacing the E-VNS method from
essarily to large cases (n P 100), probably due the stop criteria AGA by VNS4, in an attempt to address the second question. The
of VNS4. choice for AGA was due to claim, in Xu et al. (2011), of its superi-
Although AGA shows better performance than V4AGA on ority over previously reported methods.
instances with at least 100 jobs, VNS4 has better performance Statistical tests over the results suggest that V4AGA has better
than tested approaches on these instances. On 58 instances, performance than both AGA and VNS4, for instances up to 50 jobs.
W.E. Costa et al. / Expert Systems with Applications 39 (2012) 8149 8161 8161
Liu, J., & C. R. (2001). Constructive and composite heuristic solutions to the
These results indicate that VNS4 can improve the quality of hybrid
PReeves,
p== ci scheduling problem. European Journal of Operational Research, 132,
approaches for some instances, however its stop criterion might
439 452.
harm the performance on large instances. The statistics also sug-
Murata, T., Ishibuchi, H., & Tanaka, H. (1996). Genetic algorithms for flowshop
gest that VNS4 has better performance than V4AGA and AGA on in- scheduling problems. Computers and Industrial Engineering, 30, 1061 1071.
Nagano, M. S., & Moccellin, J. V. (2007). Reducing mean flow time in permutation
stances with 100 or more jobs, being therefore competitive with
flow shop. Journal of the Operational Research Society, 59, 1700 1707.
state-of-the-art approaches. Further studies involving VNS4 will fo-
Nagano, M. S., Ruiz, R., & Lorena, L. A. N. (2008). A constructive genetic algorithm for
cus on the development of novel hybrid methods with population permutation flowshop scheduling. Computers and Industrial Engineering, 55,
195 207.
based approaches.
Pan, Q.-K., Tasgetiren, M. F., & Liang, Y.-C. (2008). A discrete particle swarm
optimization algorithm for the no-wait flowshop scheduling problem.
Acknowledgement Computers and Operations Research, 35, 2807 2839.
Rajendran, C. (1993). Heuristic algorithm for scheduling in a flowshop to minimize
total flowtime. International Journal of Production Economics, 29, 65 73.
The authors want to thank Xu, Xu & Gu who kindly provided
Rajendran, C., & Ziegler, H. (1997). An efficient heuristic for scheduling in a
the source code of AGA used in this study. This work was
flowshop to minimize total weighted flowtime of jobs. European Journal of
Operational Research, 103, 129 138.
partially supported by the Conselho Nacional de Desenvolvimento
Rajendran, C., & Ziegler, H. (2004). Ant-colony algorithms for permutation flowshop
Científico e Tecnológico, CNPq  Brasil, under Grants 141851/
scheduling to minimize makespan/total flowtime of jobs. European Journal of
2009-0, 303538/2008-2, 302333/2007-0.
Operational Research, 155, 426 438.
Ruiz, R., & Stützle, T. (2007). A simple and effective iterated greedy algorithm for the
flowshop scheduling problem. European Journal of Operational Research, 177,
References
2033 2049.
Taillard, E. D. (1993). Benchmarks for basic scheduling problems. European Journal
Conover, W. J. (1980). Practical nonparametric statistics (2nd ed.). J. Wiley.
of Operational Research, 64, 278 285.
Dong, X., Huang, H., & Chen, P. (2009). An iterated local search algorithm for the
Tasgetiren, M. F., Liang, Y.-C., Sevkli, M., & Gencyilmaz, G. (2007). A particle swarm
permutation flowshop problem with total flowtime criterion. Computers and
optimization algorithm for makespan and total flowtime minimization in the
Operations Research, 36, 1664 1669.
permutation flowshop sequencing problem. European Journal of Operational
Framinan, J. M., & Leisten, R. (2003). An efficient constructive heuristic for flowtime
Research, 177, 1930 1947.
minimisation in permutation flow shops. Omega, 31, 311 317.
Tasgetiren, M. F., Pan, Q.-K., Suganthan, P. N., & Chen, A. H.-L. (2010). A discrete
Framinan, J. M., Leisten, R., & Ruiz-Usano, R. (2002). Efficient heuristics for flowshop
artificial bee colony algorithm for the permutation flow shop scheduling
sequencing with the objectives of makespan and flowtime minimisation.
problem with total flowtime criterion. Proceedings of the IEEE world congress on
European Journal of Operational Research, 141, 559 569.
computational intelligence (WCCI-2010) (pp. 137 144). IEEE.
Graham, R., Lawler, E., Lenstra, J., & Kan, A. R. (1979). Optimization and
Tseng, L.-Y., & Lin, Y.-T. (2009). A hybrid genetic local search algorithm for the
approximation in deterministic sequencing and scheduling: A survey. Annals
permutation flowshop scheduling problem. European Journal of Operational
of Discrete Mathematics, 5, 287 326.
Research, 198, 84 92.
Hansen, P., & Mladenović, N. (1997). Variable neighborhood search for the p-
Xu, X., Xu, Z., & Gu, X. (2011). An asynchronous genetic local search algorithm for
median. Location Science, 5, 207 226.
the permutation flowshop scheduling problem with total flowtime
Hansen, P., Mladenović, N., & Pérez, J. A. M. (2008). Variable neighbourhood search:
minimization. Expert Systems with Applications, 38, 7970 7979.
Methods and applications. Operations Research, 319 360.
Zhang, Y., Li, X., & Wang, Q. (2009a). Hybrid genetic algorithm for permutation
Jarboui, B., Eddaly, M., & Siarry, P. (2009). An estimation of distribution algorithm
flowshop scheduling problems with total flowtime minimization. European
for minimizing the total flowtime in permutation flowshop scheduling
Journal of Operational Research, 169, 869 876.
problems. Computers and Operations Research, 36, 2638 2646.
Zhang, Y., Li, X., Wang, Q., & Zhu, J. (2009b). Similarity based ant-colony algorithm
Jarboui, B., Ibrahim, S., Siarry, P., & Rebai, A. (2008). A combinatorial particle swarm
for permutation flowshop scheduling problems with total flowtime
optimisation for solving permutation flowshop problems. Computers and
minimization. International Conference on Computer Supported Cooperative
Industrial Engineering, 54, 526 538.
Work in Design (pp. 582 589). Los Alamitos, CA, USA: IEEE Computer Society.
Liao, C.-J., Tseng, C.-T., & Luarn, P. (2007). A discrete version of particle swarm
optimization for flowshop scheduling problems. Computers and Operations
Research, 34, 3099 3111.