Efficient repairs of infeasible job shop problems by evolutionary algorithms

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