9.2 Percorsi e percorsi critici¶
Parte 5 · Gestione dei progetti · Capitolo 9 · Capitolo 9: Gestione dei progetti · Dispensa, volume 5 (PDF) · Esercizi: Gestione dei progetti
-
In (H1) e (H2), il metodo del percorso critico risponde alle seguenti domande.
-
Qual è il tempo minimo richiesto per completare il progetto?
-
Quando può iniziare e terminare al più presto ciascuna attività?
-
Quando deve iniziare e terminare al più tardi ciascuna attività, per non ritardare il completamento del progetto?
-
Quali attività sono critiche, per cui qualsiasi ritardo su di esse ritarda il progetto?
-
Per le altre attività, quanto ritardo può essere tollerato?
-
Definizione 9.5: lunghezza di un percorso e percorso critico
Ogni arco \((i,j) \in A\) ha lunghezza \(d_i\), la durata della sua coda. Il lunghezza di un diretto il percorso \(P=i_0,i_1,\dots,i_k\) è
la durata totale dei suoi nodi tranne l'ultimo. Un percorso critico è un percorso dall'INIZIO alla FINE di lunghezza massima. Un'attività è critica se si trova su un percorso critico.
-
Su un percorso da INIZIO a FINE le durate del primo e dell'ultimo nodo sono zero: \(L(P)\) è il totale durata delle attività del percorso.
-
Un progetto può avere più percorsi critici: quando più percorsi si congiungono per la lunghezza massima, sono tutti critico.
Lemma 9.6: ogni percorso delimita la durata
Per ogni programma \(\vet{t}\) e ogni percorso \(P\) dall'INIZIO alla FINE, \(t_{n+1} \ge L(P)\).
Dimostrazione
Lascia che \(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\), il telescopio dei tempi di inizio:
e \(t_0=0\). □
- Le attività di un percorso devono essere svolte una dopo l'altra, senza sovrapposizioni: il progetto non può essere più breve di qualsiasi percorso.
Esempio 9.2: i percorsi del caso studio
La rete di Esempio 9.1 ha sei percorsi da INIZIO a FINE; la loro durata, in settimane, è:
| percorso dall'INIZIO alla FINE e durata (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 percorso più lungo è START\(,1,2,3,5,6,10,12,14,\)FINISH, di lunghezza \(44\): da Lemma 9.6, ogni programmazione dura almeno \(44\) settimane.
-
Il progetto può durare più di un determinato percorso. Sul percorso START\(,1,2,3,5,8,13,\)FINISH, di lunghezza \(31\), l'attività \(8\) attende l'attività \(5\), che può terminare nella settimana \(2+4+10+4=20\), ma anche l'attività \(7\), che non è sul percorso e non è possibile terminarlo prima della settimana \(2+4+10+6+7=29\).
Il numero di percorsi
Elencare i percorsi non funziona su progetti di grandi dimensioni: il loro numero può crescere esponenzialmente con \(n\). Una sequenza di \(k\) coppie di attività parallele, ciascuna coppia dopo la precedente, ha percorsi \(2^k\) da INIZIO a FINE. Il critico path trova la lunghezza di un percorso più lungo senza elencare i percorsi.
La lunghezza di un percorso dall'INIZIO alla FINE è la durata totale delle sue attività. Ogni programma dura almeno quanto lungo quanto ogni percorso del genere; i percorsi critici sono quelli più lunghi.