F amewo k o ask scheduling in he e ogeneous
dis ibu ed compu ing using gene ic algo i hms
And ew J. Page and Thomas J. Naugh on
Depa men o Compu e Science,
Na ional Uni e si y o I eland,
Maynoo h, I eland.
[email p o ec ed],
h p://www.cs.may.ie/∼apage
Abs ac . An algo i hm has been de eloped o dynamically schedule
he e ogeneous asks on o he e ogeneous p ocesso s in a dis ibu ed sys-
em. The scheduling s a egy ope a es in a dynamically changing com-
pu ing esou ce en i onmen and adap s o a iable communica ion cos s
and a iable a ailabili y o p ocessing esou ces. The schedule u ilises a
gene ic algo i hm o minimise he o e all execu ion ime. Expe imen s
a e pe o med which show ha he algo i hm can achie e nea op imal
e iciency, wi h up o 100,000 asks being scheduled.
1 In oduc ion
Scheduling he e ogeneous asks on o he e ogeneous esou ces, o he wise known
as he ask alloca ion p oblem, is an NP-ha d p oblem o he gene al case [7]. In
mul i-p ocesso sys ems, such as a dis ibu ed sys em, one would expec linea
speed-up when addi ional p ocesso s a e employed o p ocess asks. P ope ies
o a dis ibu ed sys em such as communica ion o e heads, he e ogeneous p oces-
so s, and he e ogeneous asks can educe he e iciency achie ed by he sys em.
The de elopmen o a scheduling s a egy is equi ed o p oduce schedules which
seek o minimise he o al execu ion ime. The schedule mus also ha e he abil-
i y o adap o a ying esou ce en i onmen s.
Many heu is ic algo i hms exis o speci ic ins ances o he ask scheduling
p oblem, bu a e ine icien o a mo e gene al case [6, 15]. The use o Holland’s
gene ic algo i hms [13] (GAs) in scheduling, which apply e olu iona y s a egies
o allow o he as explo a ion o he sea ch space o possible schedules, allows
o solu ions which seek o minimise he execu ion ime o be ound quickly and
o he schedule o be applied o mo e gene al p oblems. Many esea che s ha e
in es iga ed he use o GAs o schedule asks in homogeneous [4, 14, 23] and
he e ogeneous [1, 9, 10, 17, 22] mul i-p ocesso sys ems wi h g ea success.
Un o una ely assump ions a e o en made which educe he gene ali y o
hese solu ions, such as ha scheduling is calcula ed o -line in ad ance and
canno change, all communica ions imes mus be known in ad ance [1, 4, 9, 14,
22], ne wo ks p o ide ins an aneous message passing [10, 23] and ha p ocesso s
will always un a he same speeds [1, 4, 9, 10, 14, 15, 19, 21–24]. These assump-
ions limi he gene ali y o hese scheduling s a egies in eal wo ld sys ems.
We make no assump ions abou he homogenei y o he p ocesso s, o abou he
a ailabili y o sys em esou ces.
In his pape a scheduling s a egy is p esen ed which uses a GA o schedule
he e ogeneous asks on o he e ogeneous p ocesso s o minimise he o al exe-
cu ion ime. I ope a es dynamically, allowing o asks o a i e o p ocessing
con inuously, i conside s a iable ne wo k con en ion and a iable speed p o-
cesso s based on his o ical obse a ion o sys em condi ions, and i maximises
he use o he p ocesso which is esponsible o scheduling asks.
In Sec . 2 we e iew ela ed wo k. In Sec . 3 we gi e an o e iew o how a GA
ope a es. In Sec . 4 we desc ibe ou scheduling algo i hm. In Sec . 5 we p esen
he esul s o ou pe o mance expe imen s, and conclude in Sec . 6.
2 Rela ed Wo k
The e a e many examples in he li e a u e o a i icial in elligence echniques
being applied o ask scheduling [1, 4, 9, 10, 14, 15, 17, 19, 21–24]. Me a-heu is ic
sea ch echniques such as GAs [13], abu [8], and an colony sea ch [3] a e mos
applicable o he ask scheduling p oblem because we wish o quickly sea ch o
a nea op imal schedule ou o all possible schedules. Good esul s ha e been
yielded h ough he use o GAs in ask scheduling algo i hms [1, 4, 9, 10, 14, 15,
17, 19, 21, 23, 24].
Much wo k has been done on using GAs o s a ic scheduling [1, 4, 9, 14, 22],
whe e schedules a e c ea ed be o e un ime, bu he s a e o all asks and sys em
esou ces mus be known a p io i and canno change. This limi s hese schedule s
o speci ic p oblems and sys ems.
Dynamic GA schedule s [10, 17, 23, 24] c ea e schedules a un ime, wi h
knowledge abou he p ope ies o he sys em and asks possibly no known
in ad ance, allowing o a iable sys em and ask p ope ies o be conside ed.
Dynamic GA schedule s a e hus he mos p ac ical o he wo o use o eal
wo ld dis ibu ed sys ems. Cu en dynamic GA schedule s ha e been shown
o p oduce nea op imal schedules in simula ions, al hough assump ions ha
ha e been made limi hei use ulness. Communica ions cos s and he possibili y
o a iable p ocessing esou ces a e no conside ed. We p opose ha his o ical
in o ma ion abou communica ion cos s and a iable p ocesso speeds be con-
side ed when c ea ing a schedule. An algo i hm is p esen ed in his pape which
co esponds o he eal wo ld and add esses p ope ies which ha e no been
p e iously add essed in GA based dynamic ask scheduling algo i hms.
3 Gene ic Algo i hms
A GA is a me a-heu is ic sea ch echnique which allows o la ge solu ion spaces
o be heu is ically sea ched in polynomial ime, by applying e olu iona y ech-
niques om na u e [13]. GAs use his o ical in o ma ion o exploi he bes so-
lu ions om p e ious sea ches, known as gene a ions, along wi h andom mu a-
ions o explo e new egions o he solu ion space. A GA can be b oken down
in o h ee s eps impo an s eps, selec ion, c osso e , and andom mu a ions. Se-
lec ion acco ding o i ness is a sou ce o exploi a ion, and c osso e and andom
mu a ions p omo e explo a ion.
A gene a ion o a GA con ains a popula ion o s ings, σi, each o which
co espond o a possible solu ion om he sea ch space. Each s ing in he pop-
ula ion has a alue associa ed wi h i , Fi, indica ing how ‘ i ’ he s ing is, o
how good he s ing is, compa ed o he es o he s ings in he popula ion.
4 Scheduling Algo i hm
In his sec ion we de ail ou scheduling algo i hm which u ilises he GA me a-
heu is ic sea ch echnique. The algo i hm we ha e de eloped is based on one
de eloped by Zomaya e al. [23, 24]. We ha e c ea ed an algo i hm which can
adap o a ying esou ce en i onmen s and can p oduce nea op imal schedules.
The GA algo i hm is only pe o med i he e a e mo e unscheduled asks han
p ocesso s; i he e a e ewe asks han p ocesso s, he la ges ask ge s assigned
o he p ocesso which will inish p ocessing i ea lies .
We wish o schedule an unknown numbe o asks o p ocessing on a dis-
ibu ed sys em wi h a minimum execu ion ime. The p ocesso s o he dis-
ibu ed sys em a e he e ogeneous, and i is assumed we ha e non-exclusi e
usage o hei p ocessing esou ces. The a ailable p ocessing esou ces on each
p ocesso can a y o e ime. P ocesso s can be added, emo ed, o ail, and
can be idle. Each p ocesso can be uniquely iden i ied by a scheduling p oces-
so , which is dedica ed o c ea ing schedules o map asks o p ocesso s. The
a ailable ne wo k esou ces be ween p ocesso s in he dis ibu ed sys em can
a y o e ime. Each ask, i, o be scheduled o p ocessing has an associa ed
p ocessing esou ce equi emen and he ask can be uniquely iden i ied. Tasks
a e also indi isible, independen o all o he asks, and can be p ocessed by any
p ocesso in he dis ibu ed sys em.
Tasks a i e a unknown in e als o p ocessing, and a e placed in a queue o
unscheduled asks. Ba ches o asks om his queue a e scheduled on p ocesso s
du ing each in oca ion o he schedule . Each ask has a esou ce equi emen
which is measu ed in millions o loa ing poin ope a ions pe second (M lop/s).
Each p ocesso can only p ocess a single ask a any one ime. The a ailable
p ocessing esou ces o each p ocesso a e known (in M lop/s), measu ed using
Donga a’s Linpack benchma k [5]. This is a ecognised s anda d used o bench-
ma k sys ems o inclusion in he lis o Top 500 supe compu e s [16]. A ailable
p ocessing and ne wo k esou ces a y o e ime, so he exponen ial smoo hing
unc ion (see Sec . 4.1) is used o minimise localised luc ua ions, hus allowing
o a mo e ealis ic p ocessing en i onmen o be con olled. A single p ocesso is
dedica ed o scheduling (as in [11]) al hough i is ecognised ha he scheduling
algo i hm i sel could be dis ibu ed o e all o he p ocesso s in he dis ibu ed
sys em.
Each idle p ocesso in he sys em eques s a ask o p ocess om he sched-
ule , which is hen p ocessed and e u ned. The schedule con ains a queue o
asks which ha e been mapped o each p ocesso , and when a eques o wo k
is ecei ed om a p ocesso he ask a he head o he co esponding queue is
sen o p ocessing. A p ocesso does no con ain a queue o asks, because ne -
wo k esou ces a e limi ed and p ocessing esou ces a e no dedica ed, hus we
do no wish o epea edly hand ou he same asks mul iple imes when sys em
esou ces change signi ican ly.
4.1 Exponen ial Smoo hing Func ion
An exponen ial smoo hing unc ion, Ai=Ai−1+ν×(ai−Ai−1), is u ilised
o allow o a single ‘a e age’ alue, A, o accu a ely ep esen mul iple alues,
a1, a2, .., an, which a i e sequen ially p oducing A1, A2, .., An, while smoo hing
ou luc ua ions, and allowing ecen alues o exe mo e in luence han olde
alues whose in luence ends owa ds ze o. The o al numbe o alues is N. The
sp ead o he unc ion is con olled by ν, whe e ν= [0,1].
4.2 Communica ion cos s
Communica ion cos s, such as bandwid h (bi s/second) and la ency (seconds),
be ween he schedule and he p ocesso s a ailable o wo k should be conside ed
in any schedule p oduced. We use his o ical in o ma ion abou ne wo k commu-
nica ion imes be ween p ocesso s o es ima e u u e communica ion cos s, hus
allowing o a mo e eal wo ld scheduling en i onmen o be conside ed.
The cos o sending a ask k o p ocesso Pjis Ck,j = (bk,j /Qk,j )+(Rk,j /2).
Cj,k deno es he communica ion cos be ween p ocesso jand he schedule o
ask k. This alue is de i ed by calcula ing he cos o sending and ecei ing
messages. The la ency o he communica ions channel om he schedule o
each p ocesso is es ed, and a ound ip ime is calcula ed which is included in
Rjusing he smoo hed a e age unc ion. When a ask is sen om he schedule
o a p ocesso , i s size in by es, bk,j , is calcula ed, whe e kis he k h ask sen .
The p ocesso hen sends back an acknowledgemen , and he ask ound ip
ime is no ed as k,j. The numbe o by es sen pe second is calcula ed as
qk,j = (bk,j / k,j)−Rjand qk,j is hen sen o he smoo hing unc ion o p oduce
Qk,j , which deno es he bandwid h o a gi en channel.
4.3 Dynamic Ba ch Size
Tasks a i e o p ocessing a andom in e als and a e added o he queue o
unscheduled asks T. The queue may con ain a la ge numbe o asks wai ing
o be scheduled; howe e , i may ake a long ime o ind a schedule o all
he asks which e icien ly u ilises sys em esou ces. Ins ead a dynamically sized
ba ch conside s ba ches o asks o scheduling om he queue, which educes he
p obabili y o p ocesso s wai ing on he schedule o inish c ea ing a schedule.
A single p ocesso is dedica ed o scheduling (such as in [11]), so we s i e o
maximise he use o i s esou ces, a cos which has no been conside ed by some
dynamic scheduling algo i hms [10, 17, 23]. I is easie o ob ain a high u ilisa ion
o p ocessing esou ces i he e is a high a io o asks o p ocesso s [23].
The ime a GA akes o un om s a o inish is ela ed o he size o he
ba ch, kH2, whe e kis a cons an o e head and His he size o he ba ch. Thus
using he exponen ial smoo hing unc ion a smoo hed a e age ime, ST whe e
ST ≥1, o a single elemen in he ba ch can be calcula ed. We wish o ully
u ilise he esou ces o he dedica ed scheduling p ocesso . The ime when he
i s p ocesso becomes idle is calcula ed as ollows, minTime = minM
j=1(δj/Pj),
whe e δjis he p ocessing ime in M lop/s wai ing o be p ocessed by p ocesso Pj
and Mis he numbe o p ocesso s in he dis ibu ed sys em. Thus H=b√STc,
whe e H≥1, esul ing in a dynamically sized ba ch which ully u ilises he
p ocesso belonging o he schedule .
Once a schedule has been assigned he ba ch size is once again ecalcula ed
and ano he schedule is p oduced un il he e a e no mo e asks in T o schedule.
4.4 Encoding
Each s ing, σi, in he popula ion ep esen s a di e en possible schedule. We
ha e chosen o use double p ecision loa ing poin numbe s o each cha ac e
o σi. Each cha ac e in σip o ides in o ma ion abou mappings be ween asks
and p ocesso s. The numbe o cha ac e s in σiis ω=H+M−1, whe e His he
numbe o asks in he ba ch, and M−1 is he numbe o pa i ions in he s ing,
whe e Mis he numbe o p ocesso s. Each ask in he ba ch is mapped o a
p ocesso , wi h a unique ask ID numbe iden i ying he ask, and a delimi e
sepa a ing he di e en p ocesso s queues.
4.5 Mos in o Leas
An ini ial popula ion is gene a ed using he Mos -In o-Leas (MIL) lis schedul-
ing heu is ic, which has been success ully used in o he GA ask schedule s [4,
10]. A andom numbe o asks, a e assigned o p ocesso s in a ound obin ash-
ion. The emaining asks a e hen so ed, using Quickso [12], and alloca ed in
a ound obin ashion o he p ocesso s which will inish p ocessing hem he
ea lies , aking in o accoun exis ing and assigned asks o each p ocesso . This
leads o a well balanced andomised ini ial popula ion.
4.6 Fi ness Func ion
A i ness unc ion a aches a nume ical alue o e e y s ing in he popula ion,
which indica es how much be e one schedule is o e he es o he schedules
in he popula ion. We use ela i e e o o gene a e a i ness alue o each
s ing (used in [10]) in he popula ion because i allows o he makespan and
load balancing o a schedule o be ep esen ed in a single nume ical alue. This is

only an in e nal me ic o heu is ically di ec he explo a ion o he sea ch space.
When he GA has inished unning, he s ing wi h he smalles makespan is used
by he schedule o assign asks o p ocesso s.
In a gi en s ing σi, an e o ejis calcula ed o each p ocesso , Pj, whe e ej
is a non-nega i e loa ing poin numbe . P e iously assigned, bu unp ocessed,
load o each p ocesso is conside ed by calcula ing δj, he inishing ime o a p o-
cesso j. The inishing ime is calcula ed as δj= (Lj/Pj), whe e Ljdeno es he
p e iously assigned load, measu ed in M lop/s, and Pjis he cu en p ocessing
powe in M lop/s o p ocesso j.
The heo e ical op imal p ocessing ime can now be ound,
ψ= (
N
P
i=1
i/
M
P
j=1
Pj) +
M
P
j=1
δjwhe e iis he p ocessing equi emen o ask iin
he ba ch (in M lop/s) and Nis he o al numbe o asks in he ba ch.
The ela i e e o o a s ing is gi en as
Ei=sM
P
j=1 |ψ−(Lk,i +
M
P
u=1
(( y/Pj) + C y,j))|2whe e C y,j is he communica-
ion cos (see Sec . 4.2), o scheduling a ask, y, on a p ocesso j. The i ness
alue o a s ing is Fi= 1/Ei, whe e Fi= [0,1]. A la ge alue indica es a be e
o i e schedule.
4.7 Selec ion, C osso e and Mu a ion
We choose o use he s anda d weigh ed oule e wheel me hod o selec ion
which is widely used by p e ious esea che s who ha e applied GAs o ask
scheduling [4, 9, 10, 14, 19, 23]. Each s ing in he popula ion, σi, is assigned a
slo , ςi, be ween 0 and 1. The size o a slo is ςi=Fi×(
ρ
P
j=1
F−1
j), whe e
ρ
P
i=1
ςi= 1.
A e he selec ion p ocess is comple e we use he cycle c osso e me hod [18]
o p omo e explo a ion as used in [23]. We ha e chosen o use wo ypes o
mu a ion o p omo e explo a ion o he sea ch space. Fi s o all we andomly
swap elemen s o a andomly chosen s ing in he popula ion. The nex ype
o mu a ion aims o make a s ing mo e balanced. A andom s ing is selec ed
and a ask on he p ocesso , Pj, wi h he g ea es ela i e e o , Ei,j , is hen
andomly selec ed and inse ed andomly in o he queue o a di e en p ocesso .
This heu is ic encou ages well balanced solu ions o be ound in less ime.
4.8 S opping Condi ions
The GA will keep e ol ing he popula ion un il one o mo e s opping condi ions
a e me . The s ing wi h he lowes makespan is selec ed a e each gene a ion
and i i is less han a speci ied minimum, he GA s ops e ol ing. The maximum
numbe o gene a ions is se a 1000 [23]. The GA will also s op e ol ing i one
o he p ocesso s becomes idle, in which case i will e u n he bes schedule
ound so a .
5 Expe imen s
The scheduling algo i hm desc ibed in Sec . 4 has been implemen ed and simu-
la ions ha e been pe o med, wi h up o 50 he e ogeneous p ocesso s, and up o
100,000 andomly gene a ed he e ogeneous asks. Each expe imen was epea ed
a numbe o imes and an a e age esul was calcula ed o each poin . We also
implemen ed he o iginal algo i hm ha ou algo i hm is based on, de eloped
by Zomaya e al. [23], which is he cu en s a e o he a dynamic GA ask
schedule o homogeneous dis ibu ed compu ing. I was easily adap ed o wo k
wi h he e ogeneous p ocesso s by using M lop/s as he measu e o he a e o
execu ion a he han ime.
Tasks a e scheduled ac oss 50 he e ogeneous p ocesso s wi h a p ocessing
esou ce ange o 10 o 100 M lop/s. We assume ha all o he asks a i e o
p ocessing a he beginning o he simula ion, o hese expe imen s. De e mining
a ep esen a i e se o he e ogeneous compu ing ask benchma ks emains a
challenge o he scien i ic communi y in his esea ch a ea as no ed by Theys e
al. [20]. We ha e decided o gene a e andom se s o asks o scheduling using
he Poisson dis ibu ion. We use andomly gene a ed ask se s because: we wish
o demons a e he algo i hms e ec i eness o e a b oad ange o condi ions, a
se o he e ogeneous compu ing benchma k asks do no exis , and i is no clea
wha cha ac e is ics a ‘ ypical’ ask would exhibi [20].
We ha e decided o use a popula ion size o 10, which is known as a mi-
c o GA [2] and used in [10, 23, 24], which speeds up compu a ion ime wi hou
impac ing g ea ly on he inal esul . We ha e also compa ed ou scheduling
algo i hm agains a numbe o well known ba ch and immedia e mode heu is-
ic schedule s. An immedia e mode schedule only conside s a single ask o
scheduling on a FCFS basis.
The Min-min ba ch schedule begins wi h a ba ch o unscheduled asks. I
hen schedules he ask wi h he minimum comple ion ime o he nex a ailable
p ocesso . This is epea ed un il all asks ha e been scheduled. The Max-min
ba ch schedule is simila o he Min-min schedule excep i schedules he ask
wi h he maximum comple ion ime o he nex a ailable p ocesso . The ea lies
i s immedia e mode schedule conside s asks on a FCFS basis. When a ask
a i es o scheduling, i is assigned o he p ocesso which will inish p ocessing
i he ea lies . The ligh es loaded schedule is also an immedia e mode schedule .
When a ask a i es o scheduling i is assigned o he p ocesso which has he
ligh es exis ing load.
5.1 Communica ion
We wish o show ha ou algo i hm p o ides g ea e e iciency in a sys em wi h
a iable communica ion cos s. To demons a e i s e ec i eness we a y he a io
o he ask p ocessing equi emen o communica ions cos s, and measu e he
e iciency achie ed. We ix he a ailable p ocessing esou ces and he size o
he ba ch, o allow o he e ec o communica ion cos s o be demons a ed.
We wish o schedule 100,000 asks wi h a iew o maximising he e iciency o
0 0.05 0.1 0.15 0.2 0.25 0.3 0.35
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
1/ ime spen communica ing
E iciency
Imp o ed schedule
Ea lies Fi s
Ligh es Load
Min−Min
Max−min
O iginal schedule
Round Robin
Fig. 1. E iciency o schedule s a ying communica ion o ask size a io
he p ocessing esou ces in he dis ibu ed sys em. The communica ions cos s
be ween each p ocesso and he schedule a e no mally dis ibu ed.
Figu e 1 shows ha he imp o ed algo i hm p oposed in his pape consis-
en ly p o ides schedules wi h g ea e e iciency o e all o he o he schedul-
ing algo i hms. The conside a ion o communica ion cos s allows he imp o ed
schedule o es ima e a communica ions cos when c ea ing a schedule, esul ing
in an o e all imp o emen in e iciency o he schedule .
6 Conclusion
A scheduling algo i hm has been de eloped o schedule he e ogeneous asks on o
he e ogeneous p ocesso s in a dis ibu ed sys em. I p o ides e icien schedules,
adap ing o a ying esou ce en i onmen s wi h espec o p ocessing esou ces,
and communica ions cos s. The algo i hm also ully u ilises he dedica ed p oces-
so unning he schedule . The GA employed he MIL lis scheduling heu is ic o
c ea e a well balanced andomised ini ial popula ion. The i ness unc ion u ilises
he ela i e e o me ic in e nally which p omo es a well balanced solu ion wi h
a low makespan. Roule e wheel selec ion is used o exploi pas esul s o di-
ec he sea ch o e icien schedules. Cycle c osso e p omo es explo a ion o
he sea ch space. Random swaps and andom e-balancing o p ocesso queues
wi hin s ings pe u b he sea ch and acili a e a be e explo a ion o he sea ch
space.
Resul s ha e been p esen ed which show ha he algo i hm p oposed in
his pape consis en ly uses p ocesso s mo e e icien ly han he cu en s a e
o he a GA algo i hms o he same p oblem. I is mo e sui able o eal-
wo ld use because i conside s p ope ies o dis ibu ed sys ems, such as a iable
communica ion cos s and a iable speed he e ogeneous p ocesso s, which o he
algo i hms o he ask scheduling p oblem do no conside .
7 Acknowledgemen
Suppo is acknowledged om he I ish Resea ch Council o Science, Enginee -
ing, and Technology, unded by he Na ional De elopmen Plan.
Re e ences
1. I. Ahmad, Y.-K. Kwok, I. Ahmad, and M. Dhodhi. Scheduling pa allel p og ams
using gene ic algo i hms. In A. Y. Zomaya, F. E cal, and S. Ola iu, edi o s, So-
lu ions o pa allel and dis ibu ed compu ing p oblems, chap e 9, pages 231–254.
John Wiley and Sons, 2001.
2. A. Chippe ield and P. Flemming. Pa allel gene ic algo i hms. In A. Y. Zomaya,
edi o , Pa allel and Dis ibu ed Compu ing Handbook, pages 1118–1143. McG aw-
Hill, New Yo k, USA, i s edi ion, 1996.
3. A. Colo ni, M. Do igo, and V. Maniezzo. Dis ibu ed op imiza ion by an colonies.
In P oceedings o he Fi s Eu opean Con e ence on A i icial Li e, 1991.
4. R. Co ea, A. Fe ei a, and P. Reb eyend. Scheduling mul ip ocesso asks wi h
gene ic algo i hms. IEEE T ansac ions on Pa allel and Dis ibu ed Sys ems,
10(8):825–837, Augus 1999.
5. J. Donga a, J. Bunch, C. Mole , and G. S ewa . LINPACK Use s Guide. SIAM,
Philadelphia, USA, 1979.
6. H. El-Rewini, T. G. Lewis, and H. H. Ali. Task scheduling in pa allel and dis ibu ed
sys ems. P en ice-Hall, Englewood Cli s, NJ, USA, 1994.
7. M. R. Ga ey and D. S. Johnson. Compu e s and In ac abili y: A Guide o he
Theo y o NP-Comple eness. W. H. F eeman & Co., New Yo k, NY, 1979.
8. F. Glo e . Fu u e pa hs o in ege p og amming and links o a i icial in elligence.
Compu e s and Ope a ions Resea ch, 13:533–549, 1986.
9. M. G ajca . Gene ic lis scheduling algo i hm o scheduling and alloca ion on
a loosely coupled he e ogeneous mul ip ocesso sys em. In P oceedings o he
36 h ACM/IEEE con e ence on Design au oma ion, pages 280–285, New O leans,
Louisiana, USA, 1999. ACM P ess.
10. W. A. G eene. Dynamic load-balancing ia a gene ic algo i hm. In 13 h IEEE In-
e na ional Con e ence on Tools wi h A i icial In elligence, pages 121–129, Dallas,
Texas, USA, No embe 2001.
11. B. Hamidzadeh, L. Y. Ki , and D. Lilja. Dynamic ask scheduling using online op-
imiza ion. IEEE T ansac ions on Pa allel and Dis ibu ed Sys ems, 11(11):1151–
1163, No embe 2000.
12. C. A. R. Hoa e. Quickso . Compu e Jou nal, 5(1):10–15, 1962.
13. J. Holland. Adap a ion in Na u al and A i icial Sys ems. Uni e si y o Michigan
P ess, 1975.
14. E. Hou, N. Ansa i, and H. Ren. A gene ic algo i hm o mul ip ocesso scheduling.
IEEE T ansac ions on Pa allel and Dis ibu ed Sys ems, 5(2):113–120, Feb 1994.