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

Macchine parallele

LAVORI

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

M1 J1 J4

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

M1 J1 J4

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

M1 J1 J7

Soluzione LPT

J 1 2 3 4 5 6 7 8 9

pj 7 7 6 6 5 5 4 4 4

Soluzione Ottima

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 )

=43−13m

=43−112

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

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

∑⎧⎨⎪

⎩⎪

⎫⎬⎪

⎭⎪

Una formulazione di PL per Pm|prempt|Cmax

xiji=1

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

Vincoli Ogni lavoro deve essere completato

xiji=1

∑ ≤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

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

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

min Cmax

tale che

xiji=1

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

xiji=1

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

xijj=1

∑ ≤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

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

∑⎧⎨⎪

⎩⎪

⎫⎬⎪

⎭⎪

xiji=1

∑ =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

∑⎧⎨⎪

⎩⎪

⎫⎬⎪

⎭⎪

tale che

xiji=1

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

xij ∈ 0,1{ }

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

∑⎧⎨⎪

⎩⎪

⎫⎬⎪

⎭⎪

tale che

xiji=1

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

xij ∈ 0,1{ }

Funzione obiettivo non

lineare

min Cmax

tale che

Ci = pij xijj=1

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

xiji=1

∑ =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(λ*)

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*

θ 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

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

xiji=1

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

xij ∈ 0,1{ } (3)

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

∑ ( pijj=1

∑ xij −Cmax)

tale che

xiji=1

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

xij ∈ 0,1{ } (3)

Rilassamento Lagrangiano dei vincoli (1)

L1(λ) + L2(λ) =

min (1− λii=1

∑ )Cmax : Cmax ≥ 0⎧⎨⎪

⎩⎪

⎫⎬⎪

⎭⎪ +

min λi pijj=1

∑ xij : xiji=1

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

∑⎧⎨⎪

⎩⎪

⎫⎬⎪

⎭⎪

=min (1− λii=1

∑ )Cmax + λi pijj=1

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

∑⎧⎨⎪

⎩⎪

⎫⎬⎪

⎭⎪=

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

∑ ( pijj=1

∑ 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

∑ xij i=1

xiji=1

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

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

Il problema lagrangiano diventa quindi:

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

∑ xijj=1

∑"#$

xiji=1

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

xij ∈ 0,1{ }

{ } mix

,...,1 1,0

⎭⎬⎫

⎩⎨⎧

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

{ } nix

,...,1 1,0

⎭⎬⎫

⎩⎨⎧

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

,...,1 1,0

⎭⎬⎫

⎩⎨⎧

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

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.

•  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

⎧⎨⎪

⎩⎪

⎫⎬⎪

⎭⎪, θ it = α

Cmaxit -L(λ it−1)sit

, 0 <α ≤ 2

i =1,...,m

siit = pij xij

∑ −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

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.

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

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

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

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

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.

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

j pj rj dj1 5 0 6

2 4 1 5

3 6 4 15

4 3 11 14

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

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

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

∑ xijj=1

∑"#$

xiji=1

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

j pj rj dj1 5 0 6

2 4 1 5

3 6 4 15

4 3 11 14

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

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

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

∑ xijj=1

∑"#$

xiji=1

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

j pj rj dj1 5 0 6

2 4 1 5

3 6 4 15

4 3 11 14

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

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

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

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

j pj rj dj1 5 0 6

2 4 1 5

3 6 4 15

4 3 11 14

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

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

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

s1it = p1 j x1 j

∑ −Cmaxit =C1

it −Cmaxit = 35−35 = 0

s2it = p2 j x2 j

∑ −Cmaxit =C2

it −Cmaxit = 25−35 = −10

s3it = p3 j x3 j

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

j pj rj dj1 5 0 6

2 4 1 5

3 6 4 15

4 3 11 14

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

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

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

Esercizio (segue)

Quanto vale la soluzione ottima del problema originale?

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

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

j pj rj dj1 5 0 6

2 4 1 5

3 6 4 15

4 3 11 14

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

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

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

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

j pj rj dj1 5 0 6

2 4 1 5

3 6 4 15

4 3 11 14

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

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

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

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

Collegamenti alle macchine CNC - Assistenza Macchine Utensili · Collegamento Macchine Utensili EasyCAM realizza anche reti di collegamento per le macchine utensili. Solitamente si

Meccanica Applicata alle Macchine – Allievi Aerospazialinikemagic.altervista.org/download/Macchine/Temi_2002.pdf · Meccanica Applicata alle Macchine – Allievi Aerospaziali prof.

MACCHINE - IMPIANTI - MaquinasDePanaderia.commaquinasdepanaderia.com/wp-content/uploads/2015/04/SOTTORIVA... · MACCHINE - IMPIANTI - FORNI MACHINES - PLANTS - OVENS. Macchine, impianti

P.01.515-CB.M.13 Rev.14 Questionario anamestico … · p.01.515-cb.m.13 donazione di sangue da cordone ombelicale per uso non dedicato (unrelated) storia clinica della famiglia del

MANIPOLAZIONE E LAVORAZIONE CON INGREDIENTI ... - … · Gli ingredienti che contengono enzimi devono essere sempre manipolati e processati in modo da evitare la formazione di polvere

Macchine automatiche montaggio - solaut.it · MACCHINE MONTAGGIO AUTOMATICO MACCHINE AUTOMATICHE D’ASSEMBLAGGIO ED INCOLLAGGIO Solaut realizza macchine e linee automatizzate per

LL e macchine semplici sono macchine che non possono essere scomposte in macchine ancora più elementari SS ono le macchine che erano già disponibili.

Introduzione alle Macchine Operatrici (macchine a fluido) a... · Macchine Operatrici Nel presente modulo si vogliono fornire cenni circa le principali macchine operatrici impiegate

IONIZZATORE CON LUCEstc.dmc.it/istruzioni/I182915_PTS_SPA_ENG_RUM_CZO.pdf · user’s guide. Excluded from this warranty, damage due to a cause unrelated to the device. In particular,

Protezioni per macchine e impianti – Importanti Norme ... · Macchine per imballaggio Macchine utensili Sistemi robotici I diversi tipi di macchine appartenenti alla categoria a

1 STRUTTURA E CINEMATICA DELLE MACCHINE Macchine e …web.inge.unige.it/DidRes/MApMac2/1_struttura_cinematica1112.pdf · Meccanica delle macchine i componenti delle macchine possono

L e macchine semplici sono macchine che non possono essere scomposte in macchine ancora più elementari S ono le macchine che erano già disponibili nellantichità

Capitolo M3 - MACCHINE ELETTRICHE. - melfiweb.it - Macchine Asincorone.pdf · Capitolo M3 - MACCHINE ELETTRICHE. Le macchine elettriche sono dispositivi di conversione elettromeccanica

Superfici macchine di lavorazione per la filiera …...le macchine tenute e/o condotte a mano, le macchine portatili per il fissaggio e altre macchine ad impatto, nonché le macchine

Macchine Usate, Macchine Installate. Cosa Fare

I PIÙ INNOVATIVI TRITURATORI PRIMARI...pneumatici e molto altro possono essere triturati e processati senza problemi. Esempio dei nostri alberi SERVIZI E RICAMBI Gli intervalli di

macchine elettriche

Macchine Elettrostatiche

Sicurezza Macchine

Macchine Asincrone