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



ؼ·ߵȷ
ԿͿE
ժҪŶоɢ¼̬ϵͳЧ, ܺĿ΢Ӧø÷ǰ֮һ. ùؼ·ĸ,֤̬ܺ΢ĳҪΪϵͳĹؼ·Ը1ΨһңϵͳĹؼ·ʲΨһʱܺķڣ䷽ƫ.ָӦŶͷǹ⻬оܺ΢ϵͳ˼·.
ؼʡߣؼ·΢.
CRITICAL PATH AND SENSITIVITY ANALYSIS OF STOCHASTIC
SERIAL PRODUCTION LINES
LIU Zikuan TU Bengsheng
(Department of Computer & System Sciences, Nankai University, Tianjin300071)
AbstractPerturbation analysis is an efficient method to study DEDS, which requires the differentiability of the performance function. In this paper, by using the notion of critical path, it is first proved that the steady-state performance function of a stochastic serial production line is differentieble iff its critical path is unque w.p.1. Moreover, it is shown that in the case of the critical path being not unque with postive probability, the one-sided derivatives of the performance function exist and their unbaised estimators are given. Finally, the method of parameters optimization of DEDS via perturbation analysis and nonsmooth optimization is outlined.
Key wordsStochastic serial production line, critical path, nondifferentiability.
1
֪ѧֵʾɢ¼̬ϵͳ(DEDS)̬ܺͨûԽʽ, ÷淽. ֵĻڵȷ, Ŷ(IPA)Ȼ(LR)ȶ߷ЧʵЧ. ŶΪͻ, ÷ۺӦ÷涼ȡ˷˶ɹ1. Ҫܺݶϵͳܺݶ, Ȼݶ㷨Żϵͳ. 
һ, IPAǺЧ. Ȼ, ܺݶȲǴڵ, Y.Wardiף2вDEDSܺһܼǲ΢, ף3йһѭŶ, ܺ㴦΢, Ӷ֤ʵף2еĲ. ף4Ϊ͹, ֤ף2еĲ.ùؼ·ĸ, ̬ܺ΢б, ̬ܺƫ.
2Ҫ
´

ͼ1
лMi,in=1,2,,nӵ, Ĵ洢. pi(k,i)ʾJkڻMiϵļӹʱ, ЦiʾƲ,xi(k)ΪJk뿪Miʱ;ykʾJk뿪ϵͳʱ; X(K)=(x1(k),,xn(k))Tʾ״̬, ôڼ¸ϵͳ״̬̣5

(1)
Ц=-,e=0,ab=max(a,b),ab=a+b,C=(ţ,e)A(k)=(pij(k)),i,jn,jiʱ,pij(k)=;jiʱ,pij(k)=pj(k)pi(k);pii(k)=pi(k). ڲʡ.
ǹiļӹʱΪP(i,)=(p1(i,1),,pn(i,n)),=(1,,n). ʧһ¼:P(i,)),i1ֲͬ, ϷֲFk(k,tk)pk(i,k)ķֲ, ôɼ

зӣ0,1ϵľȷֲ.ǼӹN(㹻),Jin̨ϵļӹʱɱΪ

(2)
Ǧi=(i1,,in),=i,1iNôÿμΪϵͳһ. 
һG(t,),tR, 1.
1.Ը1G(t,)t΢, ֵKGEKGݣ

(3)
1.Li(x),xR,imm΢, 

УAʾAԪصĸ.ô 1) xE,max1im Li(x)x΢;
2)xE,max1imLi(x)xڵർ

2.Li(x,),im1, ô

֤. 1ף4Prop.2.1ֱӵ֤2.
ʽ(1)ʾ,ܺΪJN()=EΣyN(,)/N.1/JN()Ϊߵ. 蹲ӹN, ôһ,pi(j),in,jNȷ. ƹJjڻMiϼӹΪһ¼, Oij. m(Oij)ʾ¼Oijļӹʱ,xi(j)OijĽʱ. Ȼ,pi(j)=m(Oij). ¼Oij-1,Oi-1jOijǰ¼, Oij-1OijOi-1jOij. ii,jj,l=i+j-(i+j)+11ʱ, (i,j)(i,j). ¼=O1O2Ol:O1=Oij,Ol=Oij,Ok-1Ok,ôƦΪOijOijһ·. m()=m(Ol)m(Ol). xi(j)=m()m(O1)-1xi(j), ƦΪOijOijһؼ·56, *(i,j;i,j).(i,j;ij)ʾ¼Oij¼Oijȫ·. ʽ(1)ɵxi(k)=pi(k)(xi-1(k)xi(k-1)). xi-1(k)=xi(k-1), Ҳ˵¼Oikǰ¼ͬʱ, ¼Oikǰٽ״̬. 
1.ӹʱpi(j,i)1, ôJN()ķ, 

֤.һ, (1,1;n,N)ʾO11OnN·ȫ, r()=(1,1;n,N),覸(1,1;n,N)=1,,r(),c()ʾ(1,1;n,N)йؼ·Ŀ.ף54.1ɵyN(,)=max1sr()m(s).Ϊm(i)޸1Ŀ΢֮ͣҲ12ɵ֤1.
1.һɢ¼̬ϵͳĹؼ·Ը1Ψһ, Ƹϵͳ.
1.ʽ(1)Ƶ, Ҽӹʱ1,ôJN()΢,dJN()/di=EΣdyN(,)/Ndi.
2.ӹʱpi(j)1, ôƵ.
ɶ1Կϵͳʹؼ·Ψһʱ, JN()ķ. һ, Դӹؼ·ҳһؼ·, ֮Ϊ()ؼ·,¼ӹʱ֮͹ڦiĵyN(,)ڦi(), d+JN()/di(d-JN()/di)ƫ. һ, Ѱ()ؼ·ķ. Ϊҳ()ؼ·, ʽ(1)деƹϵʽ

(4)
ֱʾO11Oij()ؼ·, ȻѾ浽k, Ѿõ.еk+1, (4)һʽɵýһѾõ, ô(4)ڶʽɵ
a)xj(k)=xj-1(k+1),

(5)
b)xj(k)=xj-1(k+1),

(6)
ɵؽȥ, ԵõȫƵصõ. ɵĹ̿Եõ2.
2. ڶ1
1)c()=1, ôyN(,)ڦi΢, dyN(,)/di=dm(nN)/di;
2)c()=1, w.p.1, dJN()/di=EΣdm(nN)/(Ndi);
3)P(c()1)0, ô

3
ùؼ·ϵͳƵĸ, ֤̬ܺ΢бΪؼ·Ը1Ψһ, ䷽ƫ. ʾDEDS̬ܺ΢ԭ. ӱķùؼ·ĸоDEDSܺĿ΢ԼIPAƫԺֱۡЧ.
ϵͳĹؼ·Ψһʱ, ϵͳܺ΢. ڴ¿ùؼ·ݶϵͳܺ½, ÷ǹ⻬Ż㷨вŻ.
1) Ȼѧ(69674013)͹ʵǼƻĿ.
߼飺ԿУ196711.19987»Ͽѧϵͳѧϵʿѧλ.ڹ⿯Ϸ20ƪ.оȤΪϵͳнģ.DEDSHDSۼӦ.
ͿEУ19375.Ͽѧϵͳѧϵڣʿʦ.ִCIMSDEDSۼϵͳͨӦ.
ߵλϿѧϵͳѧϵ300071
ο
1Ho Y C, Cao X R. Perturbation Analysis of DEDS, Norwell MA Kluwer 1991
2Wardi Y, Mckinnon M W, Shuckle R. On perturbation analysis of queueing networks with finitely supported service time distributions. IEEE Trans. Automat. Contr., 1991, 36(7):863867
3Cao X R, Gong W B, Wardi Y. -Conditioned performance functons of queueing systems. IEEE Trans. Automat. Contr., 1995, 40(6):10741079
4Shaprio A, Wardi Y. Nondifferentiability of steady state function in discrete event dynamic systems, IEEE Trans. Automat. Contr. 1994,39(8): 17071711
5ͿE. ϵͳDEDSŶ. Զѧ, 1992, 18(6):716719
6ͿE. ɢ¼̬ϵͳĹؼ·Ŷ. ϵͳѧѧ, 1996,16(4):318325

ոڡ1997-06-18
޸ĸڡ1997-10-09
