I nte rna t io na l J o urna l o f   E lect rica l a nd   Co m p ute E ng in ee ring   ( I J E CE )   Vo l.   11 ,   No .   3 J u n e   2 0 2 1 ,   p p .   2 4 7 7 ~ 2 4 8 9   I SS N:  2 0 8 8 - 8708 DOI : 1 0 . 1 1 5 9 1 / i j ec e . v 1 1 i 3 . p p 2 4 7 7 - 2 4 8 9          2477       J o ur na l ho m ep a g e h ttp : //ij ec e. ia esco r e. co m   H y brid  l o a b a la nce  ba sed o n g en e tic  a lg o rith m  in  c l o ud  e nv iro n m en t       Wa la a   S a ber 1 W a lid   M o us s a 2 A t ef   M .   G hu nie m 3 , R a w y a   R izk 4   1, 4 El e c tri c a En g in e e rin g   De p a rtm e n t,   P o rt  S a i d   Un iv e rsity ,   P o rt  S a i d ,   Eg y p t   2, 3 El e c tri c a En g in e e rin g   De p a rtm e n t,   S u e z   Ca n a Un iv e rsity ,   Is m a i li a ,   Eg y p t       Art icle  I nfo     AB ST RAC T     A r ticle  his to r y:   R ec eiv ed   Au g   9 ,   2 0 20   R ev i s ed   Dec   18 ,   20 20   A cc ep ted   Dec   2 9 ,   2 0 2 0       L o a d   b a lan c in g   is  a n   e ff ici e n m e c h a n is m   to   d istri b u te  lo a d o v e c lo u d   re so u rc e in   a   w a y   th a m a x i m iz e re so u rc e   u ti li z a ti o n   a n d   m in im ize s   re sp o n se   ti m e .   M e tah e u risti c   tec h n i q u e a re   p o w e r f u tec h n iq u e f o so lv in g   th e   lo a d   b a lan c in g   p r o b lem s.  Ho w e v e r,   t h e se   tec h n iq u e su f fe f ro m   e ff ici e n c y   d e g ra d a ti o n   in   larg e   sc a le  p ro b lem s.  T h is  p a p e p r o p o se th re e   m a in   c o n tri b u t io n to   s o lv e   th is  l o a d   b a lan c i n g   p ro b lem .   F irst,   it   p ro p o se a   h e tero g e n e o u i n it ialize d   l o a d   b a l a n c in g   (HIL B)  a lg o rit h m   to   p e rf o rm   a   g o o d   tas k   sc h e d u li n g   p r o c e ss   th a i m p ro v e th e   m a k e sp a n   in   t h e   c a se   o h o m o g e n e o u o r   h e tero g e n e o u r e so u rc e a n d   p ro v id e a   d irec ti o n   to   re a c h   o p ti m a lo a d   d e v iatio n .   S e c o n d ,   it   p r o p o se a   h y b rid   lo a d   b a lan c e   b a se d   o n   g e n e ti c   a lg o r it h m   (H L B GA a a   c o m b in a ti o n   o f   HIL a n d   g e n e ti c   a lg o r it h m   (GA ).   T h ird ,   a   n e w l y   f o r m u late d   f it n e ss   f u n c ti o n   t h a m in i m ize th e   lo a d   d e v iatio n   is   u se d   f o GA .   T h e   sim u latio n   o f   th e   p r o p o se d   a l g o rit h m   is  im p le m e n ted   in   th e   c a se o f   h o m o g e n e o u a n d   h e tero g e n e o u r e so u rc e in   c lo u d   re so u rc e s.  T h e   sim u latio n   re su lt s   sh o w   th a t   th e   p r o p o se d   h y b rid   a lg o rit h m   o u tp e rf o r m o th e c o m p e ti to a lg o rit h m s   in   ter m s   o m a k e sp a n ,   re so u rc e   u ti li z a ti o n ,   a n d   lo a d   d e v i a ti o n .   K ey w o r d s :   C lo u d   co m p u tin g   Gen etic  al g o r ith m   L o ad   b alan cin g   L o ad   d ev iatio n     Me tah e u r is tic   T h is i a n   o p e n   a c c e ss   a rticle   u n d e r th e   CC B Y - SA   li c e n se .     C o r r e s p o nd ing   A uth o r :   R a w y a   R iz k   El ec tr ical  E n g i n ee r i n g   Dep ar t m en t   P o r t Said   Un iv er s it y     P o r t Said ,   E g y p t   E m ail: r . r izk @ e n g . p s u . ed u . e g       1.   I NT RO D UCT I O N     C lo u d   co m p u tin g   tec h n o lo g y   p r o v id es  lo o f   s er v ice s   to   all  u s er s   o v er   th i n ter n e u s i n g   v er y   lar g e   s ca lab le  an d   v ir tu al ized   r eso u r ce s .   T h m ain   o b j ec tiv o f   th clo u d   is   to   p r o v id s er v ices  all  o v er   th w o r ld   w it h   m i n i m u m   co s t   an d   h i g h   p er f o r m a n ce   [ 1 ,   2 ] .   To   h av t h ab ilit y   to   a llo w   all   h u g n u m b er   o f   clie n t s   all   o v er   th w o r ld   to   s h ar clo u d   r eso u r ce s   an d   p r o v id th e m   w ith   h i g h - q u alit y   s er v ice  i n   r ea s o n ab le  ti m e,   al l   clien t s   r eq u est s   s h o u ld   b h a n d led   in   a n   e f f icie n w a y   t h at   d o n w a s te  t i m e   an d   r eso u r ce s .   Fo r   th at   r ea s o n ,   th er is   b ig   n ee d   f o r   lo ad   b alan cin g   tec h n iq u es  w h ic h   a r e   th m a s ter   k e y   f o r   t h s u c ce s s   o f   a n y   clo u d   s er v ices   p r o v id er .   L o ad   b alan cin g   tr ies to   k ee p   clo u d   n o d es  eq u all y   lo ad ed   to   av o id   s it u a tio n   w h er s o m e   o f   th r eso u r ce s   ar o v er lo ad ed   w h ile  s o m o th er s   ar u n d er   l o ad ed   w h ich   as  r es u lt  r ed u c th r esp o n s e   ti m o f   th ass i g n ed   tas k s   [3 - 5 ] .   L o ad   b alan cin g   is   an   ef f icie n tech n iq u u s ed   to   d is tr ib u te  w o r k lo ad s   o v er   r eso u r ce s   in   w a y   th a i m p r o v r eso u r ce   u tili za t io n   an d   r esp o n s ti m e.   L o ad   b alan cin g   tr ies  to   k ee p   clo u d   r eso u r ce s   eq u all y   lo ad ed   an d   av o id   r eso u r ce s   b ec o m in g   o v er - lo ad ed   o r   u n d er - lo ad ed   [ 6 ] .     T r a d itio n al  alg o r it h m s   [ 7 - 11]   ar u s ed   to   s o l v t h is   p r o b le m .   Ho w e v er ,   th e s al g o r ith m s   h a v e   li m ita tio n s   in   th ca s o f   co m p lex   an d   lar g e   s ca le  p r o b le m s .   Me tah e u r is tic  al g o r it h m s   s u c h   as  p ar ticle  s w ar m   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I n t J   E lec  &   C o m p   E n g ,   Vo l.  11 ,   No .   3 J u n 2 0 2 1   :   2 4 7 7   -   2489   2478   o p tim izatio n   ( P SO)   [ 1 2 ] ,   an co lo n y   o p ti m izatio n   ( AC O)   [ 1 3 ] ,   a r tif icial  b ee   co lo n y   ( A B C )   [ 1 4 ] ,   an d   g en etic   alg o r ith m   ( G A )   [ 1 5 ,   1 6 ]   a r p o p u lar   to   s o lv n o n - d eter m i n is t ic   p o l y n o m ial - ti m ( NP )   c o m p lete  p r o b le m s .   T h co n v er g e n ce   p r o ce s s   a n d   s p ee d   o f   m etah e u r is tic  al g o r it h m s   w i th   co m p lete   r an d o m   p o p u latio n   b ec o m w o r s w h en   i n cr ea s i n g   t h n u m b er   o f   j o b s   th at  m ak t h p r o b lem   m o r co m p le x .   Usi n g   an   e f f icie n t   s ch ed u lin g   al g o r ith m   t h at  p r o d u ce s   g o o d   in itial  s o lu tio n   to   th in itial  p o p u latio n   o f   m eta h eu r i s tic  al g o r ith m ak e s   u s o f   t h co m p u tatio n al  p o w er   o f   t h i s   m eta h eu r i s tic   alg o r ith m   a n d   o v er co m e s   t h e ir   d r a w b ac k s   w it h   co m p lica ted   r an d o m   in i tialize d   p r o b lem s   [ 1 7 ,   1 8 ] .   Gen etic  al g o r ith m   ( G A )   as  a n   ev o l u tio n ar y   alg o r it h m   b ec a m v er y   p o p u lar   al g o r ith m   d u to   it s   ac cu r ac y   i n   s o lv i n g   co m p lica t ed   n o n - li n ea r   p r o b lem s .   G A   h as  b ee n   s u cc e s s f u ll y   ap p lied   to   m an y   n o n - li n ea r   an d   n o n - s m o o t h   t y p es  o f   o p t i m izatio n   c h alle n g e s   s u c h   a s   q u er y   o p ti m izatio n   [ 1 9 ] ,   m e d ical  s c i e n c e   [ 2 0 ] ,   a g r i c u l t u r e   [ 2 1 ] ,   m a n a g e m e n t   [ 2 2 ] ,   f e a t u r e   s e l e c t i o n   [ 2 3 ] ,   p o w e r   f l o w   m a n a g e m e n t   [ 2 4 ] ,   a n d   s e n s o r   n e t w o r k s   [ 2 5 ] .   GA   i s   b asicall y   d e s ig n ed   f o r   t h d is cr ete  o p ti m izatio n   p r o b l e m   w h er b its   o f   0 s   a n d   1 s   ar u s ed   to   en co d e   d is cr ete  d esig n   v ar iab les.  Un l ik b io - in s p ir ed   alg o r ith m s   t h at  ar d esig n ed   f o r   co n tin u o u s   p r o b lem s   an d   ca n   ch o o s an y   v al u to   e n co d d esig n   v ar iab les,  w h ich   m ak e s   G A   m o r s u itab le  th a n   o t h e r   alg o r ith m s   i n   t h e   lo ad   b alan cin g   p r o b lem .   C h o o s in g   g o o d   in itial  p o p u latio n   o f   G A   i s   a n   i m p o r tan s tep   to   g en er ate  n e w   b etter   g en er atio n s   w it h   h ig h - q u al it y   s o lu tio n s   w it h i n   les s   ti m [ 2 6 ] .   I n   t h is   p ap er ,   h y b r id   lo ad   b alan ce   b ased   o n   g e n etic  a lg o r ith m   ( H L B G A )   i s   p r o p o s ed   t o   d is tr ib u te   th lo ad s   o v er all  v ir tu a m ac h in es  ( VM s )   i n   an   ef f icie n w a y .   HL B G A   is   i m p le m en ted   i n   t w o   p h ases .   I n   t h f ir s p h ase,   t h e   h eter o g o n o u s   in it ialized   lo ad   b alan ci n g   ( HI L B )   alg o r it h m   is   p r o p o s ed .   I d is tr ib u tes   tas k s   o v er all  VM s   i n   an   e f f icie n wa y   to   av o id   o v er lo ad ed   o r   u n d er   lo ad ed   VM s .   I n   th s ec o n d   p h ase,   G A   is   u s ed   to   en h a n ce   t h o v er all  s y s te m   p er f o r m an ce .   I i s   i n itialize d   w it h   t h o u tp u o f   t h HI L B   alg o r ith m   a s   g o o d   in itial   p o p u latio n   f o r   G A .   T h i s   p h a s u s e s   a   n e w l y   f o r m u lat ed   f it n es s   f u n ct io n   f o r   G t h a h elp s   t h HL B G to   r ea ch   th o p ti m al  lo ad   d ev i atio n .   T h r es o f   th is   p ap er   is   o r g an ized   as:   Sectio n   2   p r esen ts   t h e   r elate d   lo ad   b alan cin g   alg o r ith m s .   I n   Sectio n   3 ,   t h p r o p o s ed   lo ad - b alan cin g   al g o r it h m   is   in tr o d u ce d .   I n   Sectio n   4 ,   t h p er f o r m an ce   e v alu a tio n   o f   th p r o p o s ed   alg o r ith m   is   p r esen ted   an d   co m p ar ed   w it h   t h ex i s tin g   lo ad   b alan cin g   al g o r ith m s .   Sectio n   5   p r ese n ts   t h m a in   co n c lu s io n s   an d   f u tu r w o r k .       2.   RE L AT E WO RK   A   lar g ar ea   o f   r esear ch es  was   in tr o d u ce d   to   s o lv th lo ad   b alan cin g   p r o b le m   to   g et  an   o p ti m a l   ass i g n m e n s o lu tio n .   T h ese   r esear ch es   ca n   b ca te g o r ized   in to   th r ee   m a in   t y p e s   o f   al g o r ith m s tr ad itio n al,   m eta h eu r i s tic,   an d   h y b r id   alg o r ith m s .       2 . 1 .     T ra ditio na l a lg o rit h m s   T r a d itio n al  al g o r ith m s   ar wo r k ed   b ased   o n   k n o w in g   in f o r m at io n   ab o u r eso u r ce s   a n d   task s   to   ca lcu late   th eir   ev al u atio n   p ar a m eter s .   Mo s o f   t h e m   r el y   o n   ex ec u tio n   ti m to   ass ig n   ta s k s   to   r eso u r ce s   i n   a   w a y   th at  m i n i m izes  m ak e s p an ,   lo ad   d ev iatio n ,   o r   b o th .   Min - Min   alg o r it h m   i s   w el l - k n o w n   alg o r it h m   i n   th i s   ca teg o r y .   Mi n - Min   alg o r it h m   is   t h b ase  o f   m a n y   s c h ed u l in g   al g o r ith m s   [ 8 ] .   I n   t h i s   al g o r ith m ,   th e   co m p letio n   ti m o f   a ll  s u b m i tted   tas k s   a m o n g   all  VM s   is   ca lc u lated .   T h task   w i th   m i n i m u m   co m p leti o n   ti m i s   as s i g n ed   to   th co r r esp o n d in g   VM .   T h en   t h co m p letio n   ti m o f   all  o th er   tas k s   o n   t h at   m ac h i n i s   u p d ated   b y   ad d in g   th co m p let io n   ti m o f   t h a s s i g n ed   ta s k   to   th e ir   co m p let io n   ti m es.  T h is   tas k   i s   r e m o v ed   f r o m   li s o f   u n a s s i g n ed   task s ,   an d   t h en   t h i s   p r o ce d u r is   r ep ea ted   u n til al l ta s k s   ar ass i g n ed .   L o ad   b a l a n c e   i m p r o v e d   M i n - M i n   ( L B I M M )   a l g o r i t h m   i m p r o v e s   t h e   s t a n d a r d   M i n - M i n   a lg o r it h m   [ 9 ] .   I n   th f ir s s tep ,   th Min - Mi n   alg o r ith m   is   e x ec u ted   to   g iv t h e   in itial  s o lu tio n   to   s tar th n e x s tep .   I n   th n e x t   s tep ,   th co m p letio n   ti m o f   t h s m al lest   s ize  ta s k   f r o m   t h h ea v ie s lo ad ed   r eso u r ce   is   ca l cu lated   o n   all  o t h er   VM s .   Ma k esp an   is   ca lc u lated   in   ca s t h at   tas k   i s   r e m o v ed   t o   th VM   w it h   th e   m in i m u m   co m p let io n   t i m e   o f   th at  tas k   a n d   co m p ar ed   w i th   t h m a k esp an   p r o d u ce d   b y   Mi n - Min .   I f   it  is   less   t h an   t h ta s k ,   it   is   r ea s s ig n ed   to   th e   r eso u r ce   t h at  p r o d u ce s   i t,  an d   th r ea d y   ti m o f   b o th   r e s o u r ce s   i s   u p d ated .   T h p r o ce s s   r ep ea ts   u n til  n o   o th er   r ea s s ig n m e n ts   ca n   p r o d u ce   less   m a k esp a n .   T h u s   th h e av y   lo ad   r eso u r ce s   ar f r ee d   an d   th li g h lo ad   o r   id le  r eso u r ce s   ar m o r u tili ze d .   A lth o u g h   th tr ad itio n al   alg o r ith m s   ar s i m p le  to   im p le m e n an d   ca n   i m p r o v m a k esp a n ,   s o m o f   t h e m   d o n ta k th lo ad   d ev ia tio n   in   it s   co n s id er atio n   esp ec iall y   i n   ca s o f   b i g   d if f er e n ce   i n   r eso u r ce   s p ee d .   A l s o ,   th e y   ca n ' f i n d   th o p ti m al  s o lu t io n   esp ec ial l y   w h e n   t h p r o b lem   b ec o m e s   co m p le x   o r   to o   lar g [ 2 5 ] .     2 . 2 .     M et a heuris t ic  a lg o rit h m s   Me tah e u r is tic  al g o r ith m s   ar th m o s p o w er f u tech n iq u e s   f o r   th o p ti m izat io n   o f   co m p lex   n o n - lin ea r   p r o b le m s   w h ic h   is   th e   ca s o f   m o s ta s k   s c h ed u li n g   an d   lo ad   b alan ci n g   is s u e s   [ 2 6 ] .   Me tah eu r is tic   alg o r ith m s   ca n   b class if ied   in to   s w ar m   i n telli g e n ce   b ased   alg o r ith m s   an d   ev o l u tio n ar y   alg o r ith m s .   S w ar m   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2 0 8 8 - 8708       H yb r id   lo a d   b a la n ce   b a s ed   o n   g en etic  a lg o r ith in   clo u d   e n viro n men t ( W a la a   S a b er)   2479   in telli g e n ce   b ased   alg o r ith m s   s u ch   as  P SO,  AC O,   an d   A B C   o p ti m ize  ce r tain   p r o b lem   b y   s i m u lati n g   t h co llectiv b e h av io r   o f   n a tu r al   s w ar m s .   E v o lu tio n ar y   a lg o r it h m s   s u c h   a s   G ar b ased   o n   t h e v o lu t io n ar y   b eh av io r   o f   n at u r al  s y s te m s .       P SO  alg o r ith m   is   o n o f   t h s ta n d ar d   alg o r it h m s   u s ed   in   lo ad   b alan c in g   a n d   als o   in   o th er   ap p licatio n s   [ 2 7 ,   2 8 ] .   I is   s w ar m   in te lli g en t   alg o r it h m ,   in s p ir ed   b y   n at u r f o r   s o lv i n g   n o n li n ea r   o p tim izatio n   p r o b le m s   [ 1 0 ] .   P SO  is   s i m u latio n   o f   t h ad v an ta g es  o f   b ir d   f lo ck s .   I s tar ts   w ith   i n itia l   in d iv id u als   ca lled   p ar ticles r ep r esen ti n g   i n itial  s o lu t io n s   f o r   t h p r o b le m .   Du r i n g   t h s ea r c h   p r o ce s s ,   k illi n g   o f   an y   i n d iv id u al  i s   n o p er m itt ed .   I n   P SO,  all  in d iv id u al s   r em ai n   aliv a n d   tr y   to   m a k t h e m s el v es  s tr o n g e r   th r o u g h o u t h s ea r ch   p r o ce s s .   I n   e v er y   g e n er atio n /iter atio n ,   in d iv id u als   m a k th e m s e lv e s   b etter .   T h id en tit y   o f   th i n d iv id u al  d o es n o t c h a n g e   o v er   th iter atio n s .   GA   i s   an   ev o l u tio n ar y   o p ti m izatio n   alg o r ith m   b ased   o n   th b io lo g ical  co n ce p o f   p o p u latio n   g en er atio n   [ 1 3 ] .   A   n e w   p o p u l atio n   is   ev o l v ed   in   ev er y   g en er atio n   b ased   o n   p r ed ef i n ed   f i tn es s   f u n ctio n .   G w o r k s   b etter   f o r   v ast  a n d   co m p lex   s ea r ch   s p ac p r o b lem s .   I w o r k s   b ased   o n   th r ee   m ai n   o p er atio n s   w h ic h   ar e   s elec tio n ,   cr o s s o v er ,   an d   m u t atio n .   T h s tr en g th   o f   G A   is   in   t h p ar allel  n at u r o f   its   s ea r ch .   T h g en etic   o p er ato r s   u s ed   ar e   th m ain   p o w er f u r ea s o n   f o r   th s u cc ess   o f   th s ea r c h .   C r o s s o v er   is   th m a in   g e n etic   o p er ato r ,   w h er ea s   m u tatio n   i s   u s ed   less   f r eq u e n tl y .   C r o s s o v er   atte m p t s   to   b en ef it  o f f s p r in g   s o lu tio n s   a n d   to   eli m i n ate  u n d esira b le  co m p o n en t s .   B y   r estricti n g   t h r ep r o d u ctio n   o f   w ea k   o f f s p r i n g s ,   GAs  eli m i n ate s   n o o n l y   t h at  s o l u t io n   b u al s o   all  o f   its   d escen d an ts .   T h is   m a k es  th al g o r ith m   co n v er g to w ar d s   h ig h - q u alit y   s o lu tio n s   w i th i n   f e w   g e n er a tio n s .   I n   o r d er   to   r ea lize  p o w er f u cr o s s o v er   a n d   m u tatio n   o p er ato r s ,   w m u s t   ch o o s g o o d   in itial p o p u latio n   f o r   GA   [ 1 4 ] .   Ho w e v er   m etah e u r is tic  al g o r ith m s   ar p o w er f u l   tech n iq u es   f o r   o p ti m iza tio n ,   t h e y   ar i n e f f icien to   h an d le  th e   lo ad   in   c lo u d   co m p u ti n g   in   ca s o f   r an d o m   i n itial   p o p u latio n .   A l s o ,   th e y   s u f f er   f r o m   i n cr ea s i n g   t h e   co m p u tatio n al  co s t   i n   t h lar g s ca le  p r o b le m s   [ 2 9 ] .   T h e r e f o r e ,   h y b r i d   a l g o r i t h m s   a r e   i n t r o d u c e d   t o   e n h a n c e   t h e   p e r f o r m a n c e   o f   b o t h   t h e   t r a d i t i o n a l   a n d   m e t a h e u r i s t i c   a l g o r i t h m s   i n   o r d e r   t o   h a n d l e   t h e i r   p r o b le m s .     2 . 3 .     H y brid  a lg o rit h m s   H y b r id   tas k   s ch ed u li n g   al g o r ith m s   ar b ased   o n   co m b i n in g   t w o   s c h ed u l in g   a lg o r i t h m s   to   m a k u s e   o f   th ad v an tag o f   b o th   t h ese  t w o   alg o r it h m s .   T h is   p a p er   p r esen ts   s o m o f   th m o s p o p u lar   h y b r id   alg o r ith m s   to   s tate  t h r ea s o n   f o r   th e   p r o p o s ed   alg o r ith m .   H GA - AC a lg o r it h m   [ 3 0 ]   co m b in es  G A   a n d   AC O   alg o r ith m s   to g e th er .   R a n d o m l y   i n itia li ze d   G is   u s ed   to   p r o d u ce   t h i n itia p h er o m o n f o r   A C O.   AC s tar ts   to   iter ate  i n   o r d er   to   g i v e   th b est  s o lu tio n .   T h b est   t wo   s o lu tio n s   f r o m   G an d   A C ar m er g ed   b y   cr o s s o v er   to   g i v t h g lo b al  b est  s o lu tio n .   Ho w e v er ,   t h al g o r ith m   f o c u s e s   o n   r esp o n s t i m e,   e x ec u tio n   ti m e   an d   th r o u g h p u t,  it  d o es n s u b j ec to   th lo ad   b alan cin g   p r o b le m .   G A   is   n o an   e f f ec ti v a lg o r ith m   to   g iv a n   in itial  s o lu t io n   w h en   it i s   r an d o m l y   i n itia lized .   Os m o tic  h y b r id   ar ti f icial  b ee   a n d   an t c o lo n y   ( OH_ B AC )   alg o r ith m   i s   p r esen ted   i n   [ 31 ] .   I ap p lies   th e   o s m o s i s   tech n iq u f o r   p r o v id in g   en er g y   e f f icien clo u d   en v ir o n m e n t.  I n   th is   alg o r it h m ,   A B C   an d   AC O   co o p er ate  to   s elec t h ap p r o p r iate  VM   to   b m ig r ated   to   th m o s s u itab le   p h y s ical   m ac h in e.   I n   ad d itio n ,   i t   m ak e s   ac ti v atio n   f o r   th m o s t   s u itab le  o s m o tic  h o s a m o n g   all  p h y s ical  m ac h i n es  i n   th s y s te m   to   d ec r ea s e   p o w er   co n s u m p tio n .   Mo r eo v er ,   in teg r atin g   m ac h i n lear n in g   tech n iq u es   w it h   lo ad   b alan cin g   a l g o r i t h m s   r e i n f o r c e m e n t   t h e   l e a r n i n g   p r o c e s s   a n d   h e l p   t o   i m p r o v e   t h e   p e r f o r m a n c e   a n d   t h e   c o n v e r g e n c e   r a t e   o f   t h e   l o a d   b a l a n c i n g   p r o c e s s   [ 3 2 ] .   Ho w e v er ,   th g o al  o f   m o s o f   th ese  al g o r ith m s   i s   to   m i n i m ize  th o v er all  co m p letio n   ti m w it h o u lo o k i n g   in to   th m i n i m izatio n   o f   t h o v er all  lo ad   d ev iatio n .   Mo s o f   p r ev io u s   al g o r ith m s   ch o o s m i n i m izi n g   m ak e s p an   as   th e   m ain   g o al  i n   s ch ed u li n g ;   h o w e v er   t h i s   ta r g et  al w a y s   c h o o s es  f as ter   V Ms  to   p er f o r m   t h e   ass i g n ed   tas k s .   T h i s   r es u lt s   i n   o v er lo ad ed   VM s   w it h   h i g h   p r o ce s s in g   s p ee d   th at   y ield s   to   s tar v atio n   p r o b le m   o f   o th er   VM s   w i th   lo w er   p r o ce s s i n g   t i m e.   I n   ad d itio n ,   th e x p er i m e n ts   o f   m o s o f   r elate d   w o r k   ar li m ited   as   th e y   test ed   t h eir   al g o r ith m s   o n   s m all   s ca le  p r o b le m s   [ 3 3 ] .   I n   th is   p ap er ,   n e w   h y b r id   HL B G A   b ala n cin g   alg o r ith m   is   p r o p o s ed   w h ic h   co m b i n es  G A   a n d   n e w   p r o p o s ed   HI L B   s ch ed u lin g   al g o r i th m   w h ic h   h elp s   g en et ics to   co n v er g m o r q u i ck l y   to   b etter   s o lu tio n   b y   f ee d i n g   it  w ith   g o o d   in itial p o p u lati o n .       3.   T H E   P RO P O SE H L B G A   3 . 1 .     Arc hite ct ure  o v er v ie w   In   t h is   s ec t io n ,   t h p r o p o s ed   H L B G A   is   p r ese n ted .   T h m ai n   p u r p o s o f   t h p r o p o s ed   alg o r ith m   i s   to   i m p r o v th a s s i g n m en p er f o r m an ce   f o r   all  th s u b m itted   t ask s   o n   all  VM s .   I tr ies  to   as s ig n   tas k s   to   ea ch   VM   b ased   o n   its   co m p u ti n g   ca p ab ilit ies  to   m a k u s o f   all  o f   th e m   w h ic h   lead s   at  th en d   to   b alan ce   th lo ad   a m o n g   all  VM s .   L o ad   b alan ce   is   an   o p ti m izatio n   p r o b le m   in   w h ich   lo ad   d ev iatio n   is   t h e   o b j ec tiv f u n ctio n   n ee d ed   to   b m in i m ized .   G A   is   o n o f   th p o p u lar   alg o r it h m s   t h at  ar u s ed   t o   s o lv o p tim izatio n   p r o b lem s .   T h p r o p o s ed   alg o r ith m   u s es  GA   w i th   g o o d   in itial p o p u lat io n   to   g et  th o p ti m a l so l u tio n   w it h   le s s   ti m e.     Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I n t J   E lec  &   C o m p   E n g ,   Vo l.  11 ,   No .   3 J u n 2 0 2 1   :   2 4 7 7   -   2489   2480   T h e   p r o p o s ed   HL B G A   i s   b ase d   o n   t w o   m ai n   p h a s es.   T h f ir s p h a s i s   ap p l y i n g   t h p r o p o s ed   HI L B   alg o r ith m   th at   d is tr ib u tes   tas k s   o v er all   VM s   b ased   o n   ea ch   r eso u r ce   co m p u tin g   ca p ab ilit i es  to   e n s u r t h at  n o   s in g le  V is   e ith er   o v er lo ad ed   o r   u n d er u tili ze d   e s p ec iall y   in   ca s o f   m aj o r   d if f er e n ce s   b et w ee n   r eso u r ce s   co m p u ti n g   ca p a b ilit ie s .   T h s ec o n d   p h ase  u s e s   th o u tp u o f   th HI L B   alg o r ith m   as  an   i n itial  p o p u latio n   f o r   th G A   w h ic h   o p ti m izes lo ad   d ev iatio n   o b j ec tiv f u n ct io n   to   ac h iev o p ti m u m   lo ad   d is tr ib u tio n .   T h e   p r o p o s ed   HL B GA  alg o r it h m   in tr o d u ce s   n e w   o b j ec tiv f u n ct io n   to   i m p r o v t h p er f o r m an ce   o f   th a s s i g n m e n t   p r o b lem   ev e n   w h e n   t h p r o b le m   b ec o m e s   c o m p le x   o r   to o   lar g e.   I i m p le m en ted   in   d if f er e n t   en v ir o n m e n t s ,   h o m o g en eo u s ,   h eter o g en eo u s - lo w   a n d   h et er o g o n o u s - h ig h   en v ir o n m e n ts .   HL B G A   also   is   i m p le m en ted   o n   d if f er e n n u m b er   o f   tas k s .   I i m p r o v es  r eso u r ce   u tili za t io n   an d   it  also   d ec r ea s es  b o th   th e   lo ad   d ev iatio n   an d   th m a k esp an .     3 . 2 .     L o a ba la ncing   pro ble m   a n a ly s is   A lt h o u g h   clo u d   co m p u ti n g   is   d y n a m ic,   at   an y   p ar tic u lar   i n s t an ce   t h lo ad   b ala n ci n g   p r o b le m   ca n   b f o r m u lated   as  ass i g n in g   s et  o f   n   task s   o n   s et  o f   VM s .   Ass u m e   t h a t   t h e   c l o u d   t a s k   s c h e d u l e r   r e c e i v e s   n   in d ep en d en t   t a s k s   1   2   3   .   wi t h   d i f f e r e n t   l e n g t h s ,   wh i c h   a r e   e x p r e s s e d   i n   m i l l i o n   i n s t r u c t i o n s   ( M I )   a s   ( 1 ) :       =   [ 1 2 3   . ]   w h er e     is   th len g t h   o f   tas k   i   a n d     = { 1 . 2 . . }   ( 1 )     A l s o ,   a s s u m e   t h a t   t h e   c l o u d   t a s k   s c h e d u l e r   c o n t a i n s   i n f o r m a t i o n   a b o u t   t h e   m   V M s ;   1   2   3 .    wi t h   d i f f e r e n t   p r o c e s s i n g   s p e e d s ,   wh i c h   a r e   e x p r e s s e d   i n   m illi o n   in s tr u c tio n s   p er   s ec o n d   ( M I P S (   a s :     = [ 1 2 3 . ] T       ( 2 )     whe r e     is   the   pr oc e s s or   s pe e d   of   VM     a n d   = { 1 . 2 . . }   T h ass ig n m en m atr i x     o f   task s   o v er   VM s   ca n   b r ep r esen t ed   as:       = [         11 1 1 1   1   ]             ( 3 )     whe r e      = 1   if   ta s k     is   a s s ign e d   to   VM     , othe r wi s e      = 0   Ass u m e   a l s o   t h a t   a t   a n y   t i m e   t h e r e   wi l l   b e   l o a d   m a t r i x   X   c o n t a i n s   i n f o r m a t i o n   a b o u t   t h e   c u r r e n t   l o a d   o f   t h e   m   V M s   1   2   3 . .   T h e   V M s   l o a d s   a r e   d e f i n e d   i n   t h e   l o a d   m a t r i x   a s :     = [ 1 2 3 . ]   ( 4 )     =  = 1             whe r e     is   the   c urr e n t   l oa d   of   VM   a n d   = { 1 . 2 . . }   ( 5 )     T h e   p er f o r m a n ce   o f   t h as s ig n m e n s o lu tio n   ca n   b m ea s u r ed   u s in g   m ak e s p an ,   lo ad   d ev iatio n   ( ) an d   r eso u r ce   u til izatio n   ( U ) .   T h e y   ca n   b ca lcu lated   as [ 2 3 ] :        = ma x ( )         w h er e     is   th co m p letio n   ti m o f   VM j .   ( 6 )     = ( ) 2 = 1     w h e r e   = = 1   ( 7 )     =            × 100       ( 8 )     3 . 3 .     T he  pro ble m   f o r m u la t io n o f   H L B G A   T h e   g o al   o f   t h e   p r o p o s e d   H L B GA   alg o r it h m   i s   t o   o p t i m a l l y   a s s i g n   a   s e t   o f   t a s k s   o n   a   s e t   o f   V M s   i n   a   wa y   t h a t   m i n i m i z e   t h e   l o a d   d e v i a t i o n   o f   a l l   V M s .   M i n i m i z i n g   l o a d   d e v i a t i o n   y i e l d s   t o   m i n i m i z e   m a k e s p a n   a n d   m a x i m i z e   r e s o u r c e   u t i l i z a t i o n   s i n c e   i t   a s s i g n s   t h e   t a s k s   t o   a l l   V M s   wi t h   d i f f e r e n t   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2 0 8 8 - 8708       H yb r id   lo a d   b a la n ce   b a s ed   o n   g en etic  a lg o r ith in   clo u d   e n viro n men t ( W a la a   S a b er)   2481   c o m p u t i n g   c a p a b i l i t i e s .   I t   e n s u r e s   t h a t   a l l   V M s   a r e   n o t   o v e r l o a d e d   o r   u n d e r   l o a d e d .   T h e n   i t   p r e v e n t s   s t a r v a t i o n   p r o b l e m   o f   V M s   wi t h   l o p r o c e s s i n g   s p e e d .   T a b l e   1   s h o ws   t h e   p a r a m e t e r s n o t a t i o n s   t h a t   a r e   u s e d   i n   t h e   p r o p o s e d   m o d e l .       T ab le  1 .   P ar am eter s '   n o tatio n s   u s ed   in   t h p r o p o s ed   m o d el   P a r a me t e r   M e a n i n g   n   T h e   n u m b e r   o f   t a s k s   m   T h e   n u m b e r   o f   V M s   T n x 1   T h e   t a sk   l e n g t h   m a t r i x   w h e r e   t i     i t h e   l e n g t h   o f     i th   t a s k     i n   M I   V m x 1   T h e   p r o c e sso r   sp e e d   mat r i x   w h e r e   v j   i s p r o c e sso r   sp e e d   o f     j th   V M   i n   M I P S   X m x 1   Th e   l o a d   M a t r i x   f o r   a l l   V M   w h e r e   x j   i s   l o a d   o f   j th   VM   σ 2   Lo a d   v a r i a n c e   σ   Lo a d   d e v i a t i o n   μ   Lo a d   M e a n   ×   A s s i g n m e n t   m a t r i x   w h e r e   θ ij   i s   a   b i n a r y   b i t   e q u a l s   t o   1   o r   0 ,   w h i c h   r e p r e s e n t s   a s s i g n m e n t   s t a t e   o f   t a s k   i   o n   V M   j       T h e   p r o p o s ed   m o d el  f o r m u lat es  th o b j ec tiv in   ter m s   o f   t h ass i g n m e n m atr ix .   I tr ies   to   g et  th ass i g n m e n m atr i x   t h at  p r o v i d es  th s o lu t io n   w i th   m i n i m u m   lo ad   d ev iatio n .   T h lo ad   v ar ian ce   ca n   b e   o b tain ed   as:     2 = ( ) 2 = 1     ( 9 )     a s s u m e       ̇ = [ 1 2 . . ]   [ 1 1 . . 1 ] = 1     ( 1 0 )     t h en     ( ) 2 = 1 ̇ ̇   ( 1 1 )     b ec au s e     = 1 = 1     ( 1 2 )     th en     = 1   ( 1 3 )     Su b s ti tu te   ( 1 3 )   in   ( 1 0 )       ̇   =   (     1   1   )     ( 1 4 )     w h er e   I   is   an   id en tit y   m atr i x ,     let = (     1   1   )   th e n   ̇ =    ( 1 5 )     A ll   th d ia g o n al  e le m e n t s   o f   t h Q   m atr i x   ar   1   an d   it s   o f f - d iag o n al  e le m e n t s   ar 1 ,   s o   Q   is   a n   id e m p o ten m atr ix   [ 3 4 ] .   T h m atr i x   Q   is   u s e f u l i n   co m p u ti n g   s u m s   o f   s q u ar ed   d ev iatio n s .     = 1   [ 1 1 1 1 1 1 1 1 1 1 1 ]   ( 1 6 )     B y   s u b s t itu tin g   ( 1 1 )   in   ( 9 )   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I n t J   E lec  &   C o m p   E n g ,   Vo l.  11 ,   No .   3 J u n 2 0 2 1   :   2 4 7 7   -   2489   2482   2 = ̇ ̇ =                w h er = ,   th en   ( 1 7 )     2 =         ( 1 8 )           =     2    = 1 +  = 1 = 1   ( 1 9 )     w h er e       = 1   , = 1 , 2 , . ,     an d    = 1       , , = 1 , 2 , . ,       2 = 1 2 [ ( 1 ) 2 = 1 = 1 = 1 ]   ( 2 0 )     w h er e     =  = 1   ( 2 1 )     =  = 1   an d   ( 2 2 )     2 =       2 = 1   = 1   ( 2 3 )     T h e   o b j ec tiv f u n ctio n   i s   co n clu d ed   b y   s u b s ti tu ti n g   ( 2 1 ) ,   ( 2 2 ) ,   an d   ( 2 3 )   in   ( 2 0 )   th at  y iel d s   ( 2 4 ) .   As   s h o w n   i n   ( 2 5 )   is   th n o n li n e ar   o b j ec tiv f u n c tio n   o f   H L B GA   w h er t ,   v,   m,   an d   n   a r e   co n s tan t s   f o r   ea ch   p r o b lem   w h ic h   r ep r esen t ta s k s   len g th ,   VM s   p r o ce s s o r   s p ee d ,   n u m b er   o f   VM s ,   a n d   n u m b er   o f   tas k s   n ee d   to   b e   ass i g n ed ,   r esp ec tiv e l y .   W h i le  θ   co n tain s   th as s i g n m e n t v ar i ab les n ee d   to   b s o lv ed   f o r   th e   o p t i m u m   s o l u t i o n .     T h i s   o b j e c t i v e   f u n c t i o n   i s   s u b j e c t   t o   t h r e e   c o n s t r a i n s   w h i c h   a r e   f o r m u l a t e d   i n   ( 2 6 - 2 8 ) .   A s   s h o w n   i n   ( 2 6 )   m ea n s   t h at  ea ch   ta s k   s h o u ld   b ass ig n ed   to   o n l y   o n VM .   θ   in   ( 2 7 )   is   b in ar y   v ar iab le  w h ich   ca n   b 1   o r   0 ,   i . e. ,   ass i g n ed   o r   n o t   ass ig n ed .   A s   s h o w n   i n   ( 2 8 )   s tate s   t h at ,   th e   co m p letio n   ti m e   f o r   a n y   VM   f o r   o p ti m u m   s o lu tio n   s h o u ld   b less   t h an   o r   eq u al  to   th m a k esp a n   o f   t h i n itial a s s i g n m e n m atr ix   ( Ma k esp an initial ).     2 =   1 2 [   ( 1 )     2 = 1 = 1 = 1                   = 1 = 1 = 1 = 1               ]   ( 2 4 )     = 1 2 [   ( 1 )     2 = 1 = 1 = 1                         = 1 = 1 = 1 = 1               ]   ( 2 5 )     s u b j ec t   t o :      = 1 = 1       ( 2 6 )        { 0 , 1 }     ,         = 1 , 2 , . .       = 1 , 2 , .   ( 2 7 )      = 1              = 1 , 2 , . ,       ( 2 8 )     3 . 4 .   T he  H L B G ph a s e s   T h e   p r o p o s ed   HL B G A   a lg o r ith m   h as   t w o   p h ases .   Firs t,  HI L B   al g o r ith m   i s   p r o p o s ed   as  a   n e w   tr ad itio n al  alg o r it h m   i n   o r d er   to   d is tr ib u te  task s   o v er all  VM s   in   an   e f f icien w a y   to   av o id   o v er lo ad ed   o r   u n d er   lo ad ed   VM s .   T h s ec o n d   p h as u s e s   t h o u tp u t a s   an   i n itial  p o p u latio n   f o r   G A .   Fi g u r 1   s h o w s   t h m ai n   s tep s   o f   th t w o   p h a s es o f   t h p r o p o s ed   alg o r ith m .   T h ese  t w o   p h a s es a r i m p le m e n ted   as:     3 . 4 . 1 .   P h a s e   I :   I ni t i a l   p o p ul a t i o n   ph a s e   In   th is   p h a s e,   t h HI L B   alg o r i th m   is   p r o p o s ed   in   o r d er   to   b alan ce   t h lo ad   an d   m in i m ize  m ak e s p an .   A l g o r ith m   s tr ateg y   is   b ased   o n   m o v i n g   ta s k s   f r o m   h ea v y   lo ad ed   m ac h in e s   to   least lo ad ed   o n es a s :     Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2 0 8 8 - 8708       H yb r id   lo a d   b a la n ce   b a s ed   o n   g en etic  a lg o r ith in   clo u d   e n viro n men t ( W a la a   S a b er)   2483       Fig u r 1 Flo w   s tr u ct u r o f   th e   HL B G A   al g o r ith m       a.   HI L B   g ets   an   i n itial  as s i g n m en s o lu t io n   f o r   all  th s u b m i tted   task s   o v er   all  th av ailab le  r eso u r ce s   b y   ass i g n in g   t h ta s k   w it h   m in .   c o m p let io n   ti m to   th co r r esp o n d in g   m ac h i n e.   T h en ,   i ca lc u lates   m a k esp a n   an d   lo ad   d ev iatio n   f o r   th i s   i n it ial  s o lu tio n   as t h cu r r en m a k esp an ,   an d   lo ad   d ev iatio n ,   r es p ec tiv el y .   b.   HI L B   ca lc u lates   t h co m p leti o n   ti m o f   all   th e   av a ilab le  VM s .   I tr ie s   to   m o v e   t h s h o r test   tas k   i n   t h e   h ea v ie s lo ad ed   r eso u r ce   to   th least  lo ad ed   r eso u r ce .   HI L B   co n s id er s   t w o   co n d itio n s   f o r   ac ce p tin g   an y   n e w   ta s k   m o v e m e n f r o m   o n VM   to   a n o t h er .   I g u ar a n te es  t h at  ea c h   n e w   tas k   m o v e m en i s   a   f o r w ar d   s tep   in   en h a n cin g   m ak e s p an   a n d   lo ad   d ev iatio n .   T h t w o   co n d itio n s   ar e :   ( 1 )   New   Ma k es p an   <=   C u r r en t   Ma k esp a n ,   an d   ( 2 )   Ne w   lo ad   d ev iatio n   <=   C u r r en lo ad   d ev iatio n.   HI L B   m a k es  a ll  t h av a ilab le  task   m o v e m e n t s   f o r   t h cu r r e n h ea v ie s lo ad ed   VM   to   an y   o n o f   t h r e m ain in g   VM s .   HI L B   r ep ea ts   th ese  p r ev io u s   o p er atio n s   o n   all  th av ailab le  r eso u r ce s .   I b alan ce s   th lo ad   o v er all  r eso u r ce s   ev e n   v er y   s l o w   o n e s   i n   w a y   th at   ac h iev es  h i g h   lo ad   b alan ci n g   a n d   o p ti m u m   co m p letio n   ti m e.   T h is   al g o r ith m   av o id s   s t ar v atio n   p r o b le m   b et w ee n   V Ms.      3 . 4 . 2 .   P h a s e   I I :   G A   p h a s e   HL B G A   al g o r ith m   r elie s   o n   GA   as  p o w er f u s o lu t io n   f o r   n o n lin ea r   p r o g r a m m in g   o p ti m izat io n   NP - co m p lete  p r o b le m s .   Gen e tics   i n   t h i s   al g o r ith m   r elie s   o n   th r ee   m a in   o p er atio n s eli te,   cr o s s o v er ,   an d   m u tatio n .   I n   E lite  o p er atio n ,   th alg o r ith m   c h o o s es  th ass i g n m e n t   m a tr ices  th a g i v th b est  f it n es s   f u n ctio n s   to   p ass   to   th n ex g en er atio n .   I n   cr o s s o v er   a n d   m u tatio n   o p er atio n s ,   t h al g o r ith m   r ea s s ig n s   ta s k s   to   d if f er en VM s   to   f o r m   n e w   s o l u tio n s   i n   d if f er en w a y s .   C r o s s o v er   r ec o m b i n es  ea c h   t w o   ass i g n m en t   m atr ices   t o   f o r m   t w o   n e w   o n e s   w h ic h   p r ac ticall y   m ea n   r ea s s ig n m en o f   ta s k s   to   f o r m   t w o   n e w   s o l u tio n s .   T h e   r ec o m b i n atio n   m u s b d o n o n   co m p lete  r o w   b a s is   i.e . ,   co m p lete  r o w s   ar s w ap p ed   b et w ee n   m atr ices.   W h ile  in   m u tatio n ,   r an d o m   ch an g es  d o n to   s i n g le  a s s ig n m e n m atr i x .   A lg o r it h m   1   s h o w s   th m ai n   p r o ce s s es o f   th p r o p o s ed   HL B GA .     Alg o rit h m   1 :   T he  pro po s ed  H L B G A   Begin   //  start Phase I: HILB Algorithm     1.   Fo   an su bm it te d   ta sk   Ti   calculate  co mpletion  time  Ctij   fo r   Re so ur ce Rj   Ctij=Etij+rtj;     2. while the non - submitted task list is not empty   3.    Find task I with minimum completion time and assign to corresponding Resource   4.    Remove the task from non - submitted task list  and update resource ready time rtj     5. End    6. Calculate current Makespan Mc and load deviation Lc    7. Add all VMs to Resources list   R   8. while list R not empty   9.   Find Heaviest loaded VM RH in Resource List   10.   Add other Resources to load list L and find least load Resource RL   11.   move the  shortest task in the heaviest loaded resource to  RL   12.   a. IF New Makespan Mn  <= Mc  And New  Load Deviation Ln<= Lc            b.   Then Mc= Mn and Lc=Ln  And Goto step  9          c.   Else if L is not empty           d.   Then undo step 11  And remove RL from List   L  And go to step 11           e.   Else remove RH  from list R   And go to step 8   13. End   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I n t J   E lec  &   C o m p   E n g ,   Vo l.  11 ,   No .   3 J u n 2 0 2 1   :   2 4 7 7   -   2489   2484   // start  Phase II: Applying GA    14. Initialize population by adding the result of phase 1 to random initial population   15. Set initial parameters           El it co un fr action,  populati on   s iz e,   Cr os so ve fr ac t io n   nu mb er   of   generations   16. Calculate number of variables V= n×m   17. Set mutation fraction U= 1 -   ( E + C )   18. while termination condition not satisfied   19.    Evaluate  each chromosome using fitness function   20       Ch oo se   (E   ×  P)   c hr om os om es   wi th   th be st   fi tn es fu nc ti on   as   el i te   fo th ne xt      generation   21.    Select (C × P) chromosomes for  crossover operation   22.    For k=1 to ( C × P)   23.        Select two random chromosomes as input for crossover  operation   24.        Perform crossover operation on selected chromosomes   25.        Select  the two output chromosomes to the next generation   26.   End For   27.    Select ( U × P )  chromosomes for  mutation operation   28.      For k=1 to ( U × P)   29.      Select one random chromosome as input for mutation operation   30.       Perform Mutation process on  the selected chromosome   31.      Select  the  output chromosome  to the next generation    32.   End For   33.    Replace the current population by new generati on   34. End     3 . 5 .     Co m plex it y   o f   H L B G A   T h HL B GA   is   b ased   o n   t w o   m ai n   p h ases .   I n   t h f ir s p h a s e ,   it  r u n s   th HI L B .   T h tim co m p le x it y   o f   t h is   p h a s i s   b ased   o n   t h e   n u m b er   o f   t h m o v e m e n t s   t h a p er f o r m ed   to   r ea ch   th e   i n itia p o p u latio n .   I t   ca n   b co m p u ted   as:  O( n 1 ) .   I n   th e   s ec o n d   p h ase,   th H L B G A   r u n s   th G A .     T h co m p le x it y   in   th is   p h ase  ca n   b co m p u ted   as  O( N)   [ 3 5 ] .   C o m p ar in g   t h ti m co m p lex it y   o f   t h f ir s p h a s to   th s ec o n d   p h ase,   it  w a s   f o u n d   th at  n 1 <<   N,   s o   it   c an   b n e g lecte d .   T h er ef o r e,   t h to tal   co m p le x it y   o f   t h H L B G A   a lg o r it h m   is O( N) .   T h in itial  p o p u lati o n   th at  i s   u s ed   in   t h p r o p o s ed   alg o r ith m   h elp s   t h g en e ti cs  to   r ea ch   b etter   s o lu tio n   w it h   less   p o p u latio n   s ize  a n d   n u m b er   o f   g e n e r atio n s   w h ic h   d ec r ea s es   t h e   co m p lex i t y   o f   th alg o r ith m .   T ab le  2   s h o w s   t h t i m co m p le x it y   o f   t h H L B GA   a n d   d escr ip tio n   o f   th co m p lex i t y   p ar a m eter s .       T ab le  2.   T im co m p le x it y   o f   t h H L B G A   A l g o r i t h m   T i m e   c o m p l e x i t y   D e s c r i p t i o n   P h a s e   I :   H I L B   O(n 1 )   n 1 :   N u m b e r   o f   mo v e s   t o   r e a c h   t h e   i n i t i a l   p o p u l a t i o n   P h a s e   I I :   G A     O ( G × N)   G:   N u m b e r   o f   g e n e r a t i o n s   N:   n × m × P     ( t i m e   o v e r h e a d   o f   a l l   c h r o m o so m e s )   w h e r e   n × m :   N u m b e r   o f   v a r i a b l e s   t h a t   r e p r e se n t   t h e   n u m b e r   o f   g e n e s   i n   e a c h   c h r o m o s o me   ( t i m e   o v e r h e a d   o f   o n e   c h r o mo s o me )   P:   P o p u l a t i o n   s i z e     ( n u m b e r   o f   c h r o m o s o m e s   i n   e a c h   g e n e r a t i o n )   H L B G A   O ( G × N)         4.   P E RF O RM ANCE E VA L U AT I O N S   In   t h is   s ec tio n ,   t h p er f o r m an ce   o f   t h p r o p o s ed   HL B GA  al g o r ith m   i s   e v al u ated   i n   d i f f er e n t   en v ir o n m e n t s   a n d   co n d itio n s .   T h p r o p o s ed   alg o r ith m   i s   c o m p ar ed   ag a in s v ar ian t   tec h n iq u es;  M in - Mi n   [ 8 ]   an d   L B I MM   [ 9 ]   as  tr ad itio n al   alg o r ith m s ,   P SO  [ 1 0 ]   w it h   t w o   d if f er en o b j ec tiv f u n ct io n s   as  m etah e u r is tic   tech n iq u es ; P SO1   is   t h b asic  P SO a lg o r ith m   w h er t h o b j e ctiv f u n ctio n   i s   to   m in i m ize   t h m ak e s p an   w h il e   P SO2   is   an   u p d ated   v er s io n   o f   t h b asic  P SO  a lg o r it h m   w h er th o b j ec tiv f u n ctio n   is   t o   m i n i m ize  t h lo ad   d ev iatio n ,   a n d   G A   [ 1 3 ]   as  a n   e v o lu tio n ar y   al g o r ith m   w h i ch   is   th e   o r ig i n al  o f   th e   p r o p o s ed   alg o r ith m .   I n   ad d itio n ,   th co m p ar is o n   i n cl u d es  th p r o p o s ed   HI L B   th at  r ep r esen ts   th i n it ial  p o p u lati o n   o f   HL B G A .   T h ev alu a tio n   i s   b ased   o n   th r es u lts   o f   s i m u latio n   d o n u s in g   C lo u d Si m   [ 3 5 ].     4 . 1 .     Si m ula t io o v er v iew   C lo u d Si m   i s   s i m u latio n   to o th at  s i m u lates  th b e h av io r   o f   lo ad   b alan cin g   al g o r ith m s   w h en   r u n   o n   r ea d ata  ce n ter s .   I w as  u s ed   t o   test   th p er f o r m a n ce   o f   t h p r o p o s ed   alg o r ith m   a n d   co m p ar th r esu lt s   w it h   th o t h er   al g o r ith m s   in   ter m s   o f   m a k esp an ,   r eso u r ce   u til iz atio n ,   a n d   lo ad   s ta n d ar d   d ev i atio n   [ 2 5 ] .   T ab le  2   s h o w s   t h C lo u d Si m   co n f i g u r atio n   f o r   th f o u r   s i m u lati o n s   u s ed   to   test   th b eh a v i o r   o f   th p r o p o s ed   alg o r ith m   in   d if f er e n r u n n i n g   co n d itio n s .   E ac h   s i m u lat io n   w a s   r u n   1 0 5   ti m es   an d   t h e   av e r ag w as   co n s id er ed   in   th r es u lt s .   T h p ar am eter s   o f   G A   an d   P SO a r s h o w n   in   T ab le  3 .   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2 0 8 8 - 8708       H yb r id   lo a d   b a la n ce   b a s ed   o n   g en etic  a lg o r ith in   clo u d   e n viro n men t ( W a la a   S a b er)   2485   T ab le  3 .   C lo u d Si m   co n f i g u r ati o n s     S i mu l a t i o n _ 1   S i mu l a t i o n _ 2   N u mb e r   o f   D a t a c e n t e r   1   1   N u mb e r   o f   H o st s   1   1   N u mb e r   o f   V M s   4   5   N u mb e r     o f   T a sk s     10 :   1 5 0   15   T a sk   l e n g t h   ( M I )   2 0 0 :   3 0 0 0   1 5 0 : 3 0 0   V M   S c h e d u l e r   p o l i c y   T i me   sh a r e d   C l o u d l e t   S c h e d u l e r   p o l i c y   S p a c e   s h a r e d   G A   a l g o r i t h   p a r a me t e r   se t t i n g   P a r a me t e r   V a l u e   C r o sso v e r   0 . 8   El i t e   0 . 0 5   M a x .   n u m b e r   o f   g e n e r a t i o n s   2 0 0   P o p u l a t i o n   s i z e   mi n . ( 1 0 × n u mb e r   o f   g e n e s,  2 5 0 )     P S O   a l g o r i t h m   p a r a me t e r   se t t i n g     P a r a me t e r   V a l u e   M a x i m u m   i t e r a t i o n s   2 0 0   C 1 ,   C 2   1 . 4 9 4 4 5   K   5   ω m i n , ω max     0 . 1 ,   0 . 9   P o p u l a t i o n   s i z e   20       4 . 2 .     I m pa c t   o f   increa s ing   t he  w o r klo a ds   w it h f ix ed  re s o urce s       In   t h i s   c a s e ,   t h e   n u m b e r   o f   t a s k s   i s   i n c r e a s e d   w h i l e   t h e   n u m b e r   o f   V M s   i s   f i x e d   t o   c h e c k   t h e   a l g o r i t h m ' s   b e h a v i o r   i n   d i f f e r e n t   w o r k l o a d s   o n   t h e   s a m e   r e s o u r c e s .   T h e   s i m u l a t i o n   p a r a m e t e r s   o f   S im u l a t i o n   1   ar s h o w n   in   T ab le   3 .   T h n u m b er   o f   tas k s   is   v ar y i n g   f r o m   1 0   to   1 5 0 .   T h tas k s   h a v d if f er e n len g t h s   as  h ap p en   i n   r ea l - w o r ld   w o r k lo ad s .   T h e y   w er e   g en er ated   r an d o m l y   at  t h r an g f r o m   2 0 0   to   3 0 0 0   ( MI ) .   Fo u r   VM s   w er e   co n s id er ed   f o r   th s i m u latio n .   T h ev alu atio n   m etr ic s   ar m a k esp an ,   r eso u r ce   u tili za tio n ,   a n d   lo ad   d ev iatio n .     Fig u r e   2   s h o w s   t h m a k esp an   co m p ar is o n   o f   th e   p r o p o s ed   HL B G A   w it h   t h i n te n d ed   alg o r ith m s .   I t   is   s h o w n   t h at  H L B G m in i m izes   t h m ak e s p an   co m p ar in g   w it h   th e   o th er   al g o r ith m s .   T h m a k esp a n   i m p r o v e m en o f   H L B G A   o v er   HI L B   an d   GA   is   u p   to   1 5 . 7 a n d   7 1 %;  r esp ec tiv el y .   Fi g u r e   3   s h o w s   t h lo ad   d ev iatio n   co m p ar i s o n   f o r   Si m u latio n   1 .   I ca n   b s ee n   t h at  th lo ad   d ev iatio n   o f   t h p r o p o s ed   HL B GA   i s   m i n i m ized   w h e n   co m p ar ed   w it h   t h o th er   al g o r ith m s .   T h lo ad   d ev iatio n   i m p r o v e m e n o f   H L B G A   o v er   HI L B   an d   G A   is   2 8 . 5 an d   9 6 . 1 %,  r esp ec tiv el y   i n   t h e   ca s o f   1 5 0   task s .   Fi g u r e   4   s h o w s   r eso u r ce   u tili za t io n   co m p ar i s o n   f o r   Si m u latio n   1 .   I i s   s h o w n   t h at  t h r eso u r ce   u til izatio n   o f   t h p r o p o s ed   HL B G A   i s   m ax i m ized   w h en   co m p ar ed   w it h   o th er   al g o r ith m s .   T h in cr ea s in   th u tili za tio n   o f   th p r o p o s ed   HL B GA  o v er   HI L B   an d   G A   is   1 . 8 % a n d   6 7 . 4 %,  r esp ec tiv el y   i n   th c ase  o f   1 5 0   task s .           Fig u r 2 .   Ma k esp an   v er s u s   n u m b er   o f   ta s k s       Fig u r 3 L o ad   d ev iatio n   v er s u s   n u m b er   o f   tas k s       T h r esu lt s   s h o w   t h at   th e   p er f o r m a n ce   o f   t h m eta h e u r is tic   alg o r ith m s   s u c h   as   P SO1 ,   P SO2 ,   an d   G is   m u c h   lo w er   t h an   th e   p er f o r m an ce   o f   t h tr ad itio n al  al g o r ith m s   at   lar g n u m b er   o f   tas k s .   W it h   i n cr ea s i n g   in   th n u m b er   o f   task s ,   HI L B   in tr o d u ce s   g o o d   p er f o r m an c th an   th o th er   tr ad itio n al  alg o r ith m s   s o   it  ca n   b u s ed   to   p r o d u ce   a n   i n itial   p o p u latio n   f o r   G A   to   f o r m   t h p r o p o s ed   HL B G A .   T h p r o p o s ed   HL B G A   al g o r it h m   as  h y b r id   tec h n iq u b et w e en   HI L B   an d   G A   o u tp er f o r m s   t h o t h er   alg o r it h m s .   T h m a k esp an ,   lo ad   d ev iatio n ,   an d   u t ilizatio n   i m p r o v e m e n o f   H L B GA   o v er   HI L B   an d   GA   ar 8 an d   4 8 . 3 %,  3 4 . 3 an d   8 5 %,   an d   3 . 4 % a n d   4 0 %,  r esp ec tiv el y .     Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I n t J   E lec  &   C o m p   E n g ,   Vo l.  11 ,   No .   3 J u n 2 0 2 1   :   2 4 7 7   -   2489   2486       Fig u r 4 .   R eso u r ce   u tili za tio n   v er s u s   n u m b er   o f   tas k s       4 . 3 .     I m ple m ent a t io n s   in ho m o g e neo us   a nd   het er o g eneo us   en v iro n m e nts   In   th i s   ca s e ,   t h s i m u la tio n   i s   i m p le m en ted   o n   f ix ed   n u m b er   o f   C lo u d let s   a n d   VM s   b u th s p ee d   o f   VM s   ar c h an g ed   to   te s t t h p er f o r m an ce   o f   th e   al g o r ith m s   in   Ho m o g e n eo u s   ( Ho m o g ) ,   Hete r o g o n o u s - h i g h   ( Het - h ig h )   a n d   Hete r o g e n eo u s - lo w   ( He t - lo w )   p r o ce s s o r s .   T h s i m u l atio n   p ar a m eter s   o f   S i m u lat io n   2   ar e   s h o w n   i n   T ab le  3 .   T h r ee   s i m u latio n s   w er r u n   w it h   d i f f er e n VM   s p ee d   en v ir o n m e n ts .   I n   Ho m o g e n o u s ,   a ll   th VM s   h av e   th e   s a m s p ee d .   I n   Hete r o g e n eo u s - lo w ,   th e   s p ee d   v ar iatio n   a m o n g   VM s   i s   l o w   w i th   r at io   1 :2 . 5   b et w ee n   lo w e s a n d   h i g h est   s p ee d   VM   w h ile  i n   Hete r o g en eo u s - h i g h ,   s i m u latio n   h i g h - s p ee d   v ar iatio n   a m o n g   all  VM s   w it h   r atio   1 :7   is   co n s id er ed .   T h tar g et  o f   th is   e x p er i m e n t   is   to   test   th p r o p o s ed   alg o r i th m   b e h av io r   in   th ca s o f   w o r k lo ad s   w it h   d if f er e n len g t h s   i n   v ar y in g   en v ir o n m e n ts .   Fi g u r e   5   s h o w s   a   m ak es p a n   c o m p a r is o n   o f   th e   p r o p o s e d   H L B GA   a lg o r i th m   w i th   th L B I M M ,   H I L B ,   s t an d a r d   GA   an d   PS O   a lg o r i th m s   w h i le   th e   s im u l a ti o n   e n v i r o n m en t   v a r i es   f r o m   h o m o g en e o u s   t o   h et e r o g en e o u s .   I t   i s   s h o w n   th a t   th e   m ak e s p a n   im p r o v em en t   o f   HL B G A   o v er   HI L B   an d   GA   i s   u p   to   2 . 6 an d   4 2 . 5 %,  r esp ec tiv el y .   Fi g u r 6   s h o w s   lo ad   d ev iatio n   co m p ar is o n   o f   Si m u latio n   3 .   I ca n   b s ee n   th at  t h lo ad   d ev iatio n   o f   th p r o p o s ed   alg o r ith m   i s   m in i m ized   w h e n   co m p ar ed   w it h   th e   o th e r   alg o r ith m s .   Fi g u r 7   s h o w s   th u tili za tio n   co m p ar is o n   o f   Si m u latio n   3 .   I i s   clea r   th at  th u tili za tio n   o f   t h p r o p o s ed   alg o r ith m   i s   m a x i m i ze d   w h e n   co m p ar ed   w ith   t h o th er   alg o r it h m s .             Fig u r 5 .   Ma k esp an   i n   d if f er e n t e n v ir o n m e n ts       Fig u r 6 .   L o ad   d ev iatio n   i n   d if f er en e n v ir o n m en t s           Fig u r 7 .   Utilizatio n   i n   d if f er e n t e n v ir o n m e n ts   Evaluation Warning : The document was created with Spire.PDF for Python.