Inf2 Tutorial 4

Sharon Wulff

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. ...

Informations

• Publié par: Nazil
• Nombre de lectures: 39
• Langue: English

Extrait

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: mt j

• 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

L i = X t k k:a(k)=i

TheMaximal loadon any machine is

1≤i≤ x k:a( X k)=i L= arg 1≤ m i a ≤ x m L i  ma= arg m

SharonuWlffnIf2uTotirla4

t k

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≤ k m :a( X k)=i k } a a

hSranouWfflnI2fTutorial4

ehtgnikatsi k t i=)(k:a X k ≤m≤i x 1 ma e. ihisset(hcnillamveraoadomumlmaxi :k X htamhcniodtneh’iistheloa a(k)=i t k axemumimadlo Sh ). ssesitneylla ht,L rial4

A Word On Mathematical Notation

a ∗ = arg minH(a min) = arg{ 1≤ m i a ≤ x k m :a( X k) t k } a a =i

from right to left..

Reading

ranouWfflnI2fuTot

sesitnesllai t,L y mahemuxioaml. S d) mexamimuoldavoreallmachines(this ≤1 xam .en (a:k X m≤i is t k =ik) thngkita eholitstheiadonachi’thm

k:a(k)=i

X t k

Reading from right to left..

a ∗ = arg minH(a min) = argt k } a { 1≤ m i a ≤ x k:a( X k)=i a m

A Word On Mathematical Notation

4lairout2TnfffIulnWroha

X t k

k:a(k)=i

is the load on the i’th machine.

ial4

A Word On Mathematical Notation

a ∗  m= arg a inH(a m) = arg a in{ 1≤ m i a ≤ x m k( X k)= t k } :a i

Reading from right to left..

fnT2turoorWnluIff k t i= atsignikmeht axm i≤1≤ k: m X k)a( ihenmlcasisi(shtumloaximeraladov lmumixam ahS .)dao iantsees he,t y L ll

A Word On Mathematical Notation

irlauTot

X t k

k:a(k)=i

= arg minH(a) = arg min{max m X t a ∗ 1≤i≤ k:a(k)=i k } a a

Reading from right to left..

4

is the load on the i’th machine.

max X t k 1≤i≤m k:a(k)=i

aron ). ShInf2Wulff istakinodaolmumixamehtg(tesinchmallravelaylneitesssihis loadimumemaxL,th

A Word On Mathematical Notation

a a 1≤i a ≤ x m X t k } a ∗ = arg minH(a min) = arg{m k:a(k)=i

Reading from right to left..

X t k

k:a(k)=i

is the load on the i’th machine.

≤i≤ k:a( X k)=i 1 max m t k

is taking the maximum load over allmachines(this is essentially L, themaximum load).

hSraonWulffInf2Tutorial4

istathemkingapemblsifjsongpivomuminisopllare oamlmuximaumimin 2fnIffluWnorahS .d

Word

A

t k }

arg m a in{max X 1≤i≤m k:a(k)= i

4

II

On Mathematical Notation

rialTuto nehi a ∗ s. stob ac o m oehtmitpissiylpmg. Themap almappin hhsahtmeipgnhwci

A Word On Mathematical Notation II

is taking the minimum over all possiblemappings of jobs machines.

to

arg min{ 1≤ m i a ≤ x k:a( X k)=i t k } a m

2fuTfflnIla4otirrahSuWno lmum.daoumimximathasinemgnhwcihhhTmepaip mapping.eoptimalhtylpmissi ∗ a