Article Contents
Article Contents

# Explicit results for the distribution of the number of customers served during a busy period for $M^X/PH/1$ queue

• We give analytically explicit solutions for the distribution of the number of customers served during a busy period for the $M^X/PH/1$ queues when initiated with $m$ customers. When customers arrive in batches, we present the functional equation for the Laplace transform of the number of customers served during a busy period. Applying the Lagrange inversion theorem, we provide a refined result to this functional equation. From a phase-type service distribution, we obtain the distribution of the number of customers served during a busy period for various special cases such as exponential, Erlang-k, generalized Erlang, hyperexponential, Coxian, and interrupted Poisson process. The results are exact, rapid and vigorous, owing to the clarity of the expressions. Moreover, we also consider computational results for several service-time distributions using our method. Phase-type distributions can approximate any non-negative valued distribution arbitrarily close, making them a useful practical stochastic modelling tool. These distributions have eloquent properties which make them beneficial in the computation of performance models.

Mathematics Subject Classification: Primary: 60K25, 68M20; Secondary: 90B22.

 Citation:

• Figure 1.  Two Phase type distributions with two phases

Figure 2.  An exponential service phase

Figure 3.  Two exponential (Erlang-2) service phases in tandem

Figure 4.  Phase diagram for the generalized Erlang-2 distribution

Figure 5.  Two exponential phases in parallel

Figure 6.  The two phase Coxian distribution

Figure 7.  Phase diagram for the IPP distribution

Table .  Exponential distribution

 Batch size distribution $R(z)$ $P(N_m = n),\; n = m, m+1,\dots$ Geometric $\frac{\mu(1-qz)}{\lambda+\mu-z(\lambda+q\mu)}$ $\frac{m}{n}\left(\frac{\mu}{\mu+\lambda}\right)^{n}\sum\limits_{j = 0}^{n-m} {2n-m-j-1 \choose n-m-j} \left(\frac{\lambda+\mu q}{\lambda+\mu}\right)^{n-m-j} {n \choose j}(-q)^j$ Arbitrary $\frac{\mu}{\lambda+\mu-\lambda(g_1 z+g_2 z^2)}$ $\frac{m}{n}\left(\frac{\mu}{\mu+\lambda}\right)^{n}\sum\limits_{r = 0}^{\infty} {n+r-1 \choose r} {r \choose n-m-r}\left(\frac{\lambda g_1}{\lambda+\mu}\right)^{r}\left(\frac{g_2}{g_1}\right)^{n-m-r}$

Table .  Erlang distribution

 Batch size distribution $R(z)$ $P(N_m = n),\; n = m, m+1,\dots$ Geometric $\left(\frac{\mu(1-qz)}{\lambda+\mu-z(\lambda+q\mu)}\right)^2$ $\begin{array}{c} \frac{m}{n}\left(\frac{\mu}{\mu+\lambda}\right)^{nk}\sum\limits_{j = 0}^{n-m} {nk+n-m-j-1 \choose n-m-j} {nk \choose j} (-q)^j \\ \times \left(\frac{\lambda+\mu q}{\lambda+\mu}\right)^{n-m-j} \end{array}$ Arbitrary $\left(\frac{\mu}{\lambda+\mu-\lambda(g_1 z+g_2 z^2)}\right)^2$ $\begin{array}{c} \frac{m}{n}{\left( {\frac{\mu }{{\mu + \lambda }}} \right)^{nk}}\sum\limits_{r = 0}^\infty {\left( \begin{array}{c} nk + r - 1\\ r \end{array} \right)} \left( \begin{array}{c} r\\ n - m - r \end{array} \right){\left( {\frac{{\lambda {g_1}}}{{\lambda + \mu }}} \right)^r}\\ \times {\left( {\frac{{{g_2}}}{{{g_1}}}} \right)^{n - m - r}} \end{array}$

Table .  Generalized Erlang distribution

 Batch size distribution $R(z)$ $P(N_m = n),\; n = m, m+1,\dots$ Geometric $\frac{\mu_1\mu_2}{\lambda+\mu_1-z(\lambda+q\mu_1)} \\ \times \frac{(1-qz)^2}{\lambda+\mu_2-z(\lambda+q\mu_2)}$ $\begin{array}{c} \frac{m}{n}\prod\limits_{i = 1}^2 {{{\left( {\frac{{{\mu _i}}}{{{\mu _i} + \lambda }}} \right)}^n}} \sum\limits_{i = 0}^{n - m} {\left( \begin{array}{c} 2n\\ i \end{array} \right)} {( - q)^i}\sum\limits_{j = 0}^{n - m - i} {\left( \begin{array}{c} n + j - 1\\ j \end{array} \right)} \\ \times {\left( {\frac{{\lambda + q{\mu _2}}}{{\lambda + {\mu _2}}}} \right)^j}\left( \begin{array}{c} 2n - m - i - j - 1\\ n - m - i - j \end{array} \right){\left( {\frac{{\lambda + q{\mu _1}}}{{\lambda + {\mu _1}}}} \right)^{n - m - i - j}} \end{array}$ Arbitrary $\begin{array}{c} \prod\limits_{i = 1}^{2}\frac{\mu_i}{\mu_i+\lambda} \\ \times \prod\limits_{i = 1}^{4}(1-z/\omega_i)^{-1} \end{array}$ $\begin{array}{c} \frac{m}{n}\prod\limits_{i = 1}^{2}\left(\frac{\mu_i}{\mu_i+\lambda}\right)^n\sum\limits_{i = 0}^{n-m}{n+i-1 \choose i}\omega_1^{-i}\sum\limits_{j = 0}^{n-m-i}{n+j-1 \choose j} \\ \times \omega_2^{-j}\sum\limits_{k = 0}^{n-m-i-j}{n+k-1 \choose k}\omega_3^{-k} {2n-m-i-j-k-1 \choose n-m-i-j-k} \\ \times\omega_4^{i+j+k+m-n} \end{array}$

Table .  Hyperexponential distribution

 Batch size distribution $R(z)$ $P(N_m = n),\; n = m, m+1,\dots$ Geometric $\begin{array}{c} \frac{{(\lambda {D_1} + {D_2})\left[ {1 - z\frac{{\lambda {D_1} + q{D_2}}}{{\lambda {D_1} + {D_2}}}} \right]}}{{\lambda + {\mu _1} - z(\lambda + q{\mu _1})}}\\ \times \frac{{(1 - qz)}}{{\lambda + {\mu _2} - z(\lambda + q{\mu _2})}} \end{array}$ $\begin{array}{c} \frac{m}{n}\left(\frac{\lambda D_1+D_2}{\prod\limits_{i = 1}^{2}(\lambda+\mu_i)}\right)^n \sum\limits_{i = 0}^{n-m} {n \choose i}\left(\frac{\lambda D_1+q D_2}{\lambda D_1+D_2}\right)^i \sum\limits_{j = 0}^{n-m-i} {n \choose j} \\ \times (-q)^j \sum\limits_{k = 0}^{n-m-i-j}{n+k-1 \choose k}\left(\frac{\lambda+q \mu_1 }{\lambda+\mu_1}\right)^{k} \\ \times {2n-m-i-j-k-1 \choose n-m-i-j-k} \left(\frac{\lambda+q \mu_2 }{\lambda+\mu_2}\right)^{n-m-i-j-k} \end{array}$ Arbitrary $\frac{(\lambda D_1+D_2)\prod\limits_{i = 1}^{2}(1-z/\xi_i)}{\prod\limits_{i = 1}^{2}(\lambda+\mu_i) \prod\limits_{i = 1}^{4}(1-z/\omega_i)}$ $\begin{array}{c} \frac{m}{n}\left(\frac{\lambda D_1+D_2}{\prod\limits_{i = 1}^{2}(\lambda+\mu_i)}\right)^n \sum\limits_{i = 0}^{n-m}{n \choose i}(-\xi_1)^{-i}\sum\limits_{j = 0}^{n-m-i}{n \choose j}(-\xi_2)^{-j} \\ \times \sum\limits_{k_1 = 0}^{n-m-i-j}{n+k_1-1 \choose k_1} \omega_1^{-k_1} \sum\limits_{k_2 = 0}^{n-m-i-j-k_1} {n+k_2-1 \choose k_2} \\ \times \omega_2^{-k_2}\sum\limits_{k_3 = 0}^{n-m-i-j-k_1-k_2} {n+k_3-1 \choose k_3}\omega_3^{-k_3} \\ \times \ {2n-m-i-j-k_1-k_2-k_3-1 \choose n-m-i-j-k_1-k_2-k_3} \omega_4^{i+j+k_1+k_2+k_3+m-n} \end{array}$

Table .  Cox-$C_2$ distribution

 Batch size distribution $R(z)$ $P(N_m = n),\; n = m, m+1,\dots$ Geometric $\begin{array}{c} \frac{{(\lambda {D_1} + {D_2})\left[ {1 - z\frac{{\lambda {D_1} + q{D_2}}}{{\lambda {D_1} + {D_2}}}} \right]}}{{\lambda + {\mu _1} - z(\lambda + q{\mu _1})}}\\ \times \frac{{1 - qz}}{{\lambda + {\mu _2} - z(\lambda + q{\mu _2})}} \end{array}$ $\begin{array}{c} \frac{m}{n}\left(\frac{\lambda D_1+D_2}{\prod\limits_{i = 1}^{2}(\mu_i+\lambda)}\right)^{n} \sum\limits_{i = 0}^{n-m}{n \choose i}(-1)^i \left(\frac{\lambda(1-\beta)+q \mu_2}{\lambda(1-\beta)+\mu_2}\right)^{i} \\ \times \sum\limits_{j = 0}^{n-m-i} {n \choose j}(-q)^j \sum\limits_{k = 0}^{n-m-i-j}{n+k-1 \choose k}\left(\frac{\lambda+q \mu_1 }{\lambda+\mu_1}\right)^k \\ \times {2n-m-i-j-k-1 \choose n-m-i-j-k}\left(\frac{\lambda+q \mu_2 }{\lambda+\mu_2}\right)^{n-m-i-j-k} \end{array}$ Arbitrary $\frac{(\lambda D_1+D_2)\prod\limits_{i = 1}^{2}(1-z/\xi_i)}{\prod\limits_{i = 1}^{2}(\lambda+\mu_i) \prod\limits_{i = 1}^{4}(1-z/\omega_i)}$ $\begin{array}{c} \frac{1}{n}\left(\frac{\lambda D_1+D_2}{\prod\limits_{i = 1}^{2}(\lambda+\mu_i) }\right)^n \sum\limits_{i = 0}^{n-1}{n \choose i}(-\xi_1)^{-i}\sum\limits_{j = 0}^{n-1-j}{n \choose j}(-\xi_2)^{-j} \\ \times\sum\limits_{k = 0}^{n-1-i-j}{n+k-1 \choose k} \omega_1^{-k} \sum\limits_{l = 0}^{n-1-i-j-k} {n+l-1 \choose l}\omega_2^{-l} \\ \times \sum\limits_{m = 0}^{n-1-i-j-k-l} {n+m-1 \choose m}\omega_3^{-m} \\ {2n-i-j-k-l-m-2 \choose n-i-j-k-l-m-1} \omega_4^{i+j+k+l+m+1-n} \end{array}$

Table .  IPP distribution

 Batch size distribution $R(z)$ $P(N_m = n),\; n = m, m+1,\dots$ Geometric $\begin{array}{c} \frac{{(\lambda {D_1} + {D_2})\left[ {1 - z\frac{{\lambda {D_1} + q{D_2}}}{{\lambda {D_1} + {D_2}}}} \right]}}{{\lambda + {\mu _1} - z(\lambda + q{\mu _1})}}\\ \times \frac{{1 - qz}}{{\lambda + {\mu _2} - z(\lambda + q{\mu _2})}} \end{array}$ $\begin{array}{c} \frac{m}{n}\left(\frac{\mu(\lambda+r_2)}{u_3}\right)^n \sum\limits_{i = 0}^{n-m}{n+i-1 \choose i}\psi_1^{-i} \sum\limits_{j = 0}^{n-m-i} {n \choose j} \\ \times \left(- \frac{\lambda+q r_2 }{\lambda+r_2}\right)^j \sum\limits_{k = 0}^{n-m-i-j}{n \choose k}(-q)^{k} \\ \times {2n-m-i-j-k-1 \choose n-m-i-j-k}\psi_2^{i+j+k+m-n} \end{array}$ Arbitrary $\frac{\lambda D_1+D_2-\lambda D_1(g_1 z+g_2 z^2)}{(\lambda^2 g_2^2 \prod\limits_{i = 1}^{4} \omega_i)\prod\limits_{i = 1}^{4}(1-z/\omega_i)}$ $\begin{array}{c} \frac{m}{n}\left(\frac{\mu(\lambda+r_2)}{u_3}\right)^n \sum\limits_{i = 0}^{n-m}{n \choose i}(-\xi_1)^{-i}\sum\limits_{j = 0}^{n-m-i}{n \choose j}(-\xi_2)^{-j} \\ \times \sum\limits_{k_1 = 0}^{n-m-i-j}{n+k_1-1 \choose k_1}\omega_1^{-k_1}\sum\limits_{k_2 = 0}^{n-m-i-j-k_1} {n+k_2-1 \choose k_2} \\ \times \omega_2^{-k_2} \sum\limits_{k_3 = 0}^{n-m-i-j-k_1-k_2} {n+k_3-1 \choose k_3}\omega_3^{-k_3} \\ \times {2n-m-i-j-k_1-k_2-k_3-1 \choose n-m-i-j-k_1-k_2-k_3} \omega_4^{i+j+k_1+l+k_2+k_3+m-n} \end{array}$

Table 1.  PH service-time distributions

 $\mu_1=3$, $\mu_2=1$, $r_{10}=1/3$, $r_{12}=2/3$, $r_{20}=1$, $r_{21}=0$ Geometric batch size $p=0.6$, $q=0.4$ Arbitrary batch size $g_1=0.4$, $g_2=0.6$ $n$ $\rho=0.25$ $\rho=0.5$ $\rho=0.75$ $\rho=0.25$ $\rho=0.5$ $\rho=0.75$ 1 0.869565 0.769231 0.689655 0.864865 0.761905 0.680851 2 0.059176 0.08193 0.088565 0.040432 0.055286 0.059178 3 0.028637 0.042662 0.047178 0.056233 0.071207 0.070724 4 0.015533 0.025829 0.029730 0.012702 0.024379 0.028500 5 0.009138 0.017213 0.020736 0.012009 0.023001 0.026226 6 0.005694 0.012222 0.015438 0.004622 0.012738 0.016531 7 0.003698 0.009070 0.012021 0.003650 0.010773 0.014187 8 0.002478 0.006951 0.009672 0.001825 0.007351 0.010714 9 0.001700 0.005460 0.007977 0.001325 0.006028 0.009135 10 0.001189 0.004373 0.006709 0.000762 0.004546 0.007492 50 0.000000 0.000033 0.000367 0.000000 0.000016 0.000367 100 0.000000 0.000001 0.000072 0.000000 0.000000 0.000062 150 0.000000 0.000000 0.000022 0.000000 0.000000 0.000016 200 0.000000 0.000000 0.000008 0.000000 0.000000 0.000005 $\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $E(N)$ 1.3333 2.00 4.00 1.3333 2.00 4.00 $V(N)$ 1.5309 11.33 148.00 1.1852 9.00 120.00

Table 2.  Exponential (Exp), Erlang (Er), Generalized-Erlang (GEr) service-time distributions

 Geometric batch size $p=0.8$, $q=0.2$, $m=3$, $\rho=0.65$ Arbitrary batch size $g_1=0.7$, $g_2=0.3$, $m=3$, $\rho=0.65$ $n$ Exp Er GEr Exp Er GEr 3 0.284754 0.249906 0.251187 0.296296 0.262144 0.263406 4 0.153814 0.155912 0.155949 0.138271 0.140929 0.140925 5 0.103324 0.108806 0.108638 0.104033 0.108104 0.107992 6 0.074714 0.080158 0.079956 0.074246 0.079344 0.079161 7 0.056661 0.061381 0.061192 0.057051 0.061597 0.061419 8 0.04445 0.048385 0.048220 0.044842 0.048768 0.048605 9 0.035768 0.039006 0.038866 0.036193 0.039482 0.039341 10 0.029358 0.032012 0.031895 0.029750 0.032485 0.032365 50 0.000625 0.000544 0.000547 0.000618 0.000532 0.000536 100 0.000038 0.000024 0.000024 0.000036 0.000022 0.000022 120 0.000014 0.000008 0.000008 0.000013 0.000007 0.000007 150 0.000004 0.000002 0.000002 0.000003 0.000001 0.000001 $\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $E(N)$ 8.57143 8.57143 8.57143 8.57143 8.57143 8.57143 $V(N)$ 97.7843 83.0030 83.5942 96.0350 81.2536 81.8449

Table 3.  Hyperexponential (H), Coxian (Cox), IPP service-time distributions

 Geometric batch size$p=0.8$, $q=0.2$, $\rho=0.48$ Arbitrary batch size$g_1=0.7$, $g_2=0.3$, $\rho=0.65$ $n$ H Cox IPP H Cox IPP 1 0.727986 0.715778 0.761631 0.673993 0.662037 0.720000 2 0.112936 0.119996 0.092479 0.101235 0.105492 0.082253 3 0.052525 0.055582 0.044531 0.060451 0.062843 0.050677 4 0.030003 0.031571 0.026147 0.034555 0.036224 0.028685 5 0.019157 0.020011 0.017118 0.023752 0.024893 0.020004 6 0.013102 0.013572 0.011986 0.017131 0.017951 0.014566 7 0.009387 0.009637 0.008783 0.013022 0.013625 0.011193 8 0.006955 0.007074 0.006651 0.010219 0.010672 0.008873 9 0.005285 0.005324 0.005164 0.008230 0.008575 0.007217 10 0.004097 0.004087 0.004088 0.006760 0.007025 0.005985 50 0.000009 0.000006 0.000020 0.000151 0.000137 0.000190 100 0.000000 0.000000 0.000000 0.000009 0.000007 0.000019 $\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $E(N)$ 1.92308 1.92308 1.92308 2.85714 2.85714 2.85714 $V(N)$ 7.06645 6.4406 8.94401 33.85932 31.03417 45.15063
•  [1] J. Abate and W. Whitt, The fourier-series method for inverting transforms of probability distributions, Queueing Systems, 10 (1992), 5-87.  doi: 10.1007/BF01158520. [2] J. Abate and W. Whitt, Numerical inversion of probability generating functions, Operations Research Letters, 12 (1992), 245-251.  doi: 10.1016/0167-6377(92)90050-D. [3] J. Abate and W. Whitt, Solving probability transform functional equations for numerical inversion, Operations Research Letters, 12 (1992), 275-281.  doi: 10.1016/0167-6377(92)90085-H. [4] S. Asmussen and H. Albrecher, Ruin Probabilities, vol. 14, Advanced Series on Statistical Science & Applied Probability, Hackensack, NJ, 2010. doi: 10.1142/9789814282536. [5] E. Borel, Sur l'emploi du théoreme de Bernoulli pour faciliter le calcul d'une infinité de coefficients. Application au probleme de l'attentea un guichet, CR Acad. Sci. Paris, 214 (1942), 452-456. [6] L. Breuer and D. Baum, An Introduction to Queueing Theory: And Matrix-Analytic Methods, Springer Science & Business Media, 2005. doi: 10.1007/1-4020-3631-0. [7] M. L. Chaudhry and V. Goswami, Analytically explicit results for the distribution of the number of customers served during a busy period for special cases of the $M/G/1$ queue, Journal of Probability and Statistics, 2019 (2019), Art. ID 7398658, 15 pp. doi: 10.1155/2019/7398658. [8] [9] P. C. Consul and F. Famoye, Lagrangian Probability Distributions, Springer, 2006. [10] P. C. Consul and L. R. Shenton, Use of lagrange expansion for generating discrete generalized probability distributions, SIAM Journal on Applied Mathematics, 23 (1972), 239-248.  doi: 10.1137/0123026. [11] D. R. Cox, Some statistical methods connected with series of events, Journal of the Royal Statistical Society: Series B (Methodological), 17 (1955), 129-157.  doi: 10.1111/j.2517-6161.1955.tb00188.x. [12] A. K. Erlang, Solution of some problems in the theory of probabilities of significance in automatic telephone exchanges, Post Office Electrical Engineer's Journal, 10 (1917), 189-197. [13] G. Falin, Functioning under nonsteady conditions of a single-channel system with group arrival of requests and repeated calls, Ukrainian Mathematical Journal, 33 (1981), 429-432.  doi: 10.1007/BF01085753. [14] W. Fischer and K. Meier-Hellstern, The Markov-modulated Poisson process (MMPP) cookbook, Performance Evaluation, 18 (1993), 149-171.  doi: 10.1016/0166-5316(93)90035-S. [15] F. A. Haight, A distribution analogous to the borel-tanner, Biometrika, 48 (1961), 167-173.  doi: 10.1093/biomet/48.1-2.167. [16] D. P. Heyman, An approximation for the busy period of the ${M/G/1}$ queue using a diffusion model, Journal of Applied Probability, 11 (1974), 159-169.  doi: 10.2307/3212592. [17] D. G. Kendall, Some problems in the theory of dams, Journal of the Royal Statistical Society. Series B (Methodological), 19 (1957), 207-233.  doi: 10.1111/j.2517-6161.1957.tb00257.x. [18] J. Kim, Busy period distribution of a batch arrival retrial queue, Communications of the Korean Mathematical Society, 32 (2017), 425-433.  doi: 10.4134/CKMS.c160106. [19] L. Kleinrock, Queueing Systems, vol. 1, Wiley, New York, 1975. [20] G. Latouche and V. Ramaswami, Introduction to Matrix Analytic Methods in Stochastic Modeling, SIAM, 1999. doi: 10.1137/1.9780898719734. [21] J. Medhi,  Stochastic Models in Queueing Theory, Academic Press, Amsterdam, 2003. [22] M. F. Neuts, Computational uses of the method of phases in the theory of queues, Computers & Mathematics with Applications, 1 (1975), 151-166.  doi: 10.1016/0898-1221(75)90015-2. [23] M. F. Neuts, Matrix-geometric solutions in stochastic models: An algorithmic approach, Bull. Amer. Math. Soc, 8 (1983), 97-99.  doi: 10.1090/S0273-0979-1983-15095-4. [24] N. U. Prabhu, Some results for the queue with Poisson arrivals, Journal of the Royal Statistical Society: Series B (Methodological), 22 (1960), 104-107.  doi: 10.1111/j.2517-6161.1960.tb00357.x. [25] N. U. Prabhu, Queues and Inventories, John Wiley & Sons, 1965. [26] J. F. Shortle, J. M. Thompson, D. Gross and C. M. Harris, Fundamentals of Queueing Theory, Fifth Edition, John Wiley & Sons, 2018. doi: 10.1002/9781119453765. [27] W. J. Stewart, Probability, Markov Chains, Queues, and Simulation: The Mathematical Basis of Performance Modeling, Princeton University Press, 2009. [28] L. Takács,  Combinatorial Methods in the Theory of Stochastic Processes, Wiley, New York, 1967. [29] J. C. Tanner, A problem of interference between two queues, Biometrika, 40 (1953), 58-69.  doi: 10.1093/biomet/40.1-2.58.

Figures(7)

Tables(9)