Vai al contenuto

9.3 La passata in avanti: i tempi al più presto

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

\[ \mathit{ES}_0=0, \qquad \mathit{ES}_j=\max_{(i,j) \in \delta^-(j)} \mathit{EF}_i, \quad \forall j \in N \setminus \{0\}, \qquad \mathit{EF}_j=\mathit{ES}_j+d_j, \quad \forall j \in N . \]
  • È 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.

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

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

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

Figura 2

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.


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