O problema de ordonantare consta in stabilirea unei ordini de efectuare a operatiilor (activitatilor) unui proiect, astfel ca interdependentele dintre ele sa fie respectate in cadrul resurselor disponibile si durata totala de executie a acestuia sa fie minima.

Pentru a putea concretiza definitia de mai sus, trebuie clarificate notiunile de proiect, operatii (activitati) ale acestuia, interdependente intre operatii si resursa a proiectului.

1. Prin proiect vom intelege o actiune de mare amploare sau un proces complex destinat atingerii unui scop bine precizat. La un proiect deosebim urmatoarele caracteristici:

- un obiectiv, care poate fi un produs, o cantitate de informatii sau un rezultat de natura organizatorica;

- un ansamblu de activitati (subactiuni, subprocese, operatii), corelate logic si tehnologic, a caror realizare permite atingerea scopului propus;

- un proces tehnologic prin care se precizeaza interconditionarilor intre activitati, interesand in special ordinea de executie a acestora.

Proiectele pot fi clasificate dupa natura lor in:

- proiecte industriale si proiecte de investitii, prin care se obtine un produs material (de exemplu constructia unei cladiri, pod, tunel, etc);

- proiecte organizatorice al caror scop este de a obtine un rezultat de natura informationala sau organizatorica (de exemplu un proiect de cercetare stiintifica).

Pentru a permite o analiza amanuntita a desfasurarii lui, o alegere a variantelor optime de

executie si un control continuu al evolutiei sale, trebuie sa descompunem proiectul in parti componente la un nivel care sa permita tratarea unitara a fiecarei parti si stabilirea conexiunilor intre acestea. Aceste componente se numesc operatii sau activitati.

O activitate este o parte distincta dintr-un proiect, un subproces precis determinat, care consuma timp si resurse. Vom presupune in continuare ca activitatile au urmatoarele proprietati:

- fiecare activitate este indivizibila (nu se mai descompune in subactivitati); - fiecare activitate are o durata cunoscuta;

- o activitate, odata inceputa, nu mai poate fi intrerupta.

Dintre interconditionarile (interdependentele) dintre activitati, ne intereseaza, in special, cele temporale, numite relatii de precedenta, care pot fi de trei tipuri:

1. de tip "terminare – inceput". Acest tip este cel mai frecvent intalnit si spunem ca o activitate A precede activitatea B printr-o interdependenta de tip "terminare – inceput" daca activitatea B nu poate incepe decat dupa un interval de timp t_AB de la terminarea activitatii A. Acest interval poate fi egal si cu zero, caz in care spunem ca activitatea A precede direct activitatea B;

2. de tip "inceput – inceput". Acest tip este frecvent intalnit si spunem ca o activitate A precede activitatea B printr-o interdependenta de tip "inceput – inceput" daca activitatea B nu poate incepe decat dupa un interval de timp t_AB de la inceperea activitatii A. Acest interval poate fi chiar mai mare decat durata activitatii A, caz in care avem de fapt o dependenta de tipul "terminare – inceput", putand chiar privi primul tip ca un caz particular al celui de-al doilea;

3. de tip "terminare – terminare". Spunem ca o activitate A precede activitatea B printr-o interdependenta de tip "terminare – terminare" daca activitatea B nu se poate termina decat dupa un interval de timp t_AB de la terminarea activitatii A sau ca activitatea A trebuie terminata cu cel putin t_AB unitati de timp inaintea terminarii activitatii B.

Prin durata totala de executie a unui proiect intelegem intervalul de timp in care se efectueaza toate activitatile acestuia, respectand toate interdependentele dintre activitati.

A programa un proiect inseamna a stabili termenele de incepere pentru fiecare activitate in parte, tinand seama de restrictiile impuse de procesul tehnologic, duratele activitatilor si resursele disponibile. Pentru un proiect dat, exista un numar enorm de programari admisibile. Un interes deosebit prezinta programul optim, adica acel program care, pe de o parte, satisface restrictiile impuse iar, pe de alta parte, optimizeaza un anumit criteriu de eficienta economica.

Criteriul de optimizare nu este acelasi pentru toate proiectele, el este stabilit pentru fiecare caz in parte si defineste obiectivele majore ale conducerii proiectului. In functie de aceste obiective, criteriul poate fi durata totala minima, costul total minim, folosirea cat mai uniforma a resurselor sau o sinteza a acestora. Deci, programul optim este acea desfasurare a proiectului, precizata prin termenele de incepere ale activitatilor, care conduce la o eficienta maxima.

Deoarece, asa cum se vede si din cele spuse mai sus, situatiile din practica ce necesita rezolvarea unei probleme de ordonantare sunt foarte variate, s-au propus numeroase modele pentru rezolvarea lor. In continuare vor fi prezentate cateva dintre modelele cele mai frecvent utilizate in practica.

 

 

 

1. Modele de analiza a drumului critic (ADC)

Principiul analizei drumului critic consta in divizarea unui proiect (actiuni complexe) in parti componente, la un nivel care sa permita corelarea logica si tehnologica a acestora, adica sa faca posibila stabilirea interactiunilor intre partile componente. Aceste parti componente sunt activitatile actiunii complexe.

La definirea listei de activitati specialistul sau specialistii care participa la aceasta operatie folosesc experienta lor pentru a raspunde pentru fiecare activitate la intrebarile: ”ce alte activitati succed sau preced in mod necesar aceasta activitate ?”; ”care este durata activitatii ?”. Ia nastere in acest fel un tabel care contine activitatile proiectului, interconditionarile intre activitati si duratele acestora.

Un astfel de tabel trebuie sa contina cel putin urmatoarele elemente:

- activitati: in aceasta coloana se enumera activitatile proiectului, fiind puse in evidenta printr-o denumire sau printr-un simbol (codul activitatii);

- conditionari: se precizeaza, pentru fiecare activitate, activitatile imediat precedente, prin simbolurile lor; activitatile de start nu au activitati precedente, in casuta fiind trecuta o liniuta;

- durata: pentru fiecare activitate se precizeaza durata de executie, intr-o anumita unitate de masura. Durata unei activitati este o constanta.

Modelele de analiza a drumului critic se bazeaza pe reprezentarea proiectului printr-un graf, elementele tabelului asociat acestuia fiind suficiente pentru a construi graful corespunzator.

In tabelul 1 este prezentat un proiect, activitatile fiind notate prin litere mari A, B, C, …. Activitatile A si B sunt activitatile de inceput ale proiectului. Activitatea A este direct precedenta activitatii C. De asemenea, activitatea C este direct precedenta activitatilor E si F.

Tabelul 1

Nr. crt. Activitatile proiectului Activitatile direct precedente Durate

(conditionari)

1 A - 3

2 B - 2

3 C A 2

4 D B 6

5 E B 4

6 F C,D,E 4

7 G E 1

 

 

Exista mai multe moduri de a reprezenta un proiect printr-un graf, cele mai cunoscute fiind prezentate mai jos:

 

 

A. Metoda CPM (Critical Path Method)

Metoda CPM este un procedeu de analiza a drumului critic in care singurul parametru analizat este timpul si in reprezentarea graficului retea se tine seama de urmatoarele conventii:

- fiecarei activitati i se asociaza un segment orientat numit arc, definit prin capetele sale, astfel fiecare activitate identificandu-se printr-un arc;

- fiecarui arc i se asociaza o valoare egala cu durata activitatii pe care o reprezinta;

- conditionarea a doua activitati se reprezinta prin succesiunea a doua arce adiacente. Nodurile grafului vor reprezenta momentele caracteristice ale proiectului, reprezentand

stadii de realizare a activitatilor (adica terminarea uneia sau mai multor activitati si/sau inceperea uneia sau mai multor activitati).

Procedeul CPM se bazeaza pe existenta unei corespondente bipartide intre elementele unui proiect (activitati, evenimente) si elementele unui graf (arce si noduri). Se obtine o relatie model- obiect, care pune in evidenta particularitatile de o mare insemnatate practica, in special, proprietatile de succesiune temporala.

Pentru reprezentarea corecta a proiectului (respectarea interdependentelor, claritatea desenului etc), cat si pentru o standardizare a reprezentarii (pentru a putea fi inteles si de altcineva decat cel care l-a desenat) in desenarea grafului se respecta urmatoarele reguli:

1. fiecare activitate se reprezinta printr-un arc a carui orientare indica, pentru activitate, desfasurarea ei in timp;

2. un arc este limitat prin doua noduri (reprezentate prin cerculete) care simbolizeaza momentele de inceput si de sfarsit ale executarii activitatii corespunzatoare;

3. lungimea fiecarui arc, in general, nu este proportionala cu lungimea activitatii; 4. activitatile vor fi reprezentate prin arce de forma:

sau sau sau

 

 

sau sau sau

 

 

esentiala fiind portiunea orizontala, pe care se vor trece informatiile despre activitate, portiunile oblice fiind la 45°.

Lungimea si inclinarea arcului au in vedere numai considerente grafice, pentru urmarirea usoara a intregului graf.

5. deoarece respectarea tuturor regulilor nu se poate face doar cu arce care corespund doar activitatilor proiectului, vor exista si arce care nu corespund nici unei activitati, care vor fi reprezentate punctat si care, pentru unitatea prezentarii, vor fi numite activitati fictive, ele neconsumand resurse si avand durata 0.

6. pentru reprezentarea unor dependente de tipul "terminare – inceput" in care t_AB > 0, vom introduce niste arce reprezentate prin linii duble, care corespund intervalului t_AB, avand semnificatia unor asteptari (in acest interval se "consuma" doar timp, nu si resurse) si care vor fi numite activitati de asteptare.

Daca se presupune ca o activitate A este precedenta activitatii B, in functie de tipul de interdependenta, in graficul retea arcele corespunzatoare activitatilor A si B vor avea urmatoarea reprezentare:

A t_AB B

sau (pentru t_AB = 0) A B

 

terminare - inceput

 

A A₁ A₂

t_AB sau t_AB

B B

 

inceput - inceput

A

B

sau

A t_AB B₁ t_AB

B₂

terminare - terminare

 

Figura 1

 

7. in graf nu sunt admise circuite (existenta unuia ar insemna ca orice activitate a acestuia ar fi precedenta ei insusi). Deoarece, pentru un proiect foarte mare graful va avea foarte multe arce, se poate intampla sa cream un circuit fara sa ne dam seama. Pentru a evita acest lucru, vom introduce o regula mai usor de respectat, care o implica pe cea dinainte:

8. nodurile vor fi numerotate, numerotarea facandu-se in asa fel incat, pentru fiecare activitate, numarul nodului de inceput sa fie mai mic decat numarul nodului de final al activitatii.

9. graful are un singur nod initial (semnificand evenimentul "inceperea proiectului") si un singur nod final (semnificand evenimentul "sfarsitul proiectului");

10. orice activitate trebuie sa aiba cel putin o activitate precedenta si cel putin una care ii succede, exceptand bineinteles activitatile care incep din nodul initial al proiectului si pe cele care se termina in nodul final al proiectului;

11. desi exista activitati care se executa in paralel, care pot incepe in acelasi moment si se pot termina in acelasi moment, este interzis ca cele doua arce corespunzatoare sa aiba ambele extremitati comune, altfel desenul care rezulta nu mai e graf. In desenul de mai jos se arata care este reprezentarea corecta, F fiind o activitate fictiva:

A A F A

B sau

B B F

incorect corect

Figura 2

12. nu trebuie introduse dependente nereale (neprevazute in tabelul de conditionari). Astfel, daca in tabelul de conditionari vom avea situatia:

Tabelul 2

Activitate Activitate direct precedenta (conditionari)

A -

B -

C A,B

D A

atunci reprezentarea:

A C

 

 

 

 

 

B D

Figura 3

este incorecta, deoarece introduce conditionarea, inexistenta in tabel, a activitatii D de activitatea B. Reprezentarea corecta este:

A C

 

 

 

B D

 

Figura 4

13. sa se foloseasca, pe cat posibil, numarul minim de activitati fictive, pentru a nu complica excesiv desenul. De exemplu acelasi efect ca in figura 4 putea fi obtinut si prin reprezentarea:

A

C

 

B D

 

Figura 5

dar am fi folosit o activitate fictiva in plus, inutila.

Daca doua sau mai multe activitati au aceeasi activitate direct precedenta, de exemplu A precede B si A precede C, reprezentarea in graful-retea va avea forma din figura 5 (a). Arcele B si C simbolizeaza doua activitati care nu pot incepe decat dupa ce s-a terminat activitatea A. Activitatile B si C pot fi executate simultan. De asemenea executia unei activitati poate depinde de terminarea mai multor activitati direct precedente, de exemplu A precede C si B precede C ca in figura 5 (b). In aceasta situatie, activitatea C nu poate incepe, logic, decat dupa ce s-au terminat activitatile A si B.

B A

 

A C

 

C B

 

(a) (b)

 

Figura 6

Proiectul dat prin tabelul 1, poate fi modelat, in reprezentarea activitatilor pe arce, prin graful-retea din figura 6, numerotat secvential.

A C

2

F

5

1 D

B 6

3

E G

4

 

Figura 7

 

Numerotarea nodurilor permite sa identificam fiecare activitate prin perechea de noduri (de inceput si sfarsit). De exemplu, activitatea D se identifica prin perechea (3,5), activitatea E prin (3,4) etc.

 

 

Analiza proiectului

Analiza proiectului consta in determinarea duratei minime a proiectului, determinarea intervalelor de timp in care poate avea loc fiecare din evenimentele reprezentate prin noduri si determinarea intervalelor de timp in care pot fi plasate activitatile, astfel incat sa se respecte toate conditionarile si sa obtinem timpul minim de executie al proiectului.

Este evident ca durata minima de executie a proiectului este cel mai mic interval de timp in

care pot fi efectuate toate succesiunile de activitati din proiect. O succesiune de activitati corespunde unui drum in graf si deci, durata minima de executie a proiectului este cel mai mic minorant al lungimilor tuturor drumurilor din graf. Cum exista un numar finit de drumuri, multimea lungimilor acestora este finita si cel mai mic minorant al ei este maximul acesteia, adica durata drumului de lungime maxima. Deoarece graful nu are circuite si are un singur punct initial si unul

singur final, este evident ca cele mai lungi drumuri vor fi cele dintre nodul initial si cel final. Avem deci de gasit drumul de lungime maxima dintr-un graf fara circuite, caz in care se poate aplica algoritmul lui Ford simplificat.

Conform acestui algoritm, se calculeaza pentru fiecare nod al grafului:

A. Termenul cel mai devreme de realizare a evenimentului j. Acest termen reprezinta momentul cel mai devreme posibil de terminare a tuturor activitatilor care converg in nodul j si este egal cu valoarea maxima a drumurilor dintre evenimentul initial 1 si evenimentul j, pe care il vom nota cu t m j

= d_max(1,j). Termenul cel mai devreme (numit si termenul minimal) a evenimentului j, conform algoritmului lui Ford in grafuri G = (X,G) fara circuite, se calculeaza astfel:

m jt = max ( )n t m i + d ij , 1 < j =

( ) i, j ∈ G

Vom presupune, fara a restrange generalitatea, ca t₁ = 0, pentru evenimentul initial 1 si, in acest caz, termenul de realizare cel mai devreme al unui eveniment oarecare j va fi dat de formula:

  0 j = 1

m jt = max ( ) t m i + d 1 < j = n

  ( )