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

全文

(1)'. i i l. i. l. l. Symbol ic Calculation of Moments for an MX/G/1 Queue Yutaka Baba,. Department of Mathematics, Faculty of Education Yokohama National University 79-2 Tokiwadai, Hodogaya-ku, Yokohama 240, Japan. Abstract Wl] study the symbolic calculation of moments of queue size and waiting time for an MX/C/1 queue by using Mathematica, which is a software with functions for symbolic formula manipulation. We can calculate algebraically the moments of any order from the probability generating function of queue size distribution and the LaplaceStieltjes transform of waiting time distribution with first-come first-served discipline and nonpreemptive last-come first-served discipline.. Keywords : MX/C/1 queue, symbolic calculation, queue size, waiting time. 1. Introduction. The queue size and the waiting time are important characteristic quantities for an MX/G/1 queueing system. Several authors have studied the batch airrival queueing system MX/G/1. under first-come first-served (FCFS) discipline (see Chaudhry [2], Chaudhry and rllempleton [3], Cooper [4], Gross and Harris [5], Kleinrock [6], 'Ibkagi [8]). For last-come firsVserved (LCFS) discipline, Baba [1] has studied the MX/G/1 queue when the order of service is nonpreemptive LCFS with respect to batches and the order of service in a batch is random.. For both FCFS and LCFS systems, only first and second moments of queue size and waiting time were obtained in these papers. Though calculating the higher moments is straightforwaird in principle, the expressions for these derivatives soon become so compli-. cated as the order grows. Such limitations of manual calculation can be broken by using a software package for symbolic calculation such as Mathematica. Recently, Takagi and Sakamaki [9] studied the symbolic calculation of moments fdr. an M/G/1 queue by using Mathematiea. They obtained the moments of queue size and waiting time for FCFS and LCFS discipline up to the 10th moments of each quantity. In this paper, extending the result of [9], we show that Mathematica programs can calculate algebraically the moments of any order for an MX/G/1 queue from the probability generating function of queue size distribution and the Laplace-Stieltjes transform of waiting time distribution with FCFS discipline and nonpreemptive LCFS discipline. In.

(2) 58. Yutaka BABA. Section 2, we study the queue size in the system. In Section 3, we study the waiting time. in the FCFS discipline. In Section 4, we study the waiting time in the nonpreemptive LCFS discipline. In each of these sections, we provide a Mathematica program that calculates the moments of any order, rearranges the terms, and generates 71EX source statements for formatting. As examples, we obtained up to third moments of each quantity. The results are shown in the Appendices. All programs in this paper were written and executed by using Mathematica Ver. 2.1 for Windows 3.1 from Wolfram Research, Inc (see Wolfram [iO]).. Let us introduce the notation for an MX/G/1 queue considered in this paper. Customers arrive in batches according to a time homogeneous Poisson process with rate A. The batch size X is a random variable and P(X =: n) == g. (n == 1, 2,...) with probability. generating function (PGF). co G(z) == 2 g.z". (i). lzl ff{ 1.. n=1 We assume that nth factorial moments of X are finite and defined by g = E(X) = G(i)(1) and g(") = E[X(X - 1)･･･(X - n + 1)] = G(")(1) (n = 2,3,...). The Laplace-Stieltjes. transform (LST) of the distribution function (DF), the mean, and the nth moment of the service time are denoted by B'(s),b and b(n) (n = 2,3,...), respectively. The traffic intensity is p := Agb, which is assumed to be less than unity for the stability of the queue.. 2. Queue Size in the System. We consider the number of customers (queue size) L present in the system at an arbitrary time. The PGF fi(z) for P is given by (see rfakagi [8]) ll(z) =. (1 - p)(1 - z)B'(A - AG(z))'. (2). B"(A - AC(z)) - z. By differentiating the right hand side (r.h.s.) of (2) m times and evaluating at z = 1, we. obtain the mth factorial moment of L: E[L(L - 1)(L - 2)･･･(L - 7n + 1)] :I[(M)(1). (m = 1, 2,`･･). (3). The nth moment of L, E(L"), is obtained by E(Ln) =: ,ll"lll., (:l]n(M)(1). (n :1,2,...). (4). where {h} is a Stirling number of the second kind generated by Knuth [7] (sec. 1.2.6):. (g]-o,. (n) - i,. (k)=.(nfii)+(kzi,],. (n 2m) 1). (5).

(3) i. Symbolic Calculation of Moments for an MX/C/1 Queue. i. I !. 59. However it is very cumbersome to differentiate the r.h.s. of (.2) n times and evaluate at z = 1 even for n = 3. Therefore we provide a Mathematica program that calculateS' . E(L") by evaluating H(M)(1) (m -- 1,2,...,n) from the [I]aylor series expansion of (2) around. z = 1 and using (4). This program is shown in Figure 1.. gl[z]=(1-lambda g b) (1--z) B[lambda-lambda.G[z]]; g2[z]=B[lambda-lambda G[z]]-z; g [z] -gl [z] /g2 [z] ;. B [O] =1;. B) [O] =-b;. Derivative [n-] [B] [O]=Derivative [n] [b] *(-1)"n; G[1] =1; G' [1] -g;. Derivative [n-] [G] [1] --Derivative [n] [g] ;. taylor=Series[g[z],{z,1,3}]; coeff[n-]:=Coefficient[taylor,(z-1)An]*n!; el [n-] :=Expand [Apart [Sum [StirlingS2 [n,m] *coeff [m] ,{m,1,n}]]];. I. eltex[n-]:=Do[TeXForrn[el[i]]>>>mxglq.tex,{i,1,n}] Figure 1. Symbolic calculation of the moments of the queue size for an MX/G/1. queue Line 1-3 defines the function H(z) as in (2). Line 4-9 simply specifies the replacement of B*(O) by 1, B*(')(O) by -b, B'(n)(O) by (-1)nb(n), G(1) by 1, G(i)(1) by g, and G(")(1) by 9("). Line 10 expands II(z) in Taylor series around z == 1 up to o((z - 1)3). Line 11 sets the coefficient of (z - 1)n in the Taylor series, multiplied by n!, into coeff [n], which is n(")(1). Line 12 calculates E(L") and rearranges the terrns by using the Stirling number. ofthe second kind {h} given by the function Stir!ingS2[n,m] of Mathematica. Line 13 generates 7- EX source statements fbr E(Ln) (n = 1,2,3) in the mxglq.tex file. In this file, we make several global changes of symbols manually. The results of formatting are. shown in Appendix 1. In the MatheMatica program in Figure 1, we used the Taylor series expansion in order to obtain the derivative of (2) at z = 1 since the Limit function of Mathematica can not handle the indefinite form O/O.. 3. Waiting Time in an FCFS System. Leti' leU(F be the steady-state waiting time of an arbitrary customer when the service discipline is FCFS. Its LST, WP(s), is given by (see e.g. Cooper[4]). w" (s) - ,[, -(} -. PA)i;i'BI 8)iB] [i (g) lii .(,)] (6) By taking the first derivative of (6) at s = O, we have. E(wF)=2ti9bt!2))+2ggi21bp) (7).

(4) Yutaka BABA. 60. by using L'H6spital's rule twice. Further, by taking the second derivative of (6) at s = O,. we have. E(vvB) .. 3tlgbl3)) + i21g2-b(i))2, +3g{(13)e2p) (s) Ag(2)2b3 + (1 + p)g(2)b(2). +. 2g(1 - p)2. by using L'H6spital's rule 3 times.. To obtain the nth moment E(WB) = (-1)"WP(")(O), we can differentiate the r.h.s of. (6) n times at s = O. However this is very cumbersome even for n = 3. Therefore we provide a Mathematica program that calculates E(WB) by evaluating WP(")(O) from the Taylor series expansion of (6). This program is shown in Figure 2.. fl[s]=s (1-lambda g b) (1-G[B[s]]); f2[s]=(s-lambda+lambda G[B[s]]) (g (1-B[s])); f[s]=f1[s]/f2[s]; B [O] =1;. B) [O] =-b;. Derivative [n-] [B] [O] =Derivative [n] [b] *(-1)An;. G[1]-1; G' [1] -g;. Derivative [n-] [G] [1] =Derivative [n] [g] ; taylor=Series [f [s] ,{s,O,3}] ;. coeff[n-]:=Coefficient[taylor,s-n]*n!*(-1)An wfcfs[n-]:=Expand[Apart[coeff[n]]] wfcfstex[n.]:=Do[TeXForm[ewfcfs[i]]>>>wtfcfs.tex,{i,n}] Figure 2. Symbolic calculation of the moments of the waiting time for an FCFS. MX/G/1 queue Line 1-3 defines the function WP(s) ,that corresponds to (6). Line 10 expands WP(s) in Taylor series around s == O up to o(s3). Line 11 sets the coeff}cient of s" in the [faylor series, multiplied by (-1)"n!, into coeff [n], which is E(WB). Line 12 rearranges. the terms. Line 13 generates CTEX source statements for E(WB) (n = 1,2,3) in the wtfcfs.tex file. The results of formatting ance shown in Appendix 2. Though the expressions fbr E(I7VF) and E(W3) in (7) and (8) seem to be different. from those fbr E(WF) and E(Wl) in Appendix 2, it is easy to show that (7) and (8) coincide with the expressions in Appendix 2.. 4 Waiting Time in a Nonpreemptive LCFS System Let I7VL and WE(s) be the steady-state waiting time of an arbitrary customer and its LST of DF when the service discipline is nonpreemptive LCFS, respectively. Further, let e and e'(s) be the busy period initiated by a single customer and its LST of DF, respectively.. i.

(5) Symbolic Calculation of Moments for an MX/G/1 Queue. 61. I. i ;. Baba [1] showed that. I. I,VE(s) -. I :. (1 - p)[1 - G(e'(s))1 g[1 - e'(s)]. +. A[1 - G(e*(s))]. s + A - AG(0"(s)). (9). where e'(s) satisfies the following functional equation:. :. '. e'(s) - B*(s + A - Acif(e*(s))). (10). Erom (9) and (10), [1] showed that. E(WL). Agb(2) g(2)b = 2(1 - p) + 2g(1 - p). E(WZ). A2g2b(2)2 Agb(3) = 3(1 - p)2 + 2(1 - p)3 +. I. (11) g(3) b2. 3g(1 - p)2. (12). Ag(2)2b3 + (1 + p)g(2)b(2). +. 1. 2g(1 - p)3. after very cumbersome calculation.. It is well known that the mean waiting times in the FCFS and LCFS systems are same, that is, E(WF) = E(WL). Further, [1] showed that E(Wl) == E(WB)/(1 - p). The moments for the waiting time in the nonpreemptive LCFS system can be obtained frdm the moments for' the length of a busy period initiated by a single customer. The moments. of e, E(en) = (-1)"e(n)(O), can be found by solving the recursive equations obtained by differentiating O successively and setting s == O. We can calculate E(WL") by using e'(i)(O) (i == 1,2,...,n). The Mathematica program that calculates E(MiB) is shown in Figure 3.. Line 1 defines the equation (10). Line 9 solves the equation fbr e*(")(O) obtained by differentiating (10) n times and setting s = O, and places the solution into sol[n]. Line 11-13 defines WE(s). Line 14 expands Wi(s) in Taylor series around s = O up to o(s3). Line 15 sets the coefficient of s" in the Taylor series, multiplied by (-1)nn!, into coeff[n],which is E(WL"). Line 16 rearranges the terms. Line 17 generates 7EX source statements for E(VVB) (n = 1,2,3) in the wtlcfs.tex file; However, the execution time of this program increases rapidly as n grows due to many substitution and rearrangement operations. E(WL) (n = 1,2,3) a[re shown in Appendix 3. Though the expressions of E(WL) and E(I7VZ) in (11) and (12) seem to be different from those of E(VVL) and E(W2) in Appendix 3, it is easy to show that (11) and (12) coincide with the expressions in Appendix 3..

(6) Yutaka BABA. 62. eq=t [s]==B [s+lambda-lambda G[t'[s]]]; t [o] =i; B [O] =1;. B) [O] =-b;. Derivative [n-] [B] [O]=Derivative [n] [b]*(-1)-n;. G[1]=1; G' [1] =g;. Derivative [n-] [G] [1]=Derivative [n] [g] ;. sol[n-]:=Derivative[n] [t] [O]=Derivative[n] [t] [O] 1. Solve[D[eq,{s,n}] 1. s->O,Derivative[n] [t] [O]] Do [sol [i] ,{i,t,3}] ;. wl[s]=(1-lambda g b) (1--G[t[s]])/(g (1-t[s])); w2 [s]=lambda (1-G[t [s]])/(s+lambda-lambda G[t [s]]); w [s] =wl [s] +w2 [s] ;. taylor=Series[w[s],{s,O,3}]; coeff [n-] :=Coefficient [t aylor,sAn] ;. wlcfs[n-]:=Expand[Apart[coeff[n]*n!*(-1)"n]] wlcfstex[n-]:=Do[TeXForm[wlcfs[i]] >>>wtlcfs.tex,{i,1,n}] Figure 3. Symbolic calculation of the moments of the waiting time in an nonpreemp-. tive LCFS MX/G/1 queue. References [1] Baba, Y.,"On the MX/G/1 queue with and without vacation time under nonpreemptive last-come-first-served discipline", Joumal of the Operations Research Society of Japan, 30 (1987) 150-158.. [2] Chaudhry, M. L.,"The queueing system MX/G/1 and its ramifications", Naval Reseanch Logistics (2uarterly, 26 (1979) 667-674. [3] Chaudhry, M. L. and rllempleton, J. G. C., A First Course in Bulk Queues, John Wiley. and Sons, New Ybrk, !983. [4] Cooper, R. B., introduction to (?ueueing 71heory, 2nd ed. Elsevier North Holland, New. Ybrk, 1981. [5] Gross, D. and Harris, C. M., RLndamentals of Queueing 7H7beory, 2nd ed. John Wiley. and Sons, New Ybrk, 1985. [6] Kleinrock, L., Queueing Systems, 1!bl. 1. [Theory, John Wiley and Sons, New Ybrk, 1975. [71 Knuth, D. E., 7'7Le Art of Cbmputer Progrczmming, I!bl. t. IihLndamental Aigorithms.. Second edition, Addison-Wesley, Reading, Massachusetts.. I 1.

(7) Symbolic Calculation of Moments for an MX/G/I Queue 63 [8] Takagi, H., Queueing Analysis, Vbl. 1, VxZzcation and Priorzty Systems, North Holland,. 1991. 1. [9] Takagi, H. and Sakamak!, K ,"Symbolic calculation for an M/G/1 queue", Symposzum. on PeT:fbrmance Models for bjormation Communication ATetworks, (1995) 454-465. [10] Wblfram, S., 'Mathematica: A SIystem for Doing Mathematics by Computer, Second Edition, Addison-Wesley, Reading, Massachusetts, 1991.. Appendix 1: Moments of Queue Size E(L) -,e,- bi g: i2 + ,g2(i,2-b`Zl . ,b(i g-(2B). E(L2) ,. (, inP,), - i,b2-g2,?,2 + (bi g-3,A)3, . 3,gE A-2 ,bi2S - 3,b(g,3-A3,g(). b2 A2 g(2)2 g(2) +2(1-p)2+2(1-p)2M 2(1-p)2 + (1-p)2 +2(1-p)2 g4 A4 b(2)2 3bAg(2) 3b2g)t2g(2) 9 A2 b(2). g3A3b(3) bg`)t4b(3) bAg(3) ･. +3(1-p)2-3(1-p)2+3(1-p). '. E(L3) = (1 -p p), - 3(lb2-g2p?,2 + 3(lb3-g3pli - (bl` z`i`, + 72g(21 A-2 pbi2,) - 771g3-Ai)b,(2). 7 b2 g4 A4 3g4A4b(2)2 b(2). 3bg5.)t5b(2)2 3 g6 A6 b(2)3 7 b. A g(2). + 2(1-p)3 + (1-p)3 ' (1-p)3 +4(1-p)3 +2(1-p)3 7 b2 g A2 7g(2) b3 g2 A36gA2b(2)g(2) g(2) 6bg2A3b(2)g(2). - (1-p)3 + 2(1-p)3 + (1-p)3 ' (1-p)3 3g3A4b(2)2g(2) 3bg4A5b(2)2g(2) 3b2A2g(2)2 3b3g)t3g(2)2. + (1-p)3 - 4(1-p)3 + (1-p)3 - (1-p)3. 3 A2 b(2)3g(2)2 b g A3 b(2) 3g(2)2 b3 A3 2g3,)t3b(3) g(2)3. 4bg`A`b(3) + 4(1-p)3 + 2(1-p)3 +4(1-p)3 + (1-p)3 - (1-p)3 2 b2 g5 A5g5A5b(2)b(3) b(3) bg6A6b(2)b(3) 3 g2 A3 g(2) b(3). + (1-p)3 + (1-p)3 - (1-p)3 + 2(1-p)3 2 b g3 A4 g(2) b2b(3) g4 A5 g(2) b(3) 2bAg(3) 4b2gA2g(3) 2 b3 g2 A3 g(3) - (1-p)3 + 2(1-p)3 +(1-p)3- (1-p)3 + (1-p)3 g)t2b(2)g(3) bg2A3b(2)g(3) b2A2g(2)g(3). b3gA3g(2)g(3) g4 A4 b(4). + (1-p)3 - (1-p)3 + (1-p)3 - (1-p)3 +4(1-p)3. b g5 A5 b2 b(4)g6 A6 b(4)bAg(4) - 2(1 - p)3 + 4(1 - p)3 +4 (1 - p).

(8) 64 Yutaka BABA Appendix 2: Moments of Waiting Time in an FCFS. System ,. E(W)7) = 2g(t b-(2)) + 2gb({(2-) p). g2 A2 b(2)2. bAb(2)g(2) b3)tg(2)2 g A b(3). E(W3) = 2(1 - p)2 +b(2) 2g (1 g(2) - p)2 + 2(1 - p)2 + 2g (1 - p)2 + 3(1 - p)2. -bg2A2b(3)+ b2g(3). 3(1 - p)2 3g (1 - p). E(ws) = 349(3iAi biii3 + 32A(.i(2-'2pg)(,2' + 3b4g (Ai2 -b(%,g(2) + 94b2,lib(2' gp()2,'2 + ib5(l2-g(iii. +g2(Ai2e(2p))b,(3) bgliA3-b)2i,b(3)+2gg((2i)2i(3i), b22g(Ai2g(2p))2(3)+gb(bl21tgi3)),. -b2Ab(2)g(3)+b4Ag(2)g(3)-b5A2g(2)g(3)+ gAb(`) -bg2A2b(4). (1 - p)3g (1 - p)3(1 b2g3A3b(4) b3g(4) + 4(1-p)3 +4g (1-p). - p)3 2(1 - p)3 4(1 - p)3. Appendix 3: Moments of Waiting Time in a Nonpreemptive LCFS System E(wL) = 2g(Al b-(2)) + 2gb({(2-) p). g2 A2 b(2)2. b)tb(2)g(2) b3Ag(2)2 g A b(3). E(WZ) == 2(1 - p)3 b(2) + 2g (1 g(2) m p)3 + 2(1 - p)3 + 2g (1 - p)3 + 3(1 - p)3. -bg2A2b(3)+ b2g(3) 3(1 - p)3 3g (1 - p)2 E(w2) .. 32g(31At li(il3 + 94A(l(2-)2pg)(,2) + 3b2g (A12 !l(2i2),g(2) + 3b2 4g2(IA3-b(p2))2,g(2). + 3 bg2 (Albli2)pg)(,2)2 + 3 b32 A(i b{2)gi2)2 + 23 gb5(ll2.g(ii3, + 3 gi)1{22(2i)b,(3). -3b,g3(i3-b(,2i,b(3'+2,g((2il(3i), b3g22(i3lhg(il,b(3'+,b(bi21gil',-bitibS",9)(i'. -b3g)t2b(2)g(3)+3b4)tg(2)g(3) 3b5A2g(2)g(3)+ gAb(`) -bg2)t2b(4). 2(1 - p)5 2g (1 - p)52(1. b2 g3 A3 b(4)b3. g(4). + 4(1-p)5 +4g(1-p)3. - p)5 2(1 - p)5 4(1 - p)5.

(9)