Retele petri temporizate

RETELE PETRI TEMPORIZATE

Introducere

Apare deseori necesitatea descrierii aspectelor temporale ale sistemelor, cum sunt duratele unor operatii. Retelele de tip C/E sau P/T, retele cu predicate si tranzitii (Pr/T) sau cu predicate multivalente si tranzitii etc. pot descrie structuri logice, dar toate neglijeaza caracterul temporal. Studiul sau descrierea paralelismului fara a lua in considerare duratele operatiilor sunt deseori incomplete. Aspectul temporal poate fi utilizat la rafinarea unor operatii, prin eliminarea unor conditionari functionale inutile. Asocierea timpului la activitatile care trebuie sa fie executate poate servi la planificarea lor. Prin urmare, timpul serveste la descrierea duratelor unor activitati, sau a intarzierii lor, la declararea cerintelor temporale si in final, la verificarea respectarii constrangerilor temporale. Ipoteza ca tranzitiile se executa instantaneu nu poate fi acceptata in urmatoarele situatii:

planificarea sarcinilor;

descrierea constrangerilor temporale;

determinarea precedentelor;

determinarea timpului minin si/sau maxim al unei secvente;

determinarea timpului probabil al unei secvente.

In asemenea cazuri apare necesitatea diferentierii sarcinilor in

sarcini reactive de timp real (legate de interactiunea dintre sistem si mediu) si sarcini de rationare. Introducerea aspectelor temporale se justifica mai ales la sistemele care sunt ciclice sau repetitive.

Exista mai multe variante de retele Petri temporizate. O prezentare generala a lor este facuta de Freedman (1991).

Retele Petri temporizate

Cea mai simpla varianta pentru includerea timpului se bazeaza pe asocierea unor atribute temporale cu nodurile retelei. Aceasta se poate realiza conditionand fie intarzierea jetoanelor in locatii, pentru un anumit interval de timp, inainte de executia tranzitiilor, fie introducand o intarziere intre momentul in care tranzitiile sunt admisibile si momentul in care ele se executa (intarzierea tranzitiilor).

Se introduce notiunea de locatie temporizata prin atasarea unei valori , reprezentand durata dintre momentul de timp cand un jeton este introdus in locatie si momentul cand el poate fi extras pentru executia unei tranzitii de iesire. Daca un jeton este introdus intr-o locatie temporizata, el nu paraseste locatia (pentru executia tranzitiilor de iesire) pana cand nu a expirat intervalul de timp asociat locatiei respective.

Definitia 1. O retea Petri (determinista) cu locatii temporizate este de forma (N,), unde N = (P, T, pre, post), iar este o functie care asociaza un numar real nenegativ fiecarei locatii a retelei,

,

este minimul timpului de stationare a unui jeton in .

Un jeton dintr-o retea Petri cu locatii temporizate poate fi in doua stari: gata si in asteptare. Cand un jeton este introdus intr-o locatie, el intra in asteptare, devenind gata dupa un interval unitati de timp. Jetoanele in asteptare nu pot permite executia unei tranzitii, situatia fiind asemenatoare aceleia in care ele nu exista inca acolo.

Deoarece tranzitiile reprezinta activitatile care schimba starea (marcajul) retelei, se considera mai adecvata asocierea timpului cu aceste activitati (tranzitii). In scopul rezolvarii confilctelor care apar intre tranzitii, mai multi autori au impartit timpul de executie al unei tranzitii, care se executa in trei faze.

Acestea sunt:

1. Cand tranzitia t devine admisibila, este initializata o executie in care pre(p,t) jetoane dispar din fiecare locatie de intrare a tranzitiei t
2. Urmeaza procesul de executie, care reprezinta o operatie cu durata de unitati de timp.
3. Cand cele unitati de timp expira, executia se termina. In aceasta faza post(t,p) jetoane sunt transferate in fiecare locatie de iesire a tranzitiei t.

In cazul in care este necesara modelarea prioritatii activitatilor, se asociaza un timp de activare fiecarei tranzitii, care se considera ca are o executie atomica (indivizibila). Conflictele sunt rezolvate la expirarea intervalelor de timp asociate tranzitiilor. Solutia este intotdeauna in favoarea primei tranzitii care indeplineste conditia legata de temporizare.

Definitia 2. O retea Petri (determinista) cu tranzitii temporizate este un cuplu de forma (N,), unde N = (P, T, pre, post) este o retea si este o functie, care ii asociaza fiecarei tranzitii a retelei un numar real nenegativ , , .

O retea Petri cu locatii temporizate poate fi transformata intr-o retea Petri cu tranzitii temporizate. Figura de mai jos reprezinta aceasta transformare. Locatia , temporizata cu , poate fi inlocuita cu doua locatii, si netemporizate si o tranzitie temporizata (cu ). Se poate face si transformarea inversa, adica o tranzitie temporizata (cu ) se inlocuieste cu doua tranzitii netemporizate si o locatie p, temporizata (cu ).

O secventa de executii temporzate este:

unde este secventa de executii, iar este timpul la care tranzitia initiaza cea de-a n-a sa executie.

Magot (1984) defineste pentru o retea Petri temporizata care are un invariant X=[], de tip T, durata ciclului unei secvente prin:

pentru orice tranzitie a reteleo, unde este momentul de timp la care tranzitia initiaza cea de-a -a executie.

Grafuri de evenimente temporizate

Un graf de evenimente este o retea Petri in care fiecare locatie are o singura tranzitie de intrare si o singura tranzitie de iesire. Graful de evenimente este temporizat daca fiecarei tranzitii i se asociaza un timp de executie. O cale directa dintr-o retea Petri, in care toate nodurile sunt distincte, exceptand locatiile si , se numeste circuit. O retea Petri este puternic conectata daca intre oricare doua noduri ale retelei exista o cale directa.

Se considera graful de evenimente reprezentat in figura 1, cu circuitele elementare:

S-a demonstrat ca numarul total de jetoane in orice circuit elementar ramane acelasi (este invariabil) dupa executia tranzitiilor.

Optimizarea grafurilor de evenimente

deterministe puternic conectate

Exista cativa algoritmi simpli (Di Cesare s.a., 1993), care pot fi aplicati pentru a obtine toate circuitele elementare ale unui graf puternic conectat. Acestia sunt utili in analiza sistemelor flexibile de fabricatie deterministe care opereaza intr-un mod ciclic, ceea ce presupune mai mult decat capacitatea evaluarii performantelor modelului bazat pe grafuri de evenimente. Pentru a optimiza un asemenea sistem, trebuie minimizata o functie liniara:

, astfel incat ,

unde:

este un numar intreg nenegativ (i=1,2,,n);

este numarul initial al jetoanelor in locatia i (i=1,2,,n);

este peformanta ceruta, iar este viteza de executie a tranzitiei

trebuie astfel ales incat sa fie mai mic sau egal cu , unde este timpul de executie al tranzitiei .

Functia liniara care este necesar sa fie minimizata, nu trebuie sa depinda de starea sistemului (aceasta functie trebuie sa ramana invariabila la executia oricarei tranzitii, altfel minimizarea nu are sens). Conditia este indeplinita daca U=[] este un invariant de tip P.

In acest sens, se considera matricea de incidenta A, cu elementele

i=1,2,,n si j=1,2,,m,

unde:

n reprezinta numarul locatiilor;

m reprezinta numarul tranzitiilor;

este setul tranzitiilor de intrare in locatia (una singura in cazul unui graf de evenimente);

este setul tranzitiilor de iesire din locatia .

Fie U=[] un vector, astfel incat UA=0, cu , i=1,2,,n.

Rezulta ca U este un invariant de tip P:

UM=UM, MR(M)

Setul circuitelor elementare este =.

Functia liniara care trebuie minimizata se bazeaza pe invariantul de tip P:

se minimizeaza astfel incat

cu un intreg nenegativ pentru i=1,2,,n, unde:

Se defineste:

(M,l,1/)= [M()-()]

unde este setul circuitelor elementare care contin locatia p.

Algoritmul se bazeaza pe urmatoarea proprietate/

Fie M ) setul marcajelor, astfel incat (M,l,1/)[0.1), pentru pP. Atunci:

Fiecare M M ) este o solutie posibila a problemei.

Fie M M ) si fie M, astfel incat MM si MM. (Daca M(p)M(p), pP si exista cel putin un pP, astfel incat M( p)<M(p), atunci M nu este realizabil si deci nu poate constitui o parte a solutiei optimale a problemei.)

M ) contine cel putin o solutie a problemei respective.

Algoritmul se starteaza cu un marcaj realizabil si deplaseaza iterativ jetoanele din locatii pana cand se obtine o solutie care apartine lui M ). Poate fi considerat ca marcaj initial posibil marcajul care contine un jeton in fiecare locatie sau oricare alta solutie posibila. La fiecare iteratie este deplasat euristic un jeton intr-o locatie p, astfel incat (M,l,1/)1si M(p)1.

Daca M(p)=0 exista MR(M) astfel incat M(p)1. Atunci se calculeaza M si se deplaseaza un jeton din p.

Daca sunt mai multe jetoane pP, astfel incat (M,l,1/)1, solutia consta din deplasarea jetoanelor care reduc cat mai mult posibil valoarea criteriului, pastrand in continuare posibilitatea de extragere a jetoanelor. In consecinta, sansa de realizare a unui marcaj foarte aproape de cel optim creste. Pentru a atinge acest scop este introdus un al doilea criteriu, notat cu g(M):

g(M)=

Fie M marcajul obtinut prin deplasarea unui jeton din p si =[g(M)-g(M)]/, presupunand ca (M,l,1/)1, este castigul in valoarea criteriului.

Se alege sa se deplaseze un jeton din locatia , astfel incat:

unde F=.

Volumul de calcul este proportional cu numarul locatiilor.

Algoritmul poate fi formulat dupa cum urmeaza:

Pas 1. Genereaza un marcaj realizabil M (de exemplu, pune un jeton in fiecare locatie).

Pas 2. Daca (M,l,1/)<1 pentru oricare pP, atunci opreste calculul si retine M, ca pe o solutie a problemei.

Pas 3. Daca (M,l,1/)1 pentru cel putin o locatie pP, calculeaza P, astfel incat .

Pas 4. Daca M()1, executa:

M()=M(p), pP, p

M()=M()-1

Daca M()=0, calculeaza un marcaj M realizabil din M, astfel incat

M()1

si executa:

M(p)= M(p), pP, p

M()=M ()-1

Pas 5. Revenire la pasul 2.

O alta categorie de retele Petri temporizate este aceea in care tranzitiile sunt intarziate, dar ele pot fi executate intr-un interval de timp dat, numit interval de executie. Notand cu I(t) intervalul de timp asociat fiecarei tranzitii, acesta ia valoarea:

I(t)=0 daca tranzitia nu este executabila;

I(t)=[a,b] cu a<b, a, b>0, daca este admisibila.

In acest caz starea retelei nu mai este suficient descrisa numai de marcajul M, ci mai trebuie adaugat un asa numit domeniu al executiilor, Q. Prin urmare, starea este data de perechea (M,Q). Deoarece timpul este continuu, tranzitiile pot fi executate in orice moment, deci starea depinde de planificarea executiilor tranzitiilor. Setul tuturor tranzitiilor executabile dintr-un marcaj initial este numit clasa de stari. Pentru simplificarea claselor de stare, deplasarea dintr-o clasa de stare in alta este restrictionata prin executia, numai, a unei singure tranzitii. Cand mai multe tranzitii sunt executabile in acelasi moment de timp, singura tranzitie aleasa pentru a fi executata este aceea al carei interval de timp nu este mai mare decat al oricarei alte tranzitii admisibile.

Concluzii:

Efectele introducerii timpului in retelele Petri pot fi sintetizate in cele ce urmeaza:

1. Setul secventeleor de executii ale unei retele Petri temporizate este un subset al secventeleor de executii al retelei netemporizate, deoarece informatiile temporale pot numai sa inhibe executiile anumitor tranzitii, dar nu pot sa creeze secvente executabile in plus.

2. Starea unei retele Petri temporizate nu mai poate fi descrisa complet numai de marcajul retelei netemporizate. Trebuie adaugate informatii despre intarzierile asociate tranzitiilor executabile.

3. Setul marcajelor realizabile al unei retele Petri temporizate este un subset al setului marcajelor retelei Petri netemporizate. Informatiile temporale pot sa altereze executiile unor tranzitii, sau sa modifice ordinea executiilor unor secvente de tranzitii, desi organizarea logica a executiilor nu se modifica.

4. Invariantii retelei Petri temporizate sunt aceiasi cu cei ai retelei netemporizate.

5. Unele proprietati, ca de exemplu marginirea, se conserva. Despre alte proprietati, ca de exemplu realizabilitatea (implicit interblocajul) nu se poate afirma nimic in cazul general.