9.2 Cammini e cammini critici¶
Parte 5 · Gestione dei progetti · Capitolo 9 · Capitolo 9: Gestione dei progetti · Dispensa, volume 5 (PDF) · Slide · Esercizi: Gestione dei progetti · App: Il metodo del cammino critico (CPM)
-
Sotto le ipotesi (H1) e (H2), il metodo del cammino critico risponde alle seguenti domande.
-
Qual è il tempo minimo necessario per completare il progetto?
-
Quando può iniziare e terminare, al più presto, ogni attività?
-
Quando deve iniziare e terminare, al più tardi, ogni attività per non ritardare il completamento del progetto?
-
Quali attività sono critiche, cioè tali che ogni loro ritardo ritarda il progetto?
-
Per le altre attività, quanto ritardo si può tollerare?
-
Definizione 9.5: lunghezza di un cammino e cammino critico
Ogni arco \((i,j) \in A\) ha lunghezza \(d_i\), la durata della sua coda. La lunghezza di un cammino orientato \(P=i_0,i_1,\dots,i_k\) è
la durata complessiva dei suoi nodi, escluso l'ultimo. Un cammino critico è un cammino da START a FINISH di lunghezza massima. Un'attività è critica se sta su un cammino critico.
-
Su un cammino da START a FINISH le durate del primo e dell'ultimo nodo sono nulle: \(L(P)\) è la durata complessiva delle attività del cammino.
-
Un progetto può avere più cammini critici: quando più cammini hanno la stessa lunghezza massima, sono tutti critici.
Lemma 9.6: ogni cammino limita la durata
Per ogni calendario \(\vet{t}\) e ogni cammino \(P\) da START a FINISH, \(t_{n+1} \ge L(P)\).
Dimostrazione
Sia \(P=i_0,i_1,\dots,i_k\) con \(i_0=0\) e \(i_k=n+1\). Sommando i vincoli \(t_{i_{s+1}} \ge t_{i_s}+d_{i_s}\) degli archi di \(P\), i tempi di inizio si elidono a catena:
e \(t_0=0\). □
- Le attività di un cammino si svolgono una dopo l'altra, senza sovrapposizioni: il progetto non può durare meno di nessun cammino.
Esempio 9.2: i cammini del caso di studio
La rete dell'Esempio 9.1 ha sei cammini da START a FINISH; le loro lunghezze, in settimane, sono:
| cammino da START a FINISH | lunghezza (settimane) |
|---|---|
| \(\text{START},1,2,3,4,7,8,13,\text{FINISH}\) | \(2+4+10+6+7+9+2=40\) |
| \(\text{START},1,2,3,5,6,10,11,14,\text{FINISH}\) | \(2+4+10+4+5+8+4+6=43\) |
| \(\text{START},1,2,3,5,6,10,12,14,\text{FINISH}\) | \(2+4+10+4+5+8+5+6=44\) |
| \(\text{START},1,2,3,5,8,13,\text{FINISH}\) | \(2+4+10+4+9+2=31\) |
| \(\text{START},1,2,3,9,10,11,14,\text{FINISH}\) | \(2+4+10+7+8+4+6=41\) |
| \(\text{START},1,2,3,9,10,12,14,\text{FINISH}\) | \(2+4+10+7+8+5+6=42\) |
-
Il cammino più lungo è START\(,1,2,3,5,6,10,12,14,\)FINISH, di lunghezza \(44\): per il Lemma 9.6, ogni calendario dura almeno \(44\) settimane.
-
Il progetto può durare più di un dato cammino. Sul cammino START\(,1,2,3,5,8,13,\)FINISH, di lunghezza \(31\), l'attività \(8\) aspetta l'attività \(5\), che può terminare alla settimana \(2+4+10+4=20\), ma anche l'attività \(7\), che non sta sul cammino e non può terminare prima della settimana \(2+4+10+6+7=29\).
Il numero dei cammini
Elencare i cammini non funziona sui progetti grandi: il loro numero può crescere esponenzialmente con \(n\). Una sequenza di \(k\) coppie di attività in parallelo, ogni coppia dopo la precedente, ha \(2^k\) cammini da START a FINISH. Il metodo del cammino critico trova la lunghezza di un cammino massimo senza elencare i cammini.
La lunghezza di un cammino da START a FINISH è la durata complessiva delle sue attività. Ogni calendario dura almeno quanto ognuno di questi cammini; i cammini critici sono quelli più lunghi.