CAPITOLUL 6

 

6.5. Determinarea duratei optime de execuţie a unui proiect

 

            Metoda PERT (Program Evaluation and Review Techique) încearcă să ţină seama de variaţiile duratelor de  execuţie a  diverselor  activităţi dintr-un graf de tip ADC. În acest scop, metoda permite calcularea timpului mediu de terminare a unui proiect, identificarea activităţilor critice precum şi estimarea probabilităţilor de realizare a termenelor planificate.

            Metoda se aplică îndeosebi la proiecte din domeniul cercetării şi dezvoltării. Ea porneşte de la următoarele ipoteze:

            a) pentru fiecare activitate a unui graf G, ataşat unui proiect dat, se poate estima durata optimistă (durata minimă de execuţie a unei activităţi) a_ij; durata cea mai probabilă (durata cu cea mai mare şansă de realizare) m_ij şi durata pesimistă b_ij (este intervalul de timp maxim de realizare a activităţii (i,j));

            b) durata fiecărei activităţi a proiectului are o distribuţie beta:(fig.6.9)

Densitatea de repartiţie

 

 

 

Aşa cum se vede, distribuţia beta satisface condiţiile care au un suport practic solid, bazat pe următoarele observaţii:

            - intersectează axa abciselor în două puncte care pot corespunde duratelor a_ij şi b_ij;

            - este unimodală, adică are o singură valoare maximă care poate corespunde duratei m_ij;

            - valoarea (b_ij - a_ij) este intervalul de variaţie al distribuţiei şi poate indica gradul de împrăştiere al duratelor posibile.

            c) durata medie de execuţie t_ij a unei activităţi (i,j) este dată de:

 ;                                                 (6.12)

 

            d) dispersia duratei t_ij de execuţie a activităţii (i,j) se calculează cu ajutorul relaţiei:

 

            Dispersia reprezintă o măsură a gradului de nesiguranţă în estimarea duratei de execuţie activităţii (i,j); o valoare mare a acesteia înseamnă o mare nesiguranţă în privinţa duratei reale de execuţie;

            e) durata totală a proiectului este o variabilă aleatoare cu distribuţie normală a cărei medie t_n şi dispersie σ_n² sunt:

 

 

unde D_crit reprezintă mulţimea tuturor arcelor reţelei G care sunt pe drumul critic;

            f) probabilitatea de realizare a duratei planificate T_plan a unui proiect se determină calculând mai întâi factorul de probabilitate Z după relaţia

Şi apoi se deduce din tabelul valorilor funcţiei Laplace probabilitatea p(t_n £ T_plan);

            g) graful trebuie să conţină un număr suficient de mare de activităţi pentru a întruni toate condiţiile aplicării teoremei limită centrală iar duratele activităţilor sunt variabile aleatoare independente.

              Teorema limită centrală.

              Fiind dat un şir de variabile aleatoare independente X₁, X₂, ... X_n, cu dispersiile σ₁², σ₂², ...σ_n², dacă dispersiile sunt finite şi suma lor creşte indefinit cu n, dar astfel încât fiecare raport σ₂²/  σ_i² --> 0 atunci variabila

 urmeaz_, la limită, o lege de repartiţie normală redusă, oricare ar fi distribuţia variabilelor X_i.

              Aceasta înseamnă că o sumă de variabile aleatoare independente, fiecare dintre ele având o repartiţie oarecare, urmează, dacă numărul acestor variabile este suficient de mare, o lege normală (legea Gauss-Laplace), a cărei medie este suma mediilor variabilelor şi a cărei dispersie este suma dispersiilor variabile.

            4) dacă sunt definite termene planificate de finalizare pentru fiecare activitate (T_ij), probabilitatea ca fiecare activitate să fie executată la termenul planificat se determină calculând factorii de probabilitate z_ij, după formula:

                                                      (6.17)

 unde t_j este termenul minim de terminare al activităţii (i,j).  Apoi, utilizând tabelul valorilor funcţiei Laplace, se determină probabilităţile P_ij(t_j £ T_ij).

 

            Calculul unui program PERT. Presupunem că s-a trasat reţeaua unui proiect şi că pentru durata fiecărei activităţi avem trei estimări a_ij, m_ij, b_ij;

            Procedura de calcul foloseşte etapele:

            1. Se calculează durata medie a fiecărei actibvităţi a reţelei utilizând relaţia (6.12);

            2. Se calculează termenele evenimentelor t_j după procedeele ADC cunoscute, considerând duratele activităţilor determinate şi egale cu mediile lor;

            3. Se calculează dispersia duratei fiecărei activităţi utilizând relaţia (6.13);

            4. Se determină t_n şi σ_n² cu ajutorul relaţiilor (6.14) şi (6.15);

            5. Se determină probabilitatea de realizare a duratei planificate a proiectului după relaţia (6.16) şi a tabelului valorilor funcţiei Laplace;

            6. Se analizează, în final, probabilitatea calculată la punctul 5 şinând seama de următoarele criterii:

            - dacă p(t_n £ T_plan) este aproximativ mai mică decât 0,25 există un mare risc de a nu se realiza proiectul la termenul planificat şi deci e necesar să se revizuiască duratele de execuţie în sensul urgentării lor;

            - dacă p(t_n £ T_plan) » 0,5 programarea este justă;

            - dacă p(t_n £ T_plan) este aproximativ mai mare ca 0,6 programarea utilizează excesiv anumite resurse.

            7. Dacă sunt date termenele planificate de execuţie a fiecărei activităţi a proiectului, atunci se calculează şi probabilităţile ca fiecare activitate să fie executată la termenul planificat. În acest sens se utilizează rela_ia (6.17) şi tabelul valorilor funcţiei Laplace.

            Analiza acestor probabilită_i se face dup_ cum urmează:

            - dacă p_ij (t_i £ T_ij) este aproximativ mai mică decât 0,6 atunci trebuie luate măsuri de urgentare a executării activităţii (i,j) în vederea realizării ei în termenul planificat;

            - dacă p_ij (t £ T_ij) ³ 0,6 atunci avem o justă planificare a execuţie activităţii (i,j).

           

Exemplu. Considerăm un proiect format din 15 activităţi (fig.6.10).

            Rezolvarea prin metoda PERT a grafului este dată în tabelul 6.5 considerând că termenul planificat al realizării proiectului este de 32 săptămâni.

 

Tabel 6.5 Rezultatele aplicării algoritmului PERT pentru proiectul dat

 

 

            Aşa cum se observă drumul critic este dat de activităţile B, E, I, H, Q, durata totală de execuţie a proiectului este   t_n = 31 săptămâni, dispersia duratei totale este σ_n² = 2,75 + 4 + 1,77 + 1,0 + 1 = 10,52 factorul de probabilitate este  iar probabilitatea de realizare a duratei planificate a proiectului este:  p(t_n £ T_plan) = 0,617

            Ţinând seama că graful are un număr mic de activităţi, putem spune că avem o planificare justă a proiectului din punct de vedere al termenului final planificat.

            Analizând probabilităţile de realizare la termene planificate ale activităţilor, observăm că pentru activităţile A,B şi E trebuie luate măsuri de urgentare a exerciţiilor în vederea realizării acestora la termenele planificate.

 

            Observaţii.

            Calculele PERT conduc la erori destul de importante:

            - ipoteza că durata medie a proiectului este egală cu cea a drumului critic este incorectă. Durata totală medie estimată prin calcule PERT este întotdeauna optimistă, adică este mai mică decât cea reală. Cu cât există mai multe drumuri paralele într-o reţea şi cu cât diferenţele dintre lungimile lor sunt mai mici, cu atât eroarea este mai mare;

            - metoda PERT oferă rezultate corecte dacă: a) drumul critic al unui proiect este suficient de lung în comparaţie cu oricare alt drum complet, astfel încât probabilitatea de a exista un alt drum critic să fie practic neglijabilă; b) drumul critic are suficient de multe activităţi astfel încât teorema limită centrală să poată fi aplicată.

            Informaţiile obţinute în urma calculelor PERT, nu sunt suficiente pentru conducătorul de proiect, deoarece atenţia acestuia va fi orientată spre activităţile de pe drumul critic, a căror distribuţie a fost înlocuită cu mediile lor, fără a acorda atenţie şi celorlalte activităţi care în cazul nerealizării uneia la timpul mediu calculat, pot produce perturbaţii mari în reţea (îndeosebi în cazul reţelelor arborescente) mergând până acolo încât, determină un alt drum critic.

 

            Modelul de simulare PERT În definirea modelului pornim de la următoarele considerente:

            - activităţile (i,j) ale unui proiect P, reprezentat prin reţeaua G, au duratele t_ij , care sunt variabile aleatoare cu distribuţii date;

            - presupunem că duratele t_ij sunt independent distribuite, fiecare cu un (ordin) interval de variaţie finit;

            - se numeşte realizare a proiectului P reţeaua G în care fiecare activitate (i,j) are o durată fixă, extrasă la întâmplare din distribuţia lui t_ij.

            - fiecărei realizări îi corespunde un drum critic şi o durată totală stabilite în mod determinist.

            Datele de bază cerute pentru rezolvarea modelului propus sunt distribuţiile duratelor activităţilor. În cazul unui proiect întâlnim cazuri practice în care, fie toate activităţile au aceeaşi distribuţie a duratelor (cazurile cele mai simple), fie că fiecărei activităţi a reţelei îi corespunde un tip propriu de distribuţie a duratei (cazurile cele mai frecvente). Aceste date sunt obţinute de la tehnicienii care au ceva experienţă în tipul de activităţi implicate sau prin metode ale analizei dispersionale în care se ţine seama de evoluţiile reale anterioare ale duratelor fiecărei activităţi obţinându-se astfel diferiţi parametrii ai distribuţiilor corespunzătoare activităţilor date (această a doua posibilitate presupune însă un volum de calcule suplimentare, ceea ce ridică costul rezolvării proiectului mărind însă exactitatea datelor obţinute).

            În ambele cazuri se consideră suficiente pe lângă limitele domeniului de variaţie finit, media şi dispersia distribuţiilor utilizate pentru fiecare activitate în parte. Aceşti parametrii (media şi dispersia distribuţiei unei activităţi) pot fi obţinuţi impunând nişte condiţii de realizare a duratelor fiecărei activităţi (de exemplu, o probabilitate dată a estimărilor pe care le facem).

            Metoda simulării Monte Carlo constă în aplicarea algoritmului de calcul al drumului critic pentru un număr suficient de mare de mulţimi de durate ale activităţilor (numărul acestora fiind determinate de exactitatea rezultatelor pe care vrem să le obţinem), generate conform distribuţiilor corespunzătoare. Această tehnică poate fi utilizată în două moduri de bază diferite.

            Prima implică o mărime relativ mai simplă şi este pentru a testa, de exemplu, dacă media duratei a proiectului µ, este sau nu realizată. Aceste teste statistice pot fi secvenţiale şi implică aplicarea tehnicilor statistice standard. Această abordare are însă dezavantajul că ea dă nişte informaţii întâmplătoare despre distribuţia duratei proiectului.

            A doua aplicaţie a tehnicii, oferă foarte multă oportunitate şi va fi considerată în cele ce urmează. Aceasta presupune următorul algoritm de calcul:

            Pasul 1. Se generează duratele aleatoare ale activităţilor conform cu anumite distribuţii date (Beta, lognormală, uniformă, normală, triunghiulară) în intervalul [A,B], în orice fel de combinaţie. Această flexibilitate permite, în particular, să încercăm diferite distribuţii şi să observăm efectele ce se obţin în cazul neglijării sau luării în considerare a distribuţiei fiecărei activităţi.

            Pasul 2. Se calculează drumul critic, folosind metoda clasică, găsindu-se activităţile critice şi termenele activităţilor.

            Pasul 3. Se determină duratele T_i de realizare a proiectului. Se repetă etapele 1, 2, 3, de N ori, N suficient de mare. Media µ şi dispersia σ_T² a duratei totale T a lucrării, sunt date de formulele:

            Pasul 4. Pentru fiecare activitate se determină indicele de criticalitate: C_ij = v_ij / N unde v_ij este numărul care exprimă de câte ori activitatea (i,j) a fost activitate critică din cele N cazuri studiate. Indicele de criticalitate al unei activităţi, reprezintă probabilitatea ca acea activitate să fie critică.

            Activităţile cu indicii C_ij mai mari, formează drumurile critice din graf.

            Întrucât se consideră un număr suficient de mare de realizări, teorema limită centrală, spune că  este o foarte bună aproximaţie normală cu media µ_x şi dispersia σ_x²/N, notată cu NOR(µ_x, σ_x²/N), unde media pentru X, (variabila aleatoare corespunzătoare duratei proiectului) este μ_x = M[x], iar σ_x², reprezintă dispersia lui X.

            Este clar că valoarea lui N are influenţă asupra gradului de exactitate al estimaţiei lui μ_x.

 

            Metode de generare a variabilelor aleatoare de distribuţii date specifice reţelelor PERT. Modelul de mai sus, presupune că duratele de execuţie ale activităţilor sunt variabile aleatoare. Dacă X este o astfel de variabilă ea trebuie să aibă următoarele proprietăţi.

            C1. SĂ fie mărginită, adică să existe un interval finit astfel încât P(xÏ[A,B]) = 0.

            C2. SĂ existe o valoare M cea mai probabilă M Î [A,B], adică X să fie o variabilă aleatoare unimodală.

            C3. Din inegalitatea lui Cebâşev rezultă că dacă μ = M[x], iar σ² este dispersia lui X, atunci ; de aceea se poate impune ca variabila de tip PERT să aibă şi proprietatea B - A = 6σ.

În problemele de tip PERT în care duratele sunt aleatoare, intervin de obicei următoarele distribuţii ale duratelor activităţilor:

            a) Distribuţia uniformă, sau rectangulară, care are densitatea

            b) Distribuţia normală a cărei funcţie de densitate este următoarea:

 

unde m şi σ desemnează parametrii distribuţiei. În cazul problemelor PERT, ne interesează însă determinarea cu o probabilitate dată a parametrilor m şi σ în intervalul (a,b). În această situaţie vom avea:

            Punând 5, vom obţine integrala lui Laplace:

unde valorile lui φ se obţin din tabele. Se demonstrează că punând

m = a+3σ, atunci P(m-3σ < x <m + 3σ) = 0,99 adică, variabila aleatoare X care urmează o lege normală aparţine intervalului (a,b) cu o probabilitate foarte aproape de unitate (regula celor trei sigma).

 

            c) Distribuţia lognormală. Variabila aleatoare Y se numeşte lognormală dacă x = lny are o repartiţie normală, adică:

 

            De obicei, duratele activităţilor au repartiţii lognormale. Această variabilă nu satisface în mod riguros condiţia C1, însă se poate arăta că oricare ar fi 8, există un interval (A,B) astfel că 9.

 

            d) Distribuţia Beta. O variabilă aleatoare V are repartiţia Beta dacă densitatea sa de repartiţie este:

unde

Dar V nu satisface condiţiile C1 şi C2 de mai sus; de aceea trebuie să facem transformarea  W = (B-A)·V + A. Densitatea de repartiţie a variabilei W este:

                                                                                                                                (6.18)

             Aceasta este repartiţia β nestandardizată, pentru care avem:

                                                                                                                                (6.19)

            Dăm în continuare, algoritmi de generare a variabilelor de distribuţie uniformă, normală, lognormală şi beta specifice problemelor Pert.

            1. Generarea (variabilelor) duratelor aleatoare cu distribuţie uniformă, pe un interval dat [A,B] presupune următorul algoritm:

            a₁ - se generează un număr aleator uniform distribuit u Î (0,1);

            a₂ - se consideră ca durată a unei activităţi valoarea care se obţine pentru X calculând expresia X = A +(B-A)·u.

            2. Pentru generarea unei variabile normale pe un interval dat [A,B], ţinem seama de regula celor 3 sigma şi de teorema limită centrală. Algoritmul în această situaţie presupune următoarele etape:

            a₁ - Se calculează

            a₂ - Se calculează µ = A + 3σ;

            a₃ - Se generează n=12 numere aleatoare u₁,...,u₁₂ uniforme pe (0,1) şi independente;

            a₄ - Se calculează . Variabila Z are o repartiţie normală N(0,1), deoarece pentru n=12, teorema limită centrală se poate considera adevărată;

            a₅ - Se calculează X = µ + σ z. Se consideră valoarea lui X ca durată a activităţii în cursul unei "realizări".

            3. Pentru generarea unei variabile aleatoare lognormale pe un interval [A,B] dat se aplică următorul algoritm:

            a₁ - Se calculează media m şi dispersia s cu ajutorul formulelor următoare:  unde σ şi µ sunt dispersia, respectiv media unei variabile normale pe [A,B];

            a₂ - Se calculează µ₁ şi σ₁ conform formulelor următoare:

   şi  

            a₃ - Se generează o variabilă Z normală N(0,1) folosind procedeul arătat la punctul 2;

            a₄ - Se calculează y = µ₁+zσ₁ (variabila y este normală N(µ₁, σ₁));

            a₅ - Se calculează (x=lny), variabila X este variabila lognormală generată.

            4. Pentru generarea variabilelor de tip beta pe un interval [A,B] se şine seama de următoarea teoremă: dacă x₁ şi x₂ sunt variabile aleatoare independente de tip gama avâd respectiv parametrii (p,λ), (q,λ) atunci variabila V = x₁ / (x₁ + x₂), este o variabilă beta de parametrii p şi q. Conform teoremei, generarea unei variabile beta se reduce la generarea a două variabile de tip gama pentru λ dat.

            Algoritmul este următorul:

            a₁ - se consideră că (B-A)/6 şi că μ = A + 3σ_T ipoteză presupusă adevărată în cazul distribuţiei Beta;

            a₂ - se determină p şi q din relaţiile (6.18) şi (6.19);

            a₃ - se generează o variabilă gama conform formulei x₁ = - log(T₁. T₂ ... T_p)/λ unde T₁ T₂ ...T_p sunt p numere aleatoare uniforme pe (0,1);

            a₄ - Se generează a doua variabilă gama utilizând formula

x₂ = -log(T₁ ...T_q)/λ unde T₁... T_q au aceiaşi semnificaţie ca şi T₁ ...T_p.

            a₆ - variabila este variabila beta utilizată ca durată a unei activităţi în calculul unei "realizări" a proiectului.

 

             Analiza performanţelor aplicării simulării Monte Carlo pentru determinarea duratelor a unui proiect Rezolvarea grafului din figura 6.11 şi utilizând metoda PERT clasică, a dus la obţinerea următoarelor rezultate: durata proiectului este de 66.0 iar dispersia este 60.27, drumul critic trecând prin 1-2-4-5-9. Metoda Monte Carlo utilizând 10.000 realizări implică o medie de 67.0 ± 0.13 şi o dispersie de 44.3 ± 2 în cazul utilizării distribuţiei beta. În figura 6.11 sunt trecuţi indicii de criticalitate obţinuţi în urma aplicării metodei Monte Carlo. Valorile acestora pot fi considerate ca o măsură utilă a gradului de atenţie pe care conducătorul proiectului, o acordă fiecărei activităţi a proiectului. Notăm de asemenea faptul că activităţile 6-8 şi 8-9 nu sunt niciodată critice. De fapt, ele nu pot fi critice, dar algoritmul determinist nu ne poate da o asemenea informaţie.

 

                                                                                                Fig. 6.4.

 

            Notăm că abordarea statistică a determinat acelaşi drum critic, însă prin simulare drumul critic a fost determinat în condiţiile în care s-a impus un grad de siguranţă mult mai mare decât în cazul modelului determinist, obţinându-se totodată şi un surplus de informaţii.

            Trebuie însă să arătăm că acest exemplu constituie un caz simplu de graf întâlnit în practică. În realitate, există reţele mult mai complexe pentru care simularea Monte Carlo oferă rezultate mult mai interesante, rezolvând şi înlăturând erorile pe care le presupune metoda PERT calsică.

            Practica simulării Monte Carlo în determinarea duratelor de execuţie a proiectelor a demonstrat că, foarte mult timp, se consumă cu generarea numerelor aleatoare, astfel încât timpul de rulare este esenţial o funcţie liniară de numerele aleatoare generate sau, pentru o aceeaşi reţea, o funcţie liniară de numărul activităţilor din reţea. Aceste relaţii sunt adevărate pentru reţele foarte mari cu un grad mare de arborescenţă. Pentru o reţea de 200 activităţi şi 10.000 de cicluri de simulare utilizând un program pentru IBM 7090, timpul de rulare a fost, în jur de 20 de minute pentru distribuţii triunghiulare şi în jur de cinci minute pentru distribuţii uniforme. În cazul folosirii metodelor analitice timpul de rulare creşte exponenţial cu numărul arcelor.

            În scopul micşorării duratei de rulare se propun diverse metode. Două dintre acestea ni se par mai interesante:

            - se consideră realizarea obţinută prin punerea tuturor duratelor activităţilor la cel mai scăzut punct al şirului de valori şi găsim drumul critic corespunzător proiectului şi durata lui, l. Punem apoi toate duratele activităţilor care nu sunt pe drumul critic la valoarea lor cea mai înaltă. Se determină activităţile care sunt pe drumurile cu lungime mai mare decât l. Activităţile care n-au fost luate în considerare după cele două teste sunt înlăturate, urmând numai pentru cele rămase să se aplice simularea Monte Carlo;

            - în cazul în care nu ne interesează distribuţia exactă a duratei proiectului ci numai media şi durata ei, activităţile care sunt întotddeauna critice sunt înlocuite cu activităţi deterministe cu duratele egale cu mediile distribuţiilor originale.