Lavori con precedenza: algoritmo di Lawler per minimizzare la massima penalità.
-
Upload
maso-castellano -
Category
Documents
-
view
252 -
download
1
Transcript of Lavori con precedenza: algoritmo di Lawler per minimizzare la massima penalità.
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