Lavori con precedenza: algoritmo di Lawler per minimizzare la massima penalità

Sequenziamento delle operazioni con precedenze

magazzino con movimentazione interna

Ci possono essere precedenze fra i lavori da compiere rappresentate da un grafo, anche non connesso

J1 J2 J3

J6

J5

J4

Algoritmo di Lawler (1973)

min max* i (ci) S i=1,…,n

i funzione non decrescente

* misura regolare: non decresce con ci

i(ci)

ci

ch

h (ch)tardiness

lateness

k (ck)

ck

max

Ti := Max (0, ci - di) Ti: 0

di ci

Ti: “tardiness”, fuori tempo( Li: “lateness”, ritardo chenegativo diventa anticipo )

k: k () = min i () Ji V

= i pi1

n

S ottima: Jk è ultimo in S

V: insieme dei lavori senza successorinel grafo delle precedenze

i(ci)ci

ch

h (ch)

tardinesslateness

k (ck)

ck

max

k ()h ()i()

k: k () = min i () Ji V

Dim: S ottima: Jk è ultimo in S

S’ :c'k

S : cl

Jl Jk

Jk JlSia S’ ottima

cA

JA

c’B

JB

cB

JB

JA

ccii c'c'i i i i k k

S’ ottimaS’ ottima

ii (c(cii)) i i (c'(c'ii) ) i i k k

k k (c(ckk) = ) = k k (() ) l l (() = ) = l l

(c’(c’ll))

max max i i (c(cii) ) max max i i

(c’(c’ii)) i=1,…,n i=1,…,n i=1,…,n i=1,…,n

PASSIPASSI DELL’ALGORITMODELL’ALGORITMO

1) k := n G: = { };

1

n

Grafo delleprecedenze

n := i pi

2) V= { }; Lavori senzasuccessori in G

i(k): i(k) () = min i () J i V

)k:= k - pi(k); G:= G{ nodo Ji(k)};

k := k -1

4) Passo 2

k S = { Ji(1), Ji(2), ... Ji(n)}

k 1

Lavori:Lavori: JJ11 JJ22 JJ33 JJ44 JJ55 JJ66

Tempi Tempi ppii : : 22 33 44 33 22 1 1

Cons. dCons. di i :: 33 66 99 77 1111 77

J1 J2 J3

J6

J5

J4

i (ci) = ci - di

lateness

Lavori: J1 J2 J3 J4 J5 J6

Tempi pi : 2 3 4 3 2 1

Cons. di : 3 6 9 7 11 7

J1 J2 J3

J6

J5

J4

n = 6

i (ci) = ci - di

Lavori: J1 J2 J3 J4 J5 J6

Tempi pi : 2 3 4 3 2 1

Cons. di : 3 6 9 7 11 7

J1 J2 J3

J6

J5

J4

Lavori Ji: J1 J2 J3 J4 J5 J6

i (n) : * * 6 * 4 8

n = 6

15

i(n)=5

i (ci) = ci - di

Lavori: J1 J2 J3 J4 J5 J6

Tempi pi : 2 3 4 3 2 1

Cons. di : 3 6 9 7 11 7

J1 J2 J3

J6

J5

J4

Lavori Ji: J1 J2 J3 J4 J5 J6

i (n) : * * 6 * 4 8i (5) : * * 4 * 6

n = 6

1513

i(n)=5

i(5)=3

i (ci) = ci - di

Lavori: J1 J2 J3 J4 J5 J6

Tempi pi : 2 3 4 3 2 1

Cons. di : 3 6 9 7 11 7

J1 J2 J3

J6

J5

J4

Lavori Ji: J1 J2 J3 J4 J5 J6

i (n) : * * 6 * 4 8i (5) : * * 4 * 6i (4) : * 3 * 2

n = 6

15139

i(n)=5

i(5)=3

i(4)=6

i (ci) = ci - di

Lavori: J1 J2 J3 J4 J5 J6

Tempi pi : 2 3 4 3 2 1

Cons. di : 3 6 9 7 11 7

J1 J2 J3

J6

J5

J4

Lavori Ji: J1 J2 J3 J4 J5 J6

i (n) : * * 6 * 4 8i (5) : * * 4 * 6i (4) : * 3 * 2i (3) : * 2 1

n = 6

151398

i(n)=5

i(5)=3

i(4)=6

i(3)=4

i (ci) = ci - di

Lavori: J1 J2 J3 J4 J5 J6

Tempi pi : 2 3 4 3 2 1

Cons. di : 3 6 9 7 11 7

J1 J2 J3

J6

J5

J4

Lavori Ji: J1 J2 J3 J4 J5 J6

i (n) : * * 6 * 4 8i (5) : * * 4 * 6i (4) : * 3 * 2i (3) : * 2 1i (2) : * -1i (1) : -1

Sequenza ottima: Ji(1) Ji(2) ...Ji(k) ... Ji(n-1) Ji(n) n = 6

15139852

i(n)=5

i(5)=3

i(4)=6

i(3)=4

i(2)=2

i(1)=1

i (ci) = ci - di

Algoritmo di Smith modificato: sequenze efficienti rispetto al

completamento medio e il ritardo massimo

Algoritmo di Smith modificato Efficiente rispetto F e Tmax

S° : Efficiente: S’ :F’ F° T’max < T°max

F’ < F° T’max T°max

F

non c’è sequenza(inclusa frontiera)

non c’è efficienza(inclusa frontiera)

F°

T°maxTmax

Tmax := maxi Ti1

n

1980

Algoritmo di Smith (1956) min F S : Tmax = 0

Ses le sequenze EDD danno Tmax

cm := rpr1

n

soluzione [S EDD Lmax ]

ri = 0 tutti i pezzi disponibili al tempo iniziale

F = 1n i (ci - ri) = c flusso medio

S’ :c’k cm dk dlpl < pk

dk , dl cm

S : cl cm dk dl

Jl Jk cl< c’k

nF’ = nF - cl + c’k > nF F’ non è ottimo

Jk Jl

una sequenza è minima solo se l’ultimo lavoro è (uno) di lunghezza massima, tra quelli che possono (senza ritardo) essere sequenziati in ultimo :

F = c = i ci1

n1n

n

S’ :c’k dk dl

S : cl dk dl

Jl Jk

= - cl + c’k >

F’ non è ottimo

Jk Jl

la sequenza dei rimanenti n-1 è minima solo se l’ultimo lavoro è (uno) di lunghezza massima, tra quelli che possono (senza ritardo) essere sequenziati al posto n-1 :

e così via a ritroso

i ci1

n-1

pl < pk

dk , dl cm

cl< c’k

i c’i1

n-1

i c’i1

n-1 i ci1

n-1 i ci1

n-1

1) k := n U: = { J1 ... Jn }; n := r pr1

n

Passi dell’algoritmo di Smith (1956)Passi dell’algoritmo di Smith (1956)

2) i(k): Ji(k) U

(i) di(k) (per ipotesi)

(ii) Jl U dl

pl pi(k)

Il passo 2 pone al posto k-esimo il lavorodi peso massimo tra quelli che ci possonostare con il vincolo Tmax =0

il vincolo Tmax =0 equivale a Lmax 0

2) i(k): Ji(k) U

(i) di(k) (per ipotesi)

(ii) Jl U dl

pl pi(k)

)k:= k - pi(k); U:= U{ Ji(k)}; k := k -1

4) Passo 2

k S = { Ji(1), Ji(2), ... Ji(n)}

k 1

Algoritmo di Smith modificato:Algoritmo di Smith modificato:Efficiente rispetto Efficiente rispetto FF e L e Lmaxmax

Tmax della EDD

i := di +

dk dl k l

Modifica dell’algoritmo

Dati: una sequenza EDD dei lavori: { J1 ... Jn }

pl < pi(k)

pl = pi(k) => l

i(k)

NO!

=pl pi(k)<i(k) l

2’) i(k): Ji(k) U (i) i(k) (per ipotesi)

(ii) Jl U l

2) i(k): Ji(k) U

(i) di(k) (per ipotesi)

(ii) Jl U dl

pl pi(k)diviene

La condizione modificata dà:

° = min Lmax F F°

F°:= min F* Lmax

È il risultato dell’algoritmomodificato

Con°:= Lmax per la S ottima

* Attenzione: Lmax può essere negativo

l’algoritmo dà:

F° = min F Tmax T°max

°= T°maxmin Tmax

F F°

Se ° 0

Con° = min Lmax F F°

F°= min F Tmax T°max

T°max = min Tmax

F F°

Efficienza rispetto F e Tmax

non c’è sequenza*

non c’è efficienza*

F

F°

T°max Tmax

* frontiera compresa

S: S° è Efficiente

F F° Tmax < T°max

F < F° Tmax T°max

L’algoritmo dà una sequenza S efficiente rispetto a F e Tmax

Att. : Se i(k) non è unico al passo 2’ ogni scelta diversa porterà a sequenze efficienti diverse

Efficienza rispetto F e Tmax

Esempio:curva diefficienza

Lavori: J1 J2 J3 J4

Tempi pi : 2 4 3 1

Cons. di : 1 2 4 6

Passo 1: =

Passo 2: Smith mod. dà: J4 J1 J3 J2

i pi = 101

nPunto 1

F° = 5 T°max = 8

Efficienza rispetto F e Tmax

Se ci sono più SPT l’alg. da’ quella con Lm minore. Es.:

Lavori: J1 J2 J3 J4

Tempi pi : 2 4 4 1

Cons. di : 1 2 4 6

Passo 1: =

Passo 2: Smith mod. dà: J4 J1 J2 J3

i pi = 101

nPunto 1

F° = 5 T°max = 6

L: 2 5 6 -5

L’altra SPT avrebbe dato 9

Efficienza rispetto F e Tmax

Esempio:curva diefficienza

Lavori: J1 J2 J3 J4

Tempi pi : 2 4 3 1

Cons. di : 1 2 4 6

Passo 1: =8 -1= 7 Passo 2: Smith mod. dà: J4 J1 J2 J3

Punto 2

F° = 5.25 T°max = 6

Passo 1: =6 -1= 5 Passo 2: Smith mod. dà: J1 J2 J3 J4

Punto 3

F° = 6.75 T°max = 5

Efficienza rispetto F e Tmax

Esempio:curva diefficienza

Lavori: J1 J2 J3 J4

Tempi pi : 2 4 3 1

Cons. di : 1 2 4 6

La seq. è una (la unica in questo caso) EDD quindi non si può abbassare T°max

Passo 1: =5 -1= 4 Passo 2: non ci sono sequenze con T°max 4 perché min Lm = 5

Infatti:

Efficienza rispetto F e Tmax

Lavori: J1 J2 J3 J4

Tempi pi : 2 4 3 1

Cons. di : 1 2 4 6

Esempio:curva diefficienza

Efficienza rispetto F e Tmax

Esempio: curva di efficienza: punti calcolati

F

F°= 5.25

T°max= 5 TmaxT°max = 8T°max = 6

F°= 5

non c’è efficienza

F°= 6.75

non c’è sequenza*

Efficienza rispetto F e Tmax

Esempio: curva di efficienza: punti calcolati

F

F°= 5.25

T°max= 5 TmaxT°max = 8T°max = 6

F°= 5

non c’è efficienza*

F°= 6.75

non c’è sequenza*

EDD:

min Lmax = 5 SPT:

min F = 5

Efficienza rispetto c ed Lm

Per come si sviluppa l’algoritmo chiamato Smith modificato è più corretto parlare di min Lm (che può anche risultare negativo) e più comodo usare c = nF

c

c = 21

L°m= 5 LmL°m = 8L°m = 6

c= 20

non c’è efficienza*

c = 27

non c’è sequenza*

EDD:

min Lm = 5 SPT:

min c = 20

Si noti che, mentre il punto con la Lm più a destra è senz’altro relativo a una SPT, quello più a sinistra ha la Lm di una EDD, ma può non essere relativo, come qui è, a una EDD.

Lavori: A B C D E F

Tempi p : 1 2 3 3 4 5

Cons. d : 18 15 11 13 11 7

Lavori: A B C D E FL18 : 0 3 7 5 7 11L14 : -4 -1 3 1 * 7L9 : -9 -6 -2 -4 * *Col vincolo LL 10, occorre calcolare i ritardi solo con c=18 perché la data 10, occorre calcolare i ritardi solo con c=18 perché la data

dovuta minore è 7, il che porta ad escludere F. Scelto E come il più lungo dei dovuta minore è 7, il che porta ad escludere F. Scelto E come il più lungo dei restanti, i ritardi con c=14 degli altri saranno tutti restanti, i ritardi con c=14 degli altri saranno tutti 10, quindi vanno ordinati 10, quindi vanno ordinati secondo la SPT che ha il minor Lsecondo la SPT che ha il minor Lmm, il che fa scegliere D e non C con c=9., il che fa scegliere D e non C con c=9.

Sequenza ottima: A B C D F E Min Lm = 7 Min c => L1010 c = = 5151

n = 6

1814 9

J(n):E

J(5):F

J(4):D

LL 1010

°c : : 11 33 66 99 1818 1414 c ==5151

cc(SPT => min (SPT => min LmLm)) :: 11 3 3 6 6 9 9 1313 1818LL(SPT => min (SPT => min LmLm) ) :: -17-17 -12-12 - 5- 5 - 4- 4 2 2 1111

c(SPT)= = 5050

minLminLmm = = 1111

Lavori: A B C D E F

Tempi p : 1 2 3 3 4 5

Cons. d : 18 15 11 13 11 7

Lavori: A B C D E FL18 : 0 3 7 5 7 11L15 : -3 0 4 * 4 8L11 : -7 -4 0 * * 4Col vincolo LL 6, occorre calcolare i ritardi solo con c=18 (attribuito a D) e con 6, occorre calcolare i ritardi solo con c=18 (attribuito a D) e con

c=15 (attribuito a E). I ritardi degli altri (A,B,C,F) saranno tutti c=15 (attribuito a E). I ritardi degli altri (A,B,C,F) saranno tutti 6, perché i 6, perché i completamenti completamenti cc diminuiscono. Quindi vanno ordinati secondo la SPT che ha il diminuiscono. Quindi vanno ordinati secondo la SPT che ha il minor Lminor Lmm, ma qui è unica: proprio A B C F , ma qui è unica: proprio A B C F

Sequenza ottima: A B C F E D Min Lm = 5 Min c => L66 c = 54 = 54

n = 6

1815 11

J(n):D

J(5):E

J(4):F

Otteniamo ora un altro punto di efficienza imponendo LOtteniamo ora un altro punto di efficienza imponendo L 66

°c : : 11 33 66 1818 1515 1111 c == 54 54

Lavori: A B C D E F

Tempi p : 1 2 3 3 4 5

Cons. d : 18 15 11 13 11 7

Lavori: A B C D E FL18 : 0 3 7 5 7 11L16 : -2 * 5 3 5 9L13 : -5 * 2 * 2 6L9 : -9 * -2 * * 2Col vincolo Col vincolo LL 4, si calcolano i ritardi con c=18 (attribuito a B), con c=16 4, si calcolano i ritardi con c=18 (attribuito a B), con c=16 (attribuito a D) , con c=13 (attribuito a E) , con c=9 (attribuito a F). I ritardi degli (attribuito a D) , con c=13 (attribuito a E) , con c=9 (attribuito a F). I ritardi degli altri (A e C) saranno tutti altri (A e C) saranno tutti 4, perché i completamenti c diminuiscono. Quindi 4, perché i completamenti c diminuiscono. Quindi vanno ordinati secondo la SPT che ha il minor Lvanno ordinati secondo la SPT che ha il minor Lmm, ma qui è unica: A C , ma qui è unica: A C

Sequenza ottima: A C F E D B Min Lm = 3 Min c => L44 c = 61 = 61

n = 6

1816 13 9

J(n):B

J(5):D

J(4):E

J(3):F

Otteniamo ora un altro punto di efficienza imponendo LOtteniamo ora un altro punto di efficienza imponendo L 44

°c : : 11 1818 44 1616 1313 99 c == 61 61

Lavori: A B C D E F

Tempi p : 1 2 3 3 4 5

Cons. d : 18 15 11 13 11 7

Lavori: A B C D E FL18 : 0(EDD!) 3 7 5 7 11L17 : * 2(EDD!) 6 4 6 10L15 : * * 4 2(EDD!) 4 8L12 : * * 1 * 1(EDD!) 5L8 : * * -3 * * 1(NO EDD!)

L3 : * * -8 * * *

Sequenza ottima: C F E D B ANon è una sequenza EDD, ma ha la stessa Lm!

18171512 8 3

J(n):A

J(5):B

J(4):D

J(3):E

J(2):F

J(1):C

LLmm 2 2

°c : : 1818 1717 33 1515 1212 88

c(EDD => min c) :18 17 8 15 12 5EDD: F C E D B AMin c Lm= 2

c(EDD=>minc)==75

c == 73 73 <75!<75!

Min Lm = 2c = 73 = 73

Efficienza rispetto c ed Lm per l’esempio sviluppato

Esistono due SPT°, entrambe con Lm=11, mentre min c con Lm=2 non è una EDD

c = 51

3 Lm117

c= 50

non c’è efficienza*

c = 54

SPT°

Quanto sopra conferma che, mentre il punto di efficienza con la Lm più a destra è senz’altro relativo a una SPT, quello più a sinistra ha la Lm di una EDD, ma può non essere relativo a una EDD.

c = 61

c = 73

52

c = 75

non c’è sequenza*

EDD => min c