Modelli dei Sistemi di Produzione
Modelli e Algoritmi della Logistica

2010-11
Project Scheduling: Analisi Temporale

CARLO MANNINO

Sapienza Università di Roma Dipartimento di Informatica e Sistemistica

1

Definizioni di base
L’analisi temporale serve a rispondere a una serie di quesiti quali: • in quanto tempo il progetto (o una sua parte) terminerà? • quando può (o deve) cominciare una determinata attività? • quanto può essere ritardato l’inizio di un’attività senza rallentare l’intero progetto? ASSUNZIONI DEL MODELLO • • Risorse: nessun vincolo Attività non interrompibili (no preemption)

OBIETTIVI: calcolare il minimo tempo di completamento del progetto (makespan)  identificare le attività critiche e altre grandezze d’interesse

2

Piani delle attività
• L’input è il grafo delle precedenze generalizzate H = (V, F) con insieme di attività V e insieme di archi F (precedenze generalizzate), unitamente al vettore delle durate delle attività d R+|V| • Principale prodotto dell’ottimizzazione è il piano temporale delle attività (schedule) che soddisfi tutti i vincoli di precedenza e ottimizzi una specifica funzione obiettivo. • Il piano può essere rappresentato associando a ogni attività i V una variabile

reale si che indica l’istante iniziale dell’attività.
• Il piano è quindi un vettore s R|V|

• L’obiettivo è minimizzare la durata dell’intero progetto, ovvero la quantità:

sn – s1 (inizio attività fine progetto – inizio attività inizio progetto)
3

Problema del makespan
Def. Makespan: durata minima del progetto

Problema del calcolo del makespan: trovare un piano s che soddisfi tutti i vincoli di precedenza e minimizzi la durata del progetto sn – s1 .

• Questo problema può essere formulato come problema di PL, costruito a partire dal grafo delle precedenze generalizzate.

• Introduciamo anche la variabile fi che rappresenta l’istante finale dell’attività i
• Valendo l’ipotesi di no-preemption si ha fi = si + di per ogni i V.
4

V.

Un modello di PL
• Il grafo delle precedenze generalizzate è la base di partenza per costruire un modello di Programmazione lineare • Le variabili del modello sono associate ai nodi del grafo • I vincoli del modello sono associati agli archi del grafo • Le relazioni di precedenza sono tradotte in vincoli lineari sulle variabili s e f. • Essendo fi = si + di per ogni i V, la variabile f può essere eliminata

• Obiettivo: rappresentare i vincoli temporali come vincoli lineari della forma Ms ≥ l, dove l è il vettore dei termini noti e M la matrice dei vincoli. • I vincoli hanno tutti forma sj - si

lij corrispondenti alla relazione SSijmin(lij)
5

• I coefficienti lij possono assumere valori positivi, negativi o nulli.

Determinazione vincoli I
1. Relazione FINISH/START FSijmin , FSijmax a. j deve cominciare almeno FSijmin istanti dopo che i finisce:

sj

fi + FSijmin

sj - si

di + FSijmin si - sj - di - FSijmax

b. j deve cominciare al massimo FSijmax istanti dopo che i finisce

sj ≤ fi + FSijmax
2. Relazione START/START SSijmin , SSijmax

a. j deve cominciare almeno SSijmin istanti dopo che i è cominciata:

sj

si + SSijmin

sj - si

SSijmin - SSijmax

b. j deve cominciare al massimo SSijmax istanti dopo che i è cominciata

sj ≤ si + SSijmax

si - sj

6

Determinazione vincoli II
3. Relazione START/FINISH SFijmin , SFijmax a. j deve finire almeno SFijmin istanti dopo che i è cominciata:

fj

si + SFijmin

sj - si

SFijmin - dj dj - SFijmax

b. j deve finire al massimo SFijmax istanti dopo che i è cominciata

fj ≤ si + SFijmax

si - sj

4. Relazione FINISH/FINISH FFijmin , FFijmax
a. j deve finire almeno FFijmin istanti dopo che i è finita:

fj

fi + FFijmin

sj - si

di - dj + FFijmin

b. j deve finire al massimo FFijmax istanti dopo che i è finita

fj ≤ fi + FFijmax

si - sj

dj- di - FFijmax

7

Dal grafo precedenze a quello dei vincoli
• I vincoli di precedenza definiscono il poliedro dei piani ammissimibili • Al poliedro dei piani ammissibili è possibile associare un grafo orientato: il grafo dei vincoli. • Le proprietà del grafo dei vincoli permettono di studiare il poliedro dei piani ammissibili e quindi la struttura delle soluzioni.
Grafo delle precedenze

Poliedro dei piani ammissibili

Gafo dei vincoli

8

Poliedro dei piani ammissibili e grafo dei vincoli
Obiettivo: definire il poliedro {s R|V|: Ms ≥ l} dei piani ammissibili Le precedenze si traducono in vincoli asssociati a coppie ordinate di attività del tipo

sv - su (1) sv - su

luv

uv

A

(Vincoli di precedenza)

Se esistono due vincoli distinti sulla stessa coppia (ordinata) uv di variabili

luv , (2) sv - su

l’uv

con l’uv ≤ luv , il vincolo (2) può essere eliminato perché dominato.

La matrice M ha esattamente un +1 e un -1 in ogni riga (tutti gli altri elementi sono nulli)
Attività = Nodi V, vincoli di precedenza = Archi A Temini noti: luv peso dell’arco uv

M è la matrice d’incidenza archinodi di un grafo orientato, semplice: grafo dei vincoli G(V,A) )

luv A u v
9

Il grafo dei vincoli
Costruzione del grafo dei vincoli a partire dal grafo delle precedenze generalizzate:

min FSij

sj - si j di + FSijmin i di

min FSij j

i

max FSij

s i - sj j - di - FSijmax di max FSij j

i

i

SS i min ij

j

sj - si

SSijmin i min SSij

j

max SSij

s i - sj j -SSijmax i max SSij j

10

i

Il grafo dei vincoli
SFijmin
i

sj - si j - dj + SFijmin i dj

SFijmin

j

SFijmax i si - sj j dj - SFijmax dj SFijmax

j

i

FF i min ij

sj - si j di - dj + FFij

min

di d j

FFijmin

j i d j di FFijmax

FF i max ij

si - sj j dj - di - FFijmax i j
11

I nodi inizio e fine progetto
Ogni nodo j è in relazione con i nodi 1 e n.

• Ogni nodo j può cominciare solo dopo che 1 è finito (time lag 0)

sj

f1 + FS1jmin
FS
1 min 1j

sj - s1 j d1 + FS1jmin

sj - s1
0 1

0 j Il nodo n può cominciare solo dopo che j è finito (time lag 0)

sn

fj + FSjnmin
FS min jn j sn - sj

dj + FSjnmin

sn - sj

dj

n j dj

n
12

Grafo dei vincoli
SSmin(1)

3
SSmin(2) 0 1 SSmin(0) SSmin(2) 3 7 4

FFmax(4) FFmax(3) 2 2

4 6 FFmin(2) 9 4

• le durate sono in blu accanto al nodo
FSmin(2)
1 0

FSmin(4)

SSmin(1) 6 FSmin(0) 8 FFmin(2)

0

SSmin(2) SFmin(10)

• Vanno aggiunte le relazioni fittizie mancanti e i corrispondenti archi nel grafo dei vincoli 0
1

5 SFmin(6) 7 5 4 1 SFmax(4) -3 4
2 2 -2

SSijmin SSijmax SFijmin SFijmax FSijmin FSijmax
6

lij= SSijmin lji= -SSijmax lij= SFijmin - dj lji= dj - SFijmax lij= di + FSijmin lji= -di - FSijmax lij= di - dj + FFijmin lji= dj - di - FFijmax
1 0

2

FFijmin FFijmax
9 1

6 6

6
2

8 1

2

3

-3 1 7
13

6

5

Grafo dei vincoli

I nodi inizio e fine progetto
Ogni nodo j è in relazione con i nodi 1 e n. • Ogni nodo j può cominciare solo dopo che 1 è finito (time lag 0)

sj

f1 + FS1jmin

sj - s1

d1 + FS1jmin

sj - s1

0

Il nodo n può cominciare solo dopo che j è finito (time lag 0)

sn

fj + FSjnmin

sn - sj
1 4 2 1 0 2 2

dj + FSjnmin
-3 6 2

s n - sj

dj

d6 = 4
9 6
1 0

-2 1
6 2 3 6 5 1 8 1 7 6

-3
14

0

Formulazione makespan
Problema del calcolo del makespan: costruisci un piano (schedule) che soddisfi tutti i vincoli di precedenza e minimizzi la durata del progetto.

Il problema di calcolo del makespan può essere formualto come PL:

min sn sj s

s1 si R|V | lij ij A
(PM)

Ogni soluzione ammissibile di (PM) è detta piano o schedule. In forma compatta: min {sn – s1: Ms l, s R|V|}, M R|A|
|V|,

l R|A|
15

M matrice d’incidenza archi-nodi del grafo dei vincoli

“Walk”, Cammini e Cicli
W “WALK” IN G(V,A)
SEQUENZA ALTERNANTE DI NODI e ARCHI W=(v1, e1, v2, e2, v3,…, ep, vp) e1 =(v1,v2)=(6,1) 6 1 2
G(N,A)

3

4

5 3 2
V3 V4

6
V1

1
V2

6

…

5

2
Vp-1

3
Vp

CAMMINO
1

“WALK” in G(V,A) senza archi e nodi interni ripetuti
3 2 6 5 1 2 3 4

CICLO

CAMMINO CHIUSO (nodi estremi coincidenti)
6 5 2 3 4 5 5

G(N,A)

16

Grafi Orientati: Cammini e Cicli Orientati
CAMMINO ORIENTATO CAMMINO P=(V1, (V1,V2), V 2, (V2,V3),…, (Vp-1,Vp), Vp) con:
Vk coda di ( Vk,Vk+1 ) per ogni k=1,…,p-1 1 6 Vi1 1 Vi2 3 Vi3 4 Vi4 6 5 2
G(N,A)

3

4

CICLO ORIENTATO
6
V1

CAMMINO ORIENTATO CHIUSO
5
V3

2
V2

6
V4

Peso di un cammino P di G(V,A)

l(A(P))=l(P)=

luv

17

uv A(P)

Condizione di esistenza delle soluzioni
OSS: Esiste (almeno) un cammino orientato dal nodo 1 a ogni nodo del grafo dei vincoli.
TEOREMA 3.1: Sia P*u il cammino di peso massimo da 1 ad un generico nodo u V. Se il grafo dei vincoli G(V,A) non ha cicli orientati di peso totale positivo allora s’u=l(P*u) per ogni u V è una soluzione ammissibile per (PM)
DIMOSTRAZIONE: Se s’v – s’u luv per ogni uv A s’ è una soluzione ammissibile

Se, per assurdo, si ha, s’v – s’u < luv per qualche uv A l(P*v)–l(P*u) < luv l(P*v) l(P*v) CONTRADDIZIONE

P*u

Quindi: v appartiene a P*u=(1,…,u)
Detto P’ =(v,…,u) il sotto-cammino di P*u da v ad u C= P’ {uv} è un ciclo orientato 1 P*v C P’
18

v

u

l(P*v) s(3) -6 Iter 4. k = 4. s(4) = -∞ < s(2) + 4 s(4) = s(2) + 4 = 6 Iter 5. k = 5. s(4) = 6 < s(3) + 3 s(4) = s(3) + 3 = 7 Iter 6. k = 6. s(2) = 2 < s(3) + 5 s(2) = s(3) + 5 = 9 Repeat 2 Iter 1. k = 1. s(2)= 9 > s(1) + 2 Iter 2. k = 2. s(3) = 4 = s(1) + 4 Iter 3. k = 3. s(1) = 0 > s(3) -6 Iter 4. k = 4. s(4) = 7 < s(2) + 4 s(4) = s(2) + 4 = 13 Iter 5. k = 5. s(4) = 13 > s(3) + 3 Iter 6. k = 6. s(2) > s(3) + 5

prec(2) = 1 prec(3) = 1 prec(4) = 2 prec(4) = 3 prec(2) = 3

prec(4) = 2

26

Alla prossima iterazione del blocco repeat non vengono aggiornate le variabili

L’arborescenza dei cammini massimi
• L’arborescenza dei cammini massimi può essere ricostruita a partire dal vettore dei predecessori, prec()

2

2
5 4 -6

4

4
3

1

3

prec(1) = 0 prec(2) = 3 prec(3) = 1 prec(4) = 2

27

Correttezza algoritmo Bellman-Ford
Def. Lunghezza di un cammino = numero archi che lo compongono OSS. Niente cicli orientati positivi: esistono cammini massimi contenenti al più n-1 archi.

Principio di ottimalità. Se P = {1, j1, j2, …., jk-1, jk} è un cammino (di peso) massimo da 1 a jk, allora P’ = {1, j1, j2, …., jk-1} è un cammino (di peso) massimo da 1 a jk-1
P j1 1 P’ jk-2 jk-1 lhi h jk i
28

Correttezza
Sia es il vettore dei pesi dei cammini massimi. Dal principio di ottimalità segue esi ji

max es j l ji
(i )

per ogni i V {1}

(A)

esh h 1 esw w esj j

lhi lwi lji i esi

Proprietà di ottimalità

esi

es j l ji , per ogni ji

(i), i V {1}
29

Correttezza
Per i q V, indichiamo con si il valore della variabile si alla fine della q-esima iterazione (piccola)

OSS. A ogni iterazione piccola viene visitato un solo arco. q Se (r,h) è l’arco visitato alla q-esima iterazione piccola allora si

siq

1

per ogni i

h

Lemma 3.5. siq Per q = 0, si ha

esi per ogni q e per ogni i s10 si0 0 0 es1 esi i V {1}

V e la condizione del lemma (invariante) è soddisfatta

Per assurdo, sia q > 0 la prima iterazione in cui l’invariante è violato.

lrh r srq 1

h esr (1)

Sia (r,h) l’arco visitato alla q-esima iterazione. q Poiché alla (q-1)-esima iterazione l’invariante è soddisfatto sarà: sh 1

esh srq
1

e

Poiché alla q-esima iterazione l’invariante è violato sarà:

q sh

esh q sh

Quindi la variabile corrispondente ad h è stata aggiornata e sarà

lrh

(2)

Da (1) e (2)

esr lrh

srq

1

lrh

q sh

Per la proprietà di ottimalità

esh

esr lrh

esh

q sh contraddizione.

30

Correttezza k Indichiamo con Si

sikm il valore della variabile si alla fine della k-esima iterazione “grande”.

Lemma 3.6. Sia i V tale che esiste un cammino massimo da 1 a i di lunghezza minore o uguale k. Allora Siq esi per ogni q ≥ k
(variabili non decrescenti) Sit Siq Per induzione. Per k = 0. L’unico cammino massimo di lunghezza 0 è il cammino da 1 a 1.

Per ogni i

V, q > t

S10

0 es1 Dal lemma 3.5 S1q

es1 per q ≥ 0.

q Per la non decrescenza S1

es1 per q ≥ 0.

Per k > 0 sia P = {1, j1, …, jk-1 , jk = i} un cammino massimo fino a i. Poniamo h = jk-1. Il cammino {1, j1, …, jk-1 = h} è un cammino massimo fino a h di lunghezza k-1 (principio di ottimalità). Quindi, esi = esh + lhi. Per ipotesi induttiva, alla fine della k-1-esima iterazione grande, si ha k Sh 1

1 j1 esh h jk-1

Durante la k-esima iterazione grande, alla r-esima iterazione piccola si visita l’arco (h,i)

s

r 1 h

esh

e per il Lemma 3.5

Dopo l’aggiornamento Da cui

s esi

r i

max( s , s

r 1 i r 1 r 1 i h

s

esi

esh lhi

lhi ) max( s , es ) esi

r 1 h hi r 1 i i

s

l

lhi
31 i

jk

esi

sir

Sik

Correttezza
Corollario 3.7. L’algoritmo di Bellman-Ford termina in al più n iterazioni grandi. Il cammino massimo più lungo contiene al più n-1 archi.
Alla fine della (n-1)-esima iterazione grande Sin 1 esi per ogni i
V (Lemma 3.6)

Per la non decrescenza, le variabili non vengono più aggiornate durante l’n-esima iterazione grande e l’algoritmo termina.

32

Ancora sulle relazioni fittizie
Precedenze fittizie: Per ogni nodo i 1, esiste l’arco (1,i) di peso 0.

Per ogni nodo i

n, esiste l’arco (i,n) di peso di.

• Nelle rappresentazioni grafiche del grafo delle precedenze generalizzate vengono spesso omesse.

• Nella risoluzione degli esercizi possono essere omesse solo se (certamente) implicate dalle altre relazioni di precedenza. 1. E’ possibile omettere l’arco (1,i) se esiste nel grafo un cammino orientato P1i da 1 a i di peso l(P1i) almeno pari a 0.
Infatti, per il Teorema 3.2 s’i s’1 + l(P1i) e il vincolo s’i corrispondente all’arco (1,i) è implicato. s’1

2. Analogamente, è possibile omettere l’arco (i,n) se esiste nel grafo un 33 cammino orientato da i a n di peso almeno pari a di.

Un esercizio completo
3 SSmin(5) 2 30 5 FSmin(0) 18 FSmin(0) 6 SSmin(1) FSmin(0) 7 FSmax(3) 7 8 0

FSmin(0)

FSmax(5) FSmin(5) 0 1 FSmin(10) 3 10 SSmax(5) SSmin(5) 4 15 FSmin(10)

FSmin(3) FSmin(0)

5
0 -15 1

2
15 3 -5 5 18 4 -18

5
30

In questo esempio è facile vedere che le relazioni fittizie sono implicate dagli altri vincoli.
8

10

20

6 1

18

7 7
34

0

Un esercizio completo e1 1 0 -15 10 2 15 5

e5
20 e8 18 e10 -18 e14

5

30 e 11

Inizializzazione: s(1) = 0, s(2) = s(3) = s(4) = s(6) = s(7) = s(8)= -∞, prec(i) = *, i V
8 Ordinamento archi: e1=(1,2), e2=(1,3), e3=(1,4),

e4
3 -5

e6 e7
5

e2 e 9
0

e12

6 1

18 e13
7

e3

e15

4

7

e4=(2,3), e5=(2,5), e6=(3,2), e7=(3,4), e8=(3,6), e9=(4,3), e10=(4,7), e11=(5,8), e12=(6,7), e13=(6,8), e14=(7,4), e15=(7,8).

Repeat 1 k = 1. s(2) = -∞ < s(1) + 0 s(2) = s(1) + 0 = 0 k = 2. s(3) = -∞ < s(1) + 10 s(3) = s(1) + 10 = 10 k = 3. s(4) = -∞ < s(1) + 0 s(4) = s(1) + 0 = 0 k = 4. s(3) = 10 > s(2) – 15 k = 5. s(5) = -∞ < s(2) + 5 s(5) = s(2) + 5 = 5 k = 6. s(2) = 0 < s(3) + 15 s(2) = s(3) + 15 = 25 k = 7. s(4) = 0 < s(3) + 5 s(4) = s(3) + 5 = 15 k = 8. s(6) = -∞ < s(3) + 20 s(6) = 30 k = 9. s(3) = s(4) -5 k = 10. s(7) = -∞ < s(4) + 18 s(7) = 33 k = 11. s(8) = -∞ < s(5) + 30 s(8) = 35 k = 12. s(7) = 33 > s(6) + 1 k = 13. s(8) = 35 < s(6) + 18 s(8) = 48 k = 14. s(4) = 15 = s(7) - 18 k = 15. s(8) = 48 > s(7) + 7

s prec(2) = 1 prec(3) = 1 prec(4) = 1 prec(5) = 2 prec(2) = 3 prec(4) = 3 prec(6) = 3 prec(7) = 4 prec(8) = 5 prec(8) = 6

prec

1 2 3 4 5 6 7 8

0 25 10 15 5 30 33 48

1 2 3 4 5 6 7 8

* 3 1 3 2 3 4 6

35

Un esercizio completo e1 1 0 -15 10 2 15 5

e5
20 e8 18 e10 -18 e14

5

30 e 11

e4
3 -5

e6 e7
5

e2 e 9
0

e12

6 1

18 e13
7

Ordinamento archi: e1=(1,2), e2=(1,3), e3=(1,4), e4=(2,3), e5=(2,5), e6=(3,2), e7=(3,4), e8=(3,6), e9=(4,3), e10=(4,7), e11=(5,8), e12=(6,7), e13=(6,8), 8 e =(7,4), e =(7,8). 14 15

e3

e15 prec 4

7

s Repeat 2 k = 1. s(2) = 25 > s(1) + 0 1 0 k = 2. s(3) = 10 = s(1) + 10 2 25 k = 3. s(4) = 15 > s(1) + 0 3 10 k = 4. s(3) = 10 > s(2) – 15 k = 5. s(5) = 5 < s(2) + 5 s(5) = s(2) + 5 = 30 prec(5) = 2 4 15 k = 6. s(2) = 25 = s(3) + 15 5 30 k = 7. s(4) = 15 = s(3) + 5 6 30 k = 8. s(6) = 30 = s(3) + 20 7 33 k = 9. s(3) = s(4) -5 k = 10. s(7) = 33 = s(4) + 18 8 60 k = 11. s(8) = 48 < s(5) + 30 s(8) = 60 prec(8) = 5 k = 12. s(7) = 33 > s(6) + 1 k = 13. s(8) = 50 > s(6) + 18 Nella prossima repeat le variabili non si k = 14. s(4) = 15 = s(7) - 18 modificano più e l’algoritmo termina k = 15. s(8) = 50 > s(7) + 7

1 2 3 4 5 6 7 8

* 3 1 3 2 3 4 5

36

Un esercizio completo
5 15

0 -15

2

5

30 18 1 7

s
8
prec

1

10 -5 0

3
5 4

20 18

6

7 -18

Arborescenza dei cammini massimi, costruita a partire dal vettore dei predecessori

1 2 3 4 5 6 7 8

* 3 1 3 2 3 4 5

1 2 3 4 5 6 7 8

0 25 10 15 20 30 33 60

37

Il cammino critico
Il cammino massimo dal nodo 1 al nodo n (fine progetto) è detto cammino critico.
3 0 -15 0 1 10 2 15 20 20 6 7 7 -18 20 5 30 5 4 30 8 0 7

3 10 -5 5 4 15

18 0

Il peso del cammino massimo dal nodo 1 al nodo n (fine progetto) corrisponde alla durata (minima) dell’intero progetto (makespan)
38

Riepilogando: il cammino critico
• Le relazioni di precedenza vengono rappresentate su un grafo orientato G(V,A) con pesi lij associati agli archi ij A. • In assenza di cicli positivi, l’es può essere calcolato utilizzando gli algoritmi noti per il calcolo del cammino massimo dal nodo 1 (inizio progetto) a tutti gli altri nodi del grafo dei vincoli. • In particolare esi = peso del cammino cammino di peso massimo dal nodo 1 al nodo i, per ogni i V. • Il peso del cammino massimo dal nodo 1 al nodo n (fine progetto) corrisponde alla durata minima dell’intero progetto e viene detto makespan. • Ogni cammino massimo dal nodo 1 al nodo n (fine progetto) è detto cammino critico. • Esistono diversi algoritmi per il calcolo del cammino di peso massimo, con complessità distinte.

• Nel caso generale si può usare l’algoritmo di Bellman-Ford.
39

Calcolo del latest completion time
Supponiamo sia data una deadline T per il progetto, ovvero un vincolo del tipo. sn T deadline

Ciò corrisponde ad aggiungere l’arco (n,1) di peso –T al grafo dei vincoli max SSij

si - sj n SSijmax
T
1 n 1

Vogliamo rispondere alla domanda: quando possono cominciare e terminare al più tardi le singole attività del progetto (determinando così il Latest Start Schedule e il Latest Finish Schedule) in modo da rispettare la deadline T ? Def. Per ogni j V si indica con lsj il latest start time dell’attività j, e cioè l’ultimo istante di tempo in cui l’attività j può cominciare violare il vincolo di deadline T, e con lfj il latest finish time, e cioè l’ultimo istante di tempo in cui l’attività j può terminare senza ritardare il progetto. In ipotesi di no – preemption : lsj + dj = lfj
40

Calcolo del Latest Start Schedule
Sia Pin un cammino da i a n. La deadline T implica T sn • Per il Teorema 3.2 sarà necessariamente sn si + l(Pin). • Quindi T si + l(Pin) si ≤ T - l(Pin) per ogni cammino Pin da i a n. i • Il vincolo più stringente si ottiene in corrispondenza del cammino massimo P*in , per cui vale si ≤ T l(P* in) = lsi

Pin

Algoritmo generico calcolo ls for i = 1 to n-1 Calcola il peso Li del cammino massimo da i a n Poni lsi = T - Li Endfor n 41

Efficienza del calcolo dell’ ls
• Per ogni nodo i V , l’algoritmo prevede il calcolo del cammino massimo da i a n. • L’algoritmo del Bellman e Ford ha complessità O(mn) e deve essere riapplicato a ogni iterazione. Quindi la complessità risulta O(mn2). • OSS. L’algoritmo di Bellman Ford calcola il peso dei cammini massimi dal nodo iniziale a tutti gli altri nodi del grafo.

• IDEA: costruisci un grafo G’(V,A’) ottenuto da G(V,A) invertendo gli archi, ovvero sostituendo ogni arco ij con un arco ji di peso pari al peso dell’arco originario h 1 -4 3 j 4 i 2 q h v 1 w

-4 3 j 2
3

q

w

3

v

Grafo reverse

4 i 42

OSS. Ogni cammino da n a i in G’ corrisponde a un cammino da i a n in G di uguale peso.

Calcolo dell’ ls per reti generalizzate

Calcolo del latest start schedule 1. Costruisci il grafo G’ reverse di G

2. Applica Bellman - Ford per calcolare il peso Li del cammino massimo da n a i per ogni i V – {n}
3. Poni lsi = T - Li per ogni i V – {n}

Poiché il grafo reverse può essere (facilmente) costruito in O(m), la complessità dell’algoritmo e O(mn).
43

Total Float e Attività Critiche
Def. Total float tfi dell’attività i misura quanto l’attività i può essere ritardata senza violare la deadline del progetto

• L’attività i non può cominciare prima del suo earliest start time esi • Se l’attività i comincia dopo il suo latest start time lsi il progetto viene ritardato. tfi = lsi - esi per ogni j in V

Def. Un’attività è detta critica se il suo total float è 0.

44

Altre rappresentazioni (Gantt Charts)
Dato un piano di attività s ammissibile è possibile darne una rappresentazione grafica mediante Gantt Charts (introdotte dall’ingegner Gantt nel 1918) Un diagramma di Gantt è una griglia bidimensionale: sulle righe ci sono le attività mentre sulle colonne gli istanti di tempo dell’orizzonte temporale.

Ogni attività i è rappresentata con una barra orizzontale di lunghezza pari alla sua durata di, partendo dalla casella nella colonna si.
Vengono cioè riempite le caselle della griglia corrispondenti a istanti in cui l’attività è (prevista) in svolgimento.
ATTIVITA'
1 2 3

PRIMO ANNO
4 5 6 7 8 9 10 11 12 1 2

SECONDO ANNO
3 4 5 6 7 8 9 10 11

RI1.1 Identificazione degli scenari tecnologici RI1.2 Definizione degli obiettivi di servizio RI1.3 Definizione dei requisiti funzionali di sistema RI1.4 Definizione metriche di valutazione RI2.1 Generazione Mappe 3D RI2.2 Generazione Mappe Vettoriali RI2.3 Modelli neurali di predizione di campi RI3.1 Studio di Algoritmi di pianificazione di reti wireless RI3.2 Realizzazione prototipale algoritmi di pianificazione RI3.3 Studio di Algoritmi di gestione delle risorse di reti wireless RI3.4 Realizzazione prototipale algoritmi di gestione SP4.1 Gestione e controllo calcolo distribuito SP4.2 Progettazione del protocollo di data communication SP4.3 Realizzazione sistemi di data storage RI4.4 Definizione piani di sperimentazione RI4.5 Esecuzione dei test RI4.6 Analisi dei risultati ottenuti dal progetto

45

Altre rappresentazioni (Gantt Charts)
Esistono “in natura” diversi formati per le Gantt Chart. Ad esempio, si possono rappresentare sulla stessa riga più attività che non si sovrappongono temporalmente. Di seguito riportiamo la rappresentazione per l’earliest start schedule del progetto esempio 3 2 5 4
2 3 4 5

Gantt chart
6 Earliest start schedule

7
6 7 8 9 10 11 12

1

Il cammino critico è evidenziato in rosso

46

Esempio di calcolo es e ls
5
0 -3 1 1 2 5 2 3 -9 9 4 4 5

Applicando Bellman-Ford con nodo radice 1 calcolo l’arborescenza dei cammini massimi e quindi l’earliest start schedule
5 0 2 5

es
4

-3
1 1

2 3

-9 9

4

5

1 2 3 4 5

0 3 1 10 14
47

Calcolo dell’ls
5 0 -3 1 1 2 5

2
3

-9
9

4

4

5

Per calcolare il latest start time lsi di un’attività i devo calcolare il peso Li del cammino massimo da i a n e porre lsi = T - Li

Applicando Bellman-Ford con nodo radice i calcolo l’arborescenza dei cammini massimi di radice i e quindi anche il cammino massimo da i a n. Es. T = 17, i = 3 L3 = 13 ls3 = 17-13 = 4
1
0 -3

5 2 5 2 -9 9 4 4 5

Non posso calcolare, ad esempio, ls2, e sono quindi obbigato a riapplicare Bellman-Ford, con radice 2, questa volta.
5 0 -3 1 2 5 2 3 -9 4 4 5

1

3

Es. T = 17, i = 2

L2 = 11

ls2 = 17-11 = 6

48

1

9

Calcolo dell’ls
5 0 -3 1 1 2 5

2
3

-9
9

4

4

5 5 0 -3 1 2

5
2 3 -9 4 4 5

1

9

Se applico Bellman-Ford una sola volta al grafo reverse con radice n ottengo l’arborescenza reverse

49