9.5 Scorte e attività critiche¶
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)
Definizione 9.12: scorte e archi stretti
Per ogni attività \(j \in \{1,2,\dots,n\}\):
-
la scorta totale è \(\mathit{TS}_j=\mathit{LS}_j-\mathit{ES}_j=\mathit{LF}_j-\mathit{EF}_j\);
-
la scorta libera è \(\mathit{FS}_j=\min_{(j,k) \in \delta^+(j)} \mathit{ES}_k-\mathit{EF}_j\).
Un arco \((i,j) \in A\) è stretto se \(\mathit{ES}_j=\mathit{EF}_i\).
-
Le due differenze in \(\mathit{TS}_j\) coincidono, perché in entrambe le coppie i due tempi differiscono di \(d_j\).
-
La scorta totale è il ritardo dell'attività \(j\) che non ritarda il progetto; la scorta libera è il ritardo che non sposta l'inizio al più presto di nessun'altra attività. I due risultati che seguono lo rendono preciso.
Teorema 9.13: scorta totale e attività critiche
Per ogni attività \(j\), sia \(L_j\) la lunghezza massima di un cammino da START a FINISH che passa per \(j\). Allora:
-
(a) \(\mathit{TS}_j=T-L_j \ge 0\), quindi \(\mathit{TS}_j=0\) se e solo se \(j\) è critica;
-
(b) per ogni \(\delta\) con \(0 \le \delta \le \mathit{TS}_j\) esiste un calendario di durata \(T\) con \(t_j=\mathit{ES}_j+\delta\), e nessun calendario di durata \(T\) ha \(t_j>\mathit{ES}_j+\mathit{TS}_j\).
Dimostrazione
-
Un cammino da START a FINISH che passa per \(j\) è un cammino da START a \(j\) seguito da un cammino da \(j\) a FINISH, e la sua lunghezza è la somma delle due lunghezze. Prendendo i più lunghi, per il Teorema 9.8 e il Teorema 9.11,
\[ L_j=\mathit{ES}_j+\big(T-\mathit{LS}_j\big)=T-\mathit{TS}_j . \] -
Ogni cammino da START a FINISH ha lunghezza al più \(T\), quindi \(\mathit{TS}_j \ge 0\), con l'uguaglianza se e solo se un cammino che passa per \(j\) ha lunghezza \(T\), cioè se \(j\) è critica.
-
Se \(\mathit{TS}_j>0\), sia \(\lambda=\delta/\mathit{TS}_j \in [0,1]\). \(\mathit{ES}\) e \(\mathit{LS}\) sono calendari di durata \(T\), e i vincoli di un calendario sono lineari, quindi \((1-\lambda)\mathit{ES}+\lambda\mathit{LS}\) è un calendario di durata \(T\), con \(t_j=\mathit{ES}_j+\lambda\,\mathit{TS}_j=\mathit{ES}_j+\delta\). Se \(\mathit{TS}_j=0\), allora \(\delta=0\) e basta \(\mathit{ES}\).
-
Per il Teorema 9.11, ogni calendario di durata \(T\) ha \(t_j \le \mathit{LS}_j=\mathit{ES}_j+\mathit{TS}_j\). □
Proposizione 9.14: scorta libera
Per ogni attività \(j\), \(0 \le \mathit{FS}_j \le \mathit{TS}_j\). Inoltre, per ogni \(\delta\) con \(0 \le \delta \le \mathit{FS}_j\), i tempi di inizio \(\mathit{ES}\) con \(\mathit{ES}_j+\delta\) al posto di \(\mathit{ES}_j\) formano un calendario di durata \(T\): l'attività \(j\) è ritardata di \(\delta\), e ogni altro nodo mantiene il suo inizio al più presto.
Dimostrazione
-
Per la passata in avanti, \(\mathit{ES}_k \ge \mathit{EF}_j\) per ogni arco \((j,k)\), quindi \(\mathit{FS}_j \ge 0\). Inoltre \(\mathit{ES}_k \le \mathit{LS}_k\) per ogni nodo \(k\): per le attività vale per il Teorema 9.13, e \(\mathit{ES}_{n+1}=\mathit{LS}_{n+1}=T\). Quindi
\[ \mathit{FS}_j=\min_{(j,k) \in \delta^+(j)} \mathit{ES}_k-\mathit{EF}_j \le \min_{(j,k) \in \delta^+(j)} \mathit{LS}_k-\mathit{EF}_j=\mathit{LF}_j-\mathit{EF}_j=\mathit{TS}_j . \] -
Cambiano solo i vincoli degli archi di \(j\). Per \((i,j) \in \delta^-(j)\): \(\mathit{ES}_j+\delta \ge \mathit{ES}_j \ge \mathit{EF}_i\). Per \((j,k) \in \delta^+(j)\): \(\mathit{ES}_k \ge \mathit{EF}_j+\mathit{FS}_j \ge (\mathit{ES}_j+\delta)+d_j\).
-
La durata è ancora \(\mathit{ES}_{n+1}=T\), perché \(j \neq n+1\). □
Teorema 9.15: i cammini critici sono cammini di archi stretti
Un cammino \(P\) da START a FINISH è critico se e solo se tutti i suoi archi sono stretti.
Dimostrazione
Sia \(P=i_0,i_1,\dots,i_k\) con \(i_0=0\) e \(i_k=n+1\). Ogni arco ha \(\mathit{ES}_{i_{s+1}}-\mathit{EF}_{i_s} \ge 0\). Sommando sugli archi di \(P\), gli inizi al più presto si elidono a catena:
Una somma di termini non negativi è nulla se e solo se ogni termine è nullo: \(L(P)=T\) se e solo se ogni arco di \(P\) è stretto. □
-
I cammini critici sono i cammini da START a FINISH che usano solo archi stretti: per elencarli tutti, si seguono gli archi stretti a partire da START.
-
Ogni attività di un cammino critico ha scorta totale nulla. Un cammino fatto di attività critiche, invece, è critico solo se i suoi archi sono stretti.
Esempio 9.5: scorte e cammino critico del caso di studio
Per mostrare tutti i tempi insieme, scriviamo accanto a ogni nodo la coppia \(\mathrm{S}=(\mathit{ES}_j,\mathit{LS}_j)\) dei suoi tempi di inizio e la coppia \(\mathrm{F}=(\mathit{EF}_j,\mathit{LF}_j)\) dei suoi tempi di fine, come nella figura per l'attività \(13\):
La tabella raccoglie i tempi e le scorte delle attività dell'Esempio 9.3 e dell'Esempio 9.4.
| \(j\) | \(d_j\) | \(\mathit{ES}_j\) | \(\mathit{EF}_j\) | \(\mathit{LS}_j\) | \(\mathit{LF}_j\) | \(\mathit{TS}_j\) | \(\mathit{FS}_j\) | critica |
|---|---|---|---|---|---|---|---|---|
| \(1\) | \(2\) | \(0\) | \(2\) | \(0\) | \(2\) | \(0\) | \(0\) | sì |
| \(2\) | \(4\) | \(2\) | \(6\) | \(2\) | \(6\) | \(0\) | \(0\) | sì |
| \(3\) | \(10\) | \(6\) | \(16\) | \(6\) | \(16\) | \(0\) | \(0\) | sì |
| \(4\) | \(6\) | \(16\) | \(22\) | \(20\) | \(26\) | \(4\) | \(0\) | |
| \(5\) | \(4\) | \(16\) | \(20\) | \(16\) | \(20\) | \(0\) | \(0\) | sì |
| \(6\) | \(5\) | \(20\) | \(25\) | \(20\) | \(25\) | \(0\) | \(0\) | sì |
| \(7\) | \(7\) | \(22\) | \(29\) | \(26\) | \(33\) | \(4\) | \(0\) | |
| \(8\) | \(9\) | \(29\) | \(38\) | \(33\) | \(42\) | \(4\) | \(0\) | |
| \(9\) | \(7\) | \(16\) | \(23\) | \(18\) | \(25\) | \(2\) | \(2\) | |
| \(10\) | \(8\) | \(25\) | \(33\) | \(25\) | \(33\) | \(0\) | \(0\) | sì |
| \(11\) | \(4\) | \(33\) | \(37\) | \(34\) | \(38\) | \(1\) | \(1\) | |
| \(12\) | \(5\) | \(33\) | \(38\) | \(33\) | \(38\) | \(0\) | \(0\) | sì |
| \(13\) | \(2\) | \(38\) | \(40\) | \(42\) | \(44\) | \(4\) | \(4\) | |
| \(14\) | \(6\) | \(38\) | \(44\) | \(38\) | \(44\) | \(0\) | \(0\) | sì |
-
Le attività critiche sono \(1,2,3,5,6,10,12,14\). Gli archi stretti a partire da START arrivano a FINISH solo lungo START\(,1,2,3,5,6,10,12,14,\)FINISH: il cammino critico è unico, e la sua lunghezza è \(T=44\) (in blu nella figura).
-
Le attività \(4,7,8,13\) formano una catena con \(\mathit{TS}_{4}=\mathit{TS}_{7}=\mathit{TS}_{8}=\mathit{TS}_{13}=4\), ma solo l'ultima ha scorta libera, \(\mathit{FS}_{13}=4\). Se l'attività \(4\) inizia con \(4\) settimane di ritardo, anche le attività \(7\), \(8\), \(13\) devono iniziare con \(4\) settimane di ritardo, e il progetto termina comunque alla settimana \(44\).
-
Le attività \(9\) e \(11\) hanno scorta totale uguale alla scorta libera, rispettivamente \(2\) settimane e \(1\) settimana.
Le scorte totali sono condivise
La scorta totale di un'attività è condivisa con le altre attività dei suoi cammini: le quattro scorte totali della catena \(4,7,8,13\) sono le stesse \(4\) settimane. Se l'attività \(4\) dura \(3\) settimane in più e l'attività \(8\) dura \(2\) settimane in più, il cammino che passa per entrambe si allunga di \(5>4\) settimane, e il progetto termina alla settimana \(45\).
La scorta totale \(\mathit{TS}_j=\mathit{LS}_j-\mathit{ES}_j\) è il ritardo di \(j\) che non ritarda il progetto; la scorta libera \(\mathit{FS}_j \le \mathit{TS}_j\) è il ritardo che non sposta nessun'altra attività. Le attività critiche hanno \(\mathit{TS}_j=0\), e i cammini critici sono i cammini da START a FINISH fatti di archi stretti.