Modulul 22.ppt

MODULUL 22

PROGRAMAREA PRODUCIEI DE SERIE MARE I MAS III

Profesor:

dr. ing. Bungau Constantin

*

Ingineria sistemelor de productie


22.1. Rezolvarea problemei cu ajutorul programrii matematice [1], [3]

Deoarece exist un numr foarte mare de moduri n care J faze pot fi grupate n N posturi de lucru, echilibrarea liniilor n flux este evident o problem de combinatoric, fapt care ne indic de la bun nceput c rezolvarea va fi foarte dificil.

Literatura de specialitate prezint o larg varietate de modele i ci de optimizare pentru problema echilibrrii liniilor; amintim: modelele de programare binar, cele de programare dinamic, modelarea sub forma unei probleme de curgeri n reele, metode de cutare n arborescene, metode euristice.

Pentru a intui natura problemei, dimensiunile ei mari i dificultile legate de rezolvarea ei se va prezenta aici modelarea problemei de echilibrare sub forma unui program matematic cu variabile binare (variabile 0-1) [1], [3]. Se face referire chiar la exemplul introdus mai sus i vom impune un ritm r = 12. Problema de echilibrare care se cere rezolvat este: dat fiind procesul tehnologic din figura 22.1 i un ritm de 12 s se grupeze fazele procesului n numrul cel mai mic posibil de posturi de lucru.


*


Se folosesc urmtoarele variabile binare:

Xji = 1 dac faza j se execit la postul i;

0 dac faza j nu se execut la postul i;

i =1 dac linia conine postul cu numrul i;

0 dac linia nu conine postul cu numrul i.

Pe baza relaiei anterioare se calculeaz c numrul minim necesar de posturi este Nmin = 5. nc nu se tie dac, n condiiile exemplului dat, se poate obine o linie cu 5 posturi i ritm egal cu 12. Este uor ns de grupat cele 12 faze n 6 posturi, aa nct n formularea noastr nu este necesar s considerm mai multe; deci j=1,2,..,6.

Se scrie acum modelul de programare cu variabile binare mai nti n form general, dup care se dau explicaii i se fac particularizri pentru exemplul dat.


*


(22.1)

j = 1,...,J (22.2)

i = 1,...L (22.3)

k{setului de indici ai predecesorilor imediai fazei j(9)


*


i = 1,...L (22.4)

j = 1,...,J; i = 1,...L (22.5)

i = 1,...L (22.6)

ntruct variabilele pot fi doar zero sau 1, funcia obiectului va fi egal cu numrul variabilelor care au valoarea 1, ceea ce reprezint chiar numrul posturilor de pe linie; se cere ca acest numr s fie minimizat. Limita superioar L a sumei din relaia (22.6) arat cunoaterea de ctre noi a faptului c n configuraia optim final linia nu va avea mai mult de L posturi de lucru.

Pentru exemplul nostru spuneam mai sus c putem gsi cu uurin o grupare n 6 posturi de lucru, configuraie fa de care soluia optim ar putea s aib eventual mai puine posturi, n nici un caz mai multe; ca urmare funcia obiectiv este:

Z = 1 + 2 + 3 + 4 + 5 + 6. (22.7)


*


Relaiile (22.7) arat c fiecare faz trebuie inclus ntr-unul i numai ntr-un singur post de lucru. Astfel, referindu-ne la faza F1 se poate scrie:

X11 + X12 + X13 + X14 + X15 + X16 = 1

Cum oricare Xji poate fi numai zero sau 1 rezult din condiia scris c doar un singur X din cei ase va lua valoarea 1, i anume acela corespunztor postului n care se cuprinde faza F1.

Membrul stng al relaiei (22.8) nsumeaz duratele tuturor fazelor grupate n postul i; ntr-adevr, dac un anumit Xji este zero durata respectivei faze j este exclus de la nsumare.

Relaia (22.8) spune c nici un post de lucru nu poate cuprinde faze a cror durate nsumate s depeasc ritmul r al liniei. n mod particular pentru postul 1 vom scrie:

6X11 + 9X21 + 4X31 + 5X41 + 4X51 + 2X61 + 3X71 + 7X81 + 3X91 + 1X10,1 + 10X11,1 + 1X12,1 12.


*


Condiiile (22.9) modeleaz relaiile de preceden succesiune dintre faze. S lum ca exemplu, la ntmplare, faza j = 7, identificm setul indicilor predecesorilor ei imediai ca fiind {3,4}.

Dac faza 7 se execut, s zicem, la postul 1, atunci predecesorii F3 i F4 trebuie n mod necesar s fac parte tot din postul ceea ce este echivalent cu a impune X31=1 i X41=1. Dac faza 7 nu este inclus n postul 1, atunci nu mai este nevoie s constrngem pe X31 i X41. Acest lucru se poate exprima concis astfel:

X31 X71 i X41 X71

Dac faza 7 se execut, ns, la postul 2, atunci predecesorii F3 i F4 trebuie s fac parte fie din postul 1 fie din postul 2, adic X31 + X32 = 1 i X41 + X42 = 1. Dac ns F7 este cuprins n alt post cele dou restricii nu mai trebuie impuse. Din nou, aceasta se scrie pe scurt:

X31 + X32 X72 i X41 + X42 X72


*


Se procedeaz n mod similar admind eventuala amplasare a fazei 7 n postul 3, apoi n 4 i n sfrit n 5. S observm c dac faza 7 se include n ultimul post, al aselea, nici un fel de condiie nu trebuie impus asupra predecesorilor F3 i F4 ntruct, oricum, orice faz se execut pn la sau la ultimul post de lucru.

Forma general a acestor restricii, considernd posturile liniei de la 1 la L-1 i dup rearanjarea termenilor, apare sub forma grupului de relaii.

S-a admis L ca limit superioar a numrului de posturi de pe linie. Este posibil ns c, pn la urm, configuraia optim s aib mai puin de L posturi; de aceea trebuie s ne asigurm c nici o faz nu apare inclus n vreunul din posturile ipotetice care nu rmn n configuraia final a liniei.

De exemplu, pentru a evita ca postul 1 s fie inexistent (adic 1 = 0), n timp ce totui unele faze i-ar fi alocate scriem:

X11 + X21 + X31 + X41 + X51 + X61 + X71 + X81 + X91 + X10,1 + X11,1 + X12,1 12 1.


*


Dac 1=0, evident c toi X care au pe 1 ca al doilea indice trebuie s fie zero; dac ns postul 1 este operant, atunci inegalitatea de mai sus impune ca n acesta s nu fie incluse mai mult de 12 faze, ceea ce de fapt nici nu constituie o restricie din moment ce numrul total al fazelor este 12.

Condiiile de acest tip formulate pentru cazul general cu L posturi de lucru sunt artate ca relaiili.

Odat modelul formulat, rezolvarea lui ne va furniza valorile optime ale variabilelor de decizie. Pentru problema luat de noi ca exemplu exist mai multe soluii optime (optim multiplu), care grupeaz cele 12 faze n 5 posturi de lucru; timpul mort d% = 8,3%.

Una din aceste soluii este:

1* = 1, 2* = 1, 3* = 1, 4* = 1, 5* = 1, 6* = 0;

X11* = 1, X22* = 1, X33* = 1, X41* = 1, X53* = 1, X64* = 1;

X73* = 1, X84* = 1, X94* = 1, X10,5* = 1, X11,5* = 1, X12,5* = 1.

cu toi ceilali Xji* egali cu zero.


*


Figura urmtoare constitue o reprezentare grafic a liniei n flux corespunztoare soluiei de mai sus.

Postul 1 Postul 2 Postul 3 Postul 4 Postul 5

P1=11min P =9 min P3=11min P4=12 min P5=12 min

Figura 22.1. Soluie optim cu 5 posturi de lucru


*


22.2. Rezolvarea problemei cu ajutorul metodelor euristice

n rezolvarea problemelor de echilibrare a liniei se pot folosi cu rezultate pozitive modelele euristice.

Termenul de euristic provine de la cuvntul grec "heuriskein" care nseamn a descoperii este atribuit acelor modele care utilizeaz logica i bunul sim bazate pe observare i introspecie pentru a rezolva o anumit problem, atunci cnd metodele analitice de calcul nu pot fi utilizate cu rezultate pozitive.

Desigur, chiar dac modelele euristice nu duc totdeauna la soluiile optime ale problemei ca n cazul folosirii metodelor matematice, ele contribuie la obinerea unor soluii apropiate de acestea.

La aceasta trebuie adugat faptul c, n cazul problemelor complexe, aproximaiile heuristice conduc la obinerea unor rezultate mai bune dect n cazul folosirii unor metode matematice formal deosebit de riguroase.


*


Folosirea procedurii euristice este recomandat datorit urmtoarelor considerente [1], [3]:
Cnd se proiecteaz organizatoric o linie n flux, de multe ori este necesar s se repete echilibrarea acesteia cu diferite valori ale ritmului, fapt care pledeaz mpotriva folosirii unor algoritmi de echilibrare costisitori.n afara relaiilor de preceden succesiune, ntre faze mai apar i alte intercondiionri (de exemplu restricii stnga-dreapta, fa-spate, sus-jos) care, dac ar fi cuprinse n modelul problemei ar face ca acesta s devin foarte complicat. De aceea uneori preferm s pornim prin a rezolva un model simplificat, a crui soluie va fi apoi mbuntit de personalul tehnic de specialitate prin ncorporarea acelor considerente care, pe motive de complexitate excesiv, nu au fost incluse iniial n model. Evident c pentru rezolvarea unui model simplificat, aproximativ, este inutil folosirea unui algoritm exact de rezolvare. n funcionarea unei linii apar deseori factori perturbatori imprevizibili (absena de la lucru a unui muncitor, defectarea unui utilaj) care pot face necesar reechilibrarea rapid a liniei; ntr-un astfel de caz, o procedur complicat care cere timp ndelung de calcul i nu va putea rspunde imperativului situaiei.

*


n cele ce urmeaz ne vom concentra asupra nelegerii modului de lucru a metodelor euristice n rezolvarea problemelor de echilibrare a liniilor, scop n care vom ilustra dou astfel de proceduri n contextul exemplului nostru din figura 22.1.

Mai nti s inspectm figura 22.3 i s observm c cele 12 faze ale procesului tehnologic, aa cum sunt ele grupate n posturile de lucru, formeaz urmtorul ir (barele verticale delimiteaz posturile):

F1, F2, | F2, | F3, F7, F5 | F9, F6, F8, | F10, F11, F12 .

Spunem c acest ir este executabil deoarece sunt respectate toate relaiile de preceden-succesiune; nici o faz nu s-a introdus n ir nainte ca toi predecesorii si s fac deja parte din ir.


*


Dac pentru o anumit problem de echilibrare construim toate irurile, sau ordonrile, executabile i apoi pentru fiecare ir grupm fazele sub forma posturilor de lucru n ordinea dat, avnd grije ca la nici un post suma duratelor s nu depeasc valoarea ritmului nseamn c de fapt facem o enumerare exhaustiv a tuturor posibilitilor de organizare a liniei, dintre care vom putea alege n final pe aceea care prezint numrul minim de posturi. Evident, enumerarea complet nu poate constitui o metod practic de rezolvare din cauza numrului foarte mare de iruri executabile.

Tocmai de aceea, orice procedur euristic renun la aceast enumerare exhaustiv. Nu construiete dect un singur ir executabil. Pentru aceasta, de fiecare dat cnd o nou faz trebuie adugat irului aceasta se alege din mulimea fazelor nc neincluse n ir, cu ajutorul unei regului de selecie.

Literetura de specialitate menioneaz multe astfel de reguli, problema este de a gsi o astfel de regul de selecie care s conduc, dac nu totdeauna la numrul minim posibil de posturi, cel puin la un numr ct mai apropiat de cel minim.


*


22.3. Procedura euristic 1 este bazat pe urmtoarele reguli [1], [3]:

Din setul de faze executabile se selecteaz, n vederea includerii n ir, mai nti faza cu cel mai mare numr de succesori imediai (o faz este executabil atunci cnd toi predecesorii ei imediai au fost inclui deja n ir; o faz fr predecesori este de la bun nceput executabil).

n caz c dou sau mai multe faze au acelai numr total de succesori, regula 1 rezultnd ntr-o nedeterminare, se alege ntre acestea faze la ntmplare.

Esena primei reguli const n aceea c, alegnd cu prioritate faze cu muli succesori, tinde s asigure n etapa urmtoare un numr mai mare de faze executabile, oferind astfel o selecie mai larg.

Pentru a uura aplicarea procedurii se prezint tabelar cele 12 faze la un loc cu numrul lor de succesori imediai, tabelul 22.1:


*


Tabel 22.1. Prezntarea numrului de succesori imediai

Iat cum se procedeaz:

la nceput fazele F1 i F2 sunt executabile; se alege F1 conform regulii 1;

dup includerea n ir a fazei F1, lista fazelor executabile devin: F2, F3, F4, dintre care F3 are cei mai muli succesori imediai i ca urmare este selectat;

apoi, F2, F4 i F6 sunt executabile; cum toate au acelai numr de succesori imediai se apeleaz la a doua regul; alegerea a czut pe F6;

acum, F2, F4 i F8 sunt executabile; prima regul conducnd la nedeterminare se selecteaz din nou la ntmplare i rezultatul este F4 etc.

n final am obinut urmtoarea ordonare executabil:

F1, F3, F6, F4, F8, F7, F2, F5, F9, F10, F11, F12.


*
FazaF1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12Numrul de succesori imediai2 1 2 1 1 1 1 1 1 1 1 0

Fazele se atribuie posturilor de lucru n aceast succesiune, avnd n vedere ca la nici un post duratele nsumate ale fazelor aferente s nu depeasc ritmul impus r=12;

F1, F3, F6 | F4, F8 | F7, F2 | F5, F9, F10 | F11, F12.


n figura 22.2 apare o reprezentare grafic a liniei n flux rezultate. S remarcm c aceast metod euristic a reuit s produc pentru problema noastr o soluie optim, adic o echilibrare cu numrul minim posibil de posturi N = 5. Totui, observm c metoda folosit nu este cea mai potrivit pentru problema considerat datorit faptului c cele mai multe faze au cte un singur succesor imediat, ceea ce a fcut ca n majoritate selecia s se fac cu a doua regul, adic printr-un mecanism aleator. Dac am aplica din nou procedura asupra exemplului nostru s-ar putea s obinem o alt echilibrare, de data aceasta poate suboptim, funcie de cum s-ar desfura selecia ntmpltoare.


*



P1=12 min P2=12 min P3=12 min P4=18 min P5=11 min

Figura 22.2. Echilibrarea optim generat prin Procedura Euristic 1


*


Cea de a doua tehnic care se va prezenta difer de cea precedent nu numai din punctul de vedere al regulilor de selecie ci i ca mod de lucru. Dac dup prima metod nti s-a generat irul executabil i de abia dup aceea s-a trecut la atribuirea fazelor posturilor de lucru, noua metod construiete ordonarea executabil n strns legtur cu alocarea fazelor n posturi.

22.4. Procedura euristic 2 const n urmtoarele [7]:

Se ntocmete lista fazelor executabile.

Din aceast list se selecteaz acele faze ale cror durate nu depesc, fiecare n parte, timpul rmas pn la limita valorii ritmului n postul curent aflat n construcie; numim aceste faze candidai. Dac nu se poate gsi nici un candidat nseamn c postului curent nu i se mai poate aloca nici o alt faz i se trece la postul urmtor.

Se alege dintre candidai o faz la ntmplare i se atribuie postului aflat n construcie.

Se repet paii 1,2 i 3 pn ce toate fazele sunt cuprinse n posturi de lucru.


*


S exemplificm cu cteva iteraii:

ncepem s construim postul 1; timpul disponibil este 12.

Postul 1 coninnd deja faza F1, timpul disponibil se reduce la 6.


*
Faze executabileDurataCandidaiSelectat ntmpltorF1F269F1F2F1Faze executabileDurataCandidaiSelectat ntmpltorF2F3F4945F3F4F3

Avnd F1 i F3 n postul 1 timpul disponibil este 2.

Postul 1 este complet.

Se trece la postul 2, timpul disponibil n acesta fiind 12.


*
Faze executabileDurataCandidaiSelectat ntmpltorF2F4F6952F6F6Faze executabileDurataCandidaiSelectat ntmpltorF2F4F8957F2F4F8F8

Procednd astfel n continuare, este generat ordonarea executabil de mai jos i echilibrarea suboptim (N=6 posturi) din figura 22.3.

Postul 1 Postul 2 Postul 3 Postul 4 Postul 5 Postul 6

P1=12min P2=12 min P3=6 min P4=9 min P5=5 min P6=11min

Figura 22.3. Echilibrarea suboptim generat prin Procedura Euristic 2


*


Date post:	25-Sep-2015
Category:	Documents
Upload:	sideacristian
View:	254 times
Download:	0 times

Modulul 22.ppt

Documents