Cuprins
- 1. SCURT ISTORIC 3
- 2. DESCRIEREA METODEI 3
- 3. DEFINIȚIE 4
- 4. DETERMINAREA DRUMULUI CRITIC 4
- 4.1 DEFINIȚII ALE TERMENILOR SPECIFICI 5
- 4.2 ALGORIMI UZUALI DE DETERMINARE A DRUMULUI CRITIC 6
- 4.2.1 Algoritmul lui DANTZIG 7
- 4.2.2 Algoritmul lui BELLMAN – KALABBA 8
- 4. APLICAȚIA PRACTICĂ 9
Extras din proiect
1. Scurt istoric
Metoda drumului critic este derivată din metoda lantului critic, dezvoltată de Eliyahu Goldratt (Critical Chain Project Management - CCPM) care este bazată pe metode si altgoritmi derivati din teoria constrângerilor.
2. Descrierea metodei
Metoda drumului critic reprezintă o metodă de determinare a timpului minim necesar executiei integrale sau totale a unui proiect.
Metoda se aplică retelelor de planificare denumite grafuri retea. Fie u graf de forma G(X,U), cu X – multimea nodurilor din graf, U – multimea arcelor. Acesta este un graf retea dacă:
- există si este unic un punct x0 numit punct de intrare în retea astfel încât toate arcele din x0 sunt incidente spre exterior U-( x0 )= Ø;
- există si este unic un punct xn numit punct de iesire din retea astfel încât toate arcele sunt incidente spre interior lui xn U+ (xn )= Øs
- fiecărui arc i se atasează valarea arcului v(u).
În executarea unui proiect există unele operatii care nu se pot realiza decât dacă altele au fost deja realizate(ordonate). Mai există si alte operatii care se pot realiza simultan. Acestei probleme i se poate asocia un graf retea, finit, si fără circuite, astfel:
1. Activitătile sau operatiile ce consumă timp sau resurse se reprezintă prin arce orientate (ij), valoarea vij a arcului reprezintă durata de executie a activitătii;
2. Evenimentele sunt momente de timp ce indică începerea uneia sau mai multor activităti sau terminarea uneia sau mai multor activităti. În graf, evenimetele sunt vârfurile sau nodurile retelei.
În construirea unei retele de planificare, se au în vedere următoarele reguli:
a) numărul vârfului de început al activitătii este mai mic decât numărul vârfului de sfârsit;
b) două activităti care au în comun vârful de începere, nu pot avea în comun vârful de terminare.
Iată un exemplu incorect de construire a unei retele de planificare:
i j
În acest caz se introduce o activitate fictivă care nu consumă nici timp nici resurse:
k
i j
Activitătile fictive se figurează prin arce punctate si se introduc numai pentru a indica dependenta logică dintre activităti fără a încalca regulile de construire a retelei (respectiv regula b).
c) Arcul (i,j) va arăta una dintre activitătile ce trebuie desfăsurată după evenimentul i.
d) Orice activitate trebuie să aibă cel putin o activitate precedentă si cel putin una care o succede (în afară de punctele x0 si xn ).
Știind că durata totală de executie nu poate fi mai mică decât suma timpilor de pe drumul de valoare maximă dintre punctul x0 de intrare în retea si punctul de iesire xn , putem determina timpul total de realizare al proiectului.
3. Definitie
Drumul de lungime maximă din retea se numeste drum critic.
Operatiile prin care trece drumul critic se numesc opertii critice.
Drumul cel mai lung se numeste drum critic deoarece, dacă stadiul de realizare al activitătilor de pe acest drum creste, atunci durata finală este întârziată corespunzător.
În concluzie, drumul critic determină durata minimă posibilă de executie a întregului proiect.
Operatiile necritice permit eventuale amânări sau rezerve în sensul că se poate determina întârzierea maximă permisă fără a modifica durata totală de executie.
4. Determinarea drumului critic
Pentru determinarea drumului critic se aplică un algoritm ce contine 2 etape:
1. Se determină timpul cel mai devreme la care se poate începe o activitate care urmeză. Vom numi acest timp tim timpul minim de începere a activitătii (ij). Activitătile care pleacă din x0 , au t0m = 0. Pentru fiecare activitate care urmează avem: tjm=max(tim+ vij , tkm + vkj ).
Preview document
Conținut arhivă zip
- Utilizarea Tehnologiilor Informationale in Gestiunea Relatiilor cu Clienti.doc