Inf2 Tutorial 4
35 pages
English
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Inf2 Tutorial 4

-

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
35 pages
English

Description

Inf2 Tutorial 4Sharon Wul March 19, 2009Sharon Wul Inf2 Tutorial 4Load BalancingInput: m identical machines; n jobs; job j has a process time tj Job j must run contiguously on one machine. A machine can process at most 1 job at a time.Def. Let a be a mapping function which assigns each job to onemachinea :f1;:::;ng!f1;:::;mg{!a({)Assumption. The number of jobs is larger than the number ofmachinesn>mSharon Wul Inf2 Tutorial 4Load BalancingDef. The load on machine i isXL = ti kk:a(k)=iDef. The Maximal load on any machine isXL = arg max L = arg max ti k1im 1imk:a(k)=iSharon Wul Inf2 Tutorial 4Load Balancing - Problem De nitionMinimize the total run time of all the jobs, In other words..Assign each job to a machine such that the Maximal load isminimized (why?)(Scary) Formulation used in the lecture,Xa = argminH(a) = argminf max tgka a 1imk:a(k)=iSharon Wul Inf2 Tutorial 4Xtkk:a(k)=iis the load on the i’th machine.Xmax tk1imk:a(k)=iis taking the maximum load over all machines (this is essentiallyL, the maximum load).A Word On Mathematical NotationXa = argminH(a) = argminf max tgka a 1imk:a(k)=iReading from right to left..Sharon Wul Inf2 Tutorial 4is the load on the i’th machine.Xmax tk1imk:a(k)=iis taking the maximum load over all machines (this is essentiallyL, the maximum load).A Word On Mathematical NotationXa = argminH(a) = argminf max tgka a 1imk:a(k)=iReading from right to left. ...

Sujets

Informations

Publié par
Nombre de lectures 39
Langue English

Exrait

Inf2
Tutorial
Sharon
March
Sharon Wulff
Wulff
19,
4
2009
Inf2 Tutorial
4
Load Balancing
Input identical machines; n jobs; job j has a process time: mtj
Job j must run contiguously on one machine. A machine can process at most 1 job at a time.
Def.Let a be a mapping function which assigns each job to one machine
a:{1, . . . , n} → {1, . . . , m}
ıa(ı)
Assumption.The number of jobs is larger than the number of machines
hSraonW
n > m
ulnIf2uTtorial4
Def.
Def.
Load Balancing
Theloadon machine i is
Li=Xtk k:a(k)=i
TheMaximal loadon any machine is
1ixk:a(Xk)=i L= arg1miaxmLi ma= argm
SharonuWlnIf2uTotirla4
tk
Load Balancing - Problem Definition
Minimizethe total run time of all the jobs, In other words..
Assign each job to a machine such that theMaximalload is minimized(why?)
(Scary) Formulation used in the lecture,
a min= argH(a min) = arg{maxt 1ikm:a(Xk)=ik} a a
hSranouWlnI2fTutorial4
ehtgnikatsikti=)(k:aXkmix1mae.ihisset(hcnillamveraoadomumlmaxi:kXhtamhcniodtnehiistheloaa(k)=itkaxemumimadloSh).ssesitneyllaht,Lrial4
A Word On Mathematical Notation
a= arg minH(a min) = arg{1miaxkm:a(Xk)tk} a a =i
from right to left..
Reading
ranouWlnI2fuTot
sesitnesllait,Lymahemuxioaml.Sd)mexamimuoldavoreallmachines(this1xam.en(a:kXmiistk=ik)thngkitaeholitstheiadonachithm
k:a(k)=i
Xtk
Reading from right to left..
a= arg minH(a min) = argtk} a{1miaxk:a(Xk)=i a m
A Word On Mathematical Notation
4lairout2TnfIulnWroha
Xtk
k:a(k)=i
is the load on the i’th machine.
ial4
A Word On Mathematical Notation
a m= argainH(a m) = argain{1miaxmk(Xk)=tk} :a i
Reading from right to left..
fnT2turoorWnluIkti=atsignikmehtaxmi1k:mXk)a(ihenmlcasisi(shtumloaximeraladovlmumixamahS.)daoiantseeshe,tyLll
A Word On Mathematical Notation
irlauTot
Xtk
k:a(k)=i
= arg minH(a) = arg min{maxmXt a1ik:a(k)=ik} a a
Reading from right to left..
4
is the load on the i’th machine.
maxXtk 1imk:a(k)=i
aron).ShInf2Wulistakinodaolmumixamehtg(tesinchmallravelaylneitesssihisloadimumemaxL,th
A Word On Mathematical Notation
a a1iaxmXtk} a= arg minH(a min) = arg{m k:a(k)=i
Reading from right to left..
Xtk
k:a(k)=i
is the load on the i’th machine.
ik:a(Xk)=i 1maxmtk
is taking the maximum load over allmachines(this is essentially L, themaximum load).
hSraonWulInf2Tutorial4
istathemkingapemblsifjsongpivomuminisopllareoamlmuximaumimin2fnIluWnorahS.d
Word
A
tk}
arg main{maxX 1imk:a(k)= i
4
II
On Mathematical Notation
rialTutonehias.stobacomoehtmitpissiylpmg.Themapalmappinhhsahtmeipgnhwci
A Word On Mathematical Notation II
is taking the minimum over all possiblemappings of jobs machines.
to
arg min{1miaxk:a(Xk)=itk} a m
2fuTlnIla4otirrahSuWnolmum.daoumimximathasinemgnhwcihhhTmepaipmapping.eoptimalhtylpmissia