Home

Federica EU

1/14

Paola Festa » 24.Il Problema della Pianificazione di un Progetto

Il Problema della Pianificazione di un Progetto, 1

Dato un progetto costituito da un numero finito di attività, cui è associata una durata o tempo di completamento, pianificare tale progetto vuol dire stabile una schedulazione ammissibile per ciascuna attività.

Formalmente,
Definizione. Si definisce progetto un insieme di m attività $\{A_i\}_{i=1,2,\ldots,m}$ .
A ciascuna attività $A_i,\ i=1,2,\ldots,m$ , è associata una durata o tempo di completamento $d_i\geq 0$ .

Il Problema della Pianificazione di un Progetto, 2

Fra due attività distinte $A_i,\ A_j,\ i,j\in\{1,2,\ldots,m\}$ può essere definita una relazione di precedenza del tipo
$A_i\prec A_j$
con il significato che l’attività $A_j$ può avere inizio solo dopo il completamento dell’attività $A_i$ .
Tale relazione è chiaramente transitiva, ossia per ogni $i,j,k\in\{1,2,\ldots,m\},\ i\not= j\not= k$ , tali che
$A_i\prec A_j\ \mbox{e}\ A_j\prec A_k\Longrightarrow A_i\prec A_k.$

Obiettivo: Il Problema della Pianificazione di un Progetto consiste nello schedulare e sincronizzare le attività di un progetto in modo da minimizzare la durata complessiva del progetto stesso, dove la durata complessiva è valutabile solo nell’istante in cui è completata l’ultima attività prevista dalla schedulazione.

Il Problema della Pianificazione di un Progetto, 3

Un progetto può essere rappresentato tramite un grafo orientato G=(V,A) adottando la convenzione di associare ad ogni attività un arco di costo pari alla durata dell’attività cui è associato.
La disposizione degli archi in G deve tener conto delle eventuali precedenze fra le varie attività del progetto.

A partire dalla descrizione del progetto per mezzo della lista delle attività e delle relative durate
$\{A_i\}_{i=1,2,\ldots,m}$

e della lista delle q relazioni di precedenza
$A_i\prec A_j,\ \mbox{per qualche}\ i,j\in\{1,2,\ldots,m\},\ i\not=j,$

si costruisce un grafo iniziale contenente un arco per ogni attività di costo pari alla durata dell’attività cui è associato ed un arco fittizio di costo nullo per ogni relazione di precedenza.
Dunque, il grafo iniziale contiene m+q archi.

Il Problema della Pianificazione di un Progetto, 4

Si consideri, ad esempio, il seguente progetto PG:

lista di 5 attività: $A_1,A_2,A_3,A_4,A_5$ ;
lista di 5 relazioni di precedenza: $A_1\prec A_2,\quad A_1\prec A_3,\quad A_2\prec A_4,\quad A_3\prec A_4, \quad A_2\prec A_5.$

Il grafo iniziale rappresentante PG ha m+q=5+5=10 archi ed è riportato in Figura.

Grafo orientato iniziale rappresentante PG: gli archi fittizzi sono contrassegnati con un cerchio, mentre gli archi-attività sono contrassegnati con un quadrato. Disegnato da Paola Festa

Il Problema della Pianificazione di un Progetto, 5

Nel grafo iniziale si “contraggono” gli archi fittizzi ridondanti per poi cancellare i nodi risultanti superflui dopo la contrazione degli archi fittizzi ridondanti.

Per il grafo rappresentante PG si ottiene il grafo ridotto mostrato in Figura.

E’ banale osservare che il grafo orientato G=(V,A) rappresentante un progetto è sempre aciclico.
Ogni nodo j in V è da interpretarsi come evento ed in
particolare come l’evento corrispondente al completamento di tutte le attività associate agli archi entranti in j, cioè di tutte le attività
$(i,j)\in A\ \mbox{tali che}\ i\in BS(j).$

Grafo orientato ridotto rappresentante PG. Disegnato da Paola Festa

Il Problema della Pianificazione di un Progetto, 6

In quanto segue, si supporrà che il grafo G abbia un solo vertice iniziale s ed un solo vertice finale d (vedi Figura).

Tali ipotesi

equivalgono a supporre che $BS(s)=FS(d)=\emptyset;$

non sono restrittive, in quanto un grafo qualunque può essere sempre trasformato in un grafo siffatto introducendo nodi e/o archi fittizzi.

Dato un progetto descritto mediante una lista di attività
ed una lista di relazioni di precedenza fra le attività, una volta costruito il grafo minimale che lo rappresenti, bisogna numerare i nodi del grafo in modo tale che la numerazione scelta rispetti l’ordine topologico, cioè sia tale che
$\mbox{per ogni}\ (i,j)\in A,\quad i<j.$

Grafo orientato finale rappresentante PG. Disegnato da Paola Festa

Il Problema della Pianificazione di un Progetto, 7

L’ordine topologico dei nodi è ottenibile grazie ad un semplice algoritmo di complessità computazionale $O(\vert A\vert)=O(m)$ , il cui pseudocodice è riportato di seguito.
L’output è l’array index[n] contenente gli indici assegnati ai nodi.

$\fbox{\begin{minipage}[ht!]{10cm} \footnotesize{ \begin{tt} {\bf algoritmo} {nodes-topological-sort}($V$,$A$) \\$1$\hspace*{0.5truecm} $V':=V$; $A':=A$; $next:=1$; \\ $2$\hspace*{0.5truecm} {\bf do}\hspace*{1truecm} \mbox{/* $BS_{A'}(j)=\{i\in V'\ \vert\ (i,j)\in A'\}$ */} \\ $3$\hspace*{1truecm} sia $j\in V'$ un nodo tale che $BS_{A'}(j)=\emptyset$; \\ $4$\hspace*{1truecm} $index[j]=next$; $next=next+1$; \\ $5$\hspace*{1truecm} $V'=V'\setminus\{j\}$; $A'=A'\setminus\{(j,v)\ \vert\ v\in V'\}$; \\ $6$\hspace*{0.5truecm} {\bf while} ($V'\not=\emptyset$) \\ $7$\hspace {0.5truecm} {\bf return} ($index$); \\ {\bf end} {nodes-topological-sort} \end{tt} } \end{minipage}}$

Il Problema della Pianificazione di un Progetto, 8

Siano

V={1,2,…,n} l’insieme dei nodi di G numerati rispettando l’ordine topologico;
$BS(1)=\emptyset,\ FS(n)=\emptyset$ ;
$t_i$ l’istante di inizio delle attività $(i,j)\in FS(i)$ (ovviamente, $t_i\geq 0,\ \forall i\in\{1,2,\ldots,n\}$ ).

Introducendo n variabili di decisione $t_i\geq 0,\ i\in\{1,2,\ldots,n\}$ , al Problema della Pianificazione di un Progetto corrisponde il seguente modello matematico:
$\begin{array}{llll} \mbox{(PG)} & \min & t_n \\ & \mbox{{\rm s.a}} \\ & (a) & t_1=0 \\ \\ & (b) & t_j\geq t_i+d_{ij} & \forall\ (i,j)\in A\\ \\& (c) & t_i\geq 0, & \forall\ i=1,2,\ldots,n. \end{array}$

Il Problema della Pianificazione di un Progetto, 9

Note.
$t_n$ rappresenta la durata complessiva del progetto da minimizzare.

I vincoli (b) hanno la seguente interpretazione: per ogni attività (i,j) in A, $t_i+d_{ij}$ ne rappresenta l’istante di completamento ed ogni attività (j,v) in A potrà iniziare solo dopo tale istante (vedi Figura).

Interpretando le durate delle attività $d_{ij}$ come costi associati agli archi, la durata minima del progetto coincide con il costo del cammino più lungo dal nodo 1 al nodo n in G.

Interpretazione dei vincoli (b) del problema (PG). Disegnato da Paola Festa

Critical Path Method, 1

Per risolvere il Problema della Pianificazione di un Progetto, in letteratura è stato proposto un algoritmo noto come CPM, acronimo di Critical Path Method.

Ad ogni nodo i=1,2,…,n, l’algoritmo CPM associa

$t_{min}[i]$ : l’istante minimo prima del quale l’evento i non può accadere, cioè l’istante minimo prima del quale tutte le attività (j,i), j in BS(i), non sono completate;
$t_{max}[i]$ : l’istante massimo in cui l’evento i può accadere senza compromettere la durata complessiva minima del progetto, cioè l’istante massimo in cui tutte le attività (j,i), j in BS(i), devono essere completate per non eccedere la durata totale minima del progetto.

$t_{min}[n]$ è la durata complessiva minima del progetto.

Critical Path Method, 2

Definizioni e Proprietà.

Un’attività (i,j) in A ha slittamento nullo se si verifica che

$t_{max}[j]-t_{min}[i]=d_{ij}$ ;
$t_{max}[i]=t_{min}[i]$ ;
$t_{max}[j]=t_{min}[j]$ .

Un’attività con slittamento nullo è detta attività critica.

Un cammino dal nodo 1 al nodo n in G è detto cammino critico se tutte le attività (equiv. archi) che lo compongono sono critiche.

Un qualunque grafo rappresentante un progetto ha almeno un cammino critico.

Critical Path Method, 3

Per ogni i=1,2,…,n, $t_{min}[i]$ e $t_{max}[i]$ sono calcolate tramite l’applicazione dell’algoritmo CPM, il cui input è costituito dal grafo minimale G=(V,A).

CPM è costituito da due fasi:

una fase forward, durante la quale viene calcolato $t_{min}[j]$ per ogni nodo j=2,3,…,n (ovviamente, $t_{min}[1]=0$ );
una fase backward, durante la quale a partire da $t_{max}[n]=t_{min}[n]$ , viene calcolato $t_{max}[i]$ per ogni nodo i=n-1,n-2,…,1.

Critical Path Method, 4

$\fbox{\begin{minipage}[ht!]{12.5cm} \footnotesize{ \begin{tt} {\bf algoritmo} {cpm}($V$,$A$) \\ $1$\hspace*{0.5truecm} {\bf call} {nodes-topological-sort}($V$,$A$);\hspace*{1.5truecm}\mbox{/* $O(m)$ */} \\ $2$\hspace*{0.5truecm} $t_{min}[1]:=0$; \\ $3$\hspace*{0.5truecm} {\bf for} $j=2$ {\bf to} $n$ {\bf do} $t_{min}[j]:=\displaystyle{\max_{i\in BS(j)}\{t_{min}[i]+d_{ij}\}}$;\hspace {1.9truecm}\mbox{/* $O(m)$ */} \\ $4$\hspace*{0.5truecm} $t_{max}[n]:=t_{min}[n]$; \\ $5$\hspace*{0.5truecm} {\bf for} $i=n-1$ {\bf downto} $1$ {\bf do} $t_{max}[i]:=\displaystyle{\min_{j\in FS(i)}\{t_{max}[j]-d_{ij}\}}$;\hspace*{0.5truecm}\mbox{/* $O(m)$ */} \\ $6$\hspace*{0.5truecm} {\bf return} ($t_{min}$,$t_{max}$); \\ {\bf end} {cpm} \end{tt} } \end{minipage}}$

Complessità computazionale dell’algoritmo CPM

In linea 1 dell’algoritmo CPM viene invocato l’algoritmo nodes-topological-sort per numerare in ordine topologico i nodi con complessità computazionale pari a $O(m)$ .