Զѧ
ACTA AUTOMATICA SINICA
1997 23 3 vol.23 No.3 1997



һ޷ Fork-Join
Ŷ

ժҪоһŶӿռҷ̨޵ķ Fork-Join Ŷ磬̬ʵֱӷ͵ЧһЩŶָͿָ(̬ӳ̨ĿöȺͷ̨ʧЧ)֤ͨȷ.
ؼʡŶ磬ɿԣ̬ʷֲ.
ANALYSIS OF A CLASS OF REPAIRABLE ACYCLIC
FORK-JOIN QUEUING NETWORKS
DING LIANYU YANG DELI
(Institute of Systems Engineering,DUT,Dalian 116024)
Abstract A class of repairable acyclic fork-join queuing networks(RAFJQN)with finite queuing spaces and repairable service machine is considered.In calculating steady-state probability,both direct method and equivalient method are proposed.In addition,some indices(such as steady-state queuing length,failure probabilities of server and utilizable rates of server)in queueing theory and repairable theoy are obtained.Finally,examples are given by simulation.
Key words Queuing network models,reliability,steady states,probability distribution function.
1
 Fork-Join Ŷ(AFJQN)1һͬԵɢ¼̬ϵͳڼӳй̣ϵͳװͲжģͳ.׷ AFJQN ʱõķٶʧЧ13ݣڷ̨ʧЧͿ޵ AFJQN(RAFJQN)۴Ŷ۽Ƕȣǿ۽Ƕȣֵо.
ͼ1ʾľ̨ RAFJQNMj Ϊ̨Bj Ϊj=1,2;Ϊȵȷɵķ.

ͼ1̨ RAFJQN
ˣj,j  j ֱΪʡʡ޸ʺʧЧʣj=1,2.һ裺(1)з̨ʧЧ(2)ʧЧ̨ȴ޸ʱѷʱЧ(3)̨޸󣬹ȫָ.
Ļף3ݵķܣף4ڷ̨ϵͳ˼룬Чؽ̨޵RAFJQNܷһЩָļ㷽.
2RAFJQNȶ
 jn Ϊ j е n ˿ʹӿʼܷ񵽷ʱ䣬аΪù˿ͷڼڷ̨ʧЧʱ.ף4ݿɵ
1/j=Ejn=(j+rj)/jj, j=1,2.(1)
ˣɽ jn Ϊʱ.ͼ1RAFJQNͿɵЧΪj  AFJQN.
1. u ̨AFJQNﵽȶƽ
(2)
֤.ף5Ѿ֤ͨŶϵͳﵽ̬ƽϸСеķʶAFJQNͬ.RAFJQNɵЧAFJQN(1)ʽ֪(2)ʽRAFJQNȶ.
3RAFJQNķ
ϵͳ״̬ռΪ(i,j,k):0iN+1,0jM+1,0k2. i,j ֱΪжӳ(Ŷӵȴڽܷܺ)k Ϊϱ־k=0 ʾϵͳk=j ʾ̨ j ϣj=1,2;N,M Ϊt ʱϵͳ(i,j,k)״̬ĸΪ Pijk(t).ͼ2״̬תͼɽƽ̣ⷽ

ͼ2RAFJQN״̬תͼ
Pi,j,o=1Pi+1,j,o+2Pi,j+1,o+Pi-1,j-1,o+1Pi,j,1+2Pi,j,2,0iN,0jM;(3)
PN+1,j,o=2PN+1,j+1,o+PN,j-1,o+1PN+1,j,1+2PN+1,j,2, 0jM;(4)
Pi,M+1,o=1Pi+1,M+1,o+Pi-1,M,o+1Pi,M+1,1+2Pi,M+1,2, 0iN;(5)
Pi,j,1=2Pi,j+1,1+Pi-1,j-1,1+1Pi,j,o, 0iN+1,0jM;(6)
Pi,M+1,1=Pi-1,M,1+1Pi,M+1,o, 0iN+1;(7)
Pi,j,2=Pi+1,j,2+Pi-1,j-1,2+2Pi,j,0,0iN,0jM+1;(8)
PN+1,j,2=Pn,j-1,2+2PN+1,j,o,0jM+1;(9)
(10)
 =+1+2+1+2,=ˣ2¡,=++2,Ц1Po,j,o=0,1Po,j,2=0,2Pi,o,o=0,2Pi,o,1=0,PN+1,j,k=0.
÷ֿ⣬
j=Po.j.o,P1.j.o,,PN+1.j.oT,
j=Po.j.1,P1.j.1,,PN+1.j.1T,
j=Po.j.2,P1.j.2,,PN+1.j.2T,
=ۦo,1,,M+1T,=ۦ0,1,,M+1T,
=ۦ0,1,,M+1T,H=0,0,,01T(q-1)1,



 i=1,2,3;v=N+2;q=v(M+2);a1=/2;a2=/2;a3=/2;b1=b2=b3=-/2;c1=c3=-/ c2=0;d1=-¡/2;d2=-á/2;d3=-2/2;e1=-2/2.


ǽ(3)(10)ʽд¾ʽ

 W=R1-M1R-12M2-N1R-13M3,
=W-1H,
=-R-12M2W-1H,
=-R-13M3W-1H.
˽̬ʷֲPijkƴ˷Ϊֱӷ.Ϊ״̬ά˷Ĳ㣬ͨ(1)ʽRAFJQNЧAFJQN.ϵͳ״̬ռΪ(i,j):0iN+1,0jM+1,
(11)
(12)
(13)
(14)
 (11)(14)ʽֱӷ׵ãijƴ˷ΪЧ.ɼЧ״̬άֱӷ֮һ.
2. j ̬ӳΪ Lj̨ j ̬ʧЧʺ̬öȷֱΪ Pjf Piu(j=1,2)ŶָͿָ
(15)
(16)
P1u=1-P1f, P2u=1-P2f.(17)
֤.,(15)ʽ.ʧЧʺͿöȵĶ׵(16)(17)ʽ.
4ʵ
N=M=2,(1,2,1,2,1,2)=(1.01.250.50.50.050.05)(1)ʽá=0.9092=1.36.1ͱ2ȻֱӷЧ̬ӳС 1%.
1ֱӷ

=0.2=0.4=0.6=0.8
EL1
EL21.912703
1.7615341.989827
1.8414912.068267
1.9235872.145000
2.004980
P1f
P2f0.047979
0.0546550.044854
0.0503840.041479
0.0459060.038068
0.041539
P1u
P2u0.952021
0.9453450.955146
0.9496160.958521
0.9540940.961932
0.958461

2Ч

=0.2=0.4=0.6=0.8
E1
E21.916493
1.7551621.996161
1.8395562.078524
1.9277902.159798
2.015916

5
ʵ֤оRAFJQNЧ.ŶһоƶͨѶϵͳϵͳ(CIMS)ϵͳ(FMS)ͲдĹ㷺Ӧ.
ߵλѧϵͳ116024
ο
1Baccelli F.Acyclic Fork-Join queuing networks.J.ACM,1989,36(3):615-642.
2Zhang Z S.Analytical results for waiting time and system size distributions in two parallel queuing systems.SIAM J.Appl.Math.,1990,50(4):1176-1193
3ѧף֣.һ Fork-Join Ŷϵͳķ.Ӧã199411(3)361-365
4ݲܽ٩.̨޵ M/G/1 Ŷϵͳ.Ӧѧѧ19825(2)113-127
5Konstantopoulos P,Walrand J.Stationary and stability of Fork-Join networks.J.Appl.Prob.,1989,26:604-614.
ոڡ1994-12-16
