Cuprins
- Cuprins 1
- A.Probleme de ordonanţare şi coordonare 4
- I. Introducere 4
- II. Probleme de ordonanţare 5
- III. Probleme de coordonare 11
- IV. Metoda PERT completă 16
- V. Metoda drumului critic 19
- VI. Rezumat 27
- B. Probleme de drumuri în reţele 28
- I. Introducere 28
- II. Problema comis-voiajorului 29
- III. Procedeul lui Little şi colaboratorii 30
- IV. Algoritmul 31
- V. Drumuri minime în reţele 39
- V.A. O metodă grafică 39
- V.B. O metodă matricială 42
- VI. Rezumat 46
- C.Aplicaţii 47
- I. Introducere 47
- II. Reprezentarea arborilor binari în calculator 48
- III. Parcurgerea arborilor binari 50
- 3.1.Parcurgerea în preordine 50
- 3.1.1. Iterativ 50
- 3.1.2. Recursiv 51
- 3.2.Parcurgerea în inordine 51
- 3.2.1.Iterativ 51
- 3.2.2.Recursiv 52
- 3.3. Parcurgerea în postordine 52
- 3.3.1.Iterativ 52
- 3.3.2.Recursiv 53
- IV. Traversarea grafurilor în adâncime ( deph-first search ) 54
- 4.1. Algoritm 54
- 4.2. Exemplu de implementare a algoritmului ( cod sursă C++ ) 55
- V. Traversarea grafurilor prin cuprindere 56
- 5.1. Algoritm 56
- 5.2. Exemplu de implementare a algoritmului ( cod sursă C++ ) 57
- VI. Aplicaţii ale traversării grafurilor 58
- 6.1. Determinarea arborelui de acoperire 58
- 6.2. Determinarea componentelor conexe 59
- 6.3. Puncte de articulaţie şi componente biconexe 59
- 6.3.1.Algoritm 60
- 6.3.2. Exemplu de implementare a algoritmului 60
- 6.4. Sortare topologică 62
- 6.5.Algoritmi pentru găsirea arborelui de valoare optimă 62
- 6.5.1. Algoritmul lui KrusKal 62
- 6.5.2. Algoritmul lui Solin 63
- 6.5.3. O varianta a algoritmului lui Kruskal 63
- Bibliografie 64
Extras din proiect
A. PROBLEME DE ORDONANŢARE ŞI COORDONARE
I. INTRODUCERE
Se consideră două tipuri de probleme relative la ordinea în care trebuie efectuate o serie de activităţi. În primul caz, referitor la probleme de ordonanţare, obiectivul constă în a găsi ordinea în care trebuie efectuate activitaţi independente ce folosesc anumite servicii comune în aşa fel încât să se optimizeze o anumită măsură a execuţiei întregii mulţimi.
În acest capitol se discută două tipuri de probleme. Primul tip priveşte stabilirea ordinii într-un fir de aşteptare, ordine care în problemele de teoria aşteptării se consideră ca data sau fixdata. Alegerea unei ordini potrivite in care să fie serviţi clienţii care aşteaptă se numeşte ordonanţare.
În textul original: sequencing problems(probleme de stabilire a succesiunii unor operaţii). Denumirea probleme de ordonanţare este larg răspândită în literatura română de specialitate.
Al doilea tip de probleme se referă la proiecte sau lucrări care constau din activităţi ce trebuie executate într-o ordine dată. Aceste probleme cer să se determine cât de mare trebuie să fie efortul depus în executarea fiecărei activităţi şi când trebuie planificată fiecare activitate, astfel încât să se optimizeze o anumită măsură a executării proiectului în ansamblu. Aceste probleme pot fi gândite ca probleme de coordonare, dar sunt adesea denumite la fel ca metodele aplicate pentru rezolvarea lor: PERT şi drum critic.
II. PROBLEME DE ORDONANŢARE
Problemele de ordonanţarepot fi reprezentate printr-o matrice, astfel:
Tabelul nr. 1
Clienţi
(sau lucrări) Servicii Data la care
poate începe Data la
care
trebuie să termine
Activităţi prin care această
lucrare trebuie să
treacă în ordinea
cerută
Timp de
execuţie
Figura nr. 1.1
Se dă o mulţime formată din doi sau mai mulţi clienţi care trebuie serviţi sau din două sau mai multe lucrări ce trebuie executate, precum şi o muţime de unul sau mai multe servicii(activităţi) care trebuie efectuate pentru clienţi(lucrări). Trebuie să ştim când poate să înceapă fiecare lucrare şi până când trebuie termintă. De asemenea, trebuie să ştim ce activităţi sunt necesare pentru efecturea fiecărei lucrări, în ce ordine anume şi cât va dura fiecare operaţie.
Cel mai obişnuit context pentru asemenea probleme este un “magazin de lucrări”, adică un centru de producţie care prelucrează multe produse diferite, folosind o varietate de maşini. Într-un astfel de context, o problemă de ordonanţare este numită uneori problemă de planificare; nu se foloseşte acest termen aici pentru a evita o confuzie cu probleme de planificare din teoria aşteptării.
Trebuie subliniat faptul că problemele de ordonanţare pot apărea chiar dacă avem o singură activitate. De exemplu, dacă fiecare din lucrările ce trebuie executate are o dată la care trebuie terminată şi un “cost al întârzierii”, minimizarea costului total al întârzierii poate să nu fie uşor de obţinut. Astfel de probleme sunt destul de frecvente; un exemplu îl constituie stabilirea ordinii de acces a unor probleme la un calculator sau a unor urgenţe de medic.
Problemele de ordonanţare pot fi complicate, printr-un număr de condiţii, dintre care cele mai importante sunt:
1. Suprapuneri. Dacă o lucrare constă din fabricarea unui număr de produse similare(un lot), primul produs care rezultă dintr-o operaţie poate trece la operaţia următoare, înainte ca anumite produse ale lotului să fi intrat în prima operaţie.
2. Tipul de transport. Transportul produselor de la un loc de prelucrare la altul poate lua un timp apreciabil. Locurile unde se execută diferite operaţii se pot găsi chiar în fabrici diferite.
3. Refacerea lucrării. Dacă una din operaţii constă dintr-un control, produsele defecte pot fi înapoiate la o operaţie anterioară în vederea reluării acesteia, provocând fie o întârziere a produselor acceptabile, fie o separare a lucrării în două loturi. Dacă produsele defecte nu pot fi refăcute, poate apărea necesitatea de a începe o lucrare nouă.
4. Accelerări. Din cauza presiunilor din partea unui client sau a altcuiva, o lucrare poate fi scoasă din şir sau accelerată, adică i se poate schimba
Preview document
Conținut arhivă zip
- Ordonontare si Coordonare.doc