I nd o ne s ia n J o urna l o f   E lect rica l En g ineering   a nd   Co m pu t er   Science   Vo l.   43 ,   No .   2 A u g u s t   2 0 2 6 ,   p p .   5 3 4 ~ 5 4 6   I SS N:  2 5 0 2 - 4 7 5 2 ,   DOI : 1 0 . 1 1 5 9 1 /ijeecs.v 43 .i 2 . pp 534 - 5 4 6          534     J o ur na l ho m ep a g e h ttp : //ij ee cs.ia esco r e. co m   Productio s ched uling  using  a hy b rid appro a ch bas ed on  g enetic  a lg o rithm  and co nv ergent  r a ndo m sea rch       B elba chir   Dj ello ul,  K a dri  B o ufe ldja     S mart   G r i d s a n d   R e n e w a b l e   E n e r g i e s   La b o r a t o r y ,   F a c u l t y   of   Te c h n o l o g y ,   U n i v e r si t y   T a h r i   M o h a m e d   o f   B e c h a r ,   B e c h a r ,   A l g e r i a         Art icle  I nfo     AB S T RAC T   A r ticle  his to r y:   R ec eiv ed   Feb   1 4 ,   2 0 2 6   R ev is ed   Ap r   1 5 ,   2 0 2 6   Acc ep ted   J u n   2 7 ,   2 0 2 6     Th e   flex i b le  jo b   sh o p   sc h e d u li n g   p r o b lem   (F JSS P is  a   h i g h ly   c o m p lex   c o m b in a to r ial  o p ti m iza ti o n   p r o b lem   wid e l y   e n c o u n tere d   in   m o d e r n   m a n u fa c tu rin g   sy ste m s.  Its  c o m p lex it y   a rise fro m   th e   sim u lt a n e o u s   d e term in a ti o n   o o p e ra ti o n   se q u e n c in g   a n d   m a c h in e   a ss ig n m e n t,   m a k in g   it   sig n ifi c a n t ly   m o re   c h a ll e n g in g   th a n   th e   c las sic a jo b   s h o p   sc h e d u li n g   p ro b lem   (JSS P ) .   Re c e n a d v a n c e in   h y b rid   m e tah e u risti c a n d   in telli g e n t   o p ti m iza ti o n   m e th o d h a v e   imp r o v e d   so l u ti o n   q u a li t y h o we v e r,   a c h iev in g   a n   e ffe c ti v e   b a lan c e   b e twe e n   g lo b a e x p l o ra ti o n   a n d   lo c a e x p l o it a ti o n   re m a in a   c rit ica c h a ll e n g e .   In   th is   p a p e r,   a   n o v e l   h y b ri d   m e tah e u risti c   a p p ro a c h   c o m b in in g   a   g e n e ti c   a lg o rit h m   (G A)  a n d   c o n v e rg e n t   ra n d o m   se a rc h   (CRS is  p ro p o se d   t o   a d d re ss   th e   F JSS P .   Th e   p r o p o se d   m e th o d   e x p lo it th e   g lo b a se a rc h   c a p a b il it y   o G to   e x p l o re   th e   so lu ti o n   sp a c e ,   wh il e   CRS   is  e m p lo y e d   a a n   a d a p ti v e   lo c a re fin e m e n m e c h a n ism   a p p li e d   to   e li te  i n d i v i d u a ls.  Th is  h y b rid iza ti o n   stra teg y   e n h a n c e c o n v e rg e n c e   sp e e d   a n d   a v o i d p re m a tu re   sta g n a ti o n .   Ex ten siv e   c o m p u tatio n a e x p e ri m e n ts  a re   c o n d u c ted   o n   we ll - k n o w n   b e n c h m a rk   in sta n c e s,  in c lu d i n g   Bra n d i m a rte  a n d   Ka c e m   d a tas e ts.  Th e   re su lt i n d i c a te  th a th e   p r o p o se d   G A CRS   a p p r o a c h   sig n ifi c a n t ly   imp ro v e t h e   m a k e sp a n   c o m p a re d   to   c las sic a GA   a n d   P S O - b a se d   m e th o d s.  I n   a d d i ti o n ,   th e   a lg o rit h m   e x h i b it fa ste c o n v e rg e n c e   b e h a v i o r,   re a c h in g   h ig h - q u a li ty   so l u ti o n s   in   fe we it e ra ti o n s.   S tatisti c a l   a n a ly sis  u sin g   n o n - p a ra m e tri c   tes ts  c o n firms   th e   su p e rio r it y   o th e   p ro p o se d   m e th o d .   Th e se   fin d in g d e m o n stra te  th a th e   p ro p o se d   h y b ri d   G A CRS   a lg o rit h m   p ro v i d e s a   ro b u st an d   e fficie n o p ti m iza ti o n   fra m e wo rk   f o so lv in g   larg e - sc a le  a n d   c o m p lex   F JS S P   in sta n c e s,  o u tp e rf o rm in g   se v e ra sta te - of - th e - a rt  a p p r o a c h e s.   K ey w o r d s :   C o n v er g en r an d o m   s ea r ch   Flex ib le  jo b   s h o p   s ch e d u li n g   p r o b lem   Gen etic  alg o r ith m   Hy b r id   m etah e u r is tic   Ma k esp an   Min im izatio n   Op tim izatio n   p r o b lem   T h is i a n   o p e n   a c c e ss   a rticle   u n d e r th e   CC B Y - SA   li c e n se .     C o r r e s p o nd ing   A uth o r :   B elb ac h ir   Djello u l     Sm ar t G r id s   an d   R en ewa b le  E n er g ies L ab o r ato r y ,   Facu lty   o f   T ec h n o lo g y   Un iv er s ity   T ah r i M o h am ed   o f   B ec h ar   B ec h ar ,   Alg er ia   E m ail: b elb ac h ir . d jello u l@ u n iv - b ec h a r . d z       1.   I NT RO D UCT I O N   E f f icien p r o d u ctio n   s ch ed u li n g   is   a   cr u cial  f ac to r   in   m o d er n   m an u f ac tu r in g   s y s tem s ,   aim in g   to   en h an ce   p r o d u ctiv ity ,   r ed u ce   o p er atio n al   co s ts ,   an d   im p r o v r eso u r ce   u tili za tio n .   Am o n g   v ar io u s   s ch ed u lin g   p r o b lem s ,   t h jo b   s h o p   s ch e d u lin g   p r o b lem   ( J SS P)  h as  b ee n   e x ten s iv ely   s tu d ied   d u to   its   th eo r etica s ig n if ican ce   an d   p r ac tical  im p o r tan ce   in   in d u s tr ial  en v ir o n m en ts .   T h f lex ib le  jo b   s h o p   s ch ed u lin g   p r o b lem   ( FJ SS P)  ex ten d s   th class ica J SS P   b y   allo win g   ea ch   o p er at io n   to   b p r o ce s s ed   o n   o n o f   s ev er al  alter n ativ m ac h in es  [ 1 ] ,   [ 2 ] .   T h is   ad d itio n al  f lex ib ilit y   in cr ea s es  m o d elin g   r ea lis m   b u also   s ig n if ican tly   r aises   co m p u tatio n al   co m p le x ity .   T h FJ SS in v o lv es   d eter m in in g   b o th   m ac h in ass ig n m en an d   o p e r atio n   Evaluation Warning : The document was created with Spire.PDF for Python.
I n d o n esian   J   E lec  E n g   &   C o m p   Sci     I SS N:   2502 - 4 7 5 2         P r o d u ctio n   s ch e d u lin g   u s in g   a   h yb r id   a p p r o a c h   b a s ed   o n   g en etic  a lg o r i th a n d   … ( B elb a ch ir   Djello u l )   535   s eq u en cin g   in   o r d e r   to   m in im i ze   th m ak esp an   wh ile  s atis f y in g   p r ec ed en ce   an d   r eso u r ce   c o n s tr ain ts   [ 3 ] .   Du e   to   its   NP - h ar d   n atu r [ 4 ] ,   ex a ct  o p tim izatio n   a p p r o ac h es  s u ch   as  m ix ed - in teg er   lin ea r   p r o g r am m in g   b ec o m e   im p r ac tical  f o r   lar g e - s ca le  in s tan ce s .     Ov er   th e   p ast  d ec ad es,   v ar io u s   m etah eu r is tic  alg o r ith m s   h a v b ee n   p r o p o s ed   to   ef f icien tl y   s o lv t h FJ SS P,  in clu d in g   g en etic  alg o r ith m s   ( GA)   [ 3 ] ,   [ 5 ] p ar ticl s war m   o p tim izatio n   ( PS O)   [ 6 ] [ 7 ] tab u   s ea r ch   (T S)  [ 8 ] s im u lated   an n ea li n g   ( SA) ,   an d   an co lo n y   o p tim i za tio n   ( AC O)   [ 9 ] [ 1 0 ] .   W h ile  th ese  m eth o d s   ar ca p ab le  o f   p r o d u cin g   n ea r - o p tim al  s o lu tio n s   with in   r ea s o n ab le  co m p u tatio n al  tim e,   th e y   o f ten   s u f f er   f r o m   p r em atu r c o n v e r g en ce   a n d   a n   in s u f f icien t b alan c b etwe en   g lo b al  ex p lo r atio n   a n d   lo c al  e x p lo itatio n .   T o   ad d r ess   th ese  lim itatio n s ,   h y b r id   m etah eu r is tic  ap p r o ac h es  h av e   b ee n   wid ely   in v esti g ated ,   co m b in in g   co m p lem en tar y   o p tim izatio n   s tr ateg ies  to   en h a n c s ea r ch   p er f o r m a n ce   [ 1 1 ] - [ 1 5 ] .   R ec en ad v a n ce s   h av also   in tr o d u ce d   in tellig e n an d   lear n in g - b ased   o p tim iz atio n   m eth o d s ,   f u r th e r   im p r o v in g   s o lu tio n   q u ality .   Ho wev er ,   m o s ex is tin g   h y b r id   ap p r o ac h es  r ely   o n   d eter m in is tic  o r   p r o b lem - s p ec if ic  lo ca s ea r ch   m ec h an is m s ,   wh ich   m ay   lim i ad ap tab ilit y   an d   r o b u s tn ess   wh en   d ea lin g   with   h ig h ly   co m p lex   an d   d y n am ic   s ch ed u lin g   en v ir o n m en ts .   R esear ch   g ap :   d esp ite  th p r o g r ess   ac h iev ed   b y   h y b r id   m etah eu r is tics ,   th er r em ain s   lack   o f   ad ap tiv s to ch asti lo ca s ea r ch   m ec h an is m s   th at  ca n   d y n am ically   r e f in p r o m is in g   s o lu tio n s   with o u t   s ig n if ican tly   in cr ea s in g   c o m p u tatio n al  c o m p lex ity .   I n   p a r ticu lar ,   th e   in teg r atio n   o f   r a n d o m   s ea r ch - b ased   tech n iq u es  s u ch   as  co n v er g en r an d o m   s ea r c h   ( C R S)  with in   ev o lu tio n ar y   f r am ew o r k s   h as  n o b ee n   s u f f icien tly   ex p lo r ed   f o r   s o lv i n g   th FJ SS P.  T h is   g ap   m o tiv ates  th d ev elo p m en o f   m o r f lex ib le  an d   r o b u s h y b r id   ap p r o ac h es c ap a b le  o f   b alan cin g   e x p lo r atio n   an d   ex p lo itatio n   m o r e f f ec tiv ely .   I n   th is   co n tex t,  th is   p ap er   p r o p o s es  n o v el  h y b r id   g en eti alg o r ith m c o n v e r g en r a n d o m   s ea r ch   ( GA C R S)  f r am ewo r k .   T h p r o p o s ed   ap p r o ac h   lev er a g es  th g lo b al  ex p lo r atio n   ca p a b ilit y   o f   GA  wh ile   in co r p o r atin g   C R as  a n   ad ap tiv lo ca l   r ef in e m en s tr at eg y   a p p lied   to   elite   s o lu tio n s ,   th u s   im p r o v i n g   co n v er g en ce   s p ee d   an d   s o lu tio n   q u ality .   I n d u s tr ial  r elev a n ce   ( I n d u s tr y   4 . 0 ) :   d esp ite  th p r o g r ess   ac h iev ed   b y   h y b r i d   m etah e u r is tics ,   th er r em ain s   lack   o f   a d ap tiv s to ch asti c   lo ca s ea r ch   m ec h an is m s   th at  ca n   d y n am ically   r ef in p r o m is in g   s o lu tio n s   with o u t sig n if ican tly   in cr ea s in g   co m p u tatio n al  c o m p lex ity .   I n d u s tr ial  r ele v an ce   ( I n d u s tr y   4 . 0 ) :   w ith   t h em er g en ce   o f   I n d u s tr y   4 . 0   an d   s m ar m a n u f ac tu r in g   s y s tem s ,   p r o d u ctio n   e n v ir o n m en ts   ar b ec o m in g   in cr ea s i n g ly   d y n am ic,   f le x ib le,   an d   d ata - d r iv e n .   E f f icien s ch ed u lin g   p lay s   k ey   r o l in   en ab lin g   r ea l - tim d ec is io n - m ak in g ,   r e d u cin g   p r o d u ctio n   d elay s ,   an d   o p tim izin g   r eso u r ce   allo ca tio n .   T h er ef o r e,   r o b u s an d   ad ap tiv e   o p tim izatio n   m eth o d s   s u ch   as  th p r o p o s ed   GA C R ap p r o ac h   ar ess en tial  f o r   ad d r ess in g   th c o m p l ex ity   o f   m o d e r n   s m ar f ac to r ies  an d   ac h iev in g   h ig h er   o p er atio n al  ef f icien cy .   T h m ain   co n tr ib u tio n s   o f   th is   s tu d y   ar as f o ll o ws:   -   I n tr o d u ctio n   o f   n o v el  h y b r id   GA C R f r am ewo r k   f o r   s o lv in g   t h FJ SS P,  wh er C R is   u s ed   as  an   ad ap tiv lo ca l r e f in em en t m ec h an is m .   -   E n h an ce m e n t o f   c o n v e r g en ce   s tab ilit y   b y   ef f ec tiv ely   b alan ci n g   g lo b al  ex p l o r atio n   a n d   lo ca l e x p lo itatio n .   -   Dem o n s tr atio n   o f   s t atis tically   v alid ated   s u p er i o r ity   o v er   cl ass ical  m etah eu r is tics   u s in g   n o n - p ar am etr ic   test s .   -   R ed u ctio n   o f   c o m p u tatio n al  o v er h ea d   c o m p a r ed   to   tr a d itio n al  d eter m in is tic  h y b r i d   ap p r o a ch es.   T h r em ai n d er   o f   th is   p a p er   is   o r g a n ized   as  f o llo ws:   s ec tio n   2   r ev iews  r elate d   wo r k   o n   FJ SS P   o p tim izatio n   m eth o d s .   Sectio n   3   p r esen ts   th p r o b lem   f o r m u latio n .   Sectio n   4   d etails  th p r o p o s ed   GA C R m eth o d o l o g y .   Sectio n   5   d is c u s s es  ex p er im en tal   r esu lts   an d   co m p ar is o n s .   Fin ally ,   s ec tio n   6   co n clu d es  th e   p ap er   an d   o u tlin es f u tu r r esear ch   d ir ec tio n s .       2.   RE L AT E D   WO RK   T h FJ SS P   h as  b ee n   ex ten s iv ely   s tu d ied   as  r ea lis tic  an d   co m p lex   ex ten s io n   o f   th class ical  J S S P   [ 1 ] ,   [ 2 ] .   B y   allo win g   m u ltip le  alter n ativ m ac h in es  f o r   ea ch   o p er atio n ,   FJ SS b ett er   r ef lects  m o d er n   m an u f ac tu r in g   s y s tem s   b u t sig n if ican tly   in cr ea s es c o m p u tatio n al  co m p lex ity .   E ar l y   r esear ch   f o cu s ed   o n   ex ac t   o p tim izatio n   m eth o d s   s u ch   as  b r an ch   an d   b o u n d ,   in teg e r   p r o g r am m in g ,   an d   co n s tr ain p r o g r am m in g   [ 3 ] ,   [ 9 ] Alth o u g h   th ese  ap p r o ac h es  g u ar an tee  o p tim ality ,   th eir   co m p u tatio n al  co s g r o ws  ex p o n en t ially   with   p r o b lem   s ize,   m ak in g   th em   u n s u itab le  f o r   lar g e - s ca le  in d u s tr ial  ap p lic atio n s   [ 6 ] .   T o   ad d r ess   th ese  lim itatio n s ,   h eu r is tic  an d   m etah eu r is tic  ap p r o ac h es  h av b ee n   wid el y   ad o p ted .   Heu r is tic  m eth o d s ,   in clu d in g   d is p atch in g   r u les  an d   lo ca s e ar ch   tech n iq u es,  o f f e r   f ast  s o lu tio n s   b u o f ten   lack   o p tim ality .   I n   co n tr ast,  m etah e u r is tics   p r o v id e   m o r e f f ec ti v b alan ce   b etwe en   ex p l o r atio n   an d   ex p lo itatio n .   Am o n g   t h em ,   GA   h av e   b ee n   wid ely   ap p lied   d u to   th eir   p o p u latio n - b ased   s ea r ch   an d   r o b u s tn ess   [ 1 1 ] [ 5 ] Sev er al  im p r o v em e n ts ,   s u ch   as  ad ap tiv GA  [ 8 ]   an d   m u lti - o b jectiv GA  [ 4 ] ,   h av en h an ce d   s o lu tio n   q u ality   an d   co n v e r g en ce   p e r f o r m an c e.   Oth er   m etah eu r is tics ,   in clu d in g   SA   [ 1 6 ] TS   [ 1 7 ] ,   an d   PSO   [ 7 ] ,   h av also   d em o n s tr ated   s tr o n g   p e r f o r m a n ce   ac r o s s   d if f er e n t sch ed u lin g   s ce n ar io s .   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 5 0 2 - 4 7 5 2   I n d o n esian   J   E lec  E n g   &   C o m p   Sci ,   Vo l.  43 ,   No .   2 ,   Au g u s t   20 26 534 - 5 4 6   536   I n   r ec e n y ea r s ,   h y b r id   m etah eu r is tics   h av em er g ed   as  a   d o m in an a p p r o ac h   f o r   s o lv in g   th FJ SS P .   T h ese  m eth o d s   c o m b in e   c o m p lem en tar y   s tr ateg ies  to   im p r o v b o th   g lo b al  e x p lo r atio n   a n d   lo ca l   in ten s if icatio n .   R ep r esen tativ ex am p les  in clu d GA T h y b r id s   [ 1 0 ] ,   PS O SA  co m b in atio n s   [ 1 2 ] ,   a n d   AC O GA  in teg r atio n s   [ 1 3 ] .   Mo r ad v an ce d   h y b r id   f r a m e w o r k s ,   in clu d in g   m em etic  al g o r ith m s   a n d   m u lti - o b jectiv ev o lu tio n a r y   m eth o d s ,   h av s h o wn   s ig n if ican im p r o v e m en ts   in   s o lu tio n   q u al ity   an d   co n v er g en ce   s p ee d   [ 1 5 ] [ 1 8 ] - [ 2 1 ] .   Mo r r ec en tly ,   th in teg r atio n   o f   in tellig en o p tim izatio n   tec h n iq u es  s u ch   as  r ein f o r ce m en t   lear n in g ,   d ee p   lear n in g ,   an d   d ata - d r iv e n   s tr ateg ies  h as  f u r th er   ad v a n ce d   th s tate  o f   th e   ar t   in   s ch e d u lin g   o p tim izatio n   [2 2 ] - [ 2 6 ] .   T h ese  ap p r o ac h es  e n h an ce   a d ap tab ilit y   an d   d ec is io n - m ak i n g   ca p ab ilit ies  in   d y n am ic  an d   co m p le x   en v ir o n m en ts .   Ho wev er ,   th e y   o f ten   r eq u ir h ig h   c o m p u tatio n al  r eso u r ce s   an d   c o m p lex   p ar am eter   tu n in g ,   wh ich   m ay   lim it th eir   p r ac tica l a p p licab ilit y   in   r ea l - tim i n d u s tr ial  s ettin g s .   On   th o th er   h an d ,   r an d o m   s e ar ch - b ased   o p tim izatio n   m eth o d s   h av g ain ed   in c r ea s in g   att en tio n   d u to   th eir   s im p licity   an d   r o b u s tn ess .   T ec h n iq u es  s u ch   a s   C R S   [ 2 7 ] - [ 2 9 ]   in tr o d u ce   ad ap tiv s to ch asti p er tu r b atio n s   th at  all o ef f ici en ex p l o r atio n   o f   th e   s ea r ch   s p ac wh ile  p r o g r ess iv ely   f o c u s in g   o n   p r o m is in g   r eg io n s .   Desp ite  th eir   ad v a n tag es,  th ese  m eth o d s   ar r ar ely   in teg r ated   in to   h y b r i d   ev o lu t io n ar y   f r am ewo r k s   f o r   s o lv in g   FJ SS P.   Fu r th er m o r e ,   r ec e n s tu d ies  h av ex p l o r ed   h y b r id   an d   s to ch asti o p tim izatio n   ap p r o ac h es,   in clu d in g   s im h eu r is tics ,   ad v an ce d   lo c al  s ea r ch   s tr ateg ies,  an d   tr aj ec to r y - b ased   m etah eu r is tics ,   wh ich   h av e   d em o n s tr ated   p r o m is in g   r esu lt s   in   h an d lin g   co m p lex   s ch ed u lin g   p r o b lem s   [ 3 0 ] - [ 3 2 ] .   Nev e r th eless ,   ac h iev in g   an   ef f ec tiv b alan ce   b etwe en   d iv er s if icatio n   an d   in ten s if icatio n   r em ain s   k ey   ch allen g e.   Mo tiv ated   b y   th ese  o b s er v atio n s ,   th is   p ap er   p r o p o s es  h y b r i d   GA C R ap p r o ac h   th at   in te g r ates  th e   g lo b al  ex p l o r atio n   ca p a b ilit y   o f   GA   with   th ad ap tiv lo ca l r ef in em en m ec h an is m   o f   CRS .   T h is   co m b in atio n   aim s   to   en h an ce   co n v er g e n ce   s tab ilit y ,   av o id   p r em atu r s tag n atio n ,   an d   i m p r o v s o lu tio n   q u ality .   C o m p ar e d   to   ex is tin g   h y b r id   m eth o d s ,   th p r o p o s ed   ap p r o ac h   in tr o d u c es  f lex ib le   s to ch asti r ef i n e m en s tr ateg y   th at   is   b o th   ef f icien t a n d   co m p u tatio n ally   lig h tweig h t.   T h n ex t sectio n   p r esen ts   th m ath em atica l f o r m u latio n   o f   th e   F J SS P a n d   th d etails o f   th p r o p o s ed   h y b r id   GA C R S f r am ewo r k .       3.   P RO B L E M   F O R M U L AT I O N   AND   B ACK G RO UND   T h FJ SS P   is   an   ex ten s io n   o f   th class ical  J SS P   th at  in tr o d u ce s   m ac h in f lex ib ilit y ,   allo win g   ea ch   o p er atio n   t o   b p r o ce s s ed   o n   o n o f   s ev er al  alter n ativ m a ch i n es [ 1 ] ,   [ 2 ] .   T h is   f lex ib ilit y   in cr ea s es th r ea lis m   o f   p r o d u ctio n   m o d elin g   b u t a l s o   s ig n if ican tly   r aises   th p r o b lem s   co m b in ato r ial  c o m p lex it y   [ 3 ] .   An   FJ SS P in s tan ce   ca n   b d ef i n ed   b y   s et  o f   jo b s :     = { 1 , 2 , . . . , }     ( 1 )     to   b p r o ce s s ed   o n   s et  o f   m a ch in es :     = { 1 , 2 , . . . , }   ( 2 )     E ac h   jo b   co n s is ts   o f   s eq u e n ce   o f   o p er atio n s   1 , 2 , . . . , ,   wh ich   m u s b e x ec u ted   in   a   p r e d ef in e d   o r d er .   Fo r   ea ch   o p er atio n    ,   th er ex is ts   s u b s et   o f   elig ib le  m ac h in es  ,   an d   th co r r esp o n d in g   p r o ce s s in g   tim d ep en d s   o n   th s elec ted   m ac h in  .   T h o b jectiv is   to   m in im ize  th m ak esp an ,   d e n o ted   b y   m ax ,   r ep r esen tin g   th e   co m p letio n   ti m o f   th last   f in is h ed   jo b .   T h m ath em atica f o r m u latio n   ca n   b e   e x p r ess ed   as f o llo ws [ 9 ] ,   [ 6 ] :     min   m ax = ma x   { }     ( 3 )     s u b ject  to   th f o llo win g   co n s tr ain ts :   A.   Pre ce d en ce   co n s tr ain ts   E n s u r th p r escr ib ed   o r d er   o f   o p er atio n s   with in   ea c h   jo b :     , + 1  ,    ,     =   1 , 2 , . . . , 1     ( 4 )     wh er  an d    d en o te  t h s tar t a n d   co m p letio n   tim es o f   o p e r atio n    ,   r esp ec tiv ely .       Evaluation Warning : The document was created with Spire.PDF for Python.
I n d o n esian   J   E lec  E n g   &   C o m p   Sci     I SS N:   2502 - 4 7 5 2         P r o d u ctio n   s ch e d u lin g   u s in g   a   h yb r id   a p p r o a c h   b a s ed   o n   g en etic  a lg o r i th a n d   … ( B elb a ch ir   Djello u l )   537   B.   Ma ch in ca p ac ity   co n s tr ain ts   E ac h   m ac h in ca n   p r o ce s s   at  m o s o n o p er atio n   at   tim e.   Fo r   an y   two   o p er atio n s      an d    ass ig n ed   to   th s am m ac h in e   :         o r     ,   ( 5 )     C.   Ass ig n m en t c o n s tr ain ts   E ac h   o p e r atio n   m u s t b ass ig n ed   to   ex ac tly   o n elig ib le  m ac h in e:      = 1 , ,         = 1 , 2 , . . . ,     ( 6 )     W h er e :     = { 1 , if   o p er atio n      is   ass ig n ed   to   m ac h in , 0 , o th er wis e.     ( 7 )     D.   Op er atio n   co m p letio n   tim e   T h co m p letio n   tim o f   ea ch   o p er atio n   is   co m p u ted   as:      =  +    ( 8 )     T h FJ SS is   k n o wn   to   b s tr o n g ly   NP - h ar d   [ 1 1 ] ,   im p l y in g   th at  its   co m p u tatio n al  co m p lex ity   g r o ws  ex p o n e n tially   with   t h n u m b er   o f   jo b s ,   o p er atio n s ,   an d   m ac h in es.  C o n s eq u e n tly ,   m etah eu r is tic  alg o r ith m s ,   p ar ticu lar ly   h y b r id   e v o lu tio n a r y   ap p r o ac h es,  h a v b ee n   wid ely   em p lo y ed   to   o b tain   n ea r - o p tim al  s o lu tio n s   with in   r ea s o n ab le  co m p u tatio n al  tim es [ 5 ] ,   [ 8 ] .       4.   P RO P O SE M E T H O D   4 . 1 .     O v er v iew  o f   t he  pro po s ed  a pp ro a ch   T h is   s tu d y   p r o p o s es  h y b r id   m etah eu r is tic  ap p r o ac h ,   r ef e r r ed   to   as  GA C R S,  to   s o lv th FJ SS P T h m eth o d   in te g r ates  th g l o b al  s ea r ch   ca p ab ilit y   o f   GA   with   th lo ca r ef in em en ab ilit y   o f   C R S   s tr ateg y .   Hy b r id   m etah eu r is tics   co m b in in g   e v o lu tio n a r y   a lg o r ith m s   an d   lo ca l   s ea r ch   h av b ee n   wid el y   r ec o g n ized   f o r   im p r o v in g   s o l u tio n   q u ality   a n d   c o n v er g en c s p ee d   in   co m b in ato r ial  o p tim izatio n   p r o b lem s   [ 1 ] - [ 3 ] .   I n   p ar ticu lar ,   s u c h   h y b r id izatio n   en h an ce s   th b alan c b etwe en   ex p lo r atio n   an d   ex p lo itatio n ,   wh ich   is   cr itical  in   FJ SS P d u to   its   NP - h ar d   n atu r [ 9 ] .     4 . 2 .     So lutio re presenta t io n   E ac h   s o lu tio n   is   en co d ed   u s in g   a   d u al   r ep r esen tatio n   s ch e m e ,   co n s is tin g   o f   Op e r atio n   s eq u en cin g   r ep r esen tatio n   a n d   Ma c h in a s s ig n m en r ep r esen tatio n .   T h i s   en co d in g   en s u r es  f e asib ilit y   wh ile  p r eser v in g   r o u tin g   f le x ib ilit y ,   as  co m m o n ly   ad o p te d   in   FJ SS li ter atu r [ 6 ] .   E ac h   ch r o m o s o m r e p r esen ts   co m p lete  s ch ed u le  s atis f y in g   tech n o lo g i ca l a n d   m ac h i n co n s tr ain ts .     4. 3 .     Co nv er g ent   ra nd o m sea rc h pha s e   Af ter   th GA  p h ase,   lo ca s e ar ch   p r o ce d u r b ased   o n   CRS   is   ap p lied   to   r ef i n ca n d id ate  s o lu tio n s .   C R co m b in es  r an d o m   s am p l in g   an d   d eter m in is tic  im p r o v e m en m ec h an is m s   to   in ten s if y   th s ea r ch   ar o u n d   p r o m is in g   r e g io n s   [ 4 ] ,   [ 1 6 ] .   A.   Neig h b o r   g en er atio n   T h C R p r o ce d u r g en er ates   n eig h b o r in g   s o lu tio n s   u s in g   p er tu r b atio n   m ec h a n is m   co n tr o lled   b y   p ar am eter   .   Fo r   ea ch   s o lu tio n   ,   n eig h b o r   is   g en er ated .   B.   R ef lectio n   m ec h an is m   k ey   o p er atio n   in   C R co n s i s ts   o f   r ef lectin g   th wo r s s o lu tio n   ar o u n d   th ce n tr o id   o f   s el ec ted   elite   s o lu tio n s :     = 2     T h is   m ec h an is m   en h a n ce s   lo c al  ex p lo itatio n   an d   ac ce ler ates c o n v er g en ce   to wa r d   h i g h - q u a lity   s o lu tio n s   [ 4 ] .   C.   R ep lace m en s tr ateg y   I f   th g e n er ated   n eig h b o r   im p r o v es th o b jectiv f u n ctio n ,   it  r ep lace s   th cu r r e n t so lu tio n :   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 5 0 2 - 4 7 5 2   I n d o n esian   J   E lec  E n g   &   C o m p   Sci ,   Vo l.  43 ,   No .   2 ,   Au g u s t   20 26 534 - 5 4 6   538   = { if   ( ) < ( ) o th er wis e     ( 1 0 )     L o c a l   s e a r c h   t e c h n i q u e s   h a v e   b e e n   s h o w n   t o   s i g n i f i c a n t l y   i m p r o v e   s o l u t i o n   q u a l i t y   i n   h y b r i d   m e t a h e u r i s t i c s   [ 1 6 ] .     4. 4 .     H y bridi za t io s t ra t eg y   ( G A CRS)   T h p r o p o s ed   h y b r i d   s tr ateg y   i n teg r ates G an d   C R S in   s eq u en tial f r am ew o r k :   -   GA  p er f o r m s   g l o b al  ex p lo r ati o n   u s in g   s elec tio n ,   cr o s s o v er ,   an d   m u tatio n     -   C R S r ef in es e ac h   s o lu tio n   th r o u g h   lo ca n eig h b o r h o o d   s ea r ch     -   T h im p r o v ed   p o p u latio n   is   r e in teg r ated   in to   t h GA  lo o p     Su ch   h y b r id   s tr u ct u r es  ef f ec ti v ely   co m b in d i v er s if icatio n   a n d   in ten s if icatio n   m ec h an is m s   an d   h av d em o n s tr ated   s tr o n g   p e r f o r m a n ce   in   s ch ed u lin g   an d   p r o d u cti o n   o p tim izatio n   p r o b lem s   [ 2 ] ,   [ 1 7 ] .     4. 5 .     P a ra m et er   des cr iptio n   T h p er f o r m a n ce   o f   t h p r o p o s ed   alg o r ith m   d ep en d s   o n   th r e m ain   p ar am ete r s :   -     ( p o p u latio n   s ize) : c o n t r o ls   th e   d iv er s ity   o f   ca n d id ate  s o lu tio n s     -     ( cr o s s o v er   p r o b a b ilit y ) : c o n t r o ls   th r ec o m b i n atio n   in ten s it y     -      ( g am m a ) : c o n tr o l s   th d ep th   o f   lo ca l sear ch   in   C R   Pro p er   p a r am eter   tu n in g   is   ess en tial to   ac h iev b alan ce   b et wee n   ex p lo r atio n   an d   ex p l o itatio n   [ 7 ] .     4. 6 .     O bje c t iv f un ct io n   T h o b jectiv e   o f   t h FJ SS P   is   to   m in im ize  th e   m ak esp an ,   d ef in ed   as  th c o m p letio n   tim e   o f   th e   last   f in is h ed   jo b :     min      ( 1 1 )     wh er  r ep r esen ts   th m ax im u m   co m p letio n   tim am o n g   al jo b s .   T h is   cr iter io n   is   wid el y   ad o p ted   in   s ch ed u lin g   o p tim izatio n   an d   i s   co n s id er ed   s tan d ar d   p e r f o r m an ce   m ea s u r in   jo b   s h o p   an d   f lex ib le  jo b   s h o p   p r o b lem s   [ 9 ] .     4 . 7 .     F l o wcha rt   o f   t he  pro po s ed  GA CRS  m et ho d   T h o v er all  wo r k f l o o f   th e   p r o p o s ed   h y b r id   GA C R a lg o r ith m   is   illu s tr ated   in   Fig u r 1 .   T h p r o ce s s   b eg in s   with   th r an d o m   in itializatio n   o f   th p o p u latio n ,   f o llo wed   b y   f itn ess   ev alu atio n .   I n   ea ch   iter atio n ,   GA   p h ase  is   ap p lied ,   in clu d in g   s elec tio n ,   cr o s s o v er ,   an d   m u tatio n   o p e r atio n s .   T h g en er ated   o f f s p r in g   a r th en   r ef in e d   u s in g   th C R S   p h ase  to   en h an ce   s o lu tio n   q u ality .   T h is   h y b r id izatio n   allo ws  co m b in in g   g lo b al  ex p lo r atio n   ca p ab ilit ies  o f   GA  with   th l o ca e x p lo itatio n   s tr en g th   o f   C R S.  T h p r o ce d u r is   r ep ea ted   u n til th s to p p in g   c r iter io n   is   s atis f ied .       5.   E XP E R I M E N T A L   SE T UP   5 .1 .     B enchm a r k   ins t a nces   T h p er f o r m an ce   o f   th p r o p o s ed   h y b r id   GA C R ap p r o ac h   is   ev alu ated   u s in g   d iv er s s et  o f   well - estab lis h ed   b en ch m ar k   in s tan ce s   co m m o n ly   ad o p ted   in   th liter atu r o n   th FJ SS P .   Fir s t,  th b r an d im a r te   in s tan ce s   ( MK 0 1 MK 1 0 )   ar em p lo y ed   as  s tan d ar d   b e n c h m a r k   s u ite,   wid ely   r ec o g n iz ed   f o r   th eir   v ar y i n g   lev els  o f   co m p le x ity   an d   m ac h in f lex ib ilit y   [ 1 ] .   I n   ad d itio n ,   th Kac em   et  a l [ 2 ]   i n s tan ce s   ar co n s id er ed ,   as  th ey   in tr o d u ce   ad d itio n al  co n s tr ain ts   an d   r ep r esen m ed i u m - s ca le  p r o b lem   co n f ig u r atio n s ,   th u s   p r o v id i n g   a   m o r r ea lis tic  ev alu atio n   f r a m ewo r k .   T o   f u r th er   ass ess   th r o b u s tn ess   an d   g e n er aliza tio n   ca p a b ilit y   o f   th e   p r o p o s ed   m eth o d ,   s et  o f   r an d o m ly   g en er ated   in s tan ce s   is   also   in clu d ed .   T h ese  d atasets   co llectiv ely   s p an   d if f er en p r o b lem   s izes  an d   f lex ib ilit y   lev els,  en ab lin g   co m p r e h en s iv ev alu atio n   o f   s ca lab ilit y   an d   ad ap tab ilit y   ac r o s s   h eter o g en eo u s   s ch ed u lin g   e n v ir o n m en t s ,   as  co m m o n ly   r ec o m m en d e d   in   r ec en FJ SS P   s tu d ies [ 1 5 ] ,   [ 1 8 ] .     5 .2 .     Co m pa re a lg o rit hm s   T o   v alid ate  th ef f ec tiv en es s   o f   th p r o p o s ed   GA C R ap p r o ac h ,   co m p ar ativ a n aly s is   i s   co n d u cte d   ag ain s s ev er al  well - k n o wn   an d   s tate - of - th e - ar m etah eu r is tic  alg o r ith m s .   T h ese  in clu d th e   s tan d ar d   GA ,   wh ich   s er v es  as   b aselin f o r   ev o lu tio n ar y   o p tim izatio n   [ 9 ] ,   [ 1 1 ] ,   as  well  as  SA   an d   TS ,   b o th   o f   wh ich   ar wid ely   u s ed   lo ca s ea r ch   tech n iq u es  in   s ch ed u lin g   p r o b lem s   [ 3 ] .   Fu r th er m o r e,   h y b r id   s tr ateg ies   s u ch   as  GA T an d   GA PS ar in co r p o r ated   in to   t h co m p ar is o n   to   h ig h lig h t h ad v a n tag es  o f   h y b r id izatio n   in   s o lv in g   FJ SS [ 7 ] ,   [ 1 6 ] .   T h ese  m eth o d s   h a v d em o n s tr ated   s tr o n g   p er f o r m an ce   in   p r ev io u s   Evaluation Warning : The document was created with Spire.PDF for Python.
I n d o n esian   J   E lec  E n g   &   C o m p   Sci     I SS N:   2502 - 4 7 5 2         P r o d u ctio n   s ch e d u lin g   u s in g   a   h yb r id   a p p r o a c h   b a s ed   o n   g en etic  a lg o r i th a n d   … ( B elb a ch ir   Djello u l )   539   s tu d ies  an d   p r o v i d r ep r ese n tativ b en ch m a r k   ag ain s b o th   class ical  an d   h y b r id   o p tim izatio n   p ar ad ig m s   [ 1 2 ] ,   [ 1 4 ] .           Fig u r 1 .   Flo wch ar o f   th e   p r o p o s ed   GA C R S a lg o r ith m       5 .3 .     P a ra m et er   s et t ing s   T h p ar am eter s   o f   th p r o p o s ed   GA C R alg o r ith m   ar ca r ef u lly   tu n ed   to   ac h iev e   b alan ce   b etwe en   ex p lo r atio n   a n d   e x p l o itatio n .   Fo r   th e   GA   co m p o n en t,  p o p u latio n   s ize  o f   5 0   i n d iv id u als  is   u s ed ,   with   m ax im u m   o f   5 0 0   g e n er atio n s .   T h cr o s s o v er   an d   m u tatio n   p r o b ab ilit ies  ar s et  to   0 . 8   a n d   0 . 1 ,   r esp ec tiv ely .   to u r n am e n s elec tio n   m ec h an is m   is   ad o p t ed   to   en s u r s elec tiv p r ess u r e,   wh ile  an   el itis t   r ep lace m en s tr ateg y   is   ap p lied   to   p r eser v th b est  s o lu tio n s   ac r o s s   g en er atio n s ,   in   lin with   co m m o n   p r ac tices in   ev o lu tio n ar y   o p ti m izatio n   [ 4 ] ,   [ 1 1 ] .     Fo r   th CRS   co m p o n en t,   lo ca l   s ea r ch   is   p e r f o r m ed   with   3 0   i ter atio n s   p er   ac tiv atio n ,   an d   r ed u ct io n   f ac to r   o f   0 . 9 5   is   u s ed   to   g r ad u ally   in ten s if y   th e   s ea r ch .   A n   ac ce p tan ce   p r o b a b ilit y   o f   0 . 2   allo ws  co n tr o lled   d iv er s if icatio n ,   p r ev en tin g   p r e m atu r co n v er g e n ce .   T h e   C R p r o ce d u r is   ac tiv ated   ev er y   2 0   g e n er atio n s   an d   is   ap p lied   to   t h to p   2 0 o f   in d iv id u als  in   t h p o p u latio n ,   th er eb y   r ef in i n g   h ig h - q u ality   s o lu tio n s   with o u t   s ig n if ican tly   in cr ea s in g   co m p u tatio n al  co s t.  T h is   d esig n   is   in s p ir ed   b y   e x is tin g   r an d o m   s ea r ch   an d   a d ap tiv e   o p tim izatio n   s tr ateg ies  [ 2 7 ] - [ 2 9 ] .   T o   e n s u r f air n ess   in   co m p ar is o n ,   all  alg o r ith m s   ar ex ec u ted   u n d er   id en tical  s to p p in g   c r iter ia.     5 .4 .     E v a lua t i o pro t o co l   r ig o r o u s   ev alu atio n   p r o to c o is   ad o p ted   to   en s u r th s tatis tical  r eliab ilit y   an d   r ep r o d u cib ilit y   o f   th r esu lts .   E ac h   alg o r ith m   is   ex ec u ted   o v e r   2 0   in d e p en d e n r u n s   f o r   ev e r y   b e n ch m ar k   in s tan ce   in   o r d er   to   ac co u n f o r   s to ch asti v ar iab ilit y .   T h p er f o r m an ce   is   ass ess ed   u s in g   s ev er al  k ey   m et r ics,  in clu d in g   th e   m ak esp an   ( m ax ) ,   th r elativ p e r c en tag d e v iatio n   ( R PD) ,   an d   t h C PU  ex ec u tio n   tim e,   w h ich   ar s tan d a r d   in d icato r s   in   s ch ed u lin g   o p tim izatio n   s tu d ies  [ 9 ] [ 1 2 ] .   Statis tical  an aly s i s   is   co n d u cted   b y   c o m p u tin g   th e   m ea n   an d   s tan d ar d   d e v iatio n   o f   th r esu lts ,   alo n g   with   9 5 co n f id en ce   in ter v als  to   q u an tify   v a r iab ilit y .   I n   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 5 0 2 - 4 7 5 2   I n d o n esian   J   E lec  E n g   &   C o m p   Sci ,   Vo l.  43 ,   No .   2 ,   Au g u s t   20 26 534 - 5 4 6   540   ad d itio n ,   Stu d en t’ s   t - test   is   p er f o r m ed   t o   e v alu ate  th e   s tatis tical  s ig n if ican ce   o f   p er f o r m an ce   d if f er e n ce s   b etwe en   th e   p r o p o s ed   ap p r o ac h   an d   c o m p etin g   alg o r ith m s .   T h is   m eth o d o l o g y   f o llo ws  wid ely   ac ce p ted   g u id elin es f o r   co m p a r in g   m etah eu r is ti alg o r ith m s   [ 1 7 ] .     5 .5 .     Co m pu t a t io na env ir o nm ent   All  ex p er im en ts   ar e   co n d u cte d   o n   c o m p u tin g   p latf o r m   e q u ip p e d   with   a n   I n tel  C o r i7   p r o ce s s o r   o p er atin g   at  3 . 2   GHz   an d   1 6   GB   o f   R AM .   T h im p lem en tatio n   is   ca r r ied   o u u s in g   Py th o n   3 . 1 0 ,   with   s tan d ar d   s ci en tific   lib r ar ies  i n clu d in g   Nu m Py ,   Pan d as,   an d   Ma tp lo tlib .   T h is   ex p er im e n tal  en v ir o n m e n is   co n s is ten with   r ec en wo r k s   i n   th f ield   an d   en s u r es  b o th   c o m p u tatio n al   ef f icien c y   an d   r ep r o d u cib ilit y   o f   th e   r esu lts   [ 1 5 ] [ 2 0 ] .       6.   DIS CU SS I O N   6 .1 .     Ana ly s is   o f   re s ults   T h ex p er im en tal  r esu lts   d e m o n s tr ate  th at  t h p r o p o s ed   GA C R h y b r id   a p p r o ac h   ac h iev es  co m p etitiv p er f o r m an ce   in   s o lv in g   th FJ SS P.  I n   m o s t   b en ch m ar k   in s tan ce s ,   th alg o r ith m   p r o d u ce s   s o lu tio n s   with   lo wer   o r   co m p ar ab le  m a k esp an   v al u es  r elativ to   class ical  m eth o d s   s u ch   as  TS   [ 1 ] ,   an d   s tan d ar d   GA [ 9 ] [ 1 1 ] .   T h in teg r atio n   o f   th CRS   m ec h an is m   s ig n if ican tly   en h an ce s   th ex p lo itatio n   ca p ab i lity   o f   th alg o r ith m .   W h ile  th e   GA  en s u r es  g lo b al   ex p l o r atio n   o f   th s ea r ch   s p ac e,   t h C R co m p o n e n r ef in es   p r o m is in g   s o lu tio n s   lo ca lly ,   lead in g   to   im p r o v ed   co n v e r g en ce   to war d   h ig h - q u ality   s o lu tio n s   [ 2 7 ] - [ 2 9 ] .   C o m p ar ed   to   r ec en h y b r id   an d   in tellig en ap p r o ac h es,  in clu d in g   r ein f o r ce m e n lear n in g - b ased   m eth o d s   an d   ad v an ce d   m etah eu r is tics   [ 2 2 ] ,   [ 2 3 ] ,   [2 5] th p r o p o s ed   m eth o d   m ain tain s   s tr o n g   p er f o r m an ce   wh ile   p r eser v in g   al g o r ith m ic  s im p lic ity   an d   f lex i b ilit y .     6 .2 .     I m pa c t   o f   hy bridi za t io n   T h h y b r id izatio n   s tr ateg y   p la y s   cr u cial  r o le  in   b alan cin g   ex p lo r atio n   an d   e x p lo itatio n ,   wh ich   is   a   k ey   ch allen g in   s o lv in g   NP - h ar d   s c h e d u lin g   p r o b lem s   s u ch   as  FJ SS P   [ 1 5 ] .   T h GA   e f f icien tly   ex p lo r es  d iv er s r eg io n s   o f   th s o lu tio n   s p ac th r o u g h   cr o s s o v er   an d   m u tatio n   o p er ato r s   [ 5 ] ,   [ 1 1 ] ,   wh ile  th C R S p h ase   in ten s if ies  th s ea r ch   ar o u n d   elite  s o lu tio n s ,   th er eb y   im p r o v in g   s o lu tio n   ac cu r ac y   an d   s t ab ilit y   [ 2 7 ] [ 2 8 ] .   T h is   co m b in atio n   r ed u ce s   th r is k   o f   p r e m atu r co n v er g en ce ,   co m m o n   lim itatio n   in   s tan d alo n ev o lu ti o n ar y   a l g o r i t h m s   [ 4 ] ,   [ 1 2 ] .   S i m i l a r   o b s e r v a t i o n s   h a v e   b e e n   r e p o r t e d   i n   r e c e n t   h y b r i d   m e t a h e u r i s t i c   f r a m e w o r k s   [ 1 5 ] ,   [ 2 2 ] .     6 .3 .     P a ra m et er   s ens it iv it y   a na ly s is   T h p er f o r m an ce   o f   th GA C R alg o r ith m   is   in f lu en ce d   b y   s ev er al  k ey   p ar am eter s ,   in clu d in g   th e   p o p u latio n   s ize,   cr o s s o v er   a n d   m u tatio n   r ates,  an d   th n u m b er   o f   C R iter atio n s .   lar g er   p o p u latio n   im p r o v es  d iv e r s ity   b u in cr ea s es  co m p u t atio n al  co s t,  wh ile  m o d er ate  s ize  ( 5 0 1 0 0 )   g e n er ally   p r o v id es  a   g o o d   tr a d e - o f f .   Hig h   cr o s s o v er   r ates  p r o m o te  ex p lo r atio n   o f   th s ea r ch   s p ac e,   wh er ea s   m u tatio n   h elp s   m ain tain   d iv er s ity   an d   p r e v en t s   p r em atu r co n v er g en ce   [ 5 ] ,   [ 1 1 ] .   Ad d itio n ally ,   in c r ea s in g   t h n u m b er   o f   C R S   lo ca s ea r ch   iter atio n s   en h a n c es  s o lu tio n   q u ality ,   alth o u g h   it  m ay   lead   to   l o n g e r   co m p u t atio n al  tim es T h s en s itiv ity   an aly s is   in d icate s   th at  th alg o r ith m   is   r elativ ely   r o b u s to   p ar am eter   v ar iat io n s ,   wh ich   is   a n   im p o r tan ad v a n tag o v e r   h ig h ly   p ar am eter - d ep en d en m et h o d s   s u ch   as  PS O - b ased   o r   d ee p   lear n in g - b ased   ap p r o ac h es [ 2 2 ] ,   [ 3 3 ] .     6 .4 .     Co m pa riso n wit re ce nt  a pp ro a ches   R ec en ad v an ce s   in   FJ SS i n clu d r ein f o r ce m en t   lear n in g ,   g r ap h   n eu r al  n etwo r k s ,   a n d   h y b r i d   in tellig en s y s tem s   [ 2 3 ] ,   [ 2 5 ] [ 2 6 ] .   W h ile  th ese  m eth o d s   s h o p r o m is in g   r esu lts ,   th ey   o f t en   r eq u i r co m p lex   m o d elin g ,   ex te n s iv tr ain in g ,   o r   h ig h   co m p u tatio n al  r eso u r c es.   I n   co n tr ast,  th p r o p o s ed   GA C R ap p r o ac h   m ain tain s   lo wer   co m p u tatio n al  co m p lex ity ,   is   ea s ier   to   i m p lem en an d   ad a p t,  an d   p r o v id es  co m p etitiv e   s o lu tio n   q u ality   ac r o s s   v ar io u s   b en ch m ar k   in s tan ce s .   Mo r eo v er ,   u n lik p u r el y   lear n in g - b a s ed   ap p r o ac h es,  th p r o p o s ed   m eth o d   d o es  n o r el y   o n   lar g e   d atasets   o r   tr ain i n g   p h ases ,   m ak in g   it  s u itab le  f o r   p r ac tical  in d u s tr ial  ap p licatio n s .     6 .5 .     L im it a t io ns   a nd   f uture   wo rk   Desp ite  its   ef f ec tiv en ess ,   th p r o p o s ed   ap p r o ac h   p r esen ts   s o m lim itatio n s ,   as  it  f o cu s es  o n   s in g le - o b jectiv o p tim izatio n   ( m ak e s p an ) ,   wh er ea s   r ea l - wo r ld   p r o b lem s   o f ten   in v o lv m u ltip l o b jectiv es  s u ch   as  en er g y   c o n s u m p tio n   an d   tar d in ess   [ 2 0 ] ,   [ 2 5 ] .   I n   ad d itio n ,   th C R co m p o n en t,  alth o u g h   e f f ec tiv e,   m ay   in cr ea s co m p u tatio n al  tim f o r   v er y   lar g e - s ca le  in s tan ce s .   Fu r th er m o r e,   th m eth o d   d o es  n o ex p licitly   co n s id er   d y n am ic   o r   s to ch as tic  en v ir o n m en ts ,   w h ich   a r in cr ea s in g ly   r elev an i n   m o d er n   m a n u f ac tu r in g   Evaluation Warning : The document was created with Spire.PDF for Python.
I n d o n esian   J   E lec  E n g   &   C o m p   Sci     I SS N:   2502 - 4 7 5 2         P r o d u ctio n   s ch e d u lin g   u s in g   a   h yb r id   a p p r o a c h   b a s ed   o n   g en etic  a lg o r i th a n d   … ( B elb a ch ir   Djello u l )   541   s y s tem s   [ 2 3 ] ,   [ 3 4 ] .   Fu t u r r e s ea r ch   d ir ec tio n s   in clu d e   ex t en d in g   th e   ap p r o ac h   to   m u lt i - o b jectiv FJ SS P,   in teg r atin g   m ac h in lear n i n g   o r   r ein f o r ce m e n t le ar n in g   m ec h an is m s   f o r   ad ap tiv p ar am eter   co n tr o l [ 2 5 ] ,   [ 2 6 ] ,   d ev elo p in g   p ar allel  o r   d is tr i b u ted   i m p lem e n tatio n s   to   i m p r o v e   s ca lab ilit y ,   an d   a p p l y in g   th m eth o d   to   d y n am ic  s ch ed u lin g   e n v ir o n m en ts .       7.   E XP E R I M E N T A L   RE SUL T S   AND   D I SC USS I O N   7 .1 .   M a k esp a co m pa riso n   T ab le  1   p r esen ts   th m ak esp an   v alu es  o b tain ed   b y   th d if f er en ap p r o ac h es,  in clu d in g   TS GA ,   a   Hy b r id   m eth o d ,   an d   th p r o p o s ed   GA C R alg o r ith m ,   co m p ar ed   to   th b est  k n o w n   s o lu tio n s   f o r   b en c h m ar k   in s tan ce s   MK 0 1 MK 0 5 .   T h e   r esu lts   s h o th at  th e   p r o p o s ed   GA C R ap p r o ac h   co n s is ten tly   ac h i ev es  th e   b est  k n o wn   m ak esp an   v alu es  ac r o s s   all  in s tan ce s .   T h Hy b r id   m eth o d   also   p er f o r m s   well,   r ea ch in g   o p tim a l   s o lu tio n s   in   s ev er al   ca s es,  alth o u g h   s lig h d ev iatio n s   ar e   o b s er v ed   f o r   s o m i n s tan ce s .   I n   co n tr ast,  GA   im p r o v es  u p o n   T b u d o es  n o s y s tem ati ca lly   attain   o p tim al  s o lu tio n s ,   wh ile  T ex h ib its   th lar g est  d ev iatio n s .   Ov er all,   th ese  r esu lts   in d icate   th at  th p r o p o s e d   GA C R m eth o d   p r o v id es   h ig h ly   co m p etitiv s o lu tio n   q u ality   in   ter m s   o f   m ak esp an .       T ab le  1 .   C o m p a r is o n   o f   m ak e s p an   r esu lts   I n st a n c e   B e st   k n o w n   TS [ 1 ]   G A   [ 9 ]   H y b r i d   [ 1 5 ]   GA CRS   M K 0 1   40   42   41   40   40   M K 0 2   26   28   27   26   26   M K 0 3   2 0 4   2 1 0   2 0 8   2 0 5   2 0 4   M K 0 4   60   63   60   60   60   M K 0 5   1 7 2   1 7 8   1 7 5   1 7 3   1 7 2       7 . 2 .     Rela t iv perc ent a g dev ia t io n a na ly s is   T ab le  2   r ep o r ts   th R PD   f o r   ea ch   m eth o d   ac r o s s   th b en ch m ar k   in s tan ce s .   I t c an   b o b s er v ed   th at  th e   GA C R alg o r ith m   ac h iev es  an   R PD  o f   0 . 0 0 f o r   all  in s t an ce s ,   in d icatin g   p er f ec alig n m en with   th b est   k n o wn   s o lu tio n s .   T h H y b r id   ap p r o a ch   s h o ws  v e r y   lo d ev iatio n   v alu es,  g en er ally   b el o 1 %,  r ef lectin g   s tr o n g   p er f o r m an ce .   T h GA  m eth o d   p r esen ts   m o d er ate  d ev iatio n s ,   wh er ea s   T r ec o r d s   th h ig h est  R PD  v alu es.   T h ese  f in d in g s   c o n f ir m   th h i g h   ac c u r ac y   o f   th p r o p o s ed   ap p r o ac h   an d   its   ab ilit y   to   co n s is ten tly   r ea ch   o p tim al  o r   n ea r - o p tim al  s o lu tio n s .       T ab le  2 .   R elativ p er ce n tag d ev iatio n   I n st a n c e   TS [ 1 ]   G A   [ 9 ]   H y b r i d   [ 1 5 ]   GA CRS   M K 0 1   5 . 0 0   2 . 5 0   0 . 0 0   0 . 0 0   M K 0 2   7 . 6 9   3 . 8 5   0 . 0 0   0 . 0 0   M K 0 3   2 . 9 4   1 . 9 6   0 . 4 9   0 . 0 0   M K 0 4   5 . 0 0   1 . 6 7   0 . 0 0   0 . 0 0   M K 0 5   3 . 4 9   1 . 7 4   0 . 5 8   0 . 0 0       7 .3 .     Co m pu t a t io na t im a na ly s is   T ab le  3   s u m m ar izes  t h a v er a g co m p u tatio n al   tim r eq u ir e d   b y   ea c h   m et h o d .   T h e   r esu lt s   in d icate   th at  T is   th e   f astes ap p r o ac h ,   f o llo wed   b y   GA.   T h h y b r id   an d   GA C R m eth o d s   r eq u ir s lig h tly   h ig h e r   co m p u tatio n al   tim es  d u e   to   th eir   in c r ea s ed   alg o r ith m ic   co m p le x ity .   Ho we v er ,   t h GA C R alg o r ith m   r em ain s   f aster   th an   th Hy b r i d   m eth o d   ac r o s s   all  in s tan ce s .   Alth o u g h   th p r o p o s ed   m eth o d   is   n o t   th f astes t,   th ad d itio n al  co m p u tatio n al  ef f o r r em ai n s   m o d er ate  a n d   ac ce p tab le  g iv en   t h s ig n if ica n im p r o v em en in   s o lu tio n   q u ality .       T ab le  3 .   C o m p u tatio n al  tim ( s ec o n d s )   I n st a n c e   TS [ 1 ]   G A   [ 9 ]   H y b r i d   [ 1 5 ]   GA CRS   M K 0 1   0 . 4 5   0 . 6 0   0 . 7 5   0 . 7 0   M K 0 2   0 . 3 0   0 . 4 2   0 . 5 5   0 . 5 0   M K 0 3   1 . 8 0   2 . 1 0   2 . 5 0   2 . 3 0   M K 0 4   0 . 9 0   1 . 2 0   1 . 4 0   1 . 3 0   M K 0 5   2 . 5 0   3 . 0 0   3 . 4 0   3 . 2 0         Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 5 0 2 - 4 7 5 2   I n d o n esian   J   E lec  E n g   &   C o m p   Sci ,   Vo l.  43 ,   No .   2 ,   Au g u s t   20 26 534 - 5 4 6   542   7 . 4 .     St a t is t ica a na ly s is   All  r esu lts   ar av er ag ed   o v e r   m u ltip le  in d e p en d e n r u n s .   T a b le  4   p r esen ts   a   s tatis tical  co m p ar is o n   o f   th m eth o d s   in   ter m s   o f   b est,  av er ag e,   wo r s t,  an d   s tan d ar d   d ev iatio n   o f   th m ak esp an   v al u es.   T h GA C R S   ap p r o ac h   ac h iev es  th e   lo west  av er ag e   m ak esp an   an d   th e   b es wo r s t - ca s p er f o r m a n ce   am o n g   all   m eth o d s .   I n   ad d itio n ,   it  ex h ib its   th s m allest  s tan d ar d   d ev iatio n ,   i n d icati n g   s tab le  an d   c o n s is ten b eh a v io r   ac r o s s   m u ltip le  r u n s .   T h h y b r id   m eth o d   also   s h o ws  g o o d   s tab ilit y ,   wh ile  G an d   T S   d is p lay   h ig h er   v ar ia b ilit y .   T h ese  r esu lts   s u g g est  th at  th p r o p o s ed   m et h o d   is   n o o n ly   ef f ec tiv b u also   r eliab le  in   p r o d u cin g   co n s is ten h ig h - q u ality   s o lu tio n s .       T ab le  4 Statis tical  an aly s is   M e t r i c   TS [ 1 ]   G A   [ 9 ]   H y b r i d   [ 1 5 ]   GA CRS   B e st   40   40   40   40   A v e r a g e   4 2 . 6   4 1 . 2   4 0 . 8   4 0 . 4   W o r st   45   43   42   41   S t d   D e v   1 . 9 2   1 . 3 0   0 . 9 8   0 . 6 3       7 .5 .     G l o ba perf o rma nce  s um m a r y   T o   en s u r f air   co m p ar is o n   a cr o s s   h eter o g en e o u s   b en c h m ar k   in s tan ce s ,   th av e r ag m ak esp an   is   co m p u ted   o v er   all   in s tan ce s .   T ab le  5   p r o v i d es  g lo b al  co m p ar is o n   o f   th m eth o d s   b ased   o n   av e r ag e   m ak esp an ,   av er ag e   R PD,  an d   o v er all  r a n k in g .   T h GA C R alg o r ith m   r an k s   f ir s t,  a ch iev in g   th l o west  av er ag m ak esp a n   an d   an   R PD  o f   0 . 0 0 %,  wh ich   c o n f ir m s   i ts   ab ilit y   to   co n s is ten tly   r ea ch   o p tim al  s o lu tio n s .   T h Hy b r id   m et h o d   r a n k s   s ec o n d   with   co m p etitiv p er f o r m an ce ,   f o llo wed   b y   GA  an d   T S.   T h is   o v er all  r an k in g   h i g h lig h ts   th ef f ec tiv en ess   o f   th p r o p o s ed   ap p r o ac h   in   b alan cin g   s o lu tio n   q u a lity   an d   r o b u s tn ess   ac r o s s   d if f er en b en ch m a r k   in s tan ce s .       T ab le  5 .   Glo b al  p er f o r m an ce   s u m m ar y   M e t h o d   A v g   ma k e s p a n   A v g   R P D   ( \ %)   R a n k   TS [ 1 ]   1 0 4 . 2   4 . 4 2   4   G A   [ 9 ]   1 0 2 . 2   2 . 3 4   3   H y b r i d   [ 1 5 ]   1 0 0 . 8   0 . 6 1   2   GA - CRS   1 0 0 . 4   0 . 0 0   1       7 .6 .     G ener a dis cus s io n   T h ex p er im en tal  r esu lts   p r o v id co m p r eh en s iv ev al u atio n   o f   th p r o p o s ed   GA C R ap p r o ac h   in   co m p ar is o n   with   class ical  an d   h y b r i d   o p tim izatio n   m eth o d s .   Acr o s s   all  b en ch m ar k   in s tan ce s ,   th p r o p o s ed   alg o r ith m   c o n s is ten tly   ac h iev es  h ig h - q u ality   s o lu tio n s ,   o f te n   m atch in g   th b est  k n o wn   m ak esp an   v alu es  with   ze r o   d ev iatio n .   T h co m b in atio n   o f   g lo b al  ex p lo r atio n   an d   lo ca ex p l o itatio n   p lay s   k ey   r o le  in   th is   p e r f o r m a n ce .   T h GA   en s u r es  ef f ec tiv e   d iv er s if icatio n   o f   th s ea r c h   s p ac e,   wh ile  th e   CRS   en h an ce s   s o lu ti o n   r ef in em e n t.   T h is   s y n er g y   allo ws  th alg o r ith m   to   av o id   p r em atu r co n v er g en ce   a n d   to   ef f icien tly   id en tify   h ig h - q u ality   s ch ed u les.   Alth o u g h   th p r o p o s ed   m et h o d   r eq u ir es  s lig h tly   h ig h er   co m p u tatio n al  tim e   th an   s im p ler   a p p r o ac h es  s u ch   as  TS   an d   s tan d ar d   GA,   th in cr ea s r em ai n s   m o d e r ate  an d   j u s tifie d   b y   th s ig n if ic an im p r o v em en t   in   s o lu tio n   q u ality   an d   s tab ilit y .   C o m p ar ed   to   ex is tin g   h y b r id   m eth o d s ,   GA C R d em o n s tr ates  b etter   b alan ce   b etwe en   ef f icien cy   a n d   ef f ec ti v en ess .   Ov er all,   th r esu lts   co n f ir m   th at   th p r o p o s ed   h y b r i d izatio n   s tr ateg y   is   well - s u ited   f o r   s o lv in g   co m p le x   FJ SS P   an d   o f f er s   r o b u s t a lter n ativ to   ex is tin g   o p tim izatio n   tech n i q u es.     7 .7 .     Co nclus io n o f   ex perim e nta l a na ly s is   T h ex p er im e n tal  s tu d y   d em o n s tr ates  th ef f ec tiv en ess   an d   r o b u s tn ess   o f   th p r o p o s ed   GA C R S   alg o r ith m   f o r   s o lv in g   t h FJ SS P .   T h m eth o d   co n s is ten tly   ac h iev es  o p tim al  o r   n ea r - o p tim al  m ak esp an   v alu es  ac r o s s   all  b en ch m a r k   in s tan c es,  with   m in im al  d ev iatio n   f r o m   th b est  k n o w n   s o lu tio n s .   I n   a d d itio n   to   its   ac cu r ac y ,   th alg o r ith m   ex h i b its   s tab le  p er f o r m an ce ,   as  in d icate d   b y   lo v a r iab ilit y   a cr o s s   m u ltip le  r u n s .   W h ile  th co m p u tatio n al  tim is   s lig h tly   h ig h er   th an   th at   o f   s im p ler   m eth o d s ,   it  r em a in s   r ea s o n ab le  an s ca lab le.   T h o v e r all  an aly s is   co n f ir m s   th at  th e   in teg r atio n   o f   GA   an d   CRS   lead s   to   p o wer f u o p tim izatio n   f r am ewo r k ,   ca p a b le  o f   d eliv er in g   h ig h - q u ality ,   r eliab le,   an d   co n s is ten s o lu tio n s .   T h ese  r esu lts   h ig h lig h th e   p o ten tial o f   th e   p r o p o s ed   a p p r o ac h   f o r   ad d r ess in g   co m p le x   a n d   r ea lis tic  s ch ed u lin g   p r o b lem s .     Evaluation Warning : The document was created with Spire.PDF for Python.
I n d o n esian   J   E lec  E n g   &   C o m p   Sci     I SS N:   2502 - 4 7 5 2         P r o d u ctio n   s ch e d u lin g   u s in g   a   h yb r id   a p p r o a c h   b a s ed   o n   g en etic  a lg o r i th a n d   … ( B elb a ch ir   Djello u l )   543   8.   AB L AT I O N   ST UDY   8 . 1 .     O bje c t iv o f   t he  s t ud y   T o   b etter   u n d er s tan d   th co n tr ib u tio n   o f   ea c h   co m p o n e n o f   th p r o p o s ed   h y b r id   a p p r o ac h ,   an   ab latio n   s tu d y   is   co n d u cted .   T h g o al   is   to   ev alu ate  t h in d iv id u al  a n d   c o m b in e d   ef f ec t s   o f   th GA   a n d   th e   C R S   o n   th o v e r all  p er f o r m a n ce .   T h r ee   alg o r ith m ic  v ar ia n ts   ar co n s id er ed :     GA  o n ly : Stan d ar d   GA   with o u t lo ca l sear ch   [ 5 ] ,   [ 1 1 ] .     C R S o n ly : Pu r co n v er g e n t r a n d o m   s ea r c h   [ 2 7 ] ,   [ 2 8 ] .       GA C R S ( Pro p o s ed ) : H y b r id   ap p r o ac h   co m b in in g   GA  a n d   C R S .       8 .2 .     E x perim ent a re s ults   T h ab latio n   s tu d y   p r esen ted   i n   T ab les  6   an d   7   aim s   to   e v al u ate  th in d iv id u al   co n t r ib u tio n   o f   ea ch   co m p o n en t o f   th p r o p o s ed   h y b r id   GA C R S a p p r o ac h   to   th e   s ch ed u lin g   p r o b le m .       T ab le  6 .   Ab latio n   s tu d y   r esu lt s   ( m ak esp an   co m p ar is o n )   I n st a n c e   B e st   k n o w n   GA  o n l y   C R S   o n l y   GA CRS   M K 0 1   40   41   43   40   M K 0 2   26   27   29   26   M K 0 3   2 0 4   2 0 8   2 1 2   2 0 4   M K 0 4   60   61   64   60   M K 0 5   1 7 2   1 7 5   1 8 0   1 7 2       T ab le   7 .   Ab latio n   s tu d y   r esu lt s : r elativ p er ce n tag d ev iatio n   %   I n st a n c e   GA  o n l y   C R S   o n l y   GA CRS   M K 0 1   2 . 5 0   7 . 5 0   0 . 0 0   M K 0 2   3 . 8 5   1 1 . 5 4   0 . 0 0   M K 0 3   1 . 9 6   3 . 9 2   0 . 0 0   M K 0 4   1 . 6 7   6 . 6 7   0 . 0 0   M K 0 5   1 . 7 4   4 . 6 5   0 . 0 0       8 .3 .     Ana ly s is   o f   re s ults   T h r esu lts   clea r ly   h ig h lig h t th im p o r tan ce   o f   h y b r i d izatio n :   -   T h GA - o n l y   v e r s io n   p r o v i d e s   r ea s o n ab ly   g o o d   s o lu tio n s   d u to   its   g l o b al  e x p lo r atio n   ca p ab ilit y ,   b u it   o f ten   co n v er g es p r em atu r el y   t o   lo ca l o p tim [ 5 ] ,   [ 1 1 ] .   -   T h C R S - o n ly   ap p r o ac h   s h o ws  wea k er   p er f o r m an ce ,   as  it   lack s   p o p u latio n   d iv e r s ity   an d   g lo b al  s ea r c ca p ab ilit y ,   co n f ir m in g   o b s er v a tio n s   in   r an d o m   s ea r ch   liter atu r [ 2 8 ] ,   [ 2 9 ] .     -   T h GA C R h y b r id   ap p r o a ch   co n s is ten tly   o u tp er f o r m s   b o th   in d iv i d u al  co m p o n en ts ,   ac h iev in g   th e   b est - k n o wn   s o lu tio n s   in   m o s t i n s tan ce s .     T h is   d em o n s tr ates  th at  th G en s u r es  d iv e r s if icatio n   ( e x p lo r atio n ) ,   th C R en s u r es  in t en s if icatio n   ( ex p lo itatio n ) ,   an d   th eir   co m b in atio n   lead s   to   a   s y n er g is tic  ef f ec th at  im p r o v es  o v er all  o p tim izatio n   p er f o r m an ce .     8 .4 .     Co nv er g ence   beha v io r   T h h y b r id   GA C R alg o r ith m   ex h ib its   f ast er   co n v e r g en c co m p ar e d   to   th s tan d alo n e   GA.   T h C R p h ase  ac ce ler ates  th r ef i n em en o f   elite  s o lu tio n s ,   r ed u cin g   th n u m b er   o f   g en er atio n s   r eq u ir ed   to   r ea ch   h ig h - q u ality   s o lu tio n s .   As  s h o wn   in   Fig u r 2 ,   th GA C R ap p r o ac h   co n v er g es  s ig n if ican tly   f aster   an d   r ea ch es  lo wer   m ak esp an   v alu es.  T h GA - o n ly   m eth o d   ex h ib its   s lo wer   co n v er g en ce   an d   ten d s   to   s tag n ate,   wh ile  th C R S - o n ly   ap p r o ac h   s h o ws  lim ited   im p r o v em e n t.   T h is   co n f ir m s   th at  h y b r id iza tio n   en h an ce s   b o th   co n v er g en ce   s p ee d   an d   s o lu tio n   q u ality .   T h is   b eh av i o r   is   co n s is ten with   f in d in g s   in   h y b r id   m etah e u r is tic  r esear ch   [ 1 5 ] ,   [ 2 2 ] ,   w h er lo ca s ea r ch   m ec h an is m s   s ig n if ican tly   en h an ce   c o n v e r g en ce   s p ee d   an d   s o lu tio n   q u ality .   T h ab latio n   s tu d y   co n f ir m s   t h at  th e   s u p er i o r   p er f o r m an ce   o f   th e   p r o p o s ed   ap p r o ac h   is   n o t   in cid en tal   b u t   is   a   d ir ec co n s eq u en ce   o f   th s tr o n g   s y n er g y   b etw ee n   GA  an d   C R co m p o n e n ts .   T h GA C R h y b r id   a p p r o ac h   co n v er g es   s ig n if ican tly   f aster   an d   r ea c h es  lo wer   m ak esp an   v alu es  c o m p ar ed   to   s tan d alo n GA  an d   C R m eth o d s ,   d em o n s tr atin g   t h ef f ec t iv e n ess   o f   h y b r id izatio n .       Evaluation Warning : The document was created with Spire.PDF for Python.