# Queue Length and Server Content Distribution in an Infinite-Buffer Batch-Service Queue with Batch-Size-Dependent Service

Authors: U. C. Gupta; S. Pradhan
Journal: Advances in Operations Research
 (2015)

---

## Abstract

We analyze an infinite-buffer batch-size-dependent batch-service queue with Poisson arrival and arbitrarily distributed service time. Using supplementary variable technique, we derive a bivariate probability generating function from which the joint distribution of queue and server content at departure epoch of a batch is extracted and presented in terms of roots of the characteristic equation. We also obtain the joint distribution of queue and server content at arbitrary epoch. Finally, the utility of analytical results is demonstrated by the inclusion of some numerical examples which also includes the investigation of multiple zeros.


---

## Body

## 1. Introduction

Recently, Banerjee and Gupta [1] analyzed a finite-buffer batch-service queue with batch-size-dependent service and obtained joint distribution of queue and server content (i.e., number in the queue as well as with the server) at departure and arbitrary epochs. However, no such results are available so far in case of an infinite-buffer queue. This paper considers an infinite-buffer single server queue with Poisson arrivals and general service time distribution where customers are served in batches according to general bulk service, (a,b) rule, and service times of the batches depend on the number of customers within the batch under service process. It is often challenging to obtain the joint distribution of queue and server content of this model due to the enumerable state space and increase in dimensionality that arises in this case. Our main objective in this paper is to develop a tractable yet easily implementable procedure to obtain the joint distribution of the queue and the server content at departure and arbitrary epochs. Banerjee and Gupta [1] used embedded Markov chain technique to analyze the finite-buffer queue wherein they first obtain transition probability matrix (TPM), which appears to be very complex in structure. Further it becomes quite challenging (if not impossible) to extend this TPM for the case of infinite-buffer queue and then to find out the analytic expression of probability generating function (pgf) of queue and server content. In this paper, we use supplementary variable technique (which essentially surpasses the direct use of the TPM) to obtain the bivariate pgf of queue and server content at departure epoch of a batch in a much simpler way and also to establish the relation between arbitrary and departure epoch as a byproduct. Therefore, new contributions in this paper are (i) construction of bivariate pgf of queue and server content at departure epoch of a batch without using embedded Markov chain technique, (ii) extraction of joint distribution (queue and server content) from the bivariate pgf which has been expressed in terms of roots of so called characteristic equation which arise in this case, (iii) illustration of analytical procedure through several numerical examples, and (iv) investigation of the cases even if the characteristic equation has nonzero repeated roots. More precisely, repeated roots occur for Erlang (Em), m≥2; service time distribution and number of roots depend on the threshold value “a” and the maximum capacity “b” and multiplicity of each root depends on “m”.Recent studies on this model have been carried out by Bar-Lev et al. [2], who derived the pgf of only queue content at departure epoch but did not use it due to the complexity involved in the inversion process. However, they obtained queue-size distribution by truncating the TPM into a finite state space and then solving a finite number of system of equations. Later, Chaudhry and Gai [3] have considered this pgf and inverted it using the method of roots in order to derive the distribution of queue content only. It may be noted that both authors did not obtain distribution of queue content at arbitrary epoch. Moreover, from their analysis, one can not get joint distribution of queue and server content.As a counterpart of continuous-time queues, in discrete-time queues, a series of papers, considered by Claeys et al. [4–6] deals with such queues. In [4], they considered GeoX/G(l,c)/1 queue and obtained joint pgf of the queue and the server content and from this they extracted marginal pgfs. However, they stayed away from inverting the joint pgf to obtain complete joint distribution of queue and server content rather restricted on finding tail distribution and performance measures only. Further, in [5], they analyze the same queueing model under discrete-batch Markovian arrival process (D-BMAP) and derived joint vector generating function of the queue content, the server content, and the remaining service time of the batch under service and then extracted marginal pgfs for several admissible quantities such as queue content when server is inactive, server content is at the end of service, and so forth. They also elaborated upon the influence of correlation of the arrival process on the mean system content. Furthermore, in [6], they approximated tail probabilities of the customer delay in GeoX/G(l,c)/1 queue. It has been emphasized that neglecting of batch-size-dependent service can lead to a devastating inaccuracy of the approximation of the tail probabilities.The rest of the paper is organized as follows: the next section describes the model in detail and governing equations. Section3 contains the derivation of bivariate pgf and extraction of joint distribution from that pgf at departure epoch of a batch. The joint distribution at arbitrary epoch is obtained in Section 4 while Section 5 shows the applicability of our analytical results through some specific service time distributions. The paper ends with conclusion.


## 2. Model Description and Governing Equations

Although the model description and governing equations have been well discussed by Banerjee and Gupta [1] for finite-buffer queue, however, for the sake of completeness it is again discussed briefly in case of infinite-buffer.(i)
Arrival Process. Customers arrive at the system according to Poisson process with rate λ.(ii)
Batch-Service Discipline. The single server serves the customers in batches according to general bulk service (a,b) rule.(iii)
Service Process. The service time (Tr) of a batch of size r (a≤r≤b) follows general distribution with probability density function (p.d.f.) sr(t), distribution function Sr(t), the Laplace-Stieltjes transform (L.-S.T.) S~r(θ), and the mean service time 1/μr=sr=-S~r(1)(0), a≤r≤b, where S~r(1)(0) is the derivative of S~r(θ) evaluated at θ=0.(iv)
Utilization Factor. The traffic intensity of the system ρ=λsb/b<1 which ensures the stability of the system.Let us define the state of the system at time t as (i)
Nq(t) ≡ number of customers in the queue waiting for service,(ii)
Ns(t) ≡ number of customers with the server,(iii)
U(t) ≡ remaining service time of the batch in service.Further, we define(1)pn,0t=Pr⁡Nqt=n,Nst=0,0≤n≤a-1,pn,ru,tdu=Pr⁡Nqt=n,Nst=r,u<Ut<u+du,u≥0,n≥0,a≤r≤b.In steady-state, let us define(2)pn,0=limt→∞⁡pn,0t,0≤n≤a-1,pn,ru=limt→∞⁡pn,ru,t,u≥0,n≥0,a≤r≤b.Relating the states of the system at two consecutive time epochs t and t+dt and using supplementary variable technique, we obtain, in steady-state, the following differential equations:(3)0=-λp0,0+∑r=abp0,r0,(4)0=-λpn,0+λpn-1,0+∑r=abpn,r0,1≤n≤a-1,(5)-ddup0,au=-λp0,au+λpa-1,0sau+∑r=abpa,r0sau,(6)-ddup0,ru=-λp0,ru+∑j=abpr,j0sru,a+1≤r≤b,(7)-ddupn,ru=-λpn,ru+λpn-1,ru,a≤r≤b-1,n≥1,(8)-ddupn,bu=-λpn,bu+λpn-1,bu+∑r=abpn+b,r0sbu,n≥1.Further, let us define(9)S~rθ=∫0∞e-θudSru=∫0∞e-θusrudu,a≤r≤b,p~n,rθ=∫0∞e-θupn,rudu,a≤r≤b,n≥0,pn,r≡p~n,r0=∫0∞pn,rudu,a≤r≤b,n≥0.Multiplying (5)–(8) by e-θu and integrating with respect to u over 0 to ∞, we obtain(10)λ-θp~0,aθ=λpa-1,0S~aθ+∑r=abpa,r0S~aθ-p0,a0,(11)λ-θp~0,rθ=∑j=abpr,j0S~rθ-p0,r0,a+1≤r≤b,(12)λ-θp~n,rθ=λp~n-1,rθ-pn,r0,a≤r≤b-1,n≥1,(13)λ-θp~n,bθ=λp~n-1,bθ+∑r=abpn+b,r0S~bθ-pn,b0,n≥1.As our major concern is to perceive the joint distribution of queue content as well as server content at departure and arbitrary epoch, we define the following probabilities at departure epoch:(14)pn,r+=Pr⁡ncustomersinthequeueatdepartureepochofabatchandrcustomerswiththedepartingbatch,n≥0,a≤r≤b,(15)pn+=Pr⁡ncustomers  in  the  queue  at  departure  epoch  of  a  batch=∑r=abpn,r+,n≥0,(16)qr+=Pr⁡rcustomers  with  the  departing  batch=∑n=0∞pn,r+,a≤r≤b.Now we propose the following lemmas which will be used later.Lemma 1.
The probabilitiespn,r+ and pn,r(0) are connected by the relation(17)pn,r+=pn,r0∑m=0∞∑r=abpm,r0.Proof.
Aspn,r+ is proportional to pn,r(0), using ∑n=0∞∑r=abpn,r+=1 we obtain the desired result.Lemma 2.
The value of∑n=0∞∑r=abpn,r(0) is given by(18)∑n=0∞∑r=abpn,r0=1-∑i=0a-1pi,0ω,where ω=sa∑n=0apn++∑n=a+1bsnpn++sb∑n=b∞pn+.Proof.
Using (3) in (4), we get(19)λpn,0=∑m=0n∑r=abpm,r0,0≤n≤a-1.Using (19) in (10), we get(20)λ-θp~0,aθ=S~aθ∑m=0a∑r=abpm,r0-p0,a0.Summing (20) and (11) to (13), we obtain(21)∑n=0∞∑r=abp~n,rθ=1-S~aθθ∑n=0a∑r=abpn,r0+∑n=a+1b∑r=ab1-S~nθθpn,r0+1-S~bθθ∑n=b+1∞∑r=abpn,r0.Taking limit as θ→0 in the above expression and using L’Hôspital’s rule, the normalizing condition ∑n=0a-1pn,0+∑n=0∞∑r=abpn,r=1, and after a little bit of manipulation, we obtain the desired result.


## 3. Joint Distribution of Queue Content and Number with the Departing Batch

In order to obtainpn,r+,n≥0,a≤r≤b, we further define the following pgfs:(22)Pz,y,θ=∑n=0∞∑r=abp~n,rθznyr,z<1,y<1,(23)P+z,y=∑n=0∞∑r=abpn,r+znyr,z<1,y<1,(24)P+z,1=∑n=0∞∑r=abpn,r+zn=∑n=0∞pn+zn=P+z.Multiplying (10)–(13) by appropriate powers of z and y, summing over n from 0 to ∞ and r from a to b and using (22), we get(25)λ-θ-λzPz,y,θ=S~aθ∑n=0a-1∑r=abpn,r0ya+∑n=ab∑r=abS~nθpn,r0yn+S~bθ∑n=b+1∞∑r=abpn,r0zn-byb-∑n=0∞∑r=abpn,r0znyr.Now substituting θ=λ-λz in (25) and using (17), (16), (15), and (23), we obtain(26)P+z,y=Kaz∑n=0a-1pn+ya+∑n=abpn+Knzyn+Kbz∑n=b+1∞pn+zn-byb,where K(r)(z)=S~r(λ-λz) is the pgf of kj(r) and(27)kjr=Pr⁡jarrivals  during  the  service  time  of  a  batch  of  sizer=∫0∞e-λtλtjj!srtdt.Substituting y=1 in (26), using (24) and after a little bit of manipulation, we obtain(28)P+z=∑n=0a-1pn+zbKaz-znKbz+∑n=ab-1pn+zbKnz-znKbzzb-Kbz.Finally, using (28) in (26) and after some algebraic simplification, we get(29)P+z,y=∑n=0a-1pn+KazKbzyb-ya+Kazzbya-Kbzznyb+∑n=ab-1pn+KbzKnzyb-yn+Knzzbyn-Kbzznybzb-Kbz.Remark 3.
To the best of the authors’ knowledge, no such bivariate pgf (expressed in (29)) of queue content as well as number with the departing batch is available so far in the literature.Remark 4.
The pgf expressed in (28) for the queue content at departure epoch exactly matches with the pgf given in Bar-Lev et al. [2, page 230] which was obtained using embedded Markov chain technique.One can observe from (29) that P+(z,y) is a bivariate pgf and has been expressed in a compact form except for the b unknowns {pn+}0b-1. One can further note that these b unknowns are the same as those b unknowns appearing in the numerator of (28). Now our first task is to get these unknowns from (28) before any further analysis is carried out using (29). Now in order to determine them, we make use of Rouché’s theorem, by which it can be shown that the denominator of (28), zb-K(b)(z), has b zeroes (say, z0=1,z1,z2,…,zb-1) in the closed complex unit disk {z∈C:|z|≤1}. Due to the analytic property of the pgf in the closed complex unit disk, these zeroes are necessarily also zeroes of the numerator of (28), which leads to b-1 linear equations as(30)∑n=0a-1pn+zibKazi-zinKbzi+∑n=ab-1pn+zibKnzi-zinKbzi=0,1≤i≤b-1.As we need one more equation in order to get b linear equations, we obtain it using normalizing condition P+(1)=1. After applying L’Hôspital’s rule, it leads to(31)∑n=0a-1pn+b-n+λsa-sb+∑n=ab-1pn+b-n+λsn-sb=b-bρ.Now the b unknowns can be determined by solving (30) and (31).


### 3.1. Extraction of Joint Probabilitiespn,r+ from the Bivariate pgf

Having found the unknownspn+n=0b-1, P+(z,y) is now completely known to us. Our main objective is to extract the probabilities pn,r+,n≥0,a≤r≤b, from P+(z,y). In order to get these, we need to invert the bivariate pgf P+(z,y). For this purpose, we first accumulate the coefficient of yj, a≤j≤b, from both the sides of (29). These are given as(32)coefficient  ofya:∑n=0∞pn,a+zn=∑i=0api+Kaz,(33)coefficient  ofyj:∑n=0∞pn,j+zn=pj+Kjz,a+1≤j≤b-1,(34)coefficient  ofyb:∑n=0∞pn,b+zn=KbzKaz∑i=0api++∑i=a+1b-1pi+Kiz-∑i=0b-1pi+zizb-Kbz.Now collecting the coefficient of zn from both the sides of (32) and (33), we obtain(35)pn,a+=∑i=0api+kna,n≥0,pn,j+=pj+knj,n≥0,a+1≤j≤b-1.As pn,r+,n≥0,a≤r≤b-1, are already known, we turn our focus on determination of pn,b+,n≥0, from (34). In order to get these probabilities, we invert the right hand side of (34) which is a completely known function in z for a specific service time distribution.In order to simplify the calculation, let us assume that the L.-S.T of service time distributionS~r(θ), a≤r≤b, is a rational function and is given by S~r(θ)=P(θ)/Q(θ),a≤r≤b, where P(θ) and Q(θ) are polynomials of degrees l and m, respectively, with l≤m. Then, substituting K(r)(z)=S~r(λ-λz)=P(λ-λz)/Q(λ-λz),a≤r≤b, in the right-hand side of (34) and after some simplification it can be proved that degree of the numerator of (34) is always less than the degree of the denominator of (34).Let us denote numerator of (34) as N(z) (after dividing the numerator of (34) by the highest power coefficient of the denominator of (34)) and the denominator as D(z)=zb-K(b)(z). Let us also assume that D(z) has degree d. To extract the probabilities {pn,b+}n=0∞, we need to know about the zeroes of D(z). Let us call these zeroes βi,i=1,2,…,d. Now applying the partial fraction technique, ∑n=0∞pn,b+zn can be uniquely written as(36)∑n=0∞pn,b+zn=∑i=1dciβi-zfor some constants ci’s, which can be determined using residue theorem as(37)ci=-NβiD′βii=1,2,…,d.Now collecting the coefficient of zn from both the sides of (36), we obtain(38)pn,b+=∑i=1dciβin+1,n≥0.This completes the evaluation of joint distributions of number of customers in the queue and number with the departing batch at departure epoch of a batch.Remark 5.
It may be remarked here that if some of the zeroes of the characteristic equation are repeated, then the above procedure has to be slightly modified to extract the joint distribution. We have included one such example in the numerical section.Remark 6.
One can also obtain the tail distribution from (34) using single root of D(z). This root is the smallest with absolute value greater than one, real and strictly positive. Otherwise, if the denominator D(z) has two complex conjugate zeros or one negative real zero with smallest modulus, this can lead to negative probabilities for sufficiently large values of n; see Desmet et al. [7]. Thus, we can find the following approximation of the tail distribution for sufficiently large n as (39)pn,b+≅δζ0n+1,whereδ=-Nζ0D′ζ0and ζ0 is the real positive zero of D(z) with the smallest modulus greater than one.Remark 7.
For some specific service time distributions, the probabilitieskj(r),a≤r≤b,j≥0, can be easily computed by inverting the pgf K(r)(z).


## 3.1. Extraction of Joint Probabilitiespn,r+ from the Bivariate pgf

Having found the unknownspn+n=0b-1, P+(z,y) is now completely known to us. Our main objective is to extract the probabilities pn,r+,n≥0,a≤r≤b, from P+(z,y). In order to get these, we need to invert the bivariate pgf P+(z,y). For this purpose, we first accumulate the coefficient of yj, a≤j≤b, from both the sides of (29). These are given as(32)coefficient  ofya:∑n=0∞pn,a+zn=∑i=0api+Kaz,(33)coefficient  ofyj:∑n=0∞pn,j+zn=pj+Kjz,a+1≤j≤b-1,(34)coefficient  ofyb:∑n=0∞pn,b+zn=KbzKaz∑i=0api++∑i=a+1b-1pi+Kiz-∑i=0b-1pi+zizb-Kbz.Now collecting the coefficient of zn from both the sides of (32) and (33), we obtain(35)pn,a+=∑i=0api+kna,n≥0,pn,j+=pj+knj,n≥0,a+1≤j≤b-1.As pn,r+,n≥0,a≤r≤b-1, are already known, we turn our focus on determination of pn,b+,n≥0, from (34). In order to get these probabilities, we invert the right hand side of (34) which is a completely known function in z for a specific service time distribution.In order to simplify the calculation, let us assume that the L.-S.T of service time distributionS~r(θ), a≤r≤b, is a rational function and is given by S~r(θ)=P(θ)/Q(θ),a≤r≤b, where P(θ) and Q(θ) are polynomials of degrees l and m, respectively, with l≤m. Then, substituting K(r)(z)=S~r(λ-λz)=P(λ-λz)/Q(λ-λz),a≤r≤b, in the right-hand side of (34) and after some simplification it can be proved that degree of the numerator of (34) is always less than the degree of the denominator of (34).Let us denote numerator of (34) as N(z) (after dividing the numerator of (34) by the highest power coefficient of the denominator of (34)) and the denominator as D(z)=zb-K(b)(z). Let us also assume that D(z) has degree d. To extract the probabilities {pn,b+}n=0∞, we need to know about the zeroes of D(z). Let us call these zeroes βi,i=1,2,…,d. Now applying the partial fraction technique, ∑n=0∞pn,b+zn can be uniquely written as(36)∑n=0∞pn,b+zn=∑i=1dciβi-zfor some constants ci’s, which can be determined using residue theorem as(37)ci=-NβiD′βii=1,2,…,d.Now collecting the coefficient of zn from both the sides of (36), we obtain(38)pn,b+=∑i=1dciβin+1,n≥0.This completes the evaluation of joint distributions of number of customers in the queue and number with the departing batch at departure epoch of a batch.Remark 5.
It may be remarked here that if some of the zeroes of the characteristic equation are repeated, then the above procedure has to be slightly modified to extract the joint distribution. We have included one such example in the numerical section.Remark 6.
One can also obtain the tail distribution from (34) using single root of D(z). This root is the smallest with absolute value greater than one, real and strictly positive. Otherwise, if the denominator D(z) has two complex conjugate zeros or one negative real zero with smallest modulus, this can lead to negative probabilities for sufficiently large values of n; see Desmet et al. [7]. Thus, we can find the following approximation of the tail distribution for sufficiently large n as (39)pn,b+≅δζ0n+1,whereδ=-Nζ0D′ζ0and ζ0 is the real positive zero of D(z) with the smallest modulus greater than one.Remark 7.
For some specific service time distributions, the probabilitieskj(r),a≤r≤b,j≥0, can be easily computed by inverting the pgf K(r)(z).


## 4. Joint Distribution of Queue and Server Content at Arbitrary Epoch

Utilizing the completely known distribution of queue and server content at departure epoch of a batch, we develop the following result in order to acquire the distribution of queue and server content at arbitrary epoch. The procedure is similar to the one given in [1, page 62]. However, for the sake of completeness, results are given here for infinite-buffer queue.Theorem 8.
The probabilities{pn,0,pn,r} and {pn,r+,pn+} are related by(40)pn,0=E-1∑j=0npj+,0≤n≤a-1,pn,a=E-1∑j=0apj+-∑j=0npj,a+,n≥0,pn,r=E-1pr+-∑j=0npj,r+,a+1≤r≤b-1,n≥0,pn,b=E-1∑j=bb+npj+-∑j=0npj,b+,n≥0,where E=λω+∑i=0a-1a-ipi+ and ω=sa∑i=0api++∑i=a+1bsipi++sb∑i=b+1∞pi+.Once the joint distribution of queue and server content at arbitrary epoch is known, we can obtain other significant distributions such as distribution of queue content,pnqueue,n≥0, and distribution of the server content in undergoing service, prser (r=0, anda≤r≤b). Moreover, the distribution of the system content (including number of customers with the server), pnsys,n≥0, which is more relevant, is given by (41)pnsys=pn,00≤n≤a-1,∑r=amin⁡b,npn-r,ra≤n≤b,∑r=abpn-r,rn≥b+1.As all the state probabilities are known, the utmost performance measures of the present model can be easily evaluated and are presented as follows: (i)
Average number of customers in the queue(Lq)=∑n=0∞npnqueue.(ii)
Average number of customers in the system(L)=∑n=0∞npnsys.(iii)
Average number of customers with the server(Ls)=∑r=abrprser.(iv)
Average waiting time of a customer in the queue(Wq)=Lq/λ as well as in the system W=L/λ.(v)
The probability that the server is idlePidle=p0ser=∑n=0a-1pn,0.The above performance measures play a significant role in evaluating the real system.


## 5. Numerical Illustration

Based on the theoretical analysis in Sections3 and 4, we illustrate numerical results for assorted service time distributions, namely, exponential (M), Erlang (E4), and deterministic (D). Extensive computation work has been executed using Maple 13 http://www.maplesoft.com/products/maple/ on PC running on Windows 7 with Intel Core i5-3470 CPU Processor @ 3.20 GHz with 4.00 GB of RAM, for both the high and low values of the model parameters. Although a vast number of tables can be generated, only a few of them that contain significant results are appended here. Parameter values are displayed at the title of the each table while the bottoms of the tables contain some performance measures.First we present the joint distributionpn,r+ and pn,r, n≥0,a≤r≤b, for exponential (M) service time distribution in Tables 1-2. The objective of this example is to match our results with the existing results available in the literature.Table 1
Joint distribution of queue and server content at departure epoch (pn,r+)  of an M/Gn(5,15)/1 queue with G∼M, λ=252, μa=11, μr=μr-1+1, and ρ=0.8.
n
p
n
,
5
+
p
n
,
6
+
p
n
,
7
+
p
n
,
8
+
p
n
,
9
+
p
n
,
10
+
p
n
,
11
+
p
n
,
12
+
p
n
,
13
+
p
n
,
14
+
p
n
,
15
+
p
n
+
0
0.003264
0.000634
0.000693
0.000751
0.000808
0.000864
0.000918
0.000970
0.001021
0.001070
0.001118
0.012112
1
0.003127
0.000606
0.000659
0.000712
0.000763
0.000812
0.000860
0.000906
0.000950
0.000992
0.002146
0.012531
2
0.002997
0.000578
0.000627
0.000674
0.000720
0.000763
0.000805
0.000845
0.000883
0.000919
0.003090
0.012903
3
0.002871
0.000552
0.000596
0.000639
0.000679
0.000718
0.000754
0.000789
0.000821
0.000851
0.003956
0.013228
4
0.002751
0.000527
0.000567
0.000605
0.000641
0.000675
0.000707
0.000736
0.000764
0.000789
0.004749
0.013511
5
0.002636
0.000503
0.000539
0.000573
0.000605
0.000635
0.000662
0.000687
0.000710
0.000731
0.005472
0.013754
10
0.002129
0.000398
0.000419
0.000437
0.000453
0.000467
0.000478
0.000487
0.000494
0.000499
0.008205
0.014465
50
0.000385
0.000062
0.000056
0.000050
0.000045
0.000040
0.000035
0.000031
0.000027
0.000024
0.008117
0.008872
100
0.000045
0.000006
0.000004
0.000003
0.000002
0.000002
0.000001
0.000000
0.000000
0.000000
0.002615
0.002678
200
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000170
0.000170
300
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000010
0.000010
370
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000001
0.000001
≥380
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
q
r
+
0.078040
0.013960
0.014132
0.014272
0.014383
0.014465
0.014522
0.014556
0.014567
0.014558
0.792539
1.000000Table 2
Joint distribution of queue and server content at arbitrary epoch (pn,r) of an M/Gn(5,15)/1 queue with G∼M.
n
p
n
,
0
p
n
,
5
p
n
,
6
p
n
,
7
p
n
,
8
p
n
,
9
p
n
,
10
p
n
,
11
p
n
,
12
p
n
,
13
p
n
,
14
p
n
,
15
p
n
q
u
e
u
e
0
0.000892
0.005507
0.000981
0.000989
0.000996
0.001000
0.001002
0.001002
0.001001
0.000998
0.000993
0.000988
0.016350
1
0.001815
0.005277
0.000937
0.000941
0.000943
0.000943
0.000942
0.000939
0.000934
0.000928
0.000920
0.001897
0.017417
2
0.002765
0.005056
0.000894
0.000895
0.000893
0.000891
0.000886
0.000879
0.000872
0.000862
0.000853
0.002731
0.018480
3
0.003740
0.004845
0.000853
0.000851
0.000846
0.000840
0.000833
0.000824
0.000813
0.000802
0.000790
0.003497
0.019537
4
0.004735
0.004642
0.000814
0.000809
0.000802
0.000793
0.000783
0.000772
0.000759
0.000746
0.000732
0.004197
0.020587
5
0.004448
0.000778
0.000770
0.000760
0.000749
0.000736
0.000723
0.000709
0.000694
0.000678
0.004837
0.015881
10
0.003593
0.000616
0.000598
0.000580
0.000561
0.000541
0.000522
0.000501
0.000482
0.000463
0.007252
0.015710
50
0.000650
0.000096
0.000080
0.000067
0.000055
0.000046
0.000038
0.000032
0.000026
0.000021
0.007175
0.008288
100
0.000077
0.000009
0.000006
0.000004
0.000003
0.000002
0.000001
0.000001
0.000000
0.000000
0.002311
0.002417
200
0.000001
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000151
0.000152
300
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000009
0.000009
370
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000001
0.000001
≥380
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
Total(prser)
0.013947(p0ser)
0.131681(p5ser)
0.021593(p6ser)
0.020178(p7ser)
0.018923(p8ser)
0.017798(p9ser)
0.016781(p10ser)
0.015856(p11ser)
0.015010(p12ser)
0.014231(p13ser)
0.013511(p14ser)
0.700489(p15ser)
1.000000
L
=
56.106800,     Lq=43.462175, and    Ls=12.644624
P
i
d
l
e
=
0.013947,     W=0.222646,  and   Wq=0.172468The numerical results given in Table2 using our methodology for exponential (M) service time distribution exactly match with the existing results of Table 3 given in Maity and Gupta [8]. The results presented in column 2 and row 1 of Table 2 match exactly with the last two rows of Table  3 of [8] which was obtained as a special case from M/Mn(a,Y)/1 queue. The methodology used in [8] is the matrix geometric method while we use probability generating function approach. It may be remarked here that, in [8], there is a misprint in the value of the arrival rate λ=232. It should be λ=252 and other parameters (which are shown in Table 2) in our example are taken the same as in [8].Table 3
Joint distribution of queue and server content at departure epoch (pn,r+)  of an M/Gn(7,15)/1 queue with G∼E4, λ=80, μ=0.75, μr=(r-1)μ, and ρ=0.507936.
n
p
n
,
7
+
p
n
,
8
+
p
n
,
9
+
p
n
,
10
+
p
n
,
11
+
p
n
,
12
+
p
n
,
13
+
p
n
,
14
+
p
n
,
15
+
p
n
+
0
0.000258
0.000099
0.000153
0.000219
0.000292
0.000370
0.000448
0.000524
0.000594
0.002957
1
0.000842
0.000315
0.000473
0.000655
0.000850
0.001048
0.001237
0.001410
0.002109
0.008939
2
0.001719
0.000624
0.000910
0.001225
0.001546
0.001854
0.002133
0.002369
0.004502
0.016882
3
0.002806
0.000989
0.001401
0.001832
0.002249
0.002626
0.002942
0.003185
0.007498
0.025528
4
0.004009
0.001371
0.001886
0.002397
0.002862
0.003253
0.003551
0.003748
0.010738
0.033815
5
0.005237
0.001737
0.002321
0.002867
0.003331
0.003685
0.003918
0.004031
0.013887
0.041014
6
0.006412
0.002064
0.002678
0.003216
0.003634
0.003913
0.004053
0.004065
0.016684
0.046719
7
0.007477
0.002335
0.002943
0.003434
0.003775
0.003957
0.003993
0.003904
0.018962
0.050780
8
0.008393
0.002544
0.003113
0.003531
0.003775
0.003853
0.003787
0.003609
0.020643
0.053248
9
0.009135
0.002687
0.003193
0.003520
0.003661
0.003637
0.003482
0.003235
0.021717
0.054267
10
0.009695
0.002767
0.003193
0.003421
0.003461
0.003347
0.003122
0.002827
0.022220
0.054053
20
0.007889
0.001665
0.001434
0.001156
0.000887
0.000656
0.000470
0.000330
0.012376
0.026862
30
0.003194
0.000499
0.000320
0.000194
0.000113
0.000064
0.000035
0.000019
0.003808
0.008246
40
0.000949
0.000110
0.000052
0.000024
0.000010
0.000004
0.000002
0.000000
0.000961
0.002112
60
0.000053
0.000003
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000046
0.000102
80
0.000002
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000002
0.000004
≥85
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
q
r
+
0.226652
0.053249
0.054267
0.054053
0.052844
0.050871
0.048344
0.045446
0.414272
1.000000Now we focus on other service time distributions. We have shown the occurrence of multiple roots in case ofE4 service time distribution with each phase mean 1/4μi so that total mean is 1/μi, a≤i≤b. The purpose of this example is to demonstrate the occurrence of multiple roots in queueing models which was often a major concern of the researchers. In this context, we point out that the multiple roots occur only for Em(m≥2) service time distribution. The occurrence of multiple roots is caused by the terms K(i)(z)=mμi/(mμi+λ-λz)m,i=a,…,b-1:(i)
The number of multiple roots depends on the values of “a” and “b.” The exact number of distinct multiple roots is (b-a).(ii)
The multiplicity of each root depends on the parameterm (m≥2), of Erlang distribution.For E4 distribution with parameters a=7, b=15, λ=80, μ=0.75, μr=(r-1)μ, and ρ=0.507936, we have encountered 8 multiple roots: 1.225000, 1.262500, 1.300000, 1.337500, 1.375000, 1.412500, 1.450000, and 1.487500 each of multiplicity 4. The joint distribution of pn,r+ and pn,r,n≥0,a≤r≤b, is displayed in Tables 3-4.Table 4
Joint distribution of queue and server content  at arbitrary epoch (pn,r) of an M/Gn(7,15)/1 queue with G∼E4.
n
p
n
,
0
p
n
,
7
p
n
,
8
p
n
,
9
p
n
,
10
p
n
,
11
p
n
,
12
p
n
,
13
p
n
,
14
p
n
,
15
p
n
q
u
e
u
e
0
0.000253
0.019330
0.004538
0.004620
0.004596
0.004487
0.004311
0.004089
0.003835
0.003563
0.053622
1
0.001016
0.019258
0.004511
0.004580
0.004540
0.004414
0.004222
0.003983
0.003715
0.006723
0.056962
2
0.002458
0.019111
0.004458
0.004502
0.004436
0.004282
0.004064
0.003802
0.003513
0.009404
0.060030
3
0.004637
0.018872
0.004373
0.004382
0.004279
0.004090
0.003840
0.003550
0.003241
0.011560
0.062824
4
0.007525
0.018529
0.004256
0.004221
0.004075
0.003846
0.003562
0.003247
0.002921
0.013182
0.065364
5
0.011027
0.018082
0.004108
0.004023
0.003830
0.003561
0.003247
0.002913
0.002576
0.014290
0.067657
6
0.015016
0.017535
0.003932
0.003795
0.003555
0.003251
0.002913
0.002567
0.002229
0.014930
0.069723
7
0.016896
0.003732
0.003543
0.003262
0.002929
0.002575
0.002226
0.001896
0.015162
0.052221
8
0.016180
0.003515
0.003277
0.002961
0.002606
0.002246
0.001902
0.001588
0.015054
0.049329
9
0.015400
0.003286
0.003005
0.002660
0.002294
0.001936
0.001605
0.001312
0.014674
0.046172
10
0.014572
0.003049
0.002732
0.002368
0.001998
0.001650
0.001338
0.001070
0.014088
0.042865
20
0.006445
0.001064
0.000748
0.000508
0.000336
0.000218
0.000139
0.000088
0.005824
0.015370
30
0.002052
0.000258
0.000138
0.000072
0.000036
0.000018
0.000009
0.000004
0.001642
0.004229
40
0.000537
0.000051
0.000020
0.000008
0.000003
0.000001
0.000000
0.000000
0.000397
0.001017
60
0.000026
0.000001
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000018
0.000045
75
0.000002
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000001
0.000003
≥85
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
Total(prser)
0.041932(p0ser)
0.344036(p7ser)
0.069281(p8ser)
0.061779(p9ser)
0.054699(p10ser)
0.048127(p11ser)
0.042119(p12ser)
0.036691(p13ser)
0.031838(p14ser)
0.269497(p15ser)
1.000000
L
=
19.946026,     Lq=9.880520,  and  Ls=10.065505
P
i
d
l
e
=
0.041932,     W=0.249325,   and  Wq=0.123506In Tables5-6, similar results are provided for deterministic (D) service time distribution. As the L.-S.T. of deterministic (D) distribution is a transcendental function, we use Padé approximation to approximate its L.-S.T as a rational function of the form P(θ)/Q(θ). For more details, see Singh et al. [9], where they have discussed choice for parameters for Padé approximation.Table 5
Joint distribution of queue and server content at departure epoch (pn,r+)  of an M/Gn(5,11)/1 queue with G∼D, λ=9, μ=0.25, μr=rμ, and ρ=0.297521.
n
p
n
,
5
+
p
n
,
6
+
p
n
,
7
+
p
n
,
8
+
p
n
,
9
+
p
n
,
10
+
p
n
,
11
+
p
n
+
0
0.000349
0.000342
0.000703
0.001060
0.001270
0.001270
0.001092
0.006084
1
0.002515
0.002054
0.003613
0.004769
0.005082
0.004571
0.004202
0.026806
2
0.009056
0.006162
0.009291
0.010729
0.010163
0.008228
0.008241
0.061869
3
0.021734
0.012325
0.015928
0.016094
0.013551
0.009874
0.011017
0.100523
4
0.039120
0.018487
0.020479
0.018106
0.013551
0.008887
0.011330
0.129959
5
0.056333
0.022184
0.021064
0.016295
0.010841
0.006398
0.009592
0.142707
6
0.067600
0.022184
0.018055
0.012221
0.007227
0.003839
0.006987
0.138113
7
0.069532
0.019015
0.013265
0.007857
0.004130
0.001974
0.004516
0.120289
8
0.062578
0.014261
0.008527
0.004419
0.002065
0.000888
0.002650
0.095388
9
0.050063
0.009507
0.004873
0.002210
0.000918
0.000355
0.001436
0.069362
10
0.036045
0.005704
0.002506
0.000994
0.000367
0.000128
0.000728
0.046472
12
0.014156
0.001556
0.000502
0.000152
0.000044
0.000013
0.000158
0.016581
14
0.004032
0.000308
0.000073
0.000017
0.000004
0.000000
0.000029
0.004463
16
0.000871
0.000046
0.000008
0.000001
0.000000
0.000000
0.000004
0.000930
18
0.000147
0.000005
0.000000
0.000000
0.000000
0.000000
0.000000
0.000152
20
0.000020
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000020
≥23
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
q
r
+
0.467958
0.138114
0.120289
0.095390
0.069362
0.046473
0.062414
1.000000Table 6
Joint distribution of queue and server content  at arbitrary epoch (pn,r) of an M/Gn(5,11)/1 queue with G∼D.
n
p
n
,
0
p
n
,
5
p
n
,
6
p
n
,
7
p
n
,
8
p
n
,
9
p
n
,
10
p
n
,
11
p
n
q
u
e
u
e
0
0.000929
0.071400
0.021036
0.018260
0.014403
0.010397
0.006902
0.004231
0.147558
1
0.005022
0.071016
0.020723
0.017708
0.013675
0.009621
0.006204
0.006122
0.150090
2
0.014470
0.069633
0.019782
0.016289
0.012037
0.008069
0.004948
0.006222
0.151450
3
0.029819
0.066314
0.017900
0.013857
0.009580
0.006000
0.003440
0.005221
0.152130
4
0.049663
0.060341
0.015077
0.010730
0.006815
0.003931
0.002083
0.003812
0.152452
5
0.051739
0.011690
0.007514
0.004327
0.002276
0.001106
0.002489
0.081141
6
0.041417
0.008303
0.004757
0.002461
0.001172
0.000520
0.001482
0.060112
7
0.030800
0.005399
0.002731
0.001261
0.000541
0.000218
0.000816
0.041766
8
0.021245
0.003221
0.001429
0.000586
0.000226
0.000083
0.000421
0.027211
9
0.013601
0.001770
0.000685
0.000249
0.000086
0.000028
0.000205
0.016624
10
0.008097
0.000899
0.000302
0.000097
0.000030
0.000009
0.000094
0.009528
12
0.002333
0.000186
0.000047
0.000012
0.000003
0.000000
0.000018
0.002599
14
0.000520
0.000029
0.000005
0.000001
0.000000
0.000000
0.000003
0.000558
16
0.000092
0.000004
0.000000
0.000000
0.000000
0.000000
0.000000
0.000096
18
0.000013
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000013
20
0.000001
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000001
≥23
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
Total(prser)
0.099903(p0ser)
0.514462(p5ser)
0.126533(p6ser)
0.094459(p7ser)
0.065544(p8ser)
0.042364(p9ser)
0.025546(p10ser)
0.031189(p11ser)
1.000000
L
=
8.655220,   Lq=3.158331, and  Ls=5.496888
P
i
d
l
e
=
0.099903,   W=0.961691, and  Wq=0.350925After the tabular representation of the numerical results, we turn our attention for inspection on the tail probabilities (using (39)) for exponential and deterministic service time distributions. In Figure 1(a), we plot exact and tail distribution of pn,b+ in case of exponential (M) distribution with the parameters a=12, b=20, λ=80, μr=0.25r, a≤r≤b, and ρ=0.8. Figure 1(b) replicates similar results for deterministic (D) service time distribution with parameters a=4, b=8, λ=15, μr=0.25r, a≤r≤b, and ρ=0.9375. It can be seen from Figures 1(a) and 1(b) that exact and tail distributions match approximately for n≥150 and n≥20, respectively. From Figure 1 it is easily noticeable that exact distribution is more significant than tail distribution.Figure 1
Exact and tail distribution.
(a)
Exponential distribution
(b)
Deterministic distributionWe also show the influence of model parameters onLq of batch-size-dependent service policy with the one when service rate of the batches remains constant irrespective of the size of the batch. In this context, we consider two cases.Case 1.
The service rate of the batches depends on the size of the batch undergoing service and it increases linearly with the batch size; that is,μr=rμ(a≤r≤b).Case 2.
The service rate of the batches is independent of the size of the batch; that is,μr=μ(a≤r≤b).In Figure2, the mean queue length (Lq) is depicted versus the arrival rate (λ) for exponential (M) and deterministic (D) service time distributions for Cases 1 and 2. For both service time distributions, the input parameters are taken as a=14, b=22, and μ=0.25 and λ varies from 1.0 to 5.0.Figure 2
Impact ofλ on Lq.It is easily noticeable from Figure2 that a fixed λ leads to a lower value of Lq in Case 1 as compared to Case 2 for both distributions. This influence turned out to be significant in the sense that applying batch-size-dependent service is more potent in comparison to the batch-size-independent service. One can also observe from Figure 2 that as λ increases Lq also increases. But for Case 1 this increases very slowly as compared to Case 2. Further, for both the distributions (M and D), the values of Lq coincide in Case 1.


## 6. Conclusion

In this paper, an analytic expression of bivariate pgf of queue content as well as server content is derived at departure epoch of a batch using supplementary variable technique. Further, the joint distribution of queue and server content is extracted from this bivariate pgf. A relationship between departure and arbitrary epoch probabilities is generated to get the latter one. Moreover, we have discussed a set of pertinent performance measures, by which a practitioner can appraise a batch-service queue. Finally, we illustrate the applicability of analytical results through assorted numerical examples where occurrence of multiple zeroes is also investigated.



---

*Source: 102824-2015-10-04.xml*