Ecien cons uc i e and composi e heu is ics o he
Pe mu a ion Flowshop o minimise o al ea liness and
a diness
∗
Vic o Fe nandez-Viagas
1
, Manuel Dios
1
, Jose M. F aminan
1†
1
Indus ial Managemen , School o Enginee ing, Uni e si y o Se ille,
Camino de los Descub imien os s/n, 41092 Se ille, Spain, { e nandez iagas,mdios, aminan}@us.es
May 19, 2016
Abs ac
In his pape we add ess he p oblem o scheduling jobs in a pe mu a ion owshop
wi h a jus -in- ime objec i e, i.e. he minimiza ion o he sum o o al a diness
and o al ea liness. Since he p oblem is NP-ha d, he e a e se e al app oxima e
p ocedu es a ailable o he p oblem, al hough hei pe o mance la gely depends
on he due da es o he specic ins ance o be sol ed. A e an in-dep h analysis
o he p oblem, die en cases o sub-p oblems a e iden ied and, by inco po a ing
his knowledge, ou heu is ics a e p oposed: a as cons uc i e heu is ic, and h ee
die en local sea ch p ocedu es ha use he p oposed cons uc i e heu is ic as ini ial
solu ion.
The p oposed heu is ics ha e been compa ed on an ex ensi e se o ins ances
wi h he bes -so- a heu is ic o he p oblem, as well as wi h adap a ions o ecien
heu is ics o simila scheduling p oblems. The compu a ional esul s show he ex-
cellen pe o mance o he p oposed algo i hms. Finally, he posi i e impac o he
ecien heu is ics is e alua ed by including hem as seed sequences o one o he
bes me aheu is ic o he p oblem.
Keywo ds: Scheduling, Flowshop, Heu is ics, PFSP, ea liness, a diness
∗
P ep in submi ed o Compu e s & Ope a ions Resea ch. h p://dx.doi.o g/10.1016/j.co .2016.05.006
†
Co esponding au ho . Tel.: +34-954487214; ax: +34-954487329.
1
1 In oduc ion
The owshop is a common manu ac u ing layou o a shop (S o e e al., 1992) in which a se
o machines a e isi ed by a numbe o jobs ollowing each one he same ou e. The owshop
scheduling p oblem deals wi h es ablishing he sequence o jobs be o e each machine in he shop.
I he sequence o jobs be o e each machine is die en , ex ensi e use o manpowe o ad ance
machines would be needed o eo de he jobs be ween each pai o machines. To a oid his, he
mos common simplica ion o he p oblem is he so-called Pe mu a ion Flowshop Scheduling
P oblem (deno ed as PFSP) whe e he sequence o jobs is he same o all machines. The PFSP
is one o he mos s udied Ope a ions Resea ch p oblems in he li e a u e (see e.g. e iews in
Reza Hejazi and Saghaan, 2005, F aminan e al., 2004 and Ruiz and Ma o o, 2005). Among he
goals usually employed o his op imisa ion p oblem, he mos commonly used a e he minimisa-
ion o makespan (see e.g. Pan e al., 2008, Nawaz e al., 1983 and Fe nandez-Viagas and F aminan,
2014), he minimisa ion o o al comple ion ime (see e.g. Pan and Ruiz, 2013, Fe nandez-Viagas and F aminan,
2015c and Dong e al., 2013) and he minimisa ion o o al a diness (see e.g. Vallada e al., 2008,
F aminan and Leis en, 2008 and Fe nandez-Viagas and F aminan, 2015d). The  s wo objec-
i es a e ela ed o bo h a balanced use o he machines and he as p ocessing o he jobs,
whe eas o al a diness ocuses on cus ome s' sa is ac ion. None o hem  s in o a jus -in- ime
philosophy whe e bo h he excess o in en o y in he shop and he delays on he due da es should
be a oided, due o he ac ha jus -in- ime app oaches aim o educe he ollowing aspec s
(Vollman e al., 1997):
•
he complexi y o de ailed ma e ial planning,
•
he need o shop-oo con ol,
•
he wo k-in-p ocess and nal in en o ies, and
•
he ansac ions associa ed wi h shop-oo and pu chasing sys ems.
Gi en he accep ance o jus -in- ime sys ems in p ac ice, he e is a g owing in e es in
he las decades in analysing scheduling p oblems whe e bo h ea liness and a diness a e pe-
nalised (see e.g. e iews Bake and Scudde , 1990, Lau and We ne , 2004, Józe owska, 2007
2
and Shab ay and S eine , 2012). This ype o p oblems is collec i ely known as E/T p oblems.
Mo e specically, he p oblem unde conside a ion is he PFSP o minimise o al ea liness and
a diness, which is deno ed as
Fm|p mu|∑Ej+∑Tj
acco ding o he no a ion in e.g. Pinedo,
1995. Fu he mo e, inse ion o idle ime is no allowed, which ep esen s a common assump-
ion in he li e a u e due o i s undesi able eec s in ce ain p oduc ion en i onmen s (see e.g.
Józe owska, 2007 and Schalle and Valen e, 2013).
Some exac app oaches and app oxima e algo i hms ha e been p oposed in he li e a u e
o he p oblem unde s udy. Howe e , bo h he NP-ha d na u e o he p oblem (see M'Hallah,
2014) and he huge compu a ion imes equi ed by he op imal app oaches e en o small ins ances
(no mo e han 20 jobs) jus i y he need o de elop as app oxima e algo i hms. The eby, se e al
algo i hms ha e been p oposed o he p oblem, such as hose by Zego di e al. (1995) and by
M'Hallah (2014). In his pape , ou new ecien heu is ics (one cons uc i e heu is ic and h ee
composi e heu is ics) a e p oposed. These heu is ics inco po a e se e al p ope ies and a speed
up p ocedu e in o de o educe and accele a e he sea ch space o he heu is ics. The subsequen
compu a ional expe ience shows ha he p oposed heu is ics ou pe o m he bes -so- a heu is ics
o he p oblem, as well as adap a ions o o he s a e-o - he-a heu is ics o ela ed p oblems.
The es o he pape is o ganised as ollows. The backg ound o he p oblem is discussed in
Sec ion 2. In Sec ion 3, he p oblem unde s udy is desc ibed and some p ope ies a e es ablished.
The p oposed algo i hms a e explained in Sec ion 4. A speed up p ocedu e o he inse ion phase
o he heu is ics as well as a comple e compa ison among he implemen ed heu is ics is pe o med
in Sec ion 5. Addi ionally, he inuence o using he heu is ics as seed sequences in he bes so- a
me aheu is ic (ILS) is discussed. Finally, in Sec ion 6, conclusions a e p esen ed.
2 Li e a u e Re iew
As explained in Sec ion 1, he e a e se e al con ibu ions o ou p oblem. Since he heu is ics
p oposed in Sec ion 4 use a speed-up p ocedu e and a e based on pa icula p ope ies o he
ins ance depending on he i s due da es, he li e a u e e iew is di ided in he ollowing i ems:
•
P ocedu es o E/T p oblems on a pe mu a ion owshop whe e idle ime canno be inse ed.
3
•
Iden ica ion o simila ins ances o he scheduling p oblem depending on hei due da es.
•
Speed-up p ocedu es o ela ed PFSP.
Rega ding owshop scheduling p oblems wi h E/T objec i e wi hou inse ion o idle imes,
Moslehi e al. (2009) p opose an op imal algo i hm o he PFSP wi h wo machines o minimise
he sum o maximum ea liness and a diness. Die en b anch-and-bound algo i hms a e de el-
oped by Madhushini e al. (2009) o se e al mul i-objec i e unc ions including o al ea liness
and a diness. Zego di e al. (1995) was  s in p oposing an app oxima e algo i hm (a simula ed
annealing algo i hm) o sol e he PFSP o minimise he sum o weigh ed ea liness and a diness.
Schalle and Valen e (2013) p opose a gene ic algo i hm (GA) ha ou pe o ms se e al me a-
heu is ics o ela ed p oblems, also yielding a ou able esul s ega ding he CPU imes when
compa ed o he algo i hm p oposed by Zego di e al. (1995). Finally, M'Hallah (2014) p oposes
an I e a ed Local Sea ch (ILS) whe e a a iable neighbo hood descen is i e a i ely epea ed a e
a pe u ba ion mechanism. This algo i hm is shown o yield be e esul s han he GA.
I is wo h no ing ha bo h he GA and he ILS algo i hms use he NEHedd (o iginally p o-
posed o he
Fm|p mu|∑Tj
by Kim, 1993) and he Ea lies Due Da e o EDD ule espec i ely,
which a e ei he e y simple seed sequences o simple adap a ions om ano he esea ch p ob-
lems. The NEHedd is an adap a ion o he NEH heu is ic, o iginally p oposed by Nawaz e al.
(1983) o he PFSP o minimise makespan. The main s eps o he NEH a e:
1. An ini ial o de ec o ,
ΠIO := (πIO
1, . . . πIO
n)
, is o med by so ing he jobs acco ding o
a gi en o de . In he o iginal o mula ion o makespan minimisa ion, jobs a e so ed in
non-inc easing o de o he sum o hei p ocessing imes. I jobs a e o de ed acco ding o
die en c i e ia such as he EDD ule, o in ascending o de o he sum o hei p ocessing
imes, he algo i hm is deno ed NEHedd o NEH-ow ime, espec i ely.
2. A pa ial sequence,
Π1
, is cons uc ed wi h he  s job o he ini ial o de , i.e.
Π1=
(π1
1) = (πIO
1)
.
3. Fo
k= 2
o
k=n
he ollowing p ocedu e is epea ed: Job
πIO
k
is inse ed in each posi ion
o
Πk−1
(
k
posi ions a e es ed) and he co esponding objec i e unc ion alue is e alua ed.
4
Then, he
πIO
k
job is inse ed in he pa ial sequence
Πk−1
in he posi ion wi h he lowes
objec i e unc ion alue, deno ed as
l
,
Πk= (πk−1
1, . . . πk−1
l−1, πIO
k, πk−1
l, . . . πk−1
k−1
).
Rega ding he cha ac e iza ion o he p oblem depending on he due da es o he ins ance,
Bagchi e al. (1986) ha e di ided he single-machine E/T p oblem wi h common due da e in wo
die en single-machine p oblems depending on he common due da e. Chand a e al. (2009) ha e
ex ended he a gumen a ion o he PFSP wi h common due da es and classi y he p oblem in o
h ee die en cases. Fe nandez-Viagas and F aminan (2015b) ha e di ided he
Fm|p mu|∑Tj
wi h die en due da es o each job in ou a eas depending on he means and a iances o he
due da es, each a ea ep esen ing a die en op imiza ion p oblem.
Finally, due o he NP-ha d na u e o PFSP, esea che s ha e subs an ially imp o ed hei e-
sul s by using speed-up p ocedu es. The mos well-known o hese p ocedu es is he speed-up algo-
i hm o he NEH de eloped by Tailla d (1990), employed o he FPSP wi h makespan objec i e.
Using his speed-up p ocedu e, he complexi y o he inse ion s ep dec eases an o de o
n
(i.e.
om
n2·m
o
n·m
) and he e o e, he complexi y o he NEH dec eases om
O(n3m)
o
O(n2m)
.
This speed-up p ocedu e has been success ully adap ed o simila scheduling p oblems in ol ing
makespan minimisa ion (see e.g. Nade i and Ruiz, 2010, Fe nandez-Viagas and F aminan, 2015a,
Rios-Me cado and Ba d, 1998 and Fe nandez-Viagas and F aminan, 2015b), al hough i canno
be di ec ly applied o o he objec i es in he PFSP since i compu es he comple ion ime o he
las job in he las machine (i.e. makespan), bu no he comple ion ime o each job. Ne e -
heless, Li e al. (2009) ake ad an ages o he in a iance o he comple ion imes o jobs p io
o he inse ion posi ion o he PFSP o minimise ow ime,so sa ing be ween 30-50% o CPU
ime a e achie ed. A simila p ocedu e is also p oposed by Vallada and Ruiz (2010) o he
Fm|p mu|∑Tj
. This p ocedu e can be di ec ly applied o he p oblem unde conside a ion
and he e o e is in oduced in each inse ion mechanism o he algo i hms implemen ed in his
pape .
5

3 Analysis o he p oblem
The p oblem unde conside a ion can be s a ed as ollows:
n
jobs ha e o be scheduled in a
owshop composed o
m
machines. Each job
j
has a p ocessing ime on each machine deno ed
as
ij
, and a due da e
dj
. Gi en a sequence o jobs
Π := (π1, . . . πn)
, le us deno e
Cij(Π)
he
comple ion ime o job
j
on machine
i
acco ding o sequence
Π
. The comple ion ime o he las
job on he las machine,
Cm,πn(Π) = Cmax(Π)
, is deno ed as makespan o maximum comple ion
ime o he sequence. No e ha
Cij(Π)
can be ecu si ely calcula ed as ollows:
Cij(Π) = max{Ci−1,j(Π), Ci,j−1(Π)}+ ij
The a diness and ea liness o job
j
in sequence
Π
a e dened as
Tj(Π) = max{Cmj(Π)−dj,0}
and
Ej(Π) = max{dj−Cmj(Π),0}
espec i ely. Finally, he o al a diness (ea liness) is dened
as
∑Tj(Π) = ∑∀jmax{Cmj(Π) −dj,0}
(
∑Ej(Π) = ∑∀jmax{dj−Cmj(Π),0}
).
I is clea ha ex emely igh o loose due da es in one ins ance may lead o a die en
p oblems. Fo he p oblem unde s udy (
Fm|p mu|∑Ej+∑Tj
), his ac is e iden acco ding
o he ollowing wo p ope ies:
P ope y 3.1.
Le
I
be an ins ance o he
Fm|p mu|∑Ej+∑Tj
p oblem, and
WM
he wo s
(maximum) makespan o he ins ance. I
dj≥WM ∀j
, an op imal solu ion o
I
is ob ained by
sol ing he co esponding
Fm|p mu| − ∑Cj
p oblem o
I
.
P oo .
Since each due da e is g ea e o equal han he wo s makespan
WM
, hen each due da e
dj
is g ea e o equal han i s comple ion ime,
Cmj(Π)
(i.e.
dj≥WM ≥Cm,j(Π),∀j, Π
). Hence,
minimising
∑∀jmax{Cm,j(Π) −dj,0}+∑∀jmax{dj−Cm,j(Π),0}= 0 + ∑∀jdj−Cm,j(Π) =
∑∀jdj−∑∀jCm,j(Π) = cons −∑∀jCm,j(Π)
.
P ope y 3.2.
Le
I
be an ins ance o he
Fm|p mu|∑Ej+∑Tj
p oblem e i ying ha
dj≤
∑m
i=1 ij ∀j
. Then, an op imal solu ion o
I
can be ob ained by sol ing he co esponding
Fm|p mu|∑Cj
p oblem o
I
.
P oo .
Conside ing
dj≤ j∀j
, each comple ion ime
Cm,j(Π)
(
∀Π
) is g ea e o equal han i s
due da e,
dj
, since
j
is a lowe bound o he makespan o he job
j
. Hence
∑∀jmax{Cm,j(Π) −
6
dj,0}+∑∀jmax{dj−Cm,j(Π),0}=∑∀j(Cm,j(Π) −dj) + 0 = ∑∀jCm,j(Π) −∑∀jdj=
∑∀jCm,j(Π) + cons
.
F om hese p ope ies, i is clea ha ex emely loose due da es ans o m he p oblem in o a
PFSP wi h he obje i e o ow ime maximiza ion. Ex emely igh due da es lead o a p oblem
simila o he PFSP wi h ow ime minimisa ion. Bo h bounds ep esen opposi e objec i e
unc ions and he e o e, algo i hms specically ocused on yielding good solu ions o ins ances
wi h loose due da es would necessa ily pe o m bad o igh due da es. The eby, depending on
he due da es, h ee die en scheduling p oblems can be sol ed: he
Fm|p mu|∑Cj
p oblem in
case o igh due da es, he
Fm|p mu|−∑Cj
p oblem in case o loose due da es and he o iginal
Fm|p mu|∑Ej+∑Tj
p oblem in he es o he cases. This ac speaks o he dicul ies o
nd cons uc i e heu is ics ha pe o m well o he p oblem, which in ou opinion is eec ed
by he ac ha he NEH an algo i hm no designed o his specic p oblem is he only
cons uc i e heu is ic p oposed so a .
Typically, he good pe o mance o a cons uc i e heu is ic is due o he ac ha he objec i e
compu ed in he i e a ions o he algo i hm is simila o he objec i e unc ion o he p oblem.
The eby, when minimising e.g. o al ow ime in he PFSP, he choice o a pa ial sequence
ullling he minimisa ion o o al ow ime clea ly seems o ha e a good pe o mance when he
sequence is comple ed. This is a consequence o ha ing a egula measu e as objec i e. Since his
is no he case o ou p oblem, he algo i hm may no wo k well. In ac , he a o emen ioned
p ope ies con m his ac and show how he objec i e o he cons uc i e heu is ics in hei
i e a ions could be dis o ed: A pa ial sequence could ha e loose due da es bu , once comple ed,
hese due da es would become igh and hus, he algo i hm would sol e a comple ely die en
objec i e du ing i s i e a ions han he objec i e unc ion. This ac could also explain he
good pe o mance o composi e heu is ics as compa ed o cons uc i e heu is ics (as discussed in
Sec ion 5.5).
In o de o o e come he a o emen ioned p oblems, ecien heu is ics o he p oblem unde
conside a ion should be designed acco ding o he ollowing ideas:
•
They should be e y as in o de o wo k as soon as possible wi h comple e sequences. In
7
his manne , i is easie o iden i y whe he he ins ance has loose due da es, o igh ones.
•
They should inco po a e an analysis o bo h sequenced and non-sequenced jobs in each
i e a ion.
•
They should a oid he use o local sea ch p ocedu es ope a ing wi h non-comple e se-
quences.
Based on hese ideas and on he p ope ies discussed be o e, a numbe o algo i hms a e
p oposed. These a e discussed in he nex sec ion.
4 P oposed Algo i hms
Following he ecommenda ions in he p e ious sec ion ega ding e y as heu is ics and comple e
local sea ch me hods, ou heu is ics a e p oposed o he
Fm|p mu|∑Ej+∑Tj
p oblem:
•
an adap i e cons uc i e heu is ic (see Sec ion 4.1), deno ed as ACH1,
•
a composi e heu is ic (see Sec ion 4.2), deno ed as ACH2, composed by ACH1 plus a
bounded local sea ch p ocedu e labelled BLS,
•
a composi e heu is ic (see Sec ion 4.2), deno ed as ACH3, o med by ACH1 plus an i e a i e
bounded ela i e local sea ch me hod, iBRLS,
•
a composi e heu is ic (see Sec ion 4.2), deno ed as ACH4, o med by ACH1 and an i e a i e
local sea ch me hod, iLS.
Addi ionally, a speed-up p ocedu e is desc ibed in Sec ion 4.3 o accele a e he inse ion phases
o all implemen ed algo i hms.
4.1 P oposed Cons uc i e Heu is ic
ACH1 ies o nd a good solu ion using e y sho compu a ional imes so i can embedded
in mo e sophis ica ed cons uc i e and composi e heu is ics such as he ones p oposed in he
nex subsec ions. The p ocedu e o his heu is ic is ela i ely simple: Beginning wi h a pa ial
8
sequence wi h a single job, he p ocedu e cons uc s a nal sequence appending one by one jobs a
he end o he pa ial sequence acco ding o an index
ξujk (Π)
. Le us deno e by
Πk:= (π1, ..., πk)
he pa ial sequence in i e a ion
k
and by
Uk
he se o unsequenced jobs o ha sequence (
ujk
he
j
h unsequenced job wi h
j∈[1, n −k]
). Addi ionally, le
NTk
be he numbe o a dy jobs
in i e a ion
k
in
Uk
. The algo i hm chooses he job om
Uk
wi h he lowes alue o
ξujk (Πk)
and
places i a he end o sequence
Πk
, i.e. in posi ion
k+ 1
, o ming he sequence
Πk+1
o he nex
i e a ion. This p ocedu e has been shown o be e y ecien o o he decision p oblems, being
he app op ia e choice o he index he c i ical issue o he eciency o he algo i hm (see e.g.
Fe nandez-Viagas and F aminan, 2015c). This dicul y inc eases in ou case due o he s ong
dependence o he bes solu ions on he due da es o he jobs. The index mus be adap ed o sol e
die en p oblems depending on he due da es (loose due da es, igh ones, o nei he o hem).
In Sec ion 3, h ee die en si ua ions ha e been iden ied: igh due da es (
Fm|p mu|∑Cj
decision p oblem), loose due da es (
Fm|p mu| − ∑Cj
decision p oblem) and no mal due da es
(
Fm|p mu|∑Ej+∑Tj
). The e o e, a each i e a ion, he algo i hm would check whe he he
sequence is wi hin one o hese cases:
•
Case 1: Tigh due da es (i.e., he p oblem is simila o he
Fm|p mu|∑Cj
). The e
a e hund ed o heu is ics sol ing he
Fm|p mu|∑Cj
in he li e a u e. Pa icula ly,
Fe nandez-Viagas and F aminan (2015c) designed an ecien cons uc i e heu is ic ol-
lowing a simila p ocedu e o inse ion in las posi ion o he pa ial sequence. The e, jobs
a e chosen acco ding o he
ξ1
ujk (Πk)
index, Equa ion (1), which conside s he minimiza-
ion o he comple ion ime and he weigh ed idle ime o he candida es jobs (i.e.
uik
wi h
j∈[1, n −k]
) o be inse ed:
ξujk (Πk) = ξ1
ujk (Πk) = (n−k−2)
4·ITujk (Πk) + Cm,ujk (Πk)
(1)
whe e
ITj(Πk)
a e:
ITujk (Πk) =
m
∑
i=2
m·max{Ci−1,ujk (Πk)−Ci,πk(Πk),0}
i−1 + k·(m−i+ 1)/(n−2)
(2)
9
P ocedu e
ACH4()
(Π,∑Ej+∑Tj) = ACH1()
;
(Π,∑Ej+∑Tj) = iLS(Π,∑Ej+∑Tj)
;
end
Figu e 6: ACH4
P ocedu e
iLS
(
Π, OF
)
OFb=OF
lag :=
alse;
while
lag =
alse
do
lag :=
alse;
o
j= 1
o
n
do
Π0:=
emo e job
πj
om
Π
;
Tes job
πj
in each posi ion o
Π0
;
Π :=
pe mu a ion ob ained by inse ing
πj
in he posi ion
j
o
Π0
wi h less
o al ea liness and a diness,
OF′
;
i
OF′< OFb
hen
OFb=OF′
;
Πb:= Π
;
lag :=
ue;
end
end
end
e u n
Πb
and
OFb
;
end
Figu e 7: I e a i e Local Sea ch, iLS
heu is ic. This local sea ch me hod simply ies o place each job
πj
in he es o po-
si ions o he cu en sequence and has been ex ensi ely used in he li e a u e (see e.g.
Ruiz and S ü zle, 2007, Li and Wu, 2005 and Pan and Wang, 2012). The p ocedu e is e-
pea ed un il he e a e no mo e imp o emen s. Pseudo codes o ACH4 and iLS me hods
a e shown in Figu es 6 and 7.
4.3 Speed Up P ocedu e
In his Sec ion, a simple speed-up p ocedu e o accele a e he inse ion phases o he algo i hms
o he
Fm|p mu|∑Ej+∑Tj
p oblem is desc ibed. Le
Πk
be a pa ial sequence wi h
k
jobs
and
l
he job which is o be inse ed in posi ion
j∈[1, k + 1]
. Simila ly o he speed up me hods
p oposed by Li e al. (2009) and Vallada and Ruiz (2010), his me hod s o es he comple ion
16

ime o each job on each machine o he pa ial sequence
Πk
. When he job
l
is inse ed in each
posi ion
j
o he pa ial sequence, he comple ion imes o he jobs p io o his posi ion
j
a e
al eady known and do no ha e o be ecompu ed. Acco ding o se e al s udies, his p ocedu e
educes he CPU imes be ween 30% and 50% and is he e o e in oduced in each inse ion phase
o all algo i hms implemen ed in his pape .
5 Compu a ional Expe ience
In his pape , he p oposed algo i hms a e compa ed agains he mos ecien heu is ics in he
li e a u e. The p ocedu e adop ed o e alua e he algo i hms is he ollowing: Fi s , we in oduce
he se o ins ances used o bo h he expe imen al pa ame e uning and he compa ison among
heu is ics. In Sec ion 5.2, a ull ac o ial design o expe imen s is ca ied ou o nd he bes
alues o he pa ame e s o he algo i hms p oposed. The algo i hms unde compa ison a e lis ed
in Sec ion 5.3. The indica o s o dene he ecien heu is ics a e in oduced in Sec ion 5.4. Using
hese indica o s, cons uc i e and composi e heu is ics a e compa ed in Sec ion 5.5, leading o he
iden ica ion o he se o ecien heu is ics o he p oblem. Finally, in Sec ion 5.6, he ecien
heu is ics a e compa ed as seed sequences o one o he bes me aheu is ic o he p oblem.
5.1 Benchma k
In his Sec ion, he ollowing wo die en se s o ins ances a e p esen ed o e alua e he algo-
i hms. No e ha die en se s o ins ances a e used in o de o a oid an o e calib a ion o he
p oposed heu is ics when he pa ame e s
a
,
b
and
c
a e dened. These se s a e:
•
Benchma k
B1
o he calib a ion o he p oposed heu is ics. This benchma k is composed
o a se o 1,080 ins ances gene a ed acco ding o he p ocedu e by Vallada and Ruiz (2010).
The benchma k is o med by 10 ins ances o each combina ion o
n={50,150,250,350}
,
m={10,30,50}
,
T={0.2,0.4,0.6}
and
R={0.2,0.6,1.0}
, whe e
T
and
R
a e pa ame e s
ela ed o he mean and s anda d de ia ion o he due da es espec i ely. These due da es
a e gene a ed using he p ocedu e desc ibed by Po s and Van Wassenho e (1982), i.e.
ollowing a uni o m dis ibu ion be ween
P·(1 −T−R/2)
and
P·(1 −T+R/2)
, whe e
17
P
is a lowe bound o he makespan. P ocessing imes a e gene a ed using a uni o m
dis ibu ion [1, 99].
•
Benchma k
B2
o compa ison among he implemen ed heu is ics. This benchma k is com-
posed o a se o 540 ins ances o Vallada e al. (2008) (a ailable in h p://soa.i i.es) and
is he mos ex ended benchma k o he PFSP wi h due da es. This benchma k con-
sis s o  e ins ances o each combina ion o
n={50,150,250,350}
,
m={10,30,50}
,
T={0.2,0.4,0.6}
and
R={0.2,0.6,1.0}
. P ocessing imes a e gene a ed using a [1,99]
uni o m dis ibu ion.
5.2 Expe imen al Pa ame e Tuning
The p oposed heu is ic ACH1 uses h ee pa ame e s:
a
,
b
and
c
. In his sec ion, a ull ac o ial
design o expe imen s is ca ied ou o de e mine hei bes alues on he se o ins ances
B1
.
The ollowing alues a e chosen o he expe imen s:
•a={0.8,0.85,0.9,0.95,1}
,
•b={0.4,0.45,0.5,0.55,0.6}
,
•c={25,30,35,40,45,50,55}
In each ins ance, he ACH1 heu is ic is e alua ed acco ding o Equa ion (7):
RPD1 = OF −Base
Base ·100
(7)
whe e
OF
and
Base
a e he solu ions ob ained by he ACH1 heu is ic and a e e ence algo i hm
(NEHedd) espec i ely.
Since no mali y and homoscedas ici y assump ions a e no ullled, a non-pa ame ic K uskal-
Wallis es is ca ied ou . The
p
- alues a e 0.267, 0.865 and 0.000 o pa ame e s
a
,
b
and
c
espec i ely. Resul s show ha he e is s a is ically signican die ences only be ween he le els
o pa ame e
c
. Addi ionally, among he 175 combina ions o
a
,
b
and
c
, he bes esul s a e
ound o
a= 0.90
,
b= 0.55
and
c= 30
. These alues a e subsequen ly used in each heu is ic
which inco po a es he ACH1, i.e. ACH2, ACH3 and ACH4.
18
5.3 Implemen ed algo i hms
The pe o mance o he p oposed heu is ics is es ed agains he mos ecien heu is ics o he
p oblem, as well as o some o he mos ecien heu is ics o simila scheduling p oblems. Mo e
specically, due o hei excellen pe o mance (see compu a ional e alua ions by Pan and Ruiz,
2013 and Rad e al., 2009), he ollowing heu is ics a e conside ed:
•
NEHedd
o
: NEHedd
o
is he NEHedd heu is ic p oposed by Kim (1993) o
Fm|p mu|∑Tj
.
The speed up p ocedu e desc ibed in Sec ion 4.3 is no applied o main ain i s o iginal e -
sion.
•
NEHedd
e
: Heu is ic NEHedd
o
using he speed up p ocedu e in Sec ion 4.3. Addi ionally,
he e alua ion o o al a diness in each i e a ion is eplaced by he e alua ion o he sum
o o al ea liness and a diness.
•
Raj: Adap a ion o he Raj heu is ic by Rajend an (1993), o iginally p oposed o he
Fm|p mu|∑Cj
p oblem. To adap he heu is ic o ou p oblem, he speed up p ocedu e
in Sec ion 4.3 is applied, and he o iginal e alua ion o o al ow ime is eplaced by he
e alua ion o o al ea liness and a diness. Addi ionally, he o iginal ini ial o de is eplaced
by he EDD ule.
•
RZ: Adap a ion o he RZ heu is ic by Rajend an and Ziegle (1997) p oposed o he
Fm|p mu|∑Cj
p oblem, wi h he ini ial o de eplaced by he EDD ule. The speed up
p ocedu e is applied, and he e alua ion o o al ow ime is eplaced by he e alua ion o
o al ea liness and a diness.
•
RZ_LW: Adap a ion o he RZ_LW heu is ic by Rajend an and Ziegle (1997), o iginally
p oposed o he
Fm|p mu|∑Cj
p oblem. The speed up p ocedu e is applied and he
e alua ion o o al ow ime is eplaced by he e alua ion o o al ea liness and a diness.
Fu he mo e, he EDD ule is used as ini ial o de .
•
FRB4
k
: Adap a ion o he FRB4
k
heu is ic by Rad e al. (2009), o iginally p oposed o he
Fm|p mu|Cmax
p oblem. The e alua ion o he makespan is eplaced by he e alua ion o
19
he o al ea liness and a diness, and he speed up p ocedu e by Tailla d (1990) is eplaced
by he p oposed one. As in he NEHedd
e
, he o iginal o de is eplaced by he EDD ule.
All heu is ics a e ully ecoded o he
Fm|p mu|∑Ej+∑Tj
p oblem unde he same
compu e condi ions, which means:
•
Unde he same compu e (an In el Co e i7-3770 wi h 3.4 GHz and 16 GB RAM).
•
Using he same p og amming language (algo i hms ha e been coded in C#).
•
Using he same lib a ies and common unc ions.
5.4 Indica o s o e alua e he heu is ics
Since each heu is ic equi es die en CPU ime, hei compa ison is no s aigh o wa d, as he e
is a ade-o be ween he quali y o he solu ions (usually measu ed by means o he A e age
Rela i e Pe cen age De ia ion
ARPD
) and he compu a ional eo equi ed (usually measu ed
using he A e age Compu a ional Eo
ACT
). These indica o s a e dened as ollows:
ACTi=∑∀jTi,j
J
(8)
ARPDi=∑∀jRP D2i,j
J
(9)
wi h
Ti,j
he a e age compu a ional ime (in seconds) equi ed by heu is ic
i
in ins ance
j
among 5 independen uns,
J
is he numbe o ins ances, and
ARPDi
is he a e age
RPD2i,j
o
heu is ic
i
o e all ins ances, which is dened by Exp ession (10):
RPD2i,j =OFi,j −Bes Cons j
Bes Cons j
·100
(10)
wi h
OFi,j
he o al ea liness and a diness o heu is ic
i
in ins ance
j
and
Bes Cons j
is he
bes alue ound among he implemen ed cons uc i e heu is ics (see bounds in online ma e ials).
The use o bo h indica o s o compa e heu is ics is e y ex ended in he li e a u e. Howe e , a
di ec compa ison be ween bo h indica o s p esen s se e al p oblems ela ed o he weigh o each
p oblem size, as shown by Fe nandez-Viagas and F aminan (2015c). To a oid hem, in addi ion
20
o epo he esul s in e ms o
ACT
, we also use he a e age ela i e pe cen age ime,
ARPTi
indica o o heu is ic
i
, dened by (11) (no e ha 1 is added o he quo ien o a oid nega i e
numbe s).
ARPTi=∑∀jRP Ti,j
J+ 1
(11)
wi h
RPTi,j
he ela i e pe cen age ime o heu is ic
i
in ins ance
j
, dened by Equa ion
(12).
RPTi,j =Ti,j −ACTj
ACTj
(12)
In he ollowing, we assume ha one heu is ic ou pe o ms ano he in an ins ance i bo h hei
RPD
and
RPT
a e lowe . A heu is ic
e
is hus deno ed
ecien o an ins ance
i i ou pe o ms
he es o heu is ics in his ins ance. Simila ly, one heu is ic is labelled
ecien
is he e is no
o he heu is ic wi h lowe alues o bo h
ARPD
and
ARPT
measu ed o e a ull es bed. The
se o ecien heu is ics is deno ed as
A
.
5.5 Ecien se o heu is ics
In his sec ion, all implemen ed heu is ics a e compa ed using benchma k
B2
. A e age esul s
in e ms o
ARPD
a e shown in Table 2 o each combina ion o
n
and
m
, and in Table 4 o
each alue o he pa ame e s. The CPU ime equi ed by each heu is ic is shown in Table 3 o
each
n
and
m
. The las wo ows show he
ACT
and he
ARPT
o each heu is ic. A summa y
o he esul s is g aphically shown in Figu e 8 using
ACT
o e alua e he compu a ional eo ,
while
ARPT
is used as indica o in Figu e 9. In iew o he esul s, he NEHedd
e
heu is ic
clea ly ou pe o ms he NEHedd
o
in e ms o quali y o he solu ion and compu a ional eo .
The bes
ARPDs
a e clea ly ound by he p oposed heu is ic ACH4 (1.19), and by he RZ_LW
heu is ic (2.40). Rega ding heu is ics adap ed om o he p oblems, he bes esul s a e ound
by Raj, RZ and RZ_LW, which a e ei he e y as heu is ics, o local sea ch me hods (using
dispa ching ules as seed sequences). The good pe o mance achie ed by he composi e heu is ics
RZ, RZ_LW, ACH2, ACH3, and ACH4 con ms he conclusions ob ained a e he analysis o
he p oblem in Sec ion 3 which ad oca ed o as heu is ics employing as soon as possible local
21

sea ch me hods o ull sequences. This ac is also con med by he pe o mance o he amily o
heu is ics FRB4
k
. Each o hese heu is ics is ou pe o med in e ms o quali y o he solu ions
and compu a ional eo by RZ and ACH3. Acco ding o Figu e 9, he ecien heu is ics (se
A
)
a e: ACH1, Raj, NEHedd
e
, ACH2, RZ, ACH3 and ACH4. To s a is ically jus i y his s a emen ,
we pe o m a Holm's p ocedu e (Holm, 1979) wi h he ollowing hypo heses:
•
H
1
: ACH2 = NEHedd
o
.
•
H
2
: RZ = FRB4
2
.
•
H
3
: RZ = FRB4
4
.
•
H
4
: RZ = FRB4
6
.
•
H
5
: ACH3 = FRB4
8
.
•
H
6
: ACH3 = FRB4
10
.
•
H
7
: ACH3 = FRB4
12
.
•
H
8
: ACH4 = RZ_LW.
Resul s a e shown in Table 5, whe e he
p
- alues ha e been calcula ed using a non-pa ame ic
Mann-Whi ney es since he no mali y and homoscedas ici y assump ions we e no con med
(see e.g. Pan e al., 2008). Assuming a condence o 0.95, only wo hypo heses (H2 and H3) a e
no ejec ed and he p oposed heu is ics (ACH2, ACH3 and ACH4) can be he e o e conside ed
as s a is ically ecien . The heu is ics o he se s
A
a e shown in Figu e 9.
22
Ins ance Raj NEHedd
e
NEHedd
o
RZ FRB4
2
FRB4
4
FRB4
6
FRB4
8
FRB4
10
FRB4
12
RZ_LW ACH1 ACH2 ACH3 ACH4
50x10 26.52 22.38 44.23 13.53 14.16 11.62 10.00 9.91 8.79 8.07 2.53 30.15 13.65 8.74 1.41
50x30 20.61 14.20 12.27 10.55 7.86 6.22 5.39 4.56 4.41 4.14 2.59 18.33 9.31 6.11 1.81
50x50 15.06 7.94 6.89 8.03 4.54 3.68 2.85 2.84 1.76 1.60 2.11 11.49 5.95 4.00 1.40
150x10 41.36 37.56 66.72 14.39 25.56 24.13 23.19 21.88 21.59 19.33 1.69 46.12 18.06 9.83 1.65
150x30 31.16 25.09 39.50 14.76 15.89 15.07 14.15 13.07 11.49 11.04 2.53 37.47 15.88 7.40 1.19
150x50 30.61 24.40 25.86 14.93 18.92 17.11 16.36 14.73 14.02 13.10 3.18 33.14 14.33 5.23 0.44
250x10 36.04 29.13 76.55 13.94 22.63 20.62 19.42 18.69 17.61 17.25 2.31 50.20 13.88 7.85 1.09
250x30 40.84 35.95 57.49 15.95 24.08 23.16 21.62 21.04 20.13 18.94 2.50 45.28 19.56 8.96 1.14
250x50 32.37 26.65 39.12 15.29 17.54 16.23 15.34 15.13 13.28 11.87 2.69 37.35 16.44 5.99 1.29
350x10 38.57 30.75 77.89 13.37 23.70 23.05 22.46 20.94 20.71 20.09 1.41 56.46 14.83 8.76 0.82
350x30 48.71 41.83 66.24 18.72 32.40 29.66 28.60 27.43 26.10 26.66 2.83 51.33 22.34 9.05 1.02
350x50 32.56 26.18 47.91 13.49 18.94 16.45 16.34 15.17 15.51 13.08 2.44 39.64 17.25 7.44 0.98
A e age 32.87 26.84 46.72 13.91 18.85 17.25 16.31 15.45 14.61 13.76 2.40 38.08 15.12 7.45 1.19
Table 2: Rela i e Pe cen age De ia ion (
RPD
) o he implemen ed heu is ics unde he se o ins ances o Vallada e al. (2008)
Ins ance Raj NEHedd
e
NEHedd
o
RZ FRB4
2
FRB4
4
FRB4
6
FRB4
8
FRB4
10
FRB4
12
RZ_LW ACH1 ACH2 ACH3 ACH4
50x10 0.00 0.00 0.00 0.01 0.02 0.02 0.02 0.03 0.03 0.04 0.03 0.00 0.00 0.02 0.03
50x30 0.00 0.01 0.01 0.02 0.04 0.05 0.07 0.09 0.10 0.11 0.09 0.00 0.01 0.06 0.08
50x50 0.00 0.01 0.02 0.03 0.06 0.09 0.11 0.14 0.16 0.19 0.17 0.00 0.02 0.08 0.13
150x10 0.01 0.06 0.10 0.13 0.26 0.41 0.55 0.68 0.80 0.91 0.98 0.00 0.09 0.56 0.95
150x30 0.04 0.16 0.35 0.41 0.82 1.30 1.75 2.17 2.56 2.92 3.42 0.01 0.28 1.74 3.20
150x50 0.07 0.26 0.61 0.72 1.44 2.31 3.12 3.89 4.58 5.26 5.84 0.02 0.49 2.64 5.27
250x10 0.06 0.21 0.46 0.56 1.12 1.81 2.47 3.09 3.68 4.24 4.93 0.01 0.38 2.84 4.73
250x30 0.18 0.64 1.60 1.82 3.67 5.92 8.00 9.93 11.80 13.58 19.33 0.03 1.25 10.24 18.88
250x50 0.31 1.13 2.80 3.24 6.50 10.50 14.22 17.74 21.06 24.30 33.00 0.06 2.21 18.64 32.80
350x10 0.15 0.53 1.24 1.52 3.02 4.91 6.72 8.46 10.12 11.73 14.74 0.02 1.03 8.88 14.33
350x30 0.46 1.69 4.30 4.88 9.90 16.15 21.96 27.51 32.70 37.91 55.90 0.06 3.33 31.85 61.23
350x50 0.81 2.98 7.54 8.60 17.37 28.02 38.17 47.65 57.07 65.66 95.51 0.09 5.88 55.56 96.84
ACT
0.17 0.64 1.59 1.83 3.68 5.96 8.10 10.12 12.06 13.90 19.49 0.03 1.25 11.09 19.87
ARP T
0.03 0.11 0.24 0.30 0.61 0.96 1.27 1.57 1.85 2.12 2.43 0.01 0.21 1.33 2.32
Table 3: A e age Compu a ional Eo (
ACT
) (in seconds) and A e age Rela i e Pe cen age Time (
ARPT
) o he implemen ed
heu is ics unde he se o ins ances o Vallada e al. (2008)
23
Pa ame e Raj NEHedd
e
NEHedd
o
RZ FRB4
2
FRB4
4
FRB4
6
FRB4
8
FRB4
10
FRB4
12
RZ_LW ACH1 ACH2 ACH3 ACH4
T
0.2 49.71 38.62 92.83 16.45 28.60 26.05 24.71 23.59 21.92 19.90 1.60 65.76 25.09 13.01 2.49
T
0.4 31.61 29.44 36.71 15.93 20.61 19.15 18.10 17.18 16.76 16.40 2.72 36.04 14.30 6.15 0.71
T
0.6 17.28 12.46 10.63 9.36 7.34 6.55 6.12 5.58 5.16 5.00 2.88 12.44 5.98 3.19 0.36
R
0.2 18.40 16.25 21.39 9.35 11.14 10.06 9.60 9.31 8.95 8.83 2.31 22.21 8.93 5.05 0.43
R
0.6 24.85 18.31 35.67 12.50 12.01 11.05 10.27 10.02 9.63 9.26 2.59 28.50 11.52 6.62 0.86
R
1 55.35 45.95 83.11 19.89 33.40 30.64 29.07 27.02 25.27 23.20 2.30 63.53 24.92 10.68 2.27
n
50 20.73 14.84 21.13 10.70 8.85 7.17 6.08 5.77 4.98 4.60 2.41 19.99 9.64 6.28 1.54
n
150 34.38 29.02 44.03 14.69 20.12 18.77 17.90 16.56 15.70 14.49 2.47 38.91 16.09 7.49 1.09
n
250 36.42 30.57 57.72 15.06 21.42 20.00 18.79 18.29 17.00 16.02 2.50 44.28 16.63 7.60 1.17
n
350 39.95 32.92 64.01 15.19 25.01 23.05 22.47 21.18 20.77 19.94 2.23 49.14 18.14 8.42 0.94
m
10 35.62 29.95 66.34 13.81 21.51 19.85 18.77 17.85 17.17 16.19 1.99 45.73 15.11 8.80 1.24
m
30 35.33 29.26 43.88 15.00 20.06 18.53 17.44 16.52 15.53 15.20 2.61 38.10 16.77 7.88 1.29
m
50 27.65 21.29 29.95 12.93 14.99 13.37 12.72 11.97 11.14 9.91 2.60 30.40 13.49 5.67 1.03
Table 4: A e age ela i e pe cen age de ia ion (
ARPD
) o each heu is ic g ouped by he alues o he pa ame e s
24
Figu e 8:
ARPD
s
ACT
o implemen ed heu is ics. X-axis (
ACT
in seconds) is shown
loga i hmic scale.
5.6 Compa ison among ecien heu is ics
As he e is a ade-o be ween quali y o he solu ion and compu a ional eo , heu is ics in se
A
canno be di ec ly compa ed in e ms o
ARPD
due o hei die en compu a ional eo s.
In his Sec ion, hey a e included as ini ial solu ion o one o he bes me aheu is ic o his
p oblem, i.e. he ILS by M'Hallah (2014), eplacing he o iginal seed sequence o he me aheu is ic
(EDD ule). Thus, he me aheu is ic is un using eigh die en ini ial sequences (EDD ule and
each heu is ic in se
A
) whe e he EDD ule is included in he compa ison as i is he o iginal
seed sequence o he me aheu is ic. Each a ia ion o he me aheu is ic is un unde he same
compu a ional condi ions desc ibed in Sec ion 5.3 using he benchma k in Sec ion 5.1. In his
case,  e uns a e pe o med pe ins ance and he a e age alues a e eco ded. The a ia ions
o he ILS a e s opped depending on he size o he p oblem acco ding o exp ession
n·m· /2
(milliseconds) whe e
= 5,10,15,20,25,30
(see e.g. Ruiz and S ü zle, 2007 o a simila s opping
c i e ion). Ob iously, he CPU ime equi ed by each heu is ic is included in he CPU ime o he
me aheu is ic, i.e. he clock s a s be o e applying he heu is ic. Resul s o he ILS me aheu is ic
using die en heu is ics as ini ial solu ion a e shown in e ms o
ARPD
in Table 6. No e ha
25