Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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

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

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

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

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

  1. 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;
  2. 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) .

I loop for in linea 3 e 5 hanno entrambi computazionale pari a O(m) .

Ne consegue che la computazionale dell’algoritmo CPM è pari a

\[ O(m).\]

I materiali di supporto della lezione

D. Bertsimas e J.N. Tsitsiklis, Introduction to Linear Optimization, Belmont - Massachusetts (USA), Dynamic Ideas and Athena Scientific, 2008.

M. Fischetti, Lezioni di Ricerca Operativa, Padova, Edizioni Libreria Progetto Padova, 1999.

S. Martello, Fondamenti di Ricerca Operativa L-A, Bologna, Società Editrice Esculapio, 2004.

S. Martello, Ricerca Operativa LS, Bologna, Società Editrice Esculapio, 2004.

Dispense del Corso di Ricerca Operativa presso l'Università degli Studi di Pisa.

Dispense ed Appunti del Corso prodotte da Paola Festa.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion