I nd o ne s ia n J o urna l o f   E lect rica l En g ineering   a nd   Co m p u t er   Science   Vo l.   1 2 ,   No .   2 ,  N o v e m b er   201 8 ,   p p .   4 8 2 ~ 4 8 8   I SS N:  2502 - 4752 ,   DOI : 1 0 . 1 1 5 9 1 / i j ee cs . v 1 2 .i 2 . p p 482 - 4 8 8           482       J o ur na l ho m ep a g e :  h ttp : //ia e s co r e. co m/jo u r n a ls /in d ex . p h p / ijeec s     Scheduli ng  Wor kflow  Applicatio ns w ith  M a k espa n  a nd  Relia bility Co nst r a ints       M a s lin a   Abdu l A ziz ,   J e m a l  H .   Aba w a j y ,   M o rsh ed  Cho wdhu ry   F a c u lt y   o f   Co m p u ter an d   M a th e m a ti c a l  S c ien c e s,  Un iv e rsiti   T e k n o lo g i  M A R A   M a la y sia ,   S h a h   A la m ,   M a lay sia   S c h o o l  o f   In f o rm a ti o n   T e c h n o lo g y ,   F a c u lt y   o f   S c ien c e ,   En g in e e rin g   a n d   Bu il t  E n v iro n m e n t ,   De a k in   Un iv e rsit y ,   G e e lo n g ,   A u st ra li a       Art icle  I nfo     AB ST RAC T     A r ticle  his to r y:   R ec eiv ed   Ma y   2 7 ,   2 0 1 8   R ev i s ed   J u l   2 4 ,   2 0 1 8   A cc ep ted   A u g   1 ,   2 0 1 8       In   th e   las t  f e w   y e a rs,  w o rk f lo ws   a re   b e c o m in g   rich e r  a n d   m o re   c o m p lex .   W o rk f lo w   sc h e d u li n g   m a n a g e m e n t  s y ste m   to   b e   ro b u st ,   f lex ib le  w it h   m u lt icriteria   sc h e d u li n g   a lg o rit h m s.  It  n e e d s  to   sa ti sfy   th e   Qu a li ty   o f   S e r v ic e   (Qo S )  p a ra m e t e rs.  Ho w e v e r,   Qo S   p a ra m e t e rs  a n d   w o rk f lo w  s y st e m   o b jec ti v e s  a re   o f ten   c o n trad ict o r y .   In   o u r  a n a ly sis,  we   d e riv e d   a n   e ff icie n t   stra teg y   to   m in i m ize   th e   o v e ra ll   p r o c e ss in g   ti m e   f o r  sc h e d u li n g   w o rk f lo w s   m o d e ll e d   b y   u sin g   Dire c ted   A c y c li c   G ra p h   (D AG ).   W e   stu d ied   th e   p ro b lem   o f   w o rk f lo w   sc h e d u li n g   t h a t  lea d   to   o p ti m izin g   m a k e sp a n   a n d   re li a b il it y .   T h e   p ro p o se d   a lg o rit h m   h a n d les   u n su c c e ss f u l  jo b   e x e c u ti o n   o r  re so u rc e   f a il u re   b y   d y n a m ic a ll y   sc h e d u li n g   w o rk f lo w s  to   a v a il a b le  re so u rc e s.  Ba s e d   o n   th e   e x p e ri m e n ts  re su lt s,  o u r   p r o p o se d   F a il u re - Aw a re   W o rk f lo w   S c h e d u l in g   (F AW S )  A lg o rit h m   c a n   sig n if ica n tl y   o p ti m ize   th e   m a k e sp a n   a n d   m in im i z e   th e   re li a b il i ty   b y   re sc h e d u li n g   t h e   f a il e d   tas k   to   th e   u n u se d   re so u rc e s.  T h e   e ffe c ti v e n e ss   o f  th e   F A W S   a lg o r it h m   w a s  v a li d a ted   b a se d   o n   a   si m u latio n - d riv e n   a n a ly sis b a se d   o n   t h e   w o rk f lo w   a p p li c a ti o n .   K ey w o r d s :   Dir ec ted   A c y clic  Gr ap h   ( D AG)   Failu r e - Aw ar e   Ma k esp a n   Qu alit y   o f   Ser v ice  ( Qo S   R eliab ilit y   Co p y rig h t  ©   2 0 1 8   In stit u te o f  A d v a n c e d   E n g i n e e rin g   a n d   S c ien c e .    Al l  rig h ts  re se rv e d .   C o r r e s p o nd ing   A uth o r :   Ma s li n a  A b d u l  A ziz,   Facu lt y   o f   C o m p u ter   an d   Ma t h e m a tical  Scie n ce s ,     Un i v er s iti T ek n o lo g i M A R A   Ma la y s ia,     Sh a h   A la m ,   Ma la y s ia .   E m ail:  m asl in a @ t m s k . u it m . ed u . m y       1.   I NT RO D UCT I O N     E x ec u t in g   a  lar g e  w o r k f lo w   a p p licatio n   is   a   co m p le x   p r o ce s s   e s p ec iall y   in   th e   s it u atio n   w h er e  t h er e  ar e  m u lt ip le  an d   d if f er en t  r eso u r ce s   in v o l v ed .   I t  in v o l v es  co m p le x   a n d   h i g h l y - s tr u ctu r ed   p r o ce s s es .     E v er y   w o r k f lo w   v ar ies   in d i v id u all y   w it h   d if f er en t  ch ar ac ter is tics ,   p r io r it y   a n d   d ep en d en c y .   T h e  m ai n   m o tiv a tio n   o f   t h is   s t u d y   i s   h o w   to   f i n d   a  s c h ed u le   th at   m a n ag es  t h e  e x ec u tio n   o f   d if f er e n t   k i n d s   o f   w o r k f lo w s   th at  h a v e  d if f er e n t  p r io r ities   an d   i n ter d ep en d en t  ta s k s   o f   lar g e   d atasets   w it h o u t   s ac r if ici n g   th e   Qo S   co n s tr ain ts .   I d en ti f y in g   tas k s   t h at  h a v e  in ter m ed iate  tas k s   a n d   k n o w i n g   th e  lo ca tio n   o f   i n ter m ed iate  tas k   ar e  i m p o r tan t.  E f f ec tiv e  s c h ed u li n g   s tr ate g ies  ar e  r eq u ir ed   i n   ex ec u tin g   lar g e  ap p licatio n s   t o   m i n i m ize  t h e   s ch ed u le  le n g th   ( Ma k e s p an ) .   Go o d   m ap p in g   o f   tas k s   to   p r o ce s s o r s   i n   ti m es   o f   f ai lu r es   o f   r eso u r ce s   ca n   h a v e   an   ad v er s e  e f f ec t  o n   ap p licat io n s .   T h er ef o r e,   t h er e  i s   a n   i n cr ea s i n g   d e m a n d   f o r   s c h ed u lin g   tec h n iq u es   to   m i n i m ize  t h e  ta s k   f ail u r e  p r o b ab ilit y   at  th e   s a m e  ti m e   m a x i m ize  t h e  r eliab ili t y   o f   d u r i n g   ex ec u tio n   o f   an   ap p licatio n .   T h e  m ai n   ch a ll en g e  is   to   ac h ie v e  t w o   o b j ec tiv es ;  t h e  m ak e s p an   a n d   r eliab ilit y   t h at  ar e  co n f lic tin g .     A   w o r k f lo w   is   th e  a u to m at io n   o f   b u s i n es s   p r o ce s s es  th at  i n v o l v e  th e  p r o ce s s i n g   o f   ca s es  an d   th e   ex ec u t io n   o f   ta s k s   i n   a   p ar ticu lar   o r d er ,   b y   s p ec i f ic   r eso u r ce s ,   s o   t h at  s o m e   o b j ec tiv e  is   m et.   I t  co m p r is ed   o f   n et w o r k ,   s er v er s ,   clie n t s   an d   t h e  p eo p le  n ee d   to   d ea l  w ith   d ata  an d   b u s in e s s   p r o ce s s   r u les .   Fo r   ea ch   ac tiv it y ,   th er e  w ill  b e  r u les  a n d   d ata  th at  ac t  as  co n tr o ller   an d   in p u t  o r   o u tp u t  r esp ec tiv el y .   T h e  r u les  ex i s t  d u e  to   th e   Evaluation Warning : The document was created with Spire.PDF for Python.
I n d o n esia n   J   E lec  E n g   &   C o m p   Sci     I SS N:  2502 - 4752       S ch ed u lin g   W o r kflo w   A p p lica tio n s   w ith   Ma ke s p a n   a n d   R elia b ilit y  C o n s tr a in ts   ( Ma s l in a   A b d u l A z iz )   483   ex is t in g   o f   t h e  p er ce n ta g e  o f   i n f lu e n ci n g   b y   in ter n al  a n d   e x t er n al  s o cial   an d   m a r k et  e n v ir o n m e n t  to w ar d s   a n   o r g an izatio n   [ 1 ] .   Me an w h ile,   s ch ed u lin g   ca n   b e  d ef i n ed   as  m ap p in g   an d   m a n a g in g   t h e  ex ec u tio n   o f   ta s k s   o n   th e  d is tr ib u ted   r eso u r ce s .   T h e  ch alle n g e  w o u ld   b e  allo ca t in g   b est - f it   r e s o u r ce s   to   w o r k f lo w   tas k s   w h ile   s atis f y in g   th e   o b j e ctiv e s   s et   b y   u s er s .   T h e  s y s te m   p er f o r m a n ce   to   s to r e,   p r o ce s s   an d   a n al y ze   lar g e  a m o u n ts   o f   d is tr ib u ted   d ata  r elies h ea v il y   o n   th e  e f f ec t iv e n es s   o f   t h e  s c h ed u lin g   p r o ce s s   [ 2 ] - [ 4] .   Ov er   th e  p ass   y ea r s ,   t h er e  ar e  a  n u m b er   o f   r esear ch   o n   d if f er en t  asp ec t  o f   w o r k f lo w   s c h ed u li n g   s u c h   as  ap p licatio n ,   tech n iq u e,   co n s tr ain t  a n d   en v ir o n m en t.  T h ese  p ap er s   f o cu s   o n   s o l v i n g   v ar i o u s   Qo S  p r o b lem s   s u c h   as  s y s te m   p er f o r m a n ce ,   R eliab ilit y   ( R ) ,   E n er g y   co n s u m p tio n   ( E ) ,   T im e  /  d ea d lin e   ( T )   an d   co s t  ( C ) .   So m e  o f   t h e  p ap er s   p r o p o s ed   alg o r ith m   u s i n g   m eta h eu r i s tic   tech n iq u es  w it h   m u l ti - o b j ec tiv e  co n s tr ai n ts   s u c h   as  g e n etic   al g o r ith m .   Ho w e v e r ,   f o r   th i s   r esear c h ,   w e   o n l y   f o cu s ed   o n   t w o   co n s tr ain ts ;  ti m e  ( m ak e s p an )   a n d   r eliab ilit y .   O u r   p r o p o s ed   alg o r ith m   u s e s   h eu r i s tic  s ch ed u li n g   alg o r ith m s   s in ce   it  r es u lted   p o s itiv el y   i n   s o lv in g   th e  s c h ed u lin g   p r o b le m   w i th   less   m at h e m atica l  f o r m u latio n .   B ased   o n   t h e  co m p ar ati v e  s tu d y ,   o u r   p r o p o s ed   alg o r ith m   d i f f er s   f r o m   e x i s tin g   tec h n iq u es  s u c h   a s   Hete r o g en eo u s   E ar lies t  Fin i s h   T i m e  ( HE FT ) ,     Mo d if ied   C r itical  P ath   ( M C P )   an d   E ar ly   Fi n is h   T i m e  ( E F T ) .   B ased   o n   th e  s i m u lat io n   r esu lt,  o u r   p r o p o s e d   alg o r ith m   r es u lted   p o s itiv e l y   a s   co m p ar ed   o th er s .     Au to m o b ile  a n d   ae r o n au tic s   a r e  ex a m p les  o f   ad v a n ce d   in d u s tr ies  w h ich   co m p r is es  o f   lar g e  co m p le x   p r o ce s s es  w it h   hi g h   u n ce r tain t y .   T h ese  lar g e  p r o ce s s es  h av e   p r o b lem s   th at  r eq u ir es  m u l ti - o b j ec tiv e  s o lu tio n s   to   s o lv e  [ 5 ] .   Hw a n g   et  al   ( 2 0 0 3 )   [ 6 ]   d iv id ed   w o r k f lo w   f ail u r e  h an d li n g   tech n iq u e s   in to   t w o   d if f er en t  le v els,   n a m e l y   tas k - le v el  a n d   w o r k f lo w - le v el.   U n f o r tu n a tel y ,   a s   it  w as   p r o v en   in   m an y   r e s e ar ch ,   w h e n   s y s te m   r eliab ilit y   i n cr ea s e s ,   m o s t  o f   t h e  ti m e,   t h e  e x ec u tio n   ti m e  will  also   i n cr ea s e.   T h is   i s   b ec a u s e  a  f a s t  s c h ed u l e   ca n   s o m e ti m es b e  v er y   u n r elia b le.   Ma n y   m et h o d s   h a v e  b ee n   p r o p o s ed   to   d ea l  w it h   f au lt s .   On e  o f   th e  alter n ati v es  is   to   h av e  b ac k u p s   an d   d u p licatio n s .   I f   le t  s a y   o n e  o f   t h e  r eso u r ce s   f ail,   th e   o th er   r eso u r ce s   w i ll  c o n tin u e  to   o p er ate.     Ho w e v er ,   t h e  m aj o r   d r aw b a ck   o f   t h is   m eth o d   i s   a   p o s s ib le  w a s te  o f   r eso u r ce s .   As  a n   alter n ati v e,     th e  s c h ed u li n g   m ec h an is m   i s   in tr o d u ce d .   I n   ca s e  o f   r es o u r ce   f ail u r e,   th e  s ch ed u ler   w il l  d ec id e  w h ich   r eso u r ce s   w ill   s tar t  a n d   s to p   th e  task .   T h er ef o r e,   t h e  p r o p er   u s e  o f   t h e  s c h ed u lin g   al g o r ith m   w i ll  m in i m ize  t h e   p r o b a b ilit y   o f   s y s te m   f ail u r e  a n d   i m p r o v e  t h e  s y s te m   r esp o n s e.   S ch e d u lin g   p r o ce s s   m a y   le ad   to   re ass ig n i n g   o f   task s   to   r eso u r ce s   w h ic h   co u ld   cr ea te  an   in f ea s ib le  s ch ed u le .   T h e  m o r e  n u m b er   o f   d ata  th e  m o r e  co m p le x   an d   d if f ic u lt  to   s ch ed u le.   T h er ef o r e,   it  is   i m p o r tan t  to   re - a s s i g n   th e  ta s k s   u s i n g   m i n i m u m   n u m b er   o f   r eso u r ce s     [7 ] - [ 9 ] .   Un f o r tu n atel y ,   a s   it   w a s   p r o v en   i n   m a n y   r esear ch ,   w h e n   t h e  r eliab il it y   i n cr ea s e s ,   m o s t  o f   t h e  t i m e,     th e  ex ec u tio n   ti m e  w ill  al s o   in cr ea s e.   T h is   is   b ec au s e  a   f ast  s c h ed u le  is   ca n   s o m et i m es  b e  u n r eliab le.     T h er ef o r e,   th er e  is   a  n ee d   to   d esig n   an   al g o r ith m   t h at  lo o k   f o r   a  s et  o f   tr ad e - o f f s .   T h e  o b j ec tiv es  ar e  to   m i n i m ize  th e  m a k esp an   a n d   to   m ax i m ize  t h e  r eliab ilit y   o f   t h e  s ch ed u le .   A   h eter o g e n eo u s   e n v ir o n m en t   th at  co n n ec ts   m il lio n s   o f   n e t w o r k s   an d   co m p u ter s   i s   u s u all y   at  r is k   to   f ac e  f ail u r es  o f   c o m p o n e n t s / r eso u r ce s   ( m ac h i n es,  h ar d war e,   s o f t w ar e  an d   d is k )   th a t  ar e  lo ca ted   an d   d is tr ib u ted   all  o v er   t h e  n e t w o r k .   Fo r   s y s te m s   t h at  ar e  cr iticall y   d ep en d e n t  o n   co m p u ter s ,   f o r   ex a m p le  f i n an cia l  s y s te m ,   th e s e  s y s te m s   h a v e  h i g h   r eliab ilit y   r eq u ir e m e n t s .   He n ce ,   t h e  r eliab i lit y   is s u e s   m u s t  b e   co n s id er ed   an d   d ea li n g   w it h   f a u lt - to ler an ce   is   a  p r o m i n en t  co n ce r n   e s p ec iall y   i n   la r g e  h e ter o g en eo u s   en v ir o n m e n t  w h er e  tas k s   t h a t  ar e  r elate d ,   b ig ,   n u m er o u s   an d   co m p lex .   T h e  p r o ce s s   s t ar ts   w h e n   a  clie n t   r eq u est  f o r   a  s er v ice.   On ce   t h e  clie n t’ s   r eq u es t  is   s u b m itt ed ,   th e  s y s te m   n ee d s   to   b e  r esp o n s i v e  an d   f ast .     T h e  clien t   o f   th e  s er v ice  r elies   h ea v il y   o n   ti m e  r eq u ir e m en ts   an d   co n s tr ain ts   i m p o s ed   b y   t h e  s er v ice  p r o v id er   f o r   th e  r eso u r ce   ca p ab ilit y   [ 10 ].   A   h ig h - p er f o r m a n ce   s y s te m   is   v er y   co s tl y ,   r eq u ir e s   m o r e  en er g y   d u e  to   th e   in cr ea s e  o f   n u m b er   o f   r e s o u r ce s .   Ho w e v er ,   b y   ad d in g   m o r e  r eso u r ce s   th e  s y s te m   w il l  b e  less   r eliab le.     As  an   i m p ac t,  th e  s y s te m   w il l   b e  less   s ec u r e  an d   ca u s e  d ela y   to   th e  o v er all  p r o ce s s ,   r es u lti n g   i n   p o te n tiall y   f r u s tr ated   clien t s   an d   lo s t i n v e s to r s .   T h is   w i ll n e g ati v el y   i m p ac t b u s i n ess   p r o f it a n d   tar n i s h   its   r ep u tatio n .   T h e  m ai n   is s u e  at  th i s   s tag e   is   to   h a v e  p r o p er   p o s itio n in g   o f   t h e  r eso u r ce s ,   it s   r elatio n   to   o t h er   r eso u r ce s   an d   s er v ices.  W h e n   a  w o r k f lo w   i s   s u b m it ted   s u b m itti n g   to   t h e  s y s te m ,   t h e  s c h ed u ler   d eter m i n es  t h e   b est  s c h ed u le   b ased   o n   t h e  d e ad lin e  co n s tr ain ts   a n d   a v ailab i lit y   o f   r eso u r ce s   i n   th e   s y s te m .   T h e  ch alle n g e   w e   ad d r ess   is   h o w   to   s ch ed u le  th e      w o r k lo ad s   o n   th e      r es o u r ce s   b u t  en s u r i n g   th at  ea ch   task                 is   s c h ed u led   o n   o n e  o f   t h e              r eso u r ce s .   E ac h               r eso u r ce   ex ec u t es  th e  tas k s   w it h o u t  e x ce ed in g   th e   d ea d lin e      w it h i n   t h e  m ax i m u m   u s e  o f   r eso u r ce s     .   W o r k f lo w   ta s k s   w er e  e x ec u ted   o n e  b y   o n e  to   s ev er al   d is tr ib u ted   r eso u r ce s .   Us u all y ,   a  w o r k f lo w   co o r d in ato r   h an d le s   all   w o r k f lo w   ta s k s   ex ec u t io n   p r o ce s s .   E x is ti n g   w o r k f lo w   p r o ce s s   is   u n ab le  to   h a n d le  lar g e  n u m b e r   o f   w o r k f lo w   tas k s .   T h er ef o r e,   lar g e  n u m b er   o f   task s   an d   lar g e  s ize  d ata  w ill   n ee d   to   b e  r esch ed u led   to   av o id   r es o u r ce   f ailu r e.   T h is   r es ea r ch   en h an ce s   th e   ex is t in g   w o r k f lo w   d esi g n   [ 11 ]   b y   m ak in g   t h e  f o llo w i n g   ch a n g es:   a)   A b le  to   h a n d le  lar g e  n u m b er   o f   tas k s   w h en   u s i n g   b o th   s i n g l e  an d   m u ltip le  w o r k f lo w s   w i t h o u t   s ac r i f ici n g   th e  Qo S c o n s tr ain t s .   b)   Failu r e - a w ar e  w o r k f lo w   th at   h an d les lar g e  n u m b er   o f   tas k s   w it h o u t sacr i f ici n g   t h e  Qo S c o n s tr ai n ts .       Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 5 0 2 - 4752   I n d o n esia n   J   E lec  E n g   &   C o m p   Sci,   Vo l .  1 2 ,   No .   2 ,  No v e m b er   201 8   :   4 8 2   –   4 8 8   484   T h e  Qo S  o f   s er v ice - b ased   s y s te m s   ar e  b ec o m in g   i n cr ea s i n g l y   co m p le x   ( also   ca lled   C SB S )   n ee d s   to   b e  m ain tain ed   d u r in g   r u n ti m e   [ 1 2 ] .   A n y   tas k   i n   a  d ata  i n te n s iv e  w o r k f lo w   m a y   h a n d le  lar ge - s ized   d ata  f ile s   at   b o th   in p u t  a n d   o u tp u t   s ta g es  o f   its   ex ec u tio n   T h is   p ap er   aim s   to   ev al u ate  t h e  p er f o r m an ce   o f   t h e  s c h ed u li n g   alg o r ith m   f o r   b o th   h o m o g e n o u s   a n d   h eter o g e n eo u s   p r o ce s s o r s .   T o tal  ex ec u tio n   ti m e  i s   m et  a n d   th er e f o r e   in cr ea s es  t h e  p er f o r m a n ce   o f   th e  w h o le  s y s te m .   T h u s ,   th e  w o r k f lo w   s c h ed u li n g   ef f ici en c y   a n d   th e  tas k   ex ec u t io n   w ill  i m p r o v e.   R ap id l y   g r o w in g   tec h n o lo g ie s   in   v ar io u s   ar ea s   s u ch   as  s y s te m s ,   h ar d w ar e  an d   n et w o r k .   A ll   th e s e  tec h n o lo g i es  ai m   to   g i v e  t h e  m o s t  e f f icie n t  a n d   r eliab le  s e r v ice s   to   a  la r g e  n u m b er   o f   en d - u s er s   in c lu d i n g   co m p u ti n g   p o w er   a s   a  u ti lit y ,   li k e  w ater ,   g a s   an d   e lectr icit y .   A s   d is c u s s ed   ea r lier ,   th e  o v er all   p er f o r m a n ce   o f   t h e  w o r k f lo w  ap p licatio n   r elies  h ea v il y   o n   m a k esp an   co n s tr ai n t  e s p ec iall y   d u r i n g   r u n ti m e.   T h er ef o r e,   b y   u til iz in g   t h e   r es o u r ce s   it  w ill i m p r o v e  th e   p er f o r m a n ce   o f   t h e   w o r k f lo w   ap p licatio n .   T h is   r esear ch   is   ab o u t  e n h a n c in g   t h e  w o r k f lo w   ex ec u tio n   p er f o r m an ce   b y   p r o p o s in g   Fail u r e - A w ar e  W o r k f lo w   Sch ed u li n g   ( F AW S)  A lg o r it h m .   Ho w e v er ,   in   th i s   p ap er ,   w e  m ai n l y   d is cu s s   o n   en ab li n g   r esch ed u li n g   o f   t h e  f ai led   task   to   th e  u n u s ed   r eso u r ce s   to   i m p r o v e  th e  p er f o r m a n ce .   T h e  v alid ate  th e  ef f ec tiv e n e s s   o f   th e  p r o p o s ed   alg o r ith m ,   a  s i m u latio n - d r iv en   an al y s i s   b ased   o n   r ea lis tic  w o r k f lo w   ap p licatio n   w a s   d e m o n s tr a ted .   Fu r th er ,   w e  p r esen t  a  co m p ar ativ e  e v alu a tio n   t h at  lo o k s   at  t w o   m a in   o b j ec tiv es:     ( 1 )   u tili zin g   u n u s ed   r eso u r ce   /ap p licatio n   in   th e  e v e n t  o f   f a ilu r e  a n d   ( 2 )   w o r k f lo w   s c h ed u li n g   a g ai n s t  f a u lt - to ler an t  to w ar d s   f ail u r es.  T h i s   r esear ch   tac k les  t h e  c h alle n g e s   o f   d ev elo p i n g   al g o r ith m s   f o r   r esch ed u lin g   f ailed   tas k s   b ased   o n   th e  r eliab ilit y   r eq u ir e m e n t.   T h e  s im u latio n   r es u lts   s h o w   th e  F A W S  al g o r ith m   h a s   o p tim ized   th e  m ak e s p an   an d   r eliab ilit y   o f   th e  w o r k f lo w   ap p licatio n .         2.   F AIL UR E - AW ARE WO RK F L O W  SCH E DUL I N G   ( F A W S)   T h is   s ec tio n   co n ti n u es  w it h   a  b r ief   d is cu s s io n   o f   a  n u m b er   o f   s tatic  s ch ed u lin g   al g o r ith m   w it h   p ass iv e  r ep licatio n   s tr ate g y .   T h e  n e w   p r o p o s ed   s ch ed u li n g   alg o r ith m   is   n a m ed   Fail u r e  Aw ar e  W o r k f lo w   Sch ed u l in g   ( F A W S)  A l g o r ith m .   T h e  co m p ar is o n   o f   o u r   p r o p o s ed   alg o r ith m   is   d o n e  b ased   o n   th e  e x p er i m e n t   u s i n g   D A G  g r ap h   as  a  co n t in u a tio n   o f   t h e  ea r lier   alg o r ith m   L a y er ed   W o r k f lo w   Sch ed u lin g   A l g o r ith m   ( L W FS )   [ 1 3 ] - [ 1 4 ] .   T h is   alg o r ith m   b asic  id ea   is   u s in g   th e  ex ec u t io n   ti m e  o f   th e  w o r k f l o w   s c h ed u le  as  t h e   p ar a m eter .   As  s h o w n   i n   t h e  a lg o r ith m   ab o v e,   a ll  a v ailab le  p r o ce s s o r   th at  is   ch ec k ed   o n   f o r   cu r r en t   b ac k u p .   T h e  ch ec k i n g   p r o ce s s   h a s   t h r ee   m ain   s tep s .     2 . 1 .     Sub  T a s k   Sched uli ng   T h e  task s       an d   th e  b ac k u p         ar e  s ch ed u led   o n   th e  ex i s ti n g   r eso u r ce s .   T h e  f ir s t  s tep   w il l  b e   esti m ati n g   t h e  ea r lies t  av ailab le  ti m e  f o r   ea ch   r eso u r ce .   I f   a  b ac k u p   task   w ill  b e  s lo t  in   an y   o f   t h e  r eso u r ce s                 an d         th e  b ac k u p   tas k s   s tar t  ti m e  w ill  b e  th e  ea r lies t  ta s k   to   b eg in .   T h en ,   f o r   th e  s ec o n d   s tep   is   to   ch ec k   t h e  r eso u r c es  s tar t  ti m e.   I f   th e  r eso u r ce s   s tar t  at  th e  s a m e  ti m e,   t h e  ti m e  g ap   f o r   th e  av ailab le  r eso u r ce s   f r o m   b o th   o v er lo ad ed   an d   n o n - o v er lo ad ed   s ch ed u les  w ill  b e  ex a m in ed .   I f   t h er e  ar e  ca s es  wh er e  b o th   f ir s t  a n d   s ec o n d   s tep s   ca n n o t b e  u s ed   to   f in d   c u r r en t b ac k u p ,   th e  t h ir d   s tep   w i ll b e  in tr o d u ce d .   T h e  th ir d   s tep   u s es  m a k esp an   as  th e   b ac k u p   s tar t  ti m e.   W h e n   t h e  ea r lies t  e x ec u tio n   ti m e  t o   s ch ed u le   th e  b ac k u p ,   s lo t  h av e   b ee n   f o u n d   th e  r ep licatio n   co s t  o f   t h e  c u r r en t  b ac k u p   w il l  b e  ca lcu la t ed .   T h e  r ep licatio n   co s t  ca n   also   b e  t h e  d ec id in g   p ar am eter   if   i n   a   s it u atio n   w h er e  s ev er al   r eso u r ce s   h a v e   th e   s a m e  ea r lie s t  f i n is h   ti m e.   T h e  b ac k u p   task   w i ll  b e  s ch ed u led   to   th e  r eso u r ce   w it h   m i n i m u m   r ep licatio n   co s t.  T h e  p er f o r m an ce   o f   F A W S a l g o r ith m   i s   test ed   b as ed   o n   th e  s i m u lati o n   u s in g   s y n th etic  w o r k f lo w .   T h e  e x p er i m en t  w il l c o m p ar e  i n   ter m s   o f   f a u lt to ler an ce   o f   t h e  p r o p o s ed   alg o r ith m   b ased   o n   g iv e n   ca s e s .     Pr o c e d u r e :   F A W S   1 :   I N PU T :   T   t a sk,   Pr i o r i t i ze l i s t ,   R   2 :   O U T PU T :   S c h e d u l e   3 :   BEG I N   5 :       W HI L E   (                      )   DO   6 … . S c h e d u l e   t h e   Pri m a ry  C o p y   u si n g   H EFT   7 … . S c h e d u l e   t h e   Ba c k u p   C o p i e s   8:                                . n e x t   9.                         (                            )   10 .                     11 .                                             +=             12 … …T ’ i                                      13 .         EN D W H I L E   8 :         R e t u r n   S c h e d u l e   8 .     EN D   F A W S         Evaluation Warning : The document was created with Spire.PDF for Python.
I n d o n esia n   J   E lec  E n g   &   C o m p   Sci     I SS N:  2502 - 4752       S ch ed u lin g   W o r kflo w   A p p lica tio n s   w ith   Ma ke s p a n   a n d   R elia b ilit y  C o n s tr a in ts   ( Ma s l in a   A b d u l A z iz )   485   2 . 1 . 1.     Ca s e  1 :   E x is t ing   T a s ks   o n Re s o urce   w it h no   F a ilu re :   I n   C ase  1 ,   th e  r eso u r ce s   alr ea d y   h a v e  tas k s   s c h ed u led   o n   t h e m .   T h er ef o r e,   w e  n ee d   to   f i n d   th e  b est  r eso u r ce   f o r   t h e  b ac k u p   tas k s .   Sin ce   th er e  ar e   ex i s ti n g   tas k s ,   th e  b ac k u p   ta s k   n ee d   to   b e  s c h ed u le  o v er lap p in g   w it h   t h e  ex is tin g   tas k s .   B u t  t h e  s ch ed u li n g   p r o ce s s   w il l  s till   f o llo w   t h e  f o u r   B ac k u p   Sch e d u lin g   C o n s tr ai n ts .   Ou r   p r o p o s ed   s ch ed u l in g   al g o r ith m   is   ca lled   B est_ R eso u r ce   A lg o r it h m .   T h e  m a in   p u r p o s e  is   f i n d in g   t h e  b e s t   r eso u r ce   to   p lace   th e  b ac k u p   t ask s .   B y   s ca n n in g   th e  w o r k f l o w   f o r w ar d   f r o m   th e  to p   o r   t h e               task   to   th e   en d ,   w e  ar e  ab le  to   d eter m i n e  w h ic h   r eso u r ce s   ar e  av ai lab le  to   p lace   th e  b ac k u p   tas k s .     Pr o c e d u r e :  B est_ Fit _ Slo t   1 :   I N PU T :   T   t a sk,   Pr i o r i t i ze l i s t ,   R   2 :   O U T PU T :   S c h e d u l e   3 :   BEG I N   5 :       F o r   (                 |   |           ) DO   4 .                                                            (       )   5 .         EN D FO R   6 :         Re t u rn   l i st   6 .     EN D   Be s t _ Fi t _ S l o t       Fig u r e  1   s h o w s   th e  ta s k s   an d   i ts   b ac k u p   ta s k s   s c h ed u li n g .   T h er e  ar e  3   r eso u r ce s   ( R 1 ,   R 2   an d   R 3 )   an d   8   p r im ar y   ta s k s   w it h   its   r esp e ctiv e  b ac k u p s .   T h er e  is   o n l y   1   b ac k u p   f o r   ea ch   tas k   b u t  n o t  all  task s   w ill  h av e  a   b ac k u p .   E ac h   b ac k u p   tas k   w ill   b e  s ch ed u led   af ter   its   p r im ar y .   I f   th e  task   o r   th e  r eso u r ce   f ai l,  i m m ed iatel y   t h e  b ac k u p   tas k   w ill b e  ac ti v ated           Fig u r e  1 .   Sch ed u li n g   b ac k u p   task   w it h   b est_ r eso u r ce   al g o r ith m       2 . 1 . 2.     Ca s e  2 :   Reso urce   F a il ure   I n   th is   ca s e,   w e  p r o p o s e  an o th er   alg o r ith m   ca lled   B est_ Fit _ Slo t  A lg o r it h m .   Or   th is   ex a m p le,     ass u m e  t h at  R e s o u r ce   1   ( R 1 )   f ails .   I n   th i s   alg o r ith m ,   th e  s ca n n i n g   p r o ce s s   g o es  u p   s tar ti n g   f r o m              task .   B y   lo o k in g   b ac k w ar d s ,   w e  ar e  ab l e  to   ass i g n   b ac k u p   to   an   a v aila b le  in ter v al   o r   o v er lap   w ith   ex is ti n g   tas k   w it h o u t   v io lati n g   t h e  co n s tr ain t s .   A s s ig n   a f f ec ted   tas k s   to   an o t h er   r eso u r ce   w i th   t h e  ea r lies t  s tar t  ti m e.   R e s tar t  t h e  f ailed   tas k   at  th e  la s t  cu r r e n t  p o s itio n .   T h is   alg o r ith m   f i n d s   th e  v ac a n t  ti m e  i n ter v al s ,   eit h er   th e  u n o cc u p ied   ti m e  i n ter v a ls   o r   o v er lo ad in g   w it h   e x is t in g   p r i m ar y   tas k . W h en   o n e  o f   th e  r eso u r ce s   ( R 1 )   f ails ,   t h e  b ac k u p   task   w il l  s tar t  i m m ed iatel y .   As  w e  ca n   s ee   R 1   o r ig in a ll y ,   R 1   h as  a  f u l l  lo ad   o f   5   task s .   Sch ed u li n g   th e  f ailed   task   is   v er y   ch a llen g i n g   s i n ce   o th er   r eso u r ce s   ar e  also   p ac k ed   w ith   ta s k s .   T h e  B est_ Fit _ Slo t  A lg o r it h m   lo o k s   at  th e  lo ad   an d   a v ailab le  ti m e  o f   ea ch   r eso u r ce .   T h is   tec h n iq u e  also   s h o w s   th e   tas k s   ar e  g r o u p ed   to   s av e  m o r e   ti m e.   T h e  al g o r ith m   a ls o   lo o k s   at   t h e  b es t  w a y   to   s h i f t  s m a ller   tas k s   to g et h er .   T h e  h i g h li g h ted   tas k s   ar e  th e   n e w   tas k   q u e u e  t h at  co m b i n es  p r i m ar y   a n d   th e  b ac k u p   task s   r ea d y   to   b e  ex ec u ted   o n   o th er   av ai lab le   r eso u r ce s .                         Pr o c e d u r e :   B e st _ R e so u r c e   1 :   I N PU T :   T   t a sk,   2 :   O U T PU T :   l i st   3 :   BEG I N   5 :       Fo r   (                 |   |           ) DO   4 .                                                         (       )   5 .         EN D F O R   6 :         R e t u r n   l i s t   6 .     EN D   B e st _ R e so u r c e     Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 5 0 2 - 4752   I n d o n esia n   J   E lec  E n g   &   C o m p   Sci,   Vo l .  1 2 ,   No .   2 ,  No v e m b er   201 8   :   4 8 2   –   4 8 8   486   Fig u r e  2   s h o w s   w h e n   o n e   o f   t h e  r eso u r ce s   ( R 1 )   f ails ,   t h e  b ac k u p   tas k   w i ll  s tar t  i m m ed iatel y .     As  w e  ca n   s ee   R 1   o r ig i n all y ,   R 1   h as a   f u ll lo ad   o f   5   tas k s .   S ch ed u li n g   th e  f ailed   ta s k   i s   v er y   ch al len g i n g   s i n ce   o th er   r eso u r ce s   ar e  also   p ac k ed   w ith   ta s k s .   T h e  B est_ Fit _ Slo t  A lg o r it h m   lo o k s   at  th e  lo ad   an d   av ailab le  ti m e   o f   ea ch   r eso u r ce .   T h is   tech n i q u e  also   s h o w s   t h e  tas k s   ar e  g r o u p ed   to   s av e  m o r e  ti m e.   T h e  alg o r ith m   als o   lo o k s   at  t h e  b est  w a y   to   s h if t  s m aller   tas k s   to g et h er .   T h e  h i g h l ig h ted   ta s k s   ar e  t h e  n e w   tas k   q u e u e  t h a t   co m b i n es p r i m ar y   a n d   th e  b ac k u p   tas k s   r ea d y   to   b e  ex ec u ted   o n   o th er   av ailab le  r eso u r ce s .           Fig u r e  2 .   Sch ed u li n g   b ac k u p   task   w it h   b est_ f it_ s lo t a l g o r ith m       3.   RE SU L T S  A ND  AN AL Y SI S     T h e  ch ec k i n g   p r o ce s s   h as  t h r ee   m ai n   s tep s .   T h e  f ir s t  s tep   w il l  b e  esti m at in g   t h e  ea r lie s t   av ailab le   ti m e   f o r   ea c h   r eso u r ce .   I f   t h e  b ac k u p   ca n   b e  s lo t  i n   o n   t h i s   r eso u r ce ,   t h e   b ac k u p   ta s k   s tar t   ti m e   w ill   b e  s et   as   th e  ea r lies t  s tar t   ti m e.   T h e  s e co n d   s tep   is   if   th e   r eso u r ce s   h av e   th e   s a m e  s tar t  ti m e,   t h e   r eso u r ce   w it h   t h e  av ailab le  ti m e  s lo t  f r o m   b o th   o v er lo ad ed   ex is ti n g   s c h ed u les  a n d   th e  ti m e  g ap   a m o n g   n o n - o v er lo ad ed   s ch ed u les.   I f   t h er e  ar e  ca s es  w h er e  b o th   s tep s   ca n n o t  b e  u s ed   to   f in d   cu r r en t  b ac k u p ,   th e  th ir d   s tep   w i ll  b e   in tr o d u ce d .   T h e  th ir d   s tep   u s es  m ak e s p an   as  th e  b ac k u p   s tar t  ti m e.   W h en   t h e  ea r lies t   ex ec u tio n   ti m e  to   s ch ed u le  th e  b ac k u p ,   s lo t  h a v e  b ee n   f o u n d   th e  r ep licat io n   co s t  o f   th e  cu r r e n t  b ac k u p   w ill  b e  ca lcu lated .     T h e  r ep licatio n   co s t  ca n   also   b e  th e  d ec id in g   p ar am eter   i f   in   a  s itu atio n   w h er e  s e v er al  r eso u r ce s   h a v e  th e   s a m e  ea r lies t  f i n is h   ti m e.   T h e  b ac k u p   tas k   w ill  b e  s ch ed u led   to   th e  p r o ce s s o r   th at  h as  th e  m in i m u m  r ep licatio n   co s t.  T h e  tas k s   T   an d   th e   b ac k u p   T ’   ar e  s ch ed u led   o n   th e   ex i s ti n g   r eso u r ce s .   W h en   s ch ed u li n g   a   n e w   b ac k u p ,   th e  r eso u r ce   t h at  m ee ts   t h e  t h r ee   co n d itio n s   a s   m e n tio n ed   ab o v e.   T h e  F A W S  alg o r it h m   p er f o r m a n ce   i s   te s ted   b ased   o n   th e   s i m u latio n   u s i n g   s y n t h etic  w o r k f lo w .   T h e  e x p er i m en t  w i ll  co m p ar e  i n   ter m s   o f   f a u lt to ler an ce   o f   t h e  p r o p o s ed   alg o r ith m   b ased   o n   g iv e n   s ce n ar io s .     3 . 1 .     S ce na rio   1   I f   a n y   o f   th e   r eso u r ce s   f ails   i n   t h e  m id d le  o f   ta s k   ex ec u tio n   a n d   t h e  ta s k   af f ec ted   is   a   n o n - cr itical   task ,   t h e  ta s k s   w il l  b e  r esch ed u led   to   th e  n e x t  a v ailab le  r eso u r ce s .   Fi g u r e  3   s h o w s   t h e  s ce n ar io   w h e n   r eso u r ce   f ail u r e  h ap p en ed   at  R 1 .           Fig u r e  3 .   R eso u r ce   f a ilu r e  i n   t h e  m id d le  o f   ta s k   e x ec u tio n       3 . 2 .     S ce na rio   2   I f   th e  h i g h l y   d ep en d en t  R eso u r ce   R 1   f ails   i n   th e  m id d le  o f   th e  f ir s t  tas k   ex ec u tio n   ( Fi g u r e  4 ) .   Fo r   th is   t y p e  o f   f ail u r e,   th e  r esch e d u lin g   tas k s   ar e  n o t a s   co m p li ca ted   as in   Sce n ar io .       R1 R2 R3 T8 T7 T2 T4 T5 T3 T2 T1 T6 T1 0 T9 Evaluation Warning : The document was created with Spire.PDF for Python.
I n d o n esia n   J   E lec  E n g   &   C o m p   Sci     I SS N:  2502 - 4752       S ch ed u lin g   W o r kflo w   A p p lica tio n s   w ith   Ma ke s p a n   a n d   R elia b ilit y  C o n s tr a in ts   ( Ma s l in a   A b d u l A z iz )   487       Fig u r e  4 .   R eso u r ce   f a ilu r e  i n   t h e  m id d le  o f   f ir s t ta s k   e x ec u ti o n       3 . 2 .     S ce na rio   3   Fo r   th e  t h ir d   s ce n ar io ,   t h e  f ail u r e  h ap p en ed   at  t h e  s a m e  s p o t  as  i n   s ce n ar io   1 .   R eso u r ce   R 1   f ail s   i n   th e  m id d le  o f           ex ec u tio n .   Fi g u r e  5   s h o w s   t h e  f ail u r e  o f   R 1   wh en   e x ec u tin g   ta s k   T 2   w it h   b ac k u p s .             Fig u r e  5 .   R eso u r ce   f a ilu r e  i n   t h e  m id d le  o f   ta s k   e x ec u tio n   with   b ac k u p s       B y   ap p l y i n g   o u r   p r o p o s ed   FA W S  alg o r ith m ,   ta s k   T 2   w ill  n o t  r estar t  f r o m   th e  b eg i n n i n g .   I n s tead ,   it  w il l  co n t in u e  f r o m   th e   T 2   last   v alu e   w h e n   R 1   f ailed .   T o   f i n is h   th e  r e m ai n i n g   T 2 ,   th e  r eso u r ce   w it h   t h e   ea r lies t  ex ec u t io n   ti m e  w ill  b e  ch o s en .   Fo r   th is   s it u atio n   th e  r e m ai n in g   ti m e  o f   T 2   w ill   s tar t  au to m atica ll y   af ter   T 5   f i n is h es.   T h e  b asic  id ea   o f   t h i s   al g o r ith m   is   to   p lac e  b ac k u p   tas k s ,   f o r   ta s k s   t h at   ar e  w h e n   a   r eso u r ce   f ails .   T h is   p r o v ed   t h at  i f   in   a  s itu a tio n   w h er e  t h e  tas k   f ails ,   th e  b ac k u p   tas k   w il l  s tar t  i m m ed iatel y   f r o m   t h e   last   v al u e  o f   th e  f ailed   tas k s ,   w it h o u t  h av i n g   to   r estar t  th e   w h o le  task .   T h e  task   s c h ed u lin g   p r o ce s s   is   th e   co n tin u atio n   o f   th e   L a y er ed   W o r k f lo w   Sc h ed u li n g   A l g o r it h m   ( L W F S)  al g o r ith m   [ 12 ] - [ 13 ] .   I t  u s es  t h e  s a m e  p r io r itized   lis t  g en er ated   u s in g   L W F S.  B ased   o n   th e  ex p er i m e n tal  r es u lt,  th e  o v er all  m a k esp an   i s   9 3   m in s .   T h is   s h o w s ,   t h e   m a k esp a n   i s   less   as   co m p ar ed   to   o th er s .   Fig u r e  6   i s   a   g r ap h   t h at  s u m m ar izes   th e   o v er all   p er f o r m a n ce   o f   t h e  g i v en   s c en ar io s .   Fro m   t h is   g r ap h ,   it  s h o w s   t h e  w o r s t - ca s e  s ce n ar io   is   Scen ar io   1 ,   th e   id ea l   s ce n ar io   is   Sce n ar io   3   as  co m p ar ed   to   th e  n o r m al  s itu at i o n   o f   w o r k f lo w   s ch ed u li n g   w it h o u t  an y   f a ilu r e s .     Fo r   th is   ex p er i m e n t,  w e  ca lc u lated   t h e  m a k esp an   b y   s i m u lati n g   it  o n   b ased   o n   d if f er en t  s ce n ar io s   u s in g   n u m b er   o f   r eso u r ce s   f o r   t h e   s a m e   ap p licatio n .   Di f f er en t   s ce n ar io s   h a v e  d i f f er e n t  e f f ec ts   o f   th e   o v er all  m ak e s p an .   T h e  r e s u l t  ca n   b e  d er iv ed   b y   ca lcu lat in g   th e   d if f e r en ce   o f   th e   o v er all   ti m e  ta k e n   f o r   ea ch   s ce n ar io .   B ased   o n   th e  r esu lt,  it  s h o ws  th at  o u r   p r o p o s ed   w o r k f lo w   F A W S  i m p r o v ed   th e  m a k esp an   o f   t h e  g i v en   w o r k f lo w .   W e  ca lc u lated   t h e  m ak e s p an   b y   s i m u lat in g   i t  o n   b ased   o n   d if f er e n t  s ce n ar io s   u s i n g   a  n u m b er   o f   r eso u r ce s   f o r   t h e  s a m e   w o r k f lo w   ap p licatio n .   Dif f er e n t   s ce n a r io s   h av e   d if f er en t  e f f ec ts   o f   th e   o v er all   m ak e s p an .   T h e  r esu lt c a n   b e  d er iv ed   b y   ca lc u lati n g   th e  d i f f e r en ce   o f   th e  o v er al l ti m e  ta k e n   f o r   ea ch   s ce n ar io .     B ased   o n   th e  r esu lt,  it  s h o w s   th at  o u r   p r o p o s ed   w o r k f lo w   F A W S  i n cr ea s ed   th e  m ak e s p an   f r o m   th e   n o r m al  s ce n ar io   w h er e  th er e  i s   n o   f ail u r e.   Sin ce   t h er e  is   tas k   f ail u r e  d u r in g   th e  e x ec u tio n   p r o ce s s   f o r   o n e  o f   th e  r eso u r ce s ,   t h e  m a k esp an   i n cr ea s e  is   u n av o id ab le.   Ho w e v er ,   th e  i n cr ea s ed   m ak e s p an   i s   v er y   m i n i m al  a s   co m p ar ed   to   o t h er s .   Fi g u r e  7   is   a  g r ap h   t h at   s u m m ar ize s   t h e  o v er all  p er f o r m a n ce   o f   F A W S  b ased   th e   g i v e n   s ce n ar io s .   Fro m   t h is   g r ap h ,   it  s h o w s   t h e  w o r s t - ca s e  s ce n ar io   is   Scen ar io   1   w it h   1 0 7   m i n u te s ,   th e  id ea l   s ce n ar io   is   Sce n ar io   3   w ith   9 3   m i n u te s   as   co m p ar ed   to   th e  n o r m al  s it u atio n   o f   w o r k f lo w   s ch ed u lin g   w i th o u t   an y   f ail u r es.   R1 T2 R2 R3 T1 T1 T2 T6 T9 T3 T8 T7 T4 T1 0 T5 R1 R2 R3 T4 T2 T2 T9 T8 T7 T5 T3 T1 T6 T1 0 Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 5 0 2 - 4752   I n d o n esia n   J   E lec  E n g   &   C o m p   Sci,   Vo l .  1 2 ,   No .   2 ,  No v e m b er   201 8   :   4 8 2   –   4 8 8   488       Fig u r e  6 .   C o m p ar is o n   o f   m a k e s p an   f o r   3   s ce n ar io s       4.   CO NCLU SI O N     T h e  p r o p o s ed   Failu r e  Aw ar e  W o r k f lo w   Sc h ed u lin g   ( F A W S)  A l g o r ith m   h a n d les  u n e x p ec ted   f ailu r e   ca u s e s   r esch ed u li n g   o f   t h e  f ailed   task   o n   th e  u n co m p let ed   task   e x ec u t io n .   T h is   is   d o n e  b ased   o n   th e   ex p er i m e n t  u s i n g   D A G   g r ap h   as  a  co n t in u atio n   o f   th e  L a y er ed   W o r k f lo w   Sch ed u li n g   Alg o r ith m   ( L W FS ) .   T h e  alg o r ith m   d is c u s s ed   in   th i s   p ap er   is   f o r   s c h ed u lin g   p ar al lel  ap p licatio n s   o n   h o m o g e n e o u s   s y s te m s   s o l v ed   t w o   co n f lict in g   o b j ec tiv es:  m ax i m ize  th e  r eliab ili t y   a n d   m in i m ize  t h e  m a k esp an   at  th e  s a m e  ti m e.     T h e  p r o p o s ed   alg o r ith m   h a n d les  u n s u cc ess f u l  j o b   ex ec u tio n   o r   r eso u r ce   f ailu r e  b y   d y n a m icall y   s c h ed u li n g   w o r k f lo w s   to   a v ailab le  r eso u r ce s .   W e  co m p ar ed   t h e  F A W S   alg o r it h m   w i th   th e   d if f er en t   s c h ed u li n g   alg o r ith m s .   B ased   o n   th e   e x p er im e n t,  s p ec if icall y   ta s k   r esch ed u lin g   h a s   a  h u g e   i m p ac t  to   t h e  s u b s eq u en t   s ch ed u lin g   d ec is io n s   f o r   n o t - s c h ed u led - y et  tas k   ( ch ild )   in   t h e  w o r k f lo w .   Fo r   s i m u latio n   a n al y s i s ,     w e  r an d o m l y   g e n er ated   task   g r ap h s   a n d   s ch ed u led   th e  p ar allel  ap p licatio n s   o n   h o m o g en eo u s   s y s te m s .     T h e  s i m u latio n   r es u lt s   s h o w   t h at  th e  p r o p o s ed   FA W S  al g o r ith m   ca n   s ig n i f ica n tl y   o p ti m iz e  th e  m a k esp a n   an d   s u cc e s s f u ll y   m ap   t h e  w o r k f lo w   ta s k s   to   th e  r eso u r ce s   ac c o r d in g l y .   T h e  p r o p o s ed   alg o r ith m   is   b etter   t h a n   ex is t in g   h eu r i s tic - b ased   tech n iq u es  f o r   s ch ed u lin g   ap p licati o n   w o r k f lo w s .   F o r   f u t u r e  w o r k ,   w e  w ill  lo o k   at   d if f er e n t c o n f l icti n g   Qo S o b j ec tiv es   s u ch   as  C o s t   an d   E n er g y .   Si n ce   s m all  i n cr ea s e  in   m a k esp an   w i ll  h av e   b ig   ef f ec t  to   b o th   co n s tr ai n t s ,   w e  w il l  p r o p o s e  a  s o lu tio n   t h at  a b le  to   m in i m ize  t h e  e n er g y   co n s u m p t io n   a n d   co s t   w it h o u t sacr i f ici n g   t h e  s y s te m   p er f o r m a n ce .       RE F E R E NC E S    [1 ]   Bro u n s ,   G .   A .   J.  F .   Fea t u rin g   wo rk fl o w  ma n a g e me n t .   T e c h n isc h e   Un iv e rsiteit  Ei n d h o v e n ,   De p a rtm e n t  o f  M a th e m a ti c s an d   Co m p u ti n g   S c ien c e ,   2 0 0 0 .     [2 ]   W iec z o re k ,   M a re k ,   A n d re a s  Ho h e ise l,   a n d   Ra d u   P r o d a n .   T a x o n o m ie s  o f  th e   mu lt i - c riter ia   g ri d   wo rk fl o w  sc h e d u li n g   p ro b lem .   G rid   m id d lew a re   a n d   se rv ice s.  S p rin g e r  US,   2 0 0 8 .   2 3 7 - 2 6 4 .   [3 ]   Al - A li ,   Ra sh id ,   e t  a l.   An   OG S A - b a se d   q u a li ty  o f  se rv ice   f ra me wo rk .   G rid   a n d   Co o p e ra ti v e   Co m p u ti n g   (2 0 0 4 ):  5 2 9 - 5 4 0 .   [4 ]   Jia   Yu .   a n d   B u y y a   R.   A  T a x o n o my   o f  W o rk fl o w  M a n a g e me n t   S y ste ms   fo r  Gr id   Co m p u ti n g .   Jo u rn a l  o f   G rid   Co m p u ti n g ,   v o l .   3 ,   n o .   3 ,   p p .   1 7 1 – 2 0 0 ,   S e p tem b e r  2 0 0 5 .   Do n g a r ra ,   Ja c k   J.,   Emm a n u e l  Je a n n o t,   Eri k   S a u le,  a n d   Zh iao   S h i .   Bi - o b jec ti v e   sc h e d u l in g   a l g o rit h ms   fo r  o p ti mizin g   ma k e sp a n   a n d   re li a b il i ty  o n   h e ter o g e n e o u s  sy ste ms .   In   P r o c e e d in g s  o f   th e   n i n e tee n th   a n n u a l  A CM   sy m p o siu m   o n   P a ra ll e l  a lg o rit h m s  a n d   a rc h it e c tu re s,  p p .   2 8 0 - 2 8 8 .   A CM ,   2 0 0 7 .   [5 ]   Hw a n g ,   S o o n w o o k ,   a n d   Ca rl  Ke ss e l m a n .   Gr id   wo rk fl o w:  a   f lex ib le   fa il u re   h a n d li n g   fr a me wo rk   fo r  t h e   g rid .   I n   Hig h   P e rf o rm a n c e   Distrib u ted   Co m p u ti n g ,   2 0 0 3 .   P ro c e e d in g s.  1 2 th   I EE E  In tern a ti o n a l  S y m p o siu m   o n ,   p p .   1 2 6 - 1 3 7 .   IEE E,   2 0 0 3 .     [6 ]   M a li m ,   M .   R.   (2 0 1 2 ).   Lectu r e   ti m etab li n g   u s i n g   i m m u n e - b ase d   alg o r ith m s .   JI R K M|  Jo u r n a l  o f  I n fo r ma tio n   R etri ev a l a n d   K n o w led g e  Ma n a g eme n t .   [7 ]   Ra h im ,   S .   K.  N.  A . ,   Ba rg iela ,   A . ,   &   Qu ,   R.   (2 0 1 3 ).   A n a lys is  o f  Ba c k tra c k in g   in   U n ive rs it y   Exa min a ti o n   S c h e d u li n g .  In   ECM S   (p p .   7 8 2 - 7 8 7 ) .   [8 ]   E. ,   S a u le,  E. ,   &   T ry str a m ,   D.  (2 0 1 2 ).   Op ti mizin g   p e rfo rm a n c e   a n d   re li a b il it y   o n   h e ter o g e n e o u s  p a r a l lel  sy ste ms :   Ap p ro x im a ti o n   a lg o rit h ms   a n d   h e u ristics .   Jo u r n a l  o f   P a ra ll e l  a n d   D istri b u te d   c o m p u ti n g ,   7 2 (2 ),   2 6 8 - 2 8 0 .   [9 ]   Is m a il ,   A . ,   Ya n ,   J.,   &   S h e n ,   J.  (2 0 1 3 ).   I n c re me n ta l  se rv ice   le v e l  a g re e me n ts  v io la ti o n   h a n d li n g   w it h   ti me   imp a c t   a n a lys is .   Jo u r n a l  o f   S y s te m s an d   S o f tw a r e ,   8 6 (6 ) ,   1 5 3 0 - 1 5 4 4 .   [1 0 ]   W o rk f lo w   M a n a g e m e n t  Co a li ti o n   (W f M C)  Re tri e v e d   f ro m   UR L   h tt p :/ /w ww . wfm c . o rg   [1 1 ]   Is m a il ,   A . ,   &   Ca rd e ll in i,   V .   (2 0 1 3 ,   De c e m b e r).   T o wa rd s  se lf - a d a p t a ti o n   p l a n n in g   fo r  c o mp le x   se r v ice - b a se d   sy ste ms .   In   In tern a ti o n a l  C o n f e re n c e   o n   S e rv ice - Orie n ted   Co m p u ti n g   (p p .   4 3 2 - 4 4 4 ).   S p ri n g e r,   Ch a m .   [1 2 ]   A z i z ,   M . A . ,   A b a w a j y ,   J.  a n d   He ra wa n ,   T .   L a y e re d   wo rk fl o w  sc h e d u li n g   a l g o rit h m .   F u z z y   S y ste m s  (F UZZ - IEE E) ,   2 0 1 5   IE EE   I n tern a ti o n a l  C o n f e re n c e   o n .   IEE E,   2 0 1 5 .     [1 3 ]   A z i z ,   M .   A . ,   A b a w a j y ,   J.,   Isla m ,   R. ,   &   He ra w a n ,   T .   W o rk fl o w  sc h e d u li n g   o n   d istri b u ted   sy ste ms .   In d u strial   El e c tro n ics   a n d   A p p li c a ti o n s (ICI EA ),   2 0 1 5   IEE E   1 0 th   C o n f e re n c e   o n   IEE E,   2 0 1 5 .   85   107   100   93   0 20 40 60 80 1 0 0 1 2 0 N o   F a i l u r e S c e n a r i o   1 S c e n a r i o   2 S c e n a r i o   3 T i m e   ( M i n u t e s)   Evaluation Warning : The document was created with Spire.PDF for Python.