Vai al contenuto

9.4 Il passaggio all'indietro: ultimi tempi

Parte 5 · Gestione dei progetti · Capitolo 9 · Capitolo 9: Gestione dei progetti · Dispensa, volume 5 (PDF) · Esercizi: Gestione dei progetti

  • Quanto tempo dopo \(\mathit{ES}_j\) può iniziare un'attività senza ritardare il progetto? Gli ultimi tempi rispondono, presupponendo che non si verifichi nessun altro ritardo.

Definizione 9.10: ultimi orari di inizio e fine

Lascia che \(T=\mathit{ES}_{n+1}\). ultima ora di fine \(\mathit{LF}_j\) e ultima ora di inizio \(\mathit{LS}_j\) dei nodi vengono calcolati nell'ordine topologico inverso da passaggio 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 . \]
  • Questa è la regola dell'ultima ora di fine: l'ultima ora di fine di un'attività è la più piccola ora di inizio dei suoi immediati successori. Gli immediati successori non potranno iniziare prima che l'attività sia terminata, quindi l'attività deve terminare in tempo affinché tutte possano iniziare entro l'ultimo orario di inizio.

Teorema 9.11: ultimi orari

Per ogni nodo \(j \in N\), \(T-\mathit{LS}_j\) è la lunghezza del percorso più lungo da \(j\) a FINISH. Inoltre, \(\mathit{LS}\) è un programma di durata \(T\), e ogni programma \(\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 percorso da \(n+1\) a FINISH ha lunghezza \(0=T-\mathit{LS}_{n+1}\) e \(t_{n+1} \le T=\mathit{LS}_{n+1}\).

  2. Percorsi più lunghi. Lascia \(j \neq n+1\). Ogni percorso da \(j\) a FINISH è un arco \((j,k) \in \delta^+(j)\), di lunghezza \(d_j\), seguito da un percorso 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}\) è una pianificazione. \(\mathit{LS}_k \ge \mathit{LF}_j=\mathit{LS}_j+d_j\) per ogni arco \((j,k) \in A\), dal minimo nel definizione. Inoltre \(\mathit{LS}_{n+1}=T\) e \(\mathit{LS}_0=T-T=0\), poiché il percorso più lungo da INIZIO a FINE ha lunghezza \(T\). □

  • In ogni programma di durata \(T\), il nodo \(j\) inizia tra \(\mathit{ES}_j\) e \(\mathit{LS}_j\) ed entrambi gli estremi sono raggiunto, secondo gli orari \(\mathit{ES}\) e \(\mathit{LS}\).

Esempio 9.4: il passaggio all'indietro sul caso di studio

Il passaggio all'indietro elabora i nodi nell'ordine \(15,14,\dots,0\). Ogni riga fornisce gli ultimi orari di inizio del successori immediati (il minimo in grassetto), quindi \(\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\)

Il passaggio termina con \(\mathit{LS}_0=0\), come previsto da Teorema 9.11. Ad 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 la prima ora di inizio \(\mathit{ES}_9=16\). Nella figura, accanto ad ogni nodo, la sua durata (blu) e i suoi ultimi tempi.

Figura 3

Il passaggio all'indietro calcola, in ordine topologico inverso, \(\mathit{LF}_j=\min \mathit{LS}_k\) sugli immediati successori e \(\mathit{LS}_j=\mathit{LF}_j-d_j\), a partire da \(\mathit{LF}_{n+1}=T\). \(T-\mathit{LS}_j\) è la lunghezza del percorso più lungo da \(j\) a FINISH e in ogni programma di durata \(T\) il nodo \(j\) inizia tra \(\mathit{ES}_j\) e \(\mathit{LS}_j\).

Avanti: 9.5 Margini e attività critiche