8/3/2019 SDED

1/26

Sisteme dinamice cu evenimente discrete

3. Modelare utiliznd algebra (max, +)

3.1 Introduceren acest sec iune prezentm elemente ale teoriei sistemelor cu evenimente discrete dezvoltate n algebra (max,+).

Sistemele dinamice cu evenimente discrete sunt sisteme ale cror comportament este completdetererminat prin cunoa terea momentelor de nceput i de sfr it ale activit ilor executate n cadrul acestora. Structura mul imii de activit i poate fi descris, n general printr-un graf de evenimente temporizat. Aceste sisteme se bucur de o anumit liniaritate n sensul algebrei (max,+), algebr ce

permite o abordare a analizei i sintezei acestora foarte asemntoare cu cele din teoria clasic a sistemelor liniare. Se regse te o reprezentare de stare ce permite introducerea conceptelor de reac ie i de sistem n bucl nchis, ai crei parametrii sunt resursele materiale ale procesului modelat.

Multe procese de produc ie pot fi modelate ca sisteme dinamice cu evenimente discrete. Ca un exemplu de aplicare a abordrii prezentate, vom trata modelarea sistemelor de produc ie, n

particular sistemele de asamblare. Ea ne va permite tratarea att a sistemelor de fabrica ie de tip flow-shop, ct i a celor de tip job-shop.

3.2 SDED deterministe i finiteUn SDED determinist i finit este caracterizat de o mul ime de activit i A i de o mul ime de

resurse Rpartajate de activit i (activit ile intr n concuren pentru a li se aloca resurse ). Ordinea n care activit ile sunt executate poate fi descris printr-un graf orientat aciclic ( A,U). Pentru dou

activit i ai i aj, apartenen a ( ai , aj ) U semnific faptul c activitatea aiprecede activitatea aj.Graful este numit de obiceo graf de preceden i corespunde unei rela ii de ordine par ial (rela ia de

preceden ). Se presupune c graful ( A, U) este conex ca n fig. 3.1. n cele ce urmeaz vom notaarcele (ai , aj ) prin (i, j).

Fig. 3.1 Exemplu de graf de preceden

Fiecrei resurs r R i se asociaz un drum Pr n graf, adic o secven de activit i

consecutive n graf. DrumulPr corespunde unei ordonan ri a activit ilor asociate resursei r. ntructfiecare activitate utilizeaz cel pu in o resurs, considerm c mul imea acestor drumuri

1

8/3/2019 SDED

2/26

P={ Pr/ r R}

este o acoperire a grafului (A, U), adic

Exist dou motive posibile pentru care o activitate ai precede o alt activitate aj:

cele dou activit i partajeaz aceea i resurs i deci nu o vor putea utiliza n acela i timp; exist o restric ie de preceden impus de procesul descris de ( A, U).Cnd exist dou activit i care necesit aceea i resurs i nu tim care dintre cele dou activit i

va fi executat prima, graful de evenimente este disjunctiv. Spunem n acest caz, c SDED nu estedeterminist (trebuie fcut o alegere de obicei la un nivel de comand). Pentru a evita acest lucrufacem ipoteza c sistemul nostru poate fi descris printr-un graf de evenimente. Astfel un SDED esteun cvartet (A, U, R, P) n care mul imile ce intervin sunt definite mai sus.

De exemplu, un proces de fabrica ie (proces de asamblare sau proces de uzinare) poate fi descris prin transformri de stare aduse la n produse (pj, j=1,..., n) de ctre m echipamente (ei, i=1,..,m).

Fiecrui produs i se asociaz o secven format dintr-un numr finit de echipamente, cu semnifica ia c produsul respectiv va trece pe rnd pe la echipamentele din secven pentru a suferi transformri de stare specifice. Aceastp secven este numit uneori rutaj. n aceste condi ii semnifica ia mul imilor definite mai sus este urmtoarea:

A = mul imea de activit i necesare pentru producerea celor n produse; le putem notaprin perechi (i, j), unde i este indicele echipamentului ei, iarj este indicele produsuluipj;

R= mul imea de produse i de ma ini (adic de resurse); U = mul imea de restric ii de preceden ntre activit i, restric ii cuprinse n secven ele

asociate produselor, sau n secven ele operatorii asociate ma inilor P = mul imea de secven e asociate produselor i de secven e operatorii asociate

ma inilor.Fiecare drum Pr con ine o activitate ini ial i o activitate final, notate a1(r) i respectiv

akr(r). Se definesc mul imile

I= { a1(r)/ r R}

F= {akr(r)/ r R}

undeI con ine toate ac iunile fr predecesor, iar F con ine toate ac iunile fr succesor. Pentru exemplul din fig. 3.1 se poate scrie:

P1 =a1a3a5a6, P2 =a1a4a5, P3 =a2a4a6I= { a1, a2}, F= { a5, a6}

Fiecare arc (i, j) din U are drept pondere un numr real tij care este suma ntre durata ac ivit ii ti i timpul de trecere (setup time) dijde la activitatea i la activitatea j. Ponderea unui drum din graful(A, U) este egal cu suma ponderilor tuturor arcelor. Lungimea unui drum este egal cu numrul sude arce.

Introducem urmtoarele variabile: xi este momentul cel mai devreme de declan are a activit ii i (momentul n care

resursele necesare pentru declan area activit ii i sunt disponibile; o activitate nu sedeclan eaz ns obligatoriu n acest moment)

ureste momentul cnd resursa r este disponibil pentru prima activitate a secven ei

sale a1(r)Dac (i, j) U, atunci xi yj + tij

2

8/3/2019 SDED

3/26

Dac i este prima activitate a resursei r, adic a1(r), atunci xi ur.

Fie mul imea de predecesori ai activit ii i i R0(i) mul imea de resurse care au proprietatea

a1(r)=i.

n aceste condi ii, xi verific ecua ia:

Aceast ecua ie va cpta o form mai simpl i linear ntr-un anumit sens, n cele ce urmeaz.

3.3 Model de stare utiliznd dioidul

Amintim structura algebric de dioid care are aplica ii n teoria grafurilor, unde mai este cunoscut i sub numele de algebra drumurilor.

Defini ie 3.1: Structura este un dioid dac satisface axiomele:

este un monoid comutativ i admite un element neutru , este un monoid cu element unitate e

este element absorbant pentru opera ia multiplicativ ,

legea este idempotent,

legea multiplicativ este distributiv la stnga i la dreapta fa de legea aditiv

Se verific u or faptul c este un dioid comutativ cu = - i e=0.

n general, opera iile i induc pe mul imea M(n,S) a matricelor ptrate de ordin n cuelemente din S, aceea i structur de dioid cu elementul nul i elementul unitate indicate mai jos:

DacA, A M , atunci avem:

Defini ie 3.2 : Se nume te quasi invers al unui element a, apar innd dioidului S, limita, atunci cnd aceasta exist.

n anumite condi ii, pentru o matrice din M(n, S) exist o quasi-invers.Se poate defini matricea de inciden generalizat pentru graful ( A, U) astfel:

A este o matrice N x N, unde N = card(A)Fie B o matrice R x N, unde R= card(R), definit astfel:

Evident, matricea B indic activit ile de debut pentru fiecare resurs.

3

8/3/2019 SDED

4/26

n condi iile enun ate mai sus, ecua ia (3.1) devine:

X=X.A U.B, unde X=(x1, ... , xN) i U=(u 1, ... , uR)

Fie Y vectorul celor mai devreme momente de timp cnd resursele se elibereaz de ultimile loractivit i. Dac se define te matricea C de dimensiuni N x R ca mai jos:

a.. fiecrei resurse s-i corespund durata ultimei sale activit i, atunci vectorul Y se poate scrieY=X.C (3.3)

Analogia ntre ecua iile (3.2) i (3.3) i ecua iile sistemelor liniare clasice este evident. Teorema 3.1: Ecua ia

X=X.A U.B

are solu ie unic, de ndat ce U este cunoscut, avnd formaX=U.B.A* (3.4)

Dm mai jos demonstra ia acestei teoreme, pentru c din ea se degaj interpretarea quasi-invers A*

n raport cu graful (A, U).Observa ie: A* se poate construi cu ajutorul unui algoritm de determinare a celui mai lung drum.

Un SDED se spune c este n bucl nchis dac este finit (un numr este finit de variabilede stare, i.e. N finit) i dac exist un retur (feedback) al activit ilor finale ctre activit ile ini iale. De fapt, acest retur modeleaz reluarea activit ilor de ctre resurse care sunt n numr finit i care rmn mereu acelea i. n acest mod se introduc aspectele repetitive.

Pentru a descrie returul resurselor se introduce rela ia:

definit astfel:

adic, resursa r i reia secven a ncepnd cu activitatea ini ial dendat ce a terminat activitatea final.

n mod formal, un SDED n bucl nchis este un cvintuplu (A, U, R, P, B), unde B estegraful bipartit (F, I, L) ata at rela iei L. Orice resurs rpoat s i reia cel de-al n-lea ciclu, dup cea terminat ultima activitate a celui de-al (n-1)-lea ciclu i preparativele legate de trecerea de la o activitate la alta sunt terminate. Aceste restric ii se pot exprima prin egalitatea:

U(n)=Y(n-1).KundeKeste o matriceRxR definit astfel:

Utiliznd rela iile (3.3), (3.4), (3.5), ob inem Y(n)=U(n).B.A*.C= Y(n-1).K.B.A*. (3.6)

Egalitatea (3.6) ne permite s determinm recursiv secven a Y(1), Y(2), ... , Y(n), ... , cunoscndu-seU(1). Cu ajutorul ecua iei (3.4) se determin secven a X(1), X(2), ... , X(n), ... . De aceea, rela iile (3.4) i (3.6) sunt de o mare inportan n simularea SDED. Ecua ia (3.6) poate fi scris sub forma

Y(n)=Y(n-1).M, Y(0)=Y0 (3.7)unde

4

8/3/2019 SDED

5/26

M=K.B.A*.Ceste o matriceNx N.Ecua ia (3.7) reprezint ecua ia recursiv a sistemului n bucl nchis .

Ca i n teoria sistemelor liniare exist un sistem dual sistemului (A,B,C) de mai sus.

Pentru a-l pune n eviden . Intorducem urmtoarele variabile: qi semnific cel mai trziu moment al nceperii activit ii i vr este cel mai trziu moment cnd resursa r trebuie s fie eliberat dup terminarea

activit ilor sale zr este cel mai ru moment cnd resursa r trebuie s fie disponibil, a.. activit ile s poat fi

executate n timpul dorit, adic resursa s fie eliberat nainte de timpul pentru r=1, ..., R.

Dac , atunci qj qi - tji , iar dac ai este ultima activitate a resursei r, atunci qi vr- ti .

Notm cu mul imea succesorilor activit ii ai i cu R(i) mul imea resurselor care au ca

activitate final pe ai.

Dualul ecua iei (3.1) este

Se introduc i vectorii Q, V, Za. .

Dualul ecua iilor SDED (3.2) i (3.3) este

Q=Q.A C.V

Z=B.Q

Cum cele mai trzii momente de eliberare a resurselor pentru ciclul n sunt condi ionate de cele mai trzii momente de disponibilitate ale acestora pentru ciclul urmtor, putem scrie

V(n)=K.Z(n+1)

n acest caz, ecua ia SDED n bucl nchis esteV(n)=K.B.A*.C.V(n+1),

cunoscndu-se V(nf) ntr-o stare final atins la un anumit n=nf.Meritul acestui formalism este de a fi scos n eviden dou aspecte. Primul este caracterul

nedeterministpe care l au, n general, sistemele dinamice cu evenimente discrete. Acest lucru reiesedin ipoteza care a trebuit s fie adoptat de formalismul (max, +), i anume c sistemul dinamic cu evenimente discrete este un graf de evenimente. Ori, un graf de evenimente se caracterizeaz tocmai

prin faptul c logica lui de evolu ie este bine precizat. n cazul general, evolu ia de stare a unui

sistem dinamic cu evenimente discrete nu este unic precizat a priori. Sistemul i alege o anumit evolu ie, n func ie de factori externi. Este binecunoscut exemplul re elelor Petri ce prezint conflicte. Acestea se rezolv la un nivel ierarhic superior sistemului modelat. Cu alte cuvinte, pentrua determina evolu ia sistemului, este nevoie de informa ie suplimentar. Din acest motiv, se poate spune c, n general, nu se cunoa te n faza de modelare toat informa ia necesar pentru a ob ine o evolu ie univoc, presupunnd intrrile cunoscute. Al doilea aspect, i cel mai important, pus n eviden de formalismul (max, +) este legat de natura intrrilor, care este oarecum artificial, fa de mrimile de intrate a sistemelor continue sau discrete. Aici apare explica ia major a dificult ii de a modela i analiza sistemele dinamice cu evenimente discrete. Este vorba despre dificultatea de a

defini no iunea de semnal.4. Modelare utiliznd algebraMinMax

5

8/3/2019 SDED

6/26

Pn acum am utilizat pentru modelarea SDED numai dioidul . O alt

structur algebric ce ne permite s abordam modelarea SDED, cu consecin e sistemice bogate, este o algebr specific de serii formale numit MinMax(,). Exist un interes major pentru grafurile deevenimente temporizate (GET) justificat prin faptul c multe sisteme de fabrica ie pot fi modelate

prin RP P-temporizate ce sunt grafuri de evenimente.Rmnnd n ipoteza simplificatoare a sistemurilor grafurilor de evenimente, formalismulMinMax amelioreaz esen ial formalismul (max, +) prin modelarea explicit a semnalelor de intrare i de ie ire. Nu orice informa ie prezent la intrarea unui sistem poate fi acceptat ca fiind semnal de

intrare. Semnalul poart informa ie, dar o informa ie inln uit, parametrizat n timp. n formalismul MinMax, se dezvluie pentru prima oar care este esen a no iunii de semnal n cadrul semnalelor dinamice cu evenimente discrete. Informa ia purtat de semnal este legat de evenimentele care se

produc ntr-o ordine cronologic. Dificultatea matematic de a trata astfel de semnale, n caremomentele de producere a evenimentelor sunt precizate explicit, este major, dar surmontabil.

4.1 Modelarea grafurilor de evenimente temporizateConsiderm c SDED n cauz se poate reprezenta printr-o RP temporizat care este un

graf de evenimente. Fiecrei tranzi ii i, i se poate asocia o func ie de datare

definit prin

n mod evident, func ia de datare este cresctoare. S-a presupus c exist un generator de tacte care d timpul absolut i c declan rile de tranzi ii sunt sincronizate pe aceste tacte. Egalitatea

semnific faptul c primele n declan ri au survenit nainte de a considera SDED, n timp ce rela ia

arat c cea de-a n -a declan are nu va avea loc niciodat.Considerm drept exemplu graful de evenimente din fig. 4.1, care este o re ea P-

temporizat. Jetoanele din locuri semnific marcajul ini ial, iar bastona ele reprezint timpii de re inere ai jetoanelor, nainte ca aceasta s poatp sensibiliza tranzi iile din aval. A a cum am vzut n sec iunea 3.2, putem scrie inegalit ile:

(4.1)

Sistemul (4.1) nu are solu ie unic. Facem i n acest caz ipoteza c tranzi iile sunt declan ate imediat ce sunt sensibilizate. Ob inem, astfel, cea mai mic solu ie pentru (4.1).

6

8/3/2019 SDED

7/26

Fig. 4.1 Exemplu de graf de evenimente cu marcaj ini ial i timpi de re inere

Dac notm cu mul imea func iilor de datare, pe care le asociem cu semnalele, putem

introduce operatorii elementari de deplasare:

: x(n)=x(n)+1 (deplasare n timp cu o unitate)

: x(n)=x(n-1) (ntrziere la numrare cu o unitate)

Mul imea operatorilor poate fi dotat cu dou opera ii:

adunarea, noatat , ce corespunde maximului semnalelor

produsul de compozi ie, notat multiplicativ.

Folosind ace ti operatori, sistemul (4.1) se scrie astfel:

(4.2)

sau utiliznd o reprezentare de stare

(4.3)

unde

7

8/3/2019 SDED

8/26

Ceea ce intereseaz este solu ia minim a sistemului (4.3), solu ie care codific func ia de datare pentru toate tranzi iile. n felul acesta se furnizeaz o descriere complet a exolu iei celei mai timpurii a grafului de evenimente.

Pentru c operatorii i comut, singurii operatori de care avem nevoie pentru a modela

grafuri de evenimente temporizate sunt sume finite de operatori

n

.

t

. Din nefericire, o sum de tipul

nu reprezint un singur operator, datorit existen ei unor propriet i de absorb ie. Dac t t, atunci

(4.4)

Dac n n, atunci

(4.5)

Avem urmtoarele reguli fundamentale de absorb ie:

(4.6)

4.2 Algebra MinMax (, )n cele ce urmeaz descriem o structur algebric care s reflecte propriet ile operatorilor de

deplasare.Fie B={, e} mul imea variabilelor booleene ( este zeroul i e unitatea) cu opera iile

booleene . Notm cuB (, ) mul imea seriilor formale de variabile i , cu coeficien i n

(mul imea numerelor ntregi), dotat cu opera iile uzuale de adunare i nmul ire .

O serie formal s corespunde unei func ii

prin expresia

Se verific cu u urin c ( B(,), , ) este un dioid comutativ. Elementul nul este seria cu to i

coeficien ii egali cu i o vom nota tot cu . Pentru simplitatea scrierii, monoamele de forma s(n,t)

le vom scrie sub forma s(n,t)n t.

Printr-o construc ie clasic, se introduce rela ia de ordine par ial

s r

i se demonstreaz c mul imea ( B(,), , ) este complet, adic orice submul ime W admite o cea mai mic margine superioar care este

Pentru c i proprietatea de distributivitate infinit

este adevarat, dioidul (B(,), , ) este complet.

Se define te suportul unei serii s ca fiind

Supp(s)={(n,t) }.

O serie este complet determinat de suportul su pentru c

8

8/3/2019 SDED

9/26

Cnd suportul unei serii s este finit, se zice c s este un polinom. Polinoamele alctuiesc unsubdioid pe care-l notam cu B(, ). Cum singurele elemente inversabile n B(, ) sunt monoamele,se introduce o opera ie nou notat *. Opera ia * joac un rol analog cu inversarea n algebra clasic i, de aceea, se nume te opera ie ra ional. Ea se introduce tot prin defini ia 3.2, dar motiva ia

existen ei elementului quasi-invers este diferit.Fiind complet, B(, ) este nchis la sume infinite. Opera ia * are urmtoarele propriet i u or de verificat:

i. (a*)* = a*

ii. (a b)* =a*.b* (4.7)

iii. a* = a* a*

Defini ia 4.1: Fie D un diod comutativ i a, b D. Spunem c a este echivalent cu b modulo z i

notm prin a b (mod z), dacaz* = bz*

Teorema 4.1: a b (mod z) este o rela ie de echivalen . Dac notm cu clasa de echivalen a elementului a, atunci i depind numai de i i nu de

elemente particulare din cele dou clase. Structura (D/z, , ) este un dioid, unde

i sunt definite prin

Corolar 4.1: Dac considerm D= B(, ) i z = -1, putem conchide c B(, )/ ( ) este un

dioid i, ntruct

( -1)*= ( )* (-1)*,

func ia

este o congruen .Dioidul ct B(, )/ ( ) va fi notat cu MinMax(, ). Pentru elementul nul n MinMax(, )

avem mai multe reprezentri:

e = ( -1)*= ( )* (-1)*= ( )*= (-1)*=0=0= 0. 0.

Acela i lucru este valabil i pentru celelalte elemente.

ntr-o clas de echivalen [a] MinMax(, ) exist un cel mai mare element din B(, )

care reprezint clasa. Datorit propriet ii (4.7)iii., avema( )* (-1)* [a]

Valoarea a( )* (-1)* nu depinde de a, ci depinde de clas. ntr-adevr,

a, b .

Pe de alt parte, ntruct

( -1)*= e ,

rezult c

.

Cum nmulirea este izoton cu relaia de ordine , avem

a( )* (-1)* .Deci a( )* (-1)* este cel mai mare element repreyentativ al clasei [a].

9

8/3/2019 SDED

10/26

Calculele n acest dioid se fac dup regulile uzuale cu serii de puteri, innd cont de faptul cputem avea mai multe reprezentri pentru aceeai cantitate.

Ca o observaie foarte important, s remarcm c regulile (4.15) sunt valabile, ceea cejustific considerarea structurii MinMax(, ). Forma lor general este

Clasele de echivalen ale polinoamelor vor fi numite de asemenea polinoame. Ele alctuiesc,n mod evident, un subdioid pe care-l notm cu MinMax(, ).

Dioidul MinMax(, ) este complet i, printr- o construcie clasic, se poate arta c, pe lngmargine superioar, exist margine inferioar pentru orice submulime a sa.

Exist o reprezentare grafic pentru elementele din MinMax(, ) care evideniaz regulile de

absorbie ale operatorilor i . Fiecrui monom B(, ) i se poate asocia punctul de

coordonate (n, t) din . Astfel, clasei de echivalen a lui s i se asociaz mulimea de puncte

corespunztoare lui , adic Supp . De exemplu, clasei de echivalen a lui i seasociaz punctele situate n colul de sus-est al planului care are vrful n punctul (3,2) i.e.

{(3+u, 2-v)| (u,v) }. Astfel, un element din MinMax(, ) este reprezentat prin reuniunea unor

astfel de coluri elementare. Se obine pentru un element din MinMax(, ) o mulime de puncte

din . Adunrii i corespunde reuniunea mulimilor de puncte, iar produsului i corespunde suma

vectorial a mulimilor asciate de puncte.

Fig. 4.2 Reprezentare grafic pentru MinMax(, )

Regulile de absorbie ale operatorilor i se justific imediat. n fig. 4.2 se prezintpolinomul

Acest polinom poate fi simplificat prin,

ntruct cade n umbra monomului .

4.2 Reprezentarea intrare ieire a SDEDOperaia * se poate extinde i asupra matricilor ptrate din Mn,n(MinMax(, )). Ca n

paragraful 3.3 se poate arta c:

Teorema 4.2: Fie A Mn,n(MinMax(, )) i b Cea mai mic soluie a

sistemului

x Ax b (4.8)

10

8/3/2019 SDED

11/26

estex=A*b (4.9)

Particulariznd la sistemul (4.2) ob inemx=A*Bu i y=C.A*.Bu

MatriceaH= C.A*.Bse nume te matricea de transfera sistemului.

n teoria sistemelor clasic, matricea de transfer este caracterizat ca fiind rspunsul laimpuls al sistemului. Aceast caracterizare este adevrat i n algebra MinMax(, ).

Am vzut c func iile de datare pot fi privite ca semnale. Unei astfel de func ii x,

,

i se asociaz n mod firesc seria

(4.10)

cu conven ia - = i + = * .Reciproc, fiind dat o serie s, singura func ie de datare Ds care s verifice s= Sx este

(4.11)

Formulele (4.10) i (4.11) permit o identficare a semnalelor cu seriile formale.

Considerm un sistem u y care are seria de transfer

H=

Aplicm defini ia operatorilor de deplasare, pentru a vedea care este efectul seriei de transfer asupra semnaluluiu de intrare:

Rela ia intrare-ie ire ntre u i y este dat de a a-numita max-convolu ie a func iilor de datare:

(4.12)

Rela ia (4.12) se scrie utiliznd seriile formale astfel:

(4.13)

S remarcm c

e =

i deci func ia de datare corespunztoare se poate scrie

Func ia de datare codific faptul c evenimentele cu numerele 0,1,2,... survin toate la momentul 0. Din aceast cauz semnalul e se nume te impuls. O cantitate infinit de intrri apar la momentul 0. n consecin

ceea ce nseamn c ie irea cu func ia de datare asociat cu H este rspunsul la impuls.4. 3 Serii ra ionale i serii periodice

Considerm un diod complet D i o submul ime E D care con ine pe i e. Faptul c a,b

E nu nseamn c solu ia (4.9), a sistemului (4.8) apar ine lui E. Acest lucru se datore te opera iei *.

11

8/3/2019 SDED

12/26

nchiderea ra ional a lui E este cea mai mic submul ime E* D care con ine pe E i toate sumele i

produsele finite, precum i quasi-inversele elementelor sale. O submul ime E D se zice c este

ra ional nchis dac i numai dac E*=E.n modelarea sistemelor de tip GET, apar numai polinoame cauzale, adic polinoame care au

numai exponen i pozitivi pentru i . Vom nota cu MinMax+(, ) subdioidul polinoamelor cauzale.Matricile de transfer sunt obiecte de tipul CA*B unde

A* Mn,n(MinMax+(, ))*, C Mp,n(MinMax+(, )), B Mn,q(MinMax+(, ))

Un rezultat fundamental (teorema Schutzenberger-Kleene) este exprimat prin:[Mn,n(MinMax+(, ))]*= Mn,n[(MinMax+(, ))*]

ceea ce nseamn c ob inerea lui A * se reduce la calculul de quasi-inverse pentru scalari. De aceea,mai jos ne ocupm de cazul scalar.

Defini ia 4.3: O serie se nume te ra ional, dac apar ine nchiderii ra ionale a subdioidului polinoamelor cauzale (MinMax+(, )).

Defini ia 4.4: Fie (v, ) (N-{0} x N-{0}) O func ie de datare nd(n) este ( v, )periodicdac exist N N a. .:

d(n+v)=d(n)+, .

Conform defini iei, la un interval de unit i de timp apar v declan ri ale tranzi iei creia i s- a asociat func ia d. Panta periodic a lui d este prin defini ie:

.

Valoarea minim a lui N se nume te lungimea regimului tranzitoriu, iar valoarea minim

pentru perechea (v, ) se nume te periodicitatea lui d. Cazul degenerat (v, )=(1,0) sau (0, )

reprezint situa ia cnd un numr infinit de evenimente apar ntr-un timp finit i, respectiv, cnd nu mai apare niciunul dup evenimentul (N-1).

Defini ia 4.5 : O serie s MinMax(, ) este (v, ) periodic, dac func ia de datare asociat este

(v, ) periodic.Se poate arta c o serie s este (v, ) periodic dac i numai dac exist dou polinoame p i q a..

S=p q(v .)* (4.14)

Acesta se nume te reprezentarea periodic a lui s cu periodicitatea v ..Teorema 4.3: Sunt echivalente propriet ile:

i. Seria s este ra ionalii. Seria s este periodic

Se poate arta c mul imea seriilor periodice este stabil fa de opera iile , i *. Pentru

aceasta, introducem pe mul imea periodicit ilor opera ia definit prin:

(4.19)

i se arat c produsul a dou serii periodice s= i este periodic cu

perioada .

12

8/3/2019 SDED

13/26

n ceea ce prive te quasi-inversa unei serii periodice s= , formula urmtoare

reduce calculul la aflarea quasi-inversei unor polinoame.Dac p este un polinom de complexitate n (numr de monoame)

,atunci problema calculului lui p* se reduce, prin aplicarea propriet ii (4.7)ii., la calculul quasi-inversei unui polinom de complexitate n-1, conform formulei

Dac aplicm cele de mai sus sistemului 4.3, vom gsi o form mai simpl pentru A

pentru c domin , conform cu interpretarea grafic dat mai sus. Pentru calculul lui A*,

aplicm urmtoarea formul valabil ntr-un dioid comutativ

i care st la baza calculului de reducere a quasi-inversei matriceale la cazul scalar.Pentru exemplul nostru ob inem

Calculnd matricea de transfer ob inem

H= C.A*.B= (4.29)

Putem ns s lucrm direct pe ecua iile de stare (4.2). Prima ecua ie se rescrie

x1=nlocuind n ecua ia a doua ob inem

x2=

Aplicnd teorema 3.1 ob inem

i deci

y=

adic, se regse te rezultatul din (4.29).

Conducerea supervizat a SDED

Aceast sec iune este consacrat prezentrii teoriei conducerii supervizate a SDED, propus de Ramadge i Wonham n [RAMADGE 87], [RAMADGE 89], [WONHAM 93] i [WONHAM 96]. Abordarea realizeaz o generalizare a no iunilor de semnal, perturba ii, evenimente controlabile i necontrolabile etc, ct i ntr-o prezentare sistemic a teoriei controlului supervizat, n care se d o interpretare explicit a sistemului n bucl nchis.

Conducerea prin supervizare utilizeaz formalismul limbajelor i automatelor i presupune c obiectul condus este modelat prin limbaj pe care l accept sau, echivalent, prin automatulgenerator al acestuia.

13

8/3/2019 SDED

14/26

Ca i n cazul problemelor clasice de conducere a sistemelor automate, conducerea supervizat i propune sinteza unui controller, numit n acest caz, supervizor. Ansamblul obiectcondus supervizorrealizeaz unsistem n bucl nchis.

Limbaje i automateEvenimentele ntr-un proce cu evenimente discrete se consider c apar spontan, asincron i instantaneu, fiind etichetate cu literele unui alfabet.

Fie , mul imea finit de etichete asociate evenimentelor, i * mul imea tuturor irurilor finite de (etichete de ) evenimente din , inclusiv irul vid, etichetat cu 1. irul vid joac rolul de identitate la opera ia de concatenare a irurilor:

1s=s1=sPrin conven ie, un element din se consider a fi un eveniment i un ir din * un cuvnt.Un ir

se nume te secven par ial dac mai pot urma i alte evenimente dup . Mul imea tutror

traiectoriilor admisibile (fizic posibile )este deci o submul ime L . Se poate spunde despre L c

este un limbaj peste alfabetul . Ca o consecin , comportamentul unui SDED poate fi caracterizat de limbajul secven elor de tranzi ii.

Un ir u este un prefix al unui ir dac exist iruri , pentru care este

adevrat rela ia:v=uw.

Un automat G se define te printr-un cvintuplu:

G = (Q, , , q0, Qm )unde:Q = {q1, q2, ,qi, } este mulmea strilor q; este alfabetul sau mul imea de evenimente care genereaz tranzi ii de stare;

, este func ia de tranzi ie a strii;

q0 este starea ini ial;

Qm Q este o mul ime de dtri marker.

Strile marker sunt stri de interes, care pot fi stri finale i marcheaz ncheierea unei secven e de taskuri.

Pentru o stare q i un eveniment , nota ia (,q)! are semnifica ia exist tranzi ie din starea q la apari ia evenimentului , sau cu alte cuvinte func ia (,q) este definit.

O stare q Q este o stare accesibildac:

, astfel nct (,q0)=q.

Un automat este accesibil dac toate strile sale sunt accesibile.Defini ia func iei de tranzi ii a strii

,

poate fi extins pe mul imea cuvintelorpeste , prin:

dup legea

14

8/3/2019 SDED

15/26

.

n termenii grafului automat G, nota ia nseamn c exist un drum pe graf, care ncepe din

strarea q i este etichetat prin elementele consecutive ale irului s.Limbajul generat de automatul G, L(G), este definit de relaia:

L(G)={w: w a.. }.

Un automat G se numetegeneratoral limbajului L, dac L(G) = L.Repreyentarea pe stare a generatorului G nu are n mod necesar un numr finit de stri ( de exemplun cazul limbajelor generate de contori sau alte dispozitive cu o infinitate de stri). Generatorul G

este un automat, care ncepnd din execut tranziii de stare i deci genereaz evenimente,

urmrind graful de tranziii. Automatul G poate fi nedeterminist, n sensul c ntr-un nod fixat algrafului se poate ntmpla s fie mai multe evenimente posibile, deci mai multe drumuri.Limbajul marcatde automatul G n L(G) este:

Lm(G)={w: w a.. }.

Limbajul L(G) ar putea corespunde comportamentului fizic posibil, n vreme ce limbajul marcatarputea descrie comportamentul corespunztor ndeplinirii unor obiective.Limbajul generat de automatul G i limbajul marcat sunt n relaia:

Lm(G) L(G).

Limbajul L(G) poate fi interpretat ca mulimea tuturor secvenelor posibile de evenimente care potaprea, n vreme ce

Lm(G) L(G)

este o submulime distinct de secvene, care pot fi marcate sau nregistrare, cu semnificaia detaskuri ncheiate (sau secvene de taskuri) de procesul fiyic pe care G l modeleaz.

Conducerea prin supervizare. Realizri ale supervizoruluiModelul cu limbaje i automate pentru un SDED, prezentat n capitolul 6, poate fi utilizat n

scopul rezolvrii problemei de conducere prin supervizare, dac se consider c evenimentele deintrare sunt de dou categorii:

Evenimente a cror apariie nu poate fi mpiedicat Evenimente care pot fi autorizate sau interzise (apariia lor poate fi impiedicat dac

se dorete), de cte ori este nevoie.Evenimentele din cea de-a doua categorie permit influenarea comportamentului sistemului dinexterior, deci exercitarea unei aciuni de control.

n aceste condiii, mulimea de evenimente, , este partiiona n dou submulimi disjuncte:

,

unde:

reprezint mulimea evenimentelor controlabile (evenimente a cror apariie

poate fi mpiedicat la orice moment de timp, dac se dorete)

reprezint mulimea evenimentelornecontrolabile (evenimente a cror apariie

nu poate fi influenat de sistemul de comand).

15

8/3/2019 SDED

16/26

Obiectivul conducerii prin supervizare a unui SDED const n asigurarea unui comportamentdorit al procesului, descris prin restriciile de funcionare.

Conducerea prin supervizare a SDED se bazeaz pe proprietatea evenimentelor controlabilede a putea fi autorizate sau interzise i de a determina astfel comutarea ntre secvene de tranziii,

nct s fie rejectat efectul perturbaiilor modelate de evenimentele necontrolabile.n cadrul teoriei conducerii supervizate, n lucrrile [RAMADGE 82], [RAMADGE 83],[RAMADGE 87a] i[WONHAM 95] sunt definite de urmtoarele concepte.

O intrare de comandpentru generatorul

G = (Q, , , q0, Qm )

este o submulime de evenimente cu proprietatea c .

Ultima incluziune nseamn c toate evenimentele sunt ntotdeauna permise.O intrare de comand, , pentru un SDED G este o mulime de evenimente care sunt

acceptabile dintr-o stare oarecare q, n sensul c asigur evoluia sistemului pe o traiectorie de stare

ce corespunde obiectivului propus pentru conducerea prin supervizare.Evenimentele necontrolabile trebuie s aparin totdeauna intrrii de comand , atunci esteun eveniment controlabil autorizat (permis). Un eveniment care nu aparine intrrii de comandeste un eveniment controlabil interzis (apariia lui este mpiedicat). Intrarea de comand depindede starea n care este aplicat i de obiectivul conducerii prin supervizare. Un eveniment controlabiloarecare, , poate s aparin intrrii de comand i din starea qi i s nu aparin intrrii de comandj din starea qj.

Pentru un SDED G dat, se noteazp cu mulimea intrrilor de comand:

.

Un sistem cu evenimente discrete, reprezentat prin generatorul G, echipat cu o mulime de intrri de

comand se numetesistem cu evenimente discrete condus i se noteaz SDEDC G.

Conducerea unui SDEDC G const n comutarea intrrii de comand conform unei secvene de

intrri de comand 1, 2, 3 ... din . Practic, problema de conducere a unui SDED revine la a

determina mulimea i succesiunea intrrilor de comand corespunztoare unui comportament

dorit. La introducerea conceptului de supervizor, va fi adoptat practica uzual din teoria sistemelorliniare, prin care se realizeaz separarea clar dintre proces i echipamentul cu funcie de comand.n cazul acesta, rolul supervizorului este de a stabili intrarea de comand din starea curent.

Unsupervizoreste o funcie:

f: L(G) ,care specific pentru fiecare ir de evenimente care s-a produs n proces, w, intrarea de comandf(w), care trebuie aplicat pentru acest ir.

Dei funcia f este definit pe mulimea L(G), implicit putem considera c f este definit pemulimea strilor accesibile ale lui G. ntr-adevr, un ir din L(G), aplicat dintr-o stare ini ial fixat a lui G conduce sistemul ntr-o stare precizat prin func ia de tranzi ie a strii. Cu alte cuvinte, de ndat ce starea ini ial este fixat, supervizorul asociaz unei stri accesibile o intrare de comand.

Un SDEDC G echipat cu un supervizor f are apoape acela i comportament ca i n cazul n care supervizorul nu exist, numai c anumite evenimente controlabile nu se vor mai produce. Cu

16

8/3/2019 SDED

17/26

alte cuvinte, dup iru de evenimente w, evenimentul urmtor , care va determina evolu ia sistemului, trebuie s respecte condi ia:

,

unde

,este starea n care a ajuns sistemul dup aplicarea semnalului w, iar mul imea definit

de :

,

este mul imea evenimentelor urmtoare din starea q.Cu alte cuvinte, dintr-o stare accesibil prin irul de evenimente w, evenimentul urmtor

trebuie s fie posibil n automatul G i trebuie s fie autorizat de intrarea de comand , dat de supervizorul f.

Se nume te sistem nchis, sistemul format din generatorul G echipat cu supervizorul f i se

noteaz (G, f). Comportamentul n bucl nchisal sistemului (G, f) se noteaz L(G, f) = Lf i este definit formal dup cum urmeaz:

1. 1 Lf

2. w .

Obiectivul conducerii este realizat printr-un supervizor f, dac respect specifica iile de

func ionare date la formularea problemei de conducere.Pentru generatorul G, echipat cu o mul ime de stri marcate (marker) limbajul controlat de

supervizorul f n Geste :

,

unde este limbajul marcat al generatorului G (adic este mul imea irurilor de evenimente

care duc n strile marcate).Limbajul controlat de f n G este format din irurile care duc n stri marcate n limbajul

procesului i, n acela i timp, sunt scceptate de sistemul nchis. Cu alte cuvinte, acest limbaj con ine irurile ce conduc n stri cu semnifica ia de taskuri ncheiate, sub ac iunea conducerii supervizate.

Pn n acest punct, specificarea supervizorului s-a fcut prin func ia f. El mai poate fi specificat i sub forma unui automat echipat cu o func ie de ie ire cu rol de func ie de comand. Avem de-a face, n acest caz, cu o realizare a supervizorului f. El mai poate fi specificat i sub forma unui automat echipat cu o func ie de ie ire cu rol de func ie de comand. Avem de-a face, n acest caz, cu o realizare a supervizorului f.

O realizare a unui supervizor f pentru sistemul G este o pereche S = (S, ), unde

S=(X, , este un automat accesibil, determinist cu

o X mul imea (posibil infinit) de stri,

o alfabetul de evenimente

o func ia (par ial) de tranzi ie

o ,

o starea ini ial,

o o submul ime de stti marcate ;

17

8/3/2019 SDED

18/26

, este func ia de ie ire care d intrarea de comand pentru fiecare stare x a

supervizorului, dac:

. (7.1)

Se remarc faptul c supervizorul este o func ie i c o realizare a sa este un automat S, dotat cu o

func ie de ie ire . Aceast func ie de ie ire furnizeaz, la un moment dat (adic din starea curent x a automatului S), intrarea de comand

.

Func ionarea perechii automat (S) func ie de ie ire ( ), care reprezint o realizare a supervizorului

f, este prezentat n diagrama de mai jos.

Dac supervizorul este specificat printr-o realizare S=(S, ), ac iunea sa de control asupra

automatului G este determinat de func ia de ie ire ( ) i de func ia de tranzi ii a automatului S. n

acest caz, dac irul

,

atunci v va trebui s apar inlimbajului automatului S, i evenimentul urmtor pentru automatul S trebuie s fie autorizat de supervizorul f, adic

numai dac .

Aceast condi ie arat c acele tranzi ii interzise de f nu apar n structura de tranzi ii a automatului S

din defini ia realizrii S=(S, ) a supervizorului f. n plus, condi ia 2. Din defini ia formal a limbajului L(G, f) se poate scrie sub forma:

,

condi ie care asigur consisten a func ionrii lui S.Cu alte cuvinte, acele tranzi ii autorizate de f, care sunt posibile n G trebuie s apar n

structura de tranzi ii a automatului realizrii S. n aceste condi ii, G i S func ioneaz n paralel, i

func ia de ie ire este o func ie de reac ie dup stare , deoarece S reproduce practic n structura sa

de tranzi ii de stare, comportamentul admisibil al lui G, fixat prin supervizorul f.

Func ia de ie ire asigur intrarea de comand din fiecare stare a automatului S:

Se poate defini func ia , pentru un eveniment i o stare x oarecare, care ia valoarea 0 sau 1,

n func ie de faptul c evenimentul apar ine sau nu la intrarea de comand, dat de func ia de ie ire

, adic:,

astfel nct

Este evident c:

18

8/3/2019 SDED

19/26

.

n cele din urm, o realizare a supervizorului f va fi desemnat de perechea S=(S, ), unde S este

automatul din defini ia 7.6 i func ia de ie ire este func ia definit mai sus.

Pentru a stabili o analogie cu teoria sistemelor clasice, G este partea fixat (sau obiectul condus),

S func ioneaz ca un compensator dinamic, n vreme ce descrie reac ia dup stare.

Limbajul L(G) reprezint comportamentul fizic posibilal procesului cu evenimente discrete, n timpce rolul supervizorului este de a asigura sistemului comportamentul admisibil, fixat prin restric iile de func ionare.

Figura 7.1 Limbajele L(G) i L an figura 7.1, este ilustrat raportul dintre comportamentul posibil L(G) i comportamentul

admisibil, descris prin limbajul admisibil(notat La).Dac se face presupunerea c nu exist evenimente necontrolabile, atunci men inerea

traiectoriei automatului G n imteriorul La este deja o problem de conducere, dar care se rezolvla nivel logic, n cadrul teoriei automatelor. Prin proiectare, se re in din L a numai irurile crora le corespund traiectorii de stare ce respect restric iile de func ionare (de exemplu traiectoria b din figura 7.1). Aceast situa ie ar echivala cu o comand n bucl deschis, posibil pentru c s-a

presupus c nu exist evenimente necontrolabile, adic perturba ii.Problema analizat n acest capitol este tocmai aceea a rejectrii efectului perturbaiilor,

adic a evenimentelor necontrolabile, evenimente ce pot determina traiectorii similare cu traiectoriade tip a din figura 7.1, ce exced limbajul admisibil La.

Un supervizor S apare, astfel, ca un compensator, al crui scop este tocmai rejectarea

perturbaiei i, n consecin, pstrarea evoluiei n cadrul La.Un supervizor f are ca obiectiv realiyarea egalitii Lf= La.Evenimentelecontrolabile sunt generate de sistemul de comand (n care supervizorul este

numai o parte). Numai n acest fel exist un control asupra producerii lor. Evenimentelenecontrolabile provin din proces sau din mediul extern lui. Producerea lor nu poate fi mpiedicat desistemul de comand. Poate fi doar prevenit efectul negativ al producerii lor, n sensul dep irii limbajului La.

ntr-o intrare de comand oarecare sunt incluse toate evenimentele necontrolabile i acele evenimente controlabile, care sunt autorizate. Evenimentele necontrolabile sunt totdeaunaautorizate, fiindc nu se poate interveni asupra lor. Pentru evenimentele controlabile , care sunt

autorizate, func ia ia valoarea 1, iar pentru evenimentele controlabile interzise,

19

8/3/2019 SDED

20/26

ia valoarea 0. Astfel, dintr-o stare oarecare, supervizorul filtreaz evenimentele, stabilind careeveniment controlabil trebuie validat i care trebuie interzis, pentru a se asigura respectarea comportamentului admisibil. Supervizorul face parte din structura de conducere a unui SDED, dar nuac ioneaz direct asupra procesului, rolul su fiind doar de a decide care eveniment controlabil

trebuie autorizat i care trebuie interzis. Rolul de a ac iona n sensul decis de supervizor, pentru determinarea evenimentului urmror, revine unui alt subsistem al sistemului de comand.

Figura 7.3 Schema bloc a unui SDED condus prin supervizare

n figura 7.3, se propune o reprezentare a structurii de conducere supervizat a sistemului G.n aceast structur este inclus o realizare a supervizorului, S, precum i un bloc filtrare evenimente. Acest bloc reprezintacea parte din sistemul de comand, care va analiza intrarea decomand , furnizat de realizarea supervizorului i nu va permite producerea evenimentelor controlabile care nu sunt validate de supervizor. Figura 7.3 sugereaz func ionarea n bucl nchis a

procesului cu supervizor. Cele dou sisteme cu evenimente discrete, G i S=(S, ), pot fi cuplate,

conform schemei bloc a unui sistem cu evenimente discrete condus prin supervizare, din Fig. 7.3.

Att realizarea S a supervizorului, ct i sistemul G evolueaz ca urmare a aceluia i ir de evenimente, care poate fi considerat semnal de intrare. Realizarea S a supervizorului interzicedoar, prin intrrile de comandfurnizate, anumite evenimentele controlabile i n felul acesta restric ioneaz func ionarea sistemuluiu G.

APLICA II ALE SDED

Modelarea sistemelor de tip flow-shop

Considerm un sistem flexibil de fabrica ie compus dintr-o mul ime de ma ini M ce trebuie s

produc piese (produse) de diferite tipuri. Fie J mul imea tipurilor de piese. Caracteristica sistemului de tip flow-shop este faptul c toate produsele trec pe la fiecare ma in ntr-o ordine fix. Eventual, unele ma ini pot fi srite de unele tipuri de produse. Sistemul este obligat s produc fiecare tip de pies propor ional cu un factor, pe care l numim factor de produc ie. Pentru a respecta aceast restric ie, se introduce o schem (ordine) periodic de intrare a pieselorastfel nct la sfr itul fiecrei scheme, notat cu I, factorul de produc ie s fie exact realizat.

De exemplu, presupunem c avem de produs trei tipuri de piese (1, 2 i 3) propor ional cu 1, 2 i 3. Secven a de intrare a pieselor va avea perioada |I|=6 i ar putea fi

unde cifrele desemneaz tipuri de piese. O alt schem de intrare ar putea fi

20

8/3/2019 SDED

21/26

Ipotezele simplificatoare considerate n acest paragraf sunt: Numrul de palete este |P|=|I| (P este mul imea paletelor);

Fiecare palet este afectat unei piese din schema de intrare; de exemplu, dac pieseledin schema de mai sus sunt identificate prin 1, 2, 3, 4, 5, 6 i paletele sunt numerotate de la 1 la 6, atunci paleta 1 va purta ntotdeauna piesa 1, , paleta 6 va purtantotdeauna piesa 6;

Piesele trec pe la toate ma inile n ordine fix 1, 2, , |M| (ipoteza de sistem flow-

shop); timpii de prelucrare sunt tmi, m M, i I.

Pentru a modela sistemul de tip flow-shop ca SDED n bucl nchis, identificm urmtoareleelemente definitorii pentru un SDED:

Mul imea de activit i A este mul imea de opera ii necesitate de piesele din secven a de intrare I

Resursele sunt ma inile i piesele din I, i.e. R=M I

Graful (A, U) este graful de preceden ce exprim restric iile ntre opera ii.

Vom desemna o opera ie prin perechea (m,i) cu m M, i I. n aceste condi ii, SDED este definit

prin tripletul (A, B, C) descris mai jos: A este o matrice ptrat de ordin |M|.|P|

B este o matrice dreptunghiular ( , ) ob inut prin concatenarea

liniilor matricilor dreptunghiulare BM i B I de dimensiuni ( )) i respectiv (

, )

C este o matrice dreptunghiular ( ) ob inut prin concatenarea

matricilor dreptunghiulare CM i C I de dimensiuni ( , ) i respectiv (

)

Vom nota cu :

X vectorul de dimensiune al momentelor de timp cele mai devreme de debut

al opera iilor (m,i), m M, i I

U vectorul de dimensiune al momentelor de timp ncepnd de la care

ma inile pot rencepe s lucreze, respectiv paletele disponibile

21

8/3/2019 SDED

22/26

Y vectorul de dimensiune indicnd momentele cele mai devreme cnd

ma inile i paletele sunt eliberate pentru o refolosire ulterioar. n aceste condi ii, sistemul este descris de ecua iile

(3.8)

Pentru a nln ui opera iile asociate unei perioade I din secven a de intrare cu opera iile urmtoare,

vom atribui un indice n fiecrei perioade I i vom considera matricea ptrat K de ordin

ce va lega ie irea Y(n) cu intrarea U(n+1) prin rela ia

U(n+1)= Y(n).Kn cazul sistemului nostru K poate avea form diagonal

n loc de e, am putea avea o valoare determinat, dac sistemul ar impune ni te ntrzierinainte de refolosirea resurselor.Se ob ine sistemul recurent

Y(n+1)=Y(n).K.B.A*.C, cu Y(0)=Y0 dat,care furnizeaz datele cele mai timpurii de eliberare a resurselor.

Analiza unei linii de fabrica ie n func ie de strategia de produc ie

O linie de fabrica ie este un ir ordonat de sta ii de lucru. Distingem linii de fabrica ie deschise, n care ritmul nu este impus de recircularea resurselor i linii de fabrica ie nchise, n care ritmul de lucru este impus i de recircularea resurselor.

Vom considera o linie deschis n care posturile de lucru pot avea structuri complexe. Este

vorba, de fapt, de sta ii multiple. Vom presupune c un post de lucru P i este alctuit din: Un stoc de capaciate Si Un numr de Ni ma ini care pot efectua aceea i opera ie n timpul t i

Numrul total de piese aflate la un moment dat n postul Pi poate fi cel mult Ci= Si + Ni.Vom considera, pentru simplitate, c linia de fabrica ie are numai dou posturi, dar rezultatele

analizei se extind la linii cu un numr oarecare de posturi.Cnd stocul are capacitatea limitat, exist dou strategii de gestionare a produc iei. Conform

primei strategii, numit blocaj dup servire, piesele asupra crora s-au fcut prelucrri rmn pema ini, dac nu mai exist locuri libere n stoc. n cazul celei de-a doua strategii, numit blocaj

nainte de servire, piesele nu sunt acceptate n postul de lucru, dect dac exist loc n stoc.Vom studia regimurile dinamice ale liniei de fabrica ie conduse dup cele dou strategii, regimuri pe care le vom ob ine cu ajutorul algebrei MinMax(, ).

Blocajul dup servire:n figura 4.3, se prezint modelul liniei de fabrica ie reprezentat printr-o RP ordinar, n cazul

blocajului dup servire. Marcajul ini ial C semnific C mrci n locul respectiv.

22

8/3/2019 SDED

23/26

Fig. 4.3 Blocaj dup servire

Ecua iile de stare ata ate SDED sunt:

x1=

x2=

Prin substitu ii repetate i aplicnd teorema 3.1, ob inem:

x2=

Aplicnd proprietatea (4.7)ii. ob inem

Identitatea

(4.30)implic

.

n consecin :

Deci

Remarcm c rspunsul sistemului nu depinde de capacitatea stocului (C 1)

Blocajul nainte de servire:

n figura 4.4, se prezint modelul liniei de fabrica ie reprezentat printr-o RP ordinar, n cazul blocajului nainte de servire.

23

8/3/2019 SDED

24/26

Figura 4.4 Blocaj nainte de servire

Ecua iile de stare sunt:

x1=

x2=

Prin substitu ii repetate ob inem:

x2=

Aplicnd rela ia (4.30), ob inem

.

Deci

Deci

Remarcm faptul c rspunsul sistemului nu depinde, nici n acest caz, de capacitatea stocului.Rezultatul este oarecum surprinztor i arat faptul c rspunsul sistemului este identic cu cel din

cazul blocajului dup servire. Deci, indiferent de strategia utilizat, blocaj nainte de servire sau dupservire, rspunsul liniei este identic.

24

8/3/2019 SDED

25/26

Conducerea supervizat a sta iei de asamblare

Pentru a exemplifica conducerea supervizat, considerm RP-controlat din figura 7.2 ce modeleaz

p sta ie de lucru de asamblare i artm cum se stabile te comportamentul admisibil L a. LimbajulL(G) care modeleaz comportamentul posibil este dat de mul imea prefixelor secven elor de taskuri care duc la asamblarea unui produs:

L(G)= ,

unde I este mul imea tuturor indicilor secven elor posibile de taskuri. Reamintim aici faptul c

este mul imea prefixelor irului s i.

Figura 7.2 Sta ie de asamblare modelat printr-o RP-controlat

Presupunem c se dore te s se asigure asamblarea produsului astfel nct tranzi iile T 1 i T 4 s nu seexecute niciodat paralel (deoarece, spre exemplu, ar exista pericolul coliziunii celor doi robo i ce execut aceste taskuri). Din punctul de vedere al comportamentului posibil, cele dou taskuri ar

putea fi executate n paralel. Restric iile de func ionare cer ns ca acest lucru s nu se ntmple. Declan area taskului T 1 , modelat de tranzi ia T 1 , este un eveniment controlabil prin marcajul locului

de comand Pc1, n timp ce declan area taskului T 4 este un eveniment necontrolabil. Pentru a se

25

8/3/2019 SDED

26/26

asigura comportamentul admisibil, determinat de restric iile de func ionare ale robo ilor, din starea din care ar fi posibil execu ia n paralel a celor dou taskuri, supervizorul va interzice nceperea execu iei taskului T 1, pn la ncheierea taskului T4. n aceste condi ii, limbajul admisibil L a

pstreaz din limbajul posibil L(G), numai acele secven e de tranzi ii care respect restric ia impus

de func ionare a celor doi robo i:

La = ,

unde J este mul imea indiciilor secven elor de taskuri n care T 4 se execut naintea lui T1.

De exemplu secven a T 4T1 ... T12 La. Pentru realizarea efectiv a supervizorului n acest caz se

poate consulta capitolul 10.