1

Capitolul 6 MMooddeellaarreeaa pprriinn ggrraaffuurrii IIII

PPEERRTT ii MMeettooddaa ddrruummuulluuii ccrriittiicc

6.1. Introducere

Grafurile pot fi utilizate ca un ajutor n planificarea proiectelor complexe care constau din mai multe activiti. Dac durata fiecrei activiti se cunoate cu siguran, metoda drumului critic (CPM - Critical Path Method) se poate utiliza la determinarea duratei necesare realizrii unui proiect. CPM se mai poate utiliza i la determinarea duratei cu care fiecare activitate poate fi ntrziat fr a se ntrzia realizarea proiectului. CPM a fost dezvoltat la sfritul anilor 50 de ctre cercettorii de la du Pont and Sperry Rand.

n cazurile cnd nu se cunoate cu siguran durata activitilor, se poate folosi PERT (Program Evaluation and Review Technique - Tehnica de Evaluare i Analiz a Planului) la estimarea probabilitii cu care un proiect se va realiza la un moment dat de timp. PERT a fost dezvoltat la sfritul anilor 50 de ctre consultanii care lucrau la dezvoltarea rachetei Polaris. Faptul c racheta Polaris a fost operaional cu doi ani naintea planificrii a condus la impunerea metodelor CPM i PERT.

Cele dou metode CPM i PERT au fost utilizate cu succes n multe aplicaii, printre care: Planificarea proiectelor n construcii, cum sunt cldiri, autostrzi i piscine. Planificarea mutrii unui spital de 400 de paturi; Dezvoltarea numrtorii inverse la lansarea navetelor spaiale; Instalarea unui nou sistem computerizat; Conceperea i realizarea unui nou produs; Construirea unei nave.

Pentru aplicarea metodelor CPM i PERT este necesar o list de activiti care vor alctui proiectul. Proiectul este considerat ndeplinit cnd fiecare activitate ce-l compune a fost realizat. Pentru fiecare activitate exist un set de activiti, numite activiti predecesoare, care trebuie s fie realizate naintea nceperii activitii curente. Graful este utilizat la reprezentarea legturii dintre activiti. n continuare, activitile vor fi reprezentate prin arce directe, iar terminarea unor seturi de activiti prin noduri. Din acest motiv, adesea se face referire la nodurile unui proiect prin evenimente. Acest tip de graf este numit activitate pe arc (APA).

Pentru a nelege cum se reprezint legtura dintre activiti predecesoare, se presupune c activitatea A este predecesoarea activitii B. Fiecare nod dintr-un graf APA reprezint

2 Modelare i simulare n afaceri

terminarea unei sau mai multor activiti. Astfel, n figura 6.1.a, nodul 2 reprezint terminarea activitii A i nceperea activitii B. Dac se presupune c activitile A i B trebuie terminate nainte ca activitatea C s nceap, acestea pot fi reprezentate ca n figura 6.1.b (nodul 3 reprezint faptul c activitile A i B sunt terminate). n figura 6.1.c se reprezint cazul n care activitatea A este predecesoare ambelor activiti B i C.

Fiind dat o list de activiti, reprezentarea APA a unui proiect, numit diagrama proiectului, poate fi construit utiliznd urmtoarele reguli:

1. Nodul 1 reprezint nceputul proiectului. Un arc care ncepe de la nodul 1 reprezint activitatea care nu are predecesori.

2. Nodul numit nod final reprezentnd terminarea proiectului trebuie inclus n graf. 3. Numrul de noduri care reprezint terminarea unor activiti trebuie s fie mai

mare dect numrul de noduri care reprezint nceputul unor activiti. 4. O activitate trebuie reprezentat printr-un singur nod. 5. Dou noduri pot fi conectate prin cel mult un singur arc.

Pentru a evita nclcarea regulilor 4 i 5, uneori este necesar a se introduce o activitate nul (ca timp) sau fictiv. Activitile fictive se noteaz prin arce punctate. De exemplu, fie A i B dou activiti predecesoare ale ale activitii C care pot ncepe n acelai timp. n absena regulii 5, reprezentarea este redat n figura 6.2.a. Totui, deoarece nodurile 1 i 2 sunt conectate prin mai mult de un singur arc, se ncalc regula 5. Prin utilizarea unei activiti nule, figura 6.2.b, se poate reprezenta faptul c A i B sunt predecesoarele activitii C. Prin aceast reprezentare se asigur faptul c activitatea C nu poate ncepe dect dup terminarea activitilor A i B fr nclcarea regulii 5.

Pentru determinarea timpului total de realizare a proiectului se observ c durata total de execuie nu poate fi mai mic dect suma timpilor de pe drumul de valoare maxim dintre punctul x0 de intrare n reea i punctul de ieire, xN. Drumul de lungime maxim din reea se numete drum critic iar operaiile prin care trece drumul critic se numesc operaii critice. Drumul cel mai lung se numete drum critic deoarece durata final a activitilor este ntrziat dac oricare din activitile aflate pe acest drum este ntrziat. Astfel drumul critic determin durata minim de execuie a ntregului proiect. Operaiile care nu sunt aflate pe drumul critic pot fi amnate sau dein rezerve de timp.

6.2. Activitile ntr-o reea PERT

Atunci cnd un proiect este planificat sau analizat, trebuie identificat fiecare activitate individual i stabilite relaiile de preceden, astfel nct s se cunoasc activitile care trebuie indeplinite nainte ca s nceap o alta. De asemenea, trebuie aflate i estimrile privind timpul ndeplinirii fiecrei activiti. Metoda PERT presupune c timpul de ndeplinire a unei activiti urmrete o distribuie Beta. Acest lucru se traduce matematic prin exprimarea mediei timpului de ndeplinire a unei activiti, t, ca fiind dat de formula:

64 bma

t++

= (6.1) iar distribuia timpului de ndeplinire, 2, este:

22

6

=

ab (6.2)

unde a este cel mai optimist timp de ndeplinire a activitii, m cel mai probabil iar b cel mai pesimist.

Modelarea prin grafuri II PERT i metoda drumului critic 3

Dup ce au fost determinate relaiile de preceden i timpul estimat de ndeplinire pentru fiecare activitate, se poate construi reeaua PERT. Aceasta const din noduri i arce direcionate. Arcele reprezint activitile. Fiecare arc este etichetat deasupra cu o liter care identific activitatea i dedesupt cu un numr care reprezint timpul estimat de ndeplinire a activitii. Fiecare arc are o sgeat care marcheaz nodul de nceput i cel de sfrit al activitii. Nodurile reprezint puncte n timp la care sunt ndeplinite toate activitile anterioare imediate ale unei anumite activiti. Nodurile sunt numerotate cu ntregi, ncepnd cu 1, n ordine cresctoare.

Uneori o activitate poate avea unele activiti anterioare comune altor activiti. n acest caz se construiesc activiti fictive de durat zero astfel nct s se identifice clar nodurile cu precedent imediat.

6.3. Analiza PERT

Fiind dat o reea PERT, timpii cei mai devreme de ncepere a unei activiti (TDI) precum i timpii cei mai devreme de finalizare a unei activiti (TDS) sunt stabilii prin crearea traseului de naintare n reea. Acest traseu se construiete lund n considerare nodurile n ordinea cresctoare a etichetelor lor, (de exemplu: nodul 1, apoi nodul 2, etc.,) dup cum urmeaz:

0. Iniializare. Toate activitile care pleac din nodul 1, au TDI = 0; 1. Se analizeaz toate activitile care pleac din nodul curent. Pentru aceste activiti

TDS = TDI + t, unde t este timpul estimat de ndeplinire al activitii (6.1) 2. Se analizeaz activitile urmtorului nod, iar dac nu exist atunci STOP. Pentru toate

activitile care pleac din acest nod TDI este valoarea maxim a valorilor TDS corespunztoare activitilor care intr n nod. Se repet apoi procesul ncepnd cu pasul 1.

Pentru a marca timpii TDI i TDS ai fiecrei activiti, perechea [TDI, TDS] se trece deasupra arcului dup litera care indic activitatea. Cel mai timpuriu moment de realizare a proiectului, T, este dat de valoarea maxim a TDS care intr n ultimul nod.

Cel mai trziu timp de ncepere a activitii (TTI) i cel mai trziu timp de finalizare a activitii (TTS) sunt stabilii prin construcia traseului invers n reea. Aceast lucru se realizeaz lund n considerare nodurile n ordine descresctoare, dup cum urmeaz:

1. Iniializare. Pentru toate activitile care intr n nodul final, TTS =T 2. Se consider toate activitile care intr n nodul curent. Pentru aceste activiti, TTI =

TTS t. 3. Se consider urmtorul nod n ordine descresctoare, iar dac nu mai exist nici unul

atunci STOP. Pentru toate activitile care intr n acest nod, TTS = minumul TTI al activitilor care prsesc acest nod. Procesul se repet apoi de la pasul 1.

Pentru a marca perechile de timpi TTI i TTS al fiecrei activiti, pe fiecare arc, sub acesta i dup timpul estimat de realizare a activitii se nscrie perechea [TTI, TTS].

4 Modelare i simulare n afaceri

Odat cu calcularea acestor timpi, se poate calcula rezerva de timp (slack time) pentru fiecare activitate, prin scderea celui mai devreme timp de ncepere din cel mai trziu timp de ncepere sau scderea celui mai devreme timp de finalizare din cel mai trziu timp de finalizare. Rezerva reprezint timpul cu care poate fi ntrziat o activitate fr ca s fie ntrziat ntregul proiect. Secvena de activiti care prezint rezerva egal cu 0 este denumit drum critic.

Timpul estimat de realizare a proiectului, T, este timpul corespunztor nodului cu numrul cel mai mare. El egaleaz suma timpilor estimai pentru activitile de pe drumul critic. Distribuia, 2, pentru ntregul proiect este suma distribuiilor de pe drumul critic. Timpul de ndeplinire se consider a avea o distribuie normal. De aici, probabilitatea ca proiectul s fie realizat la un moment de timp s, se gsete prin calcularea numrului de deviaii standard,

conform formulei:

Tsz

= i utiliznd tabele de stabilire a valorilor lui z conform

distribuiei normale. Trebuie observat c se presupune c activitile care nu se afl pe drumul critic nu afecteaz timpul total de ndeplinire a proiectului. n realitate ns, datorit ntrzierilor mari ale unei activiti necritice, timpul total poate fi afectat.

6.4. Metoda drumului critic

Dac un manager dorete resurse suplimentare pentru a ndeplini un proiect mai repede dect cel estimat, atunci va dori s tie i ct l cost acest efort. Pentru aceast analiz managerul poate utiliza metoda drumului critic (CPM Critical Path Method). Aceast metod consider timpii estimai ai unei reele ca fiind timpi normali fixai, , care necesit costurile normale Cn. Metoda presupune c:

(1) dac exist un cost maxim Cc, activitatea poate fi redus n timp la momentul ; (2) dac se cheltuiete ntre Cn i Cc pentru o activitate, atunci timpul ndeplinirii

activitii se reduce proporional.

Fie M timpul maxim cu care poate fi redus o activitate, de exemplu M=-. Fie, de asemenea, notat cu K acel cost corespunztor reducerii activitii cu o unitate, de exemplu:

MCC

K nc

= . Astfel, dac vrem s reducem timpul corespunztor unei activiti cu y uniti,

costul suplimentar va fi Ky.

Prin rezolvarea urmtorului model liniar se pot obine resursele suplimentare care sunt necesare ndeplinirii proiectului n timpul s.

Fie xi egal cu timpul reprezentat de ctre nodul i i yj reducerea de timp utilizat asupra activitii j. Atunci funcia obiectiv va fi:

MINyKzj

jj =

iar mulimea restriciilor este dat de urmtoarele elemente: (1) Proiectul trebuie terminat la momentul s, deci:

xN s (unde N este numrul de noduri) (2) Fiecare nod reprezint maximul timpilor cei mai devreme ai activitilor cu arce care

intr n nodul respectiv. Astfel, pentru activitatea j, ntre nodurile k i i, avem:

Modelarea prin grafuri II PERT i metoda drumului critic 5

xi xk + (timpul ndeplinirii activitii j, ca de exemplu xi xk + (j- yj) (existnd cte o restricie pentru fiecare activitate)

(3) Pentru fiecare activitate, reducerea de timp nu poate depi timpul disponibil, astfel c:

yj Mj (4) Toate variabilele de decizie sunt nenegative:

xi, yj 0 pentru toi i i j.

6.5. PERT/COST

PERT/COST este numele unei tehnici de monitorizare a costurilor unui proiect. Pachetele de lucru, care reprezint grupuri de activiti nrudite (executate de ctre un subcontractor, de exemplu), sunt utilizate pentru planificarea i controlul costurilor proiectului. Fiecare pachet de lucru are un buget sau cost estimat i un timp de finalizare.

Pachetele de lucru pot fi tratate ca activitile unui proiect astfel nct s se efectueze analiza PERT pentru determinarea celui mai devreme i a celui mai trziu timp de nceput i sfrit. Apoi, presupunnd c pachetele de lucru sunt distribuite echilibrat pe durata proiectului, se pot dezvolta diagrame ale costurilor proiectate pe baza celor mai devreme i trzii timpi de nceput. Aceste diagrame descriu lun de lun sau sptmn dup sptmn distribuirea proiectat a fondurilor. Astfel, la oricare punct al proiectului, fondurile care au fost deja cheltuite pe luna i trebuie s se ncadreze ntre fondurile care ar fi trebuit s fie cheltuite dac toate pachetele de lucru au fost ncepute la cele mai devreme timpi i la cele mai trzii timpi.

Astfel, dac notm cu Vi valoarea muncii pentru pachetul de lucru i, cu Pi procentul de realizare a pachetului de lucru i i cu Bi bugetul pachetului i, atunci:

ii

i BP

V

=

100

Apoi, dac ACi este costul actual la zi cheltuit pe pachetul de lucru i, diferena ntre valorile actuale i cele bugetate pentru pachetul de lucru i este:

iii VACD = Dac Di este pozitiv, pachetul de lucru I experimenteaz o depire a costurilor, iar dac Di este negativ atunci pachetul de lucru u experimenteaz o economie. Prin nsumarea tuturor diferenelor Di se calculeaz depirea de costuri a ntregului proiect. Dac aceast depire este substanial, atunci trebuie revzut fie ntregul proiect, fie trebuie luate msuri de corectare a costurilor activitilor cu depire a costurilor dar nefinalizate nc.

6.6. Problem rezolvat

AutoPrelSib este un productor de prelate auto. Firma confecioneaz att prelata ct i cadrul pe care aceasta este fixat pe main. Atunci cnd un client comand o prelat, operaiile ncep cu pregtirea documentelor iniiale, cum sunt comanda ferm cu toate specificaiile necesare, garanii, etc. Odat ce acestea au fost definitivate, este croit prelata i se confecioneaz cadrul. Dup construirea fiecrei piese, pot ncepe operaiile de finisare. Dup construcia prelatei i a cadrului, dar nu neaprat dup efectuarea operaiilor de finisare, poate ncepe documentarea final. Dup finisarea prilor se poate trece la asamblare, iar apoi

6 Modelare i simulare n afaceri

la inscripionare. Proiectul este considerat finalizat cnd toat documentaia a fost elaborat, prelata montat pe cadru i executat inscripionarea. Tabelul de mai jos ilustreaz timpul necesar fiecrei activiti.

Activitatea Descriere Timp de realizare (ore)

A Elaborarea documentaiei iniiale 3 B Construcia prelatei 3 C Construcia cadrului 2 D Finisarea prelatei 3 E Finisarea cadrului 7 F Elaborarea documentaiei finale 3 G Montarea prelatei pe cadru 6 H Inscripionarea 2

a) Trasai graful corespunztor reelei PERT; b) Gsii cei mai devreme i cei mai trzii timpi de nceput i finalizat pentru proiect; c) Ct va dura proiectul? d) Ce activiti nu pot fi ntrziate deoarece ar ntrzia ntregul proiect? e) Presupunnd c finisarea prelatei a fost ntrziat cu patru ore, cu ct va fi ntrziat

ntregul proiect?

Rezolvare

a) nainte de trasa diagrama PERT, trebuie identificate operaiile i succesiunea acestora, conform tabelului de mai jos.

Activitatea Predecesori imediai Timp de realizare (ore)

A - 3 B A 3 C A 2 D B 3 E C 7 F B, C 3 G D, E 6 H C 2

Pentru a trasa diagrama PERT, trebuie s existe un nod de finalizare a fiecrei intrri n coloana predecesorilor imediai att pentru nceputul ct i pentru sfritul fiecrei activiti. Astfel, diagrama PERT este conform figurii de mai jos. Remarcai faptul c a fost introdus un nod, numerotat 5, care exprim ndeplinirea celor dou operaii B i C. Nodul 3 reprezint finalizarea operaiei B, iar nodul 4 finalizarea operaiei C. Astfel, s-au introdus activitile fictive de durat zero care s conecteze nodurile 3 i 5 i respectiv 4 i 5.

Modelarea prin grafuri II PERT i metoda drumului critic 7

b) Cei mai devreme timpi sunt cei mai mari timpi dintre cei mai devreme timpi ai finalizrii unei activiti n nodul de nceput al activitii. Cei mai trzii timpi de finalizare sunt cei mai mici timpi dintre cei mai trzii timpi ai nceputului unei activiti la nodul de sfrit al activitii.

Traseul nainte

Nodul 1: TDIA = 0. Apoi, TDSA= 0 + 3 = 3. Nodul 2: TDIB = TDIC = TDSA = 3; TDSB = 3 + 3 = 6; TDSC = 3 + 2 = 5 Nodul 3: TDID = TDI0 = TDSB = 6; TDSD= 6 + 3 = 9; TDS0 = 6 + 0 = 6. Nodul 4: TDI0 =TDIE = TDIH = TDSC = 5; TDS0 = 5 + 0 = 5; TDSE = 5 + 7 = 12; TDSH = 5 + 2 = 7. Nodul 5: TDIF = max(TDS n nodul 5) = 6. TDSF = 6 + 3 = 9. Nodul 6: TDIG =max(TDS n nodul 6) = 12; TDSG = 12 + 6 = 18. Nodul 7: STOP, T= max(TDS n nodul 7) = 18.

A B C D E F G H 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

Traseul napoi

Nodul 7: TTSH = TTSG = TTSF = T = 18; TTIH = 18 2 = 16; TTIG = 18 6 = 12; TTIF = 18 3 = 15. Nodul 6: TTSD = TTSE = TTSG = 12; TTID = 12 3 = 9; TTIE = 12 7 = 5. Nodul 5: TTS0(sus) = TTS0(jos) = TTIF = 15; TTI0(sus) = 15 0 = 15; TTI0(jos) = 15 0 = 15. Nodul 4: TTSC = min(TTI din 4) = 5. TTIC = 5 2 = 3.

1 2

3

4

5

6

7 A

B

D

C

E

H

F

G

3

3

2

0

0

3

7 6

3

2

8 Modelare i simulare n afaceri

Nodul 3: TTSB = min(TTI din 3) = 9. TTIB = 9 3 = 6. Nodul 2: TTSA = min(TTI din 2) = 3. TTIA = 3 3 = 0. Nodul 1: STOP

A B C D E F G H 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

Astfel graful completat este:

Care conduce la urmtorul tabel rezumativ:

Activitatea TDI TDS TTI TTS Rezerva A 0 3 0 3 0 B 3 6 6 9 3 C 3 5 3 5 0 D 6 9 9 12 3 E 5 12 5 12 0 F 6 9 15 18 9 G 12 18 12 18 0 H 5 7 16 18 11

Rezerva este calculat fie prin diferena TTS-TTI fie TDS TDI pentru fiecare activitate.

c) TDS la nodul 7 este de 18 ore. d) A, C, E i G au rezerva zero, de aceea ele sunt pe drumul critic. e) Finisarea prelatei este activitatea D. Aceasta prezint o rezerv de 3 ore. Astfel, dac

se nregistreaz o ntrziere de 4 ore la finisare, ntregul proiect va fi ntrziat cu 1 or.

1 2

3

4

5

6

7 A[0,3]

B[3,6]

D[6,9]

C[3,5]

E[5,12]

H[5,7]

F[6,9]

G[12,18]

3[0,3]

3[6,9]

2[3,5]

0[15,15]

0[5,5]

3[9,12]

7[5,12]

6[12,18]

3[15,18]

2[16,18]

[6,6]

[15,15]

Modelarea prin grafuri II PERT i metoda drumului critic 9

6.7. Teme

1. Construii reeaua descris de tabelul de mai jos. Calculai lungimea fiecrui traseu i indicai drumul critic.

Activitatea Timpul (luni)

1 2 4 1 3 7 2 4 8 2 5 3 3 5 9 4 5 5 4 6 2 5 6 6 3 6 5

2. Fie un proiect care const din 13 operaii, notate A, B, C, Tabelul urmtor conine durata realizrii fiecrei activiti, n zile, precum i operaiile precedente. Determinai drumul critic, rezerva total pentru fiecare operaie i graficul Gantt.

Activitatea A B C D E F G H I

J K L M

Activitatea precedent

- - A A A C C C B,D F,I G,J E,H K,L

Durata 9 3 8 2 3 2 6 1 4 1 2 3 4

3. Urmtorul proiect a fost analizat de ctre consiliul de administraie al unei firme.

Activitatea Predecesori imediai

Varianta optimist (n ore)

Variante cea mai probabil

(n ore)

Varianta pesimist (n ore)

A - 4 6 8 B - 1 4,5 5 C A 3 3 3 D A 4 5 6 E A 0,5 1 1,5 F B, C 3 4 5 G B, C 1 1,5 5 H E, F 5 6 7 I E, F 2 5 8 J D, H 2,5 2,75 4,5 K G, I 3 5 7

a). Construii diagrama PERT; b). Determinai cel mai devreme i cel mai trziu timp de finalizare a proiectului; c). Identificai drumul critic i timpul de finalizare a proiectului; d). Care este probabilitatea ca proiectul s fie realizat n 24 de ore?

10 Modelare i simulare n afaceri

4. Un fermier dorete s-i construiasc un grajd conectat la un generator de energie i un tanc cu ap. Activitile, descrierea lor precum i estimarea duratei activitilor este redat n tabelul de mai jos. Construii reeaua proiectului, identificai drumul critic i stabilii durata proiectului.

Activitatea Descriere Activitatea anterioar

Durata activitii (Sptmni)

A Escavare - 2 B nlarea cldirii A 6 C Instalarea generatorului A 4 D Instalarea tancului A 2 E Instalarea celorlate instalaii B 4 F Conectarea generatorului i tancului la

cldire B, C, D 5

G Zugrvirea cldirii B 3 H Verificarea facilitilor E, F 2

5. O firm dorete s introduc un produs nou. O unitate a produsului 3 este realizat prin asamblarea unei uniti a produsului 1 cu a unei uniti a produsului 2. nainte ca producia s nceap la produsele 1 i 2, trebuie achiziionate materiile prime i muncitorii trebuie pregtii. nainte ca produsele 1 i 2 s fie asamblate n produsul 3, produsul finit 2 trebuie verificat. Lista activitilor i a activitilor predecesoare acestora i durata fiecrei avtiviti este dat n tabelul de mai jos. S se alctuiasc diagramele PERT i Gantt ale acestui proiect.

Activitate Activiti predecesoare Durata (zile) A = pregtire muncitori - 6 B = achiziionare materii prime - 9 C = producerea produsului 1 A, B 8 D = producerea produsului 2 A, B 7 E = testarea produslui 2 D 10 F = asamblarea produselor 1 i 2 C, E 12