Structura cursului - profs.info.uaic.rootto/Referate/intro_NPN.pdf · – p. 1/52. Re¸tele Petri...

transcript

Structura cursului

Retele Petri pe niveluri

Aplicatii ale retelelor Petri pe niveluri în modelarea fluxurilorde lucru

– p. 1/52

Retele Petri pe niveluri

punctele în locatii: puncte "atomice" sau puncte - retea

o retea de nivel înalt, numita retea sistem si o multime deretele obiect

în reteaua sistem punctele pot fi atât puncte atomice cât sipuncte-retea (retele obiect cu o anumita marcare)

punctele în retelele obiect pot fi doar puncte atomice

exista mecanisme de sincronizare între tranzitiile dinretelele obiect si cele din reteaua sistem

– p. 2/52

Exemplu

Proces P care produce o piesa pentru care are nevoie de N

componente de acelasi tip

P instantiaza doua subprocese P1 si P2

P1 produce câte o componenta. Pentru producereacomponentei are nevoie de o resursa pe care i-o furnizeazaP2

Dupa ce termina de produs piesa, P dezactiveaza celedoua subprocese

– p. 3/52

Exemplu

– p. 4/52

Exemplu

– p. 5/52

Notatii

V ar - multime de variabile. Daca v ∈ V ar, Type(v) estetipul variabilei v.

Con - multime de constante

A = V ar ∪ Con

Multimea expresiilor peste A: Expr(A) = AMS

Daca E ∈ Expr(A) este o expresie, V ar(E): multimeavariabilelor care apar în expresia E.

– p. 6/52

Multimi de etichete

Lv - multimea etichetelor pentru sincronizare verticala.

Pentru orice l ∈ Lv, exista l ∈ Lv.

Daca l1, l2 ∈ Lv, l1 6= l2 atunci l1 6= l2.

l =def l.

Lh - multimea etichetelor pentru sincronizare orizontala

Lh ∩ Lv = ∅

– p. 7/52

Definitie

Definitie 1 O retea Petri pe niveluri este un tuplu:

NPN = (A,L, SN, (EN1,m10), (EN2,m

20), . . . , (ENk,m

k0),Λ)

astfel încât :

1. A = V ar ∪ Con este multimea de variabile si constante

2. L = Lv ∪ Lh este o multime de etichete.

3. (EN1,m10), (EN2,m

20), . . ., (ENk,m

k0) sunt retele Petri

marcate, numite retele obiect.

– p. 8/52

Definitie

4. SN = (N,U ,W,M0) este o retea Petri de nivel înalt, numitareteaua sistem a NPN , unde

N = (P, T, F ) este o retea Petri.U = (Tk, I) este un model, unde:

Tk = Tkatom ∪ Tknet, Tkatom este multimea punctelor atomice în SN siTknet = {(EN,m)|∃i = 1, . . . , k : EN = ENi, m - marcare in ENi}

multimea punctelor retea.Functia de interpretare I : Con → Tk .

W : F → Expr(A) astfel încât :nu exista c ∈ Con într-o expresie de pe un arc input cu I(c) ∈ Tknet;orice variabila are o singura aparitie într-o expresie de pe un arc input;Pentru doua expresii W (p1, t), W (p2, t),V ar(W (p1, t)) ∩ V ar(W (p2, t)) = ∅.

M0 : P → TkMS este marcarea initiala a retelei .

– p. 9/52

Definitie

5. Λ este o functie partiala care asigneaza etichete din L

tranzitiilor din SN si din retelele obiect ENi (i ∈ {1, . . . , k}):daca t este o tranzitie etichetata din SN , atunciΛ(t) = l ∈ Lv

daca o tranzitie t dintr-o retea obiect ENi (i ∈ {1, . . . , k})este etichetata si Λ(t) = l ∈ Lh, atunci nu exista o altatranzitie t′ în ENi cu Λ(t′) = l.

– p. 10/52

Definitie

Restrictii referitoare la expresiile de pe arce:

– p. 11/52

Exemplu

Con = {C1, C2, 1}, V ar = {x, y}.

Lv = {p, p}, Lh = {r}

Tk = {(EN1,m)|m marcare EN1} ∪ {(EN2,m)|m marcare EN2} ∪ {•}

I(C1) = (EN1,m01), I(C2) = (EN2,m02), I(1) = •

– p. 12/52

Notatii

NPN = (A,L, SN, (EN1,m10), (EN2,m

20), . . . , (ENk,m

k0),Λ)

Daca EN retea obiect, tipulEN = {(EN,m)|m marcare a lui EN}

Daca x ∈ V ar, Type(x) ∈ {EN1, EN2, . . . ENk}

Daca t este o tranzitie în SN ,V ar(t) = {V ar(W (p, t))|p ∈ •t} ∪ {V ar(W (t, p))|p ∈ t•}

O asignare este o functie b : V ar → Tknet cub(v) ∈ Type(v).Daca Type(v) = ENi, atunci b(v) = (ENi,m), m marcare aretelei obiect ENi.

Daca v ∈ V ar({W (p, t)|p ∈ •t} si b(v) = (ENi,m) ∈ Tknet,spunem ca reteaua obiect ENi este implicata în producerealui t cu asignarea b.

– p. 13/52

Notatii

NPN = (A,L, SN, (EN1,m10), (EN2,m

20), . . . , (ENk,m

k0),Λ)

O asignare corespunzatoare unei tranzitii t in SN este oasignare b : V ar(t) → Tknet.

Daca E ∈ Expr(A) este o expresie si b o asignare, atunciE este expresia E evaluata în asignarea b:

E se obtine înlocuind fiecare x ∈ V ar(E) cu b(v)si fiecare constanta C cu I(C).E ∈ TkMS

O marcare a retelei NPN este o functie M care asociazafiecarei locatii din SN un multiset de elemente din Tk:M(p) ∈ TkMS .

– p. 14/52

Comportamentul NPN

Definitie 2 Fie NPN o retea pe niveluri.

O tranzitie t din SN este posibila la marcarea M cuasignarea b ddaca:

∀p ∈ •t : W (p, t) ≤ M(p)

Producerea tranzitiei t cu asignarea b modifica marcarearetelei în M ′, unde:

∀p ∈ P : M ′(p) = M(p)−W (p, t) +W (t, p)

– p. 15/52

Exemplu

t1 si b(x) = (EN1,m2), b(y) = (EN2,m)

W (P1, t1) = 1′x = 1′(EN1,m2) ≤ M(P1) =

1′(EN1,m1) + 1′(EN1,m2)

W (P2, t1) = 2′1 ≤ M(P2) = 3′1

W (P3, t1) = 1′y = 1′(EN2,m) ≤ M(P3) = 1′(EN2,m)

– p. 16/52

Exemplu

– p. 16/52

Exemplu

– p. 17/52

Exemplu

– p. 17/52

Comportamentul NPN

Definitie 3 (Pas de transport) Fie NPN o retea Petri peniveluri, M o marcarea a sa si t o tranzitie neetichetata din SN

(i.e. Λ(t) nedefinit). Daca t este posibila la marcarea M cu oasignare b, atunci producerea lui t în reteaua sistem SN senumeste pas de transport în NPN si se noteaza M [t[b]〉M ′.

Un pas de transport nu afecteaza marcarile retelelor obiect,modifica doar marcarea retelei SN .

– p. 18/52

Comportamentul NPN

Definitie 4 (Pas obiect-autonom) Fie M o marcare a NPN ,p ∈ P o locatie în SN . Fie (EN,m) un punct-retea din M(p). Fiet o tranzitie din EN posibila în m (conform cu regula deproducere a tranzitiilor din retele Petri clasice) astfel încâtm[t〉m′ si Λ(t) nu este definita. Atunci (; t) este un pasobiect-autonom posibil la marcarea M .

Marcarea rezultata prin producerea pasului, M ′, este obtinutadin M prin înlocuirea punctului-retea (EN,m) din p cupunctul-retea (EN,m′).

Se noteaza M [(; t)〉M ′.

– p. 19/52

Exemplu

Y = (; v1) pas obiect-autonom în M1

– p. 20/52

Exemplu

– p. 20/52

Comportamentul NPN

Definitie 5 (Pas de sincronizare orizontal a) Fie M o marcarea NPN , p ∈ P o locatie în SN si α1, α2, . . . , αn ∈ M(p) puncteleretea din M(p). Fie t1, . . . ts toate tranzitiile din aceste retelecare au aceeasi eticheta l ∈ Lh: Λ(t1) = Λ(t2) = . . . = Λ(ts) = l,astfel încât fiecare tranzitie tj (j ∈ {1, . . . , s}) este posibila înpunctul-retea αkj

= (ENj ,mj) ({k1, . . . ks} ⊆ {1, . . . , n}) din careface parte, si mj [tj〉m

′j .

Producerea simultana a tranzitiilor t1, . . . , ts se numeste pasde sincronizare orizontala.

Marcarea rezultata, M ′, se obtine din M prin înlocuireafiecarui punct-retea αkj

= (ENj ,mj) din p cu un noupunct-retea α′

kj= (ENj ,m

′j),∀j ∈ {1, . . . , s}.

Se noteaza M [(t1, . . . , ts)〉M ′.

– p. 21/52

Exemplu

Y = (u1, v2) pas de sincronizare orizontala posibil în M2

– p. 22/52

Exemplu

– p. 22/52

Exemplu

¬M2[(u1, v2)〉

– p. 23/52

Comportamentul NPN

Definitie 6 (Pas de sincronizare vertical a) Fie t o tranzitie dinSN , Λ(t) = l ∈ Lv, t posibil în M cu asignarea b si M [t[b]〉M ′.Fie α1, α2, . . . , αk ∈ Tknet toate punctele-retea implicate înproducerea lui t (α1 = (EN1,m1), . . . , αk = (ENk,mk))) cuproprietatea ca ∀ 1 ≤ i ≤ k, exista ti în ENi, astfel încâtΛ(ti) = l ∈ Lv si mi[ti〉m

Producerea simultana a tranzitiei t din SN si a tranzitiilort1, . . . , tk din punctele-retea α1, . . . , αk se numeste pas desincronizare verticala.

Marcarea rezultata este M ′:M ′(p) = (M(p)−W (p, t) ) +W ′(t, p) , pentruorice p din SN , unde W ′(t, p) este multisetul obtinutdin W (t, p) prin înlocuirea punctului-reteaαi = (ENi,mi) cu α′

i = (ENi,m′i), pentru toti 1 ≤ i ≤ k.

Se noteaza M [(t[b]; t1, . . . , tk)〉M′.

– p. 24/52

Exemplu

t2 si b(x) = (EN1,m1), b(y) = (EN2,m′′)

puncte retea implicate în producerea lui t2: (EN1,m1), (EN2,m′′)

Λ(t2) = b ∈ Labv, Λ(u2) = b ∈ Labv

M3[(t2[b];u2)〉

– p. 25/52

Exemplu

– p. 25/52

Exemplu

M3:Type(x) = EN1, Type(z) = EN1, Type(y) = EN2

Fie t2 si b(x) = (EN1,m1), b(z) = (EN1,m1), b(y) = (EN2,m′′)

puncte retea implicate în producerea lui t2: (EN1,m1), (EN1,m1), (EN2,m′′)

Λ(t2) = b ∈ Lv , Λ(u2) = b ∈ Labv

M3[(t2[b];u2, u2)〉

– p. 26/52

Exemplu

– p. 26/52

Exemplu

Type(x) = EN1, Type(z) = EN1, Type(y) = EN2

Y = t2 si b(x) = (EN1,m1), b(z) = (EN1,m2), b(y) = (EN2,m′′)

puncte retea implicate în producerea lui t2: (EN1,m2), (EN1,m3), (EN2,m′′)

Λ(t2) = b ∈ Lv, Λ(u2) = b ∈ Labv

¬M3[(t2[b];u2, u2)〉

– p. 27/52

Exemplu

– p. 28/52

Exemplu

– p. 28/52

Exemplu

– p. 28/52

Exemplu

– p. 28/52

Exemplu

– p. 28/52

Exemplu

– p. 28/52

Exemplu

– p. 28/52

Exemplu

– p. 28/52

Exemplu

– p. 28/52

Simularea retelelor cu resetare

Fie (N,R,m0) retea cu resetare

Pentru fiecare locatie p din reteaua cu resetare =⇒ o locatie P în SN , o variabilaxp si o retea obiect ENp

Pentru fiecare locatie care poate fi resetata, o constanta Ep (I(Ep) = (ENp, 0))

pentru fiecare tranzitie t, o tranzitie T în SN

daca t ∈ •p ∪ p• atunci (T, P ), (P, T ) ∈ FSN si WSN (P, T ) = WSN (T, P ) = xp.Daca t reseteaza p, WSN (T, P ) = Ep

Λ(T ) = l ∈ Labv si Λ(T ) este nedefinit ddaca t tranzitie izolata în N (i.e. doarreseteaza locatii)

– p. 29/52

M0(P ) = (EN,mp0), unde:

PEN = {p}

TEN = {t|t ∈ •p ∪ p•}

FEN = {(t, p)|(t, p) ∈ FN} ∪ {(p, t)|(p, t) ∈ FN}

Pentru orice f ∈ FEN , WEN (f) = WN (f)

mp0(p) = m0(p)

Λ(t) = l ∈ Labv (unde Λ(T ) = l)

– p. 29/52

Are loc: m[t〉Rm′ ddaca:

M [(T ; t(1), . . . , t(k))〉M′, daca t nu este tranzitie izolata (t(1), . . . , t(k) sunt

tranzitiile corespunzatoare lui t din retelele obiect corespunzatoare locatiilorincidente cu t) sau:

M [T 〉M ′, daca T este tranzitie neetichetata.

– p. 29/52

– p. 30/52

Retelele Petri pe niveluri simuleaza comportamentulretelelor Petri cu resetare

Problemele marginirii si accesibilitatii sunt nedecidabilepentru retele Petri cu resetare

Problemele marginirii si accesibilitatii sunt nedecidabilepentru retele Petri pe niveluri

– p. 31/52

Aplicatii în modelarea fluxurilor de lucru

Fluxuri de lucru interorganizationale:

WF1, . . . ,WFn fluxuri de lucru locale

WFi: actiuni locale, comunicare cu celelalte fluxuri de lucru:comunicare sincrona: actiuni din fluxuri de lucru diferitese produc simultancomunicare asincrona: ordine partiala pe actiuni dinfluxuri de lucru diferite, transmitere de mesaje între fluxride lucru

corectitudine (soundness)

– p. 32/52

– p. 33/52

Retea Petri pe niveluri:n obiecte reprezentând fluxurile de lucru locale + obiectcare descrie comunicarea asincronatranzitiile implicate în comunicare sunt etichetatetranzitiile din aceeasi multime de comunicare sincronaau o eticheta comuna

– p. 34/52

– p. 35/52

AC = {(t1, t2), (t2, t3), (t1, t4), (t4, t3), (t5, t4)}PAC = {ac1, ac2, ac3, ac4, ac5}TAC = {tc1, tc2, tc3, tc4, tc5}

– p. 36/52

– p. 37/52

– p. 38/52

Retele workflow extinse

Definitie 7 Fie WF = (P, T, F ) o WF-retea. Reteaua workflowextinsa este o retea WF ′ = (P, T ′, F ′), astfel încât :

T ′ = T ∪ {t′}

F ′ = F ∪ {(o, t′)}

– p. 39/52

Retele workflow interorganizationale

Fie (WF ′1, i1), . . . , (WF ′

n, in) retele workflow extinse si T ◦

multimea tuturor tranzitiilor (T ◦ = ∪k∈{1,...,n}Tk).

Fie SC si AC multimi de comunicare sincrona respectivasincrona:

SC ⊆ P(T ◦)

AC ⊆ T ◦ × T ◦ este o relatie de ordine partiala astfel încâtdaca (t, t′) ∈ AC, t ∈ Ti, t

′ ∈ Tj , atunci i 6= j

– p. 40/52

Retele workflow interorganizationaleO retea workflow interorganizationala este o retea Petri peniveluri:IWFN =(A,L, SN, (WF ′

1, i1), (WF ′2, i2), . . . , (WF ′

n, in), (AC, 0)Λ)astfel încât

1. A = V ar ∪ Con, Con = {1}, V ar = {x1, . . . , xn, xn+1}

2. Lv = {e, e}

3. (WF ′1, i1), (WF ′

2, i2), . . . , (WF ′n, in) sunt retele workflow

extinse

4. AC = (PAC , TAC , FAC) este o retea astfel încât :PAC = {pac|ac ∈ AC}.TAC = {tc|∃(t′, t) ∈ AC ∨ (t, t′) ∈ AC}.

FAC = {(pac, tc) ∈ PAC × T ◦|ac = (t′, t) ∈AC} ∪ {(tc, pac) ∈ T ◦ × PAC |ac = (t, t′) ∈ AC}

– p. 41/52

5. SN = (N,W,M0) este reteaua sistem a IWFN, astfel încât :N = (PN , TN , FN ):

PN = {I, p,O}, unde O este locatie astfel încâtO• = ∅ si I este locatie astfel încât •I = ∅.TN = {end}.FN = {(I, end), (p, end), (end,O)}.

W (I, end) = 1, W (p, end) = x1 + x2 + . . .+ xn+1,W (end,O) = 1.M0(I) = 1, M0(p) = ((WF ′

1, i1), . . . , (WF ′n, in), (AC, 0))

si M0(O) = 0.

– p. 42/52

6. Λ:∀x ∈ SC,∀t, t′ ∈ x,Λ(t) = Λ(t′) = l, l ∈ Lh.

daca t ∈ T ◦ astfel încât (t, t′) ∈ AC sau (t′, t) ∈ AC,atunci exista tc ∈ TAC : Λ(tc) = Λ(t) = l, l ∈ Lh.

Λ(t′i) = e,∀i ∈ {1, . . . n} si Λ(end) = e.

∀t, t′ ∈ Ti(i ∈ {1, . . . , n}) : Λ(t) 6= Λ(t′).

– p. 43/52

Corectitudine

Marcare finala a unei retele IWFN : Mf = (0, 0, 1)

Definitie 8 O retea workflow interorganizationalaIWFN = (A,L, (WF ′

1, i1), . . . , (WF ′n, in), (AC, 0), SN,Λ) este

sound ddaca:

1. (WF ′j , ij) este retea workflow extinsa sound,

∀j ∈ {1, . . . , n}.

2. (∀M)((M0[∗〉M) =⇒ (M [∗〉Mf )).

– p. 44/52

Structura cursului - profs.info.uaic.rootto/Referate/intro_NPN.pdf · – p. 1/52. Re¸tele Petri...

Documents