New VNS heuristic for total flowtime flowshop scheduling problem

background image

New VNS heuristic for total flowtime flowshop scheduling problem

Wagner Emanoel Costa

a

,

, Marco César Goldbarg

b

, Elizabeth G. Goldbarg

b

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.

(1)

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

Rajendran and Ziegler (1997)

, TFT is an impor-

tant objective in many real life manufacturing systems, for it min-
imizes holding costs.

TFTð

P

Þ ¼

X

n

i¼1

p

i

;

ð1Þ

The values of C(

p

i

, m) can be evaluated using Eqs.

(2)–(5)

. Eqs.

(2) and (3)

define the completion time relative to the first job in

permutation

P

,

p

1

. Eq.

(2)

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

(3)

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

.

p

1

;

1Þ ¼ t

p

1

;

1

ð2Þ

p

1

;

rÞ ¼ Cð

p

1

;

r  1Þ þ t

p

1

;

r

8

r 2 f2; . . . ; mg

ð3Þ

Eqs.

(4) and (5)

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.

(5)

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).

p

i

;

1Þ ¼ Cð

p

i1

;

1Þ þ t

p

i

;

1

8

i 2 f2; . . . ; ng

ð4Þ

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 (

Graham, Lawler, Lenstra,

& Kan, 1979

), many heuristic approaches have been proposed to

this problem such as constructive methods (

Framinan, Leisten, &

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

Corresponding author. Tel.: +55 84 3215 3814.
E-mail addresses:

wemano@gmail.com

(W.E. Costa),

gold@dimap.ufrn.br

(M.C.

Goldbarg),

beth@dimap.ufrn.br

(E.G. Goldbarg).

Expert Systems with Applications 39 (2012) 8149–8161

Contents lists available at

SciVerse ScienceDirect

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

background image

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 (

Rajendran & Ziegler,

2004; Zhang, Li, Wang, & Zhu, 2009b

), particle swarm optimization

(

Jarboui, Ibrahim, Siarry, & Rebai, 2008; Tasgetiren, Liang, Sevkli, &

Gencyilmaz, 2007, 2007

), bee colony optimization (

Tasgetiren, Pan,

Suganthan, & Chen, 2010

), hybrid discrete differential evolutionary

algorithm (

Tasgetiren et al., 2010

), VNS and EDA-VNS (

Jarboui,

Eddaly, & Siarry, 2009

).

From the cited approaches, the works of

Zhang et al. (2009a),

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

Zhang et al. (2009a), Tas-

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

Pan et al. (2008)

, 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

Taillard (1993)

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
(

Xu et al., 2011

), 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

2

reports a brief review of literature. Section

3

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

4

reports the experiments

to determine which combination of neighborhoods performs best,
using a subset of instances from

Taillard (1993)

. Section

5

de-

scribes the computational experiments and results obtained by
applying VNS4, AGA and V4AGA over all 120 instances of the data
set. Section

6

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

Rajendran and Ziegler (1997)

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.

(6)

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) (

Liu & Reeves, 2001

) 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.

(7)

, where w

rk

is calculated

with Eq.

(8)

. 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.

(8)

, 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.

(9)

.

f

ik

¼ ðn  k  2ÞIT

ik

þ AT

ik

ð9Þ

Also,

Liu and Reeves (2001)

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

Liu and Reeves (2001)

also proposes the use of job interchange lo-

cal search to further improve the greedy solution obtained.

Framinan et al. (2002)

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

background image

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.

Nagano and Moccellin (2007)

create the queue in the

same way as in

Framinan and Leisten (2003)

. 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

Dong et al. (2009)

adopts

the job at index neighborhood created by

Rajendran and Ziegler

(2004)

. 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

Dong et al. (2009)

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

Zhang et al. (2009a)

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

Tseng and Lin (2009)

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 (

Xu et al., 2011

), 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.

Rajendran and Ziegler (2004)

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,

Zhang et al. (2009b)

, starts using uniform

probability distribution and evolves the probabilities of the phero-
mones using Kullback–Leibler divergence, (

see Zhang et al., 2009b,

for further details

).

The PSO of

Tasgetiren et al. (2007)

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

Liao, Tseng,

and Luarn (2007)

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

Jarboui et al. (2008)

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

Jarboui et al. (2009)

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 (

Jarboui et al., 2009

) 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%.

Tasgetiren et al. (2010)

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,

Ruiz and Stützle (2007)

. 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

background image

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 (

Xu et al., 2011

), DABC (

Tasgetiren

et al., 2010

), hDDE (

also in Tasgetiren et al., 2010

), VNS, EDA-VNS

(

Jarboui et al., 2009

), HGA (

Zhang et al., 2009a

) and HGLS (

Tseng

& Lin, 2009

) 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

Hansen and Mladenovic´

(1997)

for the p-median problem. In a recent review (

Hansen,

Mladenovic´, & Pérez, 2008

), 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

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;

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

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

be easily implemented using a number of random moves from a
iven neighborhood, as suggested by

Hansen et al. (2008)

. Different

initialization methods are tested in Section

4

. 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, (

Jarboui et al., 2009;

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

.

Fig. 1

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

Fig. 1

, 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

.

Fig. 2

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

Zhang et al. (2009a)

, VNS5 (Algorithm 12) combines the neigh-

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
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

background image

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

background image

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

4

.

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

background image

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

4.1

.

The Shake procedure is implemented using a number k of random
job insert moves. In Section

4.2

up to 20 different values of k are tested.

Section

4.3

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

Liu and Reeves (2001)

.

A subset of Taillard’s instances is used in the experimentation.

The

complete

dataset

contains

120

randomly

generated

instances (

Taillard, 1993

). 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.

(10)

, 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 (

Conover, 1980

) indicates

that many options tested have a non-normal distribution (p-value
smaller than 10

3

), therefore Kruskal–Wallis test (

Conover, 1980

),

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

.

Table 1

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

Table 1

).

4.2. Shake – perturbation strength

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.
The work of

Dong et al. (2009)

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

background image

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

Table 2

. 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

Liu and Re-

eves (2001)

. 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

Xu et al. (2011)

.

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

Xu et al. (2011)

.

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 (

Taillard, 1993

). 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 (

Xu et al., 2011

), 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

background image

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

background image

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

background image

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

Xu et al. (2011)

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

Tables 3–5

. 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 (

Table 3

), 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 (

Table 4

), 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 (

Table 5

), 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

4

. 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.

Tables 6–8

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

Table 6

, 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

background image

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

Table 7

, 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

Table 8

,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

Tables 6–8

. 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

Tables 3–8

, 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

Xu et al. (2011)

, 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

background image

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