Vai al contenuto

9.4 La passata all'indietro: i tempi al più tardi

  • 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:

\[ \mathit{LF}_{n+1}=T, \qquad \mathit{LF}_j=\min_{(j,k) \in \delta^+(j)} \mathit{LS}_k, \quad \forall j \in N \setminus \{n+1\}, \qquad \mathit{LS}_j=\mathit{LF}_j-d_j, \quad \forall j \in N . \]
  • È 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.

  1. 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}\).

  2. 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 . \]
  3. 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\).

  4. \(\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.

Figura 3

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