5
)(sh
L
ij
Elemento della matrice )(sH
L
, trasformata di Laplace della
funzione )(th
ij
, funzione generatrice dei momenti del tempo di
transizione i-j.
)(tC Matrice dei prodotti tra le probabilità di transizione e le funzioni
di densità dei tempi di transizione, prodotto termine a termine
delle matrici P e )(tH
)(tc
ij
Elemento della matrice )(tC , prodotto tra
ij
p e )(th
ij
)(sC
L
Matrice dei prodotti tra le probabilità di transizione e le funzioni
generatrici dei momenti dei tempi di transizione, trasformata di
Laplace della matrice )(tC , prodotto termine a termine delle
matrici P e )(sH
L
)(sc
L
ij
Elemento della matrice )(sC
L
, trasformata di Laplace di )(tc
ij
,
prodotto tra
ij
p e )(sh
L
ij
)(tF Matrice delle funzioni densità di probabilità congiunta del
raggiungimento del nodo j a partire dal nodo i e del tempo di
primo raggiungimento di un qualsiasi nodo j di un reticolo
GERT, a partire da un altro nodo i
)(tf
ij
Elemento della matrice )(tF , funzione di densità di probabilità
congiunta del raggiungimento del nodo j a partire dal nodo i e
del tempo di primo raggiungimento del nodo j, partendo dal
nodo i
)(sF
L
Matrice delle funzioni di trasmittanza, trasformata di Laplace
della matrice )(tF
)(sf
L
ij
Elemento della matrice )(sF
L
, funzione di trasmittanza tra il
nodo i ed il nodo j, trasformata della funzione )(tf
ij
6
)0(
L
F Limite della matrice )(sF
L
per s→0, nella maggior parte dei
casi semplicemente )(sF
L
calcolata in s=0, contenente le
probabilità marginali per ogni tempo t di raggiungere un
qualsiasi nodo j da un nodo i
)0(
L
ij
f Elemento della matrice )0(
L
F , limite di )(sf
L
ij
s→0,
probabilità marginale per ogni tempo t di raggiungere il nodo j
dal nodo i
)(t
ij
φ Funzione densità di probabilità di permanenza in uno stato j al
tempo t, essendo partito il processo stocastico semi-markoviano
dallo stato i, citata per ragioni di completezza descrittiva dei
processi semi-markoviani nel paragrafo 1.9, ma non utilizzata
per lo sviluppo dei metodi di risoluzione dei reticoli GERT
ij
δ Funzione logica introdotta per illustrare la )(t
ij
φ
)(tw
i
>
Funzione di densità cumulata di effettuare una transizione dallo
stato i successivamente al tempo t, introdotta per illustrare la
)(t
ij
φ
Τ Matrice dei tempi medi di transizione
ij
τ Elemento della matrice Τ , tempo medio della transizione diretta
tra il nodo i ed il nodo j
2
Τ Matrice dei momenti secondi dei tempi di transizione
2
ij
τ Elemento della matrice
2
Τ , momento secondo del tempo della
transizione diretta tra il nodo i ed il nodo j
0
)(
ds
sdF
L
Limite della derivata della matrice )(sF
L
per s→0, nella
maggior parte dei casi semplicemente la derivata della matrice
)(sF
L
calcolata in s=0
11
Introduzione
Il presente lavoro propone una metodologia di risoluzione dei cosiddetti reticoli
GERT, uno strumento utilizzato per rappresentare progetti e per ricavare informazioni
utili alla loro pianificazione, evidenziando l’aspetto probabilistico che caratterizza le
attività reali.
Dopo una breve panoramica delle più note tecniche reticolari utilizzate nel
Project Management, nel primo capitolo vengono descritti i reticoli GERT, e presentate
le usuali tecniche di risoluzione, che fanno ricorso alla cosiddetta funzione generatrice
dei momenti ed alla funzione di trasmittanza per ricavare il valore atteso del tempo di
realizzazione dei progetti. Viene inoltre introdotto il concetto di processo semi-
markoviano, che costituisce il fondamento teorico sul quale vengono costruiti i reticoli
GERT.
Nel secondo capitolo viene presentato un diverso metodo di risoluzione dei
reticoli GERT, che permette di ricavare, a partire dai tempi medi di completamento delle
singole attività componenti il reticolo e dal momento secondo di tali tempi, i tempi medi
e le varianze dei tempi per realizzare il progetto nella sua interezza o parti di esso.
Vengono inoltre calcolate le probabilità di raggiungere i diversi nodi del reticolo.
Nel terzo capitolo la metodologia sviluppata viene applicata ad un ipotetico
progetto d’impianto, le cui caratteristiche fondamentali corrispondono a quelle di un
progetto già esaminato durante il corso di Gestione di Progetti d’Impianto tenuto dal
professor Carlo Rafele presso il Politecnico di Torino nell’anno 2003.
Nel quarto capitolo viene presentato il metodo adattato al problema della stima
dei costi, anziché dei tempi, considerando per semplicità di analisi i costi non
attualizzati.
12
Nelle appendici vengono presentati i passaggi più complessi dal punto di vista
computazionale ed il relativo codice Matlab necessario per eseguire i calcoli risolutivi.
In particolare nell’appendice D è riportato l’output di Matlab relativo al caso di studio
descritto nel capitolo 3.
13
Le tecniche reticolari
1.1 Grafi
Le tecniche reticolari costituiscono una categoria di strumenti analitici
avanzati di supporto alla programmazione e gestione dei progetti. Esse
permettono di rappresentare l’intero progetto evidenziando i legami funzionali,
oltreché temporali, tra le attività e gli eventi che lo caratterizzano.
I grafi, di cui i reticoli sono un particolare sottogruppo, vengono
utilizzati nel Project Management in un vasto numero di forme, dalle versioni
più semplici, che ne sfruttano l’immediatezza visiva, alle più complesse, in cui
agli elementi componenti il grafo vengono associati precisi significati
matematici e che permettono di accrescere il contributo informativo dello
strumento stesso, andando oltre la semplice schematizzazione delle attività.
Seguono alcune definizioni fondamentali riguardanti i grafi.
Si definisce grafo G = (N,A) una coppia ordinata di un insieme finito
non vuoto N di nodi e di un insieme di archi A, ad ogni elemento a di A sono
associati due elementi di N, detti nodi terminali o estremi di a.
Una catena consiste in una sequenza di archi che collega due nodi
appartenenti al grafo. Il grafo è detto connesso se esiste una catena tra due nodi
qualsiasi del grafo stesso. Se il grafo è orientato, ossia se ogni arco stabilisce
un ordinamento tra i due nodi che mette in collegamento, una catena viene
denominata cammino. Un circuito è un cammino che ha come estremi iniziale
e finale lo stesso nodo.
Dato un grafo orientato si definisce matrice di adiacenza nodi-nodi una
matrice che ha una riga ed una colonna per ogni nodo appartenente al grafico,
14
ed il generico elemento
ij
d vale 1 se l’arco che connette i e j esiste, 0
altrimenti.
1
Una particolare tipologia di grafo è denominata grafo di flusso: i nodi
rappresentano le variabili e le relazioni intercorrenti tra le variabili, chiamate
trasmittanze, vengono indicate sugli archi. La proprietà fondamentale del grafo
di flusso consiste nel fatto che il valore associato ad un nodo è dato dalla
somma delle trasmittanze degli archi incidenti su di esso, moltiplicata ognuna
per il valore corrispondente al nodo da cui l’arco ha origine
2
.
Si parla di reticoli per indicare particolari grafi in cui vengono
rappresentate le attività di cui si compone un progetto e le relazioni di
precedenza logica che intercorrono tra di esse. Si distinguono reticoli di tipo
AOA (Activity On Arc) e AON (Activity On Node) a seconda della modalità
di rappresentazione delle attività. Nel seguito saranno trattati reticoli di tipo
1
Tadei R.., Della Croce F., Ricerca Operativa e Ottimizzazione, p. 97-99
2
Pojaga L., Ricerca operativa per il management e il project management, p. 80-82
Fig. 1.1 - Grafo di flusso
fonte: Pojaga L., Ricerca operativa per il management e il
project management
a f
X1
X3
X2
X5
X6
X4
b
c
d
eh
g
i
15
AOA, nei quali i nodi rappresentano eventi associati alla conclusione ed
all’inizio delle attività collegate.
Si distinguono inoltre reticoli di tipo deterministico DAN e probabilistico
PAN. I primi rispettano le seguenti proprietà:
1. sono orientati;
2. sono connessi;
3. la loro matrice delle adiacenze nodo-nodo associata è consistente, ossia
priva di circuiti;
4. gli eventi hanno un’unica configurazione inizio-fine;
5. non sono ammesse configurazioni di tipo “parallelo”, ossia con archi
che possano iniziare e terminare negli stessi nodi di partenza e arrivo: è
pertanto necessaria l’introduzione di attività cosiddette dummy nel caso
in cui il progetto proceda realmente attraverso attività in parallelo,
secondo la definizione sopra esposta.
L’attività dummy inserita (d) dà contributo nullo alle elaborazioni in cui viene
coinvolto il reticolo, se si tratta di un reticolo con proprietà di un grafo di
flusso, l’arco indica una trasformazione di tipo identità (prodotto per la
costante unitaria), se si tratta di un reticolo di tipo CPM corrisponde ad
un’attività a tempo di esecuzione nullo.
I reticoli probabilistici per contro ammettono circuiti e gli eventi
possono assumere configurazioni logiche diverse permettendo una più ampia
varietà di modellizzazioni. Essi permettono inoltre configurazioni in parallelo;
successivamente per stabilire la congruenza tra reticoli GERT e processi semi-
markoviani, si elimineranno i paralleli, inserendo attività dummy, come per i
reticoli deterministici.
16
1.2 CPM
Sviluppato alla fine degli anni ’50 il metodo del cammino critico
(Critical Path Method) è principalmente un metodo per la schedulazione, che
permette nella sua versione più semplice di programmare l’esecuzione delle
attività rispettando i vincoli di precedenza, individuando quali di esse
determinano la durata complessiva del progetto (dette critiche), e quali invece
possono essere ritardate o rallentate (fornendo una precisa valutazione
quantitativa dei tempi di slittamento) senza comportare una dilatazione dei
tempi di realizzazione complessiva degli obiettivi del progetto.
Vengono introdotti un solo nodo di partenza ed uno di arrivo, a cui
devono convergere tutte le attività terminali. Per ogni attività facente parte del
progetto viene indicata una durata prevista ed il completamento di ognuna di
Fig. 1.2 - Eliminazione di un parallelo con
l’introduzione di un’attività dummy
i j
a
a
i j
l
a
a
d
17
esse viene considerato indipendente da quello delle altre: il vincolo
fondamentale consiste, con riferimento alla figura 1.3, al fatto che le attività
che seguono (c e d) iniziano solo al termine di tutte le attività che le precedono
(a e b).
Date queste premesse la durata dell’intero progetto corrisponderà alla
durata del cammino più lungo tra quelli che congiungono il nodo di partenza e
quello di arrivo; per identificarlo si segue la seguente procedura:
1. vengono stimati per ogni nodo (evento) i cosiddetti tempi al più
presto, ossia il tempo prima del quale l’evento non può verificarsi,
ottenuto sommando il tempo massimo di raggiungimento del nodo
a partire da quelli che lo precedono;
2. giunti al nodo terminale viene determinato il tempo al più presto
complessivo, che viene eguagliato al tempo al più tardi
complessivo;
3. si stimano i tempi al più tardi per ogni evento, ossia i tempi ai quali
gli eventi possono verificarsi, senza comportare ritardi per l’intero
progetto, ottenuti sottraendo al tempo al più tardi degli eventi che
seguono la durata delle attività che le congiungono con l’evento di
partenza e scegliendo il valore minore tra questi;
Fig. 1.3 - Particolare di reticolo CPM
i
j
l
a
b
c
d
18
4. per ogni nodo si calcola uno slittamento dato dalla differenza tra
tempi al più tardi e al più presto: i nodi per i quali questo
slittamento è nullo compongono il cammino critico.
Si calcolano poi gli slittamenti relativi alle attività che collegano gli
eventi:
• si assume come slittamento totale (total slack) la differenza tra data
di fine al più tardi e al più presto, la prima coincide con il tempo al
più tardi dell’evento che segue, la seconda con il tempo al più
presto dell’evento che la precede a cui viene aggiunta la durata
dell’attività stessa
3
;
• si definisce slittamento libero (free slack) la differenza tra tempo al
più presto dell’evento che segue e data di fine al più presto
dell’attività, ed ovviamente non può eccedere lo slittamento totale;
• si definisce slittamento concatenato la differenza tra slittamento
totale e slittamento libero.
Il valore degli slittamenti così calcolati permette al pianificatore di
considerare una diversa allocazione di risorse assegnate ad ogni attività,
sfruttando la possibilità di rallentare le attività non critiche a favore di quelle
che incidono sulla durata complessiva prevista del progetto, abbassandola di
conseguenza. In particolare sfruttando lo slittamento libero di un’attività non si
influenza lo slittamento permesso alle altre.
Il metodo CPM permette un ulteriore sviluppo: ad ogni attività vengono
associate due durate, una normale ed una accelerata, e due costi diretti
(normale ed accelerato) legati al tempo di esecuzione delle attività: i costi sono
assunti decrescenti al crescere del tempo di esecuzione. A questi vengono poi
sommati i costi indiretti, assunti direttamente proporzionali al tempo di
3
Wiest J.D., Levy F.K., A management guide to PERT/CPM, p. 35
19
esecuzione complessiva del progetto. L’obiettivo finale del metodo consiste nel
raggiungimento di un punto di ottimo, dal punto di vista dei costi.
La procedura prevede i seguenti passi:
1. calcolo del cammino critico con tempi e costi normali;
2. si riducono progressivamente i tempi di esecuzione e si stimano i
costi derivanti da tali riduzioni, essi si ridurranno fino a quando il
risparmio sui costi indiretti non verrà superato dall’aumento dei
costi diretti: vengono scelte per la riduzione le attività facenti parte
del cammino critico, che viene di volta in volta ricalcolato.
4
1.3 PERT
Contemporaneamente alla metodologia CPM venne sviluppato il
metodo PERT (Program Evaluation Review Tecnique): esso introduce elementi
di stima probabilistica delle durate delle singole attività e del progetto.
Si assume che la durata di ogni attività segua la distribuzione Beta, i cui valori
di media e varianza vengono calcolati in base a tre stime di durata: ottimistica,
modale e pessimistica. La distribuzione Beta si presta particolarmente a
rappresentare le durate dei progetti reali e gode delle seguenti proprietà:
• il dominio si estende su valori positivi dell’asse dei tempi;
• è continua;
• è unimodale;
• può assumere forme diverse, richiedendo la stima di un numero
limitato di parametri per ogni attività;
• le due durate estreme hanno una bassa probabilità di verificarsi.
5
4
Wiest J.D., Levy F.K., A management guide to PERT/CPM, p. 64-65
5
Pojaga L., Ricerca operativa per il management e il project management, p. 254
20
Il cammino critico viene calcolato utilizzando i tempi medi stimati in
luogo delle durate certe utilizzate nel CPM. La durata media complessiva è
quindi ottenuta come somma delle durate medie delle attività facenti parte del
cammino critico, ed anche la varianza del tempo totale è calcolata in modo
additivo, secondo l’ipotesi fondamentale che il tempo di esecuzione di ogni
attività sia indipendente da quello delle altre.
La stima della varianza ed il ricorso al teorema del limite centrale (per
cui il valore atteso della somma di variabili casuali tende a distribuirsi
normalmente) permettono di assegnare delle probabilità ad intervalli temporali
stabiliti, ad esempio alla realizzazione del progetto entro una certa scadenza.
Per una maggior precisione sarebbe necessario considerare il contributo che la
variabilità dei percorsi alternativi porta al tempo complessivo
6
, in quanto il
cammino critico può modificarsi a seconda del valore assunto dai tempi non
più deterministici: ciò porterebbe a differenti stime di durate medie e varianze
del tempo totale e sarebbe opportuno calcolare la probabilità che ogni percorso
divenga quello critico, procedere in tale direzione complicherebbe alquanto
l’analisi, suggerendo l’utilizzo della simulazione.
Analogamente al CPM è stata introdotta una versione del PERT che
considera anche la problematica dei costi.
6
Wiest J.D., Levy F.K., A management guide to PERT/CPM, p. 52-53
21
1.4 Limiti e risultati ottenuti con CPM e PERT
I metodi reticolari CPM e PERT sono soggetti ad importanti
limitazioni, diretta conseguenza delle ipotesi alla base della loro realizzazione
7
:
1. il progetto è perfettamente scomponibile in attività indipendenti, sia
sotto il profilo operativo, sia sotto quello temporale: quindi esse
sono perfettamente note a priori e tutte necessarie e sufficienti alla
realizzazione del progetto. Ciò fa sì che il reticolo sia uno strumento
statico, di scarso supporto di fronte a necessità impreviste. Inoltre
non sempre è verificabile l’effettiva indipendenza operativa delle
varie attività, essendo spesso sottoposte a vincoli comuni di risorse.
2. Le relazioni di precedenza possono essere rappresentate senza far
ricorso a cicli, con successioni di tipo finish to start, che prevedono
il perfetto completamento delle attività antecedenti prima che
abbiano inizio quelle che le seguono.
3. Le durate possono essere stimate a priori e sono indipendenti le une
dalle altre: questa premessa è alla base di tutti i calcoli eseguiti per
determinare cammino critico e slittamenti. Questa assunzione è
sicuramente molto forte, soprattutto tenendo conto della
disponibilità limitata di risorse comuni che spesso caratterizza i
progetti. Un’attenta schedulazione, realizzata a seguito di successive
iterazioni del reticolo, può però limitare la dipendenza delle durate
delle attività.
7
Wiest J.D., Levy F.K., A management guide to PERT/CPM, p. 166-173
22
4. Nel caso di reticolo PERT la distribuzione dei tempi è
necessariamente la Beta, la varianza della durata del progetto è pari
alla somma delle varianze delle attività del cammino critico. Ciò
limita le possibilità di rappresentazione dei tempi di esecuzione ed
introduce una distorsione nella stima della durata totale. Alla
semplicità del metodo si contrappone un certo grado di
imprecisione.
5. Le ipotesi sui legami tra costi e tempo di esecuzione sono plausibili
ma inaccurate; una stima più precisa può comportare molte
difficoltà di ordine pratico nell’ottenere le effettive funzioni che
legano tempi e costi.
Pur con queste limitazioni i metodi sopra descritti permettono di
raggiungere alcuni risultati importanti:
• hanno una veste grafica che semplifica la comprensione dello
svolgimento del progetto;
• permettono di ottenere una stima ragionevole del tempo di
esecuzione complessivo di un progetto composto da numerose
attività composte in una complessa rete di precedenze;
• forniscono una stima dei margini di manovra caratterizzanti ogni
attività, agevolando la schedulazione e la programmazione delle
attività;
• nelle versioni “costi” permettono di legare la programmazione delle
attività al costo conseguente.
Ricevi informazioni sui nostri servizi, sulle offerte e non perdere news e consigli su università e lavoro.
