9.1 Progetti e reti di progetto

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

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 immediato predecessore di attività \(j\) e \(j\) possono iniziare solo al termine di \(i\). Un'attività con diversi predecessori immediati può iniziare solo quando tutti saranno finiti.

• Per descrivere un progetto abbiamo bisogno di tre tipi di informazioni: le attività, al livello desiderato di dettaglio; le precedences, ovvero gli immediati predecessori di ciascuna attività; le durate, quello è una stima del tempo impiegato da ciascuna attività.

• In tutto il capitolo facciamo due ipotesi:

  • (H1) le durate sono deterministico: ogni attività dura esattamente la sua durata stimata \(d_j\), senza interruzioni;

  • (H2) le risorse sono illimitate: possono essere svolte attività non legate da precedenze allo stesso tempo.

• Il metodo di questo capitolo è il metodo del percorso critico (CPM). È stato sviluppato alla fine degli anni '50 indipendentemente dalla tecnica di valutazione e revisione del programma (PERT), e i due nomi sono spesso combinati PERT/CPM.

Definizione 9.2: rete del progetto

La rete di progetto di un progetto con attività \(n\) è il grafo diretto \(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 immediato predecessori e l'arco \((j,n+1)\) per ogni attività \(j\) che non sia un immediato predecessore di alcuna attività.

• Questa è la rete activity-on-node (AON): le attività sono i nodi e gli archi mostrano solo precedenze. Nella rete activity-on-arc (AOA) ogni attività è un arco e un nodo separa un'attività dai suoi immediati predecessori.

• La rete AON è più facile da costruire, più facile da leggere per gli utenti senza esperienza e più facile da rivedere quando il progetto cambia: lo usiamo sempre, e lo chiamiamo semplicemente rete del progetto.

• In pratica la rete di progetto viene costruita dal software di gestione del progetto a partire dall'elenco delle attività.

Esempio 9.1: il caso di studio

Un'impresa edile deve programmare le squadre che svolgono le attività \(14\) di un progetto di costruzione. Il la tabella riporta, per ogni attività, quelle immediatamente precedenti e la sua durata stimata.

attività \(j\)	descrizione	immediati predecessori	\(d_j\)
\(1\)	Scava	—	\(2\) settimane
\(2\)	Gettare le fondamenta	\(1\)	\(4\) settimane
\(3\)	Costruisci il muro grezzo	\(2\)	\(10\) settimane
\(4\)	Montare il tetto	\(3\)	\(6\) settimane
\(5\)	Installazione dell'impianto idraulico esterno	\(3\)	\(4\) settimane
\(6\)	Installa l'impianto idraulico interno	\(5\)	\(5\) settimane
\(7\)	Montare il rivestimento esterno	\(4\)	\(7\) settimane
\(8\)	Fai la verniciatura esterna	\(5\), \(7\)	\(9\) settimane
\(9\)	Esegui i lavori elettrici	\(3\)	\(7\) settimane
\(10\)	Monta il wallboard	\(6\), \(9\)	\(8\) settimane
\(11\)	Installa il pavimento	\(10\)	\(4\) settimane
\(12\)	Tinteggiatura degli interni	\(10\)	\(5\) settimane
\(13\)	Installazione degli infissi esterni	\(8\)	\(2\) settimane
\(14\)	Installazione degli infissi interni	\(11\), \(12\)	\(6\) settimane

Sommando le durate si ottiene un totale di \(79\) settimane. È possibile svolgere più attività contemporaneamente, il che possono ridurre sostanzialmente la durata del progetto. La rete di progetto ha i nodi \(16\) archi \(0,1,\dots,15\) e \(19\); accanto ad ogni nodo, in blu, la sua durata.

L'attività \(1\) è l'unica attività senza predecessori immediati, quindi START ha il singolo arco \((0,1)\); attività \(13\) e \(14\) non sono predecessori immediati di alcuna attività, quindi entrano in FINISH.

9.1.1 Pianificazioni e reti acicliche

Definizione 9.3: pianificazione

Una pianificazione di un progetto è un vettore \(\vet{t}=(t_0,t_1,\dots,t_{n+1})\) dei tempi di inizio, con \(t_0=0\), che soddisfa

\[ t_j \ge t_i+d_i, \quad \forall (i,j) \in A . \]

Il nodo \(j\) inizia a \(t_j\) e termina a \(t_j+d_j\). La durata della pianificazione è \(t_{n+1}\) e la durata minima del progetto \(T\) è la durata minima di una pianificazione.

• Il vincolo dell'arco \((i,j)\) dice che \(j\) inizia dopo che \(i\) è finito. Per (H1) e (H2), le precedenze costituiscono gli unici vincoli della pianificazione.

• Gli archi \((j,n+1)\) fanno iniziare FINISH al termine di ogni attività: \(t_{n+1}\) è il tempo di completamento del progetto.

Proposizione 9.4: una pianificazione necessita di una rete aciclica

Un progetto ha una pianificazione se e solo se la sua rete di progetti è aciclica.

Dimostrazione

Nessun arco entra nel nodo \(0\) e nessun arco esce dal nodo \(n+1\), quindi ogni ciclo diretto di \(G\) è costituito da attività.

1. Sia \(i_0,i_1,\dots,i_k=i_0\) un ciclo diretto e \(\vet{t}\) una pianificazione. Sommando i vincoli del suo archi, il telescopio dei tempi di inizio:

   \[ 0=t_{i_k}-t_{i_0} \ge \sum_{s=0}^{k-1} d_{i_s} >0, \]

   una contraddizione, poiché le durate delle attività sono positive.

2. 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 arco entrante e può essere rimosso per primo. Lascia che \(D\) sia il più grande durata e \(t_{v_a}=a\,D\) per ogni \(a\).

3. Quindi \(t_0=0\), e ogni arco \((v_a,v_b)\) va avanti, \(a<b\), quindi \(t_{v_b}-t_{v_a}=(b-a)\,D \ge D \ge d_{v_a}\): \(\vet{t}\) è una pianificazione. □

• Da ora in poi la rete del progetto è aciclica. Allora ogni attività giace su un percorso dall'INIZIO alla FINE: andare a ritroso lungo gli archi si raggiunge un nodo senza immediati predecessori, che è legato a START, e andando avanti raggiungiamo un nodo senza successori, che è legato a FINISH.

• Un ciclo nelle precedenti è un errore di progettazione: un'attività dovrebbe terminare prima di iniziare.

Un progetto è un insieme di attività con durate e precedenze. La sua rete di progetti ha un nodo per ogni attività, più INIZIO e FINE, e un arco per ogni precedenza; un programma esiste se e solo se la rete è aciclica.

---

Avanti: 9.2 Percorsi e percorsi critici