Macchine parallele - dii.unisi.itdetti/Lucidi_mac_par.pdf · Descrizione del problema n lavori...

Macchine parallele

LAVORI

M1

M2

M3

J1 J2

J3 J4

Macchine parallele

Descrizione del problema n lavori devono essere processati da m macchine diverse (unrelated) disposte in parallelo. Le macchine possono eseguire un solo lavoro alla volta. Ogni lavoro deve essere eseguito su una ed una sola macchina senza interruzione. Dati I tempi di processamento pij, i=1,…, m, del lavoro j sulla macchina i sono noti. Obiettivo Assegnare i lavori alle macchine in modo tale da minimizzare il tempo totale di completamento della macchina più carica (equivalente a minimizzare il makespan).

Scheduling su macchine parallele scorrelate R ||Cmax

Obiettivo Trovare un assegnamento dei lavori alle macchine che minimizza il makespan (Cmax) equivale a bilanciare il più possibile i carichi di lavoro delle macchine.

Scheduling su macchine parallele scorrelate R ||Cmax

Esempio

1 2 3 4 51 12 17 19 15 142 30 17 16 31 173 28 27 28 23 27

Lavori

Macchine

M3

M2

M1 J1 J4

J3

t

J5

34

J2

Una soluzione ammissibile

Esempio

1 2 3 4 51 12 17 19 15 142 30 17 16 31 173 28 27 28 23 27

Lavori

Macchine

M3

M2

M1 J1 J4

J2

t

J5

33

J3

Una soluzione ottima

Il problema è NP-completo anche con due macchine identiche •  m=2

• 

Complessità

mipp jij ,...,1 ==

P2 | |Cmax

Regola LPT (Longest Processing Time): assegna alle macchine (che si rendono) disponibili i lavori non eseguiti con tempo di esecuzione più grande. Permette di trovare una soluzione che non dista più di un dato valore dall’ottimo (algoritmo approssimato)

Un algoritmo approssimato per Pm||Cmax

Esempio regola LPT m=4


J 1 2 3 4 5 6 7 8 9

pj 7 7 6 6 5 5 4 4 4

M3

M2

M1 J1 J7

J3

t

J2

15

J8

Soluzione LPT

M4 J4

J5

J6

J9


J 1 2 3 4 5 6 7 8 9

pj 7 7 6 6 5 5 4 4 4

M3

M2

M1 J1

J7

J3

t

J2

12

J8

Soluzione Ottima

M4

J4

J5

J6

J9

Si può dimostrare che vale il seguente rapporto di approssimazione: Cmax(LPT): soluzione trovata con la regola LPT Cmax (OPT): soluzione ottima

Cmax(LPT )Cmax(OPT )

≤43−13m


Esempio regola LPT m=4


J 1 2 3 4 5 6 7 8 9

pj 7 7 6 6 5 5 4 4 4

Cmax(LPT )Cmax(OPT )

=1512

=43−13m

=43−112

=1512

Consideriamo il problema di schedulare n lavori su m macchine identiche con l’obiettivo di minimizzare il makespan, e con la possibilità di interrompere l’esecuzione dei lavori. Uno stesso lavoro può quindi essere eseguito su più macchine. Il problema è formulabile come problema di Programmazione Lineare e quindi risolubile in tempo polinomiale.

Il problema con premption Pm|prmp|Cmax

Il problema con premption Pm|prempt|Cmax

Una Formulazione di PL

Definizione delle variabili Ci , i=1,…, m, tempo di completamento della macchina i xij = tempo di lavoro j assegnato alla macchina i

{ } sistema il tutto di ntocompletame di tempo max ,...,1max imi CC ==

Funzione obiettivo Il tempo di completamento Ci della generica macchina i è pari a:

Ci = xijj=1

n

∑

Cmax =max i=1,...,m Ci{ } =max i=1,...,m xijj=1

n

∑⎧⎨⎪

⎩⎪

⎫⎬⎪

⎭⎪

Una formulazione di PL per Pm|prempt|Cmax

xiji=1

m

∑ = pj j =1,...,n

Vincoli Ogni lavoro deve essere completato


xiji=1

m

∑ ≤Cmax j =1,...,n

Vincoli Il tempo totale di ogni lavoro non può superare Cmax (il vincolo implica che le esecuzioni di uno stesso lavoro su diverse macchine non possono sovrapporsi)


xijj=1

n

∑ ≤Cmax i =1,...,m

Vincoli Il tempo totale di lavoro di ogni macchina non può superare Cmax


min Cmax

tale che

xiji=1

m

∑ = pj j =1,...,n

xiji=1

m

∑ ≤Cmax j =1,...,n

xijj=1

n

∑ ≤Cmax i =1,...,m

xij ≥ 0


Una formulazione di PLI per R| |Cmax

Una formulazione di PLI per R||Cmax

Definizione delle variabili Ci , i=1,…, m, tempo di completamento della macchina i

{ } sistema il tutto di ntocompletame di tempo max ,...,1max imi CC ==

xij =1 se lavoro j è assegnato alla macchina i0 altrimenti

⎧⎨⎩


Funzione obiettivo Ci , i=1,…, m, tempo di completamento della macchina i

Ci = pij xijj=1

n

∑

Cmax =max i=1,...,m Ci{ } =max i=1,...,m pij xijj=1

n

∑⎧⎨⎪

⎩⎪

⎫⎬⎪

⎭⎪

xiji=1

m

∑ =1 j =1,...,n

Vincoli Ogni lavoro deve essere assegnato ad esattamente una macchina


min Cmax =min max i=1,...,m Ci{ } =min max i=1,...,m pij xijj=1

n

∑⎧⎨⎪

⎩⎪

⎫⎬⎪

⎭⎪

tale che

xiji=1

m

∑ =1 j =1,...,n

xij ∈ 0,1{ }


min Cmax =min max i=1,...,m Ci{ } =min max i=1,...,m pij xijj=1

n

∑⎧⎨⎪

⎩⎪

⎫⎬⎪

⎭⎪

tale che

xiji=1

m

∑ =1 j =1,...,n

xij ∈ 0,1{ }


Funzione obiettivo non

lineare

min Cmax

tale che

Ci = pij xijj=1

n

∑ ≤Cmax i =1,...,m

xiji=1

m

∑ =1 j =1,...,n

xij ∈ 0,1{ }


Lavori

1 2 3 4 5 6 7 8 9 101 12 17 19 15 14 19 12 24 11 292 30 17 17 31 17 13 13 12 28 153 28 27 28 23 27 27 15 21 12 114 11 27 28 27 29 24 16 29 30 23

Macchine 5 16 31 31 17 18 15 28 30 27 136 28 20 23 21 13 10 10 22 24 247 20 17 28 24 30 12 16 19 21 248 14 11 15 27 17 23 30 27 12 159 26 11 28 15 22 22 29 21 21 1710 12 22 21 24 24 27 26 11 15 14

Esempio

Consideriamo un problema con 10 macchine e 10 lavori. In tabella sono riportati i tempi di processamento:

Formulazione con Excel

Soluzione del rilassamento lineare

Formulazione con Cplex min Cmax subject to 3 x0,0 + 7 x0,1 + 35 x0,2 + 26 x0,3 + 12 x0,4 + 84 x0,5 + 40 x0,6 + 44 x0,7 + 93 x0,8 + 56 x0,9 - Cmax <= 0 85 x1,0 + 3 x1,1 + 49 x1,2 + 34 x1,3 + 55 x1,4 + 52 x1,5 + 80 x1,6 + 57 x1,7 + 55 x1,8 + 74 x1,9 - Cmax <= 0 16 x2,0 + 74 x2,1 + 15 x2,2 + 86 x2,3 + 96 x2,4 + 95 x2,5 + 46 x2,6 + 33 x2,7 + 3 x2,8 + 51 x2,9 - Cmax <= 0 43 x3,0 + 11 x3,1 + 98 x3,2 + 84 x3,3 + 95 x3,4 + 7 x3,5 + 86 x3,6 + 13 x3,7 + 7 x3,8 + 15 x3,9 - Cmax <= 0 78 x4,0 + 76 x4,1 + 62 x4,2 + 58 x4,3 + 5 x4,4 + 91 x4,5 + 40 x4,6 + 1 x4,7 + 40 x4,8 + 49 x4,9 - Cmax <= 0 94 x5,0 + 13 x5,1 + 79 x5,2 + 97 x5,3 + 19 x5,4 + 78 x5,5 + 46 x5,6 + 71 x5,7 + 59 x5,8 + 7 x5,9 - Cmax <= 0 86 x6,0 + 61 x6,1 + 24 x6,2 + 30 x6,3 + 88 x6,4 + 21 x6,5 + 73 x6,6 + 21 x6,7 + 68 x6,8 + 58 x6,9 - Cmax <= 0 44 x7,0 + 6 x7,1 + 49 x7,2 + 50 x7,3 + 69 x7,4 + 27 x7,5 + 27 x7,6 + 89 x7,7 + 74 x7,8 + 74 x7,9 - Cmax <= 0 62 x8,0 + 76 x8,1 + 77 x8,2 + 55 x8,3 + 19 x8,4 + 19 x8,5 + 45 x8,6 + 13 x8,7 + 13 x8,8 + 35 x8,9 - Cmax <= 0 98 x9,0 + 42 x9,1 + 70 x9,2 + 82 x9,3 + 52 x9,4 + 33 x9,5 + 50 x9,6 + 89 x9,7 + 68 x9,8 + 94 x9,9 - Cmax <= 0 x0,0 + x1,0 + x2,0 + x3,0 + x4,0 + x5,0 + x6,0 + x7,0 + x8,0 + x9,0 =1 x0,1 + x1,1 + x2,1 + x3,1 + x4,1 + x5,1 + x6,1 + x7,1 + x8,1 + x9,1 =1 x0,2 + x1,2 + x2,2 + x3,2 + x4,2 + x5,2 + x6,2 + x7,2 + x8,2 + x9,2 =1 x0,3 + x1,3 + x2,3 + x3,3 + x4,3 + x5,3 + x6,3 + x7,3 + x8,3 + x9,3 =1 x0,4 + x1,4 + x2,4 + x3,4 + x4,4 + x5,4 + x6,4 + x7,4 + x8,4 + x9,4 =1 x0,5 + x1,5 + x2,5 + x3,5 + x4,5 + x5,5 + x6,5 + x7,5 + x8,5 + x9,5 =1 x0,6 + x1,6 + x2,6 + x3,6 + x4,6 + x5,6 + x6,6 + x7,6 + x8,6 + x9,6 =1 x0,7 + x1,7 + x2,7 + x3,7 + x4,7 + x5,7 + x6,7 + x7,7 + x8,7 + x9,7 =1 x0,8 + x1,8 + x2,8 + x3,8 + x4,8 + x5,8 + x6,8 + x7,8 + x8,8 + x9,8 =1 x0,9 + x1,9 + x2,9 + x3,9 + x4,9 + x5,9 + x6,9 + x7,9 + x8,9 + x9,9 =1 integers x0,0 x0,1 x0,2 .... x9,8 x9,9 end

La tecnica del Rilassamento Lagrangiano nella soluzione di

problemi di PLI: Un’applicazione a R||Cmax

Il Rilassamento Lagrangiano nei problemi di PLI

Si consideri il seguente problema di PLI, P:

z* =mincxAx ≥ b (1)Cx ≥ d (2)

x ∈ 0,1{ }n,b ∈ ℜm1,d ∈ ℜm2

c ∈ ℜn vettore riga

Il Rilassamento Lagrangiano nei problemi di PLI

Si consideri il seguente problema di PLI, P:

z* =mincxAx ≥ b (1)Cx ≥ d (2)

x ∈ 0,1{ }n,b ∈ ℜm1,d ∈ ℜm2

c ∈ ℜn vettore riga

Supponiamo che P sia difficile da risolvere

Supponiamo invece che sia di facile risoluzione il problema rilassato PR:

Il Rilassamento Lagrangiano dei vincoli (1) consiste nell'inserire una combinazione pesata di tali vincoli nella funzione obiettivo

mincxCx ≥ d (2)

x ∈ 0,1{ }n

Il Rilassamento Lagrangiano dei vincoli (1) consiste nell'inserire una combinazione pesata di tali vincoli nella funzione obiettivo. Si ottiene il seguente Problema Lagrangiano:

con λ≥0 vettore riga di dimensione m1

Supponiamo che il Problema Lagrangiano sia ancora facile da risolvere per ogni λ≥0

mincx + λ(b-Ax)Cx ≥ d (2)

x ∈ 0,1{ }n

La funzione L(λ) (con λ≥0 vettore riga di dim. m1):

L(λ) =min cx + λ(b − Ax) :Cx ≥ d,x ∈ 0,1{ }n{ }

è detta funzione Lagrangiana, il vettore λ è detto vettore dei moltiplicatori di Lagrange

Vale la seguente proprietà: La funzione lagrangiana è un lower bound alla soluzione ottima del problema iniziale P per ogni vettore λ≥0:

L(λ) ≤ z * ∀λ ∈ ℜm1+

Dimostrazione Infatti, per ogni vettore λ≥0 si ha:

z* =min cx : Ax ≥ b;Cx ≥ d,x ∈ 0,1{ }n{ } ≥

min cx + λ(b − Ax) : Ax ≥ b;Cx ≥ d,x ∈ 0,1{ }n{ }

Dimostrazione(segue) Infatti, per ogni vettore λ≥0 si ha:

☐

z* =min cx : Ax ≥ b;Cx ≥ d,x ∈ 0,1{ }n{ } ≥

min cx + λ(b − Ax) : Ax ≥ b;Cx ≥ d,x ∈ 0,1{ }n{ } ≥

min cx + λ(b − Ax) :Cx ≥ d,x ∈ 0,1{ }n{ } = L(λ)

Il miglior lower bound è ottenuto calcolando il Duale Lagrangiano

L(λ * ) =max L(λ) : λ ≥ 0{ }L(λ*) può essere ottenuto risolvendo un problema di ottimizzazione non differenziabile

λ

L(λ*)

L(λ)

λ*

Teorema. Sia z*PL il valore della soluzione otttima del rilassamento lineare di P : si ha L(λ*) ≥ z*PL

zPL =mincxAx ≥ b (1)Cx ≥ d (2)0 ≤ x ≤1

Teorema. Sia z*PL il valore della soluzione otttima del rilassamento lineare di P : si ha L(λ*) ≥ z*PL Dim. L(λ * ) =max min cx + λ(b − Ax) :Cx ≥ d,x ∈ 0,1{ }

n{ } : λ ≥ 0{ } ≥max min cx + λ(b − Ax) :Cx ≥ d,0 ≤ x ≤1{ } : λ ≥ 0{ }


Teorema. Sia z*PL il valore della soluzione otttima del rilassamento lineare di P : si ha L(λ*) ≥ z*PL Dim. L(λ * ) =max min cx + λ(b − Ax) :Cx ≥ d,x ∈ 0,1{ }

n{ } : λ ≥ 0{ } ≥max min cx + λ(b − Ax) :Cx ≥ d,0 ≤ x ≤1{ } : λ ≥ 0{ } ≥max min cx + λ(b − Ax)+µ(d −Cx) :−x ≥ −1,x ≥ 0{ } : λ ≥ 0,µ ≥ 0{ } ≥max min cx + λ(b − Ax)+µ(d −Cx)+ν(x −1) : x ≥ 0{ } : λ ≥ 0,µ ≥ 0,ν ≥ 0{ } =


Dim. (segue)

L(λ * ) ≥ ...≥

max min cx + λ(b − Ax)+µ(d −Cx)+ν(x −1) : x ≥ 0{ } : λ ≥ 0,µ ≥ 0,ν ≥ 0{ } =max min (c − λA−µC +ν)x +bλ +dµ −ν1: x ≥ 0{ } : λ ≥ 0,µ ≥ 0,ν ≥ 0{ } =W

Dim. (segue)

L(λ * ) ≥ ...≥


Se (c − λA−µC +ν) < 0⇒ per x = +∞ si ha

min (c − λA−µC +ν)x +bλ +dµ −ν1: x ≥ 0{ } = −∞Se (c − λA−µC +ν) ≥ 0⇒ la soluzione ottima è x = 0 e si ha

min (c − λA−µC +ν)x +bλ +dµ −ν1: x ≥ 0{ } = bλ +dµ −ν1

Dim. (segue)

L(λ * ) ≥ ...≥


Se (c − λA−µC +ν) < 0⇒ per x = +∞ si ha

min (c − λA−µC +ν)x +bλ +dµ −ν1: x ≥ 0{ } = −∞Se (c − λA−µC +ν) ≥ 0⇒ la soluzione ottima è x = 0 e si ha


per cui ha senso considerare solo vettori (c − λA−µC +ν) ≥ 0 in corrispondenza dei quali si ha x = 0


Dim. (segue)

L(λ * ) ≥ ...≥


W =max bλ +dµ −ν1: c − λA−µC +ν ≥ 0,λ ≥ 0,µ ≥ 0,ν ≥ 0{ }

per cui ha senso considerare solo vettori (c − λA−µC +ν) ≥ 0 in corrispondenza dei quali si ha x = 0


Dim. (segue) 1La penultima uguaglianza discende dalla teoria della dualità.

☐

W =max bλ +dµ −ν1: c − λA−µC +ν ≥ 0,λ ≥ 0,µ ≥ 0,ν ≥ 0{ } =1

min cx : Ax ≥ b,Cx ≥ d,0 ≤ x ≤1{ } = Z *PL

Calcolo del Duale Lagrangiano L* Metodo del subgradiente

Il calcolo del duale lagrangiano L*=L(λ*) può essere effettuato attraverso il metodo del subgradiente che genera una successione di punti del tipo:

λk = λk-1 + θk dk tale che limk->+∞ L(λk)= L*


Nel metodo del subgradiente si ha:

λk = λk-1 + θk dk tale che limk->+∞ L(λk)= L*

dove

θ k =α k UB −L(λk−1)|| sk ||

è il passo

dk = sk

|| sk || è una direzione di salita


θ k =α k UB −L(λk−1)|| sk ||

è il passo

dk = sk

|| sk || è una direzione di salita

sk è un subgradiente di L in λk−1

0 <α k ≤ 2


Può essere dimostrato che un subgradiente sk di L in λk−1 è dato da:

sk = b − Axk dove

xk è la soluzione del Problema Lagrangiano L(λk−1)

L(λk−1)

Un’applicazione al problema R||Cmax

min Cmax

tale che

Ci = pij xijj=1

n

∑ ≤Cmax i =1,...,m (1)

xiji=1

m

∑ =1 j =1,...,n (2)

xij ∈ 0,1{ } (3)

L(λ) =min Cmax + λii=1

m

∑ ( pijj=1

n

∑ xij −Cmax)

tale che

xiji=1

m

∑ =1 j =1,...,n (2)

xij ∈ 0,1{ } (3)

Rilassamento Lagrangiano dei vincoli (1)

Rilassamento Lagrangiano dei vincoli (1)

L1(λ) + L2(λ) =

min (1− λii=1

m

∑ )Cmax : Cmax ≥ 0⎧⎨⎪

⎩⎪

⎫⎬⎪

⎭⎪ +

min λi pijj=1

n

∑ xij : xiji=1

m

∑ =1 ∀j, xij ∈ 0,1{ } ∀i, ji=1

m

∑⎧⎨⎪

⎩⎪

⎫⎬⎪

⎭⎪

=min (1− λii=1

m

∑ )Cmax + λi pijj=1

n

∑ xij : (2), (3)i=1

m

∑⎧⎨⎪

⎩⎪

⎫⎬⎪

⎭⎪=

L(λ) =min Cmax + λii=1

m

∑ ( pijj=1

n

∑ xij −Cmax) : (2), (3)⎧⎨⎪

⎩⎪

⎫⎬⎪

⎭⎪=

Soluzione del problema L(λ)

1.  Se Σiλi>1 ⇒ Cmax = +∞ ⇒ L1(λ) = -∞ ⇒ L(λ) = -∞ non significativo!

2. Se Σiλi ≤ 1 ⇒ L1(λ) = 0 ⇒ L(λ) = L2(λ)

Si possono distinguere i due seguenti casi:

Nel calcolo di L( λ* ) posso considerare solo il caso 2.

2. Se Σiλi ≤ 1

L λ( ) = L2 λ( ) =

min λi pijj=1

n

∑ xij i=1

m

∑

xiji=1

m

∑ =1 ∀j =1,...,n

xij ∈ 0,1{ } ∀i =1,...m; j =1,...,n


Il problema lagrangiano diventa quindi:

L λ( ) = L2 λ( ) =min λi piji=1

m

∑ xijj=1

n

∑"#$

%$

&'$

($

xiji=1

m

∑ =1 j =1,...,n

xij ∈ 0,1{ }

{ } mix

x

xp

ik

m

iik

ik

m

iiki

,...,1 1,0

1

min

1

1

=∈

=

⎭⎬⎫

⎩⎨⎧

∑

∑

=

=

λ

L(λ) puo’ essere decomposto in n sottoproblemi, uno per ogni lavoro. Per il lavoro k si ha:


{ } nix

x

xp

ik

m

iik

ik

m

iiki

,...,1 1,0

1

min

1

1

=∈

=

⎭⎬⎫

⎩⎨⎧

∑

∑

=

=

λ

L(λ) può essere decomposto in n sottoproblemi-lavori. Per il lavoro k si ha:


La soluzione del sottoproblema associato al lavoro k consiste nell’assegnare k alla macchina i per cui è minimo il prodotto λi pik.

{ } nix

x

xp

ik

m

iik

ik

m

iiki

,...,1 1,0

1

min

1

1

=∈

=

⎭⎬⎫

⎩⎨⎧

∑

∑

=

=

λ

L(λ) può essere decomposto in n sottoproblemi-lavori. Per il lavoro k si ha:


Sia λ : 0 < Σiλi < 1, e sia λ’:

λ 'i = λi / λi

i=1

m

∑ i =1,...,m ⇒ λ 'i

i=1

m

∑ =1

Siano X e X ' i corrispondenti assegnamenti in L(λ) e

L(λ'), si ha:

•  X =X '

•  λ’ > λ ⇒ L(λ') > L(λ)

Osservazione 1: è sufficiente considerare solo moltiplicatori Lagrangiani tali che Σiλi = 1

Infatti:


Osservazione 2: ∀ λ vettore, λi ≥ 0 ∀ i, si ha: •  L(λ) è un Lower Bound della soluzione ottima.


Osservazione 2: ∀ λ vettore, λi ≥ 0 ∀ i, si ha: •  L(λ) è un Lower Bound della soluzione ottima.

•  Ogni soluzione ammissibile del problema Lagrangiano è un assegnamento dei lavori alle macchine, ed è quindi anche ammissibile per il problema originale R||Cmax , fornisce, cioé un Upper Bound della soluzione ottima di R||Cmax


Metodo del subgradiente Per una fissata iterazione it e vettore λit-1, sia xit la soluzione del problema Lagrangiano L(λit-1) Sia Cmax

it il massimo tempo di completamento relativo a xit Nota: in realtà, in L(λ), Cmax può assumere qualsiasi valore maggiore o uguale 0

Metodo del subgradiente Un subgradiente sit all’iterazione it è: Il nuovo vettore dei moltiplicatori è:

λiit =max 0,λi

it−1+θ itsiit

sit

⎧⎨⎪

⎩⎪

⎫⎬⎪

⎭⎪, θ it = α

Cmaxit -L(λ it−1)sit

, 0 <α ≤ 2

i =1,...,m

siit = pij xij

it

j=1

n

∑ −Cmaxit =Ci

it −Cmaxit i =1,...,m

Esercizio

Nome.........................................

Cognome......................................

Prova scritta di Metodi di Ottimizzazione (Mod. Modelli per la

pianificazione delle attivita) del 28/6/2012

1

Si consideri la seguente istanza del problema 1|rj|Lmax

Table 1: dati dell’istanza

j pj rj dj1 5 0 6

2 4 1 5

3 6 4 15

4 3 11 14

Si determini la soluzione ottima applicando un opportuno algoritmo.

2

Si consideri la seguente istanza di R||Cmax con 3 macchine, M1, M2, ed M3, e 5 lavori,

j1, j2, j3, j4, j5. I tempi di processamento, pij, di ogni job j su ogni macchina i sono

riportati nella tabella seguente.

Table 2: Tempi di processamento pij

pij j1 j2 j3 j4 j5M1 40 30 25 10 30M2 15 40 50 30 10M3 50 20 45 30 20

Una formulazione del problema e la seguente

minD5P

j=1pijxij D for i = 1, . . . , 3

3Pi=1

xij = 1 for j = 1, . . . , 5

xij 2 {0, 1} for j = 1, . . . , 5 and i = 1, . . . , 3

1

Esercizio (segue)

Dove xij e pari ad 1 se il lavoro j e assegnato alla macchina i e 0 altrimenti. Si scriva

per esteso la formulazione del problema utilizzando i dati di Tabella 2. Si e↵ettui il

rilassamento lagrangiano dei vincoli

5Pj=1

pijxij D , per i = 1, . . . , 3. Si calcoli il valore

della funzione lagrangiana L(�) in corrispondenza del vettore dei moltiplicatori �, con

componenti

�1 = 1/7, �2 = 4/7 e �3 = 2/7.

2

λ1 = 3/7 λ2 = 2/7 λ3 = 2/7

Esercizio (segue)

Soluzione del problema lagrangiano: Il lavoro j è assegnato alla macchina i per cui è minimo il prodotto λi pij

Nome.........................................

Cognome......................................



1



j pj rj dj1 5 0 6

2 4 1 5

3 6 4 15

4 3 11 14


2





pij j1 j2 j3 j4 j5M1 40 30 25 10 30M2 15 40 50 30 10M3 50 20 45 30 20


minD5P

j=1pijxij D for i = 1, . . . , 3

3Pi=1

xij = 1 for j = 1, . . . , 5

xij 2 {0, 1} for j = 1, . . . , 5 and i = 1, . . . , 3

1


m

∑ xijj=1

n

∑"#$

%$

&'$

($

xiji=1

m

∑ =1 j =1,...,n

xij ∈ 0,1{ }

λ1 = 3/7 λ2 = 2/7 λ3 = 2/7

Esercizio (segue)

Soluzione del problema lagrangiano: Il lavoro j è assegnato alla macchina i per cui è minimo il prodotto λi pij j1 è assegnato alla macchina 2 j2 è assegnato alla macchina 3 j3 è assegnato alla macchina 1 j4 è assegnato alla macchina 1 j5 è assegnato alla macchina 2 L(λ)=(3(25+10)+2(15+10)+2*20)/7=195/7=27,85 e quindi: LB=28

Nome.........................................

Cognome......................................



1



j pj rj dj1 5 0 6

2 4 1 5

3 6 4 15

4 3 11 14


2





pij j1 j2 j3 j4 j5M1 40 30 25 10 30M2 15 40 50 30 10M3 50 20 45 30 20


minD5P

j=1pijxij D for i = 1, . . . , 3

3Pi=1

xij = 1 for j = 1, . . . , 5

xij 2 {0, 1} for j = 1, . . . , 5 and i = 1, . . . , 3

1


m

∑ xijj=1

n

∑"#$

%$

&'$

($

xiji=1

m

∑ =1 j =1,...,n

xij ∈ 0,1{ }

λ1 = 3/7 λ2 = 2/7 λ3 = 2/7

Esercizio (segue)

La soluzione del problema lagrangiano è un assegnamento ammissibile per R| |Cmax. j1 è assegnato alla macchina 2 j2 è assegnato alla macchina 3 j3 è assegnato alla macchina 1 j4 è assegnato alla macchina 1 j5 è assegnato alla macchina 2 Si ha quindi:

Nome.........................................

Cognome......................................



1



j pj rj dj1 5 0 6

2 4 1 5

3 6 4 15

4 3 11 14


2





pij j1 j2 j3 j4 j5M1 40 30 25 10 30M2 15 40 50 30 10M3 50 20 45 30 20


minD5P

j=1pijxij D for i = 1, . . . , 3

3Pi=1

xij = 1 for j = 1, . . . , 5

xij 2 {0, 1} for j = 1, . . . , 5 and i = 1, . . . , 3

1

Cmax =C1 = p13 + p14 = 35

λ1 = 3/7 λ2 = 2/7 λ3 = 2/7

Esercizio (segue)

j1 è assegnato alla macchina 2 j2 è assegnato alla macchina 3 j3 è assegnato alla macchina 1 j4 è assegnato alla macchina 1 j5 è assegnato alla macchina 2 Subgradiente s:

Nome.........................................

Cognome......................................



1



j pj rj dj1 5 0 6

2 4 1 5

3 6 4 15

4 3 11 14


2





pij j1 j2 j3 j4 j5M1 40 30 25 10 30M2 15 40 50 30 10M3 50 20 45 30 20


minD5P

j=1pijxij D for i = 1, . . . , 3

3Pi=1

xij = 1 for j = 1, . . . , 5

xij 2 {0, 1} for j = 1, . . . , 5 and i = 1, . . . , 3

1

s1it = p1 j x1 j

it

j=1

5

∑ −Cmaxit =C1

it −Cmaxit = 35−35 = 0

s2it = p2 j x2 j

it

j=1

5

∑ −Cmaxit =C2

it −Cmaxit = 25−35 = −10

s3it = p3 j x3 j

it

j=1

5

∑ −Cmaxit =C3

it −Cmaxit = 20−35 =-15

λ1 = 3/7 λ2 = 2/7 λ3 = 2/7

Esercizio (segue)

Quanto vale la soluzione ottima del problema originale?

min Cmax subject to 40 x0,0 + 30 x0,1 + 25 x0,2 + 10 x0,3 + 30 x0,4 - Cmax <= 0 15 x1,0 + 40 x1,1 + 50 x1,2 + 30 x1,3 + 10 x1,4 - Cmax <= 0 50 x2,0 + 20 x2,1 + 45 x2,2 + 30 x2,3 + 20 x2,4 - Cmax <= 0 x0,0 + x1,0 + x2,0 =1 x0,1 + x1,1 + x2,1 =1 x0,2 + x1,2 + x2,2 =1 x0,3 + x1,3 + x2,3 =1 x0,4 + x1,4 + x2,4 =1 x0,5 + x1,5 + x2,5 =1 integers x0,0 x0,1 x0,2 x0,3 x0,4 x1,0 x1,1 x1,2 x1,3 x1,4 x2,0 x2,1 x2,2 x2,3 end

Nome.........................................

Cognome......................................



1



j pj rj dj1 5 0 6

2 4 1 5

3 6 4 15

4 3 11 14


2





pij j1 j2 j3 j4 j5M1 40 30 25 10 30M2 15 40 50 30 10M3 50 20 45 30 20


minD5P

j=1pijxij D for i = 1, . . . , 3

3Pi=1

xij = 1 for j = 1, . . . , 5

xij 2 {0, 1} for j = 1, . . . , 5 and i = 1, . . . , 3

1

Esercizio (segue)

Quanto vale la soluzione ottima del problema originale?

Nome.........................................

Cognome......................................



1



j pj rj dj1 5 0 6

2 4 1 5

3 6 4 15

4 3 11 14


2





pij j1 j2 j3 j4 j5M1 40 30 25 10 30M2 15 40 50 30 10M3 50 20 45 30 20


minD5P

j=1pijxij D for i = 1, . . . , 3

3Pi=1

xij = 1 for j = 1, . . . , 5

xij 2 {0, 1} for j = 1, . . . , 5 and i = 1, . . . , 3

1

Nodes Cuts/ Node Left Objective IInf Best Integer Best Bound ItCnt Gap * 0+ 0 165.0000 25.0000 7 84.85%* 0+ 0 135.0000 25.0000 7 81.48% 0 0 28.5135 4 135.0000 28.5135 7 78.88%* 0+ 0 35.0000 28.5135 7 18.53% 0 0 cutoff 35.0000 28.5135 7 18.53%Elapsed time = 0.05 sec. (0.15 ticks, tree = 0.00 MB, solutions = 3) Root node processing (before b&c): Real time = 0.03 sec. (0.09 ticks)Parallel b&c, 4 threads: Real time = 0.03 sec. (0.01 ticks) Sync time (average) = 0.00 sec. Wait time (average) = 0.00 sec.

MIP - Integer optimal solution: Objective = 3.5000000000e+01 Solution time = 0.08 sec. Iterations = 7 Nodes = 0

Esercizio (segue)

Quanto vale la soluzione del Rilassamento Lineare?

min Cmax subject to 40 x0,0 + 30 x0,1 + 25 x0,2 + 10 x0,3 + 30 x0,4 - Cmax <= 0 15 x1,0 + 40 x1,1 + 50 x1,2 + 30 x1,3 + 10 x1,4 - Cmax <= 0 50 x2,0 + 20 x2,1 + 45 x2,2 + 30 x2,3 + 20 x2,4 - Cmax <= 0 x0,0 + x1,0 + x2,0 =1 x0,1 + x1,1 + x2,1 =1 x0,2 + x1,2 + x2,2 =1 x0,3 + x1,3 + x2,3 =1 x0,4 + x1,4 + x2,4 =1 x0,5 + x1,5 + x2,5 =1 end

Cmax= 28,51

Nome.........................................

Cognome......................................



1



j pj rj dj1 5 0 6

2 4 1 5

3 6 4 15

4 3 11 14


2





pij j1 j2 j3 j4 j5M1 40 30 25 10 30M2 15 40 50 30 10M3 50 20 45 30 20


minD5P

j=1pijxij D for i = 1, . . . , 3

3Pi=1

xij = 1 for j = 1, . . . , 5

xij 2 {0, 1} for j = 1, . . . , 5 and i = 1, . . . , 3

1

Macchine parallele - dii.unisi.itdetti/Lucidi_mac_par.pdf · Descrizione del problema n lavori...

Documents

Transcript of Macchine parallele - dii.unisi.itdetti/Lucidi_mac_par.pdf · Descrizione del problema n lavori...