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 p r o p o se 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 d istri b u te d   re a ti m e   e m b e d d e d   sy ste m t h a a im 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 h a v e   to   b e   o u tl in e d F irst,   a   h iera rc h ica c o o p e ra ti o n   b e tw e e n   h e u risti c e n su rin g   to   trea a lt e rn a ti v e l y   th e   o b jec ti v e 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 a   se 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 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 s ch ed u l in g   R eliab ilit y     P ar eto     Co p y rig h ©   2 0 1 8   In stit u te o 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 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 2 53,   R o u te  d C o n s ta n ti n e.   Fes d is ,   B atn 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 p r in cip le  k e y   in   d is tr ib u t ed   r ea tim 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 in to   ac co u n 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 m ap p in g   o f   task s   to   p r o ce s s o r s   ar 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 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 b tak en   i n to   ac co u n t.  B i - o b j ec tiv 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 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 o f   th m o s ac ti v r esear ch   f iel d   in   th co n tex o f   d is tr ib u ted   r eal - ti m 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 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 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   s et  o f   i n d ep en d en tas k s   o n   s et  o f   h eter o g en eo u s   p r o ce s s o r s   [ 5 ] .   T h ai m   is   to   co n v er g 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 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 o f   th o b j ec tiv es.  I n   [ 7 ] ,   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 s ele ctin g   p r o ce s s o r s   m ax i m izin g   t h 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 ea r lies s tar ti m e.   T h w o r k   p r esen ted   in   [ 8 ]   ex ten d s   t h li s t sch ed u lin g   h eu r i s tic  [ 9 ] .   T h p air   ( f ail u r 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 n o r m alize d   an d   co m b in ed   i n   w ei g h ted   co s 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 au th o r s   o f   [ 4 ]   p r o p o s 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 Ma k e s p an   an d   t h 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 w o r k   in   [ 1 1 ]   p r esen ts   b i - o b j ec tiv s ch ed u lin g   h eu r i s tic   w h er 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   co m p r o m i s f u n ctio n .   T h is   o n s elec ts   f o r   ea ch   o p er atio n   th 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 p r o ce s s o r s   m a x i m iz es  th r eliab ilit y   a n d   m i n i m iz es  th r u n - ti m e.   f u n ctio n   p ar a m eter   m a y   b v ar ied   to   f av o r   o n cr iter io n .   I n   [ 1 2 ] ,   a   f r a m e w o r k   f o r   th b i - o b j ec tiv 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 r eliab ilit y   i s   p r o p o s ed .   T h g lo b al  r eliab il it y   o f   th s y s te m   i s   co n s id er ed .   T h 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 u s er   to   c h o o s 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   b i - o b j e ctiv g e n etic  al g o r it h m   i n   w h ich   w ei g h ted   s u m   ap p r o ac h   is   u s ed   to   d ea 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 b icr iter ia  s ch e d u lin g   p r o b lem .   I n   ad d itio n ,   co m p ar is io n   is   m a d w it h   th w ei g h ted - s u m   b as ed   b i - o b j ec tiv 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 s ch ed u li n g   in   d is tr ib u te d   r ea ti m 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 th 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   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 b est  s p ac ex p lo r atio n .   T h 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 p r esen ted .   Sectio n   3 ,   r ec alls   th m u lti - o b j ec tiv o ti m izatio n   an d   p r esen ts   b i cr iter ia  s ch ed u li n g   as  b i - o b j ec tiv p r o b le m .   I n   s ec tio n   4 ,   t h p r o p o s ed   ap p r o ac h   is   d escr ib ed .   B ef o r co n clu d i n g ,   s ec tio n   5   d ep icts   s o m 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 as s u m p tio n s   ar 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 m b ed d ed   s y s te m s   ar co m p o s ed   o f   t wo   p r in cip al  p ar ts ,   w h ich   ar t h e   s o f t w ar e   p ar t ( th ap p licatio n   alg o r it h m )   an d   th h ar d w ar 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 d escr ib in g   th 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 co m p o n en t s   ( ar ch itectu r m o d el) ,   an d   th ex ec u tio n   ch ar ac ter is t ic s   o f   th al g o r ith m   o n to   th ar ch itect u r   ( ex ec u tio n   m o d el) .     T h ap p licatio n   is   m o d eled   b y   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   task   a n d   ea ch   ed g i s   d ata  d ep en d en c y .               Fig u r 1 A .   A l g o r ith m   Gr ap h   A l g   Fig u r 1 B .   A r ch itect u r Gr ap h   A r c         A   ta s k   o f   A l g   ca n   b eit h er   an   ex ter n al  i n p u t /o u tp u tas k   o r   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 in p u 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 i n p u t s   o f   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 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 co m p u tatio n   ta s k s .   T h d ata - d ep en d en c ies   b et w ee n   tas k s   ar 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 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 ar ch itectu r i s   m o d eled   b y   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 is   a   co m m u n icatio n   li n k .   Fi g u r 1 B   g iv e s   a n   e x a m p le  o f   a n   ar c h itectu r 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 x 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 w o r s ca s ex ec u ti o n   ti m o f   th tas k   ti  o n   t h p r o ce s s o r   p j ,   ex p r ess ed   i n   ti m u n it s .   A s s u m i n g   th at  p r o ce s s o r s   ar h eter o g en eo u s ,   o n ta s k   co u ld   h a v d if f er en e x ec u tio n   ti m es  o n   d if f er en p r o ce s s o r s .   W h en   g i v en   ta s k   ca n n o t   b 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 v al u ”.   On   th o t h er   h a n d ,   to   e ac h   p air   ( d i,  lj ) ,   i 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   ti m t h at  ex p r e s s es  t h w o r s ca s tr an s m i s s io n   ti m o f   t h d ata  d ep en d en c y   d o n   t h co m m u n icatio n   lin k   lj .   Fu r t h e r m o r e,   th in tr a - p r o ce s s o r   co m m u n icatio n   ti m is   s u p p o s e d   to   b 0   tim u n it.   Fo r   in s ta n ce ,   E x f o r   A l g   an d   A r 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     A   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 m o d elin g   u s in g   g r ap h s ,   is   u s e f u f o r   o b j ec tiv 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 m a k esp a n   o r   s ch ed u le  le n g th   i s   th e n d   ex ec u tio n   ti m o f   th 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 ti m a 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 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 h e u r is tic  s tep   an d   co m p   to   th s et  o f   co m p eti to r   task s   i.e   th o s n o 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 ea r lies t ti m e   a 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 ;     (n) ti   : th lates t star t ti m 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 to   co n s id er ed ,   h en ce   th 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 th b est  tas k   w h ich   m i m i zises   t h le n g t h   o f   th 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 s u b ject  to   f ailu r es.  A cc o r d in g   to   th 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   P o is s o n   la w   w i th   co n s tan p ar a m e ter   λ ,   t h r eliab il it y   o f   p r o ce s s o r   P   ( r esp ec tiv el y ,   co m m u n icatio n   lin k   L )   d u r in g   t h d u r atio n   d   is :   ( 4 )           T h r eliab ilit y   o f   t h ta s k   o r   d ata  d ep en d en c y   p lace d   o n to   th h ar d w ar co m p o n e n C ,   w it h   a n   ex ec u t io n   ti m ex e( X,   C ) ,   is   t h en   d e f in ed   as  f o llo w s :     ( 5 )         B ec au s th r eliab ilit y   d ep en d s   in tr in s icall y   o n   th d u r atio n   o f   th 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 u s u al  m o d el  o f   t h r eliab ilit y   [ 1 6 ] ,   w u s t h co n ce p o f   GS F R   ( Glo b al  S y s te m   Fail u r R ate)   d ef i n ed   in   [ 1 2 ] ,   an d   n o ted   .     T h GSFR   o f   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 U( S)  i s   t h to tal  u tili za t io n   o f   t h h ar d w ar r eso u r ce s   an d   R ( S)  it s   r eliab ilit y .   T h G SF R   is   t h e   f ail u r r ate  p er   ti m e   u n it  o f   t h 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 s i n g le   tas k   s ch ed u led   o n to   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 p r o b le m   i s   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 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 m   i s   t h n u m b er   o f   o b j ec tiv f u n c tio n s ,   k   is   t h n u m b er   o f   i n eq u alit y   co n s tr ai n ts   a n d   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   d esi g n   v ec to r ,   also   ca lled   d ec is io n   v ec to r ,   w h er n   is   th n u m b er   o f   its   i n d ep en d en v ar iab les x i .   f ( x )     E n   is   v ec to r   o f   o b j ec tiv f u n ctio n s   w h er e: \           f i ( x )   ar al s o   ca lle d   o b j ec tiv o r   cr iter ia.   E ac h   p o in i n   t h d esig n   s p ac m ap s   to   p o in i n   t h o b j ec tiv s p ac b u t th r e v er s e   m a y   n o t to   b tr u e.         E v alu a tio n   o f   s o l u tio n s   is   d o n b y   u s i n g   t h 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   s o lu ti o n   s u c h   as  i m p r o v i n g   o n o b j ec tiv ca n b d o n 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 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 v ec to r   in   m u l ti - di m en s io n a l sp ac ( Fig u r 2 ) .       L et  a n d   z’   b t w o   p o in ts   o f   t h o b j ec tiv s p ac e.   Fo r m al l y ,   th 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 a   p o in t z’ :           W h ile  th co n ce p o f   d o m i n an ce   i s   r elate d   to   o b j ec tiv s p ac e,   th 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 2 .   Dec is io n   a n d   Ob j ec t iv 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 P ar eto   o p tim al  s et  w h ile  th co r r esp o n d in g   o b j ec tiv v ec to r s   i.e   t h o s o n es  n o d o m in ated ,   ar s aid   to   b o n   t h P ar eto   f r o n t.  T h 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 n eig h b o r h o o d   o a   s o lu tio n   s     S   i s   a   s u b s et   o c o n fig u r a tio n s   o r   s o lu tio n s   o S   th a a r d ir ec tly  r ea ch a b le  b a   g iven   tr a n s fo r ma tio n   o s .   I 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   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 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  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 is   s et  o f   s o l u t io n s   an d   P ( S)  is   s u b s et  o f   S.  Su ch   co n ce p is   u s e f u i n   s e ar ch   s p ac s tr u ct u r in g   an d   in   d ef in i n g   th s et  o f   s o lu tio n s   th at  ca n   b r ea ch ed   f r o m   g iv e n   s o l u tio n   th r o u g h   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 an d   is   th er ef o r co n s id er ed   as  b i - o b j ec tiv 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 ar 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   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 ev a lu ated   i n   t h o b j ec tiv s p ac ( Fi g u r 3 )   d ef in ed   b y   t h co n s id er ed   o b jectiv es  ( s u b s ec tio n   2 . 2 . ) .   T h f ir s o b j ec tiv 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 co s f u n ctio n   n a m ed   s ch ed u le  p r ess u r ( eq u atio n   ( 3 ) )   w h ile  t h s ec o n d   o b j ec tiv 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 ,   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 m ak e s   co m p r o m i s b et w ee n   t h Ma k e s p an   an d   th 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 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   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 3 O b j ec t iv Sp ac es           Fig u r 4 .   T h 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 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 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 t w o   o b j ec tiv es:  Ma k esp an   a n d   r eliab ilit y .   W u s 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 o b j ec tiv at  ti m e,   i.e ,   w tr an s f o r m   o n 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 s o lv in g   o f   th e   p r o b lem   b y   o p ti m izi n g   th s ec o n d   o b j ec tiv u n d er   th co n s tr ai n t   of   th f ir s t o n e.     As  s h o w n   i n   Fi g u r 4 ,   th f ir s t   h eu r i s tic  AR B   ( A d ap tiv R eli ab ilit y - b ased   B i - o b j ec tiv h e u r is tic)   h as   as  i n p u t s   t h a lg o r it h m   A l g ,   t h ar c h itect u r A r a n d   a   GS FR   ( r eliab ilit y   o b j ec tiv e)   v al u as  co n s tr ai n t.   AR B   h e u r is tic  e x ec u tio n   lead s   to   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 h eu r i s tic)   h a s   as  in p u ts   t h al g o r ith m   Alg ,   t h ar ch itect u r Ar an d   th 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 Ma k e s p an   v al u M AR B ,   p r o d u ce d   b y   AR B ,   is   co n s id er ed   as  co n s tr ai n i n   o r d er   to   m ax i m ize  r eliab ilit y .   T h r esu lt  is   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   s et  o f   s o l u tio n s   a m o n g   w h ic h   t h 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 s elec ted .       I n   th ca s o f   to o   clo s est  co m p r o m is v alu e s ,   w p r o p o s 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 th 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 s p ac es  is   n o s u r j ec tiv e.   T h at  m ea n s   t h er ca n   b co m p r o m i s v alu e   in   o b j ec tiv s p ac w h ic h   is   n o 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 ad ap ta tio n   m u s o p er ate  o n   d ec is io n   s p ac b y   cr ea ti n g   n eig h b o r s   o f   g i v e n   s c h ed u le,   th is   o n ( n eig h b o r )   h av i n g   n e ce s s ar el y   co m p r o m is v alu in   o b j ec tiv s p a ce.               Fig u r 5 .   A d ap tatio n   Mo d u le   Fig u r 6 .   So lu tio n   T r an s la tio n         T o   ad j u s cu r r en s o lu tio n ,   th ad ap tatio n   m o d u le  ( Fo g u r 5 )   is   b ased   o n   th n eig h b o r h o o d   s tr u ct u r co n ce p ( 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 is   u s ed it  is   d ef in ed   b y   t h f o llo w i n g   tr an s f o r m atio n :   : S    P ( S)  s u ch   t h at:    s ch ed u le  s     S   ( s )   s     s   i s   s ch ed u le  a s s o ciate d   to   g iv e n   p er m u tati o n   o f   s }         Fig u r 6   is   an   ex a m p le  o f   to o   clo s est  co m p r o m is v al u es  f ( s )   ( b lu co lo r )   an d   f ( s )   ( p in k   co lo r )   in   th o b j ec tiv s p ac e.   I n   t h i s   ca s e,   th ad ap tatio n   m o d u le  h as   t h r o le  o f   e x te n d in g   t h s ea r c h   s p ac b y   ap p l y in g   p er m u tatio n s   o n   s .   T h is   o n c o u ld   b r ep lace d   b y   o n o f   its   n eig h b o r s .   B y   ch a n g in g   t h s t ar tin g   co n s tr ai n 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 ad ap tatio n   m o d u le,   r an g o f   s o lu t io n s   i s   o b tain ed   w h ile  t h o n es  t h at   s u it c u r r en n ee d s   ar s elec ted .     4 . 2 .   Schedu lin g   Alg o rit h m s     T h h eu r is tic s   A R B   an d   A MB   i m p le m e n ti n g   th p r o p o s ed   s o lu tio n   ar 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 alter n ati v el y   w it h   t h m a k e s p an   an d   th r eliab ili t y   o b j ec tiv es.   T h f ir s t   h eu r i s tic  is   b ased   o n   co s f u n ct io n   ca lled   s c h ed u le  p r ess u r ( eq u atio n   ( 3 )   in   s u b s ec tio n   2 . 2 . )   to   s elec th e   b est  tas k   w h ich   m i n i m izes  th len g th   o f   t h cr itical  p ath .   T h s u p er s cr ip 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 h eu r i s tic  s tep .     C o n s tr ain ed   b y   s tar ti n g   co n s tr ain w h ich   i s   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 u s ed ,   -   T (0)   com p is   t h co m p etito r   tas k   lis k n o w i n g   t h at  task   i s   s a id   to   b e   co m p etito r   if   it  is   n o y et  s c h ed u led   an d   all  its   p r ed ec ess o r s   ar alr ea d y   s ch ed u led ;   -   T ( 0 ) sched : sch ed u led   task   li s w h ic h   w ill co n s tit u te,   i n   th 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 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   s elec tio n   o f   t h b est  p a ir   ( task ,   p r o ce s s o r ) ,   th u s   t h o n 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 h a n d   to   ad d   th c h o s en   ta s k   to   s ch ed u led   tas k   li s a n d   i n   t h o th er   h a n d   to   r e m o v th c h o s en   tas k   f r o m   co m p eti to r   task   lis 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 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 r ep ea ted   u n til  th er ar n o   m o r co m p etito r   tas k s .   T h A R B   r esu lt   is   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 ad ap tatio n   m o d u le.   I n   s i m ilar   m a n n er   b u co n s tr ain ed   b y   Ma k e s p an   v al u 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 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 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 is   n ec es s ar y .   A R B   an d   A MB   e x ec u t io n   ca n   b r ep ea ted   as  m a n y   ti m es  a s   t h d ec is io n   m a k er   d ec id es.  I n   ad d itio n ,   th s tar ti n g   co n s tr ain t c an   b m o d i f ied   to   cr ea te  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 o f   to o   clo s est  s o lu tio n s   ( in   o b j ec tiv s p ac e ) ,   th ad ap tatio n   p r o ce d u r co u ld   r ep lace   th cu r r en s o lu tio n   ( i n   d ec is io n   s p ac e)   b y   o n 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 p er m u tatio n - b ased   ad ap tatio n .   I 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 co u ld   b s c h e d u le  f r o m   w h ich   th s ea r ch   w il b 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 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 ti m co n s tr ain t s   ar e   co n s id er ed .   A   cu r r en s c h ed u l s   is   r ep lace d   b y   o n o f   its   n eig h b o r s   i f   ( i)   th is   o n is   n o y et  s el ec ted   an d   ( ii)  its   co m p r o m is v al u is   n o c lo s est  to   th o s 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 n o n - d o m in ated   co m p r o m i s v al u in   o b j ec tiv s p ac e.   I n   th ca s o f   n o   n eig h b o r   s atis f ie s   th t h r ee   co n d itio n s ,   s   is   s a v ed   as c u r r e n s o lu tio n .                                       I n   th i s   w a y ,   th s ea r ch   s p ac is   ex te n d ed   to   th Nei g h b o r h o o d   s tr u ctu r p r o d u ce d   b y   p er m u tatio n s .   A s   s o o s   as   s o lu tio n   ( s c h ed u le)   s at is f y in g   t h th r ee   co n d itio n s   ab o v i s   f o u n d ,   it  i s   co n s id er ed   as  th cu r r en s ch ed u le.   No te  th at,   s u ch   s c h ed u le  m a y   n o t b f o u n d ,   in   w h ic h   ca s 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 h a v ap p lied   th A MB   an d   AR B   h eu r i s tics   to   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 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 u s S y n DE x   to   g e n er ate   th 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   C AD  to o 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 h a s   b ee n   d esig n ed   an d   d ev elo p ed   in   th 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 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 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 a v er ag co m m u n i ca tio n   ti m d i v id ed   b y   th e   av er ag 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 b ee n   g e n er ated .       T h g en er al  o b j ec tiv o f   o u r   s i m u latio n s   i s   to   s tu d y   t h i m p ac 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 co m p ar 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 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 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 ca n   s e f r o m   t h 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 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 7A I m p ac o f   Ma k e s p an   f o r   C C R =1     an d   P =4       Fig u r 7B I m p ac o f   o n   R el iab ilit y   f o r     C C R =1   an d   P =4               Fig u r 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 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 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 9B .   I m p ac t o f   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 h av p r o p o s ed   n e w   b i - o b j ec tiv 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   s tati c   d is tr ib u ted   s c h ed u le  o f   g i v en   ap p licatio n   A l g   o n   g iv e n   d is tr ib u ted   ar ch itect u r 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 ex p lo r atio n ,   w 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 n eig h b o r h o o d   co n ce p 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 ca s o f   t w o   clo s est  co m p r o m i s v al u es,  t o   o p er ate  o n   th d ec is io n   s p ac b y   g e n er ati n g   n eig h b o r s .   T h e y   ar s ch ed u l es  a m o n g   w h ic h   m a y   b 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 ,   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 d es ig n er   to   s elec th o s s a tis f y in g   t h cu r r e n n ee d s .   Si m u latio n s   r es u lt s   s h o w   t h at  t h 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 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 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 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 J o u rn a o 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 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 d istri b u ted   re a t im e   s y ste m s,” in   In ter n a t io n a 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 a n d   L .   Dru m m o n d ,   A n   e ff icie n 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 h e tero g e n e o u s   s y ste m s,”  IEE 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 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 o t h e   1 4 t h   i n ter n a t io n a E u ro - P a c o n fer e n c e   o n   Pa ra ll e Pro c e ss in g ,   se r.   Eu r o - P a ’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 c rit ica a p p li c a ti o n s,”  Pa ra ll e 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 f a u lt - to lera n sc h e d u li n g   a lg o rit h m   f o p re c e d e n c e   c o n stra in e d   tas k 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 f o 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 sy s tem s,”  in   Pro c e e d in g o th e   n i n e tee n th   a n n u a ACM   sy mp o si u 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 h e tero g e n e o u s   c o m p u ti n g ,   IEE T r a n s a c ti o n s o n   Pa r a ll e 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 su b jec to   f a il u re s,   in   Pa ra ll e 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 d istri b u te d   e m b e d d e d   sy ste m u n d e 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 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 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 ,   n o v e b icriteria   sc h e d u li n g   h e u risti c p ro v id in g   a   g u a ra n tee d   g lo b a s y ste m   f a il u re   ra te,”  IEE T ra n sa c ti o n 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 f o 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 f o 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 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 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 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 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 f o e n g in e e rin g ,   S tru c tu ra 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.