Pli 2004 Geschäftsprozessmodellierung: Petri-Netze1Petri-Netze mathematisch fundierte Theorie zur formalen Beschreibung von (Informations-) Transformationsprozessen

Pli 2004 1Geschäftsprozessmodellierung: Petri-Netze

Petri-NetzePetri-Netze mathematisch fundierte Theorie zur formalen

Beschreibung von (Informations-) Transformationsprozessen

Entwicklung einer allgemeinen Theorie, die auf den Konzepten der Nebenläufigkeit, der Verteiltheit und der asynchronen Kommunikation aufbaut

Ursprung: Dissertationsschrift „Kommunikation mit Automaten“ von Carl Adam Petri (1962)

Seit Mitte der 80er Jahre vermehrter Einsatz in praktischen Anwendungen


Petri-NetzPetri-Netz

Ein Petri-Netz ist ein gerichteter bipartiter Graph, bestehend aus zwei disjunkten Mengen von Knoten

Stellen

Transitionen

sowie

Kanten

Marken (engl. „token“)


Petrinetze: Formale DefinitionPetrinetze: Formale Definition

Ein Petri-Netz ist ein Tripel N = (S,T,F) mit S (Stellen), T (Transitionen) sind endliche Mengen S T = S T F (S x T) (T x S) ist eine binäre Relation über S T

In einem Petri-Netz folgen Stellen und Transitionen jeweils abwechselnd

Eine Stelle kann mehrere Transitionen als Nachfolger haben und umgekehrt


Grundlagen von Petri-Netzen: KnotenGrundlagen von Petri-Netzen: Knoten

Stelle(Platz, Zustand)

entspricht einer Zwischenablage

Transition(Hürde, Zustandsübergang)

beschreibt die Verarbeitung

Stelle

Transition

Marke

Stelle mit Marken

Ausgabestellen von t

t

Eingabestellen von t

t

Stelle

Transition

Marke

Stelle mit Marken


t


t

Bedeutung im Modellierungskontext:Datenspeicher

Bedeutung im Modellierungskontext:Aktivität


Grundlagen von Petri-Netzen: KantenGrundlagen von Petri-Netzen: Kanten

Die Kanten dürfen jeweils nur von einer Sorte zur anderen führen

Stellen, von denen Kanten zu einer Transition t laufen, heißen Eingabestellen von t.

Stelle

Transition

Marke

Stelle mit Marken


t


t

Stellen, zu denen – von einer Transition t aus – Kanten führen, heißen Ausgabestellen von t

Stelle

Transition

Marke

Stelle mit Marken


t


t

Bedeutung im Modellierungskontext:Kontroll- und Datenfluss


Stelle

Transition

Marke

Stelle mit Marken


t


t

Objekte werden als Marken (Token) bezeichnet und als kleine schwarze Kreise in die Stellen des Petri-Netzes eingetragen

Grundlagen von Petri-Netzen: MarkenGrundlagen von Petri-Netzen: Marken

Bedeutung im Modellierungskontext:Informationsträger, Datenobjekt


Interpretation von Petrinetzen: ProzesseInterpretation von Petrinetzen: Prozesse

Transitionen Aktionen, Handlungen

Stellen Bedingungen bzw. Zustände

Verbindungen Vor- und Nachbedingungen von

Aktivitäten

Marken Zustände einer Bedingung oder zu bearbeitende Objekte

Markierungen lokale Zustände

Bestellungeingetroffen

Warenzusammenstellen

Warenverschicken

Rechnungschreiben

Wareversandfertig

Wareverschickt

Bestellungbearbeitet

Beispiel: Bestellprozess (vereinfacht)


Interpretationen von PetrinetzenInterpretationen von Petrinetzen

Logistik Transitionen

Transporte, Transformationen

Stellen Materialbehälter, Lager

Verbindungen Start und Ziel von

Transporten

Marken Güter

Datenverarbeitung Transitionen

Anweisungen, Programme

Stellen Speicher, Register, Puffer

Verbindungen Ein- Ausgabe von

Programmen

Marken Informationsobjekte


Grundlagen von Petri-Netzen: Schalten von Grundlagen von Petri-Netzen: Schalten von TransitionenTransitionen

Stelle = Zwischenablage von Daten Transition = Verarbeitung von Daten

Eingabestelle von t Ausgabestelle von t

tS1 2S

Marke

Anschauliche Vorstellung der Schaltregel:

verbinden verbindenverbinden verbinden

Schaltregel:a Eine Transition t kann schalten oder »feuern«, wenn jede Eingabestelle

von t mindestens eine Marke enthältb Schaltet eine Transition, dann wird aus jeder Eingabestelle eine Marke

entfernt und zu jeder Ausgabestelle eine Marke hinzugefügt.


Beispiele: SchaltenBeispiele: Schalten

Nicht aktiviert

t1

aktiviert

t2schalten

t2

Synchronisation: Die Transition schaltet nur, wenn beide Stellen markiert sind.


Petri-Netze modellieren Zustände und Petri-Netze modellieren Zustände und ZustandsübergängeZustandsübergänge

Beispiel: Verkehrsampel

rot

rot-gelb

grün

gelb


Beispiel: SchaltfolgeBeispiel: Schaltfolge


Verschiedene Arten von Petri-NetzenVerschiedene Arten von Petri-Netzen In Abhängigkeit von der Art der Objekte unterscheidet man:

Bedingungs/Ereignis-Netze (B/E-Netz) Stellen/Transitions-Netze (S/T-Netz) Höhere Petri-Netze


Bedingungs/Ereignis-NetzeBedingungs/Ereignis-Netze

B/E-Netz Wenn die Objekte bzw. Marken vom Datentyp

boolean sind Die Transitionen werden als Ereignisse interpretiert Die Stellen werden als Bedingungen bezeichnet Jede Stelle kann entweder genau eine oder keine

Marke enthalten

Zusätzliche Schaltbedingung: Eine Transition t kann schalten, wenn jede Eingabestelle

von t eine Marke enthält und wenn jede Ausgabestelle von t leer ist.


Bedingungs/Ereignis-NetzeBedingungs/Ereignis-Netze Beispiel

Zwei Roboter bestücken Leiterplatten mit elektronischen Bauelementen, die auf einem Fließband A antransportiert werden

Fließband A Fließband B

Roboter 1

Roboter 2

Montage-Platz 1

Montage-Platz 2


Bedingungs/Ereignis-Netze: BeispielBedingungs/Ereignis-Netze: Beispiel

bestückteLeiterplatteist bereit zumAbtransport

Leiterplatte bestücktdurch Roboter 1

unbestückteLeiterplatte isteingetroffen

Legende:AnfangsmarkierungMarkierung vor dem Schalten

unbestückte Leiterplatteantransportieren

Roboter 1ist frei

Roboter 1 ergreiftdie Leiterplatte

Roboter 1 legt dieLeiterplatte ab

bestückte Leiterplatteabtransportieren

Leiterplatte bestücktdurch Roboter 2

Roboter 2ist frei

Roboter 2 ergreiftdie Leiterplatte

Roboter 2 legt dieLeiterplatte ab

B/E-Netz des Bestückungsroboters

Nach demSchalten


Stellen/Transitions-NetzeStellen/Transitions-Netze

S/T-Netze (P/T Net, Place/Transition Net) Stellen können mehr als eine Marke enthalten (in B/E-Netzen

nur eine Marke) Transitionen müssen so viele Marken beim Schalten

wegnehmen oder hinzufügen, wie die Gewichte an den Pfeilen angeben (in B/E-Netzen nur eine Marke)

Soll eine Stelle eine Kapazität größer 1 erhalten, dann wird dies durch »K = ...« an der Stelle notiert

Die Kapazität definiert die maximale Anzahl von Marken, die auf einer Stelle liegen dürfen


Schaltbedingungen bei Stellen/Transitions-NetzenSchaltbedingungen bei Stellen/Transitions-Netzen T1 kann schalten: Anschl. sind in S1 eine Marke, in S2 4 Marken und in S3 2 Marken

T2 kann nicht schalten, da in S3 dann 3 Marken liegen würden. Dies ist wegen K = 2 von S3 nicht erlaubt.

a bK=3

K=4K=22 2

2TS1S2S3

K=3K=4K=22 2

2TS1S2S3

2

a bK=3

K=4K=22 2

2TS1S2S3

K=3K=4K=22 2

2TS1S2S31

a bK=3

K=4K=22 2

2TS1S2S3

K=3K=4K=22 2

2TS1S2S31


Strukturelemente & StrukturenStrukturelemente & StrukturenLöschen vonObjekten

Erzeugen vonObjekten

WeitergabeVerarbeitung vonObjekten

AufspaltenVervielfachen vonObjekten,Beginn einerNebenläufigkeit

Verschmelzen vonObjekten,Ende einerNebenläufigkeit,Synchronisationspunkt

Gemeinsamer Speicherfür Objekte,Synchronisationsstelle

Tote Stelle,Ablegen inein Archiv

Quelle, Reservoirfür Objekte

Zwischenablage,Zwischenspeicher

WillkürlicheVerzweigung,nichtdeterministischeFortsetzung einesProzesses undoderBeginn einerNebenläufigkeit

Löschen vonObjekten

Erzeugen vonObjekten

WeitergabeVerarbeitung vonObjekten

AufspaltenVervielfachen vonObjekten,Beginn einerNebenläufigkeit

Verschmelzen vonObjekten,Ende einerNebenläufigkeit,Synchronisationspunkt

Gemeinsamer Speicherfür Objekte,Synchronisationsstelle

Tote Stelle,Ablegen inein Archiv

Quelle, Reservoirfür Objekte

Zwischenablage,Zwischenspeicher

WillkürlicheVerzweigung,nichtdeterministischeFortsetzung einesProzesses undoderBeginn einerNebenläufigkeit


Strukturelemente & StrukturenStrukturelemente & Strukturen

Übergang

Kopplung über einegemeinsame Transi-tion

Kopplung über einegemeinsame Stelle

Verzweigung

Vereinigung

Kopplung über eineKommunikations-stelle (dynamischeEntkopplung)

Übergang



Verzweigung

Vereinigung


Übergang



Verzweigung

Vereinigung


Übergang



Verzweigung

Vereinigung



Typisches Anwendungsmuster:Typisches Anwendungsmuster:Sequentielles RoutingSequentielles Routing

A B

„Erst A dann B“


Typische Anwendungsmuster: Typische Anwendungsmuster: Parallelität und VerzweigungParallelität und Verzweigung

Neben-läufigkeit

Nicht-determiniert-heit

GegenseitigerAusschluß

einseitigeSynchron-isation

t1

t2

t3

t4

t1

t2

t3

t4

t1

t2

t3

t4

t5

t6

...

t1

t3

t2

b

Neben-läufigkeit




t1

t2

t3

t4

t1

t2

t3

t4

t1

t2

t3

t4

t5

t6

...

t1

t3

t2

b

Paralleles Routing:

„t2 und t3 nebenläufig und in beliebiger Reihenfolge“

AND-split AND-join

Verzweigung / Alternativen:

OR-split OR-join

„t2 oder t3“: Implizite Auswahl, es ist nicht definiert, ob t2 oder t3 schaltet.(d.h. die genaue Verzweigung steckt implizit in den Transitionen)


Nicht-DeterminismusNicht-Determinismus

Ein Konflikt tritt auf, wenn zwei Transitionen die gleiche Marke benötigen

Wir benötigen eine Erweiterung der Petri-Netze für expliziten OR-split!

t1

t2

OR-split


A B

Wiederholung von A

A B

C

Wiederholung von C und A

IterationIteration

OR-split

OR-join

Beachte: Implizite Auswahl bei OR-split (vgl. Modellierung von Alternativen / Auswahl)

OR-split

OR-join


Strukturelemente & StrukturenStrukturelemente & Strukturen

Neben-läufigkeit




t1

t2

t3

t4

t1

t2

t3

t4

t1

t2

t3

t4

t5

t6

...

t1

t3

t2

b

Neben-läufigkeit




t1

t2

t3

t4

t1

t2

t3

t4

t1

t2

t3

t4

t5

t6

...

t1

t3

t2

b


Analyse von Petri-Netzen: ErreichbarkeitAnalyse von Petri-Netzen: Erreichbarkeit Eine Stelle heisst markiert, wenn sie mit einer Marke belegt ist

Die Markierung m eines Netzes N ist die Menge aller markierten Stellen

Falls eine Transition t aus T unter einer Markierung m aktiviert ist, kann t schalten. Das führt zu einer Folgemarkierung m‘

Schreibweise: m -t-> m‘

Falls m -t1-> m1, m1 -t2-> m2, ..., mn-1 -tn-> mn Schaltvorgänge sind, dann ist t = t1t2 ... tn eine Schaltfolge

Wir sagen m‘ ist von m erreichbar (geschrieben m -*-> m‘), falls es eine Schaltfolge t gibt so dass m -t-> m‘

Eine Markierung heisst Endzustand, wenn keine Transition aktiviert ist.


Beispiel: ErreichbarkeitBeispiel: Erreichbarkeit

rr: aus zwei rotenein schwarzes

bb: verbraucheschwarz

rot schwarz

br: rot verbrauchtschwarz

Die Anzahl der Kanten zwischen zwei Objekten entspricht der Anzahl der Marken, die verbraucht/produziert werden

So können Verarbeitungsprozesse modelliert werden.

Übergangsgraph:7 erreichbare Markierungen, 1 Endzustand

(3,2)

(1,3) (3,1)

(1,2) (3,0)

(1,1)

(1,0)

bb, brrr

br

rr

rr

bb, br

bb, br

Anzahl der Markenin Stelle rot

Anzazhl der Markenin Stelle schwarz


High-level PetrinetzeHigh-level Petrinetze

High-level Petrinetze sind erweiterte Petrinetze:

Unterscheidbare Marken (colored tokens) zur Modellierung von Attributen expliziter OR-split

Zeit zur Performance Analyse verschiedene Zeitkonzepte

Hierarchie zur Strukturierung der Modelle Modellierung auf verschiedenen Abstraktionsebenen


High-Level Petri-Netze: Unterscheidbare High-Level Petri-Netze: Unterscheidbare MarkenMarken

Frei

BeschäftigtWartend Start Beenden Beraten

Name: MüllerFunktion: BeraterErfahrung: 2

Name: MeyerWohnort: Olten

Eine unterscheidbare Marke: stellt ein Objekt mit einer Menge von Attributen dar beinhaltet Werte für alle Attribute


High-level Petrinetze: Explizite Routing-High-level Petrinetze: Explizite Routing-ErweiterungenErweiterungen

AND-split AND-join

OR-split OR-join

Split und Join sind speziell dargestellte Transitionen

Der explizite OR-split ist eine spezielle Transition, die die Folgestelle auswählt auf Grund von Attributwerten der Eingangsmarke


Beispiel für expliziten OR-splitBeispiel für expliziten OR-split

Prozess: Kreditbearbeitung

If Betrag > 50.000then Genehmigung durch Abteilungsleiterelse Kreditwürdigkeitprüfung

KreditantragName: MüllerBetrag: 20.000 Genehmigung durch

Abteilungsleiter

Kreditwürdig-keitsprüfung

Benötigt Attribute als Entscheidungskriterium


Prädikat/Transitions-NetzePrädikat/Transitions-Netze Pr/T-Netze

Verwenden individuelle, »gefärbte« Marken B/E- und S/T-Netze verwenden nur »schwarze« Marken, die

alle gleich sind

z

b nachher

Schaltbedingung

Schaltwirkung

8

4

5 3

17

1

4210

x

y

a vorher

x = 2 y

z = 2 x + y20

5 3

17

1

4210

x

y

x = 2 y

z = 2 x + y

zz

b nachher

Schaltbedingung

Schaltwirkung

8

4

5 3

17

1

4210

x

y

a vorher

x = 2 y

z = 2 x + y20

5 3

17

1

4210

x

y

x = 2 y

z = 2 x + y

z


Zeitbehaftete Petri-NetzeZeitbehaftete Petri-Netze Verschiedene Notationsmöglichkeiten

Eine Marke wird erst nach einer Verzögerung von4 Zeiteinheiten wirksam

delay 4 delay 4

a b

delay 4 delay 4

a b

Die Transition kann erst 4 Zeiteinheiten nach dem Eintreffen der Marke in der Eingangsstelle feuern


Zeitbehaftete Petri-NetzeZeitbehaftete Petri-Netze

Beispiel

bearbeiten

WerkstückRohstoffe

Arbeiterdelay 10 sec


High-level Petrinetze: Hierarchische High-level Petrinetze: Hierarchische ModellierungModellierung

Mechanismus, um komplexe Petrinetze zu strukturieren (vgl. Prozeduren, Unterprogramme)

Wiederverwendung von Teilnetzen

Frei

BeschäftigtStart Beenden

PauseStart Beenden

Wartend Beraten

PauseStart Beenden


FUNSOFT-NetzeFUNSOFT-Netze

Vertreter eines workflow-orientierten Petri-Netz-Typs entwickelt von der Fraunhofer Gesellschaft (Institut für Software

und Systemtechnik, Deiters et al.) Token Typisierung möglich Unterschiedliche Zugriffsstrategien auf Stellen (Kanäle) Unterschiedliches Schaltverhalten von Transitionen

spezifizierbar Aktivitäten (modelliert durch Transitionen) können Attribute

haben wie z.B. Zeitverbrauch Ausführungsmodus (manuell, automatisch) Anzahl simultaner Ausführungen Verfeinerungsmodus

Formale Semantik durch definierte Abbildung auf Pr/T Netze


Beispiel eines FUNSOFT-NetzesBeispiel eines FUNSOFT-Netzes


Petri-Netze: WertungPetri-Netze: Wertung Vorteile

+ bestehen aus wenigen und einfachen Elementen+ sind grafisch gut darstellbar+ Marken erlauben eine gute Visualisierung des jeweiligen

Systemzustands+ besitzen ein solides theoretisches Fundament+ können – im beschränkten Rahmen – analysiert und simuliert

werden+ einziges weit verbreitetes Basiskonzept zur Modellierung

kooperierender Prozesse

Nachteile– Für die Praxis sind höhere Petri-Netze nötig, aber keine

einheitliche Notation– Petri-Netze sind mit anderen Basiskonzepten bisher nicht

kombiniert worden, d.h. es ist ein vollständig für sich stehendes Konzept


Petri-Netze: WertungPetri-Netze: Wertung

Petri-Netze eignen sich besonders gut zur Modellierung von Systemen mit kooperierenden Prozessen

Synchronisationen zwischen nebenläufigen Systemen können durch eine geeignete Netzstruktur erzwungen werden

Sie werden auch für die Vorgangsmodellierung von Bürovorgängen eingesetzt (workflow). Produkte, z.B.

LEU (Lion Entwicklungsumgebung) INCOME (Promatis) COSA (Software Ley) Nucleus (Baan)


Übersetzungsregeln EPK - High-level Übersetzungsregeln EPK - High-level PetrinetzePetrinetze

Ereignis

Funktion

Stelle

Transition

Schaltungsregel

Nicht vorhanden

Nicht vorhanden

Marke

AND-Split, AND-Join

OR-Split, OR-Join

UND-Split,UND-Join

ODER-Split, ODER-Join

XOR XOR XOR-Split, XOR-Join

High-level Petrinetze Ereignisgesteuerte Prozessketten

Documents

Pli 2004 Geschäftsprozessmodellierung: Petri-Netze1Petri-Netze mathematisch fundierte Theorie zur formalen Beschreibung von (Informations-) Transformationsprozessen