Զѧ
ACTA AUTOMATICA SINICA
1999ꡡ255ڡVol.25 No.5 1999



һPETRIʱܼ򻯷1)
־֣
ժҪʵϵͳPetriģмʱγTPNϵͳʱTPNԾҪ.ΪϵͳܷͼĸԣڷֽķϽṹ򻯷̽־ͬʱֽ֮ʱܵĹϵһЩͽṹļ㷨.
ؼʡTPNʱ䣬ͬ.
REDUCTION METHOD FOR TIME ANALYSIS OF A CLASS
OF PETRI NETS
XU ZhibinZHENG Dazhong
(Automation Department,Tsinghua University,Beijing100084)
AbstractIn the physical system,it is necessary to add time factor into model,and cycle time is important in the performance analysis.In order to decrease complexity of analysis and computation,we propose a decomposing method with structure reduction.When there are synchronized links between subnets,the cycle time compute algorithm and reduction method of special structure are given in detail in this paper.
Key wordsTPN, elementary net, cycle time, synchronized link.
1
ʵϵͳĹģӴֱӽϵͳԵļ㽫¼ά.ף1һC/Eṹͻ·ȡϵͳʱ.ף2¼ͼһ𲽼ϵͳṹȡϵͳʱķ.ĻPetriķֽ⣬ṹ򻯺ṹӷϵͳʱܣṹ򻯵ķʱܵĹϵ.
2
1. һʱ䣬ʱָNӱʶMʼ޳ͻṹÿһǨٷһΣֻصʶMҪСʱ䣻гͻṹ䰴ͻṹ֧·ֽΪ޳ͻṹN1NkʱΪʱֵ.
TPNĶʱصķһ֣ڱǨмʱ䣻λмʱ䣻ͬʱλúͱǨмʱ.ַЧȡһֱ﷽ܷ.Ϊڲ״̬ͽṹʱTokenĿȡֵΪ01.ھжػѭPetriȲPETRIȼ۱任任Ϊñķм򻯷.
Petriض壬ڵǰ󼯡ԡԺнԵȲμף3ݣTPNμף5.
3ᡡ
۷ֽĴСF/JͲеȽṹļ򻯣ÿֽṹΪпϺп.ṹμף4.
3.1ʱ̶
3.1.1򵥴нṹ
򵥴нṹΪSB(PTIO)λõλõĽṹΪ򻯽ͼ1ʾ.


ͼ1򵥴нṹļ
ͼ1֪λõλõĴнṹ򻯳һλã򻯺λԭṹ¹ϵ
(1)
(2)
ʼڵΪλáֹڵΪǨʼڵΪǨֹڵΪλõĴнṹɼΪһλpһǨt,
(p)=Ʀp(pi),(t)=Ʀt(tj),M(p)=M(pi).(3)
ʼֹڵ㶼ǱǨĴнṹΪһǨ
(4)
пʱҪýṹصλ.֣ṹʼǨΪt1ֹǨΪtnпΪML=M(pi)
1) t1ǰλп
(5)
2) tnλп
С(6)
1. PetriNеĴнṹΪN䣬N䱣NнԡԡظԺʱ.
֤. ֤.
3.1.2F/Jṹ
F/JṹΪF/JB(PTIO)򻯽ͼ2ʾ.


ͼ2F/Jṹļ
ͼ2֪ɵF/Jṹ򻯳һǨԭṹ֧·ӳʱпĿΪ
(7)
(8)
ṹпʱʱĶ֪¹ϵ
(9)
ṹпʱҪte1ǰλûte2ĺλõпϵο.崦μף5.
2. PetriNеF/JṹΪN䣬N䱣NнԡԡظԺʱ.
֤. ɱǨ֤.
3.1.3򵥲нṹ
򵥲нṹΪPB(PTIO)򻯽ͼ3.


ͼ3򵥲нṹļ
ͼ3֪нṹ򻯳һλãṹ֧·
(10)
(11)
ṹпʱйϵ
(12)
ṹпʱ´
1) ṹи֧·3.1.1ΪӦıǨti,pe2п
2) kʹæt(tk)=MAX1im((ti));
3) 򻯺λpӳʱΪp(p)=t(tk)+p(pe1)+p(pe2)M(p)=M(pe1)+M(pe2)+1kmML(k).
3. PetriNеĲнṹΪN䣬N䱣NнԡԡظԺʱ.
֤. ɱǨ֤.
3.1.4ڻṹ
ڻṹΪIL(PTIO)ʽΪte1ݣU1kmSB(Pk,Tk,Ik,Ok)ݣte2ݣU1jmSB(Pj,Tj,Ij,Oj)ݣte1.ȷڻṹͼ4ʾڻṹļ򻯽.


ͼ4ڻṹļ


ͼ5ܼ򻯵ڻṹ
ڻṹڵΪte1,te2·λΪǨΪpk,0,pk,1,,pk,nktk,1,tk,2,,tk,nk-1ӳʱڻṹпڻѭʱΪ
TL=t(te1)+t(te2)+ƣƦp(pi,k)+Ʀt(ti,k)(13)
ML=ơ0knkMp(pi,k),(14)
L=TL/ML.(15)
te1,te2һṹĹΪ뻡Σte2ṹΪǨt
t(t)=t(te1)+t(te2)+Ʀp(p1,k)+Ʀt(t1,k),(16)
(17)
(18)
(N)=max(N),L.(19)
te1,te2뻡ṹ Σ÷֤֤һ㲻ܼΪһǨ.֤μף5.
4. PetriNеڻṹΪN䣬N䱣NнԡԡظԺʱ.
֤. ɱǨ֤.
3.2ʱ㶯
Ʒʱ㶯ʱṹļ򻯷.ǨӳʱΪΪDT(t)ʣtmin,tmaxݣͬλӳʱΪDT(p)ʣpmin,pmaxݣʱΪ㶯(N)ʣۦmin(N),max(N).ɣ1) λõпĿֲʱ̶ʱⷽ2) 򻯺ıǨλü·ӳʱ䣬㷽̶ͬʱļ㣬ֻ½ʱֱñǨλõӳʱСֵֵ⣻3) ڼ򻯲нṹF/JṹʱжñǨλõֵСֵвͬεж.
3.3ļ
ӽṹͻĶף5.ɼ򵥴нṹнṹF/Jṹݹɣ򻯷Բ÷ֲֲ򻯷ʵ֣Ҫ£1) ԭNǰ򻯼ͷ򵥽ṹ򻯣2) 򻯺Nʱָ״̬򻯺γɵıǨλõӳʱصλõıʶ3) ظֱNɽһΪֹ4) 򻯺ΪN壬ǰ򻯷֪N޼򵥴֧·ͼ򵥲֧·ٸݻ·Nʱ.
3.4ͬӵܼ򻯷
ͬӸμף4ݣʱļϵ.
5. N1,N2,NnͨͬγɵNӦͼG޻·NkʱΪ(k)ʱ=max1kn(k).
֤. ʱĶͻ·㷽֤.
6. N1,N2,,NnͨͬγɵNӦͼGл·NkʱΪ(k),ʱ=maxmax1kn(k),max1kmL(k1)L(k2),mΪԲͬӵ·L(k1)L(k2)Ϊk·ͬ·ʱ.
֤. ף5и˱ĽһӦãƪ֤.
4ᡡ
Դģʱܷ⣬ûڲ״̬ⲿͽṹֽϵķзԴСļ㸴.˼ֻṹļ򻯷Խͬӵʱļ㷽.һṹҲɲгļ򻯣ȻԼ򻯺м㣬ܼС㸴.
1) Ȼѧ(69684001)͹ʵǼƻĿ.
߼飺־У1970.1993廪ѧԶϵƱҵֱϵۼӦרҵʿѧλ.оΪDEDSķͿƣPetriӦ.
֣ӡУ1935.Ϊ廪ѧԶϵڡʿʦԶѧ.оΪϵͳۣϵͳɢƣϵͳ³ԣDEDS϶̬ϵͳ.
ߵλ廪ѧԶϵ100084
ο
1Freedman P.Time,Petri nets,and Robotics.IEEE Trans.Robotics and Automation,1991,7(4),417433
2Zhou M C.Reduction of Timed Marked Graphs and Its Applications to Manufacturing Systems.IEEE Int.Conf.on Robotics and Automation, 1994
3Reisig W.Petri Nets:an Introduction,Springer Verlag,1982
4־֣.ͬPetriַܱ.1996CCC飬ൺ1996
5־.һDEDSܺΪPetri۲ʿģ.廪ѧ1997
ոڣ1996-10-07
޸ڣ1998-05-15
