Զѧ
ACTA AUTOMATICA SINICA
1997ꡡ236ڡVol.23No.61997




һFMSѻPetriģ͵ۺ
Ͽ塡񡡺
ժҪPetriΪһϵͳģ۱ϵͳ.ͨPetriģ͵Ľṹ֤ϵͳһֱҪ.˱ѿͨϵͳPetriģһЩµλӦĻʵ.ӶϵͳѻPetriģ.
ؼʡϵͳPetri.
SYNTHESIS OF OPTIMAL LIVE PETRI NET
MODELS FOR A CLASS OF FMS
XING KEYILI JUNMING 
(Dept. of Applied Mathematics, Xidian University, Xin710071)
HU BAOSHENG
(Systems Engineering Institute, Xin Jiaotong University, Xin710049)
AbstractIn this paper, the Petri net model for a class of flexible manufacturing systems is constructed, and the deadlock problem in FMS is discussed. We prove a necessary and sufficient condition for liveness of system model and present and optimal deadlock avoidance controller which is a Petri net. The controlled closed-loop systems may be modeled by live Petri nets.
Key wordsFMS, Petri net, deadlock avoidance control. 
1
ϵͳ(FMS)УֹļӹǲнеģЩмӹ̾޵ϵͳԴ.粻ƣ־ϵܻᵼϵͳʹĳЩӹԶ.FMSУӦȽ.ģ13ݶһFMSPetriģģ12ݸ˱ĳ㷨ģ3ݸ˱ſƲ.ģ4ԸһFMSPetriģ͸һصıĿƲ.Ŀģ4ͬһFMSPetriΪϵͳģϵͳĳֱҪһſƲ.һԿͨPetriģһЩ()λúӦĻʵ.ӶϵͳPetriģ͵ۺϷ.
2ӹϵͳPetriģ
PetriһԪG=(P,T,F),PΪλüTΪǨF(PT)(TP)Ϊ.йPetriĶ弰йȣģ5.xPT,x={yPT(y,x)F},x={yPT(x,y)F}.гʼʶm0ĶԪ(Gm0)ΪPetri.m(p)1,pʡt,mtƱǨtTڱʶmʹ.mtµıʶm䣬mtm.R(Gm0)ʾ m0ɴʶ֮.XPmR(G,m0),m(X)=m(p).R(Gm)вʹtʹܵıʶƱǨtڱʶm.ÿmR(Gm0)£tǻģt.ÿǨǻģƱ(Gm0)ǻ.
۵FMSǾnԴr1rnܼӹkֹϵͳ.һּӹһϵвɣһֹмּӹ̣ÿԴһ.ÿһԴļӹ̿PetriģһλôһβñǨʾǰһĽһĿʼ.λpi0Ҫӹӹĵiֹ.ʵiֹļӹPetriһǿͨ״̬Ni=(Pi{pi0},Ti,Fi),Piǲλüpi0Pi,
NiÿȦpi0.
ÿԴrһλãԼΪr.RԴλ֮.pPiԴrʱӻ(r,t)tʡp(t,r)tpϵͳPetriģΪG=(PP0R,T,F)P=Pi,P0={p10,p20,pk0},T=Ti (kΪ)FΪл֮.
1.ھ5Դr1,r2,r5,ӹֹϵͳУһֹļӹԴΪr1r2r1r2r1r3r4r2ڶֹԴΪr5r4r3.ֹļӹPetriϵͳPetriģͿͼ1(a),(b),(c)ֱʾ.

ͼ1(a)(b)ΪֹӹPetri(c)Ϊ򵥼ӹϵͳPetri
ϵͳPetriпеĳʼʶm0pP0Rʱ,m0(p)1pPʱm0(p)=0.Ϊƣ(p)t,(r)t,t(p)t(r)ֱʾtP,tR,tPtR.ЩǺſչXTϣ(r)X=(r)t.
3ϵͳ
mR(G,m0),D(m)ʾmʹm((p)t)1Ǩtļ.D(m)ɡP0=.
1.(G,m0)=(PP0R,T,F,m0)ϵͳʶPetriģͣmR(G,m0).D(m)٣ڷǿռDD(m)\(P0P0),ʹ(r)D=D(r),((p)D)D,m((p)D)=m0((r)D).
֤.r(r)D(m),tD(m)ʹ(r)t=rm(r)=0.T1={tTm((p)t)1, t(r)=r},m((p)T1)=m0(r),T1D(m);tiT1mR(G,m)ʹmtim.m(r)=1,mtì.tiT1֪r=t(r)iD(m)(r),(r)D(m)D(m)(r).
D(m) D1D(m)\P0.(r)D1=D1(r)ʱȡD=D1.(r)D1D1(r),ȡrD(r)1\(r)D1,D2=D1\{tD1t(r)=r},D2.(r)D2D(r)2ʱظϹ.Դޣ޷ǿռDkDk-1D1D(m),ʹDi٣(r)Dk=D(r)k.ȡD=Dk,D(m)Ķ壬m((p)D(m)(p)(r))=m0(r),r(r)D(m).r(r)D=D(r),tD(m),t(r)=r,tD,m((p)D)=m0((r)D).
֤((p)D)D.tD,((p)t)=1ʱ((p)t)=tD.((p)t)2,t(r)=r,t1t,t1((p)t),t1D(m);mR(G,m),ʹmt1m,m(r)=1.tD,(r)t=r,mt䣾ì.t1D(m)m((r)t1)=0.(r)t1=r1,t2D(m),t(r)2=r1,
(r)t2=r2,m((p)D(m)(p)(r2))=m0(r2).Ƶأt3D(m),t(r)3=r2,(r)t3=r3ʹm((p)D(m)(p)(r3))=m0(r3),.ظD(m)еıǨt1,t2ʹt(r)i+1=ri,
(r)ti=ri,m((p)D(m)(p)(ri))=m0(ri).k,l,kl,rk=rl.ri(r)D(m)D(m)(r),tiD.((p)D)D.
V(G)={DT\(P0P0)(r)D=D(r),((p)D)D}.
ͼ1(c)ʾPetriУV(G)={D1,D2,D3,D4,D5},D1={t2,t3},D2=t6,t10D3={t1,t2,t3,t5,t6,t7,t10},D4={t1,t2,t3,t5,t6,t7},D5={t1,t2,t5,t6,t10}.
1.ϵͳPetriģ(G,m0)ǻĳҪΪm((p)D)m0((r)D)-1,mR(G,m0),DV(G).
DV(G),I(D)=((p)D)\D,H(D)=(D(p)\(p)D)D.V1=D1,DnV(G)ΪWDkV1,Di,DjV1,ti,tjTʹtiDiI(Dk),tjI(Dj)Dk,(r)I(D1)ɡ(r)I(Dn)еԴΪؼԴ.
4ϵͳPetri
ǿܳϵͳPetri(G,m0).ҪΪϵͳһԱ֤ܿϵͳв.1֪ʹöκDV(G)κοɴʶmm((p)D)m0((r)D)-1.ܿϵͳıҪǳֵ.D1,D2V(G),D1D2,(r)D1=(r)D2ʱm((p)D2)m0((r)D2)-1ζm((p)D1)m0((r)D1)-1.V={D1V(G)D2V(G),D1D2,
(r)D1=(r)D2}.D0,DV(G),D0D,(D\D0)(r)(r)D0=,m((p)D0)m0((r)D0)-1 ζ m((p)D)m0((r)D)-1.V={DV(G)D0V(G),D0D,ʹ(D\D0)(r)(r)D0=,
(G)=V(G)\(VV).
A.ÿֹؼԴԴ.
1(G,m0)ϵͳPetriģ.CһPetriC=(Pc,T,Fc,mc)Pc={pDD(G)},Fc={(pD,t)tI(D),D(G)}{(t,pD)tH(D),D(G)}, mc(pD)=m0((r)D)-1.
ܿϵͳC(G,m0)ĺϳ(Gc,mco)=(PP0RPc,T,FFc,mco), mco(p)=m0(p),pPP0R,mco(p)=mc(p),pPc.(Gc,mco)У(c)tt(c)ֱǡtPctPc.mR(Gc,mco),Dc(m)={tTtmĶm((p)t)1}.
1.mR(Gc,mco),Dc(m)٣tDc(m),(r)t=rpD(c)tʹm(r)1,m(pD)=0.(֤)
2.ϵͳPetri(G,m0)Уÿֹؼ Դr,m0(r)2,CǱϵͳſC(G,m0)С.Ӷ(Gc,mco)ϵͳѻPetriģ.
֤.ÿD(G),(p)Dпm0((r)D)-1Ǳ֤(Gc,mco)ıҪ.CʹһҪ(Gc,mco)ǻģCСƵı.֤(Gc,mco)ǻ.
mR(Gc,mco)ʹDc(m)٣1t1Dc(m)pD1(c)t1ʹm((r)t1)1, m(pD1)=0.(r)t1=r1,m((p)D1)=m0(D1(r))-1, S(r1)={tD1(r)t=r1}.עt1D1,֤t2S(r1)ʹm((p)t2)1D1\(S(r1)S1)DV(G)ʹDD1, m((p)D)=m0((r)D),S1={t(I(D1)(p))t(r)=r1},ǲܵ.m((p)t2)1,m((r)t2)=m(r1)1t2Dc(m)֪D2(G)ʹt2I(D2), m((p)D2)=m0((r)D2)-1.ƴt1D1t2D2ɴt2D2t3D3ʹt3I(D3),m((p)D3)=m0((r)D3)-1.ظõ(G)һD1,D2ʹr1=(r)ti(r)I(Di),i=1,2,.D1,D2,бشWΪV1={D1,,Dk},r1ǹؼԴm0(r1)2,ʴu1D1ʹ u(r)1=r1, m((p)u1)1,u1Di, i=1,2,k(r)u1=r2D(r)1ɡD(r)k, m(r2)=0.uD1, u(r)=r2, m((p)u)0,  uDi, i=1,k. rD(r)1, Դr1,r2,,rl=rͱǨt1,t2,,tlʹ ri=t(r)i,(r)ti=ri+1,m((p)ti)1, D(r)1D(r)2ɡD(r)l,{tD1m((p)t)1}D2ɡDl. ͬD(r)iD(r)1ɡD(r)i-1D(r)i+1ɡD(r)l,{tDim((p)t)1}D1ɡDi-1Di+1ɡDl.t2D1,t2I(D2), m((p)t2)0, t2D2, ìܱDc(m)=, (Gc,mco)ǻ.
B. йؼԴr, m0(r)=1.
D(G)W{D1,,Dl}޹أDDi=,(r)D(r)Di=,i=1,2,,l. (G)ɷΪ֣1={D(G)DκW޹}2=(G)\1.
2.(G,m0)ϵͳPetriģͣCΪһPetriC=(Pc,T,Fc,mc)Pc={pDD(G}ǿλüFc={(pD,t)tI(D),D(G)}{(t,pD)tH(D),D(G)}, mc(pD)Ϊ (1)D1ʱmc(pD)=m0((r)D)-1,L(D)=m0((r)D);(2)2ϣmcǵݹ鶨.D22ԪصĲʱmc(pD)=L(D)-1, L(D)=m0((r)D).D=Di, Di2, l2,mc(pDi)жʱmc(pD)=L(D)-1, L(D)=((p)D),(G,m0)һʹL(D)ȡֵ((p)Di)L(Di)-1 (i=1,,l)Ŀɴʶ.
ܿϵͳC(G,m0)ĺϳ(Gc,mco)=(PP0RPc,T,FFc,mco),mco(p)=m0(p),PPP0R, mco(p)=mc(p), pPc. 
3.(G,m0)ϵͳPetriģͣ(Gc,mco)ǻ.֤붨2ƣ.
2.ͼ1(c)ʾPetriGȡʼʶm0(p)=5,pR,m0(p)=20,pPm0(p)=0, pP. V(G)={D1,,D5}, D4D3,(r)D3=(r)D4.D2D5, (D5\D2)(r)(r)D2=, (G)={D1,
D2,D3},ϵͳѿͼ2ʾıPetri.

ͼ2Petri
5
ĻPetriģһFMSб.ϵͳĳֱҪ.һֻPetriģۺϱϵͳ·.õĿ֤ܿϵͳĻԣϵͳԴļ.ֿһصͨϵͳPetriģһЩλúӦʵ֣ӶܿϵͳлPetriģ.ȻۺϿ㷨ĸ(G)йأۺϹ߽еģҽһΣʸⲢǱķϰ.
1)Ȼѧͨѧеϵͳ̹صʵһ.
߼飺Ͽ塡19571981ҵѧ1994ͨѧʿѧλ.ΪӿƼѧ.оΪɢ¼̬ϵͳۡPetriӦ.
19651989ӿƼѧ˶ʿѧλ.Ϊͨѧʿо.ҪоΪӦơ̬ϵͳŻܿ.
ͨѧڡʿʦеϵͳ̹صʵѧίԱΣIEEE߼ԱMathematical ReviewԱ.
ߵλϿ塢ӿƼѧӦѧϵ710071)
ͨѧϵͳо710049
ο
1ݡBanaszak Z A, Krogh B. Deadlock avoidance in flexible manufacturing systems with concurrently competing process flows. IEEE Trans. Robotics and Automation, 1990, 6(6):720-734.
2ݡHsieh F S, Chang S C. Dispatching-driven deadlock avoidance controller synthesis for FMS. IEEE Trans. Robotics and Automation, 1994, 10(2):252-261.
3ݡXing K Y Hu B S, Chen H X. Deadlock avoidance policy for FMS, in Petri nets in flexible and agile automation, M. C. Zhou(Ed), Boston: Kluwer Academic, 1995, 239-263.
4ݡEzpeleta J, Colom J M, Martinez J.A Petri net based deadlock prevention policy for flexible manufacturing systems. IEEE Trans. Robotics and Automation, 1995, 11(2):173-184.
5ݡPeterson J L. Petriϵͳģ⣬ܻ.ݣйҵѧ磬1989.
ոڡ1995-07-13
