9.8 Due cammini critici e variazioni delle durate¶
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)
- Chi pianifica si chiede spesso che cosa succede al progetto se un'attività dura di più, o se più squadre la rendono più breve. Le scorte e i cammini critici rispondono senza eseguire di nuovo il metodo.
Proposizione 9.19: variazione di una durata
Siano \(j\) un'attività, \(\delta>0\), e \(T'\) la durata minima del progetto dopo la variazione.
-
(a) Se \(d_j\) aumenta di \(\delta\), allora \(T'=T+\max\{0,\,\delta-\mathit{TS}_j\}\).
-
(b) Se \(d_j\) diminuisce di \(\delta<d_j\), allora \(T-\delta \le T' \le T\), e \(T'=T\) se qualche cammino critico non contiene \(j\).
Dimostrazione
Per il Teorema 9.9, la durata minima del progetto è la lunghezza massima di un cammino da START a FINISH. La variazione cambia di \(\pm\delta\) la lunghezza dei cammini che passano per \(j\), e solo di quelli.
-
(a) Per il Teorema 9.13, i cammini più lunghi che passano per \(j\) crescono a \(L_j+\delta=T-\mathit{TS}_j+\delta\). Se \(\mathit{TS}_j>0\), i cammini critici evitano \(j\) e mantengono la lunghezza \(T\); se \(\mathit{TS}_j=0\), i cammini che evitano \(j\) hanno lunghezza al più \(T<T+\delta\). In entrambi i casi \(T'=\max\{T,\,T-\mathit{TS}_j+\delta\}\).
-
(b) Nessun cammino si allunga e ogni cammino si accorcia al più di \(\delta\), quindi \(T-\delta \le T' \le T\). Un cammino critico che evita \(j\) mantiene la lunghezza \(T\).
□
Esempio 9.8: un progetto con due cammini critici
Un progetto ha \(8\) attività, con i predecessori immediati e le durate della tabella.
| attività \(j\) | predecessori immediati | \(d_j\) |
|---|---|---|
| \(1\) | — | \(2\) giorni |
| \(2\) | \(3\) | \(2\) giorni |
| \(3\) | — | \(4\) giorni |
| \(4\) | \(1\) | \(3\) giorni |
| \(5\) | \(1\) | \(5\) giorni |
| \(6\) | \(3\), \(4\) | \(5\) giorni |
| \(7\) | \(4\), \(5\) | \(3\) giorni |
| \(8\) | \(6\), \(7\) | \(3\) giorni |
L'attività \(2\) segue l'attività \(3\), quindi l'ordine topologico non è quello naturale. START libera \(1\) e \(3\); il nodo \(1\) è tolto per primo e libera \(4\) e \(5\); poi \(3\) è il nodo libero di indice minimo e libera \(2\), che viene prima di \(4\). L'ordine è \(0,1,3,2,4,5,6,7,8,9\), e la passata in avanti e quella all'indietro danno:
| \(j\) | \(d_j\) | \(\mathit{ES}_j\) | \(\mathit{EF}_j\) | \(\mathit{LS}_j\) | \(\mathit{LF}_j\) | \(\mathit{TS}_j\) | \(\mathit{FS}_j\) | critica |
|---|---|---|---|---|---|---|---|---|
| \(1\) | \(2\) | \(0\) | \(2\) | \(0\) | \(2\) | \(0\) | \(0\) | sì |
| \(2\) | \(2\) | \(4\) | \(6\) | \(11\) | \(13\) | \(7\) | \(7\) | |
| \(3\) | \(4\) | \(0\) | \(4\) | \(1\) | \(5\) | \(1\) | \(0\) | |
| \(4\) | \(3\) | \(2\) | \(5\) | \(2\) | \(5\) | \(0\) | \(0\) | sì |
| \(5\) | \(5\) | \(2\) | \(7\) | \(2\) | \(7\) | \(0\) | \(0\) | sì |
| \(6\) | \(5\) | \(5\) | \(10\) | \(5\) | \(10\) | \(0\) | \(0\) | sì |
| \(7\) | \(3\) | \(7\) | \(10\) | \(7\) | \(10\) | \(0\) | \(0\) | sì |
| \(8\) | \(3\) | \(10\) | \(13\) | \(10\) | \(13\) | \(0\) | \(0\) | sì |
-
\(T=13\), e da START a FINISH vanno due cammini di archi stretti: START\(,1,4,6,8,\)FINISH e START\(,1,5,7,8,\)FINISH, entrambi di lunghezza \(13\) (in blu nella figura, con le durate sopra i nodi).
-
L'attività \(3\) ha \(\mathit{TS}_3=1\) e \(\mathit{FS}_3=0\): un giorno di ritardo sposta l'inizio al più presto dell'attività \(2\), non la fine del progetto. L'attività \(2\) ha \(\mathit{TS}_2=\mathit{FS}_2=7\).
-
Il cammino START\(,1,4,7,8,\)FINISH usa solo attività critiche, ma il suo arco \((4,7)\) non è stretto, \(\mathit{EF}_4=5<7=\mathit{ES}_7\): la sua lunghezza è \(2+3+3+3=11\), e non è critico.
Esempio 9.9: variazioni di una durata
Cambiamo una durata alla volta nel progetto dell'Esempio 9.8; la nuova durata e i cammini critici sono calcolati con il metodo del cammino critico, e concordano con la Proposizione 9.19.
| variazione | \(\mathit{TS}_j\) | nuovo \(T\) | cammini critici dopo la variazione |
|---|---|---|---|
| \(d_5=5 \to 4\) | \(0\) | \(13\) | \(\text{START},1,4,6,8,\text{FINISH}\) |
| \(d_8=3 \to 2\) | \(0\) | \(12\) | \(\text{START},1,4,6,8,\text{FINISH}\); \(\text{START},1,5,7,8,\text{FINISH}\) |
| \(d_3=4 \to 6\) | \(1\) | \(14\) | \(\text{START},3,6,8,\text{FINISH}\) |
-
Accorciare di un giorno l'attività \(5\) non accorcia il progetto: il cammino critico START\(,1,4,6,8,\)FINISH evita l'attività \(5\), e \(T'=T=13\) per (b). Resta un solo cammino critico.
-
L'attività \(8\) sta su entrambi i cammini critici: accorciarla di un giorno dà \(T'=T-1=12\), ed entrambi i cammini restano critici.
-
L'attività \(3\) dura \(2\) giorni in più, più della sua scorta totale \(\mathit{TS}_3=1\): per (a), \(T'=13+(2-1)=14\), e START\(,3,6,8,\)FINISH diventa il cammino critico.
Accorciare un progetto
Per accorciare un progetto, ogni cammino critico deve diventare più corto. Quando ci sono più cammini critici, un'attività che sta su uno solo di essi non serve: si accorcia un'attività comune a tutti, oppure un'attività su ciascuno.
Se \(d_j\) cresce di \(\delta\), il progetto dura \(\max\{0,\delta-\mathit{TS}_j\}\) in più. Se \(d_j\) diminuisce, il progetto guadagna al più la stessa quantità, e niente se un cammino critico evita \(j\): con più cammini critici, bisogna accorciarli tutti.
9.9 Errori tipici¶
Attenzione
-
Sommare tutte le durate. Il caso di studio dura \(T=44\) settimane, non \(79\): le attività non legate da precedenze si svolgono in parallelo.
-
Prendere il minimo nella passata in avanti. Un'attività inizia quando tutti i suoi predecessori immediati sono terminati: \(\mathit{ES}_j\) è il massimo delle loro fini al più presto. Simmetricamente, \(\mathit{LF}_j\) è il minimo degli inizi al più tardi dei successori.
-
Dimenticare START, FINISH e i loro archi. Ogni attività senza predecessori immediati ha bisogno dell'arco da START, e ogni attività senza successori dell'arco verso FINISH.
-
Sommare le scorte totali lungo un cammino. La catena \(4,7,8,13\) del caso di studio ha in tutto \(4\) settimane di scorta, non \(16\).
-
Confondere scorta totale e scorta libera. Un ritardo maggiore di \(\mathit{FS}_j\) sposta altre attività, anche quando non ritarda il progetto.
-
Leggere un cammino critico solo dalle attività critiche. Nell'Esempio 9.8 il cammino START\(,1,4,7,8,\)FINISH ha solo attività critiche, e non è critico: bisogna controllare che gli archi siano stretti.
-
Accorciare un'attività che sta su uno solo dei cammini critici. La durata del progetto non cambia.
-
Accettare precedenze con un ciclo. Non esiste alcun calendario, e l'ordine topologico si ferma prima di aver ordinato tutti i nodi.
9.10 In sintesi¶
In sintesi
-
Un progetto ha attività con durate deterministiche e precedenze; la sua rete delle attività ha un nodo per ogni attività, più START e FINISH, e deve essere aciclica.
-
La lunghezza di un cammino da START a FINISH è la durata complessiva delle sue attività; ogni calendario dura almeno quanto ogni cammino, e i cammini critici sono quelli più lunghi.
-
La passata in avanti dà \(\mathit{ES}_j=\max \mathit{EF}_i\) e \(T=\mathit{ES}_{n+1}\), la lunghezza di un cammino critico; la passata all'indietro dà \(\mathit{LF}_j=\min \mathit{LS}_k\) partendo da \(\mathit{LF}_{n+1}=T\).
-
\(\mathit{TS}_j=\mathit{LS}_j-\mathit{ES}_j\) è il ritardo che non ritarda il progetto, \(\mathit{FS}_j \le \mathit{TS}_j\) il ritardo che non sposta altre attività; i cammini critici sono i cammini di archi stretti.
-
Il modello \(\mathrm{PD}\) \(\min\{t_{n+1}-t_0 : t_j-t_i \ge d_i\}\) ha come duale il modello di cammino massimo, ed entrambi hanno valore ottimo \(T\).
-
Aumentare \(d_j\) di \(\delta\) ritarda il progetto di \(\max\{0,\delta-\mathit{TS}_j\}\); accorciare serve solo se ogni cammino critico diventa più corto.
I due progetti in breve.
| caso di studio | \(14\) attività, \(79\) settimane in tutto; \(T=44\) settimane |
|---|---|
| cammino critico | \(\text{START},1,2,3,5,6,10,12,14,\text{FINISH}\) |
| \(j\) non critiche (\(\mathit{TS}_j,\mathit{FS}_j\)) | \(4\) (\(4,0\)), \(7\) (\(4,0\)), \(8\) (\(4,0\)), \(9\) (\(2,2\)), \(11\) (\(1,1\)), \(13\) (\(4,4\)) |
| modelli LP | \(z(\mathrm{PD})=z(D(\mathrm{PD}))=44\); \(\mathit{ES}\) e \(\mathit{LS}\) ottimi |
| secondo esempio | \(T=13\), 2 cammini critici: |
| \(\text{START},1,4,6,8,\text{FINISH}\) e \(\text{START},1,5,7,8,\text{FINISH}\) | |
| variazioni | \(d_5=5\to 4\): \(T=13\); \(d_8=3\to 2\): \(T=12\); \(d_3=4\to 6\): \(T=14\) |
Esercizi su questo capitolo: Gestione dei progetti