7/25/2019 curs 10+11-lfr

1/21

CURS 10+11 LFR

1

EXCLUDEREA MUTUAL PARALEL N LINIILEFLEXIBILE DE PRELUCRARE

Numai dup ce modelele cu reele Petri sunt construite corect pentrusistemele de prelucrare se poate trece la implementarea aplicaiilor. Implementareaaplicaiilor poate converti direct modelul reelei Petri ntr-o secven de program pentru controlul de supervizare a sistemului de prelucrare. Abordarea structural amodelrii unui sistem este foarte important. Mai nti se obine un model de reeaPetri folosind metode de determinare a erorilor de modelarei dup aceea seanalizeaz pentru respectarea proprieti cum ar fi mrginirea, viabilitateaireversibilitatea.

Din moment ce n sistemele de prelucrare de mrime mijlocie complexitatea proiectrii modelelor la nivelul implementrii n detaliu devine aproape iraional,o cerin impetuoas este construirea sistematic a modelului de reea Petri astfelca acesta s aib proprietile dorite pentru un anumit sistem de prelucrare.

Una dintre dificultile majore ale problemei const n metoda tratriiresurselor partajate n sistem. Aceste resurse pot fi roboi, sisteme de transportare a

materialelor, sau centre de prelucrare. Existena resurselor partajate este principalulmotiv pentru care sistemul poate ntmpina interblocri.De exemplu, sistemul de prelucrare simplu introdus n Capitolul 2 poate fi

blocat datorit existenei unui robot partajat. Se poate uor observa c acesta nu va putea fi niciodat blocat f r ca robotul s fie partajat indiferent ct de multe piesesunt prezentei prelucrate.

Un obiectiv al acestui capitol este de a se referi la problema de sintez pentru sistemul cu resurse partajatei s se prezinte o abordare riguroas. Acestcapitol prezint excluderea mutual paralel i rolul ei n sintez. Dou obiective

majore ale acestui capitol sunt:1. Formularea conceptului partajrii resurselor n excluderea mutual paralel

(EMP), n contextul teoriei reelelor Petri folosite n modelarea sistemelor de prelucrare;

2. Studierea condiiilor sub care reelele Petri menin pentru structurilemodelate proprietile : viabilitatea, mrginirea,i reversibilitatea.

Proprietile i teoremele referitoare la proprietile calitative ale reelelorPetri ce conin structuri de excludere mutual paralel, sunt dezvoltateidemonstrate n paragraful 3.3.

Exemplul unei aplicaii de modelare a unui sistem cu doi roboi i dou

7/25/2019 curs 10+11-lfr

2/21

CURS 10+11 LFR

2

};

;

centre de prelucrare este dat n paragraful 3.4.Conceptul excluderii mutuale paralele este generalizat pentru structurile

flexibile de sistem de prelucrare n paragraful 3.5.

3.1. Definiii i exemple

Analiznd funcionarea modelului sistemului pentru exemplul 2.1, putemobserva urmtoarele proprieti:

1. Cnd poziia resursei partajate pR01 nu este considerat, sistemul coninedou procese independente, fiecare dintre ele putnd fi repetat la infinit;i

2. Cnd resursa partajat este considerat, dou procese nu pot fi executatesimultan. Ambele sunt gata de a fi executate n starea iniial, i fiecare poate fi executat dup ce procesul de derulare este complet.

Observaiile i studiul asupra exemplului de mai sus motiveaz definireaurmtorului concept de excludere mutual paralel. n definiie, termenuli al procesuluik este modelat ca o pereche de tranziii (tai, t bi), i resursa partajat estemodelat ca o poziie pE. n exemplul 2.1, k = 2, (to01, to03) i (to02, to04) modeleaz dou procese,i pE = pR01.

Defini ia 3.1 Se d o reea Petri marcat Z = (P, T, I, O, m 0), P = P O P R P V P I

o k-excludere paralel mutual este definit ca, k-EMP=(pE, D) astfel nct:

1. pE PR cu m0(pE) = 1, D este un set de perechi de tranziii sauD = (ta1, t b1), (ta2, t b2), , (tak , t bk ), k 1,satisf cnd:

(a) tai, t bi T, tai t bj, tai taj, i t bi t bj cnd i j, i, j Nk unde Nk este mulimea indicilor tranziiilor excluderii mutuale de ordin k;

(b) I(pE, tai) = O(pE, t bi) = 1, I(pE, t bi) = O(pE, tai) = 0 cnd t bi tai, I Nk ; I(pE, tu) = O(pE, tu) = 0 cnd tu Ta T b, unde Ta = {tai, i Nk }, i T b = {t bi, i Nk

(c) i Nk , p PV, dac p CE(tai), t bi CE(tai);

(d) CE(tai), dac CE(tai) (PR PV) = {pE}, t bi CE(tai); i(e) dac t DE(tai, t bi), t este pe un O-drum al drumului elementarEP(tai, t bi);

2. PR PV satisface prezumiile 2.1i 2.2 i nu exist nici un O-drum ntret i t', t T b, t' Ta

3. m0, i o secven de tranziii executabileg ce nu conine nici o tranziien Ta, a.. m0[g face admisibil pe t, t Ta; i

4. m0, dac taj se execut la m R(Z, m0), atunci t, dac DE(taj, t) 0 it bj DE(taj, t), t poate fi admisibil i g j executabil neconinnd t bj,h j, a.. m[tajg jh j face admisibil t bj, dac m(pE) = 1 i dac tu este

admisibil, tu T, atunci tu T b.

7/25/2019 curs 10+11-lfr

3/21

CURS 10+11 LFR

3

= t bi.

O structur k-EMP caracterizeaz o resurs partajat de k-procese. Fiecare proces, care poate fi foarte complicat, este abstractizati exprimat ca o pereche detranziii ntre care ar putea exista o subreea complicat. Pentru convenien, D esteconsiderat a fi un set al tuturor tranziiilor din reuniunea Ta T b.De aceea, tu D nseamn tu Ta T b.

Condiiile 1 i 2 din aceast definiie definesc structura excluderii mutualentr-o reea Petri, denumit structur EMP . Condiiile 3i 4 definesc comportareadezvoltat de excluderea mutual paralel prin dependena fa de clasificarea poziiilor.

O explicaie detaliat a condiiilor 1 4 este:

Condi ia 1: (a) Toate tranziiile nD ar trebui s fie diferite cu excepia tai i t bi. Astfel tai

poate fi egal cu t bi. Practic, este posibili un exemplu poate fi cel

raportat la un model de reea Petri pentru un sistem-dubl-prelucrare.Totui, vom exclude un astfel de caz n discuia ce urmeaz din momentce existena perechii (tai, t bi) nu afecteaz proprietile reelelor Petricnd tai

(b) Exist cte un arc de intrare din pE ctre fiecare tai i un arc de ieire dint bi ctre pE pentru 1 i k dar nici un alt arc corespunztor lui pE.

(c) Orice circuit elementar dintre tai i o poziie PV trebuie s conin t bi

pentru 1 i k. Aceasta mpreun cu (b) implic faptul c dup ce tai seexecut i se finalizeaz, resursa partajat precumi resursele generatedin resursele variabile, adic, V-poziiile, vor fi eliberate numai dup execuia tranziiei t bi.

(d) Orice circuit elementar avnd tai i poziia resursei partajate pE, dar nici oalt R-poziie i nici o V-poziie, trebuie s includ t bi pentru 1 i k; i

(e) Orice tranziie pe un drum elementar ntre tai i t bi ar trebui s fie pe un

O-drum ntre tai i t bi pentru 1 i k. Aceasta garanteaz c grupurileconcurente ale proceselor operaionale n sistem s fie succesive.

Condi ia 2: Cere ca toate resursele s fie bine modelate n sensul n caretoate poziiile resurselor satisfac prezumia 2.1 care specific c dac o poziia resursei nu a fost iniial marcat atunci tranziia ei de ieire nu va fiexecutat niciodat. Prezumia 2.1 implic de asemenea c orice resurse alecror stri sunt modelate ca poziii diferite nu pot fi convertite din una ncealalt. n plus, prezumia 2.2 asigur c jetoanele pentru resurse diferite caroboi i maini nu pot fi grupate mpreun. Condiia 2 cere, de asemenea,s nu existe relaii secveniale ntre celek procese.

7/25/2019 curs 10+11-lfr

4/21

CURS 10+11 LFR

4

t.

al.

Condi ia 3: Garanteaz oportunitatea egal pentru fiecare proces s-iating scopul folosind resursa.

Condi ia 4: Garanteaz folosireai eliberarea corect a resursei partajate n procesul de prelucrare. De asemenea asigur c orice tranziie t ce n

execuie necesit taj poate fi admisibil dup ce taj se execut, unde 1 j ki c exist o secven de tranziii h j care determin ca t bj s fie admisibil iar dup executarea lui t bj s elibereze resursa partaja

Exemplul 3.1 : n reeaua Petri din figura 2.2, (pR01, {(to01, to03), (to02, to04)})

este o excludere 2-EMP cnd PO = {po01, po02}, PR = {pR01}i PV = {pV01, pV02}.Oricum, cnd PO = {po01, po02}, PR = {pR01, pV02}, i PV = {pV01} i m0(pV02) = 0,(pR01, (to01, to03), (to02, to04)) nu este o structur 2-EMP conform definiiei de maisus deoarece nu poate satisface condiia 3. Dac dou arce (pR01, to02) i (to04, pR01)

sunt eliminate, (pR01, {(to01, to03)}) constituie o structur 1-EMP, care se constituientr-un caz ban 1-excluderea mutual paralel (pE, {(ta, t b)}) reprezint o poziie ce

modeleaz disponibilitatea unei singure resursei 2 tranziii ce modeleaz nceputul respectiv sfr itul unei operaii. n figura 3.1,a se reprezint 1-EPMsimpl i resursa partajat notat cu PR01-pE, tranziia TO99 nceputul operaiei PO88 i tranziia TO98 sfr itul operaiei PO88. In figura 3.1, b aceeai resurs estenecesar executrii operaiilor corespunztoare subreelei ce are tranziiile denceputi sfr it TO99 i TO98 respectiv.

Generalizare a unei k-EMP prin includerea de subreele ntre tai i t bi poatefi f cut prin extinderea (tai, t bi) n D ctre (Tai, T bi) unde ambele Tai i T bi suntsubseturi ale luiT corespunztoare subreelelor.

3.2. Conservarea proprietilor la introducerea unei k-EMP

Prin includerea n modelul unui sistem de prelucrare a unei k-EMP trebuieverificat pstrarea proprietilor de comportament cum ar fi mrginirea sausigurana, viabilitateai reversibilitatea. In continuare am s definesc i am s demonstrez dou leme ajuttoare la demonstrarea teoremelor de pstrare a proprietilor de comportament prin introducerea unei k-EMP.

Lema 3.1 Se presupune c exist o k-EMP (p E , D) unde D = {(t ai , t bi ), i N k } n re eaua Petri Z' = (PO (PR {pE}) PV PI T', I', O', m0'). Dac

exist o secven de tranzi ii f necon innd nici o t bi , a.. t ai ft bi s fie executabil din m R(Z', m 0 '), atunci f nu con ine nici o t aj , j N k , i i N k , i j.

Demonstra ie: Din condiia 4 din definiia unei k-EMP, execuia lui tai implic faptul c unicul jeton din pE este eliminati de aceea, nici o tranziie t cuI(pE, t) = 1 nu poate fi admisibil f r execuia tranziiei t bi, i Nk . Aceasta arat

7/25/2019 curs 10+11-lfr

5/21

CURS 10+11 LFR

c taj nu se poate executa, pentru j Nk . De aceea,f nu conine nici un taj, j Nk .

5

PO99

0 0

_

PV99 0

0

_

PI99

0 0

_

PO88 0

0

_

PO98 0

0

_

PV98 0

0

_

PI98 0

0

_

PR01PO99PV99PI99

1

PO88 _TO99

PO88PI98

1

PR01PO98PV98 _

TO98

PR01 1

0

PE

a)

PO99 0

0

_

PV99 0

0

_

PI99 0

0

_

PO98 0

0

_

PV98 0

0

_

PI98 0

0

_

PR01 1

0

PE

PO88PI98

1

PR01PO98PV98 _TO98

PR01PO99PV99PI99

1

PO88 _TO99

b)

Figura 3.1: Exemple de 1-excludere mutual paralel, (a) cazul generali(b) un caz simplu

Aceast lem stabilete faptul c dac resursa partajat este ocupat de un proces de prelucrare, atunci nu poate fi folosit de un alt proces de prelucrare pn cnd nu este eliberat de cellalt proces.

Lema 3.2 p E este o pozi ie sigur n Z'.

Demonstra ie: Conform condiiei 4 din definiia 3.1, nici o tranziie n T b,nu poate fi admisibil cnd m(pE) = 1. Aceasta asigur c m(pE) 1 pentru oricemarcare m n Z'. De aceea, pE este o poziie sigur .

Teoremele urmtoare demonstreaz faptul c sistemul i menine proprietile calitative, dac conine mai multe procese de prelucrare independentecu proprietile calitative ndeplinite care trebuie s concure pentru a partaja o

resurs cu oportuniti egale, elibernd resursa dup ce fiecare proces a dobndit-oi a folosit-o.Urmtoarele prezumii sunt f cute pentru teoremele de la 3.1 la 3.3

7/25/2019 curs 10+11-lfr

6/21

CURS 10+11 LFR

referitoare la o reea Petri ce este extins cu excludere excludere mutual paralel :

6

1. Fie Z' = (P', T', I', O', m0') reeaua extins cu EMP, cu P' = PO (PR {pE}) PV PI iT' = T, Z = (PO PR PV PI ,T, I, O, m0) este o sub reea a lui Z',adic p P, t T, I(p, t) = I(p, t'), O(p, t) = O'(p, t),i m0(p) = m0'(p).

2. (pE, D) este o k-EMP a lui Z' unde D = {(tai, t bi), i Nk }, k 0. Teorema 3.1 Z este limitat (sigur ) dac Z este limitat (sigur ).

Demonstra ie: Dac Zk reprezint reeaua Petri marcat cu o k-EMP (pE,Dk ),i R(Zk ,m0) setul marcrilor realizabile ale lui Zk plecnd de la marcarea iniial

m0. Se presupune c m(pE) este ultimul element al oricrei marcri m R(Zk ,m0).

Se poate scrie:

)('

E pmm

ca m = ( m(pE) )

O secven de tranziii executabile este notat f , g, sau h, iar notaia m[f>nseamn c f este aplicat marcrii m.

Se definete Q(Zk , m0) = { : ( , m(pE)) R(Zk , m0)} care este un set devectori.

Dac m (Zk , m0), h, a.. m0[h> m, a.., (m0,1)[h> ( , m(pE)). Dinmoment ceh poate fi aplicat reelei Z, atunci m0[h> . Din faptul c R(Z, m0) estemrginit potrivit presupunerii, reiese c i este mrginit. m(pE) este sigur folosind lema 3.2. R(Zk , m0) este mrginit. Deci Zk este mrginit dac Z estemrginit. Similar, concluzia poate fi demonstrat i n cazul siguranei.

Teorema 3.2 Z este viabil dac Z este viabil .

Demonstra ie: Notaia Zk are aceeai semnificaie ca la teorema 3.1.Demonstraia este bazat pe inducia dup k .

Mai nti, pentru k = 1; acest caz semnific adugarea unei singure poziii pE care este iniial marcat cu un singur jeton,i are doar dou arce ctre dou diferitetranziii ta1 i t b1, a.., m0(pE) = 1,i I(pE, ta1) = O(pE, t b1) = 1. Pentru t T, m R(Z1, m0), trebuie s demonstr m c exist o secven de tranziii prin a creiexecuie t devine admisibil. Dac m(pE) = 1 atunci avem m = (,1). Presupunereac m(pE) = 0, ceea ce implic faptul c numrul execuiilor ta1 este mai mare cu o

7/25/2019 curs 10+11-lfr

7/21

CURS 10+11 LFR

7

).

:

g

g

execuie dect t b1. Din moment ce (pE , {(ta1, t b1)}) este o 1-EMP, atunci exist osecven de tranziii ce face admisibil pe t b1. Execuia acestei secvene plus t b1 conduce marcarea ctre m cu m(pE) = 1. Fie m = (, 1) unde R(Z, m0) potrivit demonstraiei teoremei 3.1.

Pentru i t n Z, sunt dou cazuri: DE(ta1,t) 0 sau DE(ta1, t) = 0.

Pentru DE(ta1,t) 0, din moment ceZ este viabil potrivit presupunerii,gcare nu conine nici o ta1 n Z, a.. [g> care face admisibil pe ta1. Motivul pentru careg nu conine nici o ta1 este acela c nainte ca ta1 s se execute dinm,trebuie s fie admisibil. Acestg se poate executa n Z1 n mod evident, ceea ceimplic faptul c m[g> m face pe ta1 admisibil. n m, t poate fi admisibil conform condiiei 4 din definiia 3.1 a EMP dac t b1 DE(ta1, t). Altfel, dinmoment ce t b1 DE(ta1, t), O-drumurile DE(t b1, t) 0. n Z, h, a.. [g> careface pe t admisibil. Aa cum h poate fi evident ordonat astfel nct fiecareexecuie ta1 este urmat de o execuie t b1. De aceea,h este executabil i face t admisibil n Z

1. Aceasta demonstreaz primul caz.Pentru cazul unde DE(ta1, t) = 0, viabilitatea luiZ implic faptul c g, a..

[g> care facet admisibil. g poate evident fi aleas s nu conin nici o ta1. Deaceea, aceasta este executabil n Z1 i face pe t admisibil. Aceasta acoper demonstraia cazului pentru k=1.

n a doua etap, presupunem c pentru k n, concluziile sunt adevrate. ncele ce urmeaz vom ar ta c sunt adevrate i pentru k = n + 1.

Presupunem c (pE , D(n+1)) = (pE , D(n) (ta, t b)) este o (n+1)-EMP. Avemde ar tat c t poate fi admisibil, pentru t T, m R(Zn+1, m0

Dup presupunerea din inducie, g n Zn, a.. m[g> sau (,1)[g> faceadmisibil t.

Urmtoarea demonstraie se focalizeaz pe primul caz. Sunt trei subcazuri,A, B,i C, demonstraiile pentru fiecare n parte sunt prezentate mai jos:

Cazul A : Dac g nu conine nici ta, t b, nici tranziiile pe orice drumurielementare ntre ta i t b, atunci este executabil n Zn+1. De aceea, m[g> facet admisibil n Zn+1.

Cazul B : Dac m(pE) = 1 i g conine ta o dat sau de mai multe ori, atunciavem de ar tat c g, a.. m[g> facet admisibil n Zn+1. Pentru c (pE, D(n+1))este i (n+1)-EMP,g poate fi ordonat n una din urmtoarele dou forme f r s se schimbe marcarea rezultat

1taf 1t bg2taf 2t btaf vt bgv+1, v 1sau

1taf 1t bg2taf 2t bgvtaf v, v 1

unde f i i gi nu conin nici ta nici t b. gi nu conine nici o tranziie n DE(ta, t b).

7/25/2019 curs 10+11-lfr

8/21

CURS 10+11 LFR

8

g

i n.

re mpiedic te executabil n Zn.

P, i t,t T,ac ambele tti tt la R(Zn, m0) sunt executabile, atunci

(p)[tt> = (p) I(p, t) + O(p, t) I(p, t) + O(p, t)i(p)[tt> = (p) I(p, t) + O(p, t) I(p, t) + O(p, t)

Astfel(p)[tt> = (p)[tt>

executabilei constau dincelea vedete a fi adevrat.

Similar, putem ar ta c:

m(p)[tahitajr it beit bj> = m(p)[tahIr It btajeIt bj>, p P.

n g care se poatexecutai g(m) face admisibil pe t n Zn+1.

B.2 Se consider g = g1taf 1t bg2taf 2t bgvtaf v,v 1

poate fi obinut din g, care se poate executai m[g> face admisibil pe t n Zn+1.

B.1 Se consider prima form

= g1taf 1t bg2taf 2t btaf vt bgv+1,v 1

Folosind lema 3.2 a n-EMP n Zn, gi conine cel mult un element al lui Ta =

{tai, i Nn}, s spunem taj, f r urmtoarea tranziie a lui t bj. Dac ar fi, deexemplu, tajhit bj n gi, atunci tajhit bj poate fi aplicat n Zn+1 unde hi nu conine nicio tranziie n Ta, i Nv+1. De aceea presupunem c, pentru i Nv, gi = tajhi i f i = r it bjei f r pierderea generalitii, i wi = gitaf it b = tajhitar it bjeit b n g, a.. wI cenu se poate executa n Zn+1. Vom demonstra c w1 = tajhir it bjtaeit b se poateexecutai marcarea rezultat este aceeai cu cea rezultat n urma executrii w

nZ

a. wi este executabil n Zn (demonstrez inexistena ipotezei contrare).

Dac wi nu se poate executa n Zn

, aceasta implic faptul c exist otranziie, s spunem t n r it bj a crei execuii necesit executarea ambelortranziii taj i t bj. Aceasta ar putea fi adevrat/posibil n Zn+1. Oricum, (pE ,D(n+1)) este o (n+1)-EMPi D(n+1) = D(n) {(ta , t b)} caexistena unei astfel de tranziii t. De aceea, w1 esb. (p)[wi> = (p)[wI>, p P, R(Zn, m0).Urmnd regula de execuie a unei reele Petri marcat, p d

Din moment ce ambele secvene wi i wi sunt

a i tranziii, concluzia se do

Folosind tehnica dezvoltat mai sus,g poate fi convertite

forma a doua

Folosind tehnica anterioar , g

7/25/2019 curs 10+11-lfr

9/21

CURS 10+11 LFR

9

[g> face admisibil pe t n Zn+1. n concluzie, orice tranziie t Zn+1 este viabil.

Teorema 3.3 Z este reversibil dac Z este reversibil . lar cu cea pentru teorema 3.2i este

tor ca cel pentruviabilitii lui Zn+1, concluzia poate fi demonstrat.

dac el exist. Unexemplu n acest sens va fi ar tat n paragraful urmtor.

e Mutual Paralel), etc. pn cnd resursa partajat este

prelucrare din paragraful urmtor va ilustraaceast procedur de sintez.

Exemplul aplicativ 3.2

Descrierea sistemului

de prelucrare: CP1 i CP2 . Specificaia

crare,

dreapta, solicit

rare, nu poate ficrare.

Cazul C : Dac m(pE) = 0 i g conine ta i tranziiile pe drumurile dintre ta i t b o dat sau de mai multe ori executabile, similar, putem ar ta c g poate figsit astfel nct mn

Demonstra ie: Demonstraia este simide asemenea construit prin inducia dup k .

m R(Zn+1,m0), trebuie s ar tm c g n Zn+1, a.. m[g> m0. Dinmoment ce oricrui m R(Zn,m0) sau ( , 1) R(Zn, m0), g n Zn a.. oricruim[g> m0 sau ( , 1) [g> m0 . Folosind un raionament asemndemonstrarea

Remarca 1 . Teoremele se verific pentru cazurile multi-resurs n sensul ncare condiiile din teorem se verific pentru adugarea unei structuri deexcludere mutual n cadrul reelei. n multe cazuri, dac se descoper situaia n care condiiile oricrei EMP sunt nesatisf cute pentru o reeaPetri specific, atunci un blocaj poate fi gsit uor

Remarca 2 . Demonstrarea teoremelor sugereaz o metod pentru sintezamodelelor cu reele Petri pentru sisteme de prelucrare cu resurse partajate

prin adugarea n trepte a arcelor, unei resurse partajate. Se poate ncepe cuo 1-EMP, apoi se adaug o pereche de arce ctre 1-EMP pentru a forma o 2-EMP(a 2-a Excluder complet modelat.Cnd sunt mai multe resurse partajate se pot aduga structurile de excluderemutual una cte una ntr-o manier sistematic. Exemplul cu sistemul dindoi roboi i dou centre de

a. Sistemul flexibil de prelucrare robotizat din figura 3.2 const din doi roboi

de manipulare: R 1 i R 2 i dou centrefuncionrii sistemului este urmtoarea:

1. Cnd oricare din CP1 i CP2 este gata s execute sarcina de preluaceasta solicit robotul din dreaptai l ocup dac este disponibil.

2. Dup ce centrul de prelucrare achiziioneaz robotul din

robotul din stngai l ocup dac acesta este disponibil.3. Cnd centrul de prelucrare demareaz procesul de prelucntrerupt pn cnd nu se ncheie procesul de prelu

7/25/2019 curs 10+11-lfr

10/21

CURS 10+11 LFR

10

, elibereaz ambii roboi.. Proiectarea modelului

logia prezentat n Capitolul 2. Paii sunt

ezbtui pe scurt n cele ce urmeaz:ocuparea

robotului din dreapta, ocuparea robotului din stngai prelucrarea.

de acesta. Aceeaisituaie pentru po04 , po05 i po06 corespunztoare lui CP2.

e eliberndtoate resursele CP1, R 1, R 2. In mod similar se modeleaz si activitile

4. arcarea iniial este (1, 0, 0, 0, 1, 0, 0, 0, 1, 1)T ceea ce nseamn c

5. Semnificaia poziiilor ce d interpretarea reelei din figura 3.3 este.1.

dup execuia lui to01 i to05 sau to05 i to01 din m0. Metoda de proiectare propus sugereaz faptul c trebuie s se considere resursele partajate

4. Cnd CP1 (CP2) terminb Pentru sistemul din figura 3.2, modelul de reea Petri corespunztor poate fi

cu uurin proiectat folosind metodo

d 1. Pentru ambele centre de prelucrare activitile cerute sunt:

2. Conform prezentrii din figura 3.3, poziiile po01 , po02 i po03 sunt create pentru CP1 i reprezint cele trei activiti efectuate

3. Deplasarea robotului R 1 la centrul de prelucrare CP1, modelat n poziiaoperaional po01, necesit s fie disponibil CP1 modelat prin pR01 i R 1 modelat prin pR03. Fiecare dintre aceste ultime poziii resurs are cte un arcde intrare ctre tranziia to01 care reprezint nceputul operaiei po01.Tranziia to02 reprezint sfr itul operaiei de deplasare a robotului R 1 inceputul deplasrii robotului R 2 la CP1, operaie modelat prin po02.Aceast operaie ncepe numai dac robotul R 2 este disponibil, condiiemodelat de poziia pR04. Tranziia to03 reprezint sfr itul deplasriirobotului R 2 la CP1 i nceputul prelucr rii de ctre CP1. Tranziia to04reprezint sfr itul operaiei de prelucrare pe CP1, dup executar

corespunztoare lui CP2.

Mresursele sunt disponibile CP1, CP2, R 1, R 2.

prezentat n tabelul 3

c. Analiza modelului

Cele dou structuri de excludere mutual paralel ale reelei din figura 3.3sunt: (pR03, {(to01, to04), (to06, to08)}) i (pR04,{(to02, to04), (to05, to08)}). Fiecare vaforma o 2-EMP f r alt structur din reea. Totui, nici una din ele nu este o 2-EMP deoarece nici una nu satisface condiia 4 din definiia 3.1. Marcarea iniial este m0 = (1, 0, 0, 0, 1, 0, 0, 0, 1, 1)T n analiza EMP nu vom lua n considerare poziiile de comand PC. Ambele tranziii to01 i to05 sunt admisibile. Totui, to02 nuse poate executa dup ce to01 i to05 se execut. De fapt, sistemul poate fi

interblocat; nici un proces nu poate demara cnd marcarea (0, 1, 0, 0, 0, 1, 0, 0, 0,0)T este atins

7/25/2019 curs 10+11-lfr

11/21

CURS 10+11 LFR

11

na cte una.u

Robotul 2

Robotul 1

Centrul de prelucrare 1

Centrul de prelucrare 2

Figura 3.2: Planul general al unui sistem de prelucrare de tipul doi-roboi idou-centre de prelucrare

PC01 1

_

0

PO01 0

DR1CP1

0

PO02 0

DR2CP1

0

PO03 0

CP1L

0

PR03

1

R1A

0

PR01 1

CP1A

0

PR04 1

R2A

0

PC51 0

_

0

PC02 1

_

0

PO04 0

DR2CP2

0

PO05 0

DR1CP2

0 PR02 1

CP2A

0

PO06 0

CP2L

0

PC52 0

_

0

PO02

1

PO03 _

TO03

PO03

PR01PC51PR0 03 _

TO0414PR

PR04PC02

1

PO04 _

TO05PR02

PR03PO0

PO05 _

TO064

1

PO05

PO06 _

TO071

PO06

1

PR03PR04PC52P 02 _

TO08

PR01PC

PO01 _

TO0101PR03

1

PO01PR

PO02 _

TO0204

1

R

7/25/2019 curs 10+11-lfr

12/21

CURS 10+11 LFR

12

Figura 3.3: Modelul de reea Petri pentru sistemul din exemplul 3.2

Tabelul 3.1. Sem ificaia poziiilor

P Sem iepr

n

oziii nificaescurtat

Semnificaiedetaliat

pR01 CP1A Centrul de Prelucrare 1 (CP1) disponibil (A) po01 D CP1R 1CP1 Deplasare Robot 1 la po02 D t 2 la CP1 R 2CP1 Deplasare Robo po03 CP1P CP1 prelucreaz (P) pR02 CP2A CP2 disponibil

po04 D 2 la CP2 R 2CP2 Deplasare Robot po05 D 2 a CP2 R 1CP Deplasare Robot 1 l po06 CP2P CP2 prelucreaz pR03 R 1A Robot 1 disponibil pR04 R 2A Robot 2 disponibil

Astfel figura 3.4 este obinut dup ce se introduce resursa reprezentat de

il. Astfel se obine reeaua prezentat figura 3.5 dup ce i excluderea (pR04, {(to01, to04), (to05, to08)}) este introdus. n

1, 0, 0, 0,1, 0, 0

Dac t 5 se execut, to06, to07, i to08 sunt singurele secvene executabile.

Din moment ce reeaua din figura 3.3 este sigur , viabil, i reversibil,

robotul R 1, excluderea (pR03, {(to01, to04), (to06, to08)}) este uor de verificat a fi o 2-

EMP. Cum s-a menionat anterior, excluderea (pR04, {(to02, to04), (to05, to08)}) cndeste adugat conform specificaiei de funcionare a sistemului, nu este o 2-EMP.Trebuie ca specificaia sistemului s fie corect pentru proiectarea unui sistemf r interblocare. Dac modificm specificaia astfel: centrul de prelucrare 1solicit ambii roboi n acelai timp cu alte cuvinte, deplasarea robotului R 1 vancepe numai dac i robotul R 2 este disponibncontinuare voi ar ta c aceasta este o 2-EMP

Notnd cu PO = {po01, po02, po03, po04, po05, po06}, PR01 = {p1, pR02, pR03, pR04}, i PV = , o structur poate cu uurin verifica condiiile 1 i 2. Pentrucondiia 3, marcarea iniial determin s fie admisibile tranziiile to01 i to05.Pentru condiia 4, din moment ce PV = , trebuie s consider m m0 = (

, 0, 1, 1)T. Dac to01 se execut, atunci to02, to03, i to04 sunt singurele secvenece se pot executa.

o0Astfel condiia 4 este adevrat. Din acest motiv, (pR04, {(to01, to04), (to05,

to08)}) este o 2-EMP.

7/25/2019 curs 10+11-lfr

13/21

CURS 10+11 LFR

13

atunci i reeaua din figura 3.4 este de asemenea sigur , viabil, i reversibil conform teoremelor 3.1 - 3.3.

PC01 1

_

0

PO01 0

DR1CP1

0

PO02 0

DR2CP1

0

PO03 0

CP1L

0

PR03 1

R1A

0PR01 1

CP1A

0

PC51 0

_

0

PC02 1

_

0

PO04 0

DR2CP2

0

PO05 0

DR1CP2

0 PR02 1

CP2A

0

PO06 0

CP2L

0

PC52 0

_

0

PO02

1

PO03 _TO03

PR03PO04

PO05 _

061 TO

PO05

PO06 _TO071

PR01PC0

PO01 _TO01

1PR03

1

PO01

PO02 _TO021

PO03

PR01PC51PR0 _TO041

3

PO06

1

PR03PC52PR02 _TO08

PC02PR02

1

PO04 _

05TO

Figura 3.4:Modelul cu reea Petri cnd este considerat doar R 1

PC01 1

_

0

PO01 0

DR1CP1

0

PO02 0

DR2CP1

0

PO03 0

CP1L

0

PR03 1

R1A

0

PR01 1

CP1A

0

PR04 1

R2A

0

PC51 0

_

0

PC02 1

_

0

PO04 0

DR2CP2

0

PO05 0

DR1CP2

0 PR02 1

CP2A

0

PO06 0

CP2L

0

PC52 0

_

0

PO02

1

PO03 _

TO03

PO03

PR01PC51PR 03 _

TO04104PR

PR04PC02P

1

PO04 _

TO05R02

PR03PO0

PO05 _

064

1 TO

PO05

PO06 _

TO071

PO06

1

PR03PR04PC52 _

TO08PR02

PO01

PO02 _

TO021

PR01PC

PO01 _

TO0101PR04PR03

1

7/25/2019 curs 10+11-lfr

14/21

CURS 10+11 LFR

14

el este luat n calcul, aceasta nu poate

fie modificat f r a avea nici o interblocare. Aceasta implic faptul c specificaia sistemului trebuie s fie schimbat aa cum s-a f cut n exemplul demai sus.

Figura 3.5: Modelul de reea Petri 2-EMP viabil

Lund n considerare discuia despre modelarea cu reele Petri a sistemuluide prelucrare precedent, cteva observaii interesante pot fi f cute. Folosireaacestei teorii asigur reelelor Petri intermediare sigurana contra interblocrilor,

prin adugarea unei excluderi mutuale paralele pentru robotul R 1. Totui, cnd adoua structur de excludere mutual paralconstitui o excludere mutual paralel. Aceasta implic de fapt o interblocare pentrumodelul de reea Petri ar tat n figura 3.3.

Dou posibile strategii decurg din acestea: prima metod este de a adugaultima resurs partajat pentru a forma o excludere mutual paralel astfel nctsistemul s

PC01 1

_ PC02 1

_

0 0

PO01 0

DR1CP1

0

PO02 0

DR2CP1

0

PO03 0

CP1L

0

PR01 1

CP1A

0

PC51 0

_

0

PC52 0

_

0

PO04 0

DR2CP2

0

PO05 0

DR1CP2

0

PO06 0

CP2L

0

PR03 1

R1A

0

PR04 1

R2A

0

PR02 1

CP2A

0

PR01PC

1

PO01 _TO01

01PR03

PO01PR

1

PO02 _TO02

04

PO021

PO03 _TO03

PO03

1

PR01PC51PR04PR03 _TO04

PR04PC02

1

PO04 _TO05

PR02

PR03PO0

1

PO05 _

TO064

PO051

PO06 _TO07

PO06

1

PR03PR04PC52PR02 _TO08

PC52

1

PC01 _TI02

PC51

1

PC02 _

TI01

or. Un exemplu simplu desecven de control a acestui controler este prezentat n figura 3.6. Secvena de

lrii cu

Figura 3.6: Modelul de reea Petri cu secven

a de control

A doua metod este s construim modelul de reea n mod corect deiexcluderile mutuale paralele anterioare ar putea fi degradate n excluderi mutualenon-paralele. n acest caz alte metode de evitare a interblocrii trebuie folosite pentru prevenirea acestor interblocri nglobate. Astfel, cu ajutorul poziiilor decontrol pC01, pC02, pC51 i pC52 se pot ordonana activitile celulelor de prelucrareCP1 i CP2 la nivelul unui controler ierarhic superi

control cuprinde poziiile pC01, pC02, pC51, pC52, tI01, tI02.

n concluzie, rezultatele exemplului ar tat ofer o nelegere a mode

7/25/2019 curs 10+11-lfr

15/21

CURS 10+11 LFR

15

c oate diminua considerabil costul de proiectare pentru sistemele distribuite cu

e devin foarte complicate.

a mutual paralel flexibil

edent unde robotul este o resurs partajat. Aadar, este necesar s segeneralizeze aceste idei n vederea implementrii tehnologiilor flexibile de preluc

Z = (P, T, I, O, m0), P = PO PR PV PI, oxcludere mutual paralel k-flexibil, notat cu k-EMPF=(PE, D) este

1. PE PR cu m0(PE) = 1, D este un set de perechi de tranziii sau D = (Ta1,

0 cnd t Ta, t T b, unde Ta = Ta1

p PV, dac p CE(t), atunci t T bi, a.. t CE(t);

) dac t DE(t, t), t, atunci t este pe un O-drum DE(tai unde t

. PR PV satisface prezumiile 2.1i 2.2 i nu exist nici un O-drum ntret

reele Petri pentru sistemele de proiectare distribuite ce conin interblocri. Unavantaj al acestei metode const n faptul c potenialele interblocri pot fidetectate pe parcursul procesului de modelare. n plus, aceast detectare apriori presurse-partajate n-timp-real, n special cnd sistemel

3.3. Excludere

3.3.1 Definiie

Excluderea mutual paralel poate fi folosit pentru a rezolva probleme desintez unde resursa partajat se mparte ntre operaii f r alternativ. Acesteconcepte pot fi extinse ctre cazul n careopera iile alternative ar putea exista pentru a genera flexibilitate. De exemplu, un robot poate avea sarcina de a

transporta piesele ntre maina 1 i mainile 2 sau 3. Cnd se obine o pies prelucrat de la maina 1, robotul poate ncrca piesa ori pe maina 2 ori pe maina3 amndou avnd posibilitatea de a executa urmtoarea operaie a procesuluitehnologic. Structura de excludere mutual paralel prezentat nu poate descriesituaia prec

rare.

Defini ia 3.2 EMPFExcludere Mutual Paralel Flexibil

Fiind dat o reea Petriedefinit de condiiile:

T b1), (Ta2, T b2), , (Tak , T bk ), k 1, satisf cnd:

(a) Tai, T bi T, Tai T bj = 0i Tai Taj sau T bi T bj cndi j, i, j Nk ;(b) I(pE, t) = O(pE, t) = 1, I(pE, t) = O(pE, t) =

T b, i I(pE, tu) = O(pE, tu) = 0 cnd tu Ta Ta2 Tak i T b = T b1 T b2 T bk ;

(c) t Tai i t T bi, O-drumul DE(t, t) 0;(d) t Tai,(e) t Tai, dac CE(t) (PR PV) = pE, atunci t T bi, a.. t

EC(t);i(f

Tai, t T b), i Nk ;2

7/25/2019 curs 10+11-lfr

16/21

CURS 10+11 LFR

16

tru un grup de tranziii {r a1, r a2, , r a3} unde r ai Tai, g ce nuconine nici o tranziie n Ta {r ai, i Nk }, a.. m0[g> face admisibil r ai, i

g j executabil neconinndtranziii n T bj, h j i r T bj, a.. m[rg jh j> face admisibil t; i dac m(pE)

adiionali astfel: Taj = numrul detranziii de nceput a excluderilor; T bj = numrul tranziiilor de sfr it a

ubcapitolul 3.1.- Cnd T 2, T 2, i N , se pot distinge mai multe cazuri, ca

. Subreelele din figurile 3.6(b), 3.7(b), 3.8, 3.9 pot fi folosite laconstituirea EMPF-urilor ndeplinind condiiile ce dau proprietile decompo

ici to02. Structurile RP din figurile 3.6(b)i 3.7(b)

pot fi folosite pentru constituirea 1-EMPFdate de (p , {(t , {t , t })}),i,respec

ate verifica excluderile (pR01, ({to02, +to03}{t 4, to05})), (pR01, ({to01, to02}, {to03, to04})) n fiecare dintre reele, excluderee satisface condiiile din definiia de mai sus.

i t, t T b, t Ta

3. m0, pen

Nk ; i

4. m0, dac r Taj se execut la m R(Z, m0), atunci t, dac DE(r, t) 0i T bj DE(r,t) = 0, t poate fi admisibil i

= 1 i tu este admisibil tu T, atunci tu T b;

Semnificaiile condiiilor sunt similare cu cele pentru EMP (vezisubcapitolul 3.1).Vom nota doi factori

excluderilor. Se disting mai multe situaii:

- Cnd Taj = T bj = 1, i Nk , atunci excluderea k-EMPF de mai suseste de tipul k-EMP definit ca n s

aj bj k cele ar tate n figurile 3.7 3.10.

Reelele din figurile 3.6(a)i 3.7(a) nu pot fi folosite la constituirea EMPFdefinit anterior

rtament.

n figura 3.6(a), dup ce to01 se execut, pR01 va obine dou jetoane prinexecuia tranziiilor to02 i to03. Acest lucru este contrar celei de-a patra condiii dindefiniia de mai sus. Cnd figura 3.6(b) este considerat, execuia lui to01 necesit execuia uneia dintre tranziii to02 sau to03. Acest lucru este posibil deoarece doar unsingur jeton din pR01 este disponibil. n figura 37,a dup executarea tranziiei to01 nu se mai poate executa nici to02 n

R01 o01 o02 o03tiv (p, {({to01, to02}, to03)}).

Subreelele ar tate n figura 3.8i 3.9 pot de asemenea s fie folosite ca dou exemple de 1-EMPF din moment ce se po

o0c

7/25/2019 curs 10+11-lfr

17/21

CURS 10+11 LFR

PO01 1

0

M1L

PO02 0

0

PO01PR01

1

PO02PO03 _

TO01

DRM1-M2

PO04 0

0

M2L

PO03 0

0

DRM1-M3

PO05 0

0

M3L

PR01 1

0

R=PEPO021

PO04PR01 _

TO02PO03

1

PO05PR01 _

TO03

Figura 3.7 (a): Transportul pieselor prelucrate de pe maina M1 la una dinmainile M2 sau M3 model greit nu este sigur

PO01 1

0

M1L

PR01 1

0

17

R=PE

PO01PR01

1

PO02 _

TO01

PO03 0

0

M2L PO04 0

0

M3L

PO02

1

PO03PR01 _

TO02PO02

1

PO04PR01 _

TO03

PO02 0

0

DR1M1-M2/M3

Figura 3.7 (b): Transportul pieselor prelucrate de pe maina M1 la una dinmainile M2 sau M3 model 1-EMPF sigur

7/25/2019 curs 10+11-lfr

18/21

CURS 10+11 LFR

PO01 1

0

M3L

PO02 1

0

M1L

PO03 0

0

M2L

PO04 0

0

18

RDPM1-M3

PO05 0

0

RDPM2-M3

PR01 1

0

R=PE

PO01PR01

1

PO03 _

TO01PO02PR01

1

PO04 _

TO02

PO03PO04

1

PO05PR01 _

TO03

Figura 3.8 (a): Transportul pieselor prelucrate pe mainile M1 sau M2 la

maina M3 model greit (nu este viabil)

PO01 1

0

M1L

PO03 0

0

RDPM1/M2-M3

PO04 0

0

M3L

PR01 1

0

R=PE

PO02 1

0

M2L

PO01PR01

1

PO03 _TO01

PO03

1

PO04PR01 _

TO03

PO02PR01

1

PO03 _TO02

Figura 3.8 (b): Transportul pieselor prelucrate pe mainile M1 sau M2 pemaina M3 modelul viabil

7/25/2019 curs 10+11-lfr

19/21

CURS 10+11 LFR

M1L PC01 1

0

PO01 1

0

_

PO02 0

0

PO01PC01

1

PO02PO03 _

TO01

P1 PR01 1

0

R PO03 0

0

P2

PO04 0

0

PO02PR01

1

PO04 _

TO02PR01PO03

1

PO04 _

TO03

RDPM1-M2/M3

PR02 1

0

PR02PO04

1

PO05PR01 _

TO04PO04PR03

1

PR01PO06 _

TO05

19

M2A PO05 0

0

M2L PO06 0

0

M3L PR03 1

0

M3A

PI01 0

0

PO05PO06

1

PR02PI01PC51PR03 _

TO06

_ PC51 0

0

_

Figura 3.9: Transferul piesei prelucrate pe maina M1 la mainile M2 sau M3 unde se va executa urmtoare operaie ce necesit schimbarea poziiei piesei pe palet (P1 paletizare pentru prelucrare pe M2; P2 paletizare pentru prelucrare peM3)

_

PO01 1

0

M1L

PC02 1

0

PC01 1

0

_

PR01 1

0

V

PR02 1

0

D1A PR03 1

0

D2APO02

0 0

DV

PC51 0

0

_ PO03 0

0

M2L PC52 0

0

_

PR02PC01PO01PR01

1

PO02 _

TO01PR01PO01PC02PR03

1

PO02 _

TO02

PO02

1

PR02PC51PO03PR01 _

TO03PO02

1

PR01PO03PC52PR03 _

TO04

Figura 3.10: Transferul cu AGV a piesei prelucrate de pe M1 ctre maina M2 pe

dou trasee diferite n funcie de accesibilitatea drumurilor D1A sau D2A.

7/25/2019 curs 10+11-lfr

20/21

CURS 10+11 LFR

20

atunci:

nci:

3.3.2. Conservarea proprietilor la introducerea unei k-EMPF

Folosindu-se tehnicile pentru demonstrarea teoremelor 3.1- 3.3, se poatedemonstra urmtoarea teorem pentru o k-EMPF. Aceast teorem generalizeaz teoremele 3.1- 3.3 pentru o reea Petri coninnd o k-EMPF.

Teorema 3.4 (Excluderea mutual paralel flexibil ) Z = (PO PR PVPI, T, I, O, m0) este o subreea a lui Z = (PO (PR {pE}) PV, T, I, O, m0),

T = T,i D = {(Tai, T bi), i Nk }. Dac (pE, D) este o k-EMPF, 1. Z este mrginit (sigur) dac Z este mrginit (sigur);2. Z este viabil dac Z este viabil; i3. Z este reversibil dac Z este reversibil.

Aa cum am notat pentru EMP, toate condiiile din aceast teorem suntsuficiente, dar nui necesare.Alte remarci pentru EMP din seciunea subcapitolul 3.3 pot fi modificate

pentru a comenta aceast teorem.Cazul pentru resursa nepartajat se deruleaz atunci cnd k = 1 n definiia

excluderii mutuale paralele,i cnd k = 1, Tai = T bi 2, n definiia excluderiimutuale paralele flexibile.

Corolarul 3.1 (Ad ugarea pozi iei unei resurse nepartajate)

Se presupune c Z = (PO PR PV, T {ta, t b}, I, O, m0) este o subreea alui Z = (P, T, I, O, m0), P = PO (PR {PE}) PVPI, T = T. Dac (PE, (Ta,T b)) este o excludere 1-GEMP, atu

1. Z este mrginit (sigur ) dac Z este mrginit (sigur );2. Z este viabil dac Z este viabil; i3. Z este reversibil dac Z este reversibil.

Acest corolar este foarte folositor n sinteza poziiilor resurselor nepartajaten cadrul procedurii de proiectare a modelelor cu RP a sistemelor flexibile de prelucrare.

Exemplul 3.2: Se d reeaua Petri din figura 3.11.Reeaua Petri din figura 3.11 modeleaz sistemul flexibil de prelucrare a

dou tipuri de piese. Primul tip de pies poate fi prelucrat ori pe maina M1 ori pemaina M2. Al doilea tip de pies se prelucreaz numai pe maina 3 care este prevzut cu un buffer de intrare. Excluderea mutual paralel a resurseireprezentat de robot se face ntre activitatea de transport a pieselor de tip 1de laintrare la mainile M1 sau M2 i activitatea de transport a pieselor de tip 2 de laintrare la buffer-ul mainii M3.

7/25/2019 curs 10+11-lfr

21/21

CURS 10+11 LFR

21

PC01 1

0

- PV01 2

0

-

PR02 1

0

M2A PR01 1

0

M1A

PI01 0

0

-

PC51 0

0

- PC52 0

0

-

PR04 1

0

M3A

PV03 2

0

BA

PC02 1

0

-PV02 2

0

-

PR03 1

0

PE=R

PC01PV01PR03

1

PO01-TO01

PR02PO01

1

PO03PR03-TO02

PR01PO01

1

PO02PR03-TO03

PO03

1

PR02PI01-

TO04PO02

1

PR01PI01-

TO05

PI02 0

0

-

PI01

1

PV01PC51-

TO06

PR03PV02PC02

1

PO04-TO07

PO04PV03

1

PR03PI02-

TO08

PR04PI02

1

PO05PV03-

TO09

PO05

1

PR04PC52PV02-TO10

PO01 0

0

RDPM1/M2 PO04 0

0

RDPB

PO05 0

0

M3L

PO02 0

0

M1LPO03 0

0

M2L

Figura 3.11: Un exemplu de 2-EMPF

Reeaua Petri din figura 3.11 conine urmtoarele seturi de poziii:

1. Setul poziiilor operaionale: PO = {po01...po05},2. Setul poziiei resursei fixe: PR = {pR01...pR04},3. Setul poziiei resursei variabile: PV = {pV01... pV03} i4. Setul poziiilor intermediare: PI = {pI01}

Fiecare R-poziie este iniial marcat conform figurii 3.11. Se poate verificacu uurin faptul c (pE, D) este o 2-EMPF, unde D = {(to01, {to02, to03}), (to07,to08)} i m0 = (m0(pV01), 0, 0, 0, 0, 1, 1, m0(pV02), 0, 0, 0, 2, 1)T cnd m0(pV01) 0i m0(pV02) 0.