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.   9 ,   No .   3 ,  Ma r ch   2 0 1 8 ,   p p .   789 ~ 798   I SS N:  2 5 0 2 - 4 7 5 2 ,   DOI : 1 0 . 1 1 5 9 1 /i j ee cs.v 9 . i3 . p p 7 8 9 - 798          789       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   Bi - o bject iv e  Sche duling  w ith  Co o pera ting   H euris tics f o r  E mbedded  Rea l - ti m e  Sys te m s       B endib   So nia   Sa bri na ,   K a lla   H a m o ud i,  a nd   K a lla   Sa li m   Co m p u ter S c ien c e   De p a rtm e n t,   Un iv e rsity   o f   Ba tn a   2 5 3 ,   Ro u te d e   Co n sta n ti n e .   F e sd is,   Ba tn a   0 5 0 7 8 ,   A lg e ria       Art icle  I nf o     AB ST RAC T     A r ticle  his to r y:   R ec eiv ed   J an   5 ,   2 0 1 8   R ev i s ed   Feb   1 4 ,   2 0 1 8   A cc ep ted   Feb   2 8 ,   2 0 1 8       T h is  p a p e r  p r o p o se s  M a k e sp a n   a n d   Re li a b i li ty   b a se d   a p p ro a c h ,   a   sta ti c   sh e d u li n g   stra teg y   f o r  d istri b u te d   re a l  ti m e   e m b e d d e d   sy ste m s  t h a t  a im s  to   o p ti m ize   th e   M a k e sp a n   a n d   th e   re li a b il it y   o f   a n   a p p li c a ti o n .   T h is  sc h e d u li n g   p ro b lem   is  NP - h a rd   a n d   w e   re l y   o n   a   h e u rist ic  a lg o rit h m   to   o b tain   e ff ici e n tl y   a p p ro x im a te  so lu ti o n s.  T w o   c o n tri b u ti o n s  h a v e   to   b e   o u tl in e d :  F irst,   a   h iera rc h ica l  c o o p e ra ti o n   b e tw e e n   h e u risti c s  e n su rin g   to   trea t  a lt e rn a ti v e l y   th e   o b jec ti v e s  a n d   se c o n d ,   a n   A d a p a tatio n   M o d u le  a ll o w in g   to   im p ro v e   so lu ti o n   e x p lo ra ti o n   b y   e x t e n d in g   th e   se a rc h   sp a c e .   It  re su lt s  a   se t  o f   c o m p ro m isin g   so lu ti o n s o f f e rin g   th e   d e sig n e r   th e   p o ss ib il it y   to   m a k e   c h o ice s in   li n e   w it h   h is  (h e r)  n e e d s.  T h e   m e th o d   w a s tes ted   a n d   e x p e rim e n tal  re su lt s are   p r o v id e d .   K ey w o r d s :   E m b ed d ed   r ea l - ti m e  s y s te m s   C o o p er atin g   h e u r is tics   Bi - o b j ec tiv e  s ch ed u l in g   R eliab ilit y     P ar eto     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 ce .    Al l  rig h ts  re se rv e d .   C o r r e s p o nd ing   A uth o r :   Kalla  Ha m o u d i ,   C o m p u ter   Scien ce   Dep ar t m en t ,   Un i v er s it y   o f   B atn a  2 53,   R o u te  d e  C o n s ta n ti n e.   Fes d is ,   B atn a  0 5 0 7 8 ,   A lg er ia.   E m ail:  h a m o u d i.k alla @ u n iv - b atn a2 . d z       1.   I NT RO D UCT I O N     On e  p r in cip le  k e y   in   d is tr ib u t ed   r ea l  tim e  e m b ed d ed   s y s te m   d esig n   is   s c h ed u lin g .   I n d ee d ,   s tr ateg ies  th at  ta k e  in to   ac co u n t  b o th   a lg o r ith m ic  a n d   ar ch itect u r al  ch ar ac ter is tic s   to   r ea lize  an   ef f icie n t  m ap p in g   o f   task s   to   p r o ce s s o r s   ar e  cr u c ial.   Fu r t h er m o r e,   i n   d i s tr ib u t ed   r ea l  ti m e   e m b ed d ed   s y s t e m s ,   s ev er al   o f te n   co n f lic tin g   cr iter ia  m u s t  b e  tak en   i n to   ac co u n t.  B i - o b j ec tiv e  s ch ed u li n g   d ea ls   w ith   r ea l - w o r ld   p r o b lem s   t h at   in v o l v e  t w o   co n f l icti n g   o b j ec tiv es  [ 1 ,   2 ,   3 ,   4 ] .   I t   is   o n e  o f   th e  m o s t  ac ti v e  r esear ch   f iel d   in   th e  co n tex t  o f   d is tr ib u ted   r eal - ti m e  s y s te m s .   P ar ticu lar l y ,   th e   Ma k e s p an   a n d   th e   r eliab ilit y   h av e  b ee n   d ea lt  b y     s ev er al  r esear ch e s .   Ma k esp a n   a n d   r eliab ilit y   ar e  s i m u lta n eo u s l y   o p ti m ized   w h i le  s c h ed u li n g   a  s et  o f   i n d ep en d en t  tas k s   o n   a  s et  o f   h eter o g en eo u s   p r o ce s s o r s   [ 5 ] .   T h e  ai m   is   to   co n v er g e  to w ar d s   P ar eto   o p ti m al  s et.   I n   [ 6 ] ,   au t h o r s   p r o p o s e  a  s p atial  allo ca tio n   b ased   alg o r ith m   th at  w o r k s   ac co r d in g   to   t w o   s tep s ,   ea ch   o n e   o p tim izi n g   o n e  o f   th e  o b j ec tiv es.  I n   [ 7 ] ,   a  h ier ar ch ical  ap p r o ac h   f av o r in g   r e liab ilit y   i s   ad o p ted   b y   f ir s t  s ele ctin g   p r o ce s s o r s   m ax i m izin g   t h e  r eliab ilit y   an d   th en   ch o o s i n g   p r o ce s s o r   th at  m in i m izes  th e  ea r lies t  s tar t  ti m e.   T h e  w o r k   p r esen ted   in   [ 8 ]   ex ten d s   t h e  li s t sch ed u lin g   h eu r i s tic  [ 9 ] .   T h e  p air   ( f ail u r e  r ate,   e x ec u t i o n   ti m e)   i s   u s ed   a s   a   b asi s   f o r   ch o o s i n g   t h e   b est   p air   ( p r o ce s s o r ,   tas k ) .   I n   [ 1 0 ] ,   Ma k esp an   an d   r eliab ilit y   ar e  n o r m alize d   an d   co m b in ed   i n   a  w ei g h ted   co s t  f u n ct io n .   P r o ce s s o r   s elec tio n   i s   b ased   o n   co s t f u n c tio n   m i n i m izat io n .   T h e  au th o r s   o f   [ 4 ]   p r o p o s e  a  n e w   h eu r i s tic  f o r   h eter o g e n eo u s   s y s te m s   t h at  s i m u lta n eo u s l y   o p tim izes   th e  Ma k e s p an   an d   t h e  r eliab ilit y   o f   a n   ap p licatio n .   A   w ei g h ted   f u n ct io n   g u id es  s o l u tio n   ch o ice.   I n   ad d itio n ,   s o lu tio n s   ar e   clas s i f ied   to   all o w   t h e   u s er   ad ap tin g   t h e   f u n ctio n   a n d   t h en   s elec t in g   th e   a p p r o p r iate  s o lu tio n .   T h e  w o r k   in   [ 1 1 ]   p r esen ts   a  b i - o b j ec tiv e  s ch ed u lin g   h eu r i s tic   w h er e  Ma k e s p an   an d   r eliab ili t y   n o r m aliza tio n   is   r ea lized   b y   a  co m p r o m i s e  f u n ctio n .   T h is   o n e  s elec ts   f o r   ea ch   o p er atio n   th e  s u b s et  o f   p r o ce s s o r s   s u c h   th 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.  9 ,   No .   3 ,  Ma r ch   2 0 1 8   :   7 8 9   –   7 9 8   790   r ep licatio n   o f   th is   o p er atio n   o n to   th o s e  p r o ce s s o r s   m a x i m iz es  th e  r eliab ilit y   a n d   m i n i m iz es  th e  r u n - ti m e.   A  f u n ctio n   p ar a m eter   m a y   b e  v ar ied   to   f av o r   o n e  cr iter io n .   I n   [ 1 2 ] ,   a   f r a m e w o r k   f o r   th e  b i - o b j ec tiv e  s tatic  m u ltip r o ce s s o r   s ch ed u li n g   p r o b lem   co n s i d er in g   th e   Ma k esp a n   an d   th e  r eliab ilit y   i s   p r o p o s ed .   T h e  g lo b al  r eliab il it y   o f   th e  s y s te m   i s   co n s id er ed .   T h e  P ar eto   cu r v e   is   p r o d u ce d   f o r   a   g i v e n   in s ta n ce   allo w i n g   t h e  u s er   to   c h o o s e  g iv i n g   ad v an ta g e   to   eit h er     Ma k esp a n   o r   r eliab ilit y .   I n   [ 1 3 ] ,   is   p r esen ted   a  b i - o b j e ctiv e  g e n etic  al g o r it h m   i n   w h ich   a  w ei g h ted   s u m   ap p r o ac h   is   u s ed   to   d ea l  w i th   th e   t w o   o b j ec tiv es  R eliab ilit y   a n d   Ma k e s p an .   W o r k   in   [ 1 4 ]   p r o p o s es  an d   co m p ar es  t w o   a lg o r it h m s   MO G A   an d   MO E P   b ased   o n   n o n - d o m i n ated   r an k in g ,   f o r   s o lv in g   th e  b icr iter ia  s ch e d u lin g   p r o b lem .   I n   ad d itio n ,   a  co m p ar is io n   is   m a d e  w it h   th e  w ei g h ted - s u m   b as ed   b i - o b j ec tiv e  ap p r o ac h .   Ou r   w o r k   co n ce r n s   b i - o b j ec tiv e  s ch ed u li n g   in   d is tr ib u te d   r ea l  ti m e  e m b ed d ed   s y s te m s   w h ile   m ak e s p an   an d   r eliab ili t y   ar e  th e  co n s id er ed   o b j ec tiv es.  T w o   h eu r i s tic s   co o p er ate  in   a  h ier ar ch ical   w a y   to   g en er ate  s o l u tio n s ,   w h ile  an   a d ap tatio n   m o d u le  is   u s ed   to   ac h iev e  a  b est  s p ac e  ex p lo r atio n .   T h e  p ap er   o r g an izatio n   i s   as  f o llo w s :  I n   s ec t io n   2 ,   s o m e   as s u p tio n s   co n ce r n in g   s y s te m   m o d el s   an d   o b j ec tiv es  ar e  p r esen ted .   Sectio n   3 ,   r ec alls   th e  m u lti - o b j ec tiv e  o ti m izatio n   an d   p r esen ts   b i cr iter ia  s ch ed u li n g   as  a  b i - o b j ec tiv e  p r o b le m .   I n   s ec tio n   4 ,   t h e  p r o p o s ed   ap p r o ac h   is   d escr ib ed .   B ef o r e  co n clu d i n g ,   s ec tio n   5   d ep icts   s o m e  ex p er i m en tal  r es u lts   a s s e s s i n g   o u r   ap p r o ac h .       2.   I NP UT   A SS UM P T I O NS   I n   o u r   w o r k ,   s o m e  as s u m p tio n s   ar e  co n s id er ed   ( Sectio n   2 . 1   a n d   Sectio n   2 . 2 ) .     2 . 1 .   Sy s t em   De s cr iptio n     Dis tr ib u ted   r ea l - ti m e  e m b ed d ed   s y s te m s   ar e  co m p o s ed   o f   t wo   p r in cip al  p ar ts ,   w h ich   ar e  t h e   s o f t w ar e   p ar t ( th e  ap p licatio n   alg o r it h m )   an d   th e  h ar d w ar e  p ar t ( th e   d is tr ib u ted   ar ch itec tu r e) .   T h e   s p ec if icatio n   o f   t h e s e   s y s te m s   in v o l v e  d escr ib in g   th e  alg o r it h m   co m p o n en t s   ( alg o r ith m   m o d el) ,   th e   ar ch it ec tu r e  co m p o n en t s   ( ar ch itectu r e  m o d el) ,   an d   th e  ex ec u tio n   ch ar ac ter is t ic s   o f   th e  al g o r ith m   o n to   th e  ar ch itect u r e    ( ex ec u tio n   m o d el) .     T h e  ap p licatio n   is   m o d eled   b y   a  d ata  f lo w   g r ap h ,   ca lled   a lg o r ith m   g r ap h   a n d   n o ted   Alg .   E ac h   v er te x   is   a  task   a n d   ea ch   ed g e  i s   a  d ata  d ep en d en c y .               Fig u r e  1 A .   A l g o r ith m   Gr ap h   A l g   Fig u r e  1 B .   A r ch itect u r e  Gr ap h   A r c         A   ta s k   o f   A l g   ca n   b e  eit h er   an   ex ter n al  i n p u t /o u tp u t  tas k   o r   a  co m p u tatio n   ta s k .   T ask s   w it h   n o   p r ed ec ess o r   ( r esp .   n o   s u cc ess o r )   ar e   th e  in p u t  i n ter f ac es  ( r esp .   o u tp u t) ,   h an d li n g   th e   e v en ts   p r o d u ce d   b y   th e   s en s o r s   ( r esp .   ac tu ato r s ) .   T h e  i n p u t s   o f   a  co m p u ta tio n   ta s k   m u s t p r ec ed e   its   o u tp u ts .       Fig u r e  1 A   is   a n   ex a m p le  o f   a n   al g o r ith m   g r ap h ,   w it h   s i x   ta s k s :  I   a n d   I ’   ( r esp .   O)   ar e   i n p u ts   ( r esp .   o u tp u ts )   ta s k s ,   w h ile  A ,   B ,   an d   C   ar e  co m p u tatio n   ta s k s .   T h e  d ata - d ep en d en c ies   b et w ee n   tas k s   ar e  d ep icted   b y   ar r o w s .   Fo r   i n s ta n ce   th e   d ata - d ep en d en ce   A C   ca n   co r r esp o n d   t o   th e   s e n d in g   o f   s o m e  ar it h m etic  r e s u l t   co m p u ted   b y   A   an d   n ee d ed   b y   C .     T h e  ar ch itectu r e  i s   m o d eled   b y   a  g r ap h ,   ca lled   ar ch itect u r e   g r ap h   a n d   n o ted   A r c.   E ac h   v er tex   i s   a   p r o ce s s o r ,   an d   ea ch   ed g e  is   a   co m m u n icatio n   li n k .   Fi g u r e  1 B   g iv e s   a n   e x a m p le  o f   a n   ar c h itectu r e  g r ap h ,   w it h   th r ee   p r o ce s s o r s   P 1 ,   P 2   an d   P3 ,   an d   th r ee   co m m u n icatio n   li n k s .     An   ex ec u tio n   ti m e  E x e  i s   d ef i n ed   f o r   ea ch   p air   ( ti,  p j ) ;  it  r e p r esen ts   t h e  w o r s t  ca s e  ex ec u ti o n   ti m e  o f   th e  tas k   ti  o n   t h e  p r o ce s s o r   p j ,   ex p r ess ed   i n   ti m e  u n it s .   A s s u m i n g   th at  p r o ce s s o r s   ar e  h eter o g en eo u s ,   o n e  ta s k   co u ld   h a v e  d if f er en t  e x ec u tio n   ti m es  o n   d if f er en t  p r o ce s s o r s .   W h en   a  g i v en   ta s k   ca n n o t   b e  ex ec u ted   o n   a   g iv e n   p r o ce s s o r ,   th e   ass o ciat i o n   is   e x p r ess ed   b y   th e  v al u e  ” ”.   On   th e  o t h er   h a n d ,   to   e ac h   p air   ( d i,  lj ) ,   i 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       Bi - o b jective   S ch e d u lin g   w ith   C o o p era tin g   Heu r is tics   fo r   E mb ed d ed   R e a l - time  S ystem   ( K a lla   Ha mo u d i )   791   ass o ciate d   a  ti m e  t h at  ex p r e s s es  t h e  w o r s t  ca s e  tr an s m i s s io n   ti m e  o f   t h e  d ata  d ep en d en c y   d i  o n   t h e  co m m u n icatio n   lin k   lj .   Fu r t h e r m o r e,   th e  in tr a - p r o ce s s o r   co m m u n icatio n   ti m e  is   s u p p o s e d   to   b e  0   tim e  u n it.   Fo r   in s ta n ce ,   E x e  f o r   A l g   an d   A r c  o f   F ig u r es 1 A   a n d   1 B   is   g iv en   i n   T ab les 1 A   an d   1 B .       T ab le  1 A .   E x ec u t io n   T i m es     I   I’   A   B   C   O   P1     2   6   4   2   4   P2   4     12   8   4   8   P3   3   2   9   6   3       T ab le   1 B .   T r an s m i s s io n   T im e s     I  A   I  B   I’ B   I’ O   A C   B C   L 1 2   3   2   4   3   1   5   L 1 3   6   5   8   6   2   10   L 2 3   3   2   4   3   1   5         A p p licatio n   a n d   ar ch itect u r e  m o d elin g   u s in g   g r ap h s ,   is   u s e f u l  f o r   o b j ec tiv e  d ef in i tio n s     ( s u b s ec tio n   2 . 2 . ) .     2 . 2 .   M a k esp a n a n d Re lia bil it y   O bje ct iv es     T h e  m a k esp a n   o r   s ch ed u le  le n g th   i s   th e  e n d   ex ec u tio n   ti m e  o f   th e  tas k   t h at  is   co m p leted   l ast  a m o n g   all  task s .   I t is d ef i n ed   as f o llo w s :     ( 1 )         w h er e,   en d   ( ti,  p j )   is   th e  ti m e  a t  w h ic h   tas k   ti ter m in ate s   its   e x ec u t io n   o n   p r o ce s s o r   p j .     A   f u n ctio n   ca lled   s ch ed u le  p r ess u r e ,   ca lcu lated   f r o m   t h e  g r ap h   alg o r ith m ,   is   p r o p o s ed   in   [ 1 5 ] ,   it  is   n o ted   (n)   an d   is   d ef in ed   f o r   ea ch   tas k   ti    T (n)   com p   ( n   r ef er in g   to   th e  h e u r is tic  s tep   an d   co m p   to   th e  s et  o f   co m p eti to r   task s   i.e   th o s e  n o t  y et  s c h ed u led   an d   w h o s e   p r ed ec ess o r s   ar e   alr ea d y   s ch ed u led )   an d   ea ch   p r o ce s s o r   p j   as f o llo w s :       ( 2 )       w h er e:     S (n)   best(ti, pj  )  : th e  ea r lies t ti m e   a t  w h ic h   tas k   ti c an   s tar t e x ec u t io n   o n   p r o ce s s o r   p j ;     S¯ (n) ti   : th e  lates t star t ti m e  f r o m   en d   o f   ti [ 1 5 ] ;       Fu r t h er m o r e,   ex ec u tio n   a n d   tr an s m i s s io n   t i m e s   h a v e  to   co n s id er ed ,   h en ce   th e  f o llo w i n g   ex p r ess io n :     ( 3 )         Sch ed u le  p r es s io n   i s   u s ed   to   s elec t  th e  b est  tas k   w h ich   m i m i zises   t h e  le n g t h   o f   th e  cr it ical  p ath .   T h at  m ea n s   t h at  s c h ed u le  p r ess io n   m i m izatio n   i m p lie s   s c h ed u le  le n g th   o n e.   Ot h er w is e,   b o th   p r o ce s s o r s   an d   co m m u n icatio n   li n k s   ar e  s u b ject  to   f ailu r es.  A cc o r d in g   to   th e  m o d el  p r o p o s ed   in   [ 1 2 ]   a n d   c o n s id er in g   th e   o cc u r r en ce   o f   f ai lu r es   f o llo w i n g   a  P o is s o n   la w   w i th   a  co n s tan t  p ar a m e ter   λ ,   t h e  r eliab il it y   o f   a  p r o ce s s o r   P   ( r esp ec tiv el y ,   a  co m m u n icatio n   lin k   L )   d u r in g   t h e  d u r atio n   d   is :   ( 4 )           T h e  r eliab ilit y   o f   t h e  ta s k   o r   d ata  d ep en d en c y   X  p lace d   o n to   th e  h ar d w ar e  co m p o n e n t  C ,   w it h   a n   ex ec u t io n   ti m e  ex e( X,   C ) ,   is   t h en   d e f in ed   as  f o llo w s :     ( 5 )         B ec au s e  th e  r eliab ilit y   d ep en d s   in tr in s icall y   o n   th e  d u r atio n   o f   th e  task s   an d   co m m u n icati o n s ,   s o m e   tech n ical  d if f ic u ltie s   r aise  w h e n   u s in g   b o th   r eliab ilit y   an d   m a k esp an   a s   o b j ec tiv es [ 1 2 ] .     So ,   r ath er   th a n   u s in g   t h e  u s u al  m o d el  o f   t h e  r eliab ilit y   [ 1 6 ] ,   w e  u s e  t h e  co n ce p t  o f   GS F R   ( Glo b al  S y s te m   Fail u r e  R ate)   d ef i n ed   in   [ 1 2 ] ,   an d   n o ted   .     T h e  GSFR   o f   a  s tatic  s ch ed u le  S,  is   co m p u ted   as  f o llo w s :   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.  9 ,   No .   3 ,  Ma r ch   2 0 1 8   :   7 8 9   –   7 9 8   792     ( 6 )           w h er e  U( S)  i s   t h e  to tal  u tili za t io n   o f   t h e  h ar d w ar e  r eso u r ce s   an d   R ( S)  it s   r eliab ilit y .   T h e  G SF R   is   t h e   f ail u r e  r ate  p er   ti m e   u n it  o f   t h e  o b tain ed   m u ltip r o ce s s o r   s c h ed u le,   s ee n   a s   i f   it   w er e  a  s i n g le   tas k   s ch ed u led   o n to   a  s in g le  p r o ce s s o r .       3.   SCH E DU L I NG   A S A  M U LTI - O B J E CT I VE   P RO B L E M   A   m u lti - o b j ec tiv e  p r o b le m   i s   a  p r o b lem   w h o s e   r eso lu t io n   i m p lies   m u ltip le   o b j ec tiv es  co n s id er atio n .   T h e  g en er al  o p ti m izatio n   p r o b le m   is   d e f in ed   as  f o llo w s   [ 1 7 ] :                 w h er e  m   i s   t h e  n u m b er   o f   o b j ec tiv e  f u n c tio n s ,   k   is   t h e  n u m b er   o f   i n eq u alit y   co n s tr ai n ts   a n d   l  i s   t h e   n u m b er   o f   eq u alit y   co n s tr ain t s .   x     E n   is   a  d esi g n   v ec to r ,   also   ca lled   d ec is io n   v ec to r ,   w h er e  n   is   th e  n u m b er   o f   its   i n d ep en d en t  v ar iab les x i .   f ( x )     E n   is   a  v ec to r   o f   o b j ec tiv e  f u n ctio n s   w h er e: \           f i ( x )   ar e  al s o   ca lle d   o b j ec tiv e  o r   cr iter ia.   E ac h   p o in t  i n   t h e  d esig n   s p ac e  m ap s   to   a  p o in t  i n   t h e  o b j ec tiv e  s p ac e  b u t th e  r e v er s e   m a y   n o t to   b e  tr u e.         E v alu a tio n   o f   s o l u tio n s   is   d o n e  b y   u s i n g   t h e  P ar eto   ’ d o m i n an ce ’   ( P ar eto   1 9 0 6 ) .   A   p o ten tiall y   in ter esti n g   s o l u tio n   i s   a  s o lu ti o n   s u c h   as  i m p r o v i n g   o n e  o b j ec tiv e  ca n ’ t  b e  d o n e  w it h o u t   d eg r ad in g   at  leas t   an o th er   o n e.   S u c h   s o l u tio n s   co n s ti tu te   t h e  P ar eto   o p ti m al  s et.   E ac h   s o lu t io n   ca n   b e   r ep r esen ted   b y   its   o b j ec tiv e  v ec to r   in   a  m u l ti - di m en s io n a l sp ac e  ( Fig u r e  2 ) .       L et  z  a n d   z’   b e  t w o   p o in ts   o f   t h e  o b j ec tiv e  s p ac e.   Fo r m al l y ,   th e  P ar eto   d o m in a n ce   o n   o b j ec tiv e   v ec to r s   is   d ef i n ed   as:       A   p o in t z is P a r eto   d o min a ted   b y  a   p o in t z’ :           W h ile  th e  co n ce p t  o f   d o m i n an ce   i s   r elate d   to   o b j ec tiv e  s p ac e,   th e  o p ti m alit y   co n ce r n s   t h e     d ec is io n   s p ac e.         Fig u r e  2 .   Dec is io n   a n d   Ob j ec t iv e  Sp ac es   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       Bi - o b jective   S ch e d u lin g   w ith   C o o p era tin g   Heu r is tics   fo r   E mb ed d ed   R e a l - time  S ystem   ( K a lla   Ha mo u d i )   793     P ar eto   o p tim al  s o lu tio n s   co n s titu te  w h at  i s   ca lled   th e  P ar eto   o p tim al  s et  w h ile  th e  co r r esp o n d in g   o b j ec tiv e  v ec to r s   i.e   t h o s e  o n es  n o t  d o m in ated ,   ar e  s aid   to   b e  o n   t h e  P ar eto   f r o n t.  T h e  Nei g h b o r h o o d   is   a n o th er   i m p o r ta n t c o n ce p t in   c o m b i n ato r ial  o p ti m izat io n .   I t i s   d ef i n ed   as f o llo w s :     “T h e  n eig h b o r h o o d   o f  a   s o lu tio n   s     S   i s   a   s u b s et   o f  c o n fig u r a tio n s   o r   s o lu tio n s   o f  S   th a t  a r e  d ir ec tly  r ea ch a b le  b y  a   g iven   tr a n s fo r ma tio n   o f  s .   I t  is   n o t ed   V   ( s )   a n d   a   s o l u tio n   s     V ( s )   is   s a id   to   b e   a   n eig h b o r   o f s.”     P ar ticu lar l y ,   f r o m   a  g i v en   s o l u tio n ,   v ar io u s   Nei g h b o r h o o d   s t r u ctu r es   ca n   b e  e s tab lis h ed   ac co r d in g   to   v ar io u s   tr a n s f o r m atio n s   w h ile  a  tr an s f o r m atio n   i s   d ef i n ed   as  an   ap p licatio n :           w h er e  S  is   a  s et  o f   s o l u t io n s   an d   P ( S)  is   a  s u b s et  o f   S.  Su ch   a  co n ce p t  is   u s e f u l  i n   s e ar ch   s p ac e  s tr u ct u r in g   an d   in   d ef in i n g   th e  s et  o f   s o lu tio n s   th at  ca n   b e  r ea ch ed   f r o m   a  g iv e n   s o l u tio n   th r o u g h   a  s er ies  o f   tr an s f o r m atio n s .     I n   o u r   w o r k ,   s c h ed u li n g   is   b i - o b j ec tiv e  an d   is   th er ef o r e  co n s id er ed   as  a  b i - o b j ec tiv e  o p t i m izatio n   p r o b lem .   So lu t io n s   i n   d ec is io n   s p ac e  ar e  s h ed u les ea c h   o f   t h e m   ex p r es s in g   b o th   ta s k   a s s i g n m en t to   p r o ce s s o r s   an d   a  g iv e n   e x ec u tio n   o r d er .   E ac h   s c h ed u le  ( s o lu tio n )   ca n   b e  ev a lu ated   i n   t h e  o b j ec tiv e  s p ac e  ( Fi g u r e  3 )   d ef in ed   b y   t h e  co n s id er ed   o b jectiv es  ( s u b s ec tio n   2 . 2 . ) .   T h e  f ir s t  o b j ec tiv e  is   Ma k e s p an   ( e q u atio n   ( 1 ) )   th at  is   d ef in ed   u s in g   th e  co s t  f u n ctio n   n a m ed   s ch ed u le  p r ess u r e  ( eq u atio n   ( 3 ) )   w h ile  t h e  s ec o n d   o b j ec tiv e  is   GSFR   ( eq u atio n   ( 6 ) ) .       R ath er   th a n   a   s i n g le  s o l u tio n ,   a  s et  o f   s o l u tio n s   ( s c h ed u l es)  {s1 ,   s 2 ,   ·   ·   ·   }  is   g e n er ated .   E ac h   s ch ed u le  s i  m ak e s   a  co m p r o m i s e  b et w ee n   t h e  Ma k e s p an   an d   th e  r eliab ilit y   a n d   is   e x p r ess ed   b y   f ( s i) .       4.   T H E   P RO P O SE D  BI - O B J E CT I V E   AP P RO ACH     Giv e n   an   alg o r it h m   a n d   a  tar g et  ar ch itectu r e,   w e   ai m   to   p r o d u ce   s ch ed u les  r ea lizi n g   co m p r o m is e s   b et w ee n   t w o   o b j ec tiv es b y   m i n i m izi n g   Ma k esp a n   an d   m a x i m izi n g   r eliab ili t y .           Fig u r e  3 .  O b j ec t iv e  Sp ac es           Fig u r e  4 .   T h e  Pro p o s ed   A p p r o ac h   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.  9 ,   No .   3 ,  Ma r ch   2 0 1 8   :   7 8 9   –   7 9 8   794   4 . 1 .   Appro a ch  P rinciples     Ou r   ap p r o ac h   is   b ased   o n   t w o   s ch ed u li n g   h e u r is tic s   w i th   a n   ad ap tatio n   m o d u le  to   i m p r o v e  s o lu tio n   ex p lo r atio n   b y   ex te n d i n g   th e   s ea r ch   s p ac e.   T h e  t w o   h e u r is t ics  co o p er ate  w h ile   d ea lin g   a l ter n ati v el y   w it h   t h e  t w o   o b j ec tiv es:  Ma k esp an   a n d   r eliab ilit y .   W e  u s e  h ier ar ch ical  s c h ed u l in g   to   m i n i m ize   Ma k esp an   a n d   to   m ax i m ize  r eliab ilit y   b y   o p ti m izi n g   o n e  o b j ec tiv e  at  a  ti m e,   i.e ,   w e  tr an s f o r m   o n e  o f   o b j ec tiv es  in to   a   co n s tr ain t,  w h ich   a llo w s   t h e  s o lv in g   o f   th e   p r o b lem   b y   o p ti m izi n g   th e  s ec o n d   o b j ec tiv e  u n d er   th e  co n s tr ai n t   of   th e  f ir s t o n e.     As  s h o w n   i n   Fi g u r e  4 ,   th e  f ir s t   h eu r i s tic  AR B   ( A d ap tiv e  R eli ab ilit y - b ased   B i - o b j ec tiv e  h e u r is tic)   h as   as  i n p u t s   t h e  a lg o r it h m   A l g ,   t h e  ar c h itect u r e  A r c  a n d   a   GS FR   ( r eliab ilit y   o b j ec tiv e)   v al u e  0  as  a  co n s tr ai n t.   AR B   h e u r is tic  e x ec u tio n   lead s   to   a  s o lu t io n   w i t h   t w o   v al u e s   :  M ARB   a n d   A R B .   L ik e   AR B ,   A MB   ( A d ap tiv e   Ma k esp a n - b ased   B i - o b j ec tiv e  h eu r i s tic)   h a s   as  in p u ts   t h e  al g o r ith m   Alg ,   t h e  ar ch itect u r e  Ar c  an d   th e  s o l u tio n   p r o d u ce d   b y   A R B   h eu r i s tic.   T h e  Ma k e s p an   v al u e  M AR B ,   p r o d u ce d   b y   AR B ,   is   co n s id er ed   as  a  co n s tr ai n t  i n   o r d er   to   m ax i m ize  r eliab ilit y .   T h e  r esu lt  is   a  s ch ed u le  w ith   t w o   v al u es:  M A MB   an d   A MB .   C o o p er atio n   b et w ee n   o u r   h ier ar ch ical  h eu r is tics   lead s   to   a  s et  o f   s o l u tio n s   a m o n g   w h ic h   t h e  o p ti m al  o n es  ac co r d in g   to   P ar eto   o p tim al it y   ar e  s elec ted .       I n   th e  ca s e  o f   to o   clo s est  co m p r o m is e  v alu e s ,   w e  p r o p o s e  to   in tr o d u ce   an   ad ap tatio n   m o d u le  to   s ea r ch   f o r   n eig h b o r s .   No te  th a t  th e  f u ct io n   f   ass o ciati n g   d ec i s io n   a n d   o b j ec tiv e  s p ac es  is   n o t  s u r j ec tiv e.   T h at  m ea n s   t h er e  ca n   b e  a  co m p r o m i s e  v alu e   in   o b j ec tiv e  s p ac e  w h ic h   is   n o t  a s s o ciate d   w i th   a n y   s o l u tio n   ( s ch ed u li n g )   i n   d ec is io n   s p ac e.   Fo r   th is   r ea s o n ,   t h e  ad ap ta tio n   m u s t  o p er ate  o n   d ec is io n   s p ac e  b y   cr ea ti n g   n eig h b o r s   o f   a  g i v e n   s c h ed u le,   th is   o n e  ( n eig h b o r )   h av i n g   n e ce s s ar el y   a  co m p r o m is e  v alu e  in   o b j ec tiv e  s p a ce.               Fig u r e  5 .   A d ap tatio n   Mo d u le   Fig u r e  6 .   So lu tio n   T r an s la tio n         T o   ad j u s t  a  cu r r en t  s o lu tio n ,   th e  ad ap tatio n   m o d u le  ( Fo g u r e  5 )   is   b ased   o n   th e  n eig h b o r h o o d   s tr u ct u r e  co n ce p t  ( s u b s ec tio n   3 . ) .   I n   th i s   w o r k ,   a   p er m u ta tio n - b ased   n ei g h b o r h o o d   s tr u c tu r e  is   u s ed ;  it  is   d ef in ed   b y   t h e  f o llo w i n g   tr an s f o r m atio n :   V  : S    P ( S)  s u ch   t h at:    s ch ed u le  s     S   V  ( s )   =  {  s ’     s ’   i s   a  s ch ed u le  a s s o ciate d   to   a  g iv e n   p er m u tati o n   o f   s }         Fig u r e  6   is   an   ex a m p le  o f   to o   clo s est  co m p r o m is e  v al u es  f ( s )   ( b lu e  co lo r )   an d   f ( s ’ )   ( p in k   co lo r )   in   th e  o b j ec tiv e  s p ac e.   I n   t h i s   ca s e,   th e  ad ap tatio n   m o d u le  h as   t h e  r o le  o f   e x te n d in g   t h e  s ea r c h   s p ac e  b y   ap p l y in g   p er m u tatio n s   o n   s .   T h is   o n e  c o u ld   b e  r ep lace d   b y   o n e  o f   its   n eig h b o r s .   B y   ch a n g in g   t h e  s t ar tin g   co n s tr ai n t  f o r   co o p er atin g   h e u r is tic s   an d   u s i n g   t h e  ad ap tatio n   m o d u le,   a  r an g e  o f   s o lu t io n s   i s   o b tain ed   w h ile  t h e  o n es  t h at   s u it c u r r en t  n ee d s   ar e  s elec ted .     4 . 2 .   Schedu lin g   Alg o rit h m s     T h e  h eu r is tic s   A R B   an d   A MB   i m p le m e n ti n g   th e  p r o p o s ed   s o lu tio n   ar e  g r ee d y   li s t sc h ed u l in g .                     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       Bi - o b jective   S ch e d u lin g   w ith   C o o p era tin g   Heu r is tics   fo r   E mb ed d ed   R e a l - time  S ystem   ( K a lla   Ha mo u d i )   795         T h ey   co o p er ate  to   d ea l  alter n ati v el y   w it h   t h e  m a k e s p an   an d   th e  r eliab ili t y   o b j ec tiv es.   T h e  f ir s t   h eu r i s tic  is   b ased   o n   a  co s t  f u n ct io n   ca lled   s c h ed u le  p r ess u r e  ( eq u atio n   ( 3 )   in   s u b s ec tio n   2 . 2 . )   to   s elec t  th e   b est  tas k   w h ich   m i n i m izes  th e  len g th   o f   t h e  cr itical  p ath .   T h e  s u p er s cr ip t  n u m b er ,   i n   p ar en th e s es  i n   b o t h   A l g o r ith m s   A R B   an d   A MB ,   r ef er s   to   th e  h eu r i s tic  s tep .     C o n s tr ain ed   b y   a  s tar ti n g   co n s tr ain t  w h ich   i s   a  GSF R   v a lu e,   AR B   alg o r ith m   w o r k s   as  f o llo w s :   • Ini t ia liza t io n:  t w o   li s ts   ar e  u s ed ,   -   T (0)   com p :  is   t h e  co m p etito r   tas k   lis t  k n o w i n g   t h at  a  task   i s   s a id   to   b e   co m p etito r   if   it  is   n o t  y et  s c h ed u led   an d   all  its   p r ed ec ess o r s   ar e  alr ea d y   s ch ed u led ;   -   T ( 0 ) sched : sch ed u led   task   li s t  w h ic h   w ill co n s tit u te,   i n   th e  e n d ,   f i n al  s c h ed u le.   •  E v a lua t io n:  s tep   ( 1 )   ca lcu lates,  f o r   ea ch   co m p e tito r   tas k   i ts   s c h ed u le  p r ess u r e  o n   ea c h   p r o ce s s o r   s u ch   t h e   s p ec if ied   co n s tr ain t ( )   is   s ati s f ied .   •  Select io n:  th is   s tep   ( 2 )   is   a  s elec tio n   o f   t h e  b est  p a ir   ( task ,   p r o ce s s o r ) ,   th u s   t h e  o n e  m i n i m izi n g     s ch ed u le  p r ess u r e.   •  Up da t e:   s tep   ( 3 )   co n s i s ts   in   o n e  h a n d   to   ad d   th e  c h o s en   ta s k   to   s ch ed u led   tas k   li s t  a n d   i n   t h e  o th er   h a n d   to   r e m o v e  th e  c h o s en   tas k   f r o m   co m p eti to r   task   lis t  as  w ell  as   all  its   s u cc es s o r s   s u c h   th at  p r ed ec ess o r s   o f   th e   latter s   ar e  alr ea d y   s ch ed u led .     Step s   1 ,   2   an d   3   o f   A R B   alg o r ith m   ar e  r ep ea ted   u n til  th er e  ar e  n o   m o r e  co m p etito r   tas k s .   T h e  A R B   r esu lt   is   a  p air   ( M A RB ,  A RB )   r ep r esen tin g   Ma k e s p an   an d   G SF R   v a lu e s .   D u r in g   its   ex ec u t io n ,   AR B   alg o r it h m   m a y   r ef er   to   t h e  ad ap tatio n   m o d u le.   I n   a  s i m ilar   m a n n er   b u t  co n s tr ain ed   b y   Ma k e s p an   v al u e  p r o d u ce d   b y   AR B   al g o r ith m ,   A MB   a lg o r it h m   ai m s   to   o p ti m ize  t h is   ti m e  r eliab ilit y   o b j ec tiv e.   A MB   alg o r ith m   w o r k s   as   f o llo w s :                                         L i k e  AR B ,   A MB   m a y   a ls o   r ef er   to   a d ap tatio n   m o d u le  i f   s o lu tio n   ad j u s t m en t  is   n ec es s ar y .   A R B   an d   A MB   e x ec u t io n   ca n   b e  r ep ea ted   as  m a n y   ti m es  a s   t h e  d ec is io n   m a k er   d ec id es.  I n   ad d itio n ,   th e  s tar ti n g   co n s tr ain t c an   b e  m o d i f ied   to   cr ea te  a  n e w   p r o ce s s   in s ta n ce .   As  m u ch   f o r   AR B   as  f o r   AM B ,   in   th e   ca s e  o f   to o   clo s est  s o lu tio n s   ( in   o b j ec tiv e  s p ac e ) ,   th e  ad ap tatio n   p r o ce d u r e  co u ld   r ep lace   th e  cu r r en t  s o lu tio n   ( i n   d ec is io n   s p ac e)   b y   o n e  o f   i ts   n eig h b o r s .   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.  9 ,   No .   3 ,  Ma r ch   2 0 1 8   :   7 8 9   –   7 9 8   796     I n   o u r   w o r k ,   w e   p r o p o s e  p er m u tatio n - b ased   ad ap tatio n .   I t  co n s is ts   o f   g e n er atin g   s ch ed u les  a m o n g   w h ic h   t h er e  co u ld   b e  a  s c h e d u le  f r o m   w h ich   th e  s ea r ch   w il l  b e  r estar ted .   P er m u tatio n   ap p licatio n   o n   s   g en er ate s   s c h ed u les  t h at  ar e  n eig h b o r s   o f   s .   Ho w ev er ,   o n l y   s c h ed u les  s atis f y i n g   r ea l  ti m e  co n s tr ain t s   ar e   co n s id er ed .   A   cu r r en t  s c h ed u l e  s   is   r ep lace d   b y   o n e  o f   its   n eig h b o r s   i f   ( i)   th is   o n e  is   n o t  y et  s el ec ted   an d   ( ii)  its   co m p r o m is e  v al u e  is   n o t  c lo s est  to   th o s e  o f   alr ea d y   s ele cted   s ch ed u les  a n d   ( iii)  a m o n g   s   n ei g h b o r s ,   it  is   th is   w h ic h   co r r esp o n d s   to   th e  n o n - d o m in ated   co m p r o m i s e  v al u e  in   o b j ec tiv e  s p ac e.   I n   th e  ca s e  o f   n o   n eig h b o r   s atis f ie s   th e  t h r ee   co n d itio n s ,   s   is   s a v ed   as c u r r e n t  s o lu tio n .                                       I n   th i s   w a y ,   th e  s ea r ch   s p ac e  is   ex te n d ed   to   th e  Nei g h b o r h o o d   s tr u ctu r e  p r o d u ce d   b y   p er m u tatio n s .   A s   s o o s   as   a  s o lu tio n   ( s c h ed u le)   s at is f y in g   t h e  th r ee   co n d itio n s   ab o v e  i s   f o u n d ,   it  i s   co n s id er ed   as  th e  cu r r en t  s ch ed u le.   No te  th at,   s u ch   a  s c h ed u le  m a y   n o t b e  f o u n d ,   in   w h ic h   ca s e  cu r r en t sc h ed u le  i s   s a v ed .       5.   SI M UL AT I O N S     T o   ev alu ate  o u r   ap p r o ac h ,   w e  h a v e  ap p lied   th e  A MB   an d   AR B   h eu r i s tics   to   a  s et  o f   r an d o m   alg o r ith m   g r ap h s   an d   a n   ar ch i tectu r e  g r ap h   co m p o s ed   o f   3 ,   4 ,   an d   5   p r o ce s s o r s .   W e  u s e  S y n DE x   to   g e n er ate   th e  co m p lete  s et  o f   alg o r it h m   g r ap h s .   S y n DE x   is   a  C AD  to o l  f o r   o p tim izi n g   an d   im p le m e n ti n g   r ea l - ti m e   e m b ed d ed   s y s te m s   ( h ttp :// www . s y n d ex . o r g ) .   I t  h a s   b ee n   d esig n ed   an d   d ev elo p ed   in   th e  I NR I A   P a r is - R o cq u en co u r t Res ea r c h   C e n te r   Fra n ce .       W e  v ar y   t w o   p ar a m eter s :  t h e   n u m b er   o f   tas k   N= 2 0 ,   4 0 ,   6 0 ,   8 0 ,   1 0 0 ,   an d   th e  co m m u n i ca tio n - to - co m p u tatio n   r atio   ( C C R ) ,   d ef in ed   as  t h e  a v er ag e  co m m u n i ca tio n   ti m e  d i v id ed   b y   th e   av er ag e  co m p u tatio n   ti m e,   C C R =0 . 1 ,   1 ,   1 0 .   Fo r   ea c h   N,   1 0 0   g r ap h s   h a v e  b ee n   g e n er ated .       T h e  g en er al  o b j ec tiv e  o f   o u r   s i m u latio n s   i s   to   s tu d y   t h e  i m p ac t  o f   N,   P ,   a n d   C C R   o n   r elia b ilit y   a n d   m ak e s p an   i n tr o d u ce d   b y   AM B   an d   AR B .   W e  co m p ar e  o u r   h e u r is tic s   w i th   th e   h eu r i s tic   p r o p o s ed   in   [ 1 1 ] ,   ca lled   R B SA   ( R eliab le  B i - C r it er ia  Sch ed u li n g   A l g o r ith m )   an d   im p le m e n ted   in   S y n DE x .       T ab le  2   s h o w s   th e  m a k esp a n   an d   r eliab ilit y   r es u lt s   o f   e x ec u t i n g   h e u r is tic s   o n   an   Alg   co m p o s ed   o f   5 0   task s .   A R B - AM B *   is   t h e  h eu r is tics   AR B - AM B   w it h o u t a d ap tatio n   m o d u le.       T ab le  2 .  Ma k esp an   an d   R eliab ilit y   R es u lt s   f o r   N =5 0   T ask s   h e u r i s t i c s     R B S A   A R B - A M B *   A RB - A M B   e x e c u t i o n   1   6 4 4 . 7 2 ,   0 . 9 9 8 2 9 7   6 1 6 . 5 1 ,   0 . 9 9 8 5 3 9   6 1 6 . 5 1 ,   0 . 9 9 8 5 3 9   e x e c u t i o n   2   6 4 4 . 7 2 ,   0 . 9 9 8 2 9 7   6 0 8 . 7 6 ,   0 . 9 9 9 0 2 9   6 0 8 . 7 6 ,   0 . 9 9 9 0 2 9   e x e c u t i o n   3   6 4 4 . 7 2 ,   0 . 9 9 8 2 9 7   6 0 8 . 7 6 ,   0 . 9 9 9 0 2 9   5 9 9 . 7 0 ,   0 . 9 9 9 3 1 2           As  s h o w n   i n   t h is   tab le,   t h an k s   to   th e   ad ap tatio n   m o d u le,   A R B - AM B   ap p r o ac h   g i v es   in ter esti n g   r esu lt s   an d   b etter   th a n   R B S A   an d   AR B - AM B * .     Fig u r es  7 A ,   7 B ,   8 A ,   8 B ,   9 A   an d   9 B   s h o w s   m ak e s p an   a n d   r eliab ilit y   v ar iatio n s .   W e  ca n   s e e  f r o m   t h e  r esu lt s   th at  o u r   ap p r o ac h   p er f o r m s   b etter   th a n   R B S A   f o r   all  t h e  d atasets .       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       Bi - o b jective   S ch e d u lin g   w ith   C o o p era tin g   Heu r is tics   fo r   E mb ed d ed   R e a l - time  S ystem   ( K a lla   Ha mo u d i )   797       Fig u r e  7A .  I m p ac t  o f   N  Ma k e s p an   f o r   C C R =1     an d   P =4       Fig u r e  7B .  I m p ac t  o f   N  o n   R el iab ilit y   f o r     C C R =1   an d   P =4               Fig u r e  8A .   I m p ac t o f   C C R   o n   Ma k esp a n   f o r     N= 5 0   an d   P = 4   Fig u r e  8B .   I m p ac t o f   C C R   o n   R eliab ilit y   f o r     N= 5 0   an d   P =4               Fig u r e  9A .   I m p ac t o f   P   o n   Ma k esp an   f o r   N= 5 0     an d   C C R =1   Fig u r e  9B .   I m p ac t o f   P  o n   R el iab ilit y   f o r   N= 5 0     an d   C C R =1       6.   CO NCLU SI O N     W e  h av e  p r o p o s ed   a  n e w   b i - o b j ec tiv e  s ch ed u lin g   ap p r o ac h   p r o d u cin g   a u to m a ticall y   a  s tati c   d is tr ib u ted   s c h ed u le  o f   a  g i v en   ap p licatio n   A l g   o n   a  g iv e n   d is tr ib u ted   ar ch itect u r e  A r c.   T h e   aim   o f   o u r   ap p r o ac h   is   to   o p ti m ize  s i m u ltan eo u s l y   t w o   an ta g o n is t   o b j ec tiv es:  s y s te m ’ s   r u n - ti m e   ( Ma k e s p an )   an d   r eliab ilit y .   O u r   ap p r o ac h   is   b a s ed   o n   t w o   co o p er atin g   h e u r i s tics   ea c h   o f   t h e m   d ea lin g   w i th   a n   o b j ec tiv e.   T o   allo w   b etter   s p ac e  ex p lo r atio n ,   w e  i n teg r ate  a n   ad ap tatio n   m o d u le.     A d ap tatio n   is   b ased   o n   th e  n eig h b o r h o o d   co n ce p t  an d   i s   ac h iev ed   b y   s o l u tio n   p er m u ta tio n .   T h is   allo w s ,   in   t h e  ca s e  o f   t w o   clo s est  co m p r o m i s e  v al u es,  t o   o p er ate  o n   th e  d ec is io n   s p ac e  b y   g e n er ati n g   n eig h b o r s .   T h e y   ar e  s ch ed u l es  a m o n g   w h ic h   m a y   b e  a  s ch ed u le  th at  i s   s elec ted   i n   o r d er   t o   im p r o v e   ex p lo r atio n .   As  o u r   ap p r o ac h   is   P ar eto - b ased ,   a  s et  o f   co m p r o m is i n g   s o lu t io n s   ( s ch ed u les)  is   p r o d u ce d   allo w i n g   th e  d es ig n er   to   s elec t  th o s e  s a tis f y in g   t h e  cu r r e n t  n ee d s .   Si m u latio n s   r es u lt s   s h o w   t h at  t h e  p r o p o s ed   ap p r o ac h   p er f o r m s   b etter   th a n   R B S A   f o r   all  t h e  d atasets .     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.  9 ,   No .   3 ,  Ma r ch   2 0 1 8   :   7 8 9   –   7 9 8   798   RE F E R E NC E S   [1 ]     L .   Zh a n g ,   K.   L i,   C.   L i,   a n d   K .   L i,   “ Bi - o b jec ti v e   w o rk f lo w   sc h e d u l in g   o f   th e   e n e rg y   c o n su m p ti o n   a n d   re l iab il it y   i n   h e tero g e n e o u s co m p u ti n g   sy st e m s,”  In fo rm a t io n   S c ien c e s ,   v o l .   3 7 9 ,   p p .   2 4 1 – 2 5 6 ,   2 0 1 7 .   [2 ]     Y.  L iu ,   H.  Do n g ,   N.  L o h se ,   a n d   S .   P e tro v ic,  “ A   m u lt i - o b jec ti v e   g e n e ti c   a l g o rit h m   f o r  o p ti m iz a ti o n   o f   e n e rg y   c o n su m p ti o n   a n d   sh o p   f lo o r  p r o d u c ti o n   p e rf o rm a n c e , ”   In ter n a ti o n a l  J o u rn a l  o f  Pro d u c ti o n   Ec o n o mic s ,   v o l.   1 7 9 ,   p p .   2 5 9   –   2 7 2 ,   2 0 1 6 .   [3 ]     S .   K.  S o n ia  S a b rin a   Be n d i b ,   H a m o u d i  Ka ll a   a n d   Ch a f ik A ra r,   “ A   t w o - ste p   b icriteria   sc h e d u li n g   a p p ro a c h   f o r  d istri b u ted   re a l  t im e   s y ste m s,” in   In ter n a t io n a l  C o n fer e n c e   o n   E lec tro n ics ,   C o mp u ter   a n d   C o mp u ta ti o n ,   2 0 1 3 .   [4 ]     I.   S .   C.   Bo e re s  a n d   L .   Dru m m o n d ,   “ A n   e ff icie n t  w e i g h ted   b io b jec ti v e   sc h e d u li n g   a lg o rit h m   f o r  h e tero g e n e o u s   s y ste m s,”  IEE E  T ra n sa c ti o n s o n   De p e n d a b le a n d   S e c u re   Co m p u ti n g ,   v o l.   3 7 ,   p p .   3 4 9 – 3 6 4 ,   2 0 1 0 .   [5 ]     E.   Je a n n o t,   E .   S a u le,  a n d   D.  T r y str a m ,   “ Bi - o b jec ti v e   a p p ro x i m a ti o n   sc h e m e   f o r  m a k e sp a n   a n d   re li a b i li ty   o p ti m iza ti o n   o n   u n if o rm   p a ra ll e l   m a c h in e s,”  in   Pro c e e d in g s  o f  t h e   1 4 t h   i n ter n a t io n a l  E u ro - P a r  c o n fer e n c e   o n   Pa ra ll e l  Pro c e ss in g ,   se r.   Eu r o - P a r  ’0 8 .   Be rli n ,   He id e lb e rg :  S p rin g e r - V e rlag ,   2 0 0 8 ,   p p .   8 7 7 – 8 8 6 .   [6 ]     I.   S .   A .   G irau lt   a n d   D.  T r y stra m ,   “ Re li a b il it y   v e rsu s p e r f o r m a n c e   fo r  c rit ica l  a p p li c a ti o n s,”  Pa ra ll e l  a n d   Distri b u te d   Co mp u t in g ,   v o l .   6 9 ,   p p .   3 2 6 – 3 3 6 ,   2 0 0 9 .   [7 ]     X .   Q in   a n d   H.  Jia n g ,   “ A   n o v e l  f a u lt - to lera n t  sc h e d u li n g   a lg o rit h m   f o r  p re c e d e n c e   c o n stra in e d   tas k s  in   re a lt i m e   h e tero g e n e o u s sy ste m s, ”   Pa ra ll e l   Co mp u ti n g ,   v o l.   3 2 ,   p p .   3 3 1 – 3 5 6 ,   2 0 0 6 .   [8 ]     J.  J.  Do n g a rra ,   E.   Je a n n o t,   E.   S a u le,  a n d   Z.   S h i ,   “ Bi - o b jec ti v e   sc h e d u li n g   a l g o rit h m s  f o r  o p ti m izin g   m a k e sp a n   a n d   re li a b il it y   o n   h e tero g e n e o u s  sy s tem s,”  in   Pro c e e d in g s  o f  th e   n i n e tee n th   a n n u a l  ACM   sy mp o si u m  o n   P a ra l lel  a lg o rith ms   a n d   a rc h it e c tu re s ,   se r.   S P AA   ’0 7 .   Ne w   Yo rk ,   NY ,   USA:  A CM ,   2 0 0 7 ,   p p .   2 8 0 – 2 8 8 .   [9 ]     S .   H.  M .   W .   H.  T o p c u o u g lu ,   “ P e rf o rm a n c e - e ff e c ti v e   a n d   lo w - c o m p lex it y   t a sk   sc h e d u li n g   f o r  h e tero g e n e o u s   c o m p u ti n g , ”   IEE E  T r a n s a c ti o n s o n   Pa r a ll e l  a n d   Distrib u ted   S y ste ms ,   v o l.   1 3 ,   p p .   2 6 0 – 2 7 4 ,   2 0 0 2 .   [1 0 ]     M .   Ha k e m   a n d   F .   Bu telle,  “ Re li a b il it y   a n d   sc h e d u li n g   o n   sy ste m s  su b jec t  to   f a il u re s, ”   in   Pa ra ll e l  Pro c e ss in g ,   2 0 0 7 .   ICPP   2 0 0 7 .   I n ter n a t io n a l   Co n fer e n c e   o n ,   2 0 0 7 ,   p p .   3 8 – 3 8 .   [1 1 ]     A .   G .   I.   A ss a y a d   a n d   H.  Ka ll a ,   “ A   b icriteria   sc h e d u li n g   h e u risti c   f o r  d istri b u te d   e m b e d d e d   sy ste m s  u n d e r  re li a b il it y   a n d   re a lt im e   c o n stra in ts, ”   in   T h e   In ter n a t io n a l  Co n fer e n c e   o n   De p e n d a b le  S y ste ms   a n d   Ne two rk s,  I EE E  Co mp u ter   S o c iety ,   2 0 0 4 .   [1 2 ]     A .   G irau lt   a n d   H.  Ka ll a ,   “ A  n o v e l  b icriteria   sc h e d u li n g   h e u risti c s  p ro v id in g   a   g u a ra n tee d   g lo b a l  s y ste m   f a il u re   ra te,”  IEE E  T ra n sa c ti o n s  o n   De p e n d a b le a n d   S e c u re   Co m p u ti n g ,   v o l.   6 ,   n o .   4 ,   p p .   2 4 1 – 2 5 4 ,   2 0 0 9 .   [1 3 ]     A .   Do g a n   a n d   F .   Oz g u n e r,   “ Bio b jec ti v e   sc h e d u li n g   a lg o rit h m s  f o r  e x e c u ti o n   ti m e - re li a b il it y   trad e - o ff   in   h e tero g e n e o u s co m p u ri n g   sy ste m s,”  T h e   c o mp u ter   jo u rn a l ,   v o l .   4 8 (3 ),   p p .   3 0 0 – 3 1 4 ,   2 0 0 5 .   [1 4 ]     P .   P . Ch it ra ,   “ Co m p a riso n   o f   e v o l u ti o n a ry   c o m p u tatio n   a lg o rit h m s  f o r  so lv in g   b i - o b jec ti v e   tas k   s c h e d u li n g   p ro b lem   o n   h e tero g e n e o u s  d istri b u ted   c o m p u ti n g   s y ste m s,”  S a d h a n a ,   In d ia n   Aca d e my   o f  S c ien c e s ,   v o l.   3 6 ,   p .   1 6 7 U 1 8 0 ,   2 0 1 1 .   [1 5 ]     Y.  S o re l,   “ T h e   a l g o rit h m   a rc h it e c tu re   a d e q u a ti o n   m e th o d o l o g y , ”   in   T h e   M a ss ive ly  Pa ra ll e l  Co mp u ti n g   sy ste ms ,  1 9 9 4 .   [1 6 ]     J.  W .   S .   S h a tz  a n d   M .   G o to ,   “ T a sk   a ll o c a ti o n   f o r  m a x i m i z in g   re li a b il it y   o f   d istri b u ted   c o m p u ter  s y ste m s,”  IEE E   T ra n s.  C o mp u ter s ,   v o l.   4 1 ,   p p .   1 5 6 – 1 6 8 ,   1 9 9 2 .   [1 7 ]     R.   T .   M a rler  a n d   J.  S .   A ro ra ,   “ S u rv e y   o f   m u lt io b jec ti v e   o p ti m iza ti o n   m e th o d s  f o r  e n g in e e rin g ,   ” S tru c tu ra l  a n d   M u lt id isc ip l in a ry   Op ti miza ti o n ,   v o l.   2 6 ,   p p .   3 6 9 – 3           Evaluation Warning : The document was created with Spire.PDF for Python.