Tuning struggle strategy in genetic algorithms for scheduling in computational grids

Tuning S uggle S a egy in Gene ic Algo i hms o Scheduling in Compu a ional G ids Fa os Xha a∗ , Be na Du an∗, Aji h Ab aham† , Kesha Dahal‡ Abs ac : Job Scheduling in Compu a ional G ids is gaining impo ance due o he need o e icien la ge-scale G id-enabled applica ions. Among di e en op imiza ion echniques add essed o he p oblem, Gene ic Algo i hm (GA) is a popula class o solu ion me hods. As GAs a e high le el algo i hms, speci ic algo i hms can be designed by choosing he gene ic ope a o s as well as he e olu iona y s a egies such as S eady S a e GAs and S uggle GAs. In his pape we ocus on S uggle GAs and hei uning o scheduling o independen jobs in compu a ional g ids. Ou esul s showed ha a ca e ul hash implemen a ion o compu ing he simila i y o solu ions was able o alle ia e he compu a ional bu den o S uggle GA and pe o m be e han s anda d simila i y measu es. This is pa icula ly in e es ing o he scheduling p oblem in G id sys ems, which due o changeabili y o e ime, has demanding ime es ic ions on he compu a ion o he planning o jobs o esou ces. Key wo ds: Gene ic Algo i hms, Scheduling, G id Compu ing, S uggle S a egy, Simila i y Measu e, Tuning. Recei ed: ?? Re ised and accep ed: ?? 1. In oduc ion Wi h he eme ging pa adigm o G id Compu ing and he de elopmen o G id in- as uc u es, G id-based applica ions a e becoming a common app oach o sol ing many complex p oblems. A key issue in his kind o applica ions is scheduling jobs in o G id esou ces e icien ly, which is known o be compu a ionally ha d and much mo e di icul han i s s anda d e sion o sequen ial o LAN compu a ion en i onmen s. ∗Depa men o Languages and In o ma ics Sys ems, Technical Uni e si y o Ca alonia, Cam- pus No d, Ed. Omega, C/Jo di Gi ona 1-3, 08034 Ba celona, Spain. E-mail: [email p o ec ed], [email p o ec ed] †Cen e o Excellence o Quan i iable Quali y o Se ice, No wegian Uni e si y o Science and Technology, T ondheim, No way [email p o ec ed] ‡School o In o ma ics, Uni e si y o B ad o d, B ad o d BD7 1DP, UK [email p o ec ed] c °ICS AS CR 2006 1 Neu al Ne wo k Wo ld 2/06, ?? Job Scheduling in Compu a ional G ids is gaining impo ance due o he need o e icien la ge-scale G id-enabled applica ions, e.g. in Op imiza ion (Casano a e al. [8], Goux e al. [13] and W igh [30]), Linde o h e al. [19]), Collabo a- i e/eScience Compu ing (e.g. Newman e al. [22], Paniagua e al. [24]), Da a- In ensi e Compu ing (e.g. Beynon al. [3]) and many applica ions a ising om con- c e e ypes o G ids such as Science G ids, Access G ids, Knowledge G ids, e c. Scheduling is a challenging p oblem in a G id en i onmen due i s dynamic na u e and he la ge numbe o esou ces o be managed and jobs o be scheduled. Fu - he mo e, esou ces can ha e hei own local policies ( ega ding access, cos e c.) o be aken in o accoun . The p oblem is mul i-objec i e in i s gene al de ini ion, as he e a e se e al op imiza ion c i e ia o be ma ched, such as makespan, low ime, and esou ce u iliza ion. Se e al app oaches a e being add essed in he li e a u e o he p oblem aiming o ob ain schedule s capable o deli e ing as planning o jobs o compu a ional esou ces o he g id sys em. On he one hand he e many ad hoc me hods such as immedia e and ba ch mode me hods [37, 36]. Such me hods dis inguish o hei simplici y and e iciency. Howe e , hese me hods ail o p oduce high quali y plan- ning o jobs o G id esou ces; o ins ance he immedia e me hod o Oppo unis ic Load balancing assigns a job o he machine ha e he smalles wo kload, which in a e y he e ogenous G id en i onmen could pe o m poo ly. Mo eo e , such me h- ods can handle only one objec i e a a ime (usually he makespan, wo kload, e c.) and in G id sys ems usually he e a e mo e equi emen s on scheduling. Gi en he la ge scale o he G id sys ems as well as pe iodic submissions o la ge quan i y o jobs, esea che s a e seeking o ways o design mo e e icien G id schedule s. In pa icula , Gene ic Algo i hms (GA) [16] ha e p o ed o be a good al e na i e o sol ing a wide a ie y o ha d combina o ial op imiza ion p oblems and a e he e- o e app op ia e o job scheduling in G ids. GAs a e a popula ion-based app oach whe e indi iduals ep esen possible solu ions, which a e successi ely e alua ed, selec ed, c ossed, mu a ed and eplaced by simula ing he Da winian e olu ion ound in na u e. Gene ic Algo i hms o G id scheduling p oblems ha e been ad- d essed by Ab aham e al. [1], B aun e al. [5], Zomaya and Teh [41], Ma ino and Mililo i [9], Page and Naugh on [23], Ca e e o and Xha a [7], Gao e al. [12], Xha a e al. [35, 34]. The esea ch wo k on GAs has shown ha a key issue in GAs is he con e gence o he algo i hm: a as con e gence o he popula ion would s agna e he sea ch o local op ima whe eas slowe con e gence would equi e a conside ably longe ime owa ds sub-op imal solu ions. The con e gence o GAs is achie ed by means o selec ion and eplacemen s a egies and i is, he e o e, e y impo an o ca e- ully une hese s a egies. In pa icula , he selec i e p essu e di ec ly a ec s he adeo be ween he explo a ion and exploi a ion o he sea ch space. Indeed, i he popula ion con e ges apidly GA would gi e mo e p io i y o he exploi a ion and, ice- e sa, when he popula ion is kep di e se, o he egions o he sea ch space would be explo ed aspi ing hus o ind be e solu ions. GAs ep esen hus an in e es ing amily o algo i hms o G id scheduling since in many p ac ical G id-enabled applica ions we a e in e es ed o compu e a easonably good plan- ning o jobs in a e y sho ime a he han an op imal planning. In such case, GAs a e use ul since we can “bu s up” he con e gence o he algo i hm. Ye , we 2 Xha a e al.: Tuning S uggle S a egy in GAs o Scheduling in G ids a e in e es ed o a oid a e y p ema u e con e gence o he algo i hm. In his wo k we ocus on he impo ance o uning he eplacemen mechanism o GA o scheduling in compu a ional g ids. The in e es in in es iga ing his aspec is mo i a ed by he need o design e icien schedule s ha will be able o deli e as and quali y planning o jobs o esou ces a he op imal solu ions in a dynamic en i onmen . Mo e p ecisely, we s udy he uning o he S uggle s a - egy (G ueninge [14]; see also [28]). Acco ding o his s a egy, a new indi idual eplaces he indi idual ha is mos simila o i only in case he new indi idual ob ains a be e i ness alue han he one o be eplaced. The aim is o p ese e he op imiza ion eloci y bu delaying i s endency o con e ge in o de o each a be e con e gence poin . This s a egy is known o i s e ec i eness bu su e s om a high compu a ional cos . Mo e p ecisely, gi en a new indi idual, inding a simila indi idual o i equi es compa ing agains all indi iduals o he cu en gene a ion. E icien compu a ion o he simila i y would he e o e alle ia e he compu a ional bu den o he S uggle GA. The es o he pape is o ganized as ollows. Some ela ed wo k o he schedul- ing p oblem as well as GA-based wo k ha , as in he case o S uggle GA, use simila i y measu es o main ain he di e si y o he popula ion du ing he e olu- ion p ocess a e gi en in Sec ion 2. The p oblem o scheduling o independen jobs conside ed in his wo k is p esen ed in Sec ion 3. The S uggle s a egy oge he wi h simila i y measu es a e in oduced in Sec ion 4. The expe imen al s udy and some compu a ional esul s a e gi en in Sec ion 5. We conclude in his wo k wi h some ema ks and indica ions o u u e wo k in Sec ion 6. 2. Rela ed wo k In his sec ion we b ie ly e iew some ela ed wo k in compu a ional in elligence echniques applied o he scheduling p oblem. Also, o he GA-based wo k ha , as in he case o S uggle GA use simila i y measu es o main ain he di e si y o he popula ion du ing he e olu ion p ocess, a e also indica ed. Gene ic Algo i hms o G id scheduling p oblems ha e been add essed by Ab a- ham e al. [1], B aun e al. [5], Zomaya and Teh [41], Ma ino and Mililo i [9], Page and Naugh on [23], Ca e e o and Xha a [7], Gao e al. [12], Xha a e al. [35, 34]. Finding a good ade-o be ween he explo a ion and exploi a ion, which is closely ela ed o he di e si y o popula ion, has been explo ed in he GA li - e a u e [4, 6, 10, 38]. An in e es ing ecen app oach o he adeo be ween explo a ion and exploi a ion in e olu iona y algo i hms is based on he en opy concep [20]. Mul i-objec i e GAs (such as NSGA, SPEA) use some simila i y measu es o main ain he di e si y o he popula ion du ing he e olu ion p ocess. Thus, Sa o e al. [26], p oposed a me hod o NSGA II (Non-domina ed So ing Gene ic Al- go i hm II) in which simila indi iduals a e elimina ed in he p ocess o e olu- ion by using he dis ance be ween indi iduals in objec i e space. Ishibuchi and Na ukawa [17] examined he ela ion be ween he pe o mance o he NSGA-II al- go i hm and he simila i y o ecombined pa en solu ions o lowshop scheduling p oblems. The au ho s examined he e ec o inc easing he selec ion p essu e on 3 Neu al Ne wo k Wo ld 2/06, ?? he simila i y o ecombined pa en solu ions. Wildman and Pa ks [29] p esen ed a compa a i e s udy o selec i e s a egies in Mul i-objec i e GAs h ough di e en pai ing s a egies o combining pa en s. Ishibuchi and Shiba a [18] p oposed a new ma ing scheme in which simila i y-based ou namen selec ion is used o choosing a pai o pa en s among he candida e solu ions aiming o main ain he di e si y o solu ions. Recen ly, Meme ic Algo i hms (MAs) [21] –a ela i ely new class o popula ion- based me hods– which combine he concep s o e olu iona y sea ch and local sea ch ha e been p oposed o G id scheduling p oblem. Xha a [32] applied uns uc u ed MAs and Xha a e al. [33] p oposed Cellula MAs (s uc u ed MAs) o he inde- penden scheduling p oblem unde ETC model. O he app oaches include Rein o ced Lea ning, Neu al Ne wo ks, Fuzzy Logic, e c. Some au ho s ha e used ein o ced lea ning echniques o scheduling in G id sys ems. Pe ez e al. [25], p oposed o implemen a Rein o cemen Lea ning based scheduling app oach o la ge G id compu ing sys ems. Venge o [27] p esen ed a u ili y-based amewo k o making epea ed scheduling decisions dynamically; he obse ed in o ma ion abou unscheduled jobs and sys em’s esou ces is used o his pu pose. Yu e al. [39] used Fuzzy Neu al Ne wo ks o de elop a high pe o mance scheduling algo i hm. The algo i hms uses Fuzzy Logic echniques o e alua e he G id sys em load in o ma ion, and adop he Neu al Ne wo ks o au oma ically une he membe ship unc ions. Hao e al. [15] p esen ed a G id esou ce selec ion based on Neu al Ne wo ks aiming a o e ing QoS on dis ibu ed, he e ogeneous esou ces. To his end, he au ho s p opose o selec G id esou ces cons ained by QoS c i e ia. The esou ce selec ion p oblem is sol ed using a no el neu al ne wo ks. Zhou e al. [40] used Fuzzy Logic echniques o design an adap i e Fuzzy Logic schedule , which u ilizes he Fuzzy Logic con ol echnology o selec he mos sui able compu ing node in he G id en i onmen . 3. P oblem de ini ion The job scheduling p oblem in G ids has many cha ac e is ics in common wi h he adi ional scheduling p oblems. The objec i e is o e icien ly map jobs o esou ces; howe e , in a global, he e ogenous and dynamic en i onmen , such as G id en i onmen , we a e in e es ed o ind a p ac ically good planning o jobs e y as . In his wo k we deal wi h he scheduling independen jobs o esou ces. We desc ibe his e sion nex and hen gi e a o mal de ini ion o an ins ance o he p oblem. Jobs ha e he ollowing cha ac e is ics: a e o igina ed om di e en use s/applica ions, ha e o be comple ed in unique esou ce (non-p eemp i e), a e independen and could also ha e hei equi emen s o e esou ces. This las cha - ac e is ic is impo an i we would like o classi y jobs o igina ed om da a in ensi e o compu ing in ensi e applica ions. On he o he hand, esou ces could dynam- ically be added/d opped om he G id, can p ocess one job a a ime and ha e hei compu ing cha ac e is ics. This e sion a ises in many G id-based applica ions, such as in simula ions, massi e da a p ocessing, which can be di ided in o independen pa s, which a e mapped o di e en G id esou ces. 4 Xha a e al.: Tuning S uggle S a egy in GAs o Scheduling in G ids Expec ed Time o Compu e simula ion model In o de o o malize he ins ance de ini ion o he p oblem, we use he ETC (Expec ed Time To Compu e) ma ix model, see e.g. [5]. This model is used o cap u ing mos impo an cha - ac e is ics o job and esou ces in dis ibu ed he e ogeneous en i onmen s. In a ce ain sense, a good planning jobs o esou ces will ha e o ake in o accoun he cha ac e is ics o jobs and esou ces. Mo e p ecisely, he Expec ed Time o Com- pu e ma ix, ET C, has size nb jobs ×nb machines and i s componen s ET C[i][j] a e de ined as he expec ed execu ion ime o job iin machine j. ETC ma ices a e hen classi ied in o consis en , inconsis en and semi-consis en acco ding o he consis ency o compu ing o esou ces: (a) consis ency means ha i a machine mi execu es a job as e han machine mj, hen miexecu es all he jobs as e han mj. I his holds o all machines pa icipa ing in he planning, he ETC ma ix is conside ed consis en ; (b) inconsis ency means ha a machine is as e o some jobs and slowe o some o he s; and, (c) semi-consis ency is used o exp ess he ac ha an ETC ma ix can ha e a consis en sub-ma ix. In his case he ETC ma ix is conside ed semi-consis en . No ice ha he a iabili y in cha ac e is- ics o jobs and esou ces yields o di e en ETC con igu a ions allowing hus o simula e di e en scena ios om eal li e dis ibu ed applica ions. P oblem de ini ion Unde he ETC simula ion model, an ins ance o he p ob- lem consis s o : – A numbe o independen (use /applica ion) jobs o be scheduled. – A numbe o he e ogeneous machines candida es o pa icipa e in he planning. – The wo kload o each job (exp essed in millions o ins uc ions). – The compu ing capaci y o each machine (exp essed in mips –millions o ins uc- ions pe second). – Ready ime eady[m] –when machine mwill ha e inished he p e iously as- signed jobs. – The Expec ed Time o Compu e ma ix, ET C. Op imiza ion c i e ia. Se e al objec i e c i e ia can be es ablished o a gi en schedule. We conside he minimiza ion o makespan, ha is, inishing ime o la es job (Sdeno es a possible schedule): min Smax{Fj:j∈Jobs}. whe e Fjis he inishing ime o job j. Makespan can be exp essed in e ms o he comple ion ime o a machine, as ollows: makespan = max{comple ion[i]|i∈Machines} whe e o a machine m: comple ion[m] = eady[m] + X {j∈Jobs |schedule[j]=m} ET C[j][m]. 5 Neu al Ne wo k Wo ld 2/06, ?? 4. S uggle s a egy in GAs and simila i y mea- su es In S uggle GAs [14, 28] (he ea e , SGA), a new gene a ion o indi iduals is c ea ed by eplacing only a po ion o he popula ion wi h he new indi iduals. The s uggle gene ic algo i hm wo ks simila ly as he s eady-s a e GAs. Howe e , is ead o eplacing he wo s indi idual, in SGA a new indi idual eplaces he indi idual ha is mos simila o i only in case he new indi idual ob ains a be e i ness alue han he one o be eplaced. This is done in o de o adap i ely main ain ce ain di e si y among he popula ion. The aim is o p ese e he op imiza ion eloci y bu delaying i s endency o con e ge in o de o each a be e con e gence poin . The design o he s uggle eplacemen ope a o equi es he de ini ion o ap- p op ia e simila i y measu es. A simila i y measu e indica es how simila a e wo indi iduals (solu ions o he p oblem). The de ini ion o a simila i y measu e could be done in di e en ways, o ins ance by using he s uc u e o he solu ion (com- bina o ics p ope ies) I has been shown in GA li e a u e ha in he long un S uggle GA and S eady S a e GA con e ge o a single solu ion. The in e es in using S uggle GA, as opposed o S eady S a e-like GAs is ha in S uggle GAs popula ion e ol es by main aining di e en solu ions long a e a basic o s eady-s a e algo i hm would ha e con e ged. This is a desi ed p ope y o he case o he scheduling p oblem in Compu a ional G ids gi en ha we can ine une he schedule o “con e ge” o a good solu ion depending on a ailable ime ( o ins ance, schedule ’s ime ac i a ion in e al). Fu he , S uggle GAs a e simple o implemen and equi e no addi ional pa ame e s o ine une bu he s uggle ope a o . I should be no ed howe e ha he pe o mance o S uggle GA, despi e o good di e si y o he popula ion, depends also on he es o gene ic ope a o s; hus, c oss-o e ope a o s eeding he popula ion wi h good indi iduals and low mu a ion a e would yield a e y good pe o mance o he S uggle GA. 4.1 Compu a ional complexi y o s uggle ope a o This s a egy has shown o be e y e ec i e o se e al p oblems [14, 2]; ye , he e is an e iciency issue he e: he compu a ional cos o his eplacemen s a egy is e y high. Indeed, in o de o ind which indi iduals should lea e he popula ion, any new indi idual o he in e media e popula ion has o be compa ed and i s simila i y measu ed agains all he indi iduals o he cu en popula ion. Ob iously, his leads o a quad a ic o de compu a ional ime, which could be e y la ge, i la ge size popula ions we e o be conside ed. In ac , his is p ecisely he case o scheduling independen jobs in compu a ional g ids; hei la ge scale and scalabili y a e c i ical ac o s since no only he numbe o esou ces and jobs submi ed o he G id sys em a e expec ed o be la ge o e y la ge bu also hey could inc ease o e ime. I is clea ha simila i y measu es which a e no e icien could consume much o he GA unning ime in de imen o he p ope sea ch ime. 6 Xha a e al.: Tuning S uggle S a egy in GAs o Scheduling in G ids 4.2 S anda d simila i y measu es In o de o compa e he simila i y be ween solu ions, a measu e o simila i y o dis ance unc ion has o be de ined and used. S anda d simila i y measu es include: •Hamming dis ance: gi en wo indi iduals S1and S2encoding wo schedulings o Njobs, le g[i] = 1, i S1[i] = S2[i] and g[0] = 0, o he wise. Simila i y is hen calcula ed as: Simh(S1, S2) = PN i=1 g[i] N. •Euclidian dis ance: This simila i y is based on he Euclidean dis ance. Gi en wo ec o solu ions S1and S2, by conside ing hem as wo poin s in N- dimensional space, he simila i y is hen compu ed as he Euclidean dis ance be ween hem: Sime(S1, S2) = u u N X i=1 (S1[i]−S2[i])2. •Cosine dis ance: In his case, he simila i y is measu ed using he angle o he wo ec o solu ions S1and S2o he N-dimensional space. Cosine alues close o 1 would mean mo e simila i y. Simc(S1, S2) = PN i=1 S1[i]·S2[i] qPN i=1 S2 1[i]·qPN i=1 S2 2[i] . 4.3 Hash-based simila i y measu e The s anda d simila i y measu es gi en abo e has linea ime compu a ional cos in numbe o jobs. The e o e o a popula ion o pop size he s anda d s uggle s a e- gies would ake O(in e media e pop size ×pop size)×N, whe e Nis he numbe o jobs. Reducing he quad a ic ac o o O(in e media e pop size ×pop size) o a linea ime ac o would be e y desi able in his case since in each eplacemen s ep i would ake a conside able ime in de imen o he p ope sea ch ime o he GA. In o de o achie e his, we p opose he use o hash echniques so ha gi en a new indi idual o he in e media e popula ion we can ind in cons an ime he indi idual mos simila o i . In o de o design he hash able, we ha e o i s de ine he key o iden i y he indi iduals o he popula ion. The key in o ma ion is he basis o compu ing he deg ee o simila i y o he s uggle gene ic ope a o : he mo e accu a e i s de ini ion he be e he pe o mance o he ope a o . In ac , a poo de ini ion o he key would simply educe he s uggle ope a o o a andom eplacemen . In ou de ini ion o he key he con ex is c ucial: he key alue should esume as much as possible he gene ic in o ma ion encoded in an indi idual; hence, i wo key alues a e simila hen hei espec i e indi iduals a e gene ically simila . The ollowing a e h ee possible de ini ions: 7 Neu al Ne wo k Wo ld 2/06, ?? a) Fi ness-based key: consis s in using he i ness alue, which is ans o med, using a hash unc ion, in o he key alue. Ce ainly his is a e y simplis ic app oach by simply looking a makespan and low ime alues and clea ly no gene ic in o ma ion is aken in o accoun (we e e o his as ’a’ key). b) Posi ion-based key: ha ing he pe mu a ion ec o o ask- esou ce alloca ion, in which asks a e so ed acco ding o he esou ce hey a e assigned o, he key is de ined as he sum o numbe o cells a componen o he ec o would mo e o he igh as indica ed by i s alue, when he ec o is ead in a ci cula way (we e e o his as ’b’ key). Fo ins ance, o he ec o o 7 asks in Fig. 1 below, key = 2 + 4 + 1 + 0 + 2 + 5 + 0 = 14.  5      1 2 3 4 5 6 7        Fig. 1 Example posi ion-based key calcula ion. No e ha his de ini ion uses he gene ic cha ac e is ics o he solu ion; how- e e , he ela ion ask- esou ce is no explici ly aken in o accoun , i.e., o which esou ce is assigned a ask. c) Task- esou ce alloca ion key: In his case bo h in o ma ion on asks and e- sou ces is used. The key alue is now he sum o he absolu e alues o he sub ac ion o each posi ion and i s p eceden in he ec o o ask- esou ce alloca ion ( eading he ec o in a ci cula way); we e e o his as ’c’ key. We gi e in Fig. 2 he g aphical ep esen a ion o he hash able design as well as he o mulae de ini ion o he hash unc ion. No e ha he co esponding posi ion is ob ained om a solu ion om he key alue k;kmin and kmax co espond espec i ely o he key wi h smalles and la ges alue in he popula ion. The hash able has he same size as he popula ion in o de o ob ain cons an ime access (in a e age). I an access ails, a ew indi iduals in he popula ion a e andomly chosen and he mos simila o he new one is conside ed o he eplacemen . Hence, he cons an access is always ensu ed e en i a ailed access occu s. The e o e, he compu a ional cos o he hash-based s uggle ope a o is O(pop size +in e media e pop size). 8 Xha a e al.: Tuning S uggle S a egy in GAs o Scheduling in G ids 0 i k < kmin hash (k) =                 − − minmax min kk kk N i kmin ≤ k < kmax N-1 i k ≥ kmax 0 1 2 i+1 N N-1 i s y s z s x Ø s q s s u s s s Fig. 2 Rep esen a ion o he hash able and he hash unc ion de ini ion. 5. Expe imen al s udy In his sec ion we p esen he expe imen al s udy o he p oposed hash-based S ug- gle GA. Ini ially, we gene a ed a se o ins ances acco ding o ETC ma ix model in o de o s udy he pe o mance o he h ee key de ini ions and also o ine une he es o he pa ame e s o S uggle GA. The bes esul ing con igu a ion was hen used o s udying he pe o mance o he SGA on a se o known ins ances om B aun e al. [5]. 5.1 Pe o mance compa ison o s uggle hash ope a o s The pe o mance o he h ee s uggle ope a o s esul ing om a key,b key and c key de ini ions we e measu ed o makespan alue o he schedule. Fo each o hem, he same con igu a ion o pa ame e s (see Table I) was used; epo ed alues a e a e aged o e 10 independen s uns. In Table I, MCT (Minimum Comple ion ime) and LJFR-SJFR (Longes Job o Fas es Resou ce - Sho es Job o Fas es Resou ce) a e wo me hods used in ini ializing he popula ion; ebalance-bo h is a mu a ion ope a o based on load balancing o esou ces. MCT me hod [11] assigns a job o he machine yielding he ea lies comple ion ime ( he eady imes o he machines a e used). When a job a i es in he sys em, all a ailable esou ces a e examined o de e mine he esou ce ha yields he smalles comple ion ime o he job. On he o he hand, LJFR- SJFR [1] ies o simul aneously minimize bo h makespan and low ime alues: LJFR (Longes Job o Fas es Resou ce) ies o minimize makespan and SJFR (Sho es Job o Fas es Resou ce) ies o minimize low ime. We show in Fig 3, he makespan alue compu ed by he SGA algo i hm wi h 9 Neu al Ne wo k Wo ld 2/06, ?? [23] Page, J. and Naugh on, J. F amewo k o ask scheduling in he e ogeneous dis ibu ed compu ing using gene ic algo i hms. AI Re iew, 24:415-429, 2005. [24] Paniagua, C., Xha a, F., Caball´e, S. and Da adoumis, T. A pa allel g id-based implemen a- ion o eal ime p ocessing o e en log da a in collabo a i e applica ions. In Pa allel and Dis ibu ed P ocessing Techniques (PDPT2005), 1177–1183, Las Vegas, USA, 2005. [25] Pe ez, J., K´egl, B. and Ge main-Renaud, C. Rein o cemen lea ning o u ili y-based G id scheduling. A NIPS07 (Twen y-Fi s Annual Con e ence on Neu al In o ma ion P ocessing Sys ems) Wo kshops, in Vancou e , Canada, 2007. [26] Sa o, M., Agui e, H.E. and Tanaka, K. E ec s o -Simila Elimina ion and Con olled Eli ism in he NSGA-II Mul iobjec i e E olu iona y Algo i hm. In IEEE Cong ess on E olu iona y Compu a ion, 1164-1171, Vancou e , BC, Canada, 2006 [27] Venge o , D. Adap i e U ili y-Based Scheduling in Resou ce-Cons ained Sys ems. In AI 2005: Ad ances in A i icial In elligence, pp. 477-488, Sp inge Ve lag, 2005 [28] Nicola Senin, Robe o G oppe i and Da id R. Wallace. Concu en assembly planning wi h gene ic algo i hms. Robo ics and Compu e -In eg a ed Manu ac u ing, Vol. 16, Issue 1, pp. 65-72, 2000 [29] Wildman, A. and Pa ks, G. A Compa a i e S udy o Selec i e B eeding S a egies in a Mul iobjec i e Gene ic Algo i hm. In C.M. Fonseca e al. (Eds.): EMO 2003, LNCS 2632, pp. 418432, 2003. [30] W igh , S. (2001). Sol ing op imiza ion p oblems on Compu a ional G ids. Op ima, Vol. 65, 2001. [31] Xha a, F. A Hype -heu is ic o Adap i e Scheduling in Compu a ional G ids, In e na ional Jou nal on Neu al and Mass-Pa allel Compu ing and In o ma ion Sys ems, 17(6), 639-656, 2007 [32] Xha a, F. A Hyb id E olu iona y Heu is ic o Job Scheduling in Compu a ional G ids. Sp inge Ve lag Se ies: S udies in Compu a ional In elligence , Vol. 75 2007, Chap e 10, ISBN: 978-3-540-73296-9. Sep embe 2007. [33] Xha a, F., Alba, E., Do onso o, B. and Du an, B. E icien Ba ch Job Scheduling in G ids using Cellula Meme ic Algo i hms, Accep ed, Jou nal o Ma hema ical Modelling and Al- go i hms, Published Online DOI: h p://dx.doi.o g/10.1007/s10852-008-9076-y [34] Xha a, F., Ba olli, L. and Du esi, A. An Expe imen al S udy On Gene ic Algo i hms o Resou ce Alloca ion On G id Sys ems, Jou nal o In e connec ion Ne wo ks, Volume: 8, Issue: 4 (Decembe 2007), 427 - 443, Wo ld Sci. Pub. [35] Xha a, F. Ca e e o, J. and Ab aham, A. Gene ic Algo i hm Based Schedule s o G id Com- pu ing Sys ems. In e na ional Jou nal o Inno a i e Compu ing, In o ma ion and Con ol, Vol. 3, No.5, pp. 1-19, 2007. [36] F. Xha a, L. Ba olli and A. Du esi. Ba ch Mode Schedule s o G id Sys ems. In e na ional Jou nal o Web and G id Se ices, Vol. 3, No. 1, 19-37, 2007. [37] F. Xha a, J. Ca e e o, L. Ba olli and A. Du esi. Immedia e Mode Scheduling in G id Sys ems. In e na ional Jou nal o Web and G id Se ices, Vol.3 No.2, 219-236, 2007. [38] Yan, W. and Clack, Ch. D. Beha iou al GP di e si y o dynamic en i onmen s: an applica- ion in hedge und in es men , In GECCO ’06: P oceedings o he 8 h annual con e ence on Gene ic and e olu iona y compu a ion, 1817–1824, New Yo k, NY, USA, 2006. ACM P ess. [39] Yu, K.M., Luo, Zh.J., Chou, Ch.H., Chen, Ch.K., and Zhou, J. A Fuzzy Neu al Ne wo k Based Scheduling Algo i hm o Job Assignmen on Compu a ional G ids. NBiS 2007: 533- 542, Lec u e No es in Compu e Science, Sp inge Ve lag, 2007 [40] Zhou, J., Kun-Ming Yu, K-M. Chou, Ch-H., Yang, L-A., and Luo, Zh-J.: A Dynamic Re- sou ce B oke and Fuzzy Logic Based Scheduling Algo i hm in G id En i onmen . ICANNGA (1) 2007: 604-613, 2007. [41] Zomaya, A.Y. and Teh, Y.H. Obse a ions on using gene ic algo i hms o dynamic load- balancing, IEEE T ansac ions On Pa allel and Dis ibu ed Sys ems, 12(9):899–911, 2001. 16