9.1 Progetti e reti delle attività¶
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.1: progetto
Un progetto è un insieme di \(n\) attività, numerate \(1,2,\dots,n\), con i seguenti dati.
-
Ogni attività \(j\) ha una durata \(d_j \in \Q_{>0}\).
-
Alcune coppie \((i,j)\) di attività sono precedenze: l'attività \(i\) è un predecessore immediato dell'attività \(j\), e \(j\) può iniziare solo quando \(i\) è terminata. Un'attività con più predecessori immediati può iniziare solo quando sono terminati tutti.
-
Per descrivere un progetto servono tre tipi di informazioni: le attività, al livello di dettaglio desiderato; le precedenze, cioè i predecessori immediati di ogni attività; le durate, cioè una stima del tempo richiesto da ogni attività.
-
In tutto il capitolo facciamo due ipotesi:
-
(H1) le durate sono deterministiche: ogni attività dura esattamente la sua durata stimata \(d_j\), senza interruzioni;
-
(H2) le risorse sono illimitate: le attività non legate da precedenze possono svolgersi contemporaneamente.
-
-
Il metodo di questo capitolo è il metodo del cammino critico (CPM, critical path method). È stato sviluppato alla fine degli anni Cinquanta, indipendentemente dalla tecnica PERT (program evaluation and review technique), e i due nomi sono spesso uniti in PERT/CPM.
Definizione 9.2: rete delle attività
La rete delle attività di un progetto con \(n\) attività è il grafo orientato \(G=(N,A)\) con \(N=\{0,1,\dots,n+1\}\) e i seguenti nodi e archi.
-
Il nodo \(j \in \{1,2,\dots,n\}\) è l'attività \(j\). Il nodo \(0\) è il nodo START e il nodo \(n+1\) è il nodo FINISH, con durate \(d_0=d_{n+1}=0\).
-
\(A\) contiene l'arco \((i,j)\) per ogni precedenza, l'arco \((0,j)\) per ogni attività \(j\) senza predecessori immediati e l'arco \((j,n+1)\) per ogni attività \(j\) che non è predecessore immediato di nessuna attività.
-
Questa è la rete activity-on-node (AON): le attività sono i nodi, e gli archi indicano solo le precedenze. Nella rete activity-on-arc (AOA) ogni attività è un arco, e un nodo separa un'attività dai suoi predecessori immediati.
-
La rete AON è più facile da costruire, più facile da leggere per chi non ha esperienza e più facile da aggiornare quando il progetto cambia: usiamo sempre questa, e la chiamiamo semplicemente rete delle attività.
-
In pratica la rete delle attività è costruita da un software di gestione dei progetti a partire dall'elenco delle attività.
Esempio 9.1: il caso di studio
Un'impresa edile deve programmare le squadre che svolgono le \(14\) attività di un progetto di costruzione. La tabella riporta, per ogni attività, i predecessori immediati e la durata stimata.
| attività \(j\) | descrizione | predecessori immediati | \(d_j\) |
|---|---|---|---|
| \(1\) | Scavare | — | \(2\) settimane |
| \(2\) | Gettare le fondamenta | \(1\) | \(4\) settimane |
| \(3\) | Erigere i muri grezzi | \(2\) | \(10\) settimane |
| \(4\) | Costruire il tetto | \(3\) | \(6\) settimane |
| \(5\) | Installare l'impianto idraulico esterno | \(3\) | \(4\) settimane |
| \(6\) | Installare l'impianto idraulico interno | \(5\) | \(5\) settimane |
| \(7\) | Montare il rivestimento esterno | \(4\) | \(7\) settimane |
| \(8\) | Eseguire la tinteggiatura esterna | \(5\), \(7\) | \(9\) settimane |
| \(9\) | Eseguire l'impianto elettrico | \(3\) | \(7\) settimane |
| \(10\) | Montare le pareti in cartongesso | \(6\), \(9\) | \(8\) settimane |
| \(11\) | Posare i pavimenti | \(10\) | \(4\) settimane |
| \(12\) | Eseguire la tinteggiatura interna | \(10\) | \(5\) settimane |
| \(13\) | Installare le finiture esterne | \(8\) | \(2\) settimane |
| \(14\) | Installare le finiture interne | \(11\), \(12\) | \(6\) settimane |
Sommando le durate si ottiene un totale di \(79\) settimane. Più attività possono svolgersi contemporaneamente, e questo può ridurre di molto la durata del progetto. La rete delle attività ha i \(16\) nodi \(0,1,\dots,15\) e \(19\) archi; accanto a ogni nodo, in blu, la sua durata.
L'attività \(1\) è l'unica senza predecessori immediati, quindi da START esce il solo arco \((0,1)\); le attività \(13\) e \(14\) non sono predecessori immediati di nessuna attività, quindi entrano in FINISH.
9.1.1 Calendari e reti acicliche¶
Definizione 9.3: calendario
Un calendario di un progetto è un vettore \(\vet{t}=(t_0,t_1,\dots,t_{n+1})\) di tempi di inizio con \(t_0=0\) e
Il nodo \(j\) inizia al tempo \(t_j\) e termina al tempo \(t_j+d_j\). La durata del calendario è \(t_{n+1}\), e la durata minima del progetto \(T\) è la minima durata di un calendario.
-
Il vincolo dell'arco \((i,j)\) dice che \(j\) inizia dopo che \(i\) è terminata. Per (H1) e (H2), le precedenze sono gli unici vincoli di un calendario.
-
Gli archi \((j,n+1)\) fanno iniziare FINISH dopo che tutte le attività sono terminate: \(t_{n+1}\) è il tempo di completamento del progetto.
Proposizione 9.4: un calendario richiede una rete aciclica
Un progetto ha un calendario se e solo se la sua rete delle attività è aciclica.
Dimostrazione
Nessun arco entra nel nodo \(0\) e nessun arco esce dal nodo \(n+1\), quindi ogni ciclo orientato di \(G\) è formato da attività.
-
Siano \(i_0,i_1,\dots,i_k=i_0\) un ciclo orientato e \(\vet{t}\) un calendario. Sommando i vincoli dei suoi archi, i tempi di inizio si elidono a catena (somma telescopica):
\[ 0=t_{i_k}-t_{i_0} \ge \sum_{s=0}^{k-1} d_{i_s} >0, \]una contraddizione, perché le durate delle attività sono positive.
-
Sia \(G\) aciclico, e sia \(v_0,v_1,\dots,v_{n+1}\) un ordine topologico (Capitolo 3, Proposizione «ordini topologici») con \(v_0=0\): il nodo \(0\) non ha archi entranti e può essere tolto per primo. Siano \(D\) la durata massima e \(t_{v_a}=a\,D\) per ogni \(a\).
-
Allora \(t_0=0\), e ogni arco \((v_a,v_b)\) va in avanti, \(a<b\), quindi \(t_{v_b}-t_{v_a}=(b-a)\,D \ge D \ge d_{v_a}\): \(\vet{t}\) è un calendario. □
-
D'ora in poi la rete delle attività è aciclica. Allora ogni attività sta su un cammino da START a FINISH: risalendo gli archi all'indietro si arriva a un nodo senza predecessori immediati, che è collegato a START, e seguendoli in avanti si arriva a un nodo senza successori, che è collegato a FINISH.
-
Un ciclo nelle precedenze è un errore del piano: un'attività dovrebbe terminare prima di iniziare.
Un progetto è un insieme di attività con durate e precedenze. La sua rete delle attività ha un nodo per ogni attività, più START e FINISH, e un arco per ogni precedenza; un calendario esiste se e solo se la rete è aciclica.
Avanti: 9.2 Cammini e cammini critici