9.3 Il passaggio in avanti: i primi tempi¶
Parte 5 · Gestione dei progetti · Capitolo 9 · Capitolo 9: Gestione dei progetti · Dispensa, volume 5 (PDF) · Esercizi: Gestione dei progetti
- Assumiamo innanzitutto che non si verifichi alcun ritardo: ogni attività assume la sua durata stimata e inizia non appena i suoi immediati predecessori sono finiti.
Definizione 9.7: primi orari di inizio e fine
Sia \(v_0,v_1,\dots,v_{n+1}\) un ordine topologico della rete del progetto. prima ora di inizio \(\mathit{ES}_j\) e prima ora di fine \(\mathit{EF}_j\) dei nodi vengono calcolati in questo ordine dal passaggio in avanti:
-
Questa è la regola dell'ora di inizio più remota: la prima ora di inizio di un'attività è la prima tempo di fine dei suoi immediati predecessori. Quando il nodo \(j\) viene elaborato, i suoi predecessori lo precedono nel file ordine topologico, quindi sono noti i primi tempi di fine.
-
Come in Capitolo 3, l'ordine topologico rimuove, ad ogni passo, il nodo senza inserire archi di indice più piccolo. Il nodo \(0\) viene rimosso per primo.
Teorema 9.8: primi tempi
Per ogni nodo \(j \in N\), \(\mathit{ES}_j\) è la lunghezza del percorso più lungo da START a \(j\). Inoltre, \(\mathit{ES}\) è un programma, e ogni programma \(\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\). Nessun arco entra in START: l'unico percorso da START a \(0\) non ha archi e ha lunghezza \(0=\mathit{ES}_0\) e ogni pianificazione ha \(t_0=0=\mathit{ES}_0\).
-
Percorsi più lunghi. Lascia \(j \neq 0\). Ogni percorso da START a \(j\) è un percorso da START ad alcuni \(i\) seguito da un arco \((i,j) \in \delta^-(j)\) di lunghezza \(d_i\) e \(i\) viene prima di \(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}\) è una pianificazione. \(\mathit{ES}_0=0\) e \(\mathit{ES}_j \ge \mathit{EF}_i=\mathit{ES}_i+d_i\) per ogni arco \((i,j) \in A\), dal massimo nella definizione. □
Teorema 9.9: durata minima del progetto
In (H1) e (H2), la durata minima del progetto è \(T=\mathit{ES}_{n+1}\), la lunghezza di un percorso critico e la pianificazione \(\mathit{ES}\) ci riesce.
Dimostrazione
Per Teorema 9.8, \(\mathit{ES}\) è un programma di durata \(\mathit{ES}_{n+1}\), e ogni programma 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 del percorso più lungo dall'INIZIO alla FINE, cioè di un percorso critico. □
-
Vengono utilizzate entrambe le ipotesi: (H1) rende fisse le lunghezze dei percorsi e (H2) rende le precedenze gli unici vincoli di un programma.
-
Il passaggio in avanti è l'algoritmo per i grafi aciclici di Capitolo 3 «Il più breve percorsi», con il massimo al posto del minimo: con le lunghezze dell'arco \(-d_i\), quell'algoritmo calcola le etichette \(d(j)=-\mathit{ES}_j\). Un percorso più lungo è facile da trovare perché la rete è aciclica.
Esempio 9.3: il passaggio in avanti del caso di studio
Nel caso di studio ogni attività ha predecessori immediati di indice più piccolo, così è l'ordine topologico \(0,1,2,\dots,15\). Ogni riga elabora un nodo: i primi tempi di fine dei suoi immediati predecessori (il massimo in grassetto), quindi \(\mathit{ES}_j\) e \(\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 FINITURA dà \(T=\mathit{ES}_{15}=44\): se tutto rispetta i tempi previsti, il progetto viene completato in \(44\) settimane. Dentro la figura, accanto a ciascun nodo, la sua durata (blu) e i suoi primi tempi.
Il passaggio in avanti calcola, in ordine topologico, \(\mathit{ES}_j=\max \mathit{EF}_i\) rispetto ai predecessori immediati e \(\mathit{EF}_j=\mathit{ES}_j+d_j\). \(\mathit{ES}_j\) è la lunghezza del percorso più lungo da START a \(j\) e \(T=\mathit{ES}_{n+1}\) è la lunghezza di un percorso critico.