Ministerul Învăţămîntului a Republicii Moldova

Universitatea Tehnică a Moldovei

Facultatea Calculatoare,Informatică şi Microelectronică

la disciplina ”Structuri de Date şi Algoritmi“ 

Tema: ”METODA DRUMULUI CRITIC”

“CRITICAL PATH METHOD “

A efectuat :Studentul grupei AI-082 Rusnac Denis

A verificat : Nastas Valentina

Chisinau 2009

“APROB” Şeful catedrei “Informatica aplicată” _________dr.,conf.univ.V.Moraru

Sarcina

Pentru lucrarea de curs la disciplina “Structuri de date şi algoritmi”Tema: Metoda drumului critic.

Scopul lucrarii:Studierea şi aplicarea algoritmului Ford pentru determinarea drumului critic într-un graf orientat.

Sarcina:Elaborarea programului care determina drumul critic, în limbajul de programare C.

DATA ÎNMÂNĂRII LUCRĂRII: 13 aprilie 2009

TERMENUL DE PREZENTARE A LUCRĂRII: 19 iunie 2009

Conducătorul lucrării: _____________ lector superior: Valentina Nastas

Executătorul lucrării _____________ studentul gr.AI-082 Rusnac Denis

1

1.Scurt istoric

Critical Path Method este procedeul fundamental al "analizei drumului critic" .In anul 1956 firma E. I. Du Pont de Nemours a creat un grup de studii, format din matematicieni şi analişti care aveau la dispozitie un calculator UNIVAC I. In 1957 la UNIVAC Application Research Center, sub conducerea lui 1. W. Mauchly, s-a pus la punct procedeul CPM de catre J. E. Kelley (de la Remington Rand) şi W. Walker (de la Du Pont). Procedeul a fost aplicat de firma Du Pont la revizia uzinei din Louisville şi a avut ca rezultat reducerea duratei lucrarilor de la 125 ore la 93 ore, şi apoi la 78 ore.In 1958 J. W. Mauchly Intemeiaza firma de consultare Mauchly Associates, care a avut un rol important in dezvoltarea şi difuzarea analizei drumului critic. Succesele obtinute cu ajutorul CPM încep sa intereseze un cerc larg de cercetatori şi utilizatori (universităţi, firme de consultare, intreprinderi) şi metoda cunoaşte o popularitate fără precedent.

In 1961 apare studiul lui Kelley "Critical - Path Scheduling: MathematicalBasis", in care CPM este prezentat Intr-o forma desavarşită [9].Procedeul CPM este o metoda folosita cu precădere de tarile anglo-saxone, cunoscuta şi ca metoda "sagitala", fiind una dintre cele mai simple procedee de analiza a drumului critic, constituind procedeul fundamental al ADC.CPM este considerat procedeul fundamental al ADC, deoarece procedeele mai perfectionate nu au facut altceva decît sa adînceasca şi sa extinda notiunile sale de baza,fără sa le anuleze sau sa le infirme.Procesul de conducere a unui proiect prin CPM ia in analiza parametrul timp, in care fiecare activitate are o durata constanta, corespunzatoare conditiilor normale de lucru, obtinandu-se programe de termene şi durata totala de executie.

Prin faptul ca procedeul CPM ia pentru analiza proiectelor numaiparametrul timp, acesta se incadreaza in procedeele ADC/TIME.

2. Note teoretice

a) Activitatile sunt actiuni sau conditii care contribuie la realizarea unui proiect. Principala caracteristica graficii a activitatilor este prezentarea lor sub forma de arce sau sageti orientate in sensul desfăşurarii procesului tehnologic. Fiecare activitate – Aij - este definita şi delimitata de durata – dij

b) Evenimentele sau fazele reprezinta anumite stadii de executie alucrarilor (activitatilor), marcand inceperea sau terminarea uneia sau mai multor activitati. Evenimentele sunt plasate in nodurile retelelor, delimiteaza activităţile şi marcheaza momente instantanee in desfaşurarea lor. La nivelul unui proiect, evenimentele ce contureaza nodurile graficelor în reţea se pot defini in raport cu semnificatia momentelor pe care le marchează astfel:

2

~ evenimentul initial "0" este evenimentul ce marcheaza inceputul proiectului şi care nu are nici o activitate precedentă;

~ evenimentul final "n" este evenimentul ce pune in evidentă sfîrşitul sau terminarea executiei proiectului şi care nu are nici o activitate urmatoare.

~ evenimentul precedent "i" este evenimentul aflat la începutul unei activitati oarecare – Aij - şi care reprezintă momentul cînd toate activitatile direct precedente s-au terminat şi poate să începă activitatea Aij;~ evenimentul urmator "j" constituie evenimentul aflat la sfîrşitul unei activitati oarecare – Aij - şi care releva momentul cind toate activitatile premergatoare lui, deci inclusiv activitatea Aij,s-au terminat, asigurînd posibilitatea de incepere pentru toate activitaţile imediat urmatoare.

c) Drumul in graficul retea CPM este 0 succesiune de arce orientate şi noduri, intre nodul initial şi nodul final. Drumul in CPM poate să fie definit ca o succesiune de activitati parcurse in sensul sageţilor,în care evenimentul final al fiecarei activitati coincide cu evenimentul iniţial al activitatii urmatoare.Drumurile retelelor CPM pot sa fie definite astfel :

~drum complet - este considerat drumul parcurs între nodul iniţial şi nodul final al retelei. In graficele retea CPM pot sa existe unul sau mai multe drumuri complete;

~ drum incomplet - este drumul parcurs tntre diferite secvenţe ale retelei. In retelele CPM distingem urmatoarele tipuri de drumuri incomplete: drumul care precede nodul "i" este drumul incomplet care incepe in nodul initial şi care se termina in nodul "i". drumul care succede nodul "i" se considera drumul incomplet care incepe in nodul "i" şi se termina in nodul final "n". drum intermediar este drumul incomplet ce se parcurge între două noduri oarecare ale reţelei,spre exemplu între nodul ”i” şi nodul ’’p’’.

Un drum poate sa fie identificat atat prin nodurile sau evenimentele sale,cît şi prin activitatile componente plasate pe traiectoria sa, dar toate drumurile sunt delimitate prin lungimea lor.

3

d) Lungimea unui drum in graficul retea CPM este egala cu suma duratelor activitalilor ce se situeaza pe drumul considerat.Intr-o retea CPM exista mai multe drumuri complete, cu lungimi diferite:e) Drumul critic in relelele CPM este drumul complet cu lungimea maxima, care pune in evidenta durata totala minima posibila de realizare a intregului proiect.

g) Numerotarea nodurilor unei retele CPM este necesara pentru identificarea evenimentelor ce delimiteaza activitalile proiectului. Fiecare nod este purtatorul unui numar distinct, corespunzator unui sistem de numerotare adoptat: ~ numerotare secventiala continua, cand nodurile se numeroteaza in ordinea crescatoare şi imediat urmatoarea numerelor naturale: 0,1,2.....11,12,13.....23,24........... ~numerotare secventiala cu lacune, cand nodurile se numeroteaza in ordinea crescatoare a numerelor naturalc, dar nu imediat urmatoare: 0,1,5.....11,15,27,.....35,45......... ~numerotare arbitrara, cand nodurile se numeroteaza aleator indiferent de ordine:

0,1,5,3,.....11,9,18,.....27,23, ......

La efectuare lucrării de curs am folosit algoritmul lui Ford pentru determinare drumului critic,cu putine modificări.

Algoritmul lui Ford pentru detrminarea drumului criticPermite determinarea drumului critic care începe cu un vârf iniţial xi până la oricare vârf al grafului G. Dacă prin Lij se va nota ponderea arcului (xi, xj) atunci algoritmul conţine următorii paşi:1. Fiecărui vârf xj al grafului G se va ataşa un număr foarte mare Hj(∞). Vârfului iniţial i

se va ataşa Ho = 0;2. Se vor calcula diferenţele Hj - Hi pentru fiecare arc (xi, xj). Sunt posibile trei cazuri:

a) Hj - Hi < Lij,b) Hj - Hi = Lij,c) Hj - Hi > Lij.

Cazul "c" permite micşorarea distanţei dintre vârful iniţial şi xj din care cauză se va realiza Hj = Hi + Lij.Pasul 2 se va repeta atâta timp cât vor mai exista arce pentru care are loc inegalitatea “c”. La terminare, etichetele Hi vor defini distanţa de la vârful iniţial până la vârful dat xi.

3. Acest pas presupune stabilirea secvenţei de vârfuri care va forma drumul critic. Se va pleca de la vârful final xj spre cel iniţial. Predecesorul lui xj va fi considerat vârful xi

pentru care va avea loc Hj - Hi = Lij. Dacă vor exista câteva arce pentru care are loc această relaţie se va alege la opţiune.

4

n

a[i][j]

k

Schema bloc a progamului:

5

void Matr();

int y=2,x=1;

i=1..n

1

r=0 r=1j=n-1..0

(j!=n-1)&&(a[j][n-1]!=0)

H[n-1]-H[j]==a[j][n-1]

dr[i]=j+1;i++; n=j+1; if(n>0) r=0;j=i-1..0 j>0

return

Start

k!=0

k=1

Prezentarea temei

Meniu

k=1

Matr(); k=2

DC();

Stop

void DC();

H[0]=0;i=1..n H[i]=d;i=0..n-1

j=1..n

(a[i][j]!=0) H[j]-H[i]>a[i][j]HH[j]=H[i]+a[i][j]; dr[j

] ->return

H[i]

H[n-1]

LISTING-UL PROGRAMULUI:

6

i=0..n

dr[0]=n;i=1;

1

// Lucrare de curs.// Tema:METODA DRUMULUI CRITIC// CRITICAL PATH METHOD#include<stdio.h>#include<conio.h>#include<process.h>#include<values.h>#define d 10000;int n,k,j,i,u,a[20][20],H[20],dr[10];//-------------------------------------------------------------------

/* Matricea de incidenta si ponderile*/void Matr() {clrscr();int y=2,x=1;printf("Introduceti numarul de evenimente:");scanf("%d",&n); clrscr(); printf("Introduceti matricea de incidenta si lungimea activitatilor: ");

for(i=0;i<n;i++) {

y=y+1;for(j=0;j<n;j++){ gotoxy(x,y); scanf("%d",&a[i][j]); x=x+3;}x=1;

} }//-------------------------------------------------------------------

/* Algoritmul aflarii drumului critic */void DC() {clrscr();

H[0]=0; for(i=1;i<n;i++)

H[i]=d;for(i=0;i<n-1;i++) for(j=1;j<n;j++) if(a[i][j]!=0) {if(H[j]-H[i]>a[i][j])H[j]=H[i]+a[i][j];}

dr[0]=n;i=1; printf("\nDrumul critic este:%d\n",H[n-1]);//--------------------------------------------------------------------

/* Afisarea succesiunii evenimentelor */ printf("Succesiunea evenimentelor este:\n"); int r=0; while(r==0){ r=1; for(j=n-1;j>=0;j--) if((j!=n-1)&&(a[j][n-1]!=0))

if(H[n-1]-H[j]==a[j][n-1]) {dr[i]=j+1;i++; n=j+1; if(n>0) r=0; }} for(j=i-1;j>=0;j--)

7

{printf("X[%d]",dr[j]); if(j>0)printf("->");} getch(); }

void main() {int k=1;//-------------------------------------------------------------------

/* Prezentarea temei */ clrscr(); printf("\n\n\n\n\t"); textcolor(3); cprintf("Lucrare de curs la disciplina Structuri de Date si Algoritmi."); printf("\r\n\n\t\t\t"); cprintf("Drum critic."); textcolor(15); getch();

textcolor(10);//-------------------------------------------------------------------

/* Meniul principal */while(k!=0) {clrscr(); printf("\n\

\n\ [ MENIU ] \n\ \n\ [1] - Introducerea grafului: ( MatIn ). \n\ \n\ [2] - Aflarea drumului critic. \n\ \n\ [0] - Iesirea. \n\ \n");

scanf("%d",&k);switch(k) {case 1:Matr(); break;case 2:DC(); break;case 0:; } }}

Testarea:

8

9