Ordonantarea fabricatiei - modele matematice ale ordonantarii

SPECIALIZAREA:MANAGEMENT,ANII II+IV

CURS NR.9

ORDONANTAREA FABRICATIEI

1 FORMULAREA PROBLEMEI GNERALE A ORDONANTARII FABRICATIEI

2 MODELE MATEMATICE ALE ORDONANTARII

ORDONANTAREA FABRICATIEI

FORMULAREA PROBLEMEI GENERALE A ORDONANTARII

FABRICATIEI

In domeniul imbunatatirii activitatii de programare a productiei, un loc central il ocupa ordonantarea fabricatiei - important domeniu al cercetarii operationale.

Ordonantarea este o problema a programarii productiei si reprezinta esalonarea in timp si spatiu a executarii operatiilor. Conceptul de ordonantare a fabricatiei desemneaza ordinea de repartizare, fabricare a n sarcini de productie pe m masini (executanti) in baza unor criterii riguros stabilite.

Indiferent de tipul de productie , ordonantarea prezinta dificultati atat in atingerea obiectivului ( incarcarea completa a locurilor de munca si minimizarea duratei ciclului de fabricatie ), cat si in dirijarea resurselor necesare productiei.

In conditiile organizarii productiei pe loturi si in flux, pe linii tehnologice polivalente (multiobiect), ordinea de lansare a produselor in fabricatie nu poate fi indiferenta din punct de vedere economic, deoarece cheltuielile de trecere de la produsul P_i la produsul P_j pot fi diferite in cazul cand trecerea s-ar face de la produsul P_j la produsul P_i. De asemenea, intervalul de asteptare intre operatii si, implicit, durata totala de executie a produselor depind de succesiunea adoptata.

Formularile posibile pentru criteriul de optimizare (indicele de performanta) sunt:

minimizarea ciclului de productie (durata totala a operatiilor);

- minimizarea timpului de stagnare a utilajelor;

minimizarea productiei neterminate;

- minimizarea costurilor specifice;

- minimizarea intarzierilor fata de termenele finale de predare a produselor.

Combinand aceste formulari, se poate obtine un numar mare de enunturi ale problemei de ordonantare, destul de diferite intre ele. Toate aceste enunturi, deoarece includ multimi finite, sunt de natura combinatorie. In esenta, este vorba de a construi o functie multivoca, depinzand de timp, intre o multime de produse si o multime de resurse; modelul este atunci secvential, iar necunoscutele sunt o multime finita de permutari. Sunt, insa, cazuri in care restrictiile micsoreaza considerabil numarul permutarilor, ajungandu-se adesea la o singura sau chiar la nici o solutie realizabila (!).

Exista si formulari ale problemei ordonantarii de natura probabilista, scrise atat pentru sistemele discrete de productie cat si pentru cele continue.

Problema ordonantarii mai poate fi enuntata sub forma statica (in cazurile in care toate datele sunt cunoscute dinainte) sau sub forma dinamica (pentru cazurile in care datele privind produsele, resursele si perturbatiile se pot modifica in cursul productiei). In cazul problemelor de ordonantare dinamice se impune o metodologie de solutionare in timp real.

In sfarsit, in formularea problemei ordonantarii este esentiala alegerea corecta a criteriului de optimizare (indicele de performanta), deoarece importanta diferitelor criterii - din punctele de vedere economic si al productiei - nu este aceeasi. Aplicatiile realizate pana in prezent arata ca eficienta obtinuta prin scurtarea ciclului mediu de fabricare a reperelor este mult mai mica decat eficienta obtinuta prin reducerea stagnarii utilajelor. Chiar si minimizarea ciclurilor de productie sau a stagnarii utilajelor se considera a fi masuri de importanta secundara fata de alimentarea ritmica cu piese si subansamble a sectiilor de montaj. Un studiu comparativ, din punctul de vedere al eficientei unor criterii de optimalitate in ordonantarea productiei, realizat prin simulari, a condus la concluzia ca o solutie optima din punctul de vedere economic este incarcarea uniforma a utilajelor (nu maxima), fara goluri si fara puncte de strangulare.

Abordarile enunturilor de mai sus se inscriu, in cea mai mare parte, in cadrul cercetarilor operationale.

O abordare posibila consta in a considera ordonantarea de natura statica si de a o trata ca pe o problema de optim. In acest caz, in cadrul modelului, restrictiile sunt presupuse inviolabile, iar criteriile fixeaza obiectivele de atins. In fapt este vorba de a cauta un extremum pentru un criteriu unic global, care poate rezulta dintr-o agregare cardinala a criteriilor locale.

O alta abordare consta in a cauta numai solutiile realizabile - adica cele care satisfac cel putin restrictiile - fara preocuparea pentru optim. O astfel de abordare, in cazul ordonantarii in sistemele ample (cu numeroase proiecte, activitati, resurse si restrictii), este bine servita de procedurile euristice care au aici un domeniu larg de aplicatie.

1.1 Varianta intai de formulare a problemei ordonantarii

In formularea problemei ordonantarii trebuie sa se tina seama de urmatoarele aspecte:

1) atelierul de productie cuprinde grupe de masini , fiecare grupa fiind formata din una sau mai multe masini , care isi iau lucrarile din firul de asteptare al grupei;

2) daca o masina ( mM ) devine libera, i se atribuie lucrarea prioritara din firul de asteptare al grupei din care face parte;

3) fiecare utilaj are un anumit interval de timp dupa care poate fi programat la prelucrarea noilor loturi; numim acest moment termen de eliberare ;

4) utilajele au prevazute reparatii planificate, care se executa dupa terminarea

unui lot, si reparatii accidentale, care prelungesc prelucrarea lotului;

5) loturile ce urmeaza a fi prelucrate l_h ( hL ) sunt lansate in fabricatie la diferite momente de timp si necesita una sau mai multe operatii de prelucrare .Ordinea operatiilor de prelucrare este cunoscuta;

6) fiecare lot are sau nu un moment planificat de predare, existand totodata un timp de transport al lotului de la o operatie la alta ();

7) un lot este format dintr-un numar diferit de piese ( );

8) o operatie pe o anumita masina trebuie sa fie executata la toate reperele din lot inainte de a incepe prelucrarea altui lot pe masina respectiva;

9) pentru fiecare lot si operatie se cunosc timpii necesari pregatirii masinii si executarii operatiei pe repere;

10) daca doua operatii tehnologice succesive sunt planificate pe aceeasi grupa de masini, acestea se executa succesiv pe aceeasi masina fara ca lotul sa mai reintre in firul de asteptare;

11) unele operatii se pot executa pe mai multe tipuri de utilaje.

Matematic, aceste conditii pot fi reformulate astfel :

daca O = este multimea operatiilor ce se ordonanteaza, procesul tehnologic se defineste ca aplicatia P:0D(0), prin care se indica ordinea de precedenta a operatiilor ;

structura unui proces tehnologic se poate reprezenta printr-un graf orientat ,in care multimea varfurilor O = semnifica operatiile procesului tehnologic iar arcele ordinea operatiilor conform aplicatiei P asociata procesului tehnologic. Graful poate sa contina si circuite;

fiecarei operatii o_j ( j = 1,) i se asocieaza un numar intreg nenegativ ( t_oj ), numit durata operatiei si care reprezinta intervalul de timp in care se efectueaza operatia, si un alt numar intreg nenegativ ( t_pj ), numit durata de pregatire a operatiei si care reprezinta intervalul de timp necesar pregatirii utilajului ce executa operatia o_j;

notam cu U = ( U₁,U₂,.,U_i) vectorul resurselor ( utilajelor ) disponibile , unde U_i este un numar intreg pozitiv numit disponibilul resursei i. Fiecare resursa (utilaj ) are un fond de timp disponibil; cand durata de folosire nu este in general limitata, momentul cand ele sunt disponibile depinde de termenul de eliberare ;

notam cu r_j = (r_j1,r_j2,.r_ji ) vectorul resurselor necesare pentru efectuarea operatiei o_j in fiecare unitate de timp, unde r_ji este un numar intreg nenegativ numit intensitatea resursei i relativa la operatia o_j.

Problema generala a ordonantarii se enunta astfel :

Fiind date :

a) un numar de loturi de produse (l_h), fiecare alcatuit dintr-un numar de piese ( n_oh );

b) procesul tehnologic pentru fiecare lot alcatuit dintr-un numar de operatii o_j, ordinea lor fiind cunoscuta;

c) duratele operatiilor, timpul de pregatire si timpul de transport intre doua operatii t_trj1j2;

d) grupele de utilaje disponibile U_i, numarul de utilaje din fiecare grupa si termenele de eliberare .

Se cere : sa se stabileasca acea succesiune de prelucrare a loturilor pe fiecare masina care asigura cea mai buna incarcare a utilajelor ( timpii de neutilizare intre prelucrarea a doua loturi trebuind sa fie minimi ).

2 MODELE MATEMATICE ALE ORDONANTARII

Stabilirea secventelor de prelucrare a n produse pe unul, doua sau trei utilaje

2.1.1 Solutionarea problemei de ordonantare a n repere pe un utilaj

In cazul in care un utilaj complex care necesita o durata mare pentru reglaj in conditiile trecerii de la executarea unui reper la altul, utilizarea eficienta a acestuia impune stabilirea unei succesiuni optime care sa duca la minimizarea timpului total afectat activitatilor de reglare a acestuia. Considerand duratele de reglare a utilajului in conditiile trecerii de la fabricarea reperului i la fabricarea reperului j, ca fiind:

(1)

in care t_ij reprezinta timpul de reglare a utilajului necesar trecerii de la fabricarea reperului (i) la fabricarea reperului (j).

Pentru i =j, solutionarea problemei se face prin aplicarea unei reguli elaborate de W.J.Gavett si intitulata Next Best (NB), ceea ce ar insemna "urmatorul cel mai bun", regula care presupune trei variante.

a) Next Best cu origine fixa

La alcatuirea matricei se considera ca exista intotdeauna cel putin doua produse de fabricat si ca executia primului produs este deja aleasa. Dat fiind primul reper care se executa, se va alege urmatorul reper acela care corespunde celui mai mic timp de reglare a utilajului, dupa executarea reperului anterior.

Deci, daca i este reperul care se executa primul, reperul care urmeaza a fi executat va fi acela care stisface relatia:

Se continua astfel procedeul pana la stabilirea succesiunii de lansare a penultimului reper, ultimul rezultand in mod evident.

b) Next Best cu origine variabila

Aceasta varianta porneste de la analiza unui numar de n-1 succesiuni in loc de una singura. In cele n-1 succesiuni se adopta ca al doilea produs oricare din cele n produse, cu exceptia produsului P₁, urmarindu-se procedura de mai sus. Pentru cele n-1 variante se stabilesc sumele timpilor de reglare, suma minima indicand varianta optima de succesiune a fabricatiei.

c) Next Best cu reducerea coloanelor

Varianta presupune stabilirea in cadrul matricei timpilor de reglare a timpului minim de pe fiecare coloana si scaderea acestuia din toate elementele coloanei respective. Se va obtine astfel cel putin cate un zero pe fiecare coloana, care va indica reperul ce urmeaza a fi executat, dupa reperul deja lansat de pe linia care contine zeroul respectiv.

In cazul in care exista pe o linie mai multe zerouri, se vor stabili mai multe variante, dintre care se va alege aceea pentru care timpul total de reglare a utilajului este minim.

Motoda Next Best prezinta avantajul rezolvarii unei probleme complexe de ordonantare cu un volum de munca redus, dar nu ofera posibilitatea de a gasi cu certitudine o solutie optima decat din intamplare.

In afara regulii Next Best cu variantele sale, se mai pot aplica - in functie de situatiile intalnite - si alti algoritmi sau metode, dupa cum se prezinta in continuare.

In cazul in care intr-o intreprindere exista doua locuri de munca, considerate locuri inguste, conditionand utilizarea capacitatii celorlate verigi de productie, se va urmari optimizarea succesiunii executarii programului operativ de productie pe aceste utilaje, cu scopul reducerii timpului de executare a reperelor.

Cunoscand structura programului operativ si consumul de manopera la cele doua utilaje, se calculeaza durata executarii pentru fiecare reper, a intregului program operativ sau a unui lot de fabricatie, cu ajutorul relatiei:

unde:

T_ij reprezinta durata de executare a cantitatii programate sau a lotului de produse i la utilajul j;

t_ij - durata executarii reperului i la utilajul(operatia) j;

N_uj - numarul utilajelor de aceeasi tip j;

K_ij - coeficientul de indeplinire a normelor la utilajul(operatia) j;

T_{disp uj} - timpul disponibil al utilajului j.

2.1.2 Solutionarea problemei de ordonantare a n repere pe doua utilaje In acest caz solutionarea se face cu ajutorul algoritmului Johnson, care pentru domeniul sau de aplicare ofera solutia optima.

Stiind ca toate cele n repere parcurg utilajele in ordinea U₁ si U_2, se cere sa se stabileasca succesiunea optima de lansare a reperelor in fabricatie astfel incat timpul total parcurs intre inceperea prelucrarii primului reper si terminarea prelucrarii ultimului reper sa fie minim.

Algoritmul lui Johnson presupune parcurgerea urmatoarelor etape:

. Se determina cel mai mic timp de prelucrare al reperelor pe cele doua utilaje. Daca acest timp se refera la utilajul U₁ reperul corespunzator se programeaza primul, iar daca timpul minim se refera la utilajul U₂ reperul se programeaza ultimul. In situatia in care exista doi sau mai multi timpi minimi egali la utilajul U₁, atunci se programeaza reperul cu cel mai mic timp la utilajul U₂ si invers.

Dupa ce reperul a fost programat, se sterge coloana respectiva si se reia algoritmul. Calculul se opreste atunci cand penultimul reper a fost lansat, lansarea ultimului reper fiind evidenta.

2.1.3 Solutionarea problemei de ordonantare a n repere pe trei utilaje

Algoritmul Johnson este aplicabil si pentru ordonantarea a n lucrari (repere) pe trei utilaje. Sa notam cu t_ij timpul de prelucrare a reperului r_i pe utilajul U_j ( j=1,2,3 ). S-a demonstrat ca daca se indeplineste una din conditiile:

max t_i2 ≤ min t_i1

sau  (4)

max t_i2 ≤ min t_i3

adica daca cel mai mare timp de prelucrare pentru o lucrare la utilajul U₂ este mai mic sau egal cu cel mai mic timp de prelucrare la primul utilaj si la cel de-al treilea, numarul liniilor matricei se reduce de la trei la doua, prin urmatoarea substitutie:

t'_i1= t_i1 + t_i2  (5)

t'_i2 = t_i2 + t_i3

Pentru determinarea succesiunii optime a lucrarilor pe cele trei utilaje U₁, U₂, U₃, se va aplica in continuare algoritmul Johnson pentru cele n repere pe doua utilaje, deduse cu substitutia (17).

Algoritmul Johnson poate fi, de asemenea, utilizat in cadrul unei metode euristice care in final ofera o solutie buna pentru ordonantarea a n repere pe m utilaje, fara insa ca respectiva solutie sa detina in mod sigur caracter de optimalitate.

Comform acestei metode euristice, pentru ordonantarea a n repere pe m utilaje se vor parcurge urmatoarele etape:

1) Se noteaza cu d_ij durata efectuarii reperului i(i=1,2,.,n) la utilajul j(j=1,2,.,m).

2) Se genereaza matricele A_ik si B_ik astfel:

si (6)

pentru i=1,2,.,n si k=1,2,.,m-1.

3) Cu ajutorul algoritmului Johnson pentru n repere pe doua utilaje, considerand timpul A_ik pentru primul utilaj si B_ik pentru al doilea utilaj, se determina succesiunea optima S_k a reperelor.

Aceasta operatie se executa pentru toate valorile lui i si k. Vor rezulta deci (m-1) succesiuni S_k pentru subproblemele generate.

4) Se calculeaza durata totala T_k necesara realizarii tuturor reperelor in succesiunea S_k, pentru toate valorile lui k.

5) Se adopta pentru aplicare acea succesiune S_k pentru care se obtine cea mai mica durata totala T_k.

Succesiunea adoptata pentru aplicare va fi cu atat mai apropiata de succesiunea optima cu cat numarul n de repere va fi mai mare.

Stabilirea secventelor de prelucrare a n repere care au aceeasi succesiune a executarii operatiilor, pentru care nu se prevad termene de predare, pe m utilaje a caror termene de eliberare initiala se cunosc

Fie reperele r₁,r₂,.,r_n, avand costurile c₁,c₂,.,c_n, care urmeaza a fi prelucrate pe utilajele U₁,U₂,.,U_m .

Daca notam cu | t_ij | matricea duratelor de executare a reperelor r_i pe utilajele U_j, atunci aceste durate satisfac inegalitatile:

t_ij ≥ 0, i=1,2,.,n; j=1,2,.,m  (7)

Nu se dau termene impuse de predare a reperelor, insa se cunosc termenele de eliberare initiala a utilajelor _j0. Se considera astfel ca utilajul U_j a fost ocupat in vederea terminarii reperelor din perioada precedenta pana la termenul de eliberare initiala _j0. Acest termen este cunoscut din situatia perioadei precedente. Numai incepand de la termenul de eliberare initiala _j0, utilajul U_j poate incepe sa actioneze in vederea prelucrarii reperelor din perioada actuala. Obiectivul minimizarii sumei timpilor de asteptare a utilajelor cere ca inceperea efectiva T_ij a prelucrarii unui reper r_i pe utilajul U_j sa coincida cu _j0

Reperele parcurg utilajele in acelasi sens, adica fiecare reper respecta aceeasi tehnologie. Se cere sa se determine succesiunea de executie a reperelor care minimizeaza timpul de asteptare a utilajelor si/sau al reperelor.

Problema prezentata are un caracter combinatoriu, iar pentru rezolvare s-ar putea explora in mod exhaustiv intreaga multime de solutii si alege solutia (sau solutiile) care satisface criteriul de optim. Numarul solutiilor posibile este insa n!, astfel ca se ajunge usor la un numar foarte mare de variante, si din aceasta cauza aceste metode nu pot fi aplicate in acest caz.

Solutionarea problemei se poate realiza utilizand un algoritm euristic, denumit "algoritmul programarii secventiale"; acesta ofera o solutie care, verificata practic, da rezultate satisfacatoare.

Pasii algoritmului sunt urmatorii:

Pasul 1. Se calculeaza termenele de incepere a prelucrarii (T_ij) pe fiecare utilaj U_j, in ordinea crescatoare a idicelui utilajului pentru reperul r_i, astfel:

- pentru utilajul U₁

T_i1 = (8)

- pentru un utilaj U_j

T_ij = max (T_{i,j -1}+ t_i,j-1; _j0 j=2,3,.,m (9)

Pasul 2. Se calculeaza durata de asteptare a fiecarui utilaj U_j pentru reperele r_i, astfel:

= T_ij- _j0 pentru T_ij> _j0

si

pentru T_ij (11)

Pasul 3. Se calculeaza suma tuturor duratelor de asteptare a utilajelor, considerand ca a fost lansat in fabricatie reperul r_i :

Pasul 4. Se reiau pasii 1,2 si 3 pentru toate repere r₁,r₂,.,r_n, obtinandu-se astfel sumele duratelor de asteptare . Se alege pentru a fi lansat primul in fabricatie reperul r_h, caruia ii corespunde suma timpilor de asteptare minima: min(

In cazul in care exista mai multe repere a caror suma totala a duratelor de asteptare este minima, se calculeaza durata de asteptare a reperelor() dupa relatia:

= _j0 - (T_{i,j -1}+ t_i,j-1), pentru _j0 > T_{i,j -1}+ t_i,j-1

si

= 0, pentru _j0 ≤ T_{i,j -1}+ t_i,j-1

Se calculeaza suma duratelor de asteptare a reperelor pentru toate utilajele, astfel:

(12)

Se va lansa dintre reperele cu aceeasi suma a duratelor de asteptare a utilajelor minima, acela pentru care se satisface relatia:

unde c_i reprezinta costul asteptarii reperelor pe unitatea de timp.

Daca si in acest caz se obtin mai multe solutii, se va alege reperul pentru lansare in fabricatie acela care are costul cel mai mare.

Pasul Se recalculeaza noile termene de eliberare a utilajelor dupa fabricarea primului reper lansat, dupa relatia:

_j1 = T_hj + t_hj (14)

Spre deosebire de termenul de eliberare initiala _j0, care reprezinta un termen de eliberare de reperele din perioada precedenta , termenul de eliberare _j1 reprezinta un termen de eliberare dupa ce a fost executat un lot de repere in cadrul perioadei actuale. Evident, dupa prelucrarea celui de-al doilea lot de repere, va rezulta un nou termen de eliberare _j2 etc.

Pasul 6. Se reia algoritmul pentru reperele ramase dupa eliminarea din matricea duratelor de prelucrare | t_ij | a coloanei t_hj, luand in considerare noile termene de eliberare a utilajelor _j1

Algoritmul se incheie odata cu stabilirea penultimului reper care urmeaza a fi fabricat, lansarea ultimului reper fiind evidenta.

2.4 Alte metode utilizate pentru determinarea unei permutari avantajoase de executie a produselor

2.4.1 Metoda indicilor de tendinta (Algoritmul lui D.S. Palmer)

Aceasta metoda serveste la determinarea succesiunii optime de prelucrare a "n" produse pe "m" masini, astfel incat sa se obtina o durata minima a ciclului de prelucrare al celor "n" produse. Pentru a putea fi aplicat , algoritmul impune conditia ca toate produsele sa se prelucreze la cele "m" masini in aceeasi succesiune (ordine).

Pentru a stabili succesiunea optima se determina un indice numeric de tendinta pentru fiecare produs a carui relatie este urmatoarea:

  (35)

in care:

- este indicele numeric de tendinta pentru produsul sau lotul de produse "i";

- timpul unitar de prelucrare a produsului "i" la utilajul sau linia tehnologica

"m" (m=1,2,3.).

Calculul termenilor cu semn negativ sau pozitiv se face pana in momentul cand se obtine zero la numarator sau se produce o schimbare de semn, in sensul ca diferentele (m-1), (m-3) s.a.m.d. trebuie sa fie totdeauna pozitive.

Pe baza acestui algoritm produsele se programeaza in ordinea descrescatoare a indicelui de tendinta (valori pozitive, zero, valori descrescatoare negative).

In scopul stabilirii duratei ciclului tehnologic de fabricatie aferent celor

produse se construieste graficul Gantt, iar pentru a demonstra validitatea algoritmului se considera una sau mai multe succesiuni oarecare pentru care se vor determina duratele de prelucarare. Prin comparatie cu succesiunea optima calculata se va confirma sau nu daca aceasta succesiune este cu adevarat cea optima.

Autorul acestei metode a demonstrat ca succesiunea obtinuta se apropie, in majoritatea cazurilor, de solutia optima. Se apreciaza ca desi numai intamplator conduce la stabilirea succesiunii optime, metoda indicilor de tendinta ofera avantajul unui volum relativ mic de calcule si, implicit rezolvarea rapida a unor probleme de mari dimensiuni.

Exemplul 1 Intr-un atelier se prelucreaza patru produse (sau loturi de produse) la cinci masini. Timpii unitari de prelucrare sunt prezentati in tabelul 1.

Tabelul 1

Se cere sa se stabileasca succesiunea optima de prelucrare astfel incat durata

ciclului de fabricatie sa fie minima.

Valorile indicilor de tendinta:

Succesiunea optima de prelucrare va fi :

Graficul Gantt se prezinta in figura 1.1.

Asa cum rezulta din grafic, durata ciclului de prelucrare este egala cu 23 ore . Pentru a verifica daca succesiunea obtinuta este optima se pot analiza si alte succesiuni, de exemplu : sau s.a.m.d.

	Operatii

M