トップページ - 横浜国立大学学術情報リポジトリ

全文

(1)' A Unified Analysis to the Queue Length Distributions in MX(k)/G/1/N and GI/MY(k)/1/N Queues. Yutaka Baba Department of Mathematies, Ilaculty of Education. Ybkohama Nat.iQnal University .. t'. 156 Tbkiwadai, Hodogaya-ku, Ybkohama 240, Japan E-mai1: [email protected]. , Abstract We study an eMcient iterative algorithm fbr computing the stationary distributions ih MX/G/IZN queues with arbitrary state-dependent arrivals, that is, .,. MX(k)/C/1/N queues. MX(k)/G/1/N queues include the well studied specidl cases, such as PBAS (partially batch acceptance strategy) At(,X/G/1/N queues and. WBAS (whole batch acceptance strategy) MX/C/1/N queues. tt We only require the. LaplaceStielojestransformoftheservicetimedistribrftfon.' ' ' ' Furthermore, we can obtain the algorithm for c6mputing the stationary queue '' length distributionS in GI/MY/1/N queues with state-dependent'services, or GI/MY(k)/1/N queues by using a relationship between the stationary queue length. distributions in GJIM.Y(k)/1/N and MX(k)/G/1/N +l queues. ,-. J,. 1 Introduction We consider a batch arr/: al MX/G/1/N qtieue with state-dep<il, }dent anivals. Each service time fbllows a generaJ probability distribution C with mean 1/pa. Wki assume t,h' at YA,e, ,. system can hold up to N customers including the one under sewice. The batch arrivals. occur according to a Poisson process that depends on the number of customers in the system, that is, the batch entering rate to the s' ystem is X.k･ (n ==･ O,1,:..,.IV r, 1;.k = ... 1, 2,...,N - n) that just k customers enter the system when there are n cust6mers in the. system. This queueing system is denoted as M'X(k)/a/1/AI queue. Similarly we define a batch service GI/MY(k)/1/N queue that is d' GI/MY/1/N queue wit･h state-dependentservice, where p.k (h ± 1,2,...,AI;k = 1,2,...,n) is the batch service rate that J'ust''k customers finish service ahd leave the system when there arqn cuStomers in the sys･tem.. Recently several researchers investigated state-dependent arrival or service queues. Fbr single arrivals or sertiices, Kijima and Makimoto [5] studied the stationary: queue. length distributions of M(le)/G/1/N and GI/M(k)/1/N queues via Neuts' method (see [7]). However, if some ofstate-dependent rates are identical, Fhe recursign formulas have. Itt t/t. ; .L.

(2) Yutaka BABA. 44. not been derived because these are extremely complicated. The numerical instability occurs if some of rates are close but not identical. Yang [9] proposes a new approach for. computing the statiohary queue length distribution in M(k)/G/1/N and al/M(k)/1/N queues. Li, Zhu and Yang [6] studied M(k)/G/1/N queues with set up time. Yang [9] and Li, Zhu and Yang (6] used the method of supplementairy variables (Keilson [4], Henderson [2], Hokstad [3]) to obtain the system equations and iterative algorithm fbr. computing the stationary queue length distribution. Furthermore, Yang [9] derived a relationship between the stationary queue length distributions in M(k)/G/1/N + 1 and. GI/M(k)/1/N queues. Fbr batch arrival queues with finite capacities, Baba [1] studied PBAS (partially batch. atceptance strategy) and WBAS (whole batch acceptance strategy) MX/G/1/N queues by using the method of supplementary variables. In PBAS, when an arriving batch is 1arger in size than the number of availab}e free capacities, it fi11s the free positions and. remaining customers of the batch are lost. In WBAS, when an arriving batch is larger in size than the number of available free capacities, the whole batch is rejectod. PBAS and. WBAS MX/G/1/N queues are special cases of state-dependent arrival MX(k)/G/1/N queues. In Talragi [8], many batch arrival queues with finite capacities are studied.. The main purpose of this paper is to derive a unified iterative algorithm for comput-. ing the stationary queue length distributions in both MX(k)/G/1/N and GI/MY(k)/1/N queues by using the method of supplementary variables. We only require the Laplace Stieltjes transform of the general distribution in the model. We can see that the computations in the algorithm are simple and,eMcient. The rest of this paper is organizod as fbllows. In section 2, we wi11 derive the sys-. tem equations for MX(k)/C/1/N queue by using the method of supplementary variables. In section 3, we wi11 derive the system equations for GI/MY(k)/1/N queue. Furthermore, we can find a relationship between the stationary queue Iength distributions in. MX(k)/C/1/N + 1 and GI/MY(k)/1/N queues. In section 4, we will develop an ef ficient iterative algoritim for calculating the stationary queue length distributions in. MX(k)/G/1/N queues, In section 5, we will study a well studied special case, PBAS MX(k)/G/1/N queue. Iibr this queueing model, the algorithm in section 4 is simplified remarkably.. 2 AnalysisofMX(k)/G/1/IVQueues Wk) consider an MK(h)/G/1/N queue. Let Ank (n == O, 1,...,N - 1; k = 1,2,...,N - n) be the exponential arrival rate thatjust k customers of an arriving batch enter the system. when there are n customers in the system and A. = 2r.1" A.h (n = O, 1,...,N - 1). Let b(u) be the probability density function of the service time distribution with mean 1/pt. Furthermore, let S(t) be the number of customers in the system and U(t) be the r'emaining service time at time t. It is clear that {(S(t),U(t));t 2 O} is a Markov chain. Define the steady state joint density function {(S(t),U(t));t ) O} as. p.(u)du=,ttm.P(S(t)=n,u<U<u+du) (n=1,2,...,N). Let S be the number of customers in the system in steady state.. (i).

(3) : i. !. A Unified Analysis to the Queue Length Distributions in MX (k)/G/1/N and GI/MY (k)/1/N Queues 45. Using ordinary arguments, we have the following differentia} difference equations:. AoP(S - O) == p,(O),. Clp1(U). - du =-A,p,(u)+AoiP(S=O)b(u)+p2(O)b(u), -'`II'S.(U)='Anbn(u)+Aonp(s=o)b(u)+tL.li,'Ai,n-ipi(")+pn+i(O)b(u) (2). ･ (2 SnS N- 1),. -opdNiu) = A,.p(s == o)b(.) + illll ll A,,.-,p,(u).. DenoteIl:(s) = .J(oo e-SUp.(u)du (n = 1,...,N), B'(s) = ygoo e-S"b(u)du and Itr(o) =. P(S = O). Then the stationary queue length distribution is given by ll:(O) = P(S = n) (n = O,1,...,N). By multiplying e-S" and taking the integration on both sides of (2),. we haye. A,.l6(O) = p,(O), (Ai - s) i?ir (s) :AoiiX (O)B*(s) + e?-(,O)B'(s) -- pi (O), "ilii'.' '. (An'--S)"Pl:(s)==Aon-le(O)B*(s)+IE.li,At,n-tl'(S)+Pn+i(O)B'(S)-Pn(O)' (3). (2 SnSN -- 1),. N-1. ･--sl Xr(s) = AoN.l lli (O)B"(s) + Z) Ai,N-iny(s) - pN(O). i=1. '. 'Ib eliminate the variables p.(O) (n == 1,.,.,N), the fo11owing two lemmas are neces-. s.ary. ･. '. Lemma 1. , n-1 -. pn(O)=2Ak,.mkRg(O) (n=1,2,...,N), (4) k=O. N-k. where Xkn= 2 Aki･ i=n+1. ProoftInsertings=Oin(3)andusingmathematicalinduction,wehave(4). O. Lemma 2. NN pZ)R(O) == 2pn(O)･ (s). n=1 n=1 Proof: Adding equations in (3), we have. .2"=,ll (S) i= 1- ?"(S) .2".,Pn(O)'. Lettings---> O, we can obtain (5) immediately. O.

(4) 46. Yutaka BABA. USing (4) to eliminate p.(O)' (n = 1,2,..,,N) in (3), we have (A, - s) ,l2r (s) = Ao{B'(s) - 1}I:(O) + A,B"(s).?il (O),. n-1 n-1 i=1 h=O. (An'S)I:(S)=2Ai,n-iny(s)-￡Ak,n-kl:I(O)+AonB'(S)1:(O) (6) n. +￡Xk,n+i-hB'(s)ll(O) (2SnSN-1), k=O. N-1 N-1. -sRie(s) = 2 Ai,Nminy(s) + AoNB'(s)1tt(O) - Z) Xk,Ar-kjP]II(O)･. i--1 '･, ' k=O. ,,;. Using (6), we will develop an eMcient iterative algorithm in section 4 to compute Il;(O) (n := O,1,...,N).. 3 AnalysisofGI/MY(k)/1/NQueues In this section, we study a GI/MY(le)/1/N queue. A relationship can be found between. the stationary queue length distributions in GI/MY(k)/1/N and MX(k)/C/1/N + 1 queues. Therefbre, the algorittm fbr computing the stationary distributions in. MX(k)/G/1/N queues in section 4 can also be applied to GI/MY(k)11/N queue, The system can hold up to N customers. An arriving customer is lost when there are already N customers in the system, When an arriving customer finds that the number of customers in the system are 1ess than N, he joins the batch service with the customers served at present.. Let pnk (n = 1,2,...,N;k = 1,2,.,.,n) be the exponential service rate that just k customers finish service and leave the system when there are n customers in the system. and Mh = ￡Z.ipnk (n : 1,2,...,N). Let a(u) be the probability demsity function of the interarrival time distribution with mean 1/A. Let S(t) be the number of customers in the system and V(t) be the remaining time for the next arrival at time t. It is clear that. ' density function of {(Q(t),V(t));t ) O} is a Markov chain. Define the steady statejoint. {(S(t),V(t));ti) O} as ' ' g. (u)du == ,ttm. P(S(t) = n,u< V(t) <u+ du). (7) Let S be the number of customers in steady state. By a similar analysis in section 2, we. have -d92￡U) = ;.ili.,piiqi(u),. ' ' -dqS￡U)=,t",,,th,i-.qi(u)+q.-i(O)a(u)-Mhq.(u) (1Sng,N-1), (8) ' (ze) dgAr ' - d. ==qN(O)a(u)+,,qN-i(O)a(u)'-1!4NqN(u).. qi(u)du (Oyloo (' i S N)e-su and A*(s) Let Q;. (s)= ..= JCcoe-S"a(u)du, Then the stationary queue length distribution is given by Q;,(O) = P(S = n)'(n = O,1,...,N). By.

(5) A Unified Analysis to the Queue Length Distributions in MX (k)/G/!/N and GI/MY (k)/1/N Queues 47. multiplyinge-S"andtakingtheintegrationonbothsidesof(8),wehaye , i 1. N. -sQ6(s) - 2paiiQ;･ (s) - bo(O),. i=1 ･N･. (Mh--s)Qn(s)=2pi,i-.Q;･(s)+q.-i(O)A'(s)-q.(O) (1-<'nSAi--1),(9) i=n+1. (MN - s)QX(s) =: qN(O)A*(s) + qN-i(O)A'(s) - qN(O).. 'Ib eliminate the variables q.(O) (n == O,1,..1.,N) in (9),the following twe leinmas are. necessary. . Lemma 3. '. '. N gn(O)=2Pi,i-nQ;･(O) (n-O,1,.,.,IV-1), ' (10) i=n+1. where pin = 2 pik･. i '''''' ''". :ermOOilltal4nSet"i"ngS=Oin(9)andusmgINnathemaScialindtiction,wehSve(io) m. qN (O) =A- li.Illi,., Q;' (O) .2., Piii-n' (n) Proof:Addingequationsin(9),wehave''.. :',... '. '. //' .. ,.2N.o(?;(s)=1-. iil"'(S),.il.:oq"(O)' ,.,i. Lettings-O,wehaVe ' ' ' ' 1==,.il.I],(?;(O)=k.2N.,qn(O)' , Using (10), it fo11ows that , N-1. gN(O) =A- Z) qn(O) ･ n=O . =A-"￡'i Sii) p,,,-.(?;(o). n=O i=n+1. N i-1. == A - ￡ (?;･ (O) 2]) p,,,-.･. i=1 n=O Using lemma 3 and 4 to eliminate q.(O) (n == O, 1･,..;,N) ' in (9), we have. NN. -sQ6(s)-￡piiQ;･(s)'-2piiQ;･(O), '' ' i=1 i=1. ･o.

(6) Yutaka BABA. 48. NN N. (M}z ' S)Q;(S) = 2Pi,i-nQ;' (S) + ￡Pi,i-n+iQ;' (O)A"(S) - ￡ Pi,i-nQ;' (O) (12). i=1 i=n i=n+1 (1 SnSN- 1), N i-1. (MN - s)QX(s) = {A - 2) Q;･ (O) 2 pi,i..}{A'(s) - 1} + MNQX(O)A'(s).. i=1 n=O Instead of solving (12) to calculate Q;(O) (n = O, 1,.,.,N), we consider the following. alternative queueing model. Let p = A,Ank = pN+i-n,k (n = 1,2,...,N; ic ; 1,2,･.･,N+ 1- n),A. = ￡X.+ii-" A.k (n = 1,2,...,N),Aoi be an arbitrary positive number, Ao. == O (n = 2, 3,...,N+ 1) and Ao == ￡hN.+ii Aok = Aoi. Furthermore, let. Il;(S)=A.k2)x--,AQO;R(;o)(Oil}k-.i,pa-,,,-.(?X+i-n(s) (n=1,2,･･,N+1)･ (13). Substituting (13) into (12), we have. (A, - s)Rr (s) =; A,.F (O){A*(s) - 1} + A,.Pr(O)A*(s),. n-1･ n-1 n i=1 i=1 i=1 (2 -<- nS N),. (An - s)llll (s) = 2 Ai,n-iny (s) - ￡ Xi,n-iny (O) + ￡ Xi,n+i-iA'(S)ny (O). (14). NN. -s.IZitr+i(s) = 2 Ai,N+i-iny(s) - ￡ Ai,N+i-iny(O)･. i=1 i=1 We can see that Il:(s) (n = N+ O,1,..., 1) is the solution of (14) if and only if Q;(s) (n = O, 1,...,N) is the solution of (12) where the relatioms are stated in (13). Iirom. (6),. we can see that (14) is the system equation for MX(k)/G/1/N+1 queue that has a statedependent arrival rate Ank (n = O,1,.,., NIk = 1,2,..., N + 1 - n) and the probability density function ofthe service time distribution is a(u) with mean 1/pt == 1/A, Therefbre, 1l (O) (n = O,1,...,N + 1) is its stationary distribution,. Using (13), we have. N+1. i- q(o) = ￡ q(o) n =1 Ao.Fl (O) (?;' (O) 2I)n-o. A-2)l･)l., i-i. N+1. Pt,t-n .2., QN+'-n(O). (15). Ao .l tr (O) A - Z)S')l.i (?;' (O) ￡:-.'o pa-i,i-n'. that implies. Q;(s)={]&/fnfk'((,S)) (n-o,i,. ..., N).. Using the above discussion, we finally obtain the following theorem.. (16).

(7) l. A Unified Analysis to the Queue Length Distributions in MX (k)/G/1/N and GI/MY (k)/1/N Queues 49. Theorem 5 Given a al/MY(k)/1/N queue that has statedependent service rates pt.k (n = 1,2,...,N; ic = 1,2,...,n) and the probability density function a(u) of the interarrival. time distribution with mean 1/A. Let QA(O) be the steady state probability of having n. (n == O,1,...,N) customers in the system. Then we have. Q;(o) == {&tf"f8'((,O)), (i7) where 1l;(O) (n = O,1,...,N + 1) is the steady state probability of having n customers. in the system of an MX(k)/G/1/N + 1 queue that has state-dependent aiTival rates. Ank = pN+i-n,k (n = 1,2,･･･,N;k = 1,2,...,N+1- n),Aoi (an arbitrary positive number), Aok = O (k = 2,3,...,N + 1) and the probability density function a(u) of the service time distribution with mean 1/pa = 1/A.. 4 Algorithm In this section, we derive an eflicient iterative algorithm for computing the stationary queue length distribution in an MX(k)/G/1/N queue by using the results in section 2.. Substituting s == A. (n = 1,2,...,N - 1) in (6), we have. Ao{1 "' B'(Ai)}. ny(o) -. A,B*(A,). q (o),. "Fl(O) == A.Bl(A.) [tL.llli A-i･n-`ny(O) - AonB'(An)1:(o) ' :II.l)i,i ii,n+i-iB'(An)ny(o) (is). n-1. -2Ai,n-iny(An)] (n=2,3,･･･,Nm1)･ i =1 Rearranging (6), we have. 1. ;Pr(S)= A, -,[Ao{B*(s) - 1}.P6(O) + A,B*(s).Ril(o)],. '. `Flll (s) = A. 1-.- , [tL.li,i Ai,n-iny (s) - :ll.lli,i A-i,n-iny (o) + AonB*(s)-l :(o). (19). n +2Xi,n+i-iB"(s)ll'(O)] (n=2,3,...,N-1). i=o 'Ib simplify the algorithm, let. I}:(s)=x.(s)Ie(O) (n=1,2,...,N) and xo(s) = B"(s). Using (18), (19), (20) and xo(O) = 1, we obtain. Ao{1 - xo(Ai)}. Xi(O)= Aixo(Ai) '. (20).

(8) Yutaka BABA. 50. '. 1 n-1nt n-1-. Xn(O) = A.xo(A.) [IE.liie At,"-tXt(O) - AonXo(An) - ,￡.-o At,n+i-txo(An)xt(O). n-1 '. ny2Ai,n-ixi(An)l (n=2,3,･･･,N"1),. (21). i=11 Xl(S) = [Ao{xo(s) - 1} + Aixo(s)xi(O)], Al -- s x"(s) = A. i- s [:IIIiilii Ai,n-ixi(s) - ti.llioi A-t,n-txt(o) + Aonxo(s). n +Z)Xi,n+i-ixo(s)xi(O)] (n==2,3,..,,N-1), i=o Given x.(O) (n == O, 1,...,N - l), the following lemma determines xN(O).. Lemma 6. xN (O) == i[:11.II,' xk(O) .tk,, Xk,n-h -p :1:.ll,i xn(o)] (22). Proof:Using(4)and(5), :' '. '. t t:t NN'. ' pa[Xx.(o)%(o)-pEny(o). n=1 Nn=1. = 2) pn(o) n=Ni n-i = [￡ 2 Xk,.-kxk(O)]IZI (O). n=1k=O. N-1 N ･. =[2xk(O) ￡ Xk,.-k].l:(o).. k=O n=k+1. N N-1 N. That iS' pa.￡.-,X"(O) = ill.lii-, Xk(O)..2,,, Xk,n-k, which implies (22)･ D By the above discussion, we can see that Il:(O) (n = O,1,,.,,N) are expressed in terms of x.(O) (n = 1,2,...,N - 1). Note that if Ak 7C A. then. Xi(Ak) : A, l A, [Ao{xe(Aic) - 1} + Aixo(Ak)xi(O)],. X9')(Ak)=A,!A,[Aox,O)(Ak)+A,x,ti)(A,)x,(O)+jxij-i)(A,)l (j･>--1),. 1 n-1 n-1". Xn(Ak) == A. ny Ak[l.lll., Ai,n-iXi(Ak) - i,llii.o Ai,n-ixi(O) + Aonxo(Ak) (23). n. +￡Xi,n+i-iXo(Ak)xi(O)] (n}ll2), i= o. '.

(9) i. l l. A Unified Analysis to the Queue Length Distributions in MX (k)/G/1/N and GI/M' (k)/1/N Queues 51. Xnij)(Ak)=A.IA,[tL.li,'Ai,n-ixS"')(Ak)+Aonxoij)(Ak) '' '1. '. n. +2Xi,n+i-ix6")(Ak)xi(O)+3'x￡j'Mi)(Ak)], (n}li:2;j'>-1) l. i=o. i. l. otherwise, if Ak = A. then. l. tt xiJ')(A,)=-3.+11[A,x8J'+i)(A,)+A,x6j'+i)(A,)x,(o)] (o･>-o), x￡")(Ak)==-].+11[th.,iAi,n-ix,ij''i)(Ak)+Aonx8"'i)(Ak) '' (24). n'. +￡Xi,n+i-ixoij"')(Ak)xi(O)] (2'>.'℃)i'."r. i=o. Using (2.1)-(24), we can derive the following algorithm to calculate the steady state probabilities R:(O) (n = O,1,...,N).. Step1 initialization:GivenA.k(n==O,1,...,N-1;k=1,2,.,.,N-n), let X == ip (an empty set) and xo(O) = 1.. for k=1 to N-1 do begin if Ale ￠ X then begin X = X u {Ak}; a(k) = O; N(Ak) = 1, end. else begin a(k) == N(Ak); N(Ak) == N(Ak) +1 end '. end; (output : xo(O) = 1,{a(k)}k".-,i). Step 2. Ao{1 - xo(Ai)}. Xi(O)== Aixo(Ai) i for k=2 to N-1 do ' begin '. if Ak = Ai then a(k) = a(k) - 1; for 2' = O to a(k) do. begin if Ak = Ai then xi")(Ak) == -1. +1 1 [Aox8"")(Ak) + Aix6j"i)(Ak)xi(O)];. else if 2' = O then xij')(Ak)'== A, l A,[Ao{x,(A,) - 1} + A,x,(Ak).,(o)]. else. Xi'i)(Ak)=A,lA,[Aox8j)(Ak)+Aix8j)(Aic)xi(O)+j'xP'm'')(Ak)] ' .,,,. end;. end 't･ ..

(10) 52 .' Yutaka BABA for n=2 to N-1 do begin. '. x"(O) = A..,i(A.) [tillgl A-t,n-txt(o) - Aonxo(An) -- :i.llll,' Xt,n+i-txo(An)xt(o). n-1. - ]2]) Ai,n-ixi(An)];. i=1. for k=n+1 to N-1 do begin if Ak = A. then a(k) = a(k) - 1; for j' =O to a(k) do. begin if Ak == A. then xnij)(Ak) = -j. +1 1 [tL.li,' Ai,n-ixtti' ")(Ak) + Aonx6j'+i)(Ak). n'. +li.lli.,Xi:n+i-ixoij'i)(Ak)xi(o)]; ., else if j' = O then xaJ')(Ak) == A. ÷ A, [tL.;,' Ai,n-ixi(Ak) - ti.li,' A-i,n-ixi(o) + Aonxo(Ak). n. + 2 Ai,n+i-ixo(Ak)xi(O)]. i=o. else ,. X"ti)(Ak) == A. ! A, l:1I.ili,' Ai,n-iXS")(Ak) + Aonx8')(Ah). + :E 'Xi,.+i-ix6i')(Ak)xi(o) + ]'x￡j`i)(Ak)]. i=o. '. end end end; (OUtput : {xn(O)}.N-:ii). il[IEI.,ixk(o).t/2,,Xk,n-k-pflli;xn(O)] ･. step3xN(o)= i. Step4 Ftr(O)=1+2i"i.ixn(O). Step5 ll(O)=x.(O)ilj(O) (n=1,2,...,N) Remark 1 In step 2 of algorithm, A. - Ak is treated as the denominator. Therefore.

(11) A Unified Analysis to the Queue Length Distributions in MX (k)/G/1/N and GI/M' (k)/1/N Queues 53. the algorithm might be numerically unstable when the values of A. and Ak are very close but not equal.. Remark 2 We can find that the number of iterations in the algorithm is in the order of N4 where N is the maximum capacity of the system.. 5 SpecialCase In this'. section, we discuss a well studied special case, PBAS MX/G/1/N queue. Ifor the MX/G/1/N queue, we assume that the interarrival times in batch are mutually independent and exponentially distributed with common arrival rate A. Consecutive batch sizes are independent and have the common probability function {g.}.co--i. Iior a PBAS. MX(k)/G/1/N queue, we have. Ank"Agk (n=O,1,...,N-1;k=1,2,...,N-n), co. An,N-n=A￡gk (n=O,1,...,N-1), k=N-n An=A (n=O,1,...,N-1). Since A. = A (n =. O,1,..,,N - 1), we can simplify the general algorithm in section 4 remarkably. The simplified algorithm for a PBAS MX/G/1/N queue is' as follows,. Step1 Initializqtion:GivenA,{g.}.co--iandxo(O)=1･ Step 2 ,)t{1 - xo(A)}. Xi(O)= A.o(A) i for j' -- O to N-2 do vij)(A) = -]. +1 1[Ax,O"i)()L) + Ax8j")(A)xi(o)];. for n=2 to N-1 do begin. ln-1 co n-1 oo. x.(O)= Axo(A)i.o [￡ai(O)2Agh-)tg.co()t)-2xo(A)xi(O)￡Agk ic.n+i-i i=o k=n+2-i. n-1. - 2 Agn-ixi(A)]; i =1. for j' =O to N-n do x￡J')(A) = -2. +1 1[tllli Agn-ixS･J"i)(A) + Ag.x8j"')(A). n oo. +Ex6"'i)(A)xi(O) llil) Agk];. i=O k=n+2-i end;. Step 3. XN(O). =i[ N-1. Si) ]illl) Agh-ptN2"x.(o)1. lll[) vi(o) i= o. n=i+lh=n+1-i n=1 ].

(12) 54 Yutaka BABA step4 RI(O):i+￡#l,x.(o) Step5 I;:(O)==x.(O)1tr(O)' (n==1,2,...,N) Thi's algorithm coincides with the results obtained in Baba [1].. '. References Il] Baba, Y.,"The MX/C/1 queue with finite waiting room", Jonmat of the Operations ReseaTth Society of Japan, 27 (1984) 261-273.. [21 Henderson, W.,"Alternative approaches to the analysis of the M/a/1 and GI/M/1 queues", .lournal of the Ciperations Research Society of Japan, 15 (1972) 92-101.. [3] Hokstad, P.,"The G/M/m queue with finite waiting room", Joumal of Applied Probabedity, 12 (1975) 779-792,. [4] Keilson, J.,`CThe ergodic queue length distribution of queueing systems with finite capacity", Joumal of the Royal Stattstical Society, Series B, 28 (1966) 190-201.. [51 Kijima, M. and Makimoto, N.,"A unified approach:,,to GI/M(n)/1/K and M(n)/C/1/K queues via finite quasi-birth-death processes", Stochastic Models, 8 (1992) 269-288. [6] Li, H., Zhu, Y. and Yang, P.,"Computational analysis of M(n)/G/1/N queues with set up time", Cbmputers and Operations Research, 22 (1995) 829-840. [7] Neuts, M. F., Matrir-Geometwic Sotutions in Stochastie Modets-An Aigorithmic Approach, John Hopkins University Press (1981). [8] Takagi, H. Queueing Analysts, Vbt 2: Finite Systems, North Holland (1993). i9] Yang, P.,"A unified algorithn for computing the stationary queue length distributions. in M(k)/C/1/N and GJ/M(k)/1/N queues", Queueing Systems, 17 (1994) 383-401..

(13)