New VNS heuristic for total flowtime flowshop scheduling problem
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
Keywords:
Flowshop
Scheduling
Total flowtime
Heuristics
VNS
a b s t r a c t
This paper presents a new Variable Neighborhood Search (VNS) approach to the permutational flowshop
scheduling with total flowtime criterion, which produced 29 novel solutions for benchmark instances of
the investigated problem. Although many hybrid approaches that use VNS do exist in the problems
literature, no experimental study was made examining distinct VNS alternatives or their calibration. In this
study six different ways to combine the two most used neighborhoods in the literature of the problem,
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
In the permutational flowshop scheduling problem, there is a
set of jobs J = {1, 2, . . . , n}. Each of n jobs has to be processed by a
set of m machines M = {1, 2, . . . , m}, sequentially from the first ma-
chine to the last, in the same order. Each job j requires t
jr
units of
time on machine r. Each machine can process at most one job at
any given time, and it cannot be interrupted. Each job is available
at time zero and can be processed by at most one machine in any
given time. Here the focus is to find the permutation of jobs
P
= {
p
1
,
p
2
, . . . ,
p
n
}, such that the total completion time of jobs,
named total flowtime (TFT), is minimized. Eq.
expresses math-
ematically the concept of total flowtime of a given permutation,
P
,
where C(
p
i
, m) stands for the completion time of job in position i of
P
,
p
i
. According to
, TFT is an impor-
tant objective in many real life manufacturing systems, for it min-
imizes holding costs.
TFTð
P
Þ ¼
X
n
i¼1
Cð
p
i
;
mÞ
ð1Þ
The values of C(
p
i
, m) can be evaluated using Eqs.
. Eqs.
define the completion time relative to the first job in
permutation
P
,
p
1
. Eq.
defines the completion time of the first
job,
p
1
, on the first machine as time required to complete its pro-
cessing, t
1,1
. It provides a base case for
which defines the com-
pletion time of
p
1
on machine r, 1 < r 6 m, as the completion time
of
p
1
on the previous machine, C(
p
1
, r 1), plus the processing
time of job
p
1
on machine r, t
1,r
.
Cð
p
1
;
1Þ ¼ t
p
1
;
1
ð2Þ
Cð
p
1
;
rÞ ¼ Cð
p
1
;
r 1Þ þ t
p
1
;
r
8
r 2 f2; . . . ; mg
ð3Þ
Eqs.
evaluate the completion times for each job
p
i
,
1 < i 6 n. When r = 1, C(
p
i
,1) is defined as the sum of the completion
time of the previous job on the first machine, C(
p
i1
,1), with the
processing time of
p
i
, t
i,1
. For all remaining machines, 1 < r 6 m,
completion time of job
p
i
, C(
p
i
, r), 1 < i 6 n, depends on two factors.
First, the time on which job
p
i
concludes its processing on the pre-
vious machine, r 1, and therefore becomes available to be pro-
cessed on machine r. Second, machine r can process job
p
i
only, if
r has finished processing the previous job,
p
i1
. If machine r has
not concluded the previous job,
p
i1
, then the processing of job
p
i
will start after machine r concludes job
p
i1
. Eq.
expresses both
factors and defines the completion time, C(
p
i
, r), 1 < i 6 n and
1 < r 6 m, as the sum of processing time t
i,r
, with the greatest value
between C(
p
i
, r 1) and C(
p
i1
,r).
Cð
p
i
;
1Þ ¼ Cð
p
i1
;
1Þ þ t
p
i
;
1
8
i 2 f2; . . . ; ng
ð4Þ
Cð
p
i
;
rÞ ¼ maxfCð
p
i
;
r 1Þ; Cð
p
i1
;
rÞg þ t
p
i
;
r
8
i
2 f2; . . . ; ng
8
r 2 f2; . . . ; mg
ð5Þ
Due to the fact that the decision problem associated with TFT is NP-
Complete in the strong sense when m P 2 (
), many heuristic approaches have been proposed to
this problem such as constructive methods (
Ruiz-Usano, 2002; Liu & Reeves, 2001; Nagano & Moccellin, 2007;
0957-4174/$ - see front matter 2012 Elsevier Ltd. All rights reserved.
doi:
⇑
Corresponding author. Tel.: +55 84 3215 3814.
E-mail addresses:
(W.E. Costa),
(M.C.
Goldbarg),
(E.G. Goldbarg).
Expert Systems with Applications 39 (2012) 8149–8161
Contents lists available at
Expert Systems with Applications
j o u r n a l h o m e p a g e : w w w . e l s e v i e r . c o m / l o c a t e / e s w a
Rajendran, 1993; Rajendran & Ziegler, 1997
), local search methods
(
Dong, Huang, & Chen, 2009; Liu & Reeves, 2001
) genetic algorithms
(
Nagano, Ruiz, & Lorena, 2008; Tseng & Lin, 2009; Xu, Xu, & Gu,
2011; Zhang, Li, & Wang, 2009a
), ant colonies (
2004; Zhang, Li, Wang, & Zhu, 2009b
), particle swarm optimization
(
Jarboui, Ibrahim, Siarry, & Rebai, 2008; Tasgetiren, Liang, Sevkli, &
), bee colony optimization (
), hybrid discrete differential evolutionary
algorithm (
), VNS and EDA-VNS (
).
From the cited approaches, the works of
Tseng and Lin (2009), Jarboui et al. (2009), Tasgetiren et al.
(2010) and Xu et al. (2011)
are the ones which produced the cur-
rent state-of-art results.
A significant number among the state-of-art approaches com-
bine two neighborhoods, named job insert and job interchange,
in an internal VND procedure. The two neighborhoods are com-
bined in the same order in the works of
getiren et al. (2010) and Xu et al. (2011)
. Within flowshop’s
literature, the only work to test distinct ways to combine these
neighborhoods is
Pan, Tasgetiren, and Liang (2008)
, where a hybrid
heuristic, particle swarm with VND, is devised for the no-wait
flowshop problem. The experiments of
, test the
hybridization of a PSO algorithm with two VND approaches, one
starting with job insert and the other starting with job interchange.
Both of them create all neighboring solutions before deciding to
which solution to migrate. The results point out that the use of
job interchange as the initial neighborhood provides the best per-
formance on the tested instances of the no-wait flowshop. So far no
study has been reported, for classical flowshop with total flowtime
criterion, examining distinct combinations of neighborhoods.
The present study examines six distinct combinations of the
two most common neighborhoods structures for the permuta-
tional flowshop scheduling using total flowtime criterion.
Although, in the problem’s literature, the use of VNS is common,
the results of the experiments performed on instances of the suite
created by
suggested that, the most profitable com-
bination of job interchange and job insert local search, is distinct
from the combination of such local searches in literature. Consider-
ing that this new combination is a novel VNS for flowshop TFT, two
questions arise: How does the new VNS perform when it is com-
pared to state-of-the-art methods? Can current state-of-the-art
methods benefit from using the new combination?
To address those questions, the novel VNS, labeled VNS4 is com-
pared with two other approaches, one named AGA and the other
named V4AGA. AGA is a genetic algorithm hybridized with VNS
(
), which was claimed by its authors as superior algo-
rithm when compared to other state-of-the-art methods. V4AGA is
a novel hybrid approach proposed here, that replaces the VNS used
in AGA by the one developed in this study. This experiment
resulted in 34 novel solutions, 29 of then generated by VNS4.
The remaining of this paper is organized as follows. Section
reports a brief review of literature. Section
describes the VNS ap-
proaches as well as the describes the job insert and job interchange
neighborhoods, the different ways to combine them and parame-
ters tested in the experiments. Section
reports the experiments
to determine which combination of neighborhoods performs best,
using a subset of instances from
. Section
de-
scribes the computational experiments and results obtained by
applying VNS4, AGA and V4AGA over all 120 instances of the data
set. Section
presents some conclusions.
2. Literature review
This section reviews some methods proposed for PFSP with TFT
criterion. Because the PFSP literature is vast this review is limited to
only some constructive methods in literature, and metaheuristic ap-
proaches that constitute the current state-of-the-art of the problem.
The method of
evaluates the lower
bound for each job available for assignment, and creates, m different
solutions by changing as many machines as were considered in eval-
uating the lower bound. For instance, the first solution was con-
structed by sorting the jobs, in the non-decreasing order, by the
weighted sum of the processing times of all m machines. The
weights are defined in such a way that one unit of processing time
of a machine, r = j, has greater impact than one unit of time of subse-
quent machines, r > j. Eq.
shows the formula for the unweighted
total flowtime. The equation for the weighted total flowtime is
slightly different, but the weighted case is not the topic of discussion
in this work. The processing time of the first machine is deleted, and
the jobs re-sorted considering only the processing times of the m 1
machines. This procedure is repeated, by deleting data from one ma-
chine at each iteration until the last solution is created, when only
the processing time of the last machine is taken into account. The
best solution among the m created ones is then submitted to a local
search procedure using job insert neighborhood.
X
m
r¼j
ðm r þ 1ÞT
ri
j 2 f1; . . . ; mg
ð6Þ
The method H(1) (
) weights down two crite-
ria: weighted sum of machine idle time (IT) and artificial flowtime
(AT). The idle time criterion for selecting job i when k jobs were al-
ready selected (IT
ik
), is defined by Eq.
, where w
rk
is calculated
with Eq.
. When the difference between C(i, r 1) and C(
p
k
, r)
is positive, means machine r is idle. The weights, as defined in
Eq.
, stress that idle times on early machines are undesirable,
for they delay the remaining jobs. Such stress is stronger if there
are many unscheduled jobs (small value of k), but it becomes weak
when the number k of scheduled jobs increases.
IT
ik
¼
X
m
r¼2
w
rk
maxfCði; r 1Þ Cð
p
k
;
rÞ; 0g
ð7Þ
w
rk
¼
m
r þ kðm rÞ=n 2
ð8Þ
The artificial flowtime (AT
ik
) of a candidate job i after k jobs
were schedule refers to the TFT value obtained after including
unscheduled job i, plus the time of an artificial job placed at the
end of the job sequence. The processing time of the artificial job
on each machine is equal to the average processing time of all
unscheduled jobs, excluding job i, on the corresponding machine.
Both criteria, IT
ik
and AT
ik
are combined according to Eq.
.
f
ik
¼ ðn k 2ÞIT
ik
þ AT
ik
ð9Þ
Also,
propose a class of constructive heu-
ristics named H(x), where x is an integer, 1 6 x 6 n. Each variant
differs in the number of solutions it produces which is given by
x. While H(1) produces only one solution, H(2) produces two solu-
tions and so on. These methods create new solutions by changing
the initial job. Once the greedy criterion used in these heuristics
is adaptive, different initial jobs produce different solutions. H(1)
uses the job with the best value according to the greedy criterion
as the initial job. H(2) creates two solutions using each of the
two best evaluated jobs as the initial job. Thus, the first solution
generated by H(2) is exactly the same as the one generated by
H(1). The second solution uses the second best job as the initial
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
also proposes the use of job interchange lo-
cal search to further improve the greedy solution obtained.
define a queue based on the sum of the
processing times of each job. The job at the top of the queue is
8150
W.E. Costa et al. / Expert Systems with Applications 39 (2012) 8149–8161
inserted in the best possible position in the partial solution. Later
the inserted job can be interchanged with any other job in the par-
tial solution in order to minimize the current value of the total
flowtime.
create the queue in the
same way as in
. The algorithm itera-
tively removes the first job in the queue and places it at the end of
the partial solution. Local search methods, job insert and inter-
change, are then applied over the partial sequence to minimize to-
tal flowtime.
The iterated local search proposed by
adopts
the job at index neighborhood created by
. This neighborhood consists of job insert moves; the order
in which neighboring solutions are created depends on of the best
solution found so far. In
each time the local
search procedure gets trapped in local optima, a perturbation is
performed over the solution and local search resumed. In this case,
the perturbation involves six randomly interchanging adjacent
jobs in the solution.
The hybrid genetic algorithm (HGA) of
ap-
plies a data mining procedure over its population, creating a table
that maps jobs to positions and counts the ‘‘good’’ solutions in a gi-
ven association job/position. An assignment procedure creates a
solution that will be used during crossover operations to preserve
building blocks in the new solutions. Solutions obtained after
crossover are submitted to local searches (with job insert and
interchange neighborhoods). The HGLS (hybrid genetic with local
search) of
uses an orthogonal crossover oper-
ator to recombine solutions. New solutions are submitted to two
local searches that use the job insert neighborhood. One local
search method is driven to minimize total flowtime, whereas the
other looks for minimizing idle times. The latter is used to escape
local optima, and then minimization of TFT is resumed. The asyn-
chronous genetic algorithm, AGA (
), has a population
of 40 solutions, one of them generated using H(n/m) heuristic,
where n/m are created using the H criterion, followed by inter-
change local search, the other 39 are randomly generated. At each
iteration, the evolution process submits a solution to E-VNS (an
specific VNS approach), crossover and E-VNS a second time. If
all individual in population have the same TFT value, the popula-
tion is restarted, by random generating 38 individuals, keeping
the best solution in the current pool of solutions and inserting
the solution generated by H(n/m) again. The E-VNS uses job insert
local search and job interchange. When using job insert local
search, a job
p
i
is randomly selected. E-VNS will attempt to re-in-
sert
p
i
on a different position j, also randomly selected. If such at-
tempt improves current solution, the new solution is accepted
and a new iteration of job insert occurs, selecting another random
job to be re-inserted. E-VNS executes 50 iterations of job insert.
After them, 50 iterations of job interchange occurs, where the
jobs to be interchanged are randomly selected, if any improve-
ment is achieved the solution is accepted and E-VNS resumes
job insert local search. The number of times job insert can be re-
sumed is limited by a value, randomly selected each time E-VNS
is called, between 10 and 60, therefore is possible to E-VNS to ter-
minate not trapped in a local optima. AGA uses a two point cross-
over defined in
Murata, Ishibuchi, and Tanaka (1996)
. The pair of
parents used in crossover is randomly selected. The crossover
chooses two random points, s and t, of a parent, the block of jobs
within the index (
p
i
, s 6 i 6 t) are copied to their respective posi-
tions in a new solution, the remaining positions are filled follow-
ing the job order on the second parent. Such crossover is applied
twice for each pair of parents creating 2 new solutions. In each
iteration, the crossover operator is applied repeatedly, until 40
new solutions are created, replacing the previous population.
E-VNS is applied over the new solutions. AGA stops if a time limit
of 0.4 n m seconds is reached.
propose two ant colonies for the
problem, they are named MMAS and PACO. They apply three iter-
ations of job at index local search once a solution has been fully
constructed. MMAS and PACO differ on how the probabilities are
assigned to unscheduled jobs in constructing the solution. MMAS
adopts uniform distribution for the best five options, whereas
PACO assigns distinct probabilities to the five best options. The
ant colony named SACO,
, starts using uniform
probability distribution and evolves the probabilities of the phero-
mones using Kullback–Leibler divergence, (
).
The PSO of
use a real representation of
solution and a rule is used to decode the real representation into
a permutational representation. The particles move towards the
best global point and visit the best previous position. A variable
neighborhood descent (VND) approach (using interchange and
job insert neighborhoods) is defined and applied to the best solu-
tion in the population of each generation. The PSO of
represents a solution using a discrete binary ma-
trix B, where job i is assigned to position j if the entry b
ij
= 1. The
velocity represents probabilities of changes within B. This PSO uses
two local searches (interchange and job insert) but limits the
neighborhood size. Depending on the jobs positions, the search
procedure considers only movements within a distance of 12 posi-
tions (e.g. a job in the first position cannot be inserted in position
14 or above, nor can it be interchanged with another job placed in
position 14 or above). The PSO of
uses the per-
mutation representation and applies a simulated annealing meth-
od to optimize solutions whose TFT is within 2% of the best TFT
value obtained so far.
The VNS of
uses two neighborhoods: job in-
sert and interchange. First, the procedure starts using job inter-
change. Once this neighborhood fails to improve the current
solution, it migrates to insert neighborhood and keeps using job
insert moves until no further improvement can be reached, when
it reverts to using job interchange. If both neighborhoods fail to
further improve the solution further, the VNS makes a copy of
the best solution found, applies the random interchange move to
it, and resumes optimization using job interchange neighborhood.
The algorithm alternates between the two neighborhoods until
both of them fail to improve the current solution.
EDA-VNS (
) is a hybrid evolutionary ap-
proach. It uses a population of 10 solutions from which a subset
Q of three solutions is selected. A probabilistic model is con-
structed based on Q which is used to generate new solutions. If a
new solution is better than the worst solution in the population,
the new one replaces the worst solution. There is a probability of
applying VNS over a solution. Such probability is related to objec-
tive function: the closer the value is to the best found total flow-
time value the better are the chances that VNS will be applied
over a solution. The closer the value of a given solution is to the
best flowtime value found so far, the better the chances of applying
VNS over a solution. The changes decrease exponentially for farther
from the minimum of 1%.
propose two approaches for TFT: a bee
colony optimization (name DABC) and a hybrid evolutionary ap-
proach (hDDE). There is a population of ten bees in DABC, each
one executing one of three activities. In the first activity, namely
employed bee phase, the bee exploits its current solution by ran-
domly choosing between three methods: job insert, interchange
and iterated greedy neighborhood,
. Once
a neighborhood is chosen, it is further improved by using VND.
In the second activity, namely onlooker phase, the bee migrates
to another solution, randomly picking two solutions from the other
bees and keeping the better one. Then, the bee creates a neighbor
of the chosen solution, using the same schemes from employed
W.E. Costa et al. / Expert Systems with Applications 39 (2012) 8149–8161
8151
bee, and applies a VND composed of job insert, followed by inter-
change afterwards. The VND procedure keeps using interchange
until no further improvement is possible then migrates to inter-
change, until no further improvement is possible. The VND mi-
grates between insert and interchange until a local minimum,
common to both neighborhoods is found. In the third activity,
namely scout, the bee generates two random solutions, keeps the
worse one and applies the iterated greedy move over it. The algo-
rithm hDDE also uses a population with 10 individuals. Its solution
representation is discrete. Mutation is done by a random insert or
interchange move. The crossover operator takes a muted individual
and combines it with a non-mutated solution. For a given position
pos, the crossover picks a random number c within [0,1]. If c is
smaller than the constant CR = 0.9, the value from the mutated
solution fills position pos, otherwise the value for pos comes from
the non-mutated one. There is 1% probability of applying VNS (in-
sert and interchange moves only) over an individual. The iterated
greedy procedure is applied only over the best individual of the
population. Crossover and mutation rates are 90% and 20%,
respectively.
The results produced by AGA (
), DABC (
), hDDE (
also in Tasgetiren et al., 2010
), VNS, EDA-VNS
(
) and HGLS (
) are used as references for the experiments presented
here, once these methods present the best results over flowshop
instances created by Taillard, as far as the authors’ knowledge con-
cerns. These instances have been used as test set for flowshop TFT
and are used here on the computational experiments to assess the
proposed approach performance in comparison to the state-of-the-
art methods.
3. Variable Neighborhood Search – VNS
VNS is a meta-heuristic created by
for the p-median problem. In a recent review (
), the creators define VNS as ‘‘. . . a meta-
heuristic which systematically exploits the idea of neighborhood
change, both in descent to local minima and in escape from the val-
leys which contain them’’.
Because of its simplicity and efficiency, VNS is often hybridized
with other heuristics in order to find solutions of higher quality.
VNS has few parameters, at the same time, it has a record of good
results in many problems including flowshop. The approaches pre-
sented by
, 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;
3. A set of local search neighborhoods;
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
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
produced the best results among the tested
methods. Therefore, H heuristics are used to create initial solutions
in the methods described in Section
. The second item, Shake, can
be easily implemented using a number of random moves from a
iven neighborhood, as suggested by
. Different
initialization methods are tested in Section
. The remaining of this
section is devoted to items 3 and 4, describing the neighborhoods
and the tested VNS approaches.
Considering the particular case of permutational flowshop with
TFT criterion, two local search methods are repeatedly used in lit-
erature. They are job insert local search, also referred as shift local
search, and the job interchange local search, (
Tasgetiren et al., 2010; Xu et al., 2011; Zhang et al., 2009a
).
The neighborhood used in job insert is defined as follows, let
P
A
= {
p
A1
,
p
A2
, . . . ,
p
An
} be a solution for the PFSP. Solution
P
B
= {
p
B1
,
p
B2
, . . . ,
p
Bn
} is in the job insert neighborhood of solution
P
A
if given two indices s and t, s < t one of the two possibilities is
true, either
p
Bs
=
p
At
, and "c, s 6 c < t,
p
Bc
=
p
Ac+1
, or
p
Bt
=
p
As
, and
"d, s < d 6 t,
p
Bd
=
p
Ad1
.
illustrates the job insert neighbor-
hood,
P
A
= {1, 2, 7, 4, 5, 6, 3}, s = 2, t = 6 and
P
B
= {1, 7, 4, 5, 6, 2, 3}.
On
, job 2 (in black) occupies the second position in the start-
ing solution. A neighbor solution is generated moving job 2 to the
sixth position and shifting the jobs between the third and sixth
positions of the starting solution.
In the interchange neighborhood, two jobs exchange positions.
Solution
P
B
= {
p
B1
,
p
B2
, . . . ,
p
Bn
} is a neighbor of
P
A
= {
p
A1
, -
p
A2
, . . . ,
p
An
} if given two indices s and t, s – t,
p
As
=
p
Bt
,
p
At
=
p
Bs
and "c, c – s, t,
p
Ac
=
p
Bc
.
illustrates two neighbors,
P
A
= {1,2,7,4,5,6,3} and
P
B
= {1,6,7,4,5,2,3}, where s = 2 and t = 6.
The Algorithms 1–6 describe how to implement local search
methods based on the above described neighborhoods, Algorithms
7–12 refer to six VNS implementations combining both neighbor-
hoods in distinct ways. The VNS of Algorithm 7 is the one used
in
, VNS5 (Algorithm 12) combines the neigh-
borhoods as
do. Algorithm 12 has the same
structure of the VNS used in work by
. The
other three VNS are novel approaches proposed and under exam
in this paper.
Algorithm 1 implements the task of, given a job
p
i
, creating all
possible neighbors by re-inserting
p
i
in a different position. The
procedure receives a solution
P
and the index of a position. Ini-
tially a temporary copy, named
P
0
, of solution
P
is made in line
1. The procedure continues by shifting the job
p
i
to a different po-
sition j, (i – j), lines 2 to 11. If the new solution (
P
0
) is better than
the original (
P
), then,
P
is updated and the procedure finishes,
lines 5 to 7. Otherwise, the shift is reversed by the command In-
sert(
P
0
, j, i) (line 9). The procedure continues to loop until all n
positions, except position i, are examined.
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
between the second and sixth position, in gray, are shifted during the process.
Fig. 2. Example of a movement using interchange neighborhood. Job 2, in black, is
moved from the second position to the sixth, creating a neighbor solution. Jobs in
between the second and sixth position, in gray, are shifted during the process.
8152
W.E. Costa et al. / Expert Systems with Applications 39 (2012) 8149–8161
Algorithm 1. Job-insert-
p
i
(
P
, i)
1:
P
0
P
2: for j = 1 to n do
3:
if i – j then
4:
Insert(
P
0
, i, j)
5:
if TFP(
P
0
) < TFP(
P
) then
6:
P
P
0
7:
return
P
8:
end if
9:
Insert(
P
0
, j, i)
10: end if
11: end for
12: return
P
Algorithm 2 creates neighbors using the interchange neigh-
borhood. The procedure receives a solution
P
and the index of
a position. With these two arguments it constructs neighboring
solutions, by interchanging job
p
i
with job
p
j
, j > i. Initially a
temporary copy, named
P
0
, of solution
P
is made in line 1.The
loop, from line 2 to line 9, creates and exams the interchange
neighbors. In line 3, job
p
i
changes its positions with job
p
j
. If
this change improves the original solution,
P
, then
P
is updated
and the procedure returns, lines 4 to 7. Otherwise, the change is
reversed, line 8.
Algorithm 2. Interchange-
p
i
(
P
, i)
1:
P
0
P
2: for j = i + 1 to n do
3:
Interchange(
P
0
, i, j)
4:
if TFP(
P
0
) < TFP(
P
) then
5:
P
P
0
6:
return
P
7:
end if
8:
Interchange(
P
0
, j, i)
9: end for
10: return
P
The Algorithms 3 and 4 are reduced local search methods. For
each job
p
i
, they apply either Job-insert-
p
i
(
P
, i) or the Inter-
change-
p
i
(
P
, i) procedure. They conclude after applying their
respective neighborhoods over all positions. Algorithm 3, named
Reduced-JI(
P
), uses Job-insert-
p
i
(
P
, i) procedure. If the Job-
insert-
p
i
(
P
, i) procedure improves the current solution, it returns
a True value otherwise it returns False. Similarly, Algorithm 3,
named Reduced-Interchange (
P
), uses Interchange-
p
i
(
P
, i) proce-
dure. Reduced-Interchange(
P
) will return True only if it improves
the current solution,
P
.
Algorithm 3. Reduced-JI (
P
)
1: improve False
2:
P
0
P
3: Current_Flow TFT
4: for i = 1 to n do
5:
Job-insert-
p
i
(
P
, i)
6:
if TFT(
P
) < Current_Flow then
7:
improve True
8:
end if
9: end for
10: return improve
Algorithm 4. Reduced-Interchange(
P
)
1: improve False
2:
P
0
P
3: Current_Flow TFT
4: for i = 1 to n 1 do
5:
Interchange-
p
i
(
P
, i)
6:
if TFT(
P
) < Current_Flow then
7:
improve True
8:
end if
9: end for
10: return improve
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
value and the running time has not exceeded the time limit. The
procedure Job-Insert-LS(
P
, time_limit) will continuously explore
the insert neighborhood until, either no further improvement is
possible, or the time limit is reached. The Algorithm 6, Job-Inter-
change-LS(
P
, time_; limit) procedure, explores the job interchange
neighborhood until no further improvement is possible as well as
limit for the execution time. In both procedures an initial solution
is provided, as well the time limit constraint.
Algorithm 5. Job-Insert-LS(
P
, time_limit)
1: condition True
2: while conditionand within time_limit do
3: condition Reduced-JI (
P
)
4: end while
5: return
P
Algorithm 6. Job-Interchange-LS(
P
, time_limit)
1: condition True
2: while condition and within time_limit do
3:
condition Reduced-Interchange(
P
)
4: end while
5: return
P
The VNS of Algorithm 7, named VNS1, explores both neighbor-
hoods fully. First it explores job insert, once it reaches a local optima,
there is a neighborhood change to job interchange. VNS1 continues
applying interchange moves until no further improvements can be
found. At this point the procedure exams if the current solution is
the best one so far and updates the best solution if it is the case, line
6. The procedure then copies the best solution found during the
search, and disturbs it with shake, introducing random modifica-
tions into
P
in order to escape local optima. After it, the procedure
restarts from job insert local search, in line 9. Otherwise the proce-
dure returns the best solution found (Best_Solution), line 10.
Algorithm 7. VNS1(
P
)
1:
P
Initial_Sol
2: Best_Solution
P
3: repeat
4: Job-Insert-LS (
P
, time_limit)
5: Job-Interchange-LS (
P
, time_limit)
6: Update_Best_Solution(
P
)
7:
P
Best_Solution
8: Shake(
P
)
9: until time limit is reached
10: return Best_Solution
W.E. Costa et al. / Expert Systems with Applications 39 (2012) 8149–8161
8153
The VNS2, Algorithm 8, is very similar to VNS1, the difference
lies on the order neighborhoods are examined. VNS2 firstly ex-
plores interchange neighborhoods and later migrates to job insert
(lines 4 and 5).
Algorithm 8. VNS2(
P
)
1:
P
Initial_Sol
2: Best_Solution
P
3: repeat
4:
Job-Interchange-LS(
P
, time_limit)
5:
Job-Insert-LS(
P
, time_limit)
6:
Update_Best_Solution(
P
)
7:
P
Best_Solution
8:
Shake(
P
)
9: until time_limit is reached
10: return Best_Solution
The main difference between Algorithms 9 and 10, to VNS1 and
VNS2 heuristics, is the use of reduced local searches procedures,
Algorithms 3 and 4. The third VNS approach, Algorithm 9, starts
fully exploring job insert, when it fails to improve the current solu-
tion, it calls Reduced-Interchange (
P
) which is equivalent to one
iteration of interchange local search. If this single iteration finds
an improvement over current solution
P
, the VNS resumes job in-
sert local search. In terms of pseudo-code, this is expressed from
lines 5 to 8. The repeat loop starting on line 3 is equivalent to
the repeat loops of Algorithms 7 and 8. Within this loop, there is
a Boolean variable named condition, initially set to True so an inner
while loop can iterate, lines 4 and 5. Job insert local search is ap-
plied, line 6, when it stops on a local optima, an iteration of inter-
change is applied, line 7. If this single iteration improves the
quality of
P
, Reduced-Interchange (
P
) will return true, this will lead
the algorithm back to job insert local search, for variable condition
will be true. If the interchange iteration fails, then, condition will be
false, terminating while loop. In this case VNS3 exams if a new best
solution was found, line 9.
P
receives a copy of the current best
solution, line 10. The shake procedure acts over
P
, line 11, and if
the time limit was not reached, the local search is resumed, other-
wise the procedure terminates returning the best solution found so
far, line 13.
Algorithm 9. VNS3(
P
, time_limit)
1:
P
Initial_Sol
2: Best_Solution
P
3: repeat
4:
condition True
5:
while condition and within time_limit do
6:
Job-Insert-LS(
P
, time_limit)
7:
condition Reduced-Interchange(
P
)
8:
end while
9:
Update_Best_Solution(
P
)
10:
P
Best_Solution
11:
Shake(
P
)
12: until time limit is reached
13: return Best_Solution
VNS4, Algorithm 10, is analogous to VNS3. Algorithm 10 starts
exploring interchange until no further improvement is possible,
line 6. Then, Reduced-JI(
P
) is used, a single iteration of job insert
neighborhood. If this iteration improves the current solution, the
algorithm resumes the interchange local search.
Algorithm 10. VNS4(
P
, time_limit, Initial_Sol)
1:
P
Initial_Sol
2: Best_Solution
P
3: repeat
4: condition True
5: while condition and within time_limit do
6:
Job-Interchange-LS(
P
, time_limit)
7:
condition Reduced-JI(
P
)
8: end while
9: Update_Best_Solution(
P
)
10:
P
Best_Solution
11: Shake(
P
)
12: until time limit is reached
13: 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 procedure, different from VNS1, resumes job insert local search.
The Shake procedure is called only if a local minimum common to
both neighborhoods is found. In terms of pseudo-code it was ex-
pressed using an inner loop, line 6, two Boolean variables (named
condition1 and condition2), and four if tests (lines 8, 12, 16, 20).
The variable textitcondition1 in tested in line 8, only if the variable
has a true value job insert local search is executed. The variable con-
dition2 is used similarly to variable condition1, but related to job
interchange local search. Initially both variables, condition1 and
condition2, are set to True, lines 4 and 5. The while loop of line 6
is executed only if at least one of the two variable stores a true value
and there is time to continue the search. Once the local search fin-
ishes, condition1 receives false. It will continue to be false until
either job interchange improves the current solution (then the if
statement of line 20 will be satisfied) or if both procedures no long-
er improve the current solution, exiting the inner while to the re-
peat loop where condition1 and condition2 receive the true value.
The use of condition2 follows the same logic. When condition2 holds
a true value, the statements within the if statement of line 16 exe-
cute job interchange local search and set condition2 as false. The
variable condition2 is set to True only if job insert improves the cur-
rent solution (line 12), or in the beginning of a new iteration of the
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
current solution,
P
, is set to the best solution found and is submit-
ted to Shake procedure (line 26).
The sixth VNS, VNS6 is depicted in Algorithm 12. The only dif-
ference between VNS5 and VNS6 is that the former starts using
job insert local search, whereas the latter starts using job inter-
change local search, line 9. The remaining of Algorithm 12 is sim-
ilar to Algorithm 11. This concludes the description of VNS
approaches to be examined on Section
.
Algorithm 11. VNS5(
P
, time_limit, Initial_Sol)
1:
P
Initial_Sol
2: Best_Solution
P
3: repeat
4:
condition1 True
5:
condition2 True
6: while (condition1 or condition2) and within time_limit do
7:
current_flowtime TFT(
P
)
8:
if condition1 then
9:
Job-Insert-LS(
P
, time_limit)
10:
condition1 False
8154
W.E. Costa et al. / Expert Systems with Applications 39 (2012) 8149–8161
11:
end if
12:
if TFT(
P
) < current_flowtime then
13:
condition2 True
14:
end if
15:
current_flowtime TFT(
P
)
16:
if condition2 then
17:
Job-Interchange-LS(
P
, time_limit)
18:
condition2 False
19:
end if
20:
if TFT(
P
) < current_flowtime then
21:
condition1 True
22:
end if
23:
end while 24:
Update_Best_Solution(
P
)
25:
P
Best_Solution
26:
Shake(
P
)
27: until time limit is reached
28: return Best_Solution
Algorithm 12. VNS6(
P
, time_limit, Initial_Sol)
1:
P
Initial_Sol
2: Best_Solution
P
3: repeat
4:
condition1 True
5:
condition2 True
6:
while (condition1 or condition2) and within time_limit do
7:
current_flowtime TFT(
P
)
8:
if condition1 then
9:
Job-Interchange-LS (
P
, time_limit)
10:
condition1 False
11:
end if
12:
if TFT(
P
) < current_flowtime then
13:
condition2 True
14:
end if
15:
current_flowtime TFT(
P
)
16:
if condition2 then
17:
Job-Insert-LS(
P
, time_limit)
18:
condition2 False
19:
end if
20:
if TFT(
P
) < current_flowtime then
21:
condition1 True
22:
end if
23:
end while
24:
Update_Best_Solution(
P
)
25:
P
Best_Solution
26:
Shake(
P
)
27: until time limit is reached
28: return Best_Solution
4. Calibration experiments
This section reports experiments done to calibrate the following
parameters of the proposed algorithms: neighborhood order and
change strategy, Shake mechanism and initial solution method. The
six VNS procedures, described in Section 3, are tested in Section
.
The Shake procedure is implemented using a number k of random
job insert moves. In Section
up to 20 different values of k are tested.
Section
reports the results of the comparison between six different
methods utilized to create the initial solution, one random and five oth-
ers using the criterion of
.
A subset of Taillard’s instances is used in the experimentation.
The
complete
dataset
contains
120
randomly
generated
instances (
). The number of jobs is in the set
{20, 50, 100, 200, 500} and the number of machines in {5, 10, 20}.
The subset utilized in the experiments reported in this section com-
prises the five first test cases of each group of 50 and 100 jobs of Tail-
lard’s dataset, making a total of 30 instances. Twenty independent
executions of each algorithmic version are performed for each in-
stance; therefore there will be 600 (six hundred) data points col-
lected for each version under test. The tests were executed on a
Core 2 – Quad 2.4 GHz (Q6600), 1 GB RAM.
The methodology transforms the results obtained during trials
into relative percentage deviation (RPD) using Eq.
, where
Best
Solution
refers to the lowest TFT found in any experiment on
the same instance. Because RPD is a dimensionless value resultant
from a normalization procedure, the RPDs from different instances
are comparable. The Shapiro–Wilk test (
) indicates
that many options tested have a non-normal distribution (p-value
smaller than 10
3
), therefore Kruskal–Wallis test (
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
considered the best one among the tested options. The median is
used instead of using arithmetic mean of RPDs, as the median is
a non-parametric indicator, whereas arithmetic mean is an indica-
tor for normal distributions.
RPDð%Þ ¼ 100
Heuristic
Solution
Best
Solution
Best
Solution
ð10Þ
Initially the VNS’ parameters are defined as follows:
1. Initial solution randomly generated;
2. The Shake procedure is defined as two random job interchange
moves;
3. Time limit set to 0.4 n m seconds.
4.1. Neighborhood order
The first decision to be made concerns is which VNS procedure
presents the best behavior. The best one is adopted in the experi-
ments. The Kruskal–Wallis test suggests differences among differ-
ent procedures tested, p-value smaller than 10
3
.
summarizes the results, reporting the RPD median value of each
option. As stated earlier, the median is the criterion used to define
which parameter value is the best one, in this case it means that
VNS4 was considered the best option among the tested VNS proce-
dures (indicated in bold face in
).
4.2. Shake – perturbation strength
The next parameter to be examined is the Shake procedure. The
VNS of
uses one interchange move as Shake.
They do not report any experiment to calibrate this parameter.
The work of
tested multiple numbers of inter-
change moves, and their results indicated that four to seven inter-
change moves were appropriate when using only job insert local
search.
Table 1
RPD’s median for different VNS approaches.
VNS approaches
Technique
VNS1
VNS2
VNS3
Median – RPD(%)
0.671894
0.663554
0.503719
Technique
VNS4
VNS5
VNS6
Median – RPD(%)
0.461363
0.685505
0.493171
W.E. Costa et al. / Expert Systems with Applications 39 (2012) 8149–8161
8155
This experiment deals with the number of job insert moves, k,
used in Shake. The experiment varies k from one up to twenty,
1 6 k 6 20. Again Kruskal–Wallis test points out differences when
the value k varies (p-value smaller than 10
3
). The medians are
summarized in
. They indicate that Shake procedures com-
posed of less than 14 moves or greater than 18 moves are not
among the best options. Although, the results with 14 6 k 6 18
produce very similar results, the value k = 14 is selected, as it is
the one with the lowest RPD median.
4.3. Initialization method
This subsection deals with different initialization methods. The
tests were restricted to heuristics using the criterion of
. The heuristics tested are H(1), H(2), H(n/10), H(n/m),
and H(n). Random generated solutions are also testes as initial
solution. Heuristic H(n/m) is described in
The analysis of the results, using Kruskal–Wallis, did not detect
a significant difference between initialization methods (p-value
equals to 0.21). Under these circumstances, the decision of what
method to choose does not depend on the median of RPDs.
Once a decision cannot be made based on the median, we
decided to choose the heuristic H(n/m) once it is used in AGA
and this algorithm is compared to VNS4.
This concludes the calibration experiments. The final version of
VNS uses the following parameters.
1. Initialization method: H(n/m);
2. Shake procedure: 14 random job insert moves;
3. Local search methods: Job Interchange and Insert
4. Neighborhood change scheme: VNS4 procedure;
The next section reports the results obtained in tests performed
with VNS4 applied to 120 Taillard’s benchmark instances. Those
results are compared to the ones obtained by the best approaches
from literature, as far as the authors’ knowledge concerns, and
with state-of-art method AGA presented by
5. Computational experiments
The proposed VNS algorithm was implemented in C++ on a Core
2 – Quad 2.4 GHz (Q6600), 1 GB RAM, using Gnu C++ compiler. The
experiments were performed on all 120 instances from the Tail-
lard’s benchmark (
). Thirty independent executions
were performed for each instance. The stopping criterion adopted
in the experimentation was a maximum processing time of
0.4 n m seconds, for it is the same used in recent works of
Jarboui et al. (2009), Tasgetiren et al. (2010) and Xu et al. (2011)
.
The results achieved by VNS4 are compared with the one
obtained by AGA (
), and V4AGA. There are two
Table 2
RPD’s median for different number of job insert moves, used as Shake procedure.
Number of insert moves k
k = 1
k = 2
k = 3
k = 4
k = 5
RPD(%)
0.531533
0.547817
0.532402
0.522590
0.550798
k = 6
k = 7
k = 8
k = 9
k = 10
RPD(%)
0.535054
0.538884
0.561393
0.570443
0.534179
k = 11
k = 12
k = 13
k = 14
k = 15
RPD(%)
0.524655
0.545517
0.543708
0.469627
0.472480
k = 16
k = 17
k = 18
k = 19
k = 20
RPD(%)
0.481483
0.477755
0.478360
0.532989
0.532077
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
8156
W.E. Costa et al. / Expert Systems with Applications 39 (2012) 8149–8161
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
differences between AGA and V4AGA. First, the fact the latter uses
VNS4 instead of E-VNS. VNS4 is applied only to solutions created
during crossover, in this case no Shake procedure is used. Second,
AGA uses E-VNS which is bounded in number of iterations,
whereas VNS4 ends by finding a local minimum common to both
neighborhoods, therefore VNS4 is likely to consume more process-
ing time than E-VNS, and might harm the performance of V4AGA
on large instances. The authors of
kindly provided
the source code of their method.
From the 30 instances with n = 20, algorithm VNS4 achieved the
best known solution of 20 instances with convergence rate 100%.
AGA heuristic achieved the best known solution of 29 instances
on all trials. The exception was on instance identifier 4 with
n = 20 and m = 10, with 95% of convergence. V4AGA converged to
the optimum on 100% of its independent executions.
A summary of the results for the remaining instances (90 in-
stances with n P 50) are summarized on
. Each line of
these tables shows the name of the instance (Instance), which is
denoted by n m and an identifying number, the best solution re-
ported in literature (Best), the algorithm that produced the best
solution (Algorithm), the minimum (Min), average (Ave), maxi-
mum (Max) and standard deviation (S.D.) recorded after 30 execu-
tions by each tested method. Novel solutions are indicated by a star
symbol (w) next to the value. The best average and minimum val-
ues found during experimentation are indicated in bold face. For
the 30 instances with n = 50 jobs (
), the approach V4AGA
achieves the highest number of minimum solutions, 18 in total,
three of them novel solutions. V4AGA has the best average on 27
cases. AGA achieves 10 minimum solutions, two of them are novel
solutions (one of them is a novel solution that both AGA and
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 (
), VNS4 has the highest num-
ber of minimum solutions, 27 in total, eight of them novel ones.
VNS4 exhibited the best average value for all 30 instances. AGA
achieves the minimum solution in three cases, one of them is a no-
vel solution. A similar trend was observed on instances with
n P 200 (
), where VNS4 has the smallest minimum solution
in all 30 cases, 21 of them novel solutions, and has the best average
in 29 cases.
The results obtained by the three tested approaches are also
examined using the Kruskal–Wallis test. However it is used slightly
different from the way it was used in Section
. Instead of trans-
forming all the results into RPD values, and then applying Krus-
kal–Wallis test over all results, the test is applied for each
instance with n P 50 jobs, and if, for a given instance, the test indi-
cates evidence of differences between the compared methods
(p-value 6 0.05), the median value of each method is used to dis-
cern the performances of the tested approaches. Because here the
interest is to rank the methods, therefore the analysis of statistical
results includes comments regarding how many time each method
has the best median and the second best median. Considering the
instances with n = 20 jobs, AGA and V4AGA are tied in all instances,
and for ten of them there is enough evidence that both methods
are superior in performance than VNS4. For one case V4AGA is
found superior than AGA.
show the statistical test results for each instance.
Each line of these tables show the name of the instance (Instance),
the p-value obtained by Kruskal–Wallis, if the p-value is significant
it is followed by the name of the method with the smallest
median, and finally the median values achieved by each algorithm.
According to results in
, there are 26 instances where
Kruskal–Wallis indicates evidence of significant differences
between methods. Within these 26 instances, V4AGA presents
the best median values in 25 cases, and in one case AGA presents
Table 6
p-Values from Kruskal–Wallis test over instances with 50 jobs and the median values
obtained by each method.
Instance
p-Value
In favor of
VNS4
AGA
V4AGA
50 05 1
p < 10
3
V4AGA
64922.00
64885.50
64844.50
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
50 05 4
p < 10
3
V4AGA
68548.00
68468.50
68428.00
50 05 5
0.008
V4AGA
69570.50
69563.00
69521.00
50 05 6
p < 10
3
V4AGA
67053.00
67019.00
66959.00
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
50 05 9
p < 10
3
V4AGA
63149.00
63104.50
63072.50
50 05 10
0.062
–
69118.00
69094.00
69087.50
50 10 1
p < 10
3
V4AGA
88225.00
87702.00
87589.00
50 10 2
0.860
–
83241.50
83231.00
83262.00
50 10 3
p < 10
3
V4AGA
80299.00
80364.00
80223.50
50 10 4
0.043
V4AGA
86907.50
86913.00
86849.00
50 10 5
0.033
V4AGA
86858.50
86853.00
86774.00
50 10 6
p < 10
3
V4AGA
87002.50
86952.00
86829.50
50 10 7
0.009
V4AGA
89428.00
89338.00
89261.00
50 10 8
0.171
–
87095.00
87164.00
87223.00
50 10 9
0.883
–
86042.50
86031.50
86049.00
50 10 10
0.037
AGA
88494.00
88384.00
88421.00
50 20 1
0.006
V4AGA
126449.50
126422.00
126116.50
50 20 2
0.007
V4AGA
119614.00
119524.50
119399.50
50 20 3
0.002
V4AGA
117150.50
117061.00
116950.00
50 20 4
p < 10
3
V4AGA
121511.00
121199.00
120973.50
50 20 5
p < 10
3
V4AGA
119036.50
118909.00
118742.50
50 20 6
p < 10
3
V4AGA
121287.00
121170.00
121060.50
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
50 20 9
p < 10
3
V4AGA
122455.50
122287.50
122262.00
50 20 10
0.004
V4AGA
124699.00
124700.50
124558.00
Table 7
p-Values from Kruskal–Wallis test over instances with 100 jobs and the median
values obtained by each method.
Instance
p-Value
In favor of
VNS
AGA
V4AGA
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
100 05 3
p < 10
3
VNS4
238814.50
239493.50
239815.50
100 05 4
p < 10
3
VNS4
228853.00
228914.50
229583.00
100 05 5
p < 10
3
VNS4
241600.00
241862.50
242391.00
100 05 6
p < 10
3
VNS4
233748.50
234293.50
234820.50
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
100 05 9
p < 10
3
VNS4
249365.00
250185.50
250377.50
100 05 10
p < 10
3
VNS4
244398.00
244521.00
244937.00
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
100 10 3
p < 10
3
VNS4
290654.00
291242.50
292010.50
100 10 4
0.184
–
304804.50
305163.50
305498.50
100 10 5
p < 10
3
VNS4
286335.50
288263.00
288645.50
100 10 6
p < 10
3
VNS4
272691.00
273905.00
274389.00
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
100 10 9
p < 10
3
VNS4
305224.00
305590.50
306165.00
100 10 10
p < 10
3
VNS4
293511.00
294543.00
296250.50
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
100 20 3
p < 10
3
VNS4
374279.50
375545.00
376074.00
100 20 4
p < 10
3
VNS4
377512.00
377949.00
379701.00
100 20 5
p < 10
3
VNS4
373076.50
374277.00
375016.00
100 20 6
p < 10
3
VNS4
376916.00
377004.00
378104.50
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
100 20 9
p < 10
3
VNS4
378597.50
379922.50
381012.50
100 20 10
p < 10
3
VNS4
383143.50
384011.00
385009.50
W.E. Costa et al. / Expert Systems with Applications 39 (2012) 8149–8161
8159
the best median. AGA presents the best medians in 22 cases, and
VNS4 has the second best value in 4 cases. For instances with
n = 100 jobs, the results are shown in
, the Kruskal-Wallis
test indicates significant differences on 29 cases, in all of them
VNS4 is the method presenting the best values for median. AGA
has better median values than V4AGA on all 29 cases. A similar
behavior was observed in
,where results for instances with
n P 200 jobs are shown. The Kruskal–Wallis test points out differ-
ences on all 30 instances. Among those instances, VNS4 presents
the best median on 29 cases, the second best in one case. AGA pre-
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-
ond best median on 16 cases, including the ones it ties with AGA.
Overall, from the set of 90 instances, there are 85 cases where a
significant difference was pointed out by statistical analysis, on
display in
. On these 85 instances, VNS4 has the best
median in 58 cases, and the second best in 5 cases; AGA has the
best median on 2 cases and the second best on 65 cases, including
ties. Whereas V4AGA has the best median value in 26 cases, the
second best on 17 cases.
A few remarks on the relative performance of the three tested
methods, given the results shown in
, are:
V4AGA exhibits better performance than VNS4 and AGA on
cases with n 6 50 jobs. AGA presented better median values
for a large number of instances with n P 100, 35 in total. There-
fore, one can conclude that hybridization of AGA with VNS4
(V4AGA) was beneficial on small to medium cases, but not nec-
essarily to large cases (n P 100), probably due the stop criteria
of VNS4.
Although AGA shows better performance than V4AGA on
instances with at least 100 jobs, VNS4 has better performance
than tested approaches on these instances. On 58 instances,
statistic methods pointed out differences, favoring VNS4. VNS4
produced 29 novel solutions for the benchmark. The new VNS
also has the best average and median values of most instances
with n P 100;
The two methods developed in this study, VNS4 and V4AGA, are
competitive with state-of-art methods, for both were capable of
producing novel solutions, besides statistical tools favored these
two methods on particular cases.
6. Conclusions
This work presented a new VNS approach, VNS4, to optimize to-
tal flowtime in a permutational flowshop environment, among the
results reported there are 34 novel solutions for Taillard’s bench-
mark instances, 29 of them produced by VNS4, contributing to
the state-of-the-art of the problem. The design of VNS4 considered
some factors, namely neighborhood order, Shake procedure and
initial solution. Statistical analyses were conducted to define the
proper value for each factor, resulting in a VNS different from other
VNS approaches reported in the literature of the problem. There-
fore two questions were raised: how this new VNS performs in
comparison with state-of-the-art methods of the problem? Would
current state-of-art hybrid methods benefit, having their perfor-
mance improved, with the use of VNS4?
To address the stated questions, experiments comparing VNS4,
AGA and V4AGA were conducted over 120 benchmark instances.
Where, AGA is one current state-of-the-art method, and V4AGA
is a novel approach created by replacing the E-VNS method from
AGA by VNS4, in an attempt to address the second question. The
choice for AGA was due to claim, in
, of its superi-
ority over previously reported methods.
Statistical tests over the results suggest that V4AGA has better
performance than both AGA and VNS4, for instances up to 50 jobs.
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
8160
W.E. Costa et al. / Expert Systems with Applications 39 (2012) 8149–8161
These results indicate that VNS4 can improve the quality of hybrid
approaches for some instances, however its stop criterion might
harm the performance on large instances. The statistics also sug-
gest that VNS4 has better performance than V4AGA and AGA on in-
stances with 100 or more jobs, being therefore competitive with
state-of-the-art approaches. Further studies involving VNS4 will fo-
cus on the development of novel hybrid methods with population
based approaches.
Acknowledgement
The authors want to thank Xu, Xu & Gu who kindly provided
the source code of AGA used in this study. This work was
partially supported by the Conselho Nacional de Desenvolvimento
Científico e Tecnológico, CNPq – Brasil, under Grants 141851/
2009-0, 303538/2008-2, 302333/2007-0.
References
Conover, W. J. (1980). Practical nonparametric statistics (2nd ed.). J. Wiley.
Dong, X., Huang, H., & Chen, P. (2009). An iterated local search algorithm for the
permutation flowshop problem with total flowtime criterion. Computers and
Operations Research, 36, 1664–1669.
Framinan, J. M., & Leisten, R. (2003). An efficient constructive heuristic for flowtime
minimisation in permutation flow shops. Omega, 31, 311–317.
Framinan, J. M., Leisten, R., & Ruiz-Usano, R. (2002). Efficient heuristics for flowshop
sequencing with the objectives of makespan and flowtime minimisation.
European Journal of Operational Research, 141, 559–569.
Graham, R., Lawler, E., Lenstra, J., & Kan, A. R. (1979). Optimization and
approximation in deterministic sequencing and scheduling: A survey. Annals
of Discrete Mathematics, 5, 287–326.
Hansen, P., & Mladenovic´, N. (1997). Variable neighborhood search for the p-
median. Location Science, 5, 207–226.
Hansen, P., Mladenovic´, N., & Pérez, J. A. M. (2008). Variable neighbourhood search:
Methods and applications. Operations Research, 319–360.
Jarboui, B., Eddaly, M., & Siarry, P. (2009). An estimation of distribution algorithm
for minimizing the total flowtime in permutation flowshop scheduling
problems. Computers and Operations Research, 36, 2638–2646.
Jarboui, B., Ibrahim, S., Siarry, P., & Rebai, A. (2008). A combinatorial particle swarm
optimisation for solving permutation flowshop problems. Computers and
Industrial Engineering, 54, 526–538.
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.
Liu, J., & Reeves, C. R. (2001). Constructive and composite heuristic solutions to the
p==
P
c
i
scheduling problem. European Journal of Operational Research, 132,
439–452.
Murata, T., Ishibuchi, H., & Tanaka, H. (1996). Genetic algorithms for flowshop
scheduling problems. Computers and Industrial Engineering, 30, 1061–1071.
Nagano, M. S., & Moccellin, J. V. (2007). Reducing mean flow time in permutation
flow shop. Journal of the Operational Research Society, 59, 1700–1707.
Nagano, M. S., Ruiz, R., & Lorena, L. A. N. (2008). A constructive genetic algorithm for
permutation flowshop scheduling. Computers and Industrial Engineering, 55,
195–207.
Pan, Q.-K., Tasgetiren, M. F., & Liang, Y.-C. (2008). A discrete particle swarm
optimization algorithm for the no-wait flowshop scheduling problem.
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.
Rajendran, C., & Ziegler, H. (1997). An efficient heuristic for scheduling in a
flowshop to minimize total weighted flowtime of jobs. European Journal of
Operational Research, 103, 129–138.
Rajendran, C., & Ziegler, H. (2004). Ant-colony algorithms for permutation flowshop
scheduling to minimize makespan/total flowtime of jobs. European Journal of
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,
2033–2049.
Taillard, E. D. (1993). Benchmarks for basic scheduling problems. European Journal
of Operational Research, 64, 278–285.
Tasgetiren, M. F., Liang, Y.-C., Sevkli, M., & Gencyilmaz, G. (2007). A particle swarm
optimization algorithm for makespan and total flowtime minimization in the
permutation flowshop sequencing problem. European Journal of Operational
Research, 177, 1930–1947.
Tasgetiren, M. F., Pan, Q.-K., Suganthan, P. N., & Chen, A. H.-L. (2010). A discrete
artificial bee colony algorithm for the permutation flow shop scheduling
problem with total flowtime criterion. Proceedings of the IEEE world congress on
computational intelligence (WCCI-2010) (pp. 137–144). IEEE.
Tseng, L.-Y., & Lin, Y.-T. (2009). A hybrid genetic local search algorithm for the
permutation flowshop scheduling problem. European Journal of Operational
Research, 198, 84–92.
Xu, X., Xu, Z., & Gu, X. (2011). An asynchronous genetic local search algorithm for
the
permutation
flowshop
scheduling
problem
with
total
flowtime
minimization. Expert Systems with Applications, 38, 7970–7979.
Zhang, Y., Li, X., & Wang, Q. (2009a). Hybrid genetic algorithm for permutation
flowshop scheduling problems with total flowtime minimization. European
Journal of Operational Research, 169, 869–876.
Zhang, Y., Li, X., Wang, Q., & Zhu, J. (2009b). Similarity based ant-colony algorithm
for
permutation
flowshop
scheduling
problems
with
total
flowtime
minimization. International Conference on Computer Supported Cooperative
Work in Design (pp. 582–589). Los Alamitos, CA, USA: IEEE Computer Society.
W.E. Costa et al. / Expert Systems with Applications 39 (2012) 8149–8161
8161
Document Outline
Wyszukiwarka
Podobne podstrony:
Happy New Year & Top New Year’s Resolutions for 13!
A new control strategy for instantaneous voltage compensator using 3 phase PWM inverter
10 129 139 New Tool Steel for Warm and Hot Forging
New valve series for large refrigeration systems
plany, We have done comprehensive research to gauge whether there is demand for a new football stadi
christmas and new year a glossary for esl learners
Hitler s New Economic Order for Europe
Jagota, Dani 1982 A New Calorimetric Technique for the Estimation of Vitamin C Using Folin Phenol
Clarkson P, Dorn R New Chronometric Dates for the Puquinos of Nasca, Peru
A new control strategy for instantaneous voltage compensator using 3 phase PWM inverter
A new evaluation method for lumbar spinal instability
Heron, Shapira (2003) Time to log of New diagnostic criteria for problematic Internet use
RAFTER Music For Total Chickens CD (Asthmatic Kitty) AKR27akr27
A New Rapid Method for Detecting Val103Ile
A new comminution device for high quality chip production
100108 nmea 0183 sentences not recommended for new designs
A New Hybrid Transmission designed for FWD Sports Utility Vehicles
więcej podobnych podstron