Inf2 Tutorial 4
35
pages
English
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
35
pages
English
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
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. ...
Voir
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
ulffnIf2uTtorial4
Def.
Def.
Load Balancing
Theloadon machine i is
Li=Xtk k:a(k)=i
TheMaximal loadon any machine is
1≤i≤xk:a(Xk)=i L= arg1≤mia≤xmLi ma= argm
SharonuWlffnIf2uTotirla4
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 1≤i≤km:a(Xk)=ik} a a
hSranouWfflnI2fTutorial4
A Word On Mathematical Notation
a∗= arg minH(a min) = arg{1≤mia≤xkm:a(Xk)tk} a a =i
from right to left..
Reading
ranouWfflnI2fuTot
k:a(k)=i
Xtk
Reading from right to left..
a∗= arg minH(a min) = argtk} a{1≤mia≤xk:a(Xk)=i a m
A Word On Mathematical Notation
4lairout2TnfffIulnWroha
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{1≤mia≤xmk(Xk)=tk} :a i
Reading from right to left..
fnT2turoorWnluIffkti=atsignikmehtaxmi≤1≤k:mXk)a(ihenmlcasisi(shtumloaximeraladovlmumixamahS.)daoiantseeshe,tyLll
A Word On Mathematical Notation
irlauTot
Xtk
k:a(k)=i
= arg minH(a) = arg min{maxmXt a∗1≤i≤k:a(k)=ik} a a
Reading from right to left..
4
is the load on the i’th machine.
maxXtk 1≤i≤mk:a(k)=i
aron).ShInf2Wulffistakinodaolmumixamehtg(tesinchmallravelaylneitesssihisloadimumemaxL,th
A Word On Mathematical Notation
a a1≤ia≤xmXtk} 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.
≤i≤k:a(Xk)=i 1maxmtk
is taking the maximum load over allmachines(this is essentially L, themaximum load).
hSraonWulffInf2Tutorial4
Word
A
tk}
arg main{maxX 1≤i≤mk:a(k)= i
4
II
On Mathematical Notation
rialTutonehia∗s.stobacomoehtmitpissiylpmg.Themapalmappinhhsahtmeipgnhwci
A Word On Mathematical Notation II
is taking the minimum over all possiblemappings of jobs machines.
to
arg min{1≤mia≤xk:a(Xk)=itk} a m
2fuTfflnIla4otirrahSuWnolmum.daoumimximathasinemgnhwcihhhTmepaipmapping.eoptimalhtylpmissi∗a
