Vai al contenuto

9.8 Due percorsi critici e cambi di durata

Parte 5 · Gestione dei progetti · Capitolo 9 · Capitolo 9: Gestione dei progetti · Dispensa, volume 5 (PDF) · Esercizi: Gestione dei progetti

- Un pianificatore spesso chiede cosa succede al progetto se un'attività richiede più tempo o se più squadre la realizzano più breve. Gli allentamenti e i percorsi critici rispondono senza eseguire nuovamente il metodo.

Proposizione 9.19: modifica una durata

Lascia che \(j\) sia un'attività, \(\delta>0\) e \(T'\) la durata minima del progetto dopo la modifica.

  • (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 percorso critico lo fa non contenere \(j\).

Dimostrazione

Per Teorema 9.9, la durata minima del progetto è la lunghezza massima di un percorso da INIZIO per FINE. La modifica modifica con \(\pm\delta\) la lunghezza dei percorsi attraverso \(j\), e solo di essi.

  • (a) Secondo Teorema 9.13, i percorsi più lunghi attraverso \(j\) crescono fino a \(L_j+\delta=T-\mathit{TS}_j+\delta\). Se \(\mathit{TS}_j>0\), i percorsi critici evitano \(j\) e mantengono la lunghezza \(T\); se \(\mathit{TS}_j=0\), il i percorsi che evitano \(j\) hanno una lunghezza massima pari a \(T<T+\delta\). In entrambi i casi \(T'=\max\{T,\,T-\mathit{TS}_j+\delta\}\).

  • (b) Nessun percorso cresce e ogni percorso perde al massimo \(\delta\), quindi \(T-\delta \le T' \le T\). Un percorso critico quello evita \(j\) mantiene la lunghezza \(T\).

□

Esempio 9.8: un progetto con due percorsi critici

Un progetto ha attività \(8\) con i predecessori immediati e le durate della tabella.

attività \(j\) e predecessori immediati e \(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\); nodo \(1\) viene rimosso per primo e libera \(4\) e \(5\); quindi \(3\) è il nodo libero con l'indice più piccolo e libera \(2\), che viene prima di \(4\). L'ordine è \(0,1,3,2,4,5,6,7,8,9\), e il passaggio avanti e quello indietro danno:

\(j\) \(d_j\) \(\mathit{ES}_j\) \(\mathit{EF}_j\) \(\mathit{LS}_j\) \(\mathit{LF}_j\) \(\mathit{TS}_j\) \(\mathit{FS}_j\) critico
\(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 due percorsi di archi stretti vanno dall'INIZIO alla FINE: START\(,1,4,6,8,\)FINISH e START\(,1,5,7,8,\)FINISH, entrambi di lunghezza \(13\) (blu in 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 la prima ora di inizio dell'attività \(2\), non la fine del progetto. L'attività \(2\) ha \(\mathit{TS}_2=\mathit{FS}_2=7\).

  • Il percorso START\(,1,4,7,8,\)FINISH utilizza 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 è critica.

Figura 7

Esempio 9.9: modifiche di una durata

Modifichiamo una durata alla volta nel progetto di Esempio 9.8; la nuova durata e la criticità i percorsi sono calcolati con il metodo del percorso critico e concordano con Proposizione 9.19.

modifica \(\mathit{TS}_j\) e nuovo \(T\) e percorsi critici dopo la modifica
\(d_5=5 \to 4\) \(0\) \(13\) \(\text{START},1,4,6,8,\text{FINISH}\)
\(d_8=3 \to 2\) e \(0\) e \(12\) e \(\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 abbrevia il progetto: il percorso critico START\(,1,4,6,8,\)FINISH evita l'attività \(5\) e \(T'=T=13\) da (b). Rimane solo un percorso critico.

  • L'attività \(8\) si trova su entrambi i percorsi critici: accorciandolo di un giorno si ottiene \(T'=T-1=12\) ed entrambi i percorsi rimangono critico.

  • L'attività \(3\) impiega \(2\) giorni in più, più del suo rallentamento totale \(\mathit{TS}_3=1\): da (a), \(T'=13+(2-1)=14\) e START\(,3,6,8,\)FINISH diventa il percorso critico.

Riduzione di un progetto

Per abbreviare un progetto, ogni percorso critico deve diventare più breve. Quando sono presenti diversi percorsi critici, un'attività poggiare su uno solo di essi non aiuta: abbreviare 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\}\) di più. Se \(d_j\) diminuisce, il progetto guadagna a più o meno la stessa quantità, e niente se un percorso critico evita \(j\): con diversi percorsi critici, tutti devono essere accorciato.

9.9 Errori tipici

Attenzione

  • Sommando tutte le durate. Il caso di studio dura \(T=44\) settimane, non \(79\): attività che non sono collegati da precedenze funzionano in parallelo.

  • Prendendo il minimo nel passaggio in avanti. Un'attività inizia quando tutti i suoi immediati predecessori sono finiti: \(\mathit{ES}_j\) è il massimo dei loro primi tempi di arrivo. Simmetricamente, \(\mathit{LF}_j\) è il minimo del ultimi orari di inizio dei successori.

  • Dimenticando INIZIO, FINE e i loro archi. Ogni attività senza predecessori immediati necessita dell'arco da INIZIO, e ogni attività senza successori l'arco fino a FINE.

  • Somma dei rallentamenti totali lungo un percorso. La catena \(4,7,8,13\) del caso di studio ha \(4\) settimane di rallentamento in tutto, non \(16\).

  • Confusione del margine di flessibilità totale e libero. Un ritardo maggiore di \(\mathit{FS}_j\) sposta altre attività, anche quando lo fa non ritardare il progetto.

  • Lettura di un percorso critico solo dalle attività critiche. In Esempio 9.8 il il percorso START\(,1,4,7,8,\)FINISH ha solo attività critiche, e non è critico: controlla che gli archi siano stretti.

  • Riduzione di un'attività su uno dei numerosi percorsi critici. La durata del progetto non cambia.

  • Accettare le precedenze con un ciclo. Non esiste alcuna pianificazione e l'ordine topologico si interrompe prima ordinare tutti i nodi.

9.10 In sintesi

In sintesi

  • Un progetto ha attività con durate e precedenze deterministiche; la sua rete di progetto ha un nodo per ogni attività, più INIZIO e FINE, e deve essere aciclica.

  • La lunghezza di un percorso dall'INIZIO alla FINE è la durata totale delle sue attività; ogni programma dura alle almeno quanto ogni percorso, e i percorsi critici sono i più lunghi.

  • Il passaggio in avanti fornisce \(\mathit{ES}_j=\max \mathit{EF}_i\) e \(T=\mathit{ES}_{n+1}\), la lunghezza di un percorso critico; il passaggio all'indietro dà \(\mathit{LF}_j=\min \mathit{LS}_k\) a partire 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 percorsi critici sono i percorsi di archi stretti.

  • Il modello \(\mathrm{PD}\) \(\min\{t_{n+1}-t_0 : t_j-t_i \ge d_i\}\) ha il modello con percorso più lungo come duale ed entrambi hanno valore ottimale \(T\).

  • L'aumento di \(d_j\) di \(\delta\) ritarda il progetto di \(\max\{0,\delta-\mathit{TS}_j\}\); l'accorciamento aiuta solo se ogni il percorso critico si accorcia.

I due progetti in sintesi.

caso di studio e attività \(14\), settimane \(79\) in tutto; \(T=44\) settimane
percorso critico \(\text{START},1,2,3,5,6,10,12,14,\text{FINISH}\)
non critico \(j\) (\(\mathit{TS}_j,\mathit{FS}_j\)) e \(4\) (\(4,0\)), \(7\) (\(4,0\)), \(8\) (\(4,0\)), \(9\) (\(2,2\)), \(11\) (\(1,1\)), \(13\) (\(4,4\))
Modelli LP e \(z(\mathrm{PD})=z(D(\mathrm{PD}))=44\); \(\mathit{ES}\) e \(\mathit{LS}\) ottimali
secondo esempio \(T=13\), 2 percorsi critici:
\(\text{START},1,4,6,8,\text{FINISH}\) e \(\text{START},1,5,7,8,\text{FINISH}\)
modifiche \(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