Problema de ordonantare - Metoda incarcarii in aval imbunatatita

Lucrarea nr.

Problema de ordonantare.

Metoda incarcarii in aval imbunatatita

Scopul lucrarii

Lucrarea are drept scop insusirea cunostintelor legate de modelarea si rezolvarea problemelor de ordonantare a n lucrari la mai multe utilaje, cand ordinea de prelucrare difera de la o lucrare la alta.si se impun termenele de predare a lucrarilor. Se va folosi metoda incarcarii in aval imbunatatita, utilizand un exemplu practic.

Lucrarea parcurge urmatoarele etape:

1. Se va formula problema de rezolvat
2. Se va aplica metoda incarcarii in aval imbunatatita.
3. Se va interpreta rezultatele
4. Se vor face modificari asupra modelului si se vor studia solutile obtinute

Formularea problemei de ordonantare.

Se considera executarea a 4 lucrari la 5 masini (Mi, i=1,5), ordinea de prelucrare fiind diferita pentru fiecare lucrare Se considera di,j timpul necesar executarii lucraii i la masina j. Se cunoasc momentele de eliberare a fiecaei masini.

Scopul problemei este de a determina ordinea optima de executare a lucrailor astfel incat durata totala de exutre a lucrarilor sa fie minima, adica intervalul de timp intre momentul lansarii in executie a primei lucrari la prima masina si momentul trminartii ultimei lucrari la ultima masina.   

Problema se poate reprezenta ca in tabelul nr.1 unde sunt prezentate lucraile si duratele de executie la fiecare masina.

Tabelul nr. 1 Formularea problemei sub forma de tabel.

Aplicarea metodei incarcarii in aval

Etapele metodei

Metoda consta in urmatoarele etape :

Metoda considera ca prioritate termenul minim de eliberare a utilajului la prima operatie. Se aseaza masinile in ordinea crescatoare a timpilor de eliberare.

M2(8), M3(16), M1(16), M5(24), M4(32)

Daca sunt mai multe masini cu acelas timp se poate alege masina:

Cu timpul total de prelucrare cel mai mare a tuturor lucrarilor la aceasi masina

Costul de asteptare a masinii cel mai mare.

Masinile M3 si M1 au acelas moment de eliberare (16) dar masina M3 are timpul de prelucrare cel mai mare (55)

Se alege masina cu timpul cel mai mic si se repartizeaza lucrarea cu prima operatie la masina aleasa. Se alege masina M2 si se repartizeaza lucrarea L1.

Se calculeaza momentul eliberarii masinii alese pentru lucrarea repartizata astfel : suma dintre momentul eliberarii masini M2 inainte de repartizarea lucrarii L1 si durata de prelucrare a lucraii L1 la masina aleasa (M2)

T12=8+d12=8+5=13

Se alege urmatorea masina in ordinea eliberarii, adica M3.

La masina aleasa se repartizeaza lucrarea lucrarea cu prima operatie la masina aleasa. Sunt doua lucrari L3 (d33=25) si L4(d43)=5.

Daca sunt mai multe lucrari, se calculeaza rezerva de timp R ca diferenta intre timpul de prerdare, timpul total ramas si momentul eliberarii.

unde R_k este rezerva de timp pentru lucrarea k, T_i     - timpul de prelucrare a lucrarii i, m_i - numarul operatiei la lucrarea i, j_h - numarul de ordine a masinii care executa operatia de rang h, τ _j,p - termenul de eliberare a masinii j dupa p cicluri de alegere.

Se alege lucrarea pentru care rezerva de timp este cea mai mica.

R3=160-100-16=44

R4=160-55-16=89

Lucrarea cu rezerva cea mai mica (min(R3, R4)) este L3.

Se repete etapele de alegere si repartizare pana cand toate lucrarile au fost repartizate.

Dupa repartizarea tuturor lucrarilor, sa obtinut timpii de eliberare a tuturor masinilor si momentul de terminare a tuturor lucrarilor.

Se reia algoritmul de la inceput, ordonarea masinilor in ordine descrescatoare a timpilor de eliberale, . . . .

Se aplica metoda utilizand datele de intrare si algoritmul prezentat. Se pun in evidenta rezultatele.