当前位置:首页 >> 理学 >>

000 Petri Net 讲义(英文)


Petri nets
Classical Petri nets: The basic model

Prof.dr.ir. Wil van der Aalst
Eindhoven University of Technology, Faculty of Technology Management, Department of Information and Technology, P.O.Box 513, NL-5600 MB, Eindhoven, The Netherlands.

/faculteit technologie management

Process modeling
? Emphasis on dynamic behavior rather than structuring the state space ? Transition system is too low level ? We start with the classical Petri net ? Then we extend it with:
– Color – Time – Hierarchy

/faculteit technologie management

Classical Petri net
? Simple process model
– Just three elements: places, transitions and arcs. – Graphical and mathematical description. – Formal semantics and allows for analysis.

? History:
– Carl Adam Petri (1962, PhD thesis) – In sixties and seventies focus mainly on theory. – Since eighties also focus on tools and applications (cf. CPN work by Kurt Jensen). – “Hidden” in many diagramming techniques and systems.
/faculteit technologie management

p4 place

Elements
(name) place

t34 p3

t43

transition

t23 p2

t32

(name)

transition

token

arc (directed connection)
t12 t21 p1

token

t01 p0

t10

/faculteit technologie management

free

Rules
wait enter before make_picture after leave gone

occupied

? ? ? ?

Connections are directed. No connections between two places or two transitions. Places may hold zero or more tokens. First, we consider the case of at most one arc between two nodes.

/faculteit technologie management

Enabled
? A transition is enabled if each of its input places contains at least one token.
free

wait

enter

before

make_picture

after

leave

gone

occupied

enabled
/faculteit technologie management

Not enabled

Not enabled

Firing
? An enabled transition can fire (i.e., it occurs). ? When it fires it consumes a token from each input place and produces a token for each output place. free
fired
wait enter before make_picture after leave gone

occupied

/faculteit technologie management

Play “Token Game”
? In the new state, make_picture is enabled. It will fire, etc.
free

wait

enter

before

make_picture

after

leave

gone

occupied

/faculteit technologie management

Remarks
? Firing is atomic. ? Multiple transitions may be enabled, but only one fires at a time, i.e., we assume interleaving semantics (cf. diamond rule). ? The number of tokens may vary if there are transitions for which the number of input places is not equal to the number of output places. ? The network is static. ? The state is represented by the distribution of tokens over places (also referred to as marking).
/faculteit technologie management

Non-determinism
t34

p4

p4

t43 p3

t34 p3

t43

t23 p2

t32 transition t23 fires

t23 p2

t32

t12 p1

t21

t12 p1

t21

Two transitions are enabled but only one can fire
/faculteit technologie management

t01 p0

t10

t01 p0

t10

Example: Single traffic light

rg

green

red

go

orange

or
/faculteit technologie management

Two traffic lights
rg rg

rg

green
green green

red

go

red

go

OR
orange

red

go

orange

or

or

orange

or
/faculteit technologie management

Problem

/faculteit technologie management

Solution
rg1 rg2

g1

g2

r1

go1

x

go2

r2

How to make them alternate?
or1

o1

o2

or2

/faculteit technologie management

Playing the “Token Game” on the Internet
? Applet to build your own Petri nets and execute them: http://www.tm.tue.nl/it/staff/wvdaalst/Downloads/ pn_applet/pn_applet.html ? FLASH animations: http://www.tm.tue.nl/it/staff/wvdaalst/courses/pm /flash/

/faculteit technologie management

Exercise: Train system (1)
? Consider a circular railroad system with 4 (oneway) tracks (1,2,3,4) and 2 trains (A,B). No two trains should be at the same track at the same time and we do not care about the identities of the two trains.

/faculteit technologie management

Exercise: Train system (2)
? Consider a railroad system with 4 tracks (1,2,3,4) and 2 trains (A,B). No two trains should be at the same track at the same time and we want to distinguish the two trains.

/faculteit technologie management

Exercise: Train system (3)
? Consider a railroad system with 4 tracks (1,2,3,4) and 2 trains (A,B). No two trains should be at the same track at the same time. Moreover the next track should also be free to allow for a safe distance. (We do not care about train identities.)

/faculteit technologie management

Exercise: Train system (4)
? Consider a railroad system with 4 tracks (1,2,3,4) and 2 trains. Tracks are free, busy or claimed. Trains need to claim the next track before entering.

/faculteit technologie management

WARNING
It is not sufficient to understand the (process) models. You have to be able to design them yourself !
/faculteit technologie management

Multiple arcs connecting two nodes
? The number of arcs between an input place and a transition determines the number of tokens required to be enabled. ? The number of arcs determines the number of tokens to be consumed/produced.
free

wait

enter

before

make_picture

after

leave

gone

/faculteit technologie management

Example: Ball game
red rb black

rr

bb

/faculteit technologie management

Exercise: Manufacturing a chair
? Model the manufacturing of a chair from its components: 2 front legs, 2 back legs, 3 cross bars, 1 seat frame, and 1 seat cushion as a Petri net. ? Select some sensible assembly order. ? Reverse logistics?
/faculteit technologie management

Exercise: Burning alcohol.
? Model C2H5OH + 3 * O2 => 2 * CO2 + 3 * H2O ? Assume that there are two steps: first each molecule is disassembled into its atoms and then these atoms are assembled into other molecules.

/faculteit technologie management

Exercise: Manufacturing a car
? Model the production process shown in the BillOf-Materials.
car subassembly2 engine 2 chair subassembly1 4 chassis
/faculteit technologie management

wheel

Formal definition
A classical Petri net is a four-tuple (P,T,I,O) where: ? P is a finite set of places, ? T is a finite set of transitions, ? I : P x T -> N is the input function, and ? O : T x P -> N is the output function. Any diagram can be mapped onto such a four tuple and vice versa.
/faculteit technologie management

Formal definition (2)
The state (marking) of a Petri net (P,T,I,O) is defined as follows: ? s: P-> N, i.e., a function mapping the set of places onto {0,1,2, … }.

/faculteit technologie management

Exercise: Map onto (P,T,I,O) and S
red rb black

rr

bb

/faculteit technologie management

Exercise: Draw diagram
Petri net (P,T,I,O): ? P = {a,b,c,d} ? T = {e,f} ? I(a,e)=1, I(b,e)=2, I(c,e)=0, I(d,e)=0, I(a,f)=0, I(b,f)=0, I(c,f)=1, I(d,f)=0. ? O(e,a)=0, O(e,b)=0, O(e,c)=1, O(e,d)=0, O(f,a)=0, O(f,b)=2, O(f,c)=0, O(f,d)=3. State s: ? s(a)=1, s(b)=2, s(c)=0, s(d) = 0.
/faculteit technologie management

Enabling formalized
Transition t is enabled in state s1 if and only if:

/faculteit technologie management

Firing formalized
If transition t is enabled in state s1, it can fire and the resulting state is s2 :

/faculteit technologie management

Mapping Petri nets onto transition systems
A Petri net (P,T,I,O) defines the following transition system (S,TR):

/faculteit technologie management

Reachability graph
? The reachability graph of a Petri net is the part of the transition system reachable from the initial state in graph-like notation. The reachability graph can be calculated as follows:
1. Let X be the set containing just the initial state and let Y be the empty set. 2. Take an element x of X and add this to Y. Calculate all states reachable for x by firing some enabled transition. Each successor state that is not in Y is added to X. 3. If X is empty stop, otherwise goto 2.
/faculteit technologie management

?

Example
red rb black

(3,2)

(3,1)

(3,0)

(1,3)
rr bb

(1,2)

(1,1)

(1,0) Nodes in the reachability graph can be represented by a vector “(3,2)” or as “3 red + 2 black”. The latter is useful for “sparse states” (i.e., few places are marked).
/faculteit technologie management

Exercise: Give the reachability graph using both notations
rg1 rg2

g1

g2

r1

go1

x

go2

r2

o1

o2

or1

or2

/faculteit technologie management

Different types of states
? Initial state: Initial distribution of tokens. ? Reachable state: Reachable from initial state. ? Final state (also referred to as “dead states”): No transition is enabled. ? Home state (also referred to as home marking): It is always possible to return (i.e., it is reachable from any reachable state). How to recognize these states in the reachability graph?
/faculteit technologie management

Exercise: Producers and consumers
? Model a process with one producer and one consumer, both are either busy or free and alternate between these two states. After every production cycle the producer puts a product in a buffer. The consumer consumes one product from this buffer per cycle. ? Give the reachability graph and indicate the final states. ? How to model 4 producers and 3 consumers connected through a single buffer? ? How to limit the size of the buffer to 4?
/faculteit technologie management

Exercise: Two switches
? Consider a room with two switches and one light. The light is on or off. The switches are in state up or down. At any time any of the switches can be used to turn the light on or off. ? Model this as a Petri net. ? Give the reachability graph.

/faculteit technologie management

Modeling
? ? ? ? Place: passive element Transition: active element Arc: causal relation Token: elements subject to change

The state (space) of a process/system is modeled by places and tokens and state transitions are modeled by transitions (cf. transition systems).
/faculteit technologie management

Role of a token
Tokens can play the following roles: ? a physical object, for example a product, a part, a drug, a person; ? an information object, for example a message, a signal, a report; ? a collection of objects, for example a truck with products, a warehouse with parts, or an address file; ? an indicator of a state, for example the indicator of the state in which a process is, or the state of an object; ? an indicator of a condition: the presence of a token indicates whether a certain condition is fulfilled.
/faculteit technologie management

Role of a place
? a type of communication medium, like a telephone line, a middleman, or a communication network; ? a buffer: for example, a depot, a queue or a post bin; ? a geographical location, like a place in a warehouse, office or hospital; ? a possible state or state condition: for example, the floor where an elevator is, or the condition that a specialist is available.
/faculteit technologie management

Role of a transition
? an event: for example, starting an operation, the death of a patient, a change seasons or the switching of a traffic light from red to green; ? a transformation of an object, like adapting a product, updating a database, or updating a document; ? a transport of an object: for example, transporting goods, or sending a file.

/faculteit technologie management

Typical network structures
? ? ? ? ? Causality Parallelism (AND-split - AND-join) Choice (XOR-split – XOR-join) Iteration (XOR-join - XOR-split) Capacity constraints
– Feedback loop – Mutual exclusion – Alternating

/faculteit technologie management

Causality

/faculteit technologie management

Parallelism

/faculteit technologie management

Parallelism: AND-split

/faculteit technologie management

Parallelism: AND-join

/faculteit technologie management

Choice: XOR-split

/faculteit technologie management

Choice: XOR-join

/faculteit technologie management

Iteration: 1 or more times

XOR-join before XOR-split
/faculteit technologie management

Iteration: 0 or more times

XOR-join before XOR-split
/faculteit technologie management

Capacity constraints: feedback loop

AND-join before AND-split
/faculteit technologie management

Capacity constraints: mutual exclusion

/faculteit technologie management

AND-join before AND-split

Capacity constraints: alternating

/faculteit technologie management

AND-join before AND-split

We have seen most patterns, e.g.:
Example of mutual exclusion
rg1 rg2

g1

g2

r1

go1

x

go2

r2

How to make them alternate?
/faculteit technologie management
or1

o1

o2

or2

Exercise: Manufacturing a car (2)
? Model the production process shown in the Bill-Of-Materials with car resources. ? Each assembly step engine requires a dedicated machine and an operator. ? There are two operators subassembly1 and one machine of each type. 4 wheel ? Hint: model both the start and completion of an assembly step.

subassembly2 2 chair

chassis
/faculteit technologie management

Modeling problem (1): Zero testing
? Transition t should fire if place p is empty.

t

?

p
/faculteit technologie management

Solution
? Only works if place is N-bounded
N input and output arcs

t p’

Initially there are N tokens

p
/faculteit technologie management

Modeling problem (2): Priority
? Transition t1 has priority over t2

t1

?
t2
/faculteit technologie management

Hint: similar to Zero testing!

A bit of theory
? Extensions have been proposed to tackle these problems, e.g., inhibitor arcs. ? These extensions extend the modeling power (Turing completeness*). ? Without such an extension not Turing complete. ? Still certain questions are difficult/expensive to answer or even undecidable (e.g., equivalence of two nets).
* Turing completeness corresponds to the ability to execute any computation.
/faculteit technologie management

Exercise: Witness statements
? As part of the process of handling insurance claims there is the handling of witness statements. ? There may be 0-10 witnesses per claim. After an initialization step (one per claim), each of the witnesses is registered, contacted, and informed (i.e., 0-10 per claim in parallel). Only after all witness statements have been processed a report is made (one per claim). ? Model this in terms of a Petri net.
/faculteit technologie management

Exercise: Dining philosophers
? 5 philosophers sharing 5 chopsticks: chopsticks are located in-between philosophers ? A philosopher is either in state eating or thinking and needs two chopsticks to eat. ? Model as a Petri net.

/faculteit technologie management


相关文章:
000 Petri Net 讲义(英文)_图文.pdf
000 Petri Net 讲义(英文) - Petri nets Classical Petri nets: The basic model Prof.dr.ir. Wil van der ...
04-PetriNet(1)_图文.ppt
04-PetriNet(1)_IT/计算机_专业资料。信息系统建模及企业流程再造 Lecture4 (...大量研究(>10.000 publications),至1985年,它主要被用于 理论界;自从80年中期...
信息系统建模 PetriNet_图文.pdf
经典的Petri net是由 Carl Adam Petri在 1962年的博士论文 <Communication with Automata >中提出的。 ? 大量研究(>10.000 publications),至1985年,它主要被用于...
analysis of Petri nets.pdf
For example, it is not surprising that a Petri net with a hundred places has 10,000 reachable states: its theoretical state space (2100) is ...
现代计算机网络讲义3(英语)+数据链路层_图文.ppt
现代计算机网络讲义3(英语)+数据链路层_工学_高等教育_教育专区。Chapter 3 ...? Finite State Machined Models Petri Net Models 3.5.1 Finite State Machined...
混合动力汽车英文讲义(牛津)Hybrid-Oxford_图文.ppt
混合动力汽车英文讲义(牛津)Hybrid-Oxford_广告/传媒_人文社科_专业资料。HYBRID ...2007 Hyundai Accent Hybrid MSRP $15,000 Hwy/City:45mpg 2007 Chevrolet ...
aspnet讲义_图文.doc
aspnet讲义_司法考试_资格考试/认证_教育专区。***静态网页,动态网页 静态网页...red black #000000 RGB:红绿蓝 #FFFFFF #FFFF00 ***文件信息(meta 放在头部...
Groebner Basis Procedures for Testing Petri Nets.pdf
Gr¨bner Basis Procedures for Testing Petri Nets o ? arXiv:math/0002119v...By using a Petri net to model the navigation system the C code ...
JIT生产系统Petri Net建模与仿真研究_图文.pdf
兰堡马汉武1 第3期 圣塑鱼±兰星 JIT生产系统PetriNet建模与仿真研究王建华1 ...(2)仿真时长为一年120000分钟。 (3)随机变量服从GAMMA分布。 (4)原材料及时...
Accounting会计学教程与案例讲义中英文对照Ch04第四章_....ppt
Accounting会计学教程与案例讲义英文对照Ch04第四章...? Device used for calculating net change Simplest...On hand at YE (12/31) are $3,000 of ...
基于Petri网的建模技术A_图文.ppt
经典Petri Net 3. 高阶Petri网 4. 一个Petri网建模实例 5.小结 2 1 Petri...大量研究(>10.000 publications),至1985年,它主要被用于 理论界;自从80年中期...
第一章PETRI 网简介_图文.ppt
? ? ? 闭卷考试 80% 大作业 20% 讲义及资料:nettheory@gmail.com ? 密码:nettheory111 课本:可选 ? ? ? 计算机网络理论及网络基础 张德运编著 Petri网...
A Petri Net Based Approach For Hardware Soft ware P....pdf
A Petri Net Based Approach For Hardware Soft ware Partitioning_专业资料。...{fmcf ,prmm,ensb}Qcin.ufpe.br 0-7695-1333-6101 $10.000 2001 E E...
基于Petri网的建模技术A.ppt
基于Petri 基于Petri网的建模技术 Petri网的建模技术 agenda 1 Petri Net概述 ...大量研究 大量研究(>10.000 publications),至1985年,它主要被用于 ,年 理论界...
自动制造系统Petri网模型SPN的化简_论文.pdf
在一类SPN自动制造系统(Automated Manufacturing System,简称AMS)Petri(Petri net...(000026 自动制 造 系统 Ptier 网模 型SN 的化 简 P岳 昊 ,李 文杰...
四自由度气动机械手的程序设计.pdf
从图 3 可知,幅度频率采用了 0~10 000 rad/s,...英文刊名: 年,卷(期): 引用次数: 蒋晓刚, 高岭...结果表明:3个子 PetriNet具有相同的结构性质,只要...
最大速度变化的连续Petri网(VCPN)的动态演变及性质判定....pdf
CoNTINUoUSPETRINET( VCPN) YEZio hBa0,ZHA0 u*,adIONG a eYiJnn )HunHe (mtueo otaehnsaey。 cesIitfSf'rCieeAcdmfSi BHn108)t wmeifg000 《(eao...
讲义1 计算机网络基础_图文.pdf
讲义1 计算机网络基础_工学_高等教育_教育专区。...Petri网 高等计算机 网络技术 实践 网络通信 网络...PRNET, SATNET; all long gone today IP runs...
基于Petri网的流程间元素映射方法_论文.pdf
基于Petri网的流程间元素映射方法_互联网_IT/计算机...000-9825/4773.htm 英文 引用格式 :Cao B,Wang ...net.Ruan Jian Xue Bao/Joumal of Software,2015,...
Petri网行为包含的业务流程模型查询优化分析_论文.pdf
16208/j. issn l000-7024. 2017. 02. 025 中图法分类号 : 1000-7024 (...Petri net behavior inclusion (1. College of Science, Anhui University of ...
更多相关标签: