第11讲_PT网和着色网(2)

1、DONG HUA UNIVERSITY Copyright DHU 2010工作流建模技术Petri Net(c2)管理学院 Copyright DHU 20102Main ContentslReviewlPlace/Transition SystemlColored Petri Net管理学院 Copyright DHU 20103Sequential Case Graph1 23 2e11 4e23 4e2e35 2e21 6e4e13 65 4e1e3e45 6e4 e3e6e5管理学院 Copyright DHU 20104Case Graphe5e3e3e25 7e3e1e57 2e

2、5e2e17 8e1 e2e4e63 4 5 61 5 62 3 4 66 3 4 81 6 81 2 6e5,e3e2,e3e1,e5e1,e2管理学院 Copyright DHU 20105State Space Similar1 23 2e11 4e23 4e2e35 2e21 6e4e13 65 4e1e3e45 6e4e3e6e5e5e3e3e25 7e3e1e57 2e5e2e17 8e1e2e4e63 4 5 61 5 62 3 4 66 3 4 81 6 81 2 6Can we find a pair of bijections :v1v1, and : ? such tha

3、t(v1) =v1(c1, A, c2)Y1 iff ( (c1), (A), (c2) Y1管理学院 Copyright DHU 20106ComplementsCondition b1, b2 are complements of each other, b1=b2 iff e E, b1 e iff b2 e and e E, b1 e iff b2 eb1b2b3e1e2e3b4e4e5e6b5According to the above definition, give out the complements of the b1,b2,b3,b4, and b5管理学院 Copyri

4、ght DHU 20107ConstructionLet N =(B,E,F,Cin) be EN systemLet B be a set disjoint with BE,and let :BB be a bijectionThe S-complementation of N is the EN system N =(B,E,F,Cin) such that B=BB, E=E, F=F (e, (b):eE&(b,e) F (b),e) :eE&(e,b) F,Cin=Cin (B-Cin)管理学院 Copyright DHU 20108Constructionb1b2b3b4管理学院

5、Copyright DHU 20109Main ContentslReviewlPlace/Transition SystemlColored Petri Net管理学院 Copyright DHU 201010Folding a Nett8t1t2t4t6t3t7t5s0s1s2s4s3s9s5s8s6s7t8t1t3t7t5s0s1s3s9s5t8t1/t2t3/t4t7t5/t6s0s1/s2s3/s4s9s5/s6s7/s822管理学院 Copyright DHU 201011Omit some Detailst8t1/t2t3/t4t7t5/t6s0s1/s2s3/s4s9s5/s6

6、s7/s822t1/t2/s3/s4t3/t4t7t5/t6s0/t8/s9s1/s2s5/s6s7/s822t8t1/t2/s3/s4t3/t4t7s0s1/s2s9s5/s6s7/s822t5/t6管理学院 Copyright DHU 201012Control structure of Vending MInsertcoinReady for insertionHoldingcoinRejectcoinAcceptcoinDispenseitemReady todispense管理学院 Copyright DHU 201013A Vending Machine with Capacity

7、 4 InsertcoinReady for insertionHoldingcoinRejectcoinAcceptcoinReady todispenseMove1 Move2 Move3 =4Dispenseitem管理学院 Copyright DHU 201014Place/Transition NetMarked place/transition nets generalize EN SystemTerminologyEN SystemConditionEventCaseSCGMarked P/T NetPlaceTransitionMarkingMarking Graph管理学院

8、Copyright DHU 201015Definition of Marked Place/Transition NetA marked place/transition net is a tuple N=(S, T, F, k, w, M0) where(1)(S, T, F) is a net S, set of Places; T, set of Transitions(2)k: S1,2,3, (3)w:F1,2,3,(4)M0:S0,1,2,3,Capacity restrictionWeight function Are the transition t is enabled?s

9、1s2t2M(s1)K(s2)管理学院 Copyright DHU 201018Question 2Let P/T Net , (S, T, F, k, w, M0 ) A transition t T is enabled. The occurrence of t leads to the successor marking m:s S,m(s) = m(s) w(s,t)if s t - t m(s) = m(s) + w(t,s)if s t - tm(s) = m(s) w(s,t) + w(t,s)if s t tm(s) = m(s)if s t t管理学院 Copyright D

10、HU 201019Marking GraphLet P/T Net , (S, T, F, k, w, M0 )The marking graph of a marked P/T Net is an edge-labeled graph with initial vertex, (M, Y), M0)M0initial vertexinitial markingMverticesset of reachable markingsYlabeled-edgesset of triples(m,t,m), mtm管理学院 Copyright DHU 201020t1/t2/s3/s4t3/t4t7t

11、5/t6s0/t8/s9s1/s2s5/s6s7/s822Example of Marking Graph t1t2t3p2p1p3p422(2,1,0,0)(1,1,1,0)t1t1(0,1,2,0)(0,1,0,2)t2(1,1,0,1)t3t3管理学院 Copyright DHU 201021Main ContentslReviewlPlace/Transition SystemlColored Petri Net管理学院 Copyright DHU 201022Folding the Net Furthert8t1/t2t3/t4t7t5/t6s0s1/s2s3/s4s9s5/s6s7

12、/s822t8t1/t2t3/t4t7t5/t6s0s1/s2s3/s4s9s5/s6s7/s822t1/t2t3/t4t7t5/t6/t8s0/s1/s2s3/s4s5/s6s7/s8/s9222管理学院 Copyright DHU 201023Behavior of the Examplet1/t2t3/t4t7t5/t6/t8s0/s1/s2s3/s4s5/s6s7/s8/s922(3,0,0,0)(1,1,0,0)(1,0,1,1)2(2,0,1,0)(0,1,1,0)(0,0,2,1)(0,0,0,3)(1,0,2,0)(1,0,2,0)(1,0,0,2)(2,0,0,1)(0,1,

13、0,1)(0,0,1,2)管理学院 Copyright DHU 201024Adding Constraintst1/t2t3/t4t7t5/t6/t8s0/s1/s2s3/s4s5/s6s7/s8/s9+DeclarationsType S12 = S1 | S2Type S123 = S0| S1 | S2Var x, u: S12Var y: S123管理学院 Copyright DHU 201025Marking with Multi Sett1/t2t3/t4t7t5/t6/t8s0/s1/s2s3/s4s5/s6s7/s8/s9+Sets and Multi SetA set ha

14、s unordered elements, and only one occurrence of an elementsA multi set, or a bag, allows more than one occurrence of an elements Tokens in s0/s1/s2 2+1+12+管理学院 Copyright DHU 201026Behavior with Constraintst1/t2t3/t4t7t5/t6/t8s0/s1/s2s3/s4s5/s6s7/s8/s9+DeclarationsType S12 = S1 | S2Type S123 = S0| S

15、1 | S2Var x, u: S12Var y: S123(+,-,-,-)(,-,-)(,-,)(+,-,-)( -, ,-)(-,-,+ , )(-,-,-, + )(+,-,-,-)(,-,-)(,-,)(+,-,-)( -, ,-)(-,-,+ , )(-,-,-, + )(,-,-)(,-,)(+,-,-)( -, ,-)( ,-,+ ,-)( ,-,-, +)管理学院 Copyright DHU 201027Colored Petri Net EN System and P/T Net has no types and no modules - Only one kind of

16、tokens- With more elements in the model With colored Petri Net(CP-Nets) it is possible to use data types and complex data manipulation:- Each token has attached a data value called the token colors- The token colors can be investigated and modified by the occurring transitions管理学院 Copyright DHU 2010

17、28Example of Colored Petri Net Education For MSEMSEABCDEs0s3t1s4t2t3s5t0s1s2管理学院 Copyright DHU 201029Definition of CP Net Declarations- Types, Functions, Operations and Variables Each place has the following inscription - Name(for identification)- Color set(specifying the type of token may reside on

18、 the place)- Initial marking(multi-set of token colors)管理学院 Copyright DHU 201030Definition of CP Net(1) Each transition has the following inscriptions- Name(for identification)- Guard(boolean expression containing some of the variables) Each arc has the following inscriptions- Arc expression(contain

19、ing some of the variables) When the arc expression is evaluated it yields a multi-set of token colors管理学院 Copyright DHU 201031Constructs for CP NetArc ExpressionDeclarationsNameColor SetInitial MarkingNameGuardSTF管理学院 Copyright DHU 201032Resource Allocation System Tow kinds of processes- 3 cyclic q-

20、processes(states A,B,C,D,E)- 2 cyclic p-processes(states B,C,D,E) Three kinds of resources- Represented by the places R, S and T During a cycle a process reserves some resources and release them again- Tokens are removed form and added to the resource places R, S and T管理学院 Copyright DHU 201033A CP N

21、et for RAS管理学院 Copyright DHU 201034Binding Binding(绑定)- A binding assigns a color( a value) to each variable of a transition Binding Element(绑定元素)- A binding element is a pair(t, b) where t is transition while b is a binding for the variables of t- Example: (T2, )管理学院 Copyright DHU 201035Enabled and Firing A binding element is enabled iff- There are enough tokens(of the correct colors on each input place)- The Gu