9.3 La passata in avanti: i tempi al più presto¶
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)
- Supponiamo dapprima che non ci siano ritardi: ogni attività dura quanto stimato e inizia appena tutti i suoi predecessori immediati sono terminati.
Definizione 9.7: tempi di inizio e di fine al più presto
Sia \(v_0,v_1,\dots,v_{n+1}\) un ordine topologico della rete delle attività. L'inizio al più presto \(\mathit{ES}_j\) e la fine al più presto \(\mathit{EF}_j\) dei nodi si calcolano in quest'ordine con la passata in avanti:
-
È la regola dell'inizio al più presto: l'inizio al più presto di un'attività è la massima fine al più presto dei suoi predecessori immediati. Quando si elabora il nodo \(j\), i suoi predecessori lo precedono nell'ordine topologico, quindi le loro fini al più presto sono note.
-
Come nel Capitolo 3, l'ordine topologico toglie, a ogni passo, il nodo senza archi entranti di indice minimo. Il nodo \(0\) è tolto per primo.
Teorema 9.8: tempi al più presto
Per ogni nodo \(j \in N\), \(\mathit{ES}_j\) è la lunghezza di un cammino massimo da START a \(j\). Inoltre \(\mathit{ES}\) è un calendario, e ogni calendario \(\vet{t}\) soddisfa \(t_j \ge \mathit{ES}_j\) per ogni \(j \in N\).
Dimostrazione
Dimostriamo la prima e l'ultima affermazione per induzione lungo l'ordine topologico.
-
Nodo \(0\). In START non entra nessun arco: l'unico cammino da START a \(0\) non ha archi e ha lunghezza \(0=\mathit{ES}_0\), e ogni calendario ha \(t_0=0=\mathit{ES}_0\).
-
Cammini massimi. Sia \(j \neq 0\). Ogni cammino da START a \(j\) è un cammino da START a un nodo \(i\) seguito da un arco \((i,j) \in \delta^-(j)\) di lunghezza \(d_i\), e \(i\) precede \(j\). Per induzione la sua lunghezza massima è
\[ \max_{(i,j) \in \delta^-(j)} \big(\mathit{ES}_i+d_i\big)=\max_{(i,j) \in \delta^-(j)} \mathit{EF}_i=\mathit{ES}_j . \] -
Limite inferiore. Per ogni arco \((i,j) \in \delta^-(j)\), per induzione \(t_j \ge t_i+d_i \ge \mathit{ES}_i+d_i=\mathit{EF}_i\); quindi \(t_j \ge \mathit{ES}_j\).
-
\(\mathit{ES}\) è un calendario. \(\mathit{ES}_0=0\), e \(\mathit{ES}_j \ge \mathit{EF}_i=\mathit{ES}_i+d_i\) per ogni arco \((i,j) \in A\), per il massimo nella definizione. □
Teorema 9.9: durata minima del progetto
Sotto le ipotesi (H1) e (H2), la durata minima del progetto è \(T=\mathit{ES}_{n+1}\), la lunghezza di un cammino critico, e il calendario \(\mathit{ES}\) la raggiunge.
Dimostrazione
Per il Teorema 9.8, \(\mathit{ES}\) è un calendario di durata \(\mathit{ES}_{n+1}\), e ogni calendario ha \(t_{n+1} \ge \mathit{ES}_{n+1}\): quindi \(T=\mathit{ES}_{n+1}\). Per lo stesso teorema, \(\mathit{ES}_{n+1}\) è la lunghezza di un cammino massimo da START a FINISH, cioè di un cammino critico. □
-
Usiamo entrambe le ipotesi: (H1) rende le lunghezze dei cammini numeri fissati, e (H2) rende le precedenze gli unici vincoli di un calendario.
-
La passata in avanti è l'algoritmo per i grafi aciclici del Capitolo 3 «Cammini minimi», con il massimo al posto del minimo: con le lunghezze degli archi \(-d_i\), quell'algoritmo calcola le etichette \(d(j)=-\mathit{ES}_j\). Un cammino massimo è facile da trovare perché la rete è aciclica.
Esempio 9.3: la passata in avanti sul caso di studio
Nel caso di studio ogni attività ha predecessori immediati di indice minore, quindi l'ordine topologico è \(0,1,2,\dots,15\). Ogni riga elabora un nodo: le fini al più presto dei suoi predecessori immediati (il massimo in grassetto), poi \(\mathit{ES}_j\) ed \(\mathit{EF}_j\).
| nodo \(j\) | \(d_j\) | \(\mathit{EF}_i\) dei predecessori (\(i\)) | \(\mathit{ES}_j\) | \(\mathit{EF}_j\) |
|---|---|---|---|---|
| \(0\) | \(0\) | — | \(0\) | \(0\) |
| \(1\) | \(2\) | \(\mathbf{0}\) (\(0\)) | \(0\) | \(2\) |
| \(2\) | \(4\) | \(\mathbf{2}\) (\(1\)) | \(2\) | \(6\) |
| \(3\) | \(10\) | \(\mathbf{6}\) (\(2\)) | \(6\) | \(16\) |
| \(4\) | \(6\) | \(\mathbf{16}\) (\(3\)) | \(16\) | \(22\) |
| \(5\) | \(4\) | \(\mathbf{16}\) (\(3\)) | \(16\) | \(20\) |
| \(6\) | \(5\) | \(\mathbf{20}\) (\(5\)) | \(20\) | \(25\) |
| \(7\) | \(7\) | \(\mathbf{22}\) (\(4\)) | \(22\) | \(29\) |
| \(8\) | \(9\) | \(20\) (\(5\)), \(\mathbf{29}\) (\(7\)) | \(29\) | \(38\) |
| \(9\) | \(7\) | \(\mathbf{16}\) (\(3\)) | \(16\) | \(23\) |
| \(10\) | \(8\) | \(\mathbf{25}\) (\(6\)), \(23\) (\(9\)) | \(25\) | \(33\) |
| \(11\) | \(4\) | \(\mathbf{33}\) (\(10\)) | \(33\) | \(37\) |
| \(12\) | \(5\) | \(\mathbf{33}\) (\(10\)) | \(33\) | \(38\) |
| \(13\) | \(2\) | \(\mathbf{38}\) (\(8\)) | \(38\) | \(40\) |
| \(14\) | \(6\) | \(37\) (\(11\)), \(\mathbf{38}\) (\(12\)) | \(38\) | \(44\) |
| \(15\) | \(0\) | \(40\) (\(13\)), \(\mathbf{44}\) (\(14\)) | \(44\) | \(44\) |
Il nodo FINISH dà \(T=\mathit{ES}_{15}=44\): se tutto procede secondo i piani, il progetto si completa in \(44\) settimane. Nella figura, accanto a ogni nodo, la sua durata (in blu) e i suoi tempi al più presto.
La passata in avanti calcola, in ordine topologico, \(\mathit{ES}_j=\max \mathit{EF}_i\) sui predecessori immediati ed \(\mathit{EF}_j=\mathit{ES}_j+d_j\). \(\mathit{ES}_j\) è la lunghezza di un cammino massimo da START a \(j\), e \(T=\mathit{ES}_{n+1}\) è la lunghezza di un cammino critico.