Զѧ
AGTA AUTOMATICA SINICA
1999 25 2 Vol.25 No.2 1999



ɢװϵͳĻԿ1)
Ͽ塡
ժҪ״оɢװϵͳĻԿ.ϵͳĹӹPetriģ.ͨϵͳPetriģ͵Ľṹ˵ϵͳԪؽṹ.һɢװϵͳ˱Petriʵ֣ϵͳС,ʹܿϵͳԾPetriģ.һɢװϵͳ˱֤ϵͳԵĿƲ.
ؼʡϵͳ,Petri,.
LIVENESS CONTROL FOR DISCRETE MANUFACTURING
/ASSEMBLY SYSTEMS
XING Keyi
(Department of Applied Mathematics, Xidian University, Xi'an710071)
HU Baosheng WAN Baiwu
(Institute of Systems Engineering, Xi'an Jiaotong University, Xian 710049)
AbstractThe liveness problem for discrete manufacturing/assembly systems is studied first in this paper. We develop a Petri net model for processings of jobs in a manufacturing/assembly system. By analysis of the Petri net model, two kinds of structural objects which can lead to system deadlock and the liveness characteristics of the system are obtained. We then present our deadlock- avoidance Petri net controller for a class of manufacturing/assembly systems. This controller can be implemented easily and places less restrictive requirement on systems. And the controlled system can be modeled by a Petri net. For a general manufacturing/assembly system, we present a policy which can guarantee that the controlled system is live.
Key wordsManufacturing system, Petri net, control.
1
PetriģͽϵͳĻΪѧߵȤ17.ף15ݶϵͳPetriģ˱ĿƲ,ʹܿϵͳвٷ.ף6,7ֱӽϵͳPetriģ,ԴΪϵͳеļ.Щоڡԡϵͳ,ҪڼӹйȲֽ⣬Ҳ.ϵͳǼӹװһģйĽǱزٵ.
омӹװܵɢϵͳĻԿ.PetriΪϵͳģϵͳ͵ϵͳPetriṹԪأ˱֤ϵͳԵĿۺϷ.
2װϵͳPetriģ
PetriһԪGPTFPTֱλüͱǨFPTȣTP򻡼.aPT.aa.ֱʾaԪؼ.abPTbaFa.bPTabF..aba.bʱΪ.aba.b.ԼAPTǡA.a,A.=a..ãGm0ʾгʼʶm0ıPetriG.mGıʶtTmp1p.tʱtǱʶmʹܵ.ʹܱǨtʹϵͳӱʶmתƵʶm䣬m䣨pmpt.p-tp.mtm.ZGm0ʾGܴm0ıʶ֮.mZGm0APmAm(p).
mZ(G,m0),mZ(G,m)ʹtmʹ,tǻ.ԱʶmmZ(G,m)ʹtmʹ,tm.ÿǨǻ,(G,m0)ǻ;(G,m0).
ĿǵװϵͳԴR,ĲƷ༯ΪQ,ÿƷһЩԭϾӹװ.ԭϼΪI,һԭϽһֲƷ.ÿֲƷиԵ̣һЩɣÿβԴһ.ѵĳԴĲΪӹ.Ѷװһ¹Ĺ̳Ϊװ.Ʒ̾һϵеļӹװ.ÿһԴļӹԴ಻ͬ.
ϵͳPetriģУһλñʾһβñǨʾתʾʼǵ˳ϵλǨĻʾ.ÿλýһǨһǨÿǨҲһλ.һǨһӹʼʱһλãһװʼʱж1λ.PTֱǲλüͱǨ.ÿԭiIһλãϵͳԭiĹΪıǨʾλãепʾõiԭ.TIʾбǨ֮.ÿֲƷjQһƷλԴŸòƷ.PIPQֱԭλüͲƷλü.ƷPetriģGP£


1) PPIPQǿգ
2) PIҽһλáPQʹôӵΨһһ·
3) pPPI.pp.1pPQ.p1p.0
4) TI.0tiI.piItTt.1.t1.
ƾж1λõıǨΪϱǨ.ϱǨӦŶװһĲ̵Ŀʼ.
ÿԴrһԴλãԼΪr.PRԴλ֮.λpĹԴrʱRprGP뻡бǨtԴrʹãrt,trͬʱڣɾȥ.FRʾӻ֮.ϵͳPetriģΪ

Gĳʼʶm0Ϊm0p0pPPQPIm0rCrrPRCrΪrԴ.ѣGm0ΪϵͳPetriSPNSystem Petri Net.
tTãttpttrtpֱʾtPR.tɣPPIt.PRt.ɣPPQ.ЩǺſչϣBTrB(r)t.rPR,H(r)=pPR(p)=r.
ϱǨtλúĳλͬһԴʱ,(r)t=.
mZ(G,m0),p(p)t,m(p)1,tTmʹ.(r)t=m((r)t)1,tmԴʹ.ֻй̺Դͬʱʹʱ,Ǩ.
3SPNĽṹԷ
SPNĽṹʼ.
1. 裨Gm0һSPN.Gһ·Уp1t1,,pktkΪP-·piPi1krp1.
2. 裨Gm0һSPN.Gһչ·E-·ݹ鶨Ϊ1) һP-·һE-·2) 1p11t11,,p1kt1k,2p21t21,p2lt2lE-·R)Rp21ʱУ12ҲE-·.
P,TзֱʾE-·еλ֮бǨ֮.

FTУбǨʹϣPУпӣLTУбǨ٦ϵп.
RУRPУR(p),ϲλԴ֮.
3. E-·=p1t1,,pntnΪһDͽṹ,tLT(У,R(t(p))R((p)tP),R(p1)=(r)tn.DͽṹһѭE-·.
1. һDͽṹ,

=pPУpΪP-·pt1p1,,tkpk,k1,piP,R(pi)=R(p),i=1,,k,(p)tPУ 2,Sһsiphon.Sɦɵsiphon(֤).
4. tT,rR,BH(r),BѴBtE-·YΪһYͽṹ,YһÿpBtE-·.FR(Y)=r,LT(Y)=t.P-·,E-·Yͽṹ.
5. һWͽṹΪһYͽṹP-·ĽW=Y11Y22,,Ynn:1) YiYͽṹ,iP-·.ʼW=(YW,W)2) FR(i)=FR(Yi+1),i=1,2,,n-1,FR(n)=FR(Y1)3) LT(Yi)=LT(i),i=1,,n4) Yi,jLT(Yi),LT(j)ûйͬԪ.

2. WһWͽṹ,

дpΪP-·SWһsiphon.SWWɵsiphon.(֤)
,ֱʾDͺWͽṹ֮.ڱʶmµǨDT(m)ǿ.õݹ,(G,m0).tDT(m),֮һس.
a. tԴʹ,(r)t=r,m(r)=0;
b. tԴʹܶǹʹ,(r)t=(r)t=r,m(r)1,p(p)t,m(p)=0.
aʱ,p1,p2,,pkH(r)ʹm(pi)0,m(pi)=m0(r).=ti,Ǧi=piti,T1=t1,,tk,1=i,i=1,,k.
bʱ,ÿPIбǨɹʹ,P-·=p1t1,,pktkptʹm(pi)=0,i=1,,k,k0,.p1=t0ǹʹܵ.t0ǷԴʹܵ.(r)t0=r1,m(r1)=0.a,q1,,qkH(r1)ʹm(qi)0,m(qi)=m0(r1).=si,Ǧ1=qisi,i=1,,l,2=У,T1=si,i=1,,l.
ٶT1еÿǨظϷ.Ϊ,ñʾѷ̵ıǨ֮,ʼ=.tiT1,iʦ1,ti=LT(i),Σ
1) tiԴʹ,(r)ti=ri,m(ri)=0.aķ֪,q1,,qkH(ri),m(qi)0,m(qj)=m0(ri).=sj,iͨqjsjչΪkE-·iqjsj,j=1,,k.1=(1ܣi)ȣiqjsj,j=1,,k,T1á=T1ȣsj,j=1,,k,á=ti.
2)(r)ti=(r)ti=ri,m(ri)0.tiһϱǨҷǹʹ.P-·=p1s1,,pktiʹm(pj)=0,j=1,,k,t0=.p1m¹ʹ.R(p1)=r,m(r)=0,Ҵq1,,qlH(r)ʹm(qj)0,m(qj)=m0(r).=xj,1=1ȣqjxj,j=1,,l,2á=2ȣУ,T1á=T1ȣxj,j=1,,l,=ȣti.
ظϷ,ֱT1=.GıǨ,бǨڶγT1֮,Ϊ˼,tһֵıǨ.tʼķ֪,2=ʱ,1һЩչ·,ʱչ·,ӦһǨϷõҲһǦ.ӶһDͽṹ,rR(P)m(r)=Cr.ɦɵsiphon Sзǿ.2ʱ,12һWͽṹW,ʹSWΪ.
ϵķ֤¶1,2.
1. (G,m0)һSPN,mZ(G,m0),DT(m),֮һ.


GDͻWͽṹYʱ,(G,m0)Ľṹ֪,һпɴʶmZ(G,m0)ʹYɵsiphonΪ.YбǨmΪ.ɴ˿ԸSPN».
2.(G,m0)һSPN,(G,m0)ǻĳֱҪGвκDͻWͽṹ.
4SPNĻԿ
(G,m0),ͼ1ʾӽṹ,еĺϱǨtԶ.ϵͳĲƻԴĲ.ʱļκκϱǨt,rt(r),Cr2rǷǹԴ,H(r)=1.

ͼ1SPNӽṹ
6.W=(YW,W)=Y11YnnһWͽṹ,


DWʵһڲDͽṹ,.
W0,W,W0WһڲWͽṹ.ǣBWڲDͻWͽṹ.
7. D1,,Dn(G,m0)еһDͽṹ,FT(Di+1)TDi(±modn),,Cr=1,r(G,m0)һؼԴ.KRǹؼԴ֮.
8. (G,m0)=(PPIPQPR,TTI,FFR,m0)һSPN,KR=.(G,m0)һPetriC=(PC,T,FC,m0),,PC=pBBʡȣ,FC=,


(G,m0)϶ĿCµıջϵͳ(G,m0),CĺϳPetri:

,
(c)tt(c)ֱʾǨtλüλü.pc(c)t,m(pc)1,tmǿʹܵ.ֻй̡ԴͿͬʱʹܵıǨڱջϵͳ.
3.(G,m0)һSPN,KR=,ܿϵͳ(CG,mc0)ǻ.
֤. пɴʶmZ(CG,mc0),ʹmµǨDT(m)ǿ.tDT(m),m((p)t)0.֤Ǩй,ڴ˲赱m(()t)0,tDT(m).õݹ쵼ìܵϵͳṹķ֤.
Eһչ·,SS0ֱʾһǨ.ʼE=,S=t1,S0=.t1SS0,.
1)(r)t1,m((r)t1)=0,t1Դʹ.(r)t1=r1,ڲλp11,,p1kʹR(p1i)=r1,m(p1i)0,i=1,,k,=t1it1im·Դʹܣ,XA=t1jt1jmԴʹܣ.
X0ʾѷıǨ֮.ʼ,X0=.ȡt2X1X0.(r)t2=r2,m(r2)=0,Ҵp21,,p2lʹR(p2i)=r2,m(p2i)1,i=1,,l,VA=VAȣp21,,p2l,X0=X0ȣt2,X1=X1ȣp.2ip.2im·Դʹܣ,XA=XAȣp.2jp.2jmԴʹܣ.ظ,ֱX1X0=.ʱXA,̸ıǨλöX1VA,ЩλռõԴ,X1VAչ·D,ʹm(PD)=mc0(R(PD)).pPD,t=pTD,P-·=p1t1,,pktktp,ʹpiPD,R(pi)=R(p),i=1,,k,D֮չ·.пܵչõչ·DһDͽṹ,m(PD)=mc0(R(PD)),PDĿì.
EAǷ̸Ĵp1itXAE-·֮.E=EEA,S=SXA,S0=S0ȣt1.
2)t1Դʹ,ǹʹ.t2T,t2ʹ,t(p)2t1һP-·,ÿλmΪ,m(P)=0.E=EȣУ,S=Sȣt2,S0=S0ȣt1.
3)t1Դʹ,ǿʹ.(r)t1=r1,t.1=p1,m(r1)1,pBPCʹ(pB,t1)FC,m(pB)=0,Bʡ.(C1) B.m(PB)=mc0(R(PB))-1,t1FT(B).ʱtTB,ʹ(r)t=r1,Xc=tTBtԴʹܣǿ.E=EȣB,S=SXc,S0=S0ȣt1.(C2) B.B=W=Y11Ynn,t1FT(Yi+1),Xc=tFT(W)(r)t=r1ǿ.E=EW,S=SXc,S0=S0ȣt1.֤ĳ(C1)ǲܵ.
SS0еÿǨظ,ֱSS0=.Ǩ,ĳǨظXA,XBXc,Ϊt1,t1ʼֱSS0=ķһEеչ·ɵWͽṹ,WеÿBm(PB)=mc0(R(PB))-1,ÿBm(PBY)=mc0(R(PBY))-I(B)-1,m(PB)=0,ЩBWڲṹ.Wm(PWY)=mc0(R(PWY))-I(W),Cì,DT(m)=,(CG,mc0)ǻ.
PetriĶͶ֤Կ,ʵֶҶϵͳС.
9.(G,mc0)һSPN,rKR,(G,mc0)r-G(r)Ǵ(G,mc0)¹̵õPetri.
1) (G,mc0)ɾȥԴλrػ;2) pH(r),t2ǷǺϱǨ.(r)t2t(r)1(r)t2t(r)1,t1ΪϱǨʱ,ɾȥpػ,t1,t2صΪһ±Ǩ,t1+t2.(r)t2t(r)1,t1ΪǺϱǨʱ,p1(p)t1,p2=ʹR(p1)=R(p2),ɾȥp,t1,t2ػ,p1p2صΪһλ,p1+p2.
G(r),R(p1+p2)=R(p1)=R(p2),G(rһSPN.
rһؼԴ,G(r)ͨrټ,õPetriΪG(r,r).KRеÿrһ(G,m0)õG(KR)һSPN,ҲؼԴ.
ñʾG(KR)(G,m0)ĹͬǨ(ͬǨ)֮.T0=T,G(KR)ĲеıǨʽt1++tn,Ӧ(G,m0)еһ·KR.·ΪؼǨ·,T1йؼǨ·ϵıǨ֮.G(KR)Ϊp1++pnλöӦ(G,m0)һp1pn·=p1t11p11t12p2t21p21t22p3t(n-1)2pn,R(pij)KR,R(pi)=R(p1++pn),ÿtijǷǺϱǨ.·Ϊؼλ·..p1=t0ΪеױǨ.T2ǹؼλ·ϱǨ֮,T0=T1T2.
10. (G,m0)һSPN,G(KR),CG(KR)ɶ8һԿ.(G,m0)һƲԦ.
1)ʹ(G,m0)CG(KR)ĹͬǨtͬ,tĳؼλ·еױǨʱ,tбǨӦ˳һ;
2)ʹtT1(G,m0)һΰtıǨt1++tnCG(KR)һ.
ɶ֪,C/G(KR)еĿɴӳʼʶm0ıǨ,m0ۦңm,f()ҶӦĦѣ(G,m0)еĿɴm0ıǨ,m0f()m,f()ɴӦҵõ,ڦаt1++tnt1t2tn,ѹؼλ·=p1t11p11t12p2t(n-1)1pnױǨtñǨt11t12t(n-1)2.
4.(G,m0)һSPN,綨10ĿƲ,/(G,m0)ǻģ֤).
5
ĻPetriģװϵͳĻԿ,ͨPetriģ͵Ľṹ,ָϵͳĻ䱣֤ϵͳԵĿƲԵۺϷ.ֿƶϵͳԴõС,ڴ˻ϵʵʱƵȵʵ.
1)Ȼѧͨѧеϵͳ̹صʵһ.
߼飺Ͽ塡1957.1994ͨѧʿѧλΪӿƼѧ.оɢ¼̬ϵͳPetriӦ.Ľ.
ͨѧڣʿʦ.еϵͳ̹صʵѧίԱΣIEEE߼ԱMathematical ReviewԱ.
塡ͨѧڣʿʦ.ҪодϵͳŻݽ׿ƣϵͳܿƵ.ڹⷢ250ƪҽίƼһΣȽεȽ.
ߵλϿ塡ӿƼѧӦѧϵ710071
塡ͨѧϵͳо710049
ο
1Banaszak Z, Krogh B H. Deadlock avoidance flexible manufacturing system with concurrently competing process flows. IEEE Trans. on RA,1990,6(6):724734
2Ezpeleta J, Conlom J M, Martinez J. A Petri net based deadlock prevention policy for flexible manufacturing systems. IEEE Trans. on RA, 1995,11(2):173184
3Hsieh F S, Chang S C. Dispatching-driven deadlock avoidance controller synthesis for flexible manufacturing system. IEEE Trans. on RA, 1994,10(2):196209
4Xing K Y, Hu B S, Chen H X. Deadlock avoidance policy for Petri net modeling flexible manufacturing system with shared resources. IEEE Trans. on AC, 1996,41(2):289295.
5Xing K Y et al. Deadlock avoidance controller for a class of manufacturing systems. In: IEEE Int. Conf. on Robotics and Automation, USA, 1996
6Zhou M C, DiCesare F. Petri Net Synthesis for Discrete Event Control of Manufacturing Systems. Kluwer Academic Press, 1993
7Jeng M D, DiCesare F. Synthesis using resource control nets for modeling shared-resource systems. IEEE Trans. on RA, 1995,11(3):317327.
ոڡ1996-10-03
޸ĸڡ1997-12-16
