Retele Petri

Retele Petri si Aplicatii

Curs 4

RPA (2015) Curs 4 1 / 48

Cuprins

1 Analiza structurala a retelelor Petri

Sifoane

Capcane

Proprietati

2 Modelarea fluxurilor de lucru: retele workflow

Retele workflow

3 Proprietatea de corectitudine (soundness) n retele workflow

RPA (2015) Curs 4 2 / 48

Analiza structurala a retelelor Petri

Cuprins


Sifoane

Capcane

Proprietati


Retele workflow


RPA (2015) Curs 4 3 / 48

Analiza structurala a retelelor Petri Sifoane

Sifoane

Definitie 1

Fie N = (P, T, F,W ) o retea si R P o multime de locatii. R se

numeste sifon daca R R. Un sifon este propriu, daca R 6= .

RPA (2015) Curs 4 4 / 48


Sifoane

Definitie 1



p1

t1

p2

t2

t3 p3

t4

p4

t5

RPA (2015) Curs 4 4 / 48


Sifoane

Definitie 1



p1

t1

p2

t2

t3 p3

t4

p4

t5

{p1, p2} = {t1, t2}, {p1, p2} = {t1, t2, t3}

{p1, p2} {p1, p2} = {p1, p2} sifon.

RPA (2015) Curs 4 4 / 48


Proprietatea fundamentala sifoanelor

Notatie: fie R P o multime de locatii si M o marcare.

M(R) =

pR M(p)

RPA (2015) Curs 4 5 / 48




M(R) =

pR M(p)

Definitie 2

Fie N = (P, T, F,W ) o retea, R P un sifon propriu si M o marcare a

lui N . R este marcat n marcarea M , daca M(R) 6= 0.

RPA (2015) Curs 4 5 / 48




M(R) =

pR M(p)

Definitie 2

Fie N = (P, T, F,W ) o retea, R P un sifon propriu si M o marcare a

lui N . R este marcat n marcarea M , daca M(R) 6= 0.

Propozitie 1 (Proprietatea fundamentala sifoanelor)

Fie N = (P, T, F,W ) o retea si R P un sifon propriu. Fie M o marcare

a retelei astfel ncat M(R) = 0. Atunci, M [M, M (R) = 0.

RPA (2015) Curs 4 5 / 48


Exemplu

p1

t1

p2

t2

t3 p3

t4

p4

t5

[M0 = {(0, 0, 1, 0), (0, 0, 0, 1)}, {p1, p2} nu sunt marcate niciodata.

RPA (2015) Curs 4 6 / 48


Proprietati

Fie = (N,M0) o retea P/T marcata , R un sifon si M [M0.

Daca M0(R) = 0, atunci M(R) = 0

Se obtine o conditie necesara pentru accesibilitate

Daca R sifon pentru care M0(R) = 0 si M(R) 6= 0, atunci M 6 [M0.

p1

t1

p2

t2

t3 p3

t4

p4

t5

R = {p1, p2} sifon cu M0(R) = 0 marcarea M = (1, 0, 0, 1) nu este

accesibila.RPA (2015) Curs 4 7 / 48


Proprietati

Propozitie 2

Fie = (N,M0) o retea P/T marcata pentru care W (f) = 1, f F si

M o marcare a sa. Daca M este marcare moarta, atunci multimea de

locatii R = {p P |M(p) = 0} este sifon propriu.

RPA (2015) Curs 4 8 / 48


Proprietati

Propozitie 2




p1

p2

p3

p4

p5

t2t1

t3t4

M = (0, 1, 0, 0, 0) este marcare moarta, deci {p1, p3, p4, p5} sifon .

M = (1, 0, 0, 0, 0) este marcare moarta, deci {p2, p3, p4, p5} sifon

RPA (2015) Curs 4 8 / 48


Proprietati

Propozitie 2




Propozitie 3

Fie N = (P, T, F,W ) o retea Petri. Daca x este P-invariant al lui N , atunci suportul

sau, ||x||, este sifon.

RPA (2015) Curs 4 8 / 48

Analiza structurala a retelelor Petri Capcane

Capcane-definitie

Definitie 3


numeste capcana daca R R. O capcana este proprie, daca R 6= .

RPA (2015) Curs 4 9 / 48


Capcane-definitie

Definitie 3


numeste capcana daca R R. O capcana este proprie, daca R 6= .

p1

t1

p2

t2

t3 p3

t4

p4

t5

{p3, p4} este capcana.

RPA (2015) Curs 4 9 / 48


Propozitie 4

Fie N = (P, T, F,W ) o retea Petri si R P o capcana proprie. Fie M o

marcare a retelei astfel ncat M(R) 6= 0. Atunci, M [M, M (R) 6= 0.

RPA (2015) Curs 4 10 / 48


Propozitie 4



p1

t1

p2

t2

t3 p3

t4

p4

t5

{p3, p4} este capcana.

Locatiile p3, p4 raman marcate n orice marcare accesibila din M0.

RPA (2015) Curs 4 10 / 48


Propozitie 4



Propozitie 5

Fie N = (P, T, F,W ) o retea Petri. Daca x este P-invariant al lui N ,

atunci suportul sau, ||x||, este capcana.

RPA (2015) Curs 4 10 / 48


Fie = (N,M0) o retea P/T marcata , M [M0 si R o capcana.

Daca M0(R) 6= 0, atunci M(R) 6= 0.

Se obtine o conditie necesara pentru accesibilitate

Data o marcare M si R capcana cu M0(R) 6= 0, daca M(R) = 0,

atunci M 6 [M0

p1 t1

p2

p3

t2

t4

p4t3

t5p5

R = {p1, p2, p3} capcana, M0(R) 6= 0.

M = (0, 0, 0, 1, 0) 6 [M0 (M(R) = 0)

RPA (2015) Curs 4 11 / 48


Caracterizare capcane

Propozitie 6

O multime R de locatii este capcana ddaca, pentru orice tranzitie t:

| t| |R t | |R t|

p1 t1 p3

t2t3

t4p4

p2

R = {p1, p3, p4} nu este capcana: | t2| |R t2 | = 0 < |R t2| = 1

RPA (2015) Curs 4 12 / 48

Analiza structurala a retelelor Petri Proprietati

Conditie necesara pentru viabilitate

Propozitie 7

Fie = (N,M0) o retea P/T marcata viabila. Orice sifon R este marcat

la M0.

RPA (2015) Curs 4 13 / 48



Propozitie 7

Fie = (N,M0) o retea P/T marcata viabila. Orice sifon R este marcat

la M0.

p1t1

p2t2

p3

t3

p4

p5

t4

{p3, p4} nemarcat n marcarea initiala, deci reteaua nu este viabila.

RPA (2015) Curs 4 13 / 48



Reciproca nu este adevarata:

Sifoane:

{p1, p2, p3}

{p1, p2, p3}

Reteaua nu este viabila.RPA (2015) Curs 4 14 / 48


Conditie suficienta pentru lipsa blocajelor

Propozitie 8

Fie = (N,M0)o retea P/T marcata cu W (f) = 1, f F . Daca orice

sifon propriu al lui N include o capcana marcata n M0, atunci este fara

blocaje.

RPA (2015) Curs 4 15 / 48



Propozitie 8

Fie = (N,M0)o retea P/T marcata cu W (f) = 1, f F . Daca orice

sifon propriu al lui N include o capcana marcata n M0, atunci este fara

blocaje.

p1

p2

p3

p4

p5

t2t1

t3t4

Sifoane: {p1, p3, p4, p5}, {p2, p3, p4, p5}, {p2, p3, p4}, {p2, p3}

Capcane: {p2, p3}, {p1, p3, p4, p5}, {p1, p2, p3}

Retea fara blocaje.

RPA (2015) Curs 4 15 / 48



Reciproca nu este adevarata:

p1 p2 p3t1

t2

t3 t4

Retea fara blocaje

Sifoane proprii: {p1, p2} nu include nici o capcana!

Capcane proprii: {p3}

RPA (2015) Curs 4 16 / 48

Modelarea fluxurilor de lucru: retele workflow

Cuprins


Sifoane

Capcane

Proprietati


Retele workflow


RPA (2015) Curs 4 17 / 48


Fluxuri de lucru

Flux de lucru(workflow): proces complex care se desfasoara n

cadrul unei organizatii:

actiuni executate ntr-o anumita ordine

date utilizate, prelucrate, produse de actiuni

resurse necesare executiei actiunilor

RPA (2015) Curs 4 18 / 48


Fluxuri de lucru

Flux de lucru(workflow): proces complex care se desfasoara n

cadrul unei organizatii:

actiuni executate ntr-o anumita ordine

date utilizate, prelucrate, produse de actiuni

resurse necesare executiei actiunilor

Sisteme de administrare a fluxurilor de lucru (WFMS): permit

definitia fluxurilor de lucru si asigura executia acestora

RPA (2015) Curs 4 18 / 48


Exemplu

RPA (2015) Curs 4 19 / 48


Flux de lucru - notiuni / componente

Caz: instanta a fluxului de lucru, subiectul operatiilor din cadrul

fluxului de lucru (exemplu: o cerere de decontare);

Actiune: operatie atomica realizata n cadrul fluxului de lucru;

Resursa: executa actiunile;

Work item: actiune + caz (actiune care se poate executa pentru un

anumit caz);

Activitate: actiune + caz + resursa (actiune care este executata

ntr-un anumit caz, de catre o resursa);

Structuri de control al executiei: dependenta logica ntre actiuni;

RPA (2015) Curs 4 20 / 48


Structuri de control al executiei

Secventa:

A B

AND-split

A

B

CAND - split

D

AND-joinA

B

C

DAND - join

OR-split

A

B

C

OR - Split

OR-join

A

B

COR - join

RPA (2015) Curs 4 21 / 48


Perspective asupra fluxurilor de lucru

Perspectiva proces: actiuni, ordinea de executie

Perspectiva resurselor: resurse, modul de organizare, modul n care

resursele sunt alocate pentru executia actiunilor

Perspectiva datelor:

date pentru controlul executiei

date create/utilizate de catre actiuni

RPA (2015) Curs 4 22 / 48


Analiza fluxurilor de lucru

Validare: n momentul executiei.

Verificare: determinarea unor proprietati calitative ale procesului,

nainte de executia/implementarea acestuia:

exista blocaje?

executia unui caz se poate ncheia cu succes?

se pot executa toate actiunile din proces?

Analiza performantei procesului:

numarul de cazuri care pot fi procesate ntr-o anumita perioada de timp

timpul mediu de procesare al unui caz

RPA (2015) Curs 4 23 / 48


Limbaje de specificare a fluxurilor de lucru

Sistemele de administrare a fluxurilor de lucru lucreaza cu definitii ale

fluxurilor de lucru, exprimate ntr-un anumit limbaj de specificare

Abordari utilizate pentru descrierea proceselor:

Limbaje dependente de produsul software

Diagrame UML

Grafuri

BPMN

Limbaje bazate pe XML: BPEL, XPDL

Algebre de procese

Retele Petri

RPA (2015) Curs 4 24 / 48


Retele Petri n modelarea fluxurilor de lucru

Retele workflow:

modeleaza perspectiva proces, se face abstractie de resurse si date

modelarea executiei unui singur caz

Retele Petri de nivel nalt pentru modelarea celorlalte perspective

(perspectiva resurselor si cea a datelor)

RPA (2015) Curs 4 25 / 48


Retele Petri n modelarea fluxurilor de lucru

actiuni: modelate prin tranzitii

caz: punct in retea

preconditii si post-conditii pentru producerea actiunilor: locatii

work item: tranzitie posibila ntr-o anumita stare

activitate: tranzitie care se executa

structuri de control ale executiei: locatii sau tranzitii

RPA (2015) Curs 4 26 / 48


Modelarea structurilor de control

A B = A B

A

B

CAND - split

D

=A

B

C

D

AND-Split

A

B

CAND - split

D

=A

B

C

D

AND - split

RPA (2015) Curs 4 27 / 48



A

B

C

DAND - join

A

B

C

DAND - join

A

B

C

D

AND - join

RPA (2015) Curs 4 28 / 48



A

B

C

D

EAND-Split AND-join

A

B

C

D

AND - split

E

AND-join

RPA (2015) Curs 4 29 / 48



A

B

C

OR - Split = A

B

C

OR - split

A

B

C

OR - Split =A

B

C

OR - split

RPA (2015) Curs 4 30 / 48



A

B

COR - Split

OR - Split

D

E

RPA (2015) Curs 4 31 / 48



A

B

CD

E

RPA (2015) Curs 4 31 / 48



A

B

D

E

C

RPA (2015) Curs 4 31 / 48



A

B

COR - join

A

B

COR - join

RPA (2015) Curs 4 32 / 48

Modelarea fluxurilor de lucru: retele workflow Retele workflow

Definitia retelelor worklfow

Definitie 4

O retea workflow (WF-retea) este o retea Petri PN = (P, T, F ) astfel

ncat:

1 P contine o locatie input i si o locatie output o astfel ncat i = si

o = .

2 Pentru orice element n P T , exista un drum n PN de la i la n si

un drum de la n la o.

RPA (2015) Curs 4 33 / 48


Retele workflow

io

t1

p1

p2

t2

t3

t4

p3

p4

t4

io

p4

p1

t1

p2

p3

t4

t3

t2

p5 t5

RPA (2015) Curs 4 34 / 48


Observatii

W (x, y) = 1, pentru orice (x, y) F .

Notatii:

Marcarea initiala, M0, a unei retele workflow:

M0(i) = 1,M0(p) = 0, p 6= i.

Se noteaza M0 = i

Marcarea finala a, Mf , unei retele workflow:

Mf (o) = 1,Mf (p) = 0, p 6= o.

Se noteaza Mf = o

RPA (2015) Curs 4 35 / 48


Exemplu

RPA (2015) Curs 4 36 / 48


Exemplu

RPA (2015) Curs 4 37 / 48

Proprietatea de corectitudine (soundness) n retele workflow

Cuprins


Sifoane

Capcane

Proprietati


Retele workflow


RPA (2015) Curs 4 38 / 48


Proprietatea de corectitudine logica

verif client

inreg. date client nou

i

o

client depune cerere

preia date

calc impozit

emite ordin plata

Tranzitia calc impozit nu se poate produce

Cazul nu poate fi procesat

RPA (2015) Curs 4 39 / 48



verif client


i

o


preia date

calc impozit

emite ordin plata

calcul impozit cl nou

Exista o secventa de executie catre marcarea finala

Exista situatii n care cazul nu poate fi procesat corect

RPA (2015) Curs 4 40 / 48



i

client depune cerere inreg

date OK

date gresite

recompleteaza

inregistreaza

inreg date

Procesul se termina, dar cazul nu este procesat corect.

RPA (2015) Curs 4 41 / 48


Corectitudine logica (soundness) n fluxuri de lucru

Intr-un flux de lucru executia unui caz trebuie sa se poata termina

ntotdeauna

RPA (2015) Curs 4 42 / 48


Corectitudine logica (soundness) n fluxuri de lucru

Intr-un flux de lucru executia unui caz trebuie sa se poata termina

ntotdeauna

Nu exista actiuni inutile (orice actiune trebuie sa se poata produce la

un moment dat)

RPA (2015) Curs 4 42 / 48


Definitia proprietatii de corectitudine

Definitie 5

O retea workflow PN = (P, T, F) este corecta (sound) ddaca:

1 M [i, o [M (conditia de terminare corecta)

2 t T , t este pseudo-viabila

RPA (2015) Curs 4 43 / 48



Definitie 5




verif client


i

o


preia date

calc impozit

emite ordin plata

RPA (2015) Curs 4 43 / 48



Definitie 5




verif client


i

o


preia date

calc impozit

emite ordin plata

calcul impozit cl nou

RPA (2015) Curs 4 43 / 48


Inchiderea unei retele workflow

Definitie 6

Fie PN = (P, T, F ) o WF-retea. Inchiderea retelei PN este o retea

PN = (P , T , F ), astfel ncat :

P = P

T = T {t}

F = F {(o, t), (t, i)}

PN

t*

i o

PN este retea tare conexa.

RPA (2015) Curs 4 44 / 48


Proprietati

Lema 3.1

Fie PN = (P, T, F ) o retea workflow pentru care are loc conditia de

terminare corecta. Atunci au loc:

1 (M [i)(M o M = o)

2 (PN, i) este marginita.

3 multimea marcarilor accesibile din (PN, i) coincide cu multimea

marcarilor accesibile din (PN, i).

4 (PN, i) este pseudo-viabila ddaca (PN, i) este pseudo-viabila.

RPA (2015) Curs 4 45 / 48


Caracterizare soundness

Lema 3.2

Fie PN = (P, T, F ) o WF-retea sound. Atunci (PN, i) este retea viabila

si marginita.

RPA (2015) Curs 4 46 / 48



Lema 3.2

Fie PN = (P, T, F ) o WF-retea sound. Atunci (PN, i) este retea viabila

si marginita.

Demonstratie:

1 Din Lema 3.1(2) = (PN, i) este marginita. Cum [iPN = [iPN (Lema 3.1(3)), rezulta (PN, i)marginita.

2 Se arata ca PN este reversibila si pseudo-viabila.

RPA (2015) Curs 4 46 / 48



Lema 3.3

Fie PN = (P, T, F ) o WF-retea. Daca (PN, i) este retea viabila si

marginita, atunci PN este sound.

RPA (2015) Curs 4 47 / 48



Lema 3.3

Fie PN = (P, T, F ) o WF-retea. Daca (PN, i) este retea viabila si

marginita, atunci PN este sound.

Demonstratie:

1 Fie M [iPN . Se arata ca exista T astfel ncat M [PNo.

2 Se arata ca orice tranzitie este pseudo-viabila.

RPA (2015) Curs 4 47 / 48



Teorema 1

O WF - retea PN este corecta ddaca (PN, i) este viabila si marginita.

RPA (2015) Curs 4 48 / 48



Teorema 1


Consecinta 1

Problema corectitudinii este decidabila pentru WF-retele.

RPA (2015) Curs 4 48 / 48



Teorema 1


Consecinta 1

Problema corectitudinii este decidabila pentru WF-retele.

Observatie:O WF-retea este corecta ddaca:

marcarea o este marcare acasa

reteaua este pseudo-viabila

RPA (2015) Curs 4 48 / 48

Analiza structurala a retelelor PetriSifoaneCapcaneProprietati

Modelarea fluxurilor de lucru: retele workflowRetele workflow


Retele Petri

Documents

Transcript of Retele Petri