9.5 Margini e attività critiche¶
Parte 5 · Gestione dei progetti · Capitolo 9 · Capitolo 9: Gestione dei progetti · Dispensa, volume 5 (PDF) · Esercizi: Gestione dei progetti
Definizione 9.12: allentamenti e archi stretti
Per ogni attività \(j \in \{1,2,\dots,n\}\):
-
margine totale è \(\mathit{TS}_j=\mathit{LS}_j-\mathit{ES}_j=\mathit{LF}_j-\mathit{EF}_j\);
-
margine libero è \(\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, poiché entrambe le coppie di orari differiscono per \(d_j\).
-
Il margine di flessibilità totale è il ritardo dell'attività \(j\) che non ritarda il progetto; il margine libero è il ritardo che non sposta la prima ora di inizio di qualsiasi altra attività. I due risultati seguenti precisano queste definizioni.
Teorema 9.13: attività critiche e flessibilità totali
Per ogni attività \(j\), sia \(L_j\) la lunghezza massima di un percorso dall'INIZIO alla FINE attraverso \(j\). Quindi:
-
(a) \(\mathit{TS}_j=T-L_j \ge 0\), quindi \(\mathit{TS}_j=0\) se e solo se \(j\) è critico;
-
(b) per ogni \(\delta\) con \(0 \le \delta \le \mathit{TS}_j\) è previsto un programma di durata \(T\) con \(t_j=\mathit{ES}_j+\delta\) e nessun programma di durata \(T\) ha \(t_j>\mathit{ES}_j+\mathit{TS}_j\).
Dimostrazione
-
Un percorso da INIZIO a FINE attraverso \(j\) è un percorso da INIZIO a \(j\) seguito da un percorso da \(j\) a FINE e la sua lunghezza è la somma delle due lunghezze. Prendendo quelli più lunghi, di Teorema 9.8 e Teorema 9.11,
\[ L_j=\mathit{ES}_j+\big(T-\mathit{LS}_j\big)=T-\mathit{TS}_j . \] -
Ogni percorso da INIZIO a FINE ha lunghezza al massimo \(T\), quindi \(\mathit{TS}_j \ge 0\), con uguaglianza se e solo se un percorso fino a \(j\) ha lunghezza \(T\), ovvero \(j\) è critico.
-
Se \(\mathit{TS}_j>0\), lascia \(\lambda=\delta/\mathit{TS}_j \in [0,1]\). \(\mathit{ES}\) e \(\mathit{LS}\) sono orari di durata \(T\), e il i vincoli di una pianificazione sono lineari, quindi \((1-\lambda)\mathit{ES}+\lambda\mathit{LS}\) è una pianificazione 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 \(\mathit{ES}\) funzionano.
-
Per Teorema 9.11, ogni programma di durata \(T\) ha \(t_j \le \mathit{LS}_j=\mathit{ES}_j+\mathit{TS}_j\). □
Proposizione 9.14: lasco libero
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\), il gli orari di inizio \(\mathit{ES}\) con \(\mathit{ES}_j+\delta\) al posto di \(\mathit{ES}_j\) formano un programma di durata \(T\): l'attività \(j\) è ritardata di \(\delta\) e ogni altro nodo mantiene la prima ora di inizio.
Dimostrazione
-
Con il passaggio 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\), da Teorema 9.13 per le attività e da allora \(\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\). For \((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\), da \(j \neq n+1\). □
Teorema 9.15: i percorsi critici sono percorsi di archi stretti
Un percorso \(P\) dall'INIZIO alla FINE è critico se e solo se tutti i suoi archi sono stretti.
Dimostrazione
Lascia che \(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 oltre gli archi di \(P\), il telescopio con i primi tempi di inizio:
Una somma di termini non negativi è zero se e solo se ogni termine è zero: \(L(P)=T\) se e solo se ogni arco di \(P\) è stretto. □
-
I percorsi critici sono i percorsi da INIZIO a FINE che utilizzano solo archi stretti: per elencarli tutti seguire gli archi stretti da START.
-
Ogni attività di un percorso critico ha un margine di flessibilità totale pari a zero. Un percorso fatto di attività critiche, invece, lo è critico solo se i suoi archi sono stretti.
Esempio 9.5: pantaloni e percorso critico del caso studio
Per mostrare tutti gli orari contemporaneamente scriviamo accanto a ciascun nodo la coppia \(\mathrm{S}=(\mathit{ES}_j,\mathit{LS}_j)\) dei suoi orari di inizio e la coppia \(\mathrm{F}=(\mathit{EF}_j,\mathit{LF}_j)\) dei suoi tempi di arrivo, come nella figura dell'attività \(13\):
La tabella raccoglie gli orari ed i tempi delle attività di Esempio 9.3 e Esempio 9.4.
| \(j\) | \(d_j\) | \(\mathit{ES}_j\) | \(\mathit{EF}_j\) | \(\mathit{LS}_j\) | \(\mathit{LF}_j\) | \(\mathit{TS}_j\) | \(\mathit{FS}_j\) | critico |
|---|---|---|---|---|---|---|---|---|
| \(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 dall'INIZIO raggiungono la FINE solo lungo START\(,1,2,3,5,6,10,12,14,\)FINISH: il percorso critico è unico e la sua lunghezza è \(T=44\) (blu in 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 margine libero, \(\mathit{FS}_{13}=4\). Se l'attività \(4\) inizia \(4\) con settimane di ritardo, le attività \(7\), \(8\), \(13\) devono iniziare \(4\) con settimane di ritardo anche, e il progetto termina ancora alla settimana \(44\).
-
Le attività \(9\) e \(11\) hanno lo stesso margine di flessibilità totale e libero delle settimane \(2\) e \(1\).
I margini totali sono condivisi
Il margine totale di un'attività è condiviso con le altre attività dello stesso percorso. Le attività della catena \(4,7,8,13\) hanno ciascuna un margine totale di \(4\) settimane. Se l'attività \(4\) dura \(3\) settimane in più e l'attività \(8\) dura \(2\) settimane in più, il ritardo complessivo lungo la catena è \(5>4\) settimane e il progetto termina alla settimana \(45\).
Il margine di flessibilità totale \(\mathit{TS}_j=\mathit{LS}_j-\mathit{ES}_j\) è il ritardo di \(j\) che non ritarda il progetto; il margine libero \(\mathit{FS}_j \le \mathit{TS}_j\) è il ritardo che non sposta nessun'altra attività. Le attività critiche hanno \(\mathit{TS}_j=0\) e il i percorsi critici sono i percorsi dall'INIZIO alla FINE costituiti da archi stretti.