Vai al contenuto

9.1 Progetti e reti delle attività

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.

Figura 1

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

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

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à.

  1. 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.

  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 archi entranti e può essere tolto per primo. Siano \(D\) la durata massima e \(t_{v_a}=a\,D\) per ogni \(a\).

  3. 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