Reţele Petri

•Definiţii

# 1

•Definiţii•Convenţii•Reguli de funcţionare•Reţele temporizate•Reţele stochastice•Reţele stochastice•Exemple de abstractizare

• Reţelele Petri sunt un instrument pentru studiul sistemelor. Teoria reţelelor Petri permite unui sistem să fie modelat de către o reţea Petri,

1 Introducere

sistem să fie modelat de către o reţea Petri, realizându-se astfel o reprezentare matematică a sistemului. Analiza reţelei Petri poate apoi să furnizeze informaţii importante despre structura şi comportamentul dinamic al sistemului modelat, putând fi folosită pentru a evalua sistemul modelat putând fi folosită pentru a evalua sistemul modelat şi pentru a sugera îmbunătăţiri sau schimbări. Astfel, dezvoltarea unei teorii a reţelelor Petri se bazează pe aplicarea reţelelor Petri în modelarea şi proiectarea sistemelor

• Reţelele Petri sunt proiectate special pentru a modela sisteme cu componente cu interacţiune concurentă. Reţelele Petri au la bază studiile lui

2 Istoric

concurentă. Reţelele Petri au la bază studiile lui Carl Adam Petri (lucrarea de doctorat)

• A.W. Holt extinde proiectul pentru teoria sistemelor informaţionale (Information System Theory Project)

• 1970 Jack B. Dennis reţelele Petri şi metodele • 1970 Jack B. Dennis reţelele Petri şi metodele aferente Institutul de Tehnologie din Massachusetts (M.I.T.)

• Din 1978 grup de cercetare la Hamburg Germania

Definiţii fundamentale

• Structura unei reţele PetriO reţea Petri este compusă din patru părţi:O reţea Petri este compusă din patru părţi:- o mulţime de locaţii S;- o mulţime de tranziţii T;- o funcţie de intrare I;- o funcţie de ieşire O.

Funcţiile de intrare şi ieşire sunt relaţii între T (mulţimea de tranziţii) şi S(mulţimea de locaţii). Funcţia de intrare I este o funcţie de la o tranziţie t la o colecţie de locaţii I(tj) care poartă numele de locaţiile tranziţie tj la o colecţie de locaţii I(tj) care poartă numele de locaţiile de intrare ale tranziţiei. Funcţia de ieşire O este o funcţie de la o tranziţie tj la o colecţie de locaţii O(tj) care poartă numele de locaţiile de ieşire ale tranziţiei. Structura unei reţele Petri este definită de locaţiile şi tranziţiile sale, de funcţia sa de intrare şi de cea de ieşire.

Grafuri pentru reţele Petri• O structură de reţea Petri constă din locaţii şi tranziţii. Corespunzător

acestora, un graf de reţea Petri are două tipuri de noduri. Un cerc acestora, un graf de reţea Petri are două tipuri de noduri. Un cerc reprezintă o locaţie; Un pătrat (sau o bară) reprezintă o tranziţie. Deoarece un cerc reprezintă o locaţie, am numit cercurile locaţii. Similar, am numit barele tranziţii.

• Arcele direcţionate (săgeţile) conectează locaţiile şi tranziţiile, unele fiind direcţionate de la locaţii la tranziţii, altele de la tranziţii la locaţii. Un arc direcţionat de la o locaţie pi la o tranziţie tj defineşte locaţia ca fiind o intrare a tranziţiei. Intrările multiple într-o tranziţie sunt indicate prin arce multiple de la locaţiile de intrare la tranziţii. O indicate prin arce multiple de la locaţiile de intrare la tranziţii. O locaţie de ieşire este indicată printr-un arc de la o tranziţie la o locaţie.

De asemenea, ieşirile multiple se indică prin arce multiple.

Marcajele reţelelor Petri

• Un marcaj este o asignare de jetoane locaţiilor unei reţele Petri. Conceptul de jeton este un concept fundamental în teoria reţelelor Petri (la fel ca locaţiile şi tranziţiile). Jetoanele sunt asignate locaţiilor unei reţele Petri si pot fi gândite ca aparţinând acestora. Numărul şi fi gândite ca aparţinând acestora. Numărul şi poziţia jetoanelor se pot schimba în timpul funcţionării unei reţele Petri. Jetoanele sunt folosite pentru a defini funcţionarea unei reţele Petri.

Reguli de funcţionare pentrureţele Petri

• Funcţionarea unei reţele Petri este controlată de numărul şi distribuţia jetoanelor în reţeaua Petri. Jetoanele sunt rezidente în distribuţia jetoanelor în reţeaua Petri. Jetoanele sunt rezidente în locaţii şi controlează execuţia tranziţiilor reţelei. O reţea Petri se execută prin declanşarea tranziţiilor. O tranziţie se declanşează prin mutarea jetoanelor din locaţiile de intrare şi crearea de noi jetoane care sunt distribuite în locaţiile de ieşire.

• O tranziţie se poate declanşa dacă este posibilă. O tranziţie este posibilă dacă fiecare dintre locaţiile sale de intrare conţine un posibilă dacă fiecare dintre locaţiile sale de intrare conţine un număr de jetoane mai mare sau egal cu numărul de arce de la acea locaţie la tranziţie. Sunt necesare jetoane multiple pentru arce multiple de intrare. Jetoanele din locaţiile de intrare care permit o tranziţie sunt jetoanele sale de validare.

Definiţie

Categorie de grafuri

# 8

Noduri

Arce

Definiţie

Categorie de grafuriNoduri Locuri + Tranziţii

# 9

Noduri Locuri + Tranziţii

Arce

LocuriTranziţii

Convenţii

Intrare în P2 Ieşire din T1

# 10

P1

P2

P3

T1

T2

T3

Ieşire din P2Intrare în T1

P3T2

Convenţii

a(Ti,Pj ) = evaluarea arcului

# 11

P1

P2

P3

T1

T2

T3

a(P1,T1) a(P2,T3)

a(T1,P2)

a(T3,P1)

P3T2

a(P3,T3)a(P1,T2)

a(T3,P1)

Convenţii

201

021

A = matricea de incidenţă

# 12

P1

P2

P3

T1

T2

T3

1 2 1

211

P3T2

122

1

Convenţii

M = (2, 1, 0) = marcajul reţeleiJeton

# 13

P1

P2

P3

T1

T2

T3

1 2 1

Jeton

P3T2

122

1

Reguli de funcţionare

Tranziţieactivabilă

Tranziţie

M3 < a (P3, T3)

# 14

P1

P2

P3

T1

T2

T3

1 2 1M1 a (P1, T1)

Tranziţieinactivabilă

P3T2

122

1

Reguli de funcţionare

Activaretranziţie T1

# 15

P1

P2

P3

T1

T2

T3

1 2 1

P3T2

122

1

Reguli de funcţionare# 16

P1

P2

P3

T1

T2

T3

1 2 1

P3T2

122

1

Reguli de funcţionare

Activare

# 17

P1

P2

P3

T1

T2

T3

1 2 1

Activaretranziţie T2

P3T2

122

1

Reguli de funcţionare# 18

P1

P2

P3

T1

T2

T3

1 2 1

P3T2

122

1

Reguli de funcţionare

Activare

# 19

P1

P2

P3

T1

T2

T3

1 2 1

Activaretranziţie T3

P3T2

122

1

Reguli de funcţionare# 20

P1

P2

P3

T1

T2

T3

1 2 1

P3T2

122

1

Durată deactivare

Reţele temporizate

Timp de

# 21

P1 (s1)

P2 (s2)

P3 (s3)

T1(t1)

T2 (t2)

T3 (t3)1 2 1

sejur

P3 (s3)T2 (t2)

122

1

Reţele temporizate

t = 0: activare tranziţie T1

# 22

P1

P2

P3

T1(t1)

T2 (t2)

T3 (t3)1 2 1

t = 0: activare tranziţie T1

P3T2 (t2)

122

1

Reţele temporizate

0 < t < t1: staţionare jeton în T1

# 23

P1

P2

P3

T1(t1)

T2 (t2)

T3 (t3)1 2 1

0 < t < t1: staţionare jeton în T1

P3T2 (t2)

122

1

Reţele temporizate

t = t1: sfârşit activare T1

# 24

P1

P2

P3

T1(t1)

T2 (t2)

T3 (t3)1 2 1

t = t1: sfârşit activare T1

P3T2 (t2)

122

1

Durată deactivare

Reţele stochastice

Timp desejur

Probabilistice

# 25

P1 (s1)

P2 (s2)

P3 (s3)

T1(t1)

T2 (t2)

T3 (t3)1 2 1

sejur

P3 (s3)T2 (t2)

122

1

T1(t1)1 1

Exemple de abstractizare

Post simplu de lucru

# 26

T1(t1)1 1

Exemple de abstractizare

Post simplu de lucru

# 27

3 3Prelucrare simultanăT1(t1)

T1(t1)1 1

Exemple de abstractizare

Post simplu de lucru

# 28

P2

T (t )1

3 3Prelucrare simultanăT1(t1)

P3

T3 (t3)

2

1Asamblare

Evenimente şi condiţii

• Evenimentele sunt acţiuni care au loc în • Evenimentele sunt acţiuni care au loc în sistem. Apariţia acestor evenimente este controlată de starea sistemului. Starea sistemului poate fi descrisă ca o mulţime de condiţii. O condiţie este un predicat sau descriere logică a stării sistemului. sau descriere logică a stării sistemului. Astfel, o condiţie poate fi fie adevărată, fie falsă

Evenimente şi condiţii

• Deoarece evenimentele sunt acţiuni, ele se • Deoarece evenimentele sunt acţiuni, ele se pot produce. Pentru ca un eveniment să se producă, s-ar putea să fie necesar ca anumite condiţii să fie adevărate. Acestea se numesc precondiţiile evenimentului. Apariţia evenimentului poate determina Apariţia evenimentului poate determina ca precondiţiile să nu mai fie adevărate, şi poate stabili ca alte condiţii, numite postcondiţii, să devină adevărate

Exemplu - problema modelăriiunui atelier simplu

Atelierul aşteaptă până când apare un ordin şi apoi îl prelucrează şi îl trimite afară pentru distribuire. şi îl trimite afară pentru distribuire.

Condiţiile pentru sistem sunt:

a. Atelierul este în aşteptare.

b. A sosit un ordin şi este în aşteptare.

c. Atelierul prelucrează ordinul.

d. Prelucrarea ordinului s-a încheiat.

Evenimentele vor fi:

1. Sosirea unui ordin.

2. Atelierul începe prelucrarea ordinului.

3. Atelierul termină prelucrearea ordinului.

4. Ordinul este trimis pentru distribuire.

Precondiţiile evenimentului 2 („Atelierul începe prelucrarea ordinului.”) sunt evidente: (a)„Atelierul este în aşteptare.” şi (b) „A sosit un ordin şi este în aşteptare.”. Postcondiţia evenimentului 2 este (c) „Atelierul prelucrează Postcondiţia evenimentului 2 este (c) „Atelierul prelucrează ordinul.”. Similar, putem să definim precondiţiile şi postcondiţiile celorlalte evenimente şi să construim următorul tabel de evenimente cu precondiţiile şi postcondiţiile corespunzătoare.

Intrăriile unei tranziţii sunt precondiţiile evenimentului corespunzător; ieşirile sunt postcondiţiile. Apariţia unui eveniment corespunde cu declanşarea tranziţiei corespunzătoare. O condiţie adevărată este reprezentată de existenţa unui jeton în locaţia corespunzătoare condiţiei. Când o tranziţie se declanşează, mută jetoanele de validare reprezentând îndeplinirea precondiţiilor şi creează noi jetoanele de validare reprezentând îndeplinirea precondiţiilor şi creează noi jetoane reprezentând îndeplinirea postcondiţiilor.

Reţeaua Petri din figura este un model de reţea Petri pentru exemplul de mai sus cu atelierul. Am etichetat fiecare tranziţie şi locaţie cu evenimentul sau

condiţia corespunzătoare.

Exemplul 2• Atelierul poate avea trei maşini diferite M1, M2, şi M3 şi doi operatori F1 şi F2.

Operatorul F1 poate opera maşinile M1 şi M2, iar operatorul F2 poate opera maşinile M1 şi M3. Lucrările necesită două stagii de prelucrare. Mai întâi acestea trebuie prelucrate de maşina M1, apoi de oricare dintre maşinile M2, sau M3. Acest sistem mai complicat va avea următoarele condiţii:

• a. A sosit o lucrare şi aşteaptă să fie prelucrată de M1.

• b. O lucrare a fost prelucrată de M1 şi aşteaptă să fie prelucrată de M2 sau M3.

• c. Prelucrarea lucrării s-a terminat.

• d. Maşina M1 este liberă.

• e. Maşina M2 este liberă.

• f. Maşina M3 este liberă.

• g. Operatorul F este liber.• g. Operatorul F1 este liber.

• h. Operatorul F2 este liber.

• i. Maşina M1 este operată de F1.

• j. Maşina M1 este operată de F2.

• k. Maşina M2 este operată de F1.

• l. Maşina M3 este operată de F2.

Pot apărea următoarele evenimente:1. Soseşte un ordin.2. Operatorul F1 porneşte prelucrarea lucrării pe maşina M1.2. Operatorul F1 porneşte prelucrarea lucrării pe maşina M1.3. Operatorul F1 termină prelucrarea lucrării pe maşina M1.4. Operatorul F2 porneşte prelucrarea lucrării pe maşina M1.5. Operatorul F2 termină prelucrarea lucrării pe maşina M1.6. Operatorul F1 porneşte prelucrarea lucrării pe maşina M2.7. Operatorul F1 termină prelucrarea lucrării pe maşina M2.8. Operatorul F2 porneşte prelucrarea lucrării pe maşina M3.2

9. Operatorul F2 termină prelucrarea lucrării pe maşina M3.10. Ordinul este trimis pentru livrare.

Declanşarea nedeterministă şi nesimultană a tranziţiilor în modelarea sistemelor concurente este indicată în figura de mai jos. În această situaţie, cele două tranziţii posibile nu se afectează reciproc în nici un fel, şi secvenţele posibile de evenimente includ unele în care apare mai întâi una dintre evenimente includ unele în care apare mai întâi una dintre tranziţii, şi altele în care apare mai întâi cealaltă tranziţie.

Cealaltă situaţie în care simultaneitatea este mai dificil de mânuit şi care poate fi controlată prin definirea de evenimente care nu apar simultan, este ilustrată în figura de mai jos. Aici, cele două tranziţii posibile sunt în conflict. Se poate declanşa numai o singură tranziţie, deoarece, prin declanşare, jetonul din intrarea singură tranziţie, deoarece, prin declanşare, jetonul din intrarea comună este mutat şi dezactivează cealaltă tranziţie.

pi

tj

tk