E icien epai s o in easible job shop p oblems by
e olu iona y algo i hms
Ra´
ul Menc´
ıaa,∗, Ca los Menc´
ıaa, Rami o Va elaa
aDepa men o Compu e Science, Uni e si y o O iedo, Spain
Abs ac
We add ess he ask o epai ing in easibili y in he con ex o in easible job shop
scheduling p oblems wi h a ha d cons ain on he maximum makespan allowed. Fo
his pu pose, we adop a job-based iew o epai s, ha allows o d opping some o he
jobs and so gi es ise o he p oblem o compu ing he la ges subse o jobs ha can be
scheduled unde he makespan cons ain . Recen wo k p oposed a gene ic algo i hm
o sol ing his p oblem, which in eg a es an e icien solu ion builde o de ining he
sea ch space. In his pape , we build on his ea lie wo k and make se e al con ibu-
ions. We p o ide a o mal analysis o bo h he sea ch space and he solu ion builde .
Then, we p opose wo impo an enhancemen s o he gene ic algo i hm: i s , we de-
elop a new solu ion builde aimed a educing he numbe o easibili y es s, making
he sea ch p ocess mo e e icien . In addi ion, we p opose a mo e e ec i e p ocedu e
o es ing he easibili y o di e en subse s o jobs unde he gi en makespan con-
s ain based on he use o a ligh -weigh gene ic algo i hm. Expe imen al esul s show
ha he p oposed me hods a e e ec i e a sol ing he p oblem, and ha he enhance-
men s b ing signi ican imp o emen s.
Keywo ds: Job Shop Scheduling, In easibili y, Repai s, E olu iona y Algo i hms,
Solu ion Builde s
1. In oduc ion
Scheduling p oblems a ise p o usely in a wide ange o a eas, especially in man-
u ac u ing and enginee ing, whe e a p ope o ganiza ion o limi ed esou ces is usu-
ally necessa y. In addi ion, hese p oblems a e o en compu a ionally in ac able, wha
makes hem a na u al applica ion domain o ad anced a i icial in elligence and ope a-
ions esea ch me hods. As a consequence, scheduling p oblems ha e been ho oughly
s udied in he li e a u e o e he las decades, gi ing ise o a la ge body o sol ing
app oaches, bo h exac and app oxima e, e.g. (B ucke e al., 1994; Nowicki and Smu -
nicki, 2005; Beck, 2007; Zhang e al., 2008; Menc´
ıa e al., 2015; Peng e al., 2015;
Deng e al., 2020).
∗Co esponding au ho
Email add ess:
P ep in submi ed o Enginee ing Applica ions o A i icial In elligence June 26, 2021
Scheduling p oblems usually equi e compu ing schedules ha op imize a gi en
objec i e unc ion. Howe e , in some se ings he e can be cons ain s ha make he
p oblem in easible, i.e., wi h no possible solu ion wha soe e . Such scena io may ap-
pea when, o ins ance, conside ing a ha d cons ain ha imposes a limi on he max-
imum makespan allowed, en o cing all he jobs in he p oblem o be scheduled (and
comple ed) by a gi en ime limi . This kind o cons ain is na u al in p ac ice, and
in easibili y may easily a ise unde his cons ain i he gi en scheduling ho izon is
oo igh . Fu he mo e, a numbe o scheduling p oblems wi h a cons ain on he
makespan ha e been s udied in he pas , e.g. (Dawande e al., 2006; Allah e di and
Aydilek, 2014; Guyon e al., 2014; Choi, 2015)). In his con ex , beyond de ec ing in-
easibili y, use s may be in e es ed in iden i ying i s causes, o in inding possible ways
o epai ing i , so ha being able o sol e he p oblem o some ex en .
In his pape , we add ess he ask o epai ing in easible job shop scheduling p ob-
lems wi h a ha d cons ain on he makespan. Fo his pu pose, we adop a job-based
iew o epai s, which enables d opping some o he jobs so ha he emaining ones can
be scheduled wi hin he makespan cons ain . This iew was ecen ly aken in (Menc´
ıa
e al., 2019), gi ing ise o di e en no ions o epai s, such as easible subse s o jobs
(FSJs), se -wise maximal easible subse s o jobs (MFSJs) and easible subse s o jobs
o maximum ca dinali y (maxFSJs), i.e., easible subse s o jobs wi h he g ea es pos-
sible numbe o jobs. These concep s a e inspi ed in analogous no ions in he analysis
o inconsis ency in logic, whe e epai ing (o co ec ing) inconsis en o mulas has
been widely in es iga ed (Ma ques-Sil a and Menc´
ıa, 2020). In addi ion, Menc´
ıa e al.
(2019) p elimina ily add essed he p oblem o app oxima ing maxFSJs, by means o a
gene ic algo i hm. This algo i hm looks o solu ions in he sea ch space o (app ox-
ima ions o ) MFSJs, de ined by a solu ion builde used in i s decoding phase. The
gene ic algo i hm was ecen ly adap ed o a weigh ed e sion o he p oblem and com-
bined wi h a local sea ch algo i hm speci ically ailo ed o he case ha jobs ha e di -
e en weigh s (Menc´
ıa e al., 2020).
We ocus on he p oblem o app oxima ing maxFSJs, ha is, compu ing he la ges
subse s o jobs ha can be scheduled unde he ha d makespan cons ain . Building
on (Menc´
ıa e al., 2019), we make se e al con ibu ions:
•We i s p o ide a o mal analysis o he sea ch space o MFSJs and he solu ion
builde , p o ing ele an p ope ies.
•The analysis gi es ise o impo an enhancemen s o he gene ic algo i hm. In
his espec , we p opose a new solu ion builde ha de ines he same sea ch space
bu in a mo e e icien way. By in eg a ing a bina y sea ch phase, i aims a e-
ducing he numbe o easibili y es s needed o compu e a solu ion, wha allows
o sa ing ime.
•Fu he mo e, we p opose a new (incomple e) p ocedu e o es ing he easibili y
o di e en subse s o he jobs (i.e. deciding whe he hese can be scheduled
wi hin he gi en makespan limi ), which is i e a i ely in oked by he solu ion
builde s. Whe eas ea lie wo k used a g eedy algo i hm o his pu pose, he new
p ocedu e in eg a es a ligh -weigh gene ic algo i hm which is mo e e ec i e,
leading o be e esul s.
2
We conduc ed an ex ensi e expe imen al s udy o e alua e he p oposed algo i hms
o e a la ge se o ins ances wi h di e en sizes and cha ac e is ics. The expe imen al
esul s e eal ha gene ic algo i hms a e success ul a sol ing he p oblem and con i m
ha he new me hods b ing signi ican imp o emen s in p ac ice.
The emainde o he pape is s uc u ed as ollows: Sec ion 2 in oduces he nec-
essa y backg ound and no a ion, including he de ini ion o he p oblem. Sec ion 3
e iews ela ed wo k. Sec ion 4 p esen s a o mal analysis o he sea ch space and he
solu ion builde om (Menc´
ıa e al., 2019), and desc ibes he new solu ion builde ha
exploi s bina y sea ch. The main componen s o he gene ic algo i hm a e p esen ed
in Sec ion 5. The new p ocedu e o es ing he easibili y o a gi en subse o jobs
is desc ibed in Sec ion 6. Sec ion 7 is de o ed o he expe imen al s udy. Finally, we
summa ize he main conclusions and ou line ideas o u u e esea ch in Sec ion 8.
2. P elimina ies
In he classical job shop scheduling p oblem (JSP) we a e gi en a se o njobs
J={J1, . . . , Jn} ha mus be scheduled on a se o m esou ces o machines
M={M1, . . . , Mm}. Job Ji∈ J consis s o a sequence o m asks o op-
e a ions (θi1, . . . , θim), and each o i s ope a ions θij equi es a pa icula machine
M(θij)∈ M du ing a (posi i e in ege ) p ocessing ime pθij . Besides, wi hou loss
o gene ali y, i is commonly assumed ha any wo ope a ions o he same job equi e
di e en machines.
A schedule Sis an alloca ion o a s a ing ime s θij o each ope a ion sa is ying
he ollowing cons ain s:
i. Conjunc i e cons ain s. Ope a ions mus be scheduled in he o de hey appea
in hei job, i.e., s θij +pθij ≤s θi(j+1) o all i= 1, ..., n and j= 1, ..., m −1.
ii. Disjunc i e cons ain s. Machines canno p ocess mo e han one ope a ion a a
ime, ha is, (s u+pu≤s )∨(s +p ≤s u) o all ope a ions u, wi h
u6= and M(u) = M( ).
iii. Non-p eemp ion. The p ocessing o ope a ions canno be in e up ed, i.e., Cu=
s u+pu o e e y ope a ion u, whe e Cudeno es he comple ion ime o u.
The quali y o a schedule can be e alua ed wi h espec o se e al di e en me -
ics (B ucke and Knus , 2006), such as he makespan, o al low ime o a diness and
la eness measu es (when due da es a e conside ed), o name a ew. In his wo k, we
ocus on he makespan: gi en schedule S, i s makespan is de ined as he maximum
comple ion ime o he ope a ions in S, and i is deno ed Cmax(S).
This me ic gi es ise o one o mos s udied op imiza ion e sions o he JSP,
deno ed J||Cmax in he s anda d α|β|γno a ion (G aham e al., 1979)), which equi es
compu ing a schedule wi h he minimum possible makespan.
Taking he makespan in o accoun , he decision e sion o he JSP equi es de e -
mining whe he he e exis s a schedule Ssuch ha Cmax(S)≤C, whe e Cis a ixed
limi on he maximum makespan allowed. I such a schedule Sexis s, we call he p ob-
lem ins ance easible, whe eas in easible o he wise. The JSP, in i s decision e sion, is
well-known o be NP-comple e (Ga ey e al., 1976).
3
This pape ocuses on in easible p oblem ins ances due o a ha d cons ain on he
makespan and, mo e speci ically, on he ask o epai ing in easibili y in he bes pos-
sible manne . To his aim, we adop a job-based iew o epai s, ha enables elaxing
he p oblem by d opping some o he jobs in a way ha he emaining ones can be
scheduled wi hin he makespan limi imposed by he ha d cons ain . Th oughou , we
will e e o such an in easible ins ance by a pai I= (J, C), equi ing scheduling he
se o jobs Jwi hou exceeding he maximum makespan C.
In his se ing, he ollowing de ini ions se e o cha ac e ize di e en no ions o
epai s (Menc´
ıa e al., 2019):
De ini ion 1. (FSJ) Gi en an in easible ins ance I= (J, C),S(Jis a easible
subse o jobs (FSJ) o Ji and only i (S, C)is easible.
An FSJ is a subse o jobs ha can be scheduled unde he makespan cons ain .
Thus, i ep esen s a possible way o epai ing in easibili y. Howe e , an a bi a y FSJ
may lea e ou a numbe o jobs unnecessa ily, and so conside ing some maximali y
c i e ia would be bene icial.
De ini ion 2. (MFSJ) Gi en an in easible ins ance I= (J, C),S(Jis a maximal
easible subse o jobs (MFSJ) o Ji and only i (S, C)is easible and o all S0⊆ J
wi h S(S0, (S0, C) is in easible.
De ini ion 3. (maxFSJ) Gi en an in easible ins ance I= (J, C),S∗(Jis a
maximum easible subse o jobs (maxFSJ) i and only i (S∗, C)is easible and o all
FSJs S0o J,|S0| ≤ |S∗|.
MFSJs and maxMFSJs exhibi di e en o ms o maximali y. On he one hand,
MFSJs a e maximal wi h espec o se inclusion, ha is, no supe se o an MFSJ is
an FSJ. On he o he hand, maxFSJs a e maximal wi h espec o se ca dinali y, i.e.,
maxFSJs a e he la ges possible FSJs. As we will see in he ollowing sec ion, maxF-
SJs a e MFSJs as well, bu he opposi e does no always hold ue. A guably, MFSJs
ep esen a kind o local op ima wi h espec o app oxima ing maxFSJs, since hese
canno be ex ended wi h any jobs wi hou losing easibili y.
These de ini ions build on ela ed concep s in he analysis o inconsis en p oposi-
ional o mulas, such as maximal sa is iable sub o mulas (MSSes) o maximum sa is ia-
bili y (maxSAT), ep esen ing analogous concep s o MFSJs and maxFSJs espec i ely
(see (Ma ques-Sil a and Menc´
ıa, 2020) o a ecen su ey).
The ollowing example (Menc´
ıa e al., 2019) illus a es all he de ini ions:
Example 1. Le us conside a job shop wi h jobs J={J1, J2, J3, J4}and machines
M={M1, M2}. Each job Jiconsis s o a sequence o wo ope a ions (θi1, θi2),
wi h p ocessing imes and machine equi emen s as indica ed in Table 1 (e.g., job J1
consis s o he sequence o ope a ions (θ11, θ12);θ11 equi es machine M1du ing 2
ime uni s, and θ12 equi es machine M2du ing 3 ime uni s, ...).
I we conside a ha d cons ain limi ing he makespan o a mos C= 10 he
ins ance (J, C)is in easible. The e a e 11 FSJs o J:∅,{J1},{J2},{J3},{J4},
{J1, J2},{J1, J3},{J1, J4},{J2, J3},{J2, J4}and {J1, J2, J4}as he e exis s a
schedule wi h makespan less han o equal o 10 o each o hem. Ou o hese
4
Table 1: Ins ance da a.
J1J2J3J4
θi12 (M1) 3 (M1) 6 (M2) 5 (M2)
θi23 (M2) 2 (M2) 4 (M1) 5 (M1)
J1θ11, M1θ12, M2
J2θ21, M1θ22, M2
J4θ41, M2θ42, M1
12345678910
Figu e 1: Gan cha o a schedule o he maxFSJ {J1, J2, J4}in Example 1.
se s, h ee a e MFSJs: {J1, J3},{J2, J3}and {J1, J2, J4}; and only he las one is
a maxFSJ, wi h 3 jobs. Figu e 1 shows a schedule o he maxFSJ wi h makespan 10,
which does no exceed he limi C.
Wi h he de ini ions abo e, compu ing maxFSJs may be seen as he bes way o
epai ing in easibili y, due o hei maximum size. Hence, in his pape we add ess
he maximiza ion p oblem o app oxima ing maxFSJs o a gi en in easible ins ance
(J, C), ha is inding easible subse s o jobs wi h maximum ca dinali y.
Table 2 summa izes he main no a ion and e minology in oduced in his sec ion.
I will be used h oughou he pape .
Table 2: Main no a ion and e minology.
No a ion De ini ion
JSP Job shop scheduling p oblem
MSe o machines
Mii- h machine
JSe o jobs
Jii- h job
θij j- h ope a ion o job Ji
s θij S a ing ime o ope a ion θij
pθij P ocessing ime o ope a ion θij
CuComple ion ime o ope a ion u
Cmax(S)Makespan o schedule S
CMaximum makespan
(J, C)P oblem ins ance, wi h jobs Jand maximum makespan C
FSJ Feasible subse o jobs
MFSJ Maximal easible subse o jobs
maxFSJ Maximum easible subse o jobs
5

3. Rela ed wo k
The p oblem s udied in his pape was i s add essed in (Menc´
ıa e al., 2019). In
his p e ious wo k, he no ions o MFSJ and maxFSJ we e p oposed as a means o
epai ing in easibili y in he con ex o job shop scheduling p oblems wi h a ha d con-
s ain on he makespan. These de ini ions a e based on concep s commonly used in
he ield o Boolean sa is iabili y in he analysis o unsa is iable p oposi ional o mu-
las. Fo app oxima ing maxFSJs, Menc´
ıa e al. (2019) p oposed a gene ic algo i hm
ha looks o solu ions in he space o (app oxima ions o ) MFSJs. To his aim, i in e-
g a es a solu ion builde based on a linea sea ch app oach (Bailey and S uckey, 2005;
Ma ques-Sil a e al., 2013) and uses a g eedy algo i hm (Gi le and Thompson, 1960)
as an incomple e p ocedu e o es he easibili y o subse s o jobs. To ou knowledge,
his gene ic algo i hm is he cu en bes pe o ming app oach o sol ing he p oblem.
This algo i hm was la e adap ed o handle a weigh ed e sion o he p oblem and com-
bined wi h a local sea ch app oach (Menc´
ıa e al., 2020). The local sea ch app oach
is only applicable when jobs ha e di e en weigh s, so i canno b ing any bene i s o
he unweigh ed e sion o he p oblem conside ed he ein. In con as , imp o emen s
o he co e componen s o he gene ic algo i hm can be expec ed o be e ec i e in he
weigh ed e sion o he p oblem as well.
In his pape , we build on his ea lie wo k and make signi ican con ibu ions, in
bo h heo y and p ac ice. Fi s , we p o ide a de ailed o mal analysis p o ing ele an
p ope ies, as he comple eness o he sea ch space o MFSJs, and he soundness o he
solu ion builde . In addi ion, we p opose wo key enhancemen s o he gene ic algo-
i hm: a new, mo e e icien , solu ion builde and a new p ocedu e o es he easibili y
o subse s o jobs mo e e ec i ely. Despi e es ic ing ou s udy o he ask o epai ing
in easible job shop scheduling p oblems wi h a ha d cons ain on he makespan, he
scope and applicabili y o his amewo k should be unde sco ed. The same no ions o
epai ing in easible p oblem ins ances could be applied o o he e sions o job shop
scheduling (e.g., conside ing se up imes, unce ain y o addi ional cons ain s on he
esou ces) o o o he scheduling p oblems whe e he inpu is a se o jobs. Fu he -
mo e, he ha d cons ain ha makes he p oblem ins ance in easible could be de ined
on me ics o he han he makespan. In any case, compu ing MFSJs and maxFSJs may
be a sui able app oach o dealing wi h in easibili y. In addi ion, he me hodology in
he o mal analysis and he algo i hms p oposed he ein could se e as a solid basis o
ackle such p oblems in he u u e.
In he emainde o his sec ion, we i s discuss some ela ed p oblems and hen
e iew gene ic algo i hms o sol ing scheduling p oblems.
3.1. Rela ed p oblems
The p oblem o compu ing maxFSJs add essed in his pape is ela ed o o he
p oblems s udied in he ield o scheduling.
Fo example, Dawande e al. (2006) conside ed he p oblem o inding a easi-
ble subse o jobs in a wo-s age low shop maximizing a weigh ed sum o he jobs.
Howe e , es ing he easibili y o a wo-s age low shop can be done in polynomial
ime (Ga ey e al., 1976), whe eas es ing he easibili y o gene al job shop ins ances
is an NP-comple e p oblem.
6
Ano he ela ed p oblem is he one add essed in (Della C oce e al., 2017), which
conside s polynomially sol able wo machine low shop and job shop p oblems, and
ocuses on selec ing he se o jobs o a gi en ixed size (in oduced as a pa ame e ) ha
op imizes he makespan. In con as , we ocus on op imizing he size o he selec ed
se o jobs, while ixing he limi on he maximum makespan allowed.
The p oblem add essed he ein can be also ela ed o he classical objec i e unc ion
o minimizing he numbe o la e, o a dy, jobs (Moo e, 1968; Della C oce e al.,
2000). In his se ing, each job is associa ed a due da e, and he goal is o compu e a
schedule ha minimizes he numbe jobs ha a e comple ed a e hei indica ed due
da es. This objec i e unc ion plays an impo an ole in he con ex o o e loaded
single-machine eal- ime sys ems (Liao e al., 2019), whe e he goal is comple ing he
maximum numbe o asks on ime. In his pape , ou goal is no compu ing a schedule
ha op imizes a gi en objec i e unc ion, bu iden i ying he la ges subse o jobs ha
can be scheduled unde he gi en addi ional ha d cons ain , emo ing any o he jobs
ha do no ake pa in he solu ion.
3.2. Gene ic algo i hms
Gene ic algo i hms (GAs) s and ou among he mos success ul popula ion-based
me aheu is ics (Talbi, 2009). GAs we e o iginally p oposed by Holland (1975) and a e
inspi ed in he heo y o e olu ion. These algo i hms main ain a popula ion o solu-
ions which is e ol ed by he applica ion o selec ion, ecombina ion and eplacemen
ope a o s, wi h he goal o eaching an app op ia e adeo be ween explo a ion o he
sea ch space and in ensi ica ion in i s mos p omising egions.
Gene ic algo i hms ha e been widely used o sol e a a ie y o ha d scheduling
p oblems, including single machine (Mus u and E en, 2018; Menc´
ıa e al., 2019), pa -
allel machines (Vallada and Ruiz, 2011; Tan e al., 2019), open shop (And esen e al.,
2008; Hosseinabadi e al., 2019), low shop (B anda e al., 2021), job shop (Gonc¸al es
and Resende, 2014; Zhang e al., 2020) o esou ce cons ained p ojec scheduling
p oblems (Gonal es e al., 2008). In addi ion, GAs ha e been success ully applied
in nume ous domains, as he e ogeneous compu ing sys ems Akba i e al. (2017) o
ope a ions managemen (Lee, 2018), o name a ew.
A la ge body o gene ic algo i hms has been p oposed o sol ing job shop schedul-
ing p oblems in hei op imiza ion e sions. The pe o mance o hese algo i hms e-
lies on coding schemas speci ic o he p oblem, as well as on he use o sophis ica ed
c osso e ope a o s. Some examples o coding schemas a e hose based on p e e ence
ules (Della C oce e al., 1995), pe mu a ions o jobs wi h epe i ions (Bie wi h, 1995)
o andom keys (Gonc¸al es and Resende, 2014). C osso e ope a o s play an impo -
an ole in he e olu iona y p ocess, since hese allow o an e ec i e ansmission o
ele an cha ac e is ics om pa en s o hei o sp ing. Examples o c osso e ope -
a o s include o de -based c osso e (Da is, 1985), mul i-s ep c osso e (Yamada and
Nakano, 1995) o job-based o de c osso e (Ono e al., 1996), among o he s.
In o de o decode ch omosomes in o ac ual schedules, GAs commonly exploi
schedule builde s. These a e me hods ha allow o es ic ing he sea ch o subse s
o all possible schedules. Fo ins ance, he well-known G&T algo i hm (Gi le and
Thompson, 1960) de ines he space o he so-called ac i e schedules. This algo i hm
has been ex ended o cope wi h a ian s o he job shop scheduling p oblem ha include
7
addi ional elemen s and cons ain s, o ins ance sequence-dependen se up imes (A -
igues e al., 2005) unce ain y in he p ocessing imes (Palacios e al., 2014), o skilled
ope a o s ha assis he p ocessing o he ope a ions (Menc´
ıa e al., 2015).
Gene ic algo i hms ha e also been success ully combined wi h o he me aheu is-
ics, as local sea ch me hods. Fo example, Mee an and Mo shed (2012) combined
a gene ic algo i hm wi h abu sea ch o sol e eal-li e job shop scheduling p oblems.
Ku di (2015) p oposed a hyb id gene ic algo i hm which inco po a es a sel -adap a ion
s a egy based on abu sea ch and andom mu a ion ope a o s. Hyb id gene ic algo-
i hms ha e also been success ul in di e en a ian s o he p oblem, as dynamic (Kun-
dakc and Kulak, 2016) o mul iobjec i e (Gong e al., 2019) job shop scheduling p ob-
lems, among o he s.
4. Sea ch space
The de ini ion o a sea ch space is a undamen al s ep owa ds sol ing ha d com-
bina o ial p oblems. Ideally, he sea ch space would exhibi some desi able p ope ies,
such as being o easonable size and con aining high-quali y solu ions o he p oblem,
including op imal ones.
When acing scheduling p oblems, he use o so-called schedule builde s is com-
mon o his pu pose, e.g. (Gi le and Thompson, 1960; Kolisch, 1996; A igues e al.,
2005; Palacios e al., 2014; Menc´
ıa e al., 2015). Schedule builde s, also e e ed o as
schedule gene a ion schemes, a e cons uc i e me hods o compu ing and enume a -
ing a subse o he schedules o a gi en p oblem ins ance, and so enable he de ini ion
o a sea ch space.
Howe e , o sol ing he p oblem conside ed he ein, i.e., app oxima ing maxFSJs
o a gi en in easible p oblem ins ance, compu ing schedules alone does no su ice,
since i is also necessa y o iden i y easible subse s o jobs. As a consequence, he
de ini ion o he sea ch space needs o be done in wo le els: i s on he subse space
o he se o all he jobs, and hen on he se o schedules o any gi en subse o jobs
in o de o es i s easibili y. We desc ibe bo h in he ollowing subsec ions.
4.1. Subse space o he se o jobs
Ou app oach aims a es ic ing he sea ch o he se o MFSJs, wha comes wi h
se e al bene i s. Fi s , he sea ch space de ined by he se o all MFSJs is comple e,
i.e., i con ains all op imal solu ions o any gi en p oblem ins ance. This ollows om
he ac ha all maxFSJs a e MFSJs as well, as p o en nex .
P oposi ion 1. Le I= (J, C)be an in easible p oblem ins ance and S∗(Ja
maxFSJ o J.S∗is also an MFSJ o J.
P oo . S∗is a maxFSJ o Jso, by De ini ion 3 i is an FSJ o J. Suppose ha S∗is
no an MFSJ o J. Then, by De ini ion 2, he e mus exis a p ope supe se S0(J
o S∗which is also an FSJ o J. As S∗(S0, i necessa ily ollows ha |S∗|<|S0|,
so S∗is no a maxFSJ o J. A con adic ion.
FSJs exhibi a use ul mono onici y p ope y ha will be used h oughou . We p o e
ha all he subse s o an FSJ a e easible subse s o jobs as well.
8
P oposi ion 2. Le I= (J, C)be an in easible p oblem ins ance and S(Jan FSJ
o J. Then, o all S0⊆ S,S0is an FSJ o J.
P oo . Since Sis an FSJ o J, he e exis s a schedule S o he jobs in Swi h
Cmax(S)≤C. Gi en S0⊆ S, we can build a schedule S0by assigning each op-
e a ion in S0 he same s a ing ime as in S.S0is a schedule o he jobs in S0and
Cmax(S0)≤Cmax(S)≤C, as he ope a ions in S0a e a subse o hose in S. Thus,
by De ini ion 1, S0is an FSJ o J.
A consequence o P oposi ion 2 is he dual esul ha all he supe se s o an in ea-
sible se o jobs a e in easible oo, as p o en nex :
P oposi ion 3. Le I= (J, C)be an in easible p oblem ins ance and le U ⊆ J be
such ha he ins ance (U, C)is in easible. Then, o all U0wi h U ⊆ U0⊆ J , he
ins ance (U0, C)is in easible.
P oo . Conside an a bi a y U0such ha U ⊆ U0⊆ J . Since, he ins ance (U, C)
is in easible and U ⊆ U0, no all he subse s o U0a e FSJs. By he con aposi i e o
P oposi ion 2 i ollows ha ha U0is no an FSJ o J, i.e., he ins ance (U0, C)is
in easible.
I is clea ha he numbe o MFSJs o any gi en p oblem ins ance is ne e g ea e
han he numbe o FSJs since, by de ini ion, all MFSJs a e FSJs oo. Howe e , P opo-
si ion 2 allows o easily p o ing ha he numbe o FSJs can be exponen ially g ea e
han ha o MFSJs.
P oposi ion 4. The e a e in easible p oblem ins ances wi h a numbe o FSJs expo-
nen ially g ea e han he numbe o MFSJs.
P oo . Conside a easible p oblem ins ance (S, C)and a job j /∈ S such ha he
sum o he p ocessing imes o i s ope a ions exceeds C. The job jalone canno be
scheduled unde he makespan cons ain , i.e., he ins ance ({j}, C)is in easible. Now
de ine he ins ance (J, C), wi h J=S ∪ {j}. By P oposi ion 3, his ins ance is
in easible since {j}⊆J. The se Sis he only MFSJ o J, whe eas by P oposi ion 2
each se in he powe se o Sis an FSJ o J, ha is, he e a e 2|S| FSJs o J.
No iceably, he mono onici y p ope ies s a ed abo e enable an al e na i e de ini-
ion o MFSJs:
P oposi ion 5. Le I= (J, C)be an in easible p oblem ins ance. S(Jis an MFSJ
o Ji and only i (S, C)is easible and o all j∈ J S,(S ∪ {j}, C)is in easible.
P oo . (I ) The ins ance (S, C)is easible, so Sis an FSJ o J. Le us suppose ha
Sis no an MFSJ o J. Then, he e mus exis an FSJ S0(Jsuch ha S(S0. As
S0is a p ope supe se o S,S0mus con ain some job j∈ J S. Since (S ∪ {j}, C)
is in easible o all j∈ J S, by P oposi ion 3, (S0, C)is necessa ily in easible. A
con adic ion.
(Only i ) Sis an MFSJ o Jso, by De ini ion 2, o all S0⊆ J such ha S(
S0, he ins ance (S0, C)is in easible. Hence, o all j∈ J S,(S ∪ {j}, C)is
in easible.
9
easibili y o a gi en p oblem ins ance (J0, C), wi h J0⊆ J he G&T algo i hm
builds a schedule S o he jobs in J0scheduling, a each i e a ion, he ope a ion in
he se B(see Algo i hm 3) ha appea s i s in he ope a ion sequence. We no ice ha
he ope a ion sequence con ains all he ope a ions o he jobs in J, so he ope a ions
o jobs no in J0a e simply igno ed. I he makespan o he compu ed schedule S
does no exceed he maximum limi C, he ins ance is decla ed easible (wi h Sbeing
a wi ness ha Jis a easible se o jobs). O he wise, al hough he e is no gua an ee
ha he ins ance is in easible, he solu ion builde would handle i as such. This does
no cons i u e a comple e decision p ocedu e, so he compu ed subse o jobs may no
be an ac ual MFSJ, bu an app oxima ion ins ead.
Anyway, he compu ed se is a easible se o jobs, and i s ca dinali y is he i ness
alue o he ch omosome.
C osso e and Mu a ion. The GA exploi s he Job-based O de C osso e (JOX) (Ono
e al., 1996) ope a o , which is pa icula ly ailo ed o pe mu a ions wi h epe i ions.
I wo ks as ollows: gi en a pai o (pa en ) ch omosomes, JOX selec s a andom
subse o he job indices and copies hem o he o sp ing in he same posi ions as hey
appea in he i s pa en . The emaining posi ions a e illed om he second pa en ,
main aining hei ela i e o de . As an example, le us conside he ollowing wo
ch omosomes:
Pa en 1: (211323 1 23) Pa en 2: (3 3 1 2 1 3 2 2 1)
I he selec ed subse o jobs only includes he job 2, he gene a ed o sp ing is:
O sp ing: (233121 3 21).
The second o sp ing is ob ained by he same p ocedu e, bu swi ching he ole
o he pa en s. On he o he hand, he mu a ion ope a o in oduces small changes by
swapping wo consecu i e posi ions o he ch omosome andomly.
O e all in eg a ed wo k low. Figu e 2 shows he o e all wo k low o he gene ic al-
go i hm. Gi en a p oblem ins ance and he GA pa ame e s, he GA s a s by gene -
a ing and e alua ing he ini ial popula ion. Then, un il he e mina ion condi ion is
me , he popula ion e ol es by unde going selec ion, ecombina ion, e alua ion and
eplacemen phases. A each gene a ion, he ch omosomes in he popula ion a e pai ed
andomly (selec ion). In he ecombina ion phase, each pai o ch omosomes gi es ise
o wo o sp ing, by he applica ion o c osso e and mu a ion ope a o s. Then, he
new indi iduals a e e alua ed, ob aining ac ual solu ions om he ch omosomes. To
his aim, o each indi idual he job sequence and he ope a ions sequence a e ex ac ed
om he ch omosome. Nex , he solu ion builde is in oked, which is guided by he job
sequence in he app oxima ion o an MFSJ. Fo his pu pose, ei he he one based on
linea sea ch (Algo i hm 1) o he new one ha in eg a es bina y sea ch (Algo i hm 2)
can be used. The solu ion builde makes se e al in oca ions o he p ocedu e Feasible,
which is guided by he ope a ions sequence ex ac ed om he ch omosome. The im-
plemen a ion o his p ocedu e is based on he G&T algo i hm, as explained in his
sec ion. An imp o emen o his p ocedu e is p esen ed in he ollowing sec ion (Al-
go i hm 5). A e all he ch omosomes a e e alua ed, he ones ha will su i e o he
16

E alua ion
(J, C) Ins ance,
GA pa ame e s
Gene a e and E alua e
Ini ial Popula ion
Selec ion
Random
Recombina ion
C osso e and Mu a ion
Ex ac job and
ope a ions sequences
Solu ion Builde
Alg. 1 o Alg. 2
P ocedu e Feasible
G&T o Alg. 5
Replacemen
Tou namen
Te mina e? FSJ wi h he
g ea es size ound
no
yes
Figu e 2: O e all wo k low o he gene ic algo i hm.
nex gene a ion a e hose ha a e i e , acco ding o a ou namen be ween pa en s and
o sp ing ( eplacemen ). A e he GA is un o he gi en numbe o gene a ions, he
FSJ wi h he g ea es size ound along he whole p ocess is e u ned.
6. Imp o ing he e ec i eness o he decoding algo i hms
The decoding algo i hms used by he GA aim a unde -app oxima ing an MFSJ
e icien ly by using he g eedy G&T algo i hm o es he easibili y o subsequen
subse s o jobs. A guably, using a g eedy algo i hm o his pu pose ep esen s he mos
e icien app oach possible bu , in u n, he app oxima ions p oduced may no always
be accu a e. I only e ec i eness is sough o , one could use a comple e decision
p ocedu e; howe e , as al eady poin ed ou , using an exac algo i hm, e.g. (B ucke
e al., 1994; Beck, 2007; Menc´
ıa e al., 2014; Vil´
ım e al., 2015), may be oo ime
consuming, making he app oach imp ac ical. Be ween hese wo ex emes he e is a
17
wide ange o possibili ies, such as using me aheu is ics mo e e ec i e (al hough mo e
expensi e) han g eedy algo i hms o es he easibili y o a gi en subse o jobs.
He ein, we aim a imp o ing he e ec i eness o he decoding algo i hms by means
o an al e na i e implemen a ion o he p ocedu e Feasible used in Algo i hms 1 and 2.
To his aim, we p opose an app oach ha no only issues he G&T algo i hm o his
ask, bu also uses a ligh -weigh gene ic algo i hm, e med LWGA h oughou , i he
o me ails a p o ing easibili y.
The p oposed me hod is shown in Algo i hm 5. Gi en a se o jobs J0, a limi on
he makespan Cand a p obabili y PLW GA, he algo i hm i s compu es a schedule S
by using he g eedy G&T algo i hm. I he makespan o Sis no g ea e han C, he
ins ance (J0, C)is e icien ly decla ed easible. O he wise, he me hod pe o ms a sec-
ond phase wi h p obabili y PLW GA (in his espec , he p ocedu e Random(0,1) gen-
e a es a andom numbe in he in e al [0,1] wi h uni o m dis ibu ion). In his phase
he p ocedu e in okes LWGA, ha sea ches o a schedule minimizing he makespan
and e u ns he bes schedule S0 ound a e a sho unning ime. Finally, i S0has
a makespan no exceeding C, he ins ance is decla ed easible, whe eas o he wise he
easibili y o he ins ance is deemed unknown.
We no e ha he p ocedu e e u ns a Boolean alue indica ing whe he he ins ance
(J0, C)has been p o en easible. In his ega d, he alue ue means ha a schedule
wi h makespan no exceeding Chas been ound and so he ins ance is easible. In
con as , he alue alse does no mean ha he ins ance is necessa ily in easible, bu
ha a schedule wi h makespan no exceeding Chas no been ound. So, Algo i hm 5
is an incomple e (bu sound) decision p ocedu e. Howe e , since i uses a mo e e -
ec i e p ocedu e o sea ching o high-quali y schedules, i can be expec ed o de ec
easibili y mo e imes han only using he G&T algo i hm, hus leading o be e ap-
p oxima ions o MFSJs. In any case, whene e an ins ance is decla ed easible, he e is
he gua an ee ha he esul is co ec , and so he compu ed app oxima ions o MFSJs
a e co ec as well.
Mo eo e , al hough i is no shown in he pseudocode, he p ocedu e exploi s he
ope a ion sequences encoded in he ch omosomes o he main GA bo h when issuing
he G&T algo i hm (as desc ibed in Sec ion 5), and LWGA (as desc ibed below). So,
i is in eg a ed in he global sea ch ca ied ou by he main GA.
Since he p ocedu e Feasible is in oked many imes along he execu ion o he
main GA, in o de o keep he o e head easonably low, LWGA is only in oked wi h
he gi en p obabili y PLW GA in oduced as a pa ame e . The alue o his pa ame e
is he same o all he in oca ions along he execu ion o he main GA. This way, he
po en ial imp o emen s a e equally dis ibu ed among all he indi iduals.
6.1. Ligh -weigh gene ic algo i hm (LWGA)
As poin ed ou , LWGA sea ches o schedules aiming a minimizing he makespan.
I ollows he same gene al s uc u e as he main GA, shown in Algo i hm 4. Howe e ,
since LWGA mus no ake a long unning ime, we need o limi i s popula ion size
and numbe o gene a ions o small alues. In addi ion, LWGA e mina es whene e i
inds a schedule wi h a makespan less han o equal o he limi C.
As he main GA desc ibed in Sec ion 5, LWGA uses pe mu a ions wi h epe i ions
o encoding ch omosomes. In his case, a ch omosome only includes he asks o he
18
Algo i hm 5 P ocedu e Feasible.
Da a: Se o jobs J0, makespan limi C, p obabili y PLW GA
Resul : Boolean alue indica ing ha he ins ance (J0, C)has been p o en easible
S←G&T(J0);
i Cmax(S)≤C hen
e u n ue;
else i Random(0,1) ≤PLW GA hen
S0←LWGA(J0, C);
i Cmax(S0)≤C hen
e u n ue;
end
end
e u n alse
jobs in J0, ep esen ing ope a ion sequences. Besides, i uses he same c osso e (JOX)
and mu a ion ope a o s. As decoding algo i hm, LWGA exploi s he G&T algo i hm
guided by he ope a ion sequences encoded in he ch omosomes. A e building a
schedule, he i ness o he indi idual is he makespan o he compu ed schedule.
Fu he mo e, wo addi ional p ocesses a e ca ied ou as a means o e ec i ely
in eg a ing LWGA in he global sea ch p ocess conduc ed by he main GA.
Fi s , in o de o exploi he in o ma ion encoded in a gi en ch omosome co he
main GA o guiding he sea ch in he space o schedules, LWGA c ea es i s ini ial
popula ion by he ollowing p ocedu e: a ch omosome c0is c ea ed by conside ing
he asks o he jobs in J0keeping hei o de as hey appea in c, and he esul ing
ch omosome c0is included in he popula ion. Then ano he wo ch omosomes a e
gene a ed by in oducing small andom pe u ba ions o c0(by swapping wo andom
posi ions o c0), which a e included in he ini ial popula ion as well. The emaining
indi iduals a e gene a ed a andom. This way, he cha ac e is ics o ca e included in
he ini ial popula ion o LWGA, bu no in an ex en ha would cause i o con e ge
e y p ema u ely.
On he o he hand, when using LWGA, he main GA ins umen s a Lama ckian
e olu ion model in o de o ans e he cha ac e is ics ha led o an imp o emen back
o he main GA’s popula ion. Fo his pu pose, a e an app oxima ion o an MFSJ
has been compu ed by he decoding algo i hm o he main GA, i LWGA p o ed he
easibili y o he subse o jobs, he co esponding ch omosome co he main GA is
eplaced by a ch omosome c00 buil as ollows: he i s posi ions o c00 co espond o he
ch omosome ha led LWGA o compu e a schedule o such subse o jobs J0wi hou
exceeding he makespan limi ; hen, he emaining posi ions o c00 a e illed wi h he
asks o he emaining jobs in he o de hey appea in c. Lama ckian e olu ion models
a e commonly used by meme ic algo i hms, ha combine a gene ic algo i hm wi h a
local sea ch p ocedu e. Howe e , hese could also be expec ed o p ac ical use in his
his con ex .
19
7. Expe imen al esul s
An expe imen al s udy was conduc ed o e alua e he me hods p oposed in his
wo k. Fo his pu pose, we coded a p o o ype in C++ implemen ing he algo i hms and
an expe imen s on a Linux machine (In el Xeon 2.26 GHz. 128 GB RAM).
The expe imen s we e ca ied ou o e a se o in easible ins ances de i ed om
classical JSP benchma ks om he OR-lib a y (Beasley, 1990) as well as la ge Tail-
la d’s ins ances (Tailla d, 1993). The benchma k se consis s o ins ances o di e en
sizes n×mwi h a numbe o jobs n∈ {10,15,20,30,50}and a numbe o machines
m∈ {5,10,15,20}. Speci ically, we conside 5 ins ances o size 10 ×5: LA01-05; 5
ins ances o size 15 ×5: LA06-10; 6 ins ances o size 20 ×5: LA11-15 and FT20; 16
ins ances o size 10×10: LA016-20, ORB01-10 and FT10; 5 ins ances o size 15×10:
LA21-25; 5 ins ances o size 20×10: LA26-30; 5 ins ances o size 30 ×10: LA31-35;
5 ins ances o size 15 ×15: LA36-40; 10 ins ances o size 50 ×15: ai50 15 01-10;
and 10 ins ances o size 50 ×20: ai50 20 01-10. Fo each o hese ins ances, h ee
in easible ins ances we e buil by ixing di e en alues o he makespan limi C o be
70%,80% and 90% o he op imal makespan o he JSP ins ance, deno ed Cop . So, in
all he e a e 216 ins ances.
The goal o he expe imen al s udy is o assess he pe o mance o he p oposed
me hods. To his aim we compa e h ee gene ic algo i hms, e med GALS, GABS and
GA∗ h oughou . All hese algo i hms sha e he main s uc u e and componen s de-
sc ibed in Sec ion 5, bu di e in he solu ion builde used in he decoding phase. GALS
uses he solu ion builde based on linea sea ch depic ed in Algo i hm 1, whe eas GABS
exploi s he wo-phase solu ion builde ha in eg a es a bina y sea ch phase shown in
Algo i hm 2. Bo h GALS and GABS use a single un o he g eedy G&T algo i hm
(Algo i hm 3) o es ing he easibili y o di e en subse s o jobs. On he o he hand,
mo i a ed by he i s se ies o expe imen s shown below, GA∗in eg a es he wo-phase
solu ion builde , bu using he p ocedu e Feasible gi en in Algo i hm 5, which issues
he ligh -weigh gene ic algo i hm ( e med LWGA in Sec ion 6) wi h a gi en p oba-
bili y PLW GA when he single un o he G&T algo i hm ails a p o ing easibili y.
We no ice ha GALS co esponds o he gene ic algo i hm p oposed in (Menc´
ıa e al.,
2019), which was shown o pe o m (much) be e han a simple enume a ion o an-
dom app oxima ions o MFSJs. To ou knowledge, his is he only algo i hm p oposed
so a o he p oblem ackled in his pape , so i se es as a baseline me hod in he
expe imen al e alua ion.
In all he expe imen s, he conside ed GAs e ol e a popula ion o 100 indi iduals
wi h c osso e p obabili y o 0.9and mu a ion p obabili y o 0.1un il a e mina ion
condi ion is me (ei he comple ing a numbe o gene a ions o su passing a gi en ime
limi ). In he case o GA∗, he unde lying LWGA has he same c osso e and mu a ion
p obabili ies. The algo i hms we e un 20 imes on each ins ance.
Fu he mo e, in he expe imen al s udy he quali y o he solu ions compu ed is
e alua ed in e ms o hei e o in pe cen age w. . . he bes solu ion ound o each
ins ance along all he expe imen s. Mo e conc e ely, i o a gi en ins ance he bes
known solu ion has Nbes jobs and an algo i hm inds a solu ion wi h Njobs (wi h
N≤Nbes ), he e o in pe cen age is compu ed as 100 ×(Nbes −N)/Nbes .
Ou i s hypo hesis is ha GABS and GALS will yield simila esul s in e ms o he
20
Table 3: Main no a ion used in he expe imen al s udy.
No a ion De ini ion
nNumbe o jobs
mNumbe o machines
CMakespan limi
Cop Op imal makespan
LWGA Ligh -weigh gene ic algo i hm
PLW GA P obabili y o in oking LWGA in p ocedu e Feasible (Algo i hm 5)
GALS GA wi h he solu ion builde based on linea sea ch (Algo i hm 1)
GABS GA wi h he solu ion builde based on bina y sea ch (Algo i hm 2)
GA∗GA wi h he solu ion builde based on bina y sea ch issuing LWGA in p ocedu e Feasible
#cNumbe o indi iduals (popula ion size) o LWGA
#gNumbe o gene a ions o LWGA
GAPLW GA
#c/#g
GA∗using a p obabili y PLW GA and se ing he unde lying LWGA wi h a popula ion
size o #cindi iduals and #ggene a ions
quali y o solu ions eached, while GABS will be as e , since he solu ion builde wi h
he bina y sea ch phase is expec ed o make less in oca ions o he p ocedu e Feasible
han he solu ion builde based on linea sea ch. On he o he hand, we expec GA∗ o
each be e solu ions han GABS and GALS, due o a mo e e ec i e implemen a ion o
he p ocedu e Feasible, a he expense o longe unning imes.
The expe imen al s udy is di ided in h ee pa s. We i s compa e GALS and GABS
in o de o assess he wo solu ion builde s. Then, we ocus on GA∗and analyze he
e ec ha he pa ame e PLW GA and he con igu a ion o he unde lying LWGA ha e
on he o e all pe o mance o he algo i hm. Finally, we p o ide a de ailed compa ison
o he h ee gene ic algo i hms.
Table 3 summa izes he main no a ion used in his sec ion.
7.1. Compa ing GALS and GABS
We conduc ed a i s se ies o expe imen s in o de o compa e he wo solu ion
builde s and assess he e iciency gains ha in oducing a bina y sea ch phase has on
he pe o mance o he algo i hm. Fo his pu pose, we an bo h GALS and GABS on
he whole benchma k se , limi ing he numbe o gene a ions o 250.
Table 4 summa izes he esul s. I shows he e o (in pe cen age e ms) o he bes
(Bes ) and a e age solu ions (A g.) ob ained by each me hod o e he 20 independen
uns, as well as he compu a ion imes in seconds, a e aged o each g oup o ins ances
o he same size n×m. As we can obse e, bo h algo i hms yield solu ions o simila
quali y ega dless o he size o he ins ances, wi h only small a ia ions ha may be
due o hei s ochas ic na u e. The wo gene ic algo i hms a e e y e ec i e a sol ing
he smalles ins ances (up o size 20 ×5), ob aining solu ions close o he bes known
ones, al hough he e o g ows o la ge (and mo e challenging) ins ances, exceeding
10% on a e age o he la ges ones o size 50 ×20.
Howe e , GABS is as e han GALS a comple ing he 250 gene a ions. On a e age
GABS akes less han 75% o he ime aken by GALS. This indica es ha he bina y
sea ch phase included in he solu ion builde used by GABS is e ec i e a sa ing easi-
bili y es s, wha enables educing he o e all compu a ion ime. G ea e imp o emen s
21

Table 4: Summa y o esul s om GABS and GALS a e e ol ing a popula ion o 100 indi iduals o e 250
gene a ions. Bes and a e age esul s (in e ms o e o in pe cen age) om 20 independen uns a e epo ed.
Running imes a e gi en in seconds.
GALS GABS
n×mBes A g. T.(s) Bes A g. T.(s)
10 ×50.00 1.09 0.58 0.00 1.12 0.48
15 ×50.99 1.12 1.78 0.99 1.07 1.27
20 ×50.68 1.49 3.66 1.01 1.38 2.49
10 ×10 1.77 4.82 0.85 2.35 4.75 0.80
15 ×10 3.37 7.31 2.51 3.97 6.74 2.21
20 ×10 4.83 8.04 5.44 4.73 7.88 4.50
30 ×10 3.79 6.18 16.80 3.79 6.28 11.72
15 ×15 3.07 7.63 2.98 3.91 7.83 2.78
50 ×15 6.08 8.42 80.72 5.91 8.36 57.09
50 ×20 7.32 10.28 92.34 7.14 10.20 70.95
All 3.43 5.97 26.62 3.63 5.89 19.76
0 5 10 15 20
GALS
0
5
10
15
20
GABS
(a) Up o 30 jobs
0 20 40 60 80 100 120
GALS
0
20
40
60
80
100
120
GABS
(b) 50 jobs
Figu e 3: Sca e plo s o he ime aken (seconds) by GALS and GABS o comple e 250 gene a ions on he
ins ances wi h (a) up o 30 jobs and (b) 50 jobs.
a e obse ed as he numbe o jobs g ows, which does no come as a su p ise since in
hese cases a la ge numbe o es s can be sa ed by applying bina y sea ch.
Figu e 3 shows wo sca e plo s depic ing he ime aken by GALS and GABS o
comple e 250 gene a ions o he ins ances wi h up o 30 jobs (Figu e 3(a)) and o
he la ges ins ances wi h 50 jobs (Figu e 3(b)). Each poin ep esen s he unning
ime in seconds o GALS (ho izon al axis) compa ed o GABS ( e ical axis) on a gi en
ins ance. Poin s below he diagonal indica e ha GABS is as e han GABS. As can
be obse ed, he di e ence in a o o GABS is g ea e wi h longe compu a ion imes.
No iceably, o he ins ances wi h 50 jobs, e e y poin is a om he diagonal, which
means ha o hese la ge ins ances, GABS is much as e han GALS.
22
Table 5: Summa y o a e age esul s (e o in pe cen age) om he con igu a ions o GA∗a e e ol ing a
popula ion o 100 indi iduals o e 250 gene a ions.
PLW GA = 0.15 PLW GA = 0.5PLW GA = 1
#c/#g10/10 10/20 10/30 20/20 10/10 10/20 10/30 20/20 10/10 10/20 10/30 20/20
10 ×50.33 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
15 ×50.99 0.99 0.96 0.94 0.97 0.89 0.81 0.79 0.99 0.82 0.59 0.18
20 ×50.83 0.76 0.73 0.60 0.76 0.65 0.59 0.57 0.65 0.63 0.61 0.47
10 ×10 1.57 1.10 0.83 0.69 1.06 0.51 0.30 0.17 0.81 0.23 0.06 0.12
15 ×10 4.49 3.79 3.92 3.49 3.64 3.49 3.29 2.86 3.12 2.90 2.52 2.25
20 ×10 5.36 4.95 4.75 4.45 4.50 4.22 3.71 3.22 4.42 3.67 3.24 2.81
30 ×10 3.43 3.31 3.36 3.12 3.22 2.91 2.70 2.23 2.95 2.59 2.22 1.92
15 ×15 3.19 2.76 2.49 2.05 2.53 1.63 1.38 1.13 1.71 1.19 1.16 1.03
50 ×15 3.89 3.51 3.41 2.96 3.05 2.67 2.45 2.27 2.61 2.30 2.62 2.62
50 ×20 4.73 4.05 3.85 3.41 3.44 2.81 2.91 2.83 2.94 2.92 3.40 3.68
All 2.85 2.46 2.33 2.06 2.23 1.84 1.69 1.51 1.92 1.61 1.58 1.51
7.2. Analyzing GA∗
The second pa o he expe imen al s udy is aimed a analyzing GA∗. As men-
ioned abo e, GA∗uses he p ocedu e gi en in Algo i hm 5 o es he easibili y o
subse s o jobs. This p ocedu e issues a ligh -weigh gene ic algo i hm (LWGA) wi h a
gi en p obabili y PLW GA whene e he G&T algo i hm ails a p o ing easibili y. So,
i is expec ed o be (much) mo e ime consuming han simply using he G&T algo i hm
o his pu pose (as GALS and GABS do). As a consequence, and gi en he esul s in
he p e ious subsec ion, GA∗uses he solu ion builde ha in eg a es he bina y sea ch
phase in o de o sa e ime.
In hese expe imen s we e alua e di e en alues o he pa ame e PLW GA; con-
c e ely we conside alues o PLW GA in {0.15,0.5,1}. In addi ion, we e alua e di -
e en con igu a ions o LWGA in e ms o popula ion size and numbe o gene a ions.
In his espec , we conside ou con igu a ions: e ol ing a popula ion o 10 indi iduals
o e 10, 20 and 30 gene a ions, and a popula ion o 20 indi iduals o e 20 gene a ions.
Th oughou we will use he no a ion GAPLW GA
#c/#g o e e o GA∗using a gi en p obabil-
i y PLW GA and se ing he unde lying LWGA wi h a popula ion size o #cindi iduals
and #ggene a ions. Taking all in o accoun , we conside 12 con igu a ions o GA∗.
We i s e alua e he di e en e sions o GA∗wi h he e mina ion c i e ion o
comple ing 250 gene a ions. Besides, since some con igu a ions may be oo ime con-
suming, we se a imeou o 3600 seconds in hese expe imen s. Table 5 shows, o
each con igu a ion, he e o on a e age o he solu ions ob ained o e he 20 inde-
penden uns, a e aged o g oups o ins ances o he same size. On he o he hand,
Table 6 shows he ime aken by each con igu a ion in seconds. In bo h cases, he las
ow a e ages he esul s o e all he ins ances.
As we can obse e in Table 5, he quali y o he solu ions imp o es wi h la ge al-
ues o PLW GA in mos cases. Fo mos g oups o ins ances, using PLW GA = 1 yields
he bes esul s. Howe e , he la ges ins ances o size 50 ×15 and 50 ×20 a e he
excep ion o his end. In hese cases, op ions wi h PLW GA = 0.5achie ed he bes
esul s. This can be explained by he ac ha o hese la ge ins ances, some con ig-
u a ions wi h PLW GA = 1 we e only able o comple e a ac ion o he 250 i e a ions
23
Table 6: Summa y o he a e age ime (in seconds) ha each con igu a ion o GA∗ ook o e ol e a popula-
ion o 100 indi iduals o e 250 gene a ions.
PLW GA = 0.15 PLW GA = 0.5PLW GA = 1
#c/#g10/10 10/20 10/30 20/20 10/10 10/20 10/30 20/20 10/10 10/20 10/30 20/20
10 ×52.2 3.0 3.8 5.7 6.2 9.2 11.8 18.7 12.4 19.0 24.4 40.0
15 ×55.6 8.0 9.9 15.2 16.3 25.1 32.1 51.8 33.1 52.1 67.6 109.7
20 ×512.1 18.0 23.1 34.9 35.6 56.3 74.3 117.5 71.4 115.4 153.8 245.1
10 ×10 4.5 6.5 8.3 12.6 13.0 20.3 26.2 41.4 26.0 41.1 53.6 86.2
15 ×10 12.3 18.3 23.2 36.2 36.2 56.7 73.9 119.3 72.5 116.0 151.2 248.0
20 ×10 26.4 40.3 51.5 79.5 79.0 126.6 165.7 262.7 157.2 257.2 339.5 546.4
30 ×10 67.4 106.3 140.2 205.1 202.9 337.8 457.0 682.6 404.5 688.9 941.6 1411.4
15 ×15 16.8 25.5 33.1 50.5 50.2 80.0 105.8 167.4 100.1 162.5 219.1 349.3
50 ×15 397.1 658.4 912.4 1258.7 1206.6 2107.5 2988.6 3567.5 2388.6 3581.2 3600 3600
50 ×20 530.3 885.5 1229.5 1707.3 1619.9 2849.5 3600 3600 3212.4 3600 3600 3600
All 139.9 231.4 319.4 444.9 425.6 741.8 986.5 1106.5 843.8 1107.7 1149.8 1233.0
by he ime limi o 3600 seconds. In he es o he expe imen s, hey comple ed hem
and p oduced he bes esul s. Also, con igu a ions wi h PLW GA = 0.5yielded be e
esul s han hose wi h PLW GA = 0.15 o all he ins ance se s. On he o he hand,
assigning he LWGA la ge alues o popula ion size and numbe o gene a ions leads
o be e esul s as well. In mos cases, he con igu a ions ha p oduce he leas a e -
age e o a e hose wi h GAPLW GA
20/20 , ollowed by GAPLW GA
10/30 , hen GAPLW GA
10/20 and he
con igu a ion in he las posi ion is no mally GAPLW GA
10/10 . This anking does no hold
o PLW GA ∈ {0.5,1.0}on he la ges ins ances, due o he eason men ioned abo e.
These esul s indica e ha he use o LWGA is e ec i e a es ing easibili y, and
ha issuing i mo e o en and wi h la ge popula ion size and numbe o gene a ions
leads o be e esul s in mos cases. Howe e , hese imp o emen s do no come wi hou
a cos . As shown in Table 6, unning imes g ow signi ican ly wi h PLW GA, as well
as wi h he popula ion size and numbe o gene a ions o LWGA, being GA0.15
10/10 he
mos e icien app oach, as could be expec ed. No e ha o some con igu a ions wi h
PLW GA ∈ {0.5,1} unning imes a e a he long, especially o he la ges ins ances,
whe e some o hese con igu a ions imed ou be o e comple ing he 250 gene a ions.
Figu e 4 shows wo boxplo s o he ime aken (seconds) o comple e 250 gene a-
ions by he di e en con igu a ions o GA∗on he ins ances wi h up o 30 jobs (Fig-
u e 4(a)) and 50 jobs (Figu e 4(b)). We can see ha , he la ge he alues o PLW GA,
#cand #ga e, he mo e ime consuming he esul ing algo i hm is.
Figu e 5(a) shows a boxplo o he a e age e o s o he 50 ×20 se , which il-
lus a es he beha iou o he di e en con igu a ions on he la ges ins ances. As we
can obse e, he bes con igu a ions a e hose in he middle in e ms o esou ce con-
sump ion, which each a p ope balance be ween he e o spen a each indi idual and
he global sea ch p ocess ha he gene ic algo i hm is able o conduc unde he gi en
condi ions.
In o de o do a ai compa ison, we conduc ed a se ies o expe imen s gi ing he
algo i hms he same ime, le ing he di e en con igu a ions o pe o m as many gen-
e a ions as possible by he gi en ime limi . Conc e ely, o an ins ance o size n×m,
24
GA0.15
10/10 GA0.15
10/20 GA0.15
10/30 GA0.15
20/20 GA0.5
10/10 GA0.5
10/20 GA0.5
10/30 GA0.5
20/20 GA1
10/10 GA1
10/20 GA1
10/30 GA1
20/20
0
200
400
600
800
1000
1200
1400
1600
1800
ime (s)
(a) Up o 30 jobs
GA0.15
10/10 GA0.15
10/20 GA0.15
10/30 GA0.15
20/20 GA0.5
10/10 GA0.5
10/20 GA0.5
10/30 GA0.5
20/20 GA1
10/10 GA1
10/20 GA1
10/30 GA1
20/20
0
500
1000
1500
2000
2500
3000
3500
4000
ime (s)
(b) 50 jobs
Figu e 4: Boxplo s o he ime aken (seconds) by he di e en con igu a ions o GA∗ o comple e 250
gene a ions on he ins ances wi h (a) up o 30 jobs and (b) 50 jobs.
GA0.15
10/10 GA0.15
10/20 GA0.15
10/30 GA0.15
20/20 GA0.5
10/10 GA0.5
10/20 GA0.5
10/30 GA0.5
20/20 GA1
10/10 GA1
10/20 GA1
10/30 GA1
20/20
0
1
2
3
4
5
6
7
8
9
e o (%)
(a) 250 gene a ions
GA0.15
10/10 GA0.15
10/20 GA0.15
10/30 GA0.15
20/20 GA0.5
10/10 GA0.5
10/20 GA0.5
10/30 GA0.5
20/20 GA1
10/10 GA1
10/20 GA1
10/30 GA1
20/20
0
2
4
6
8
10
12
e o (%)
(b) Timeou 1000 seconds
Figu e 5: Boxplo s o he a e age e o in pe cen age ob ained o he ins ances o size 50 ×20, limi ing he
con igu a ions o GA∗ o (a) 250 gene a ions and (b) 1000 seconds.
we se he ime limi o n×mseconds (which we belie e is a easonable choice).
The esul s a e summa ized in Table 7, which epo s he e o s on a e age o e he
20 independen uns p oduced by he di e en con igu a ions, a e aged o each g oup
o ins ances, as well as he a e age alues o e he whole benchma k se . Looking a he
esul s o he smalles ins ances, i.e., 10×5and 15×5, we can d aw simila conclusions
as o wha we obse ed in he p e ious compa isons: he hea ie con igu a ions o GA∗
pe o m be e , al hough wi h small di e ences in his case. Howe e , as he size o he
ins ances g ows, his end is in e ed, a o ing smalle alues o PLW GA as well as
smalle popula ion size and numbe o gene a ions o he unde lying LWGA. Figu e
5(b) shows a boxplo o he 50 ×20 ins ance se . We can see how he ligh e e sions
o GA∗a e now a o ed when compa ing o he i s se ies o expe imen s.
O e all, he bes con igu a ion o GA∗seems o be GA0.15
10/20, since i yields he
leas a e age e o i all he ins ances a e conside ed. So, we will use his con igu a ion
25
easibili y. Ano he in e es ing line o u u e esea ch is he de elopmen o al e na-
i e algo i hms, and hei combina ion wi h he gene ic algo i hms p oposed he ein. In
his espec , de ising a local sea ch app oach, o e en an exac me hod, seems p omis-
ing. Finally, u u e e o s will a ge he ask o epai ing in easibili y conside ing
o he scheduling p oblems and ha d cons ain s de ined on me ics di e en om he
makespan.
Acknowledgemen s
This esea ch is suppo ed by he Spanish Go e nmen unde p ojec s TIN2016-
79190-R and PID2019-106263RB-I00, and by he P incipali y o As u ias unde g an
IDI/2018/000176.
Re e ences
Akba i, M., Rashidi, H., Alizadeh, S. H., 2017. An enhanced gene ic algo i hm wi h
new ope a o s o ask scheduling in he e ogeneous compu ing sys ems. Eng. Appl.
A i . In ell. 61, 35–46.
Allah e di, A., Aydilek, H., 2014. To al comple ion ime wi h makespan cons ain
in no-wai lowshops wi h se up imes. Eu opean Jou nal o Ope a ional Resea ch
238 (3), 724 – 734.
And esen, M., B sel, H., M ig, M., Tusch, J., We ne , F., Willenius, P., 2008. Simula ed
annealing and gene ic algo i hms o minimizing mean low ime in an open shop.
Ma hema ical and Compu e Modelling 48 (7), 1279–1293.
A igues, C., Lopez, P., Ayache, P., 2005. Schedule gene a ion schemes o he job shop
p oblem wi h sequence-dependen se up imes: Dominance p ope ies and compu a-
ional analysis. Annals o Ope a ions Resea ch 138, 21–52.
Bailey, J., S uckey, P. J., 2005. Disco e y o minimal unsa is iable subse s o con-
s ain s using hi ing se dualiza ion. In: PADL. pp. 174–186.
Beasley, J. E., 1990. O -lib a y: Dis ibu ing es p oblems by elec onic mail. J Ope
Res Soc 41 (11), 1069–1072.
Beck, J. C., 2007. Solu ion-guided mul i-poin cons uc i e sea ch o job shop
scheduling. J. A i . In ell. Res. 29, 49–77.
Bie wi h, C., 1995. A gene alized pe mu a ion app oach o job shop scheduling wi h
gene ic algo i hms. OR Spec um 17, 87–92.
B anda, A., Cas ellano, D., Guizzi, G., Popolo, V., 2021. Me aheu is ics o he low
shop scheduling p oblem wi h main enance ac i i ies in eg a ed. Compu e s & In-
dus ial Enginee ing 151, 106989.
B ucke , P., Ju isch, B., Sie e s, B., 1994. A b anch and bound algo i hm o he job-
shop scheduling p oblem. Disc e . Appl. Ma h. 49 (1-3), 107–127.
32

B ucke , P., Knus , S., 2006. Complex Scheduling. Sp inge .
Choi, J. Y., 2015. Minimizing o al weigh ed comple ion ime unde makespan con-
s ain o wo-agen scheduling wi h job-dependen aging e ec s. Compu e s & In-
dus ial Enginee ing 83, 237 – 243.
Da is, L., 1985. Applying adap i e algo i hms o epis a ic domains. In: Joshi, A. K.
(Ed.), IJCAI. Mo gan Kau mann, pp. 162–164.
Dawande, M., Ga i neni, S., Rachamadugu, R., 2006. Scheduling a wo-s age lowshop
unde makespan cons ain . Ma hema ical and Compu e Modelling 44 (1), 73 – 84.
Della C oce, F., Gup a, J. N., Tadei, R., 2000. Minimizing a dy jobs in a lowshop wi h
common due da e. Eu opean Jou nal o Ope a ional Resea ch 120 (2), 375 – 381.
Della C oce, F., Koulamas, C., T’Kind , V., 2017. A cons ain gene a ion app oach o
wo-machine shop p oblems wi h jobs selec ion. Eu . J. Ope . Res. 259 (3), 898–905.
Della C oce, F., Tadei, R., Vol a, G., 1995. A gene ic algo i hm o he job shop p ob-
lem. Compu . Ope . Res. 22 (1), 15–24.
Deng, G., Su, Q., Zhang, Z., Liu, H., Zhang, S., Jiang, T., 2020. A popula ion-based
i e a ed g eedy algo i hm o no-wai job shop scheduling wi h o al low ime c i e-
ion. Enginee ing Applica ions o A i icial In elligence 88, 103369.
Galla do, J. E., Co a, C., 2015. A g asp-based meme ic algo i hm wi h pa h elinking
o he a om mos s ing p oblem. Eng. Appl. A i . In ell. 41, 183–194.
Ga c´
ıa, S., Fe n´
andez, A., Luengo, J., He e a, F., 2010. Ad anced nonpa ame ic es s
o mul iple compa isons in he design o expe imen s in compu a ional in elligence
and da a mining: Expe imen al analysis o powe . In . Sci. 180 (10), 2044–2064.
Ga ey, M., Johnson, D., Se hi, R., 1976. The complexi y o lowshop and jobshop
scheduling. Ma hema ics o Ope a ions Resea ch 1 (2), 117 – 129.
Gi le , B., Thompson, G. L., 1960. Algo i hms o sol ing p oduc ion scheduling
p oblems. Ope a ions Resea ch 8, 487–503.
Gonal es, J., Mendes, J., Resende, M., 2008. A gene ic algo i hm o he esou ce
cons ained mul i-p ojec scheduling p oblem. Eu opean Jou nal o Ope a ional Re-
sea ch 189 (3), 1171–1190.
Gonc¸al es, J. F., Resende, M. G. C., 2014. An ex ended ake s g aphical me hod wi h a
biased andom-key gene ic algo i hm o job-shop scheduling. In . T ans. Ope . Res.
21 (2), 215–246.
Gong, G., Deng, Q., Chiong, R., Gong, X., Huang, H., 2019. An e ec i e meme ic
algo i hm o mul i-objec i e job-shop scheduling. Knowledge-Based Sys ems 182,
104840.
33
G aham, R., Lawle , E., Lens a, J., Kan, A., 1979. Op imiza ion and app oxima ion in
de e minis ic sequencing and scheduling: a su ey. Annals o Disc e e Ma hema ics
5, 287 – 326.
Guyon, O., Lemai e, P., Pinson, E., Ri eau, D., 2014. Sol ing an in eg a ed job-shop
p oblem wi h human esou ce cons ain s. Annals OR 213 (1), 147–171.
Holland, J., 1975. Adap a ion in Na u al and A i icial Sys ems. Uni e si y o Michigan
P ess, Ann A bo .
Hosseinabadi, A. A. R., Vahidi, J., Saemi, B., Sangaiah, A. K., Elhoseny, M., 2019. Ex-
ended gene ic algo i hm o sol ing open-shop scheduling p oblem. So Compu .
23 (13), 5099–5116.
Kolisch, R., 1996. Se ial and pa allel esou ce-cons ained p ojec scheduling me h-
ods e isi ed: Theo y and compu a ion. Eu opean Jou nal o Ope a ional Resea ch
90 (2), 320 – 333.
Kundakc, N., Kulak, O., 2016. Hyb id gene ic algo i hms o minimizing makespan
in dynamic job shop scheduling p oblem. Compu e s & Indus ial Enginee ing 96,
31–51.
Ku di, M., 2015. A new hyb id island model gene ic algo i hm o job shop scheduling
p oblem. Compu e s & Indus ial Enginee ing 88, 273 – 283.
Lee, C., 2018. A e iew o applica ions o gene ic algo i hms in ope a ions manage-
men . Enginee ing Applica ions o A i icial In elligence 76, 1 – 12.
Liao, X., Zhang, H., Koshimu a, M., Huang, R., Yu, W., 2019. Maximum sa is iabil-
i y o mula ion o op imal scheduling in o e loaded eal- ime sys ems. In: Nayak,
A. C., Sha ma, A. (Eds.), PRICAI. Vol. 11670 o Lec u e No es in Compu e Sci-
ence. Sp inge , pp. 618–631.
Ma ques-Sil a, J., He as, F., Jano a, M., P e i i, A., Belo , A., 2013. On compu ing
minimal co ec ion subse s. In: IJCAI. pp. 615–622.
Ma ques-Sil a, J., Menc´
ıa, C., 2020. Reasoning abou inconsis en o mulas. In: IJ-
CAI. pp. 4899–4906.
Mee an, S., Mo shed, M. S., 2012. A hyb id gene ic abu sea ch algo i hm o sol ing
job shop scheduling p oblems: a case s udy. J. In ell. Manu . 23 (4), 1063–1078.
Menc´
ıa, C., Sie a, M. R., Menc´
ıa, R., Va ela, R., 2019. E olu iona y one-machine
scheduling in he con ex o elec ic ehicles cha ging. In eg a ed Compu e -Aided
Enginee ing 26, 49–63.
Menc´
ıa, C., Sie a, M. R., Va ela, R., 2014. In ensi ied i e a i e deepening a* wi h
applica ion o job shop scheduling. J. In elligen Manu ac u ing 25 (6), 1245–1255.
34
Menc´
ıa, R., Menc´
ıa, C., Va ela, R., 2019. Repai ing in easibili y in scheduling ia ge-
ne ic algo i hms. In: de Vicen e, J. M. F., S´
anchez, J. R. ´
A., de la Paz L´
opez, F.,
Toledo-Mo eo, F. J., Adeli, H. (Eds.), F om Bioinspi ed Sys ems and Biomedical
Applica ions o Machine Lea ning - 8 h In e na ional Wo k-Con e ence on he In e -
play Be ween Na u al and A i icial Compu a ion, IWINAC 2019, Alme ´
ıa, Spain,
June 3-7, 2019, P oceedings, Pa II. Vol. 11487 o Lec u e No es in Compu e Sci-
ence. Sp inge , pp. 254–263.
Menc´
ıa, R., Menc´
ıa, C., Va ela, R., 2020. A meme ic algo i hm o es o ing easibili y
in scheduling wi h limi ed makespan. Na u al Compu ing (Online Fi s ).
Menc´
ıa, R., Sie a, M. R., Menc´
ıa, C., Va ela, R., 2015. Meme ic algo i hms o he
job shop scheduling p oblem wi h ope a o s. Appl. So Compu . 34, 94–105.
Menc´
ıa, R., Sie a, M. R., Menc´
ıa, C., Va ela, R., 2015. Schedule gene a ion schemes
and gene ic algo i hm o he scheduling p oblem wi h skilled ope a o s and a bi a y
p ecedence ela ions. In: P oc. o ICAPS. AAAI P ess, pp. 165–173.
Moo e, J. M., 1968. An n job, one machine sequencing algo i hm o minimizing he
numbe o la e jobs. Managemen Science 15 (1), 102–109.
Mus u, S., E en, T., 2018. The single machine scheduling p oblem wi h sequence-
dependen se up imes and a lea ning e ec on p ocessing imes. Applied So Com-
pu ing 71, 291–306.
Nowicki, E., Smu nicki, C., 2005. An ad anced abu sea ch algo i hm o he job shop
p oblem. Jou nal o Scheduling 8, 145–159.
Ono, I., Yamamu a, M., Kobayashi, S., 1996. A gene ic algo i hm o job-shop schedul-
ing p oblems using job-based o de c osso e . In: P oceedings o 1996 IEEE In e -
na ional Con e ence on E olu iona y Compu a ion, Nayoya Uni e si y, Japan, May
20-22, 1996. pp. 547–552.
Palacios, J. J., Vela, C. R., Rod ´
ıguez, I. G., Puen e, J., 2014. Schedule gene a ion
schemes o job shop p oblems wi h uzziness. In: P oc. o ECAI. pp. 687–692.
Peng, B., L, Z., Cheng, T., 2015. A abu sea ch/pa h elinking algo i hm o sol e he
job shop scheduling p oblem. Compu e s & Ope a ions Resea ch 53, 154 – 164.
Tailla d, E., 1993. Benchma ks o basic scheduling p oblems. Eu opean Jou nal o
Ope a ional Resea ch 64 (2), 278–285.
Talbi, E., 2009. Me aheu is ics - F om Design o Implemen a ion. Wiley.
Tan, M., Yang, H. L., Su, Y. X., 2019. Gene ic algo i hms wi h g eedy s a egy o g een
ba ch scheduling on non-iden ical pa allel machines. Meme ic Comp. 11, 439–452.
Vallada, E., Ruiz, R., 2011. A gene ic algo i hm o he un ela ed pa allel machine
scheduling p oblem wi h sequence dependen se up imes. Eu . J. Ope . Res. 211 (3),
612–622.
35
Vil´
ım, P., Labo ie, P., Shaw, P., 2015. Failu e-di ec ed sea ch o cons ain -based
scheduling. In: CPAIOR. pp. 437–453.
Yamada, T., Nakano, R., 1995. A gene ic algo i hm wi h mul i-s ep c osso e o job-
shop scheduling p oblems. In: Fi s In e na ional Con e ence on Gene ic Algo i hms
in Enginee ing Sys ems: Inno a ions and Applica ions. pp. 146–151.
Zhang, C. Y., Li, P., Rao, Y., Guan, Z., 2008. A e y as TS/SA algo i hm o he job
shop scheduling p oblem. Compu e s and Ope a ions Resea ch 35, 282–294.
Zhang, G., Hu, Y., Sun, J., Zhang, W., 2020. An imp o ed gene ic algo i hm o he
lexible job shop scheduling p oblem wi h mul iple ime cons ain s. Swa m and
E olu iona y Compu a ion 54, 100664.
36