9.4 La passata all'indietro: i tempi al più tardi¶
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)
- Quanto dopo \(\mathit{ES}_j\) può iniziare un'attività senza ritardare il progetto? Rispondono i tempi al più tardi, supponendo che non ci siano altri ritardi.
Definizione 9.10: tempi di inizio e di fine al più tardi
Sia \(T=\mathit{ES}_{n+1}\). La fine al più tardi \(\mathit{LF}_j\) e l'inizio al più tardi \(\mathit{LS}_j\) dei nodi si calcolano nell'ordine topologico inverso con la passata all'indietro:
- È la regola della fine al più tardi: la fine al più tardi di un'attività è il minimo inizio al più tardi dei suoi successori immediati. I successori immediati non possono iniziare prima che l'attività sia terminata, quindi l'attività deve terminare in tempo perché tutti possano iniziare entro il loro inizio al più tardi.
Teorema 9.11: tempi al più tardi
Per ogni nodo \(j \in N\), \(T-\mathit{LS}_j\) è la lunghezza di un cammino massimo da \(j\) a FINISH. Inoltre \(\mathit{LS}\) è un calendario di durata \(T\), e ogni calendario \(\vet{t}\) con \(t_{n+1} \le T\) soddisfa \(t_j \le \mathit{LS}_j\) per ogni \(j \in N\).
Dimostrazione
Dimostriamo la prima e l'ultima affermazione per induzione lungo l'ordine topologico inverso.
-
Nodo \(n+1\). L'unico cammino da \(n+1\) a FINISH ha lunghezza \(0=T-\mathit{LS}_{n+1}\), e \(t_{n+1} \le T=\mathit{LS}_{n+1}\).
-
Cammini massimi. Sia \(j \neq n+1\). Ogni cammino da \(j\) a FINISH è un arco \((j,k) \in \delta^+(j)\), di lunghezza \(d_j\), seguito da un cammino da \(k\) a FINISH. Per induzione la sua lunghezza massima è
\[ d_j+\max_{(j,k) \in \delta^+(j)} \big(T-\mathit{LS}_k\big)=d_j+T-\mathit{LF}_j=T-\mathit{LS}_j . \] -
Limite superiore. Per ogni arco \((j,k) \in \delta^+(j)\), per induzione \(t_j \le t_k-d_j \le \mathit{LS}_k-d_j\); quindi \(t_j \le \mathit{LF}_j-d_j=\mathit{LS}_j\).
-
\(\mathit{LS}\) è un calendario. \(\mathit{LS}_k \ge \mathit{LF}_j=\mathit{LS}_j+d_j\) per ogni arco \((j,k) \in A\), per il minimo nella definizione. Inoltre \(\mathit{LS}_{n+1}=T\), e \(\mathit{LS}_0=T-T=0\), perché un cammino massimo da START a FINISH ha lunghezza \(T\). □
- In ogni calendario di durata \(T\), il nodo \(j\) inizia fra \(\mathit{ES}_j\) e \(\mathit{LS}_j\), ed entrambi gli estremi sono raggiunti, dai calendari \(\mathit{ES}\) e \(\mathit{LS}\).
Esempio 9.4: la passata all'indietro sul caso di studio
La passata all'indietro elabora i nodi nell'ordine \(15,14,\dots,0\). Ogni riga riporta gli inizi al più tardi dei successori immediati (il minimo in grassetto), poi \(\mathit{LF}_j\) e \(\mathit{LS}_j\).
| nodo \(j\) | \(d_j\) | \(\mathit{LS}_k\) dei successori (\(k\)) | \(\mathit{LF}_j\) | \(\mathit{LS}_j\) |
|---|---|---|---|---|
| \(15\) | \(0\) | — | \(44\) | \(44\) |
| \(14\) | \(6\) | \(\mathbf{44}\) (\(15\)) | \(44\) | \(38\) |
| \(13\) | \(2\) | \(\mathbf{44}\) (\(15\)) | \(44\) | \(42\) |
| \(12\) | \(5\) | \(\mathbf{38}\) (\(14\)) | \(38\) | \(33\) |
| \(11\) | \(4\) | \(\mathbf{38}\) (\(14\)) | \(38\) | \(34\) |
| \(10\) | \(8\) | \(34\) (\(11\)), \(\mathbf{33}\) (\(12\)) | \(33\) | \(25\) |
| \(9\) | \(7\) | \(\mathbf{25}\) (\(10\)) | \(25\) | \(18\) |
| \(8\) | \(9\) | \(\mathbf{42}\) (\(13\)) | \(42\) | \(33\) |
| \(7\) | \(7\) | \(\mathbf{33}\) (\(8\)) | \(33\) | \(26\) |
| \(6\) | \(5\) | \(\mathbf{25}\) (\(10\)) | \(25\) | \(20\) |
| \(5\) | \(4\) | \(\mathbf{20}\) (\(6\)), \(33\) (\(8\)) | \(20\) | \(16\) |
| \(4\) | \(6\) | \(\mathbf{26}\) (\(7\)) | \(26\) | \(20\) |
| \(3\) | \(10\) | \(20\) (\(4\)), \(\mathbf{16}\) (\(5\)), \(18\) (\(9\)) | \(16\) | \(6\) |
| \(2\) | \(4\) | \(\mathbf{6}\) (\(3\)) | \(6\) | \(2\) |
| \(1\) | \(2\) | \(\mathbf{2}\) (\(2\)) | \(2\) | \(0\) |
| \(0\) | \(0\) | \(\mathbf{0}\) (\(1\)) | \(0\) | \(0\) |
La passata termina con \(\mathit{LS}_0=0\), come prevede il Teorema 9.11. Per esempio, l'attività \(9\) deve terminare entro \(\mathit{LF}_9=\mathit{LS}_{10}=25\), quindi deve iniziare entro \(\mathit{LS}_9=18\), due settimane dopo il suo inizio al più presto \(\mathit{ES}_9=16\). Nella figura, accanto a ogni nodo, la sua durata (in blu) e i suoi tempi al più tardi.
La passata all'indietro calcola, in ordine topologico inverso, \(\mathit{LF}_j=\min \mathit{LS}_k\) sui successori immediati e \(\mathit{LS}_j=\mathit{LF}_j-d_j\), partendo da \(\mathit{LF}_{n+1}=T\). \(T-\mathit{LS}_j\) è la lunghezza di un cammino massimo da \(j\) a FINISH, e in ogni calendario di durata \(T\) il nodo \(j\) inizia fra \(\mathit{ES}_j\) e \(\mathit{LS}_j\).
Avanti: 9.5 Scorte e attività critiche