2. THE GI^X/G/1 SYSTEM

Let W_q*(s) be the LST of the stationary waiting-time distribution of an arbitrary customer in a group at an arrival epoch. The following notation (see [11]) is used. (Since we consider the equilibrium behavior of the queue, the traffic intensity ρ = λm_g /μ < 1.)

Proposition 1 [11]:

where W_q1*(s) is the LST of the (stationary) waiting time of the customer who is the first to receive service in a group. This is equal to the LST of the waiting time in the GI/G_X /1 queue, where the service time is a sum of a random number (X) of i.i.d. r.v.'s. W_q2*(s) is the LST of an additional (stationary) waiting time for the random customer of a group,

3. THE GI/R/1 SYSTEM

Let us assume that

where P(s) is a polynomial of degree at most n and Q(s) is of degree n. We further assume that P(s) and Q(s) have no common factors, and let

respectively be the LST of the interbatch-time and service-time distributions for the GI/R/1 queue. Assumption (3.1) does not amount to any great limitations on the scope of the analysis of the GI/G/1 queue, as this class can fit almost all of the distributions that may arise in practice, as noted by several researchers; see, for example, Botta, Harris, and Marchal [2]. Further, Bladt [1] shows that there is a one-to-one correspondence between matrix-exponential distributions and distributions having rational Laplace transforms. Examples are given by Bladt [1] and Botta et al. [2] to show that even distributions that cannot be represented by phase type (PH) belong to a somewhat smaller class than the matrix-exponential. Such examples that do not belong to PH distributions can also be handled by our method. In view of this, it is worth emphasizing that the method of rational transforms discussed in this article is not only more comprehensive than the phase method, but it is also computationally more efficient, although the former may not have a direct probabilistic interpretation. We assume that the coefficient of sⁿ in Q(s) is unity and denote the same in P(s) by a_n, which satisfies the relation |a_n| ≤ 1 (see [4, Thm.1]). Although (3.2)–(3.9) are given in Chaudhry et al. [4], they are repeated here for easy readability of the article.

Denoting by W_q*(s) the LST of W_q(t), the cumulative distribution function (CDF) of the stationary waiting time, it follows from (3.3) of [4, p.112] that

where W_q⁻*(s) is the LST of W_q⁻(t) defined by

and

Using spectrum factorization (Kleinrock [7, pp.286,287,288,289,290]), we have from (3.4) of [4, p.112] that

where s_i (i = 1,2,…,n) are the roots (assumed distinct) of the c.e.,

, with Re(s_i) < 0.

Resolving (3.5) into partial fractions, we get

where

Also, the probability density function (pdf) w_q(t) and the CDF W_q(t) of the waiting time are obtained as

and

where δ(t) is the Dirac delta function.

4. THE GI^X/R/1 SYSTEM

Let us assume that

where P(s) and Q(s) are the same as in (3.1). We consider the case with batch size distribution having finite support: Pr(X = i) = g_i,i = 1,2,…,k. We now consider the functions W_q1*(s), W_q2*(s), and W_q*(s) under three separate cases: (4.1), (4.2), and (4.3), respectively.

Case 4.1: W_q1*(s)

Denoting by

the LST of the service-time distribution in the GI/G_X /1 queue, we have

where

Remarks:

1. U(s) is a polynomial of degree at most nk and V(s) is of degree nk.
2. U(s) and V(s) have no common factors.
3. The coefficient of s^nk in V(s) is unity and the same in U(s) is u_nk, where
   
   satisfies the relation |u_nk| ≤ 1. Note that |u_nk| ≤ 1 is a condition that is needed in Theorem 1 of [4].

From (3.6) and (3.7), we get

where s_i (i = 1,2,…,nk) are the roots (assumed distinct) of the c.e.,

, with Re(s_i) < 0,

They satisfy the relation

Case 4.2: W_q2*(s)

From (2.2), we obtain W_q2*(s) as

where

Remarks:

1. C(s) is a polynomial of degree less than n(k − 1) and D(s) is of degree n(k − 1).
2. Since we assume that P(s) and Q(s) have no common factors, C(s) and D(s) have no common factors.
3. Since W_q2*(s) is convergent for Re(s) ≥ 0, D(s) has no zeros in Re(s) ≥ 0. This implies that it has zeros in the open half-region Re(s) < 0, say x_i (i = 1,2,…,n), (assumed distinct) where x_i has a multiplicity of k − 1.

Resolving (4.7) into partial fractions (see [6, pp.24,25,26]), we obtain

where

They satisfy the relation

Case 4.3: W_q*(s)

Using (4.4) and (4.9), we rewrite (2.1) as

For further analysis, let us assume that

have no common zeros (see Theorem 1 of Chaudhry et al. [4]). Then, all s_i and x_j are distinct roots. Otherwise, minor modifications are needed and can be easily dealt with, as we have done in Remark (3) of Case 4.2.

Taking the inverse LST of (4.12), explicit closed-form expressions of the pdf w_q(t) and the CDF W_q(t) of the stationary waiting time of a customer are found to be

and

where

From (4.14) and (4.6), we obtain the (stationary) probability of no wait in queue as

Using (4.6), (4.11), and (4.12), we get the following expression for the first moment, E(W_q):

for the second moment, E(W_q²), we obtain

The expressions for the stationary waiting-time distribution of the GI^X/R/1 queue and its first two moments are obtained as above. The presented results have a definite value for the practical engineers and are also useful for the queuing theorists to test the accuracies of inequalities, bounds, or approximations. We now provide some numerical examples.

Numerical Examples

Although complete distributions can be obtained, we only give a few performance measures in a self-explanatory table (Table 1). Consider the GE₄^X/GE₄ /1 queue. In this case, we take

. Then, using the procedure described in this section, we carry out numerical work for several cases. From (4.15), (4.16), and (4.17), we present sample numerical results for W_q(0), E(W_q), and S.D.(W_q).

Exact Values for Wq(0), E(Wq), and S.D.(Wq) of the Queue GE4X/GE4 /1 for Various Values of ρ

5. APPROXIMATION OF THE GI^X/D/1 SYSTEM

In this section, we consider the GI^X/D/1 queue, where each customer arriving in a group requires a deterministic service time that could be greater than or equal to one (i.e., D ≥ 1). This queuing model has gained importance in recent years in view of a number of possible practical applications to telecommunications systems. It may be possible to find explicit results for the (stationary) waiting time of the GI^X/D/1 queue, but the results are likely to be very complex, as can be seen from the results of the GI/D/1 queue discussed by Chaudhry [3]. However, it is much better to use continued fractions, as they give good approximate results with much simplified algebra. Although the procedure being discussed here is more general because it covers transcendental and irrational functions, it is exemplified by considering only the exponential function. Continued fractions are quite useful in computation, as they usually provide representations for transcendental functions that are much more generally valid than the classical representation by power series (see, e.g., Parthasarathy and Balakrishnan [8] for another use of continued fractions). In this article, we make use of the continued fractions approach to approximate the exponential function, and then approximate results for the GI^X/D/1 queue.

5.1. Continued-Fractions Representation for Exponential Function

Exponential function e^z can be represented in the form of continued fractions as follows (see [9]):

which is valid for all z ∈ C.

Using (2.14) of Cooper and Thron [5, p.235], the even part of (5.1) is defined by

Let A_n (B_n) denote the nth numerator (denominator) and let f_n denote the nth approximant of (5.2) (i.e., 2nth approximant of (5.1)). Then, these are defined as

where

and

Remark: Note that f_n = A_n /B_n is a rational function of complex variable z (ratios of a polynomial of degree n − 1 to a polynomial of degree n).

5.2. Approximation by the Continued Fractions

Confining ourselves to the GI^X/D/1 queue, we have

if the service time is constant and equal to 1/μ.

Replacing z by −s/μ in (5.2) gives the representation

Denoting by P_n(s) (Q_n(s)) the nth numerator (denominator) and letting

denote the nth approximant of (5.2), we have

where

and

It may be remarked here that

is a rational function where the numerator (P_n(s)) is a polynomial of degree n − 1 and the denominator (Q_n(s)) is a polynomial of degree n; that is,

can be approximated by the R-type distribution mentioned in the previous section. As a consequence, we can approximate the GI^X/D/1 queue using the results of the GI^X/R/1 queue studied in Section 4, and, thus, we will omit the details in this section. We demonstrate the performance of our approximations in the tables.

Numerical Examples

In order to examine the performance of our approximations, some calculations for the numerical computations of W_q(0), E(W_q), and E(W_q²) were done for the M^X/D/1 and E₃^X/D/1 queues, which are special cases of GI^X/D/1.

Tables 2 and 3 contain the results for M/D/1 and E₃ /D/1, respectively, for various values of ρ. These values have been selected for illustrative purposes, but the method puts no restrictions on any reasonable value of ρ. We take the exact and approximate values from Chaudhry [3]. It may be remarked that the time taken to get the results of M/E₅₀₀ /1 and E₃ /E₅₀₀ /1 is more than that of getting the results of M/D/1 and E₃ /D/1 by continued fractions, as the number of roots required is 500 in the former case. In addition, Tables 4 and 5 give results for M^X/D/1 with g₁ = 0.25, g₂ = 0.5, and g₃ = 0.25 and E₃²/D/1, respectively. The exact values are obtained from Takagi [10, pp.46,47] and Chaudhry [3], respectively, since the waiting-time distribution of E₃²/D/1 is equivalent to that of E₃ /D₂ /1, where D₂ is convolution of D with itself.

M/D/1: Values of Wq(0), E(Wq), and E(Wq2) for Various Values of ρ

E3 /D/1: Values of Wq, E(Wq), and E(Wq2) for Various Values of ρ

MX/D/1 with g1 = 0.25, g2 = 0.5, and g3 = 0.25; Values of Wq(0), E(Wq), and E(Wq2) for Various Values of ρ

E32/D/1: Values of Wq(0), E(Wq), and E(Wq2) for Various Values of ρ

It can be seen from Tables 2, 3, 4, and 5 that as the number of steps (n) increases, the performance of approximation increases and the approximate value converges rapidly into the exact value. The steps are defined at the end of Table 5.

We hope that our approximation would be beneficial for practitioners who would like practical answers to their bulk-arrival queuing systems with deterministic service time.

We approximate

as follows: