1

Probleme rezolvate

1. S se studieze proprietile de mrginire, viabilitate, ciclicitate i fr blocaje pentru reelele Petri ilustrare n figura urmtoare:

-a- -b-

P1P1

2 (3)

T4T4T3T3 T1T1

P3P3

P2 P2

T2T2

Rezolvare.

Graful de marcaje al reelei din figura a) este :

Se observ c numrul de vectori de marcaj este finit, prin urmare reeaua este mrginit. Deoarece nici un marcaj nu este vector de blocaj reeaua nu prezint blocaje. Tranziiile T3 i T4 se pot executa o singur dat. De aceea ele sunt cvasiviabile, spre deosebire de celelalte tranziii care se execut de un numr infinit de ori. n concluzie, se poate spune c reeaua este cvasiviabil. Proprietatea de reversibilitate nu este ndeplinit deoarece nu exist o secven de tranziii care s conduc din marcajul M3 n marcajul iniial.

M0 =

2

0

0

M1 =

1

1

0

M2 =

0

2

0

M3 =

0

0

1

M4 =

1

0

0

M5 =

0

1

0

T2

T1

T1

T2

T4

T3

T1

T2

2

Pentru reeaua din figura b) cu ponderea arcului T4 P1 egal cu 2, graful de marcaje accesibile este ilustrat n figura . Din graf se deduce c reeaua este mrginit i fr blocaje ca cea dinainte, n plus, prin buclele care s-au format n graf, reeaua este viabil, pentru oricare marcaj din graf i oricare tranziie putndu-se gsi o secven pornind de la acest marcaj care s conin tranziia respectiv.

Pe acest exemplu se mai poate face o observaie. Prin buclele care s-au format pe graf se pot identifica secvenele repetitive (secvene de tranziii care, pornind de la un anumit marcaj, conduc la acelai marcaj). Acestea sunt: S1 = T1T3T4, S2 = T1T1T2T2, S3 = T1T1T2T3T4. Se poate vedea uor c din toate marcajele accesibile de pe acest graf se poate ajunge n marcajul iniial, deci reeaua este reversibil.

S consideram un ultim caz n care ponderea arcului T4 P1 este 3 (vezi figura -b-). n acest caz se obine urmtorul graf de acoperire:

T4

0

0

2

M0=T1

T2

0

1

1

M1=

0

2

0

M2=T1

T2

T3

1

0

0

M3=

0

0

M4=T1

0

M5=T3

M6=

T1, T2 T1, T2, T3, T4

Se observ c pe acest graf s-a substituit, conform algoritmului de construcie a arborelui

de acoperire, valoarea 3 care s-ar fi obinut dup prima executare a lui T4 cu . n continuare se poate observa c reeaua Petri are toate poziiile nemrginite; n acest fel se deduce c reeaua este nemrginit. Se pstreaz ns proprietile de viabilitate i de fr blocaje.

2. S se construiasc graful de marcaje i s se discute proprietile de mrginire, viabilitate i ciclicitate ale reelei sincronizate din figura de mai jos. S se compare aceste proprieti cu cele ale reelei nesincronizate.

T4

T3

T2T2

0

2

0

1

1

0

2

0

0

0

0

1

T1 T1

M0 =

3

Rezolvare.

Reeaua Petri sincronizat este viabil aa cum se poate vedea imediat din graful de marcaje accesibile.

{T1, T2}/e1

T3/e2

{T4, T5}/e3

M0 =

2

0

0

0

0

M1 =

0

0

1

1

0

M2 =

1

1

0

0

0

Figura

Dac ns considerm aceeai reea dar nesincronizat se poate vedea, construind din nou graful de acoperire, c aceasta nu mai este viabil.

Prin executarea de dou ori la rnd a tranziiei T1 sau a tranziiei T2 pornind de la marcajul iniial se ajunge la blocaj, deci de la aceste marcaje nici o tranziie nu va mai putea fi executat. Secvenele T1T1 i T2T2 nu sunt posibile pentru reeaua sincronizat.

P1

e1T2e1T1

P3P2

e2T3

P5P4

e3T4 e3 T5

4

0

2

0

0

0

1

0

0

0

1

1

1

0

0

0

0

0

0

1

1

2

0

0

0

0

0

1

1

0

0

1

0

1

0

0

1

0

0

1

0

0

0

2

0

0

T5

T1

T4T2T1

T2

T3

T1

T5T2

M0 =

T4

5

Probleme propuse

3. Pentru reeaua Petri din figura de mai jos, s se determine pe baza grafului de marcaje proprietile :

- viabilitate;

- mrginire;

- reversibilitate;

- blocaje;

- conflicte (structurale, efective);

- conservativitate;

- secvene repetitive;

- invariani de execuie;

- limbajul generat de reea.

P1

P2 P3

P4

P5

P6

T1

T2 T3

T4T5

T6 T7

4. Se d reeaua Petri din figura de mai jos. Se cere studierea proprietilor (mrginire, viabilitate, conflicte, conservativitate, invariani) pe baza grafului de marcaje, pentru marcajul iniial M0= [1 0 k 0].

6

P1

1

P2

1

P3

1P4

1

T2

1

T1

1

T4

1T3

1k

k

5. Fie reeaua din figura de mai jos:

P2

P1

P4

P3 P5

P6

T1

T2

T3 T4

Se cer:

a) proprietile de mrginire, viabilitate, conflicte, siguran, puritate;

b) invarianii de marcaj;

c) limbajul generat de RP.

6. Se consider RP din figura de mai jos. S se construiasc arborele de acoperire i s se studieze proprietile de mrginire, viabilitate reversibilitate i conservativitate. Care sunt invarianii de marcaj i de execuie?

7

T3

T1

P1 P2

P3

P4

T2

7. S se construiasc graful de marcaje al RP din figur i pe baza lui :

a) s se determine proprietile;

b) s se compare proprietile de la punctul a) cu cele ale reelei autonome.

P1

P2P4

P3

P5

P6

T1

T2 T4

T3 T5

e1

e

e2

e1

e

8. S se studieze proprietile reelei Petri din figura de mai jos. Invarianii de execuie i limbajul reelei.

8

P3

P5

P4

P1 P2

T2

T1

T3

T4

9. S se realizeze graful de marcaje i s se precizeze proprietile (mrginire, viabilitate, blocaje, conflicte, invariani de marcaj, invariani de execuie, conservativitate) pentru reeaua din figura de mai jos.

P1 P2 P3

P4

T2

T3

T1

T4

P5

10. Determinai secvena de simulare completa (SSC) n raport cu evenimentul a pentru marcajele iniiale pentru reeaua Petri sincronizata din figura de mai jos:

a. M0= [2 1 1 0 0 1]

b. M0 = [2 2 2 0 0 2]

Menionai care din SSC sunt maximale i explicai rspunsul.

9

P1

P2

P4

P3

P5 P6

T1T2

T4T3 T5

b

a

a

a

T6b

a

11. S se determine proprietile Reelei Petri din figura de mai jos utiliznd graful de marcaje accesibile.

P3P2

2

P4

3

T3T1

P1

T2

2

12. Fie reeaua P temporizat i generalizat din figura, unde di reprezint durata asociat poziiei Pi. Pentru marcajul iniial reprezentat n figura de mai jos se cer:

a) graful de marcaje accesibile;

b) proprietile reelei.

10

T1 T2

3

3

d3=1

P3

d2=1

d1=1

P2

P1

13. S se construiasc graful de acoperire pentru reeaua din figura de mai jos att n cazul sincronizat ct i dac se consider reeaua nesincronizat. S se discute proprietile reelei n ambele situaii.

P1

e2

T1 e1

T2

P2

e3

T5

e2

T3T4 e1

P3

14. Pentru reeaua Petri sincronizat din figura de mai jos s se construiasc graful de marcaje accesibile i s se discute proprietile.

e1

T1 P2P1

e1T4

T2 eT3 e

2

e2

T5P4 P3

15. Fie reeaua Petri generalizat din figura de mai jos.

11

a) Care sunt tranziiile valide din M0 ?

b) Dup execuia a dou tranziii reeaua se blocheaz. Care sunt tranziiile i care este marcajul de blocaj?

c) Este reeaua mrginit? Justificai rspunsul. Reeaua este viabil?

d) Demonstrai c secvena T3T1 se poate executa maxim de dou ori.

2

P1

P4P2

T111

T2

T4 T3

P3

16. Construii arborele de acoperire i graful de marcaje accesibile pentru reeaua Petri din figura de mai jos. Studiai proprietile de mrginire, viabilitate fr blocaje i conservativitate.

T2

T1

T3

P1

P2P3

17. S se discute proprietile RP din figura de mai jos.

12

P2

P4

P3

P5

T1

T2T4

T3

T5

P6

T6

T7

P1

18. S se construiasc graful de marcaje i s se precizeze proprietile (mrginire, viabilitate, reversibilitate, conservatitivitate, blocaje, conflicte). S se determine invarianii de marcaj i de execuie. De asemenea se cere construirea grafului de marcaje accesibile pentru reeaua T temporizat. (duratele asociate tranziiilor sunt indicate n paranteze).

P1

P2

P4

P3

P5

T1

T2 T4

T3T5

(2)

(3)

(2)

(1)

(1)

P6

T6

13

19. Sistemul din figura de mai jos prelucreaz dou tipuri de piese: A respectiv B, preluate din dou depozite de intrare cu capacitate infinit. Robotul R1 ncarc piesele de tip A pe maina M1 i piesele de tip B pe maina M2. Dup prelucrarea pe maina M1, respectiv pe maina M2, piesele de tip A sunt transferate automat n bufferul B1 de capacitate 4, iar piesele de tip B sunt transferate automat n bufferul B2 de capacitate 6. Robotul R2 preia piese din bufferele B1 i B2 i ncarc maina M3 nti cu o pies de tip A i dup aceea cu dou piese de tip B (pe rnd). Astfel maina M3 realizeaz operaia de asamblare a unei piese A i a dou piese B n ordinea A+B+B. Dup asamblare piesele prsesc sistemul.

Se presupune c mainile pot prelucra o singur pies la un moment dat; de asemenea capacitatea de transfer a roboilor este de o pies. Se cunosc timpii de prelucrare pe cele trei maini: durata de prelucrare a unei piese de tip A pe maina M1 este d1 = 3 uniti de timp; prelucrarea unei piese de tip B pe maina M2 se face n d2 = 2 uniti de timp; iar durata operaiei de asamblare pe maina M3 este das = 2 uniti de timp.

S se modeleze sistemul de producie astfel nct reeaua s fie mrginit. S se identifice invarianii de marcaj.

M1

d1=3

M2 d2=2

R1A B

B1

(4)

B2

(6)

R2

M31A+ 2B

d_as = 2

Iesire din sistem

20. Considerm execuia de tip Round-Robin a mai multor taskuri. Aceasta presupune transferul controlului succesiv fiecrui task pentru execuia unei pri a sa. Taskurile n execuie partajeaz o aceeai unitate central, iar la fiecare control

14

fiecare task poate executa una sau mai multe instruciuni. S se construiasc RP care modeleaz acest protocol, n urmtoarele cazuri :

a) Se consider 4 taskuri, fiecare task executnd cte o singur instruciune cnd primete controlul;

b) Se consider 2 taskuri, taskul 1 executnd 3 instruciuni, iar taskul 2 executnd 5 instruciuni la primirea controlului.

Indicaie.

a) Pentru fiecare task se vor considera urmtoarele poziii:

poziie ai care marcata semnifica taskul n ateptare;

poziie exi care marcat semnific faptul c taskul i este n execuie pentru o instruciune;

poziie pi care dac este marcat semnific faptul c s-a dat controlul taskului i.

b) Se utilizeaz o reea Petri generalizat.

21. Se consider un proces de producie simplu, coninnd un consumator i un productor ce folosesc mpreun un acelai stoc, acesta avnd o capacitate limitat la 3 uniti. Productorul poate produce o singur pies la un moment dat, el putnd depune piesa n stoc imediat ce a terminat-o dac stocul permite depunerea. Imediat dup depunerea piesei productorul rencepe procesul de producie. Consumatorul la rndul su, imediat ce a terminat de consumat o pies (una singur la un moment dat) ia o noua pies din stoc dac acesta nu este vid. S se modeleze cu RP funcionarea acestui proces.

depunere retragere

produc tor stoc consumator

22. Fie un sistem de producie care prelucreaz un singur tip de piese conform fluxului tehnologic descris n figura de mai jos. La intrare n sistem, piesele sunt ncrcate pe paletele preluate dintr-un stoc de capacitate 3. Robotul R1 ncarc piesele alternativ pe mainile M1 i M2, M1 fiind ncrcat prima. Bufferele B1 (de capacitate 4) i B2 (de capacitate 3) sunt ncrcate automat cu piese de pe mainile M1 respectiv M2 de ndat ce acestea termina operaia de prelucrare. Robotul R2 ncarc maina M3 prelund piese att din bufferul B1 ct i din bufferul B2. Dup prelucrarea pe maina M3 piesele prsesc sistemul iar paletele sunt reciclate la intrarea sistemului i depuse n stocul de palete. tiind c fiecare main poate prelucra o singur pies la un moment dat (capacitate 1), s se construiasc reeaua Petri care modeleaz acest sistem de producie.

15

R1

M1 (1)

B1 B2

R2

M2 (1)

M3 (1)

Stoc palete

23. Se consider un stoc ce poate conine un numr infinit de piese. Funcionarea sa este sincronizat pe dou evenimente externe: evenimentul e1, sosirea unei piese i evenimentul e

2, sosirea unei cereri de pies. O cerere de pies este satisfcut imediat dac exist piese n stoc.

Modelai comportamentul stocului de piese printr-o reea Petri sincronizat i construii graful de marcaje accesibile pentru urmtoarele dou situaii:

a) se presupune ca o cerere de pies nesatisfcut (nefiind piesa n stoc) este pierdut (utilizatorul trebuie s-i rennoiasc cererea);

b) se presupune c o cerere de pies nesatisfcut este memorat, i satisfcut atunci cnd o nou pies sosete n stoc.

stoc

sosirea unei

cereri de piesa

sosirea unei

piese

plecarea

pieselor

sosirea

pieselor

e2e

1

16

24. Patru filosofi, f1f4, stau n jurul unei mese, ntre ei fiind dispuse baghetele b1b4. Un filosof se poate gsi ntr-una din urmtoarele dou stri: poate gndi sau poate mnca. Pentru a manca un filosof are nevoie de cele dou baghete aflate de o parte i de cealalt a sa. n starea iniial toi filosofii gndesc i baghetele se afla pe mas.

a) Descriei printr-o reea Petri urmtorul protocol: cnd un filosof dorete s mnnce el ia mai nti bagheta din dreapta sa, apoi pe cea din stnga sa i ncepe s mnnce. Cnd termin de mncat el depune pe mas mai nti bagheta din mana dreapt, apoi pe cea din mana stng i trece astfel n starea n care gndete. Indicai invarianii minimali pentru reeaua construit. Este aceasta reea viabil? Dac exist un blocaj gsii secvena de validri care conduce la acesta i dai o explicaie a acestui blocaj.

b) Definii un protocol astfel nct s nu mai poat aprea situaie de blocaj, i construii reeaua Petri corespunztoare.

25. Se consider dou bile de biliard, A i B, (figura de mai jos) care se deplaseaz pe o aceeai dreapt, paralel cu una din margini. Fiecare bil are trei stri: deplasare la dreapta, deplasare la stnga sau ateptare (bila oprit). Se cere modelarea comportamentului celor dou bile printr-o reea Petri, presupunnd c: a) atunci cnd lovete o margine o bil pornete n sens invers cu aceeai viteza; b) dac cele dou bile se ciocnesc, ambele fiind n micare cu aceeai vitez, ele repornesc n sens invers; c) dac o bil oprit este lovit de cealalt, prima se pune n micare i a doua se oprete. Presupunem c bilele realizeaz o micare ideal, fr ncetinire datorat frecrii. S se studieze, n funcie de marcajul iniial posibil, proprietile reelei construite, pe baza grafului de marcaje.

A B

26. Se consider 6 taskuri a cror executare este condiionat de urmtoarele reguli: iniial taskul 1 este executabil; taskurile 2 i 3 nu pot fi executate dect dup taskul 1 (nensemnnd ns c vor ncepe simultan sau imediat dup terminarea taskului 1). Taskul 4 nu poate fi executat dect dup taskul 3, taskul 5 dup taskurile 2 i 4, iar taskul 6 dup taskurile 4 i 5. Taskul 1 nu poate fi reexecutat dect dup terminarea taskului 2, iar taskul 3 dup taskurile 1 i 6. Considernd c execuia fiecrui task are o durata di s se modeleze prin reele Petri P - temporizate acest sistem. Care este momentul la care ncepe prima execuie a taskului 5 ?

Indicaie. Pentru fiecare task se introduc dou poziii: una corespunztoare execuiei taskului i una care asigur ndeplinirea condiiei de execuie a taskului respectiv.

27. Se consider o linie de asamblare cuprinznd dou maini fiecare cu cte un stoc n intrare, aa cum se vede n figura de mai jos. Stocurile au o capacitate nelimitat.

17

Sistemul prelucreaz dou tipuri de piese, p1 i p2, care sosesc ntr-o ordine aleatoare n stocul 1 dar prelucrarea lor pe main fcndu-se prin alternana. Se presupune c mainile pot prelucra o singur piesa la un moment dat.

Fie evenimentul ei sosirea unei piese de tip pi. O piesa de tipul 1 necesit o

prelucrare de 8 uniti de timp pe maina 1 i de 3 uniti de timp pe maina 2 iar o piesa de tipul 2 necesit cte 5 uniti de timp pe fiecare main.

a) S se modeleze acest sistem printr-o reea sincronizat i T-temporizat n condiiile enunate anterior;

b) Cum se modific reeaua n ipoteza c stocul 1 conine permanent cel puin cte o pies de fiecare tip ?

sosire

piese

p1, p2

stoc 2stoc 1

masina 2masina 1

plecare

piese

p1, p2

28. Se consider un flux de fabricaie compus din dou maini, fiecare avnd un stoc de piese n intrare. n sistem exist dou palete, piesele trecnd ntre maini purtate pe palete. Aceste palete sunt reciclabile, adic ele se ntorc n stocul 1 dup ce piesele pe care le-au purtat sunt terminate pe maina 2. Maina 1 poate trata o singur pies la un moment dat, timpul de servire fiind d1 = 2 uniti de timp, n timp ce maina 2 poate trata dou piese, pentru fiecare fiind necesare d2 = 3 uniti de timp.

a) S se construiasc RP P-temporizat pentru acest sistem;

b) S se construiasc graful de marcaje pentru reeaua P-temporizat considernd funcionarea cu vitez maxim. Care este durata unui ciclu de fabricaie?

stoc 2 d2=3d1=2stoc 1

masina 2masina 1