An Algorithm for Estimating the Expected Number of Customers for a Class of Markovian Queueing Systems

Hung-Yuan Tu, Hillel Kumin

School of Industrial and Systems Engineering, University of Oklahoma, Norman, USA.

DOI: 10.4236/ajor.2020.104009                

Abstract

An algorithm is presented for estimating the expected number of customers for a class of Markovian queueing systems. The class is characterized by those systems whose transition matrix for the underlying customer arrival and departure process is finite, irreducible, and aperiodic. The algorithm does not depend on a closed-form solution for the limiting behavior of the queue. The expected number of customers is frequently used as a measure of effectiveness to describe the behavior of the system or to optimize its design or control. To calculate such a quantity one must usually obtain a closed-form expression for the steady-state probabilities. Unfortunately, of the myriad of Markovian queueing systems, only a few have known closed-form expressions for their steady-state probabilities. The most well-known, using Kendall’s notation, are the M/M/1 and the M/M/c system. The algorithm described below estimates the expected number in the system under steady-state without a need for closed form steady-state probabilities. All that is needed is the transition matrix for the underlying Markov chain.

Keywords

Queueing Systems, Markov Chain, Expected Number in System

1. Preliminaries

Consider a Markovian queueing system in which the customer arrival and departure process is described by a finite, irreducible, and aperiodic Markov Chain $\left\{X_n:n=0,1,\cdots \right\}$ whose $N\times N$ transition matrix is given by $A=\left(a_{ij}\right)$, where $a_{ij}=pr\left\{X_n=j|X_{n+1}=i\right\}$.

It is well known that for a finite, irreducible, aperiodic Markov chain, there exists a unique stationary probability vector $V=\left(v_0,\cdots ,v_0\right)$ such that $VA=V$ [1].

Let L = Expected number of customers in the steady state system. The expected number of customers is frequently used as a measure of effectiveness to describe the behavior of the system or to optimize its design or control [2] [3] [4], and [5]. Now define the following

$F={\left(0,1,\cdots ,N-1\right)}^t$

$A^{Z}F={\left(w_0^{\left(z\right)},\cdots ,w_{N-1}^{\left(z\right)}\right)}^t=W^{(\; z\; )}$

${\underset{\_}{w}}^{\left(z\right)}=\underset{i}{\min }\left\{w_i^{\left(z\right)}:i=0,1,\cdots ,N-1\right\}$

${\bar{w}}^{\left(z\right)}=\underset{i}{\max }\left\{w_i^{\left(z\right)}:i=0,1,\cdots ,N-1\right\}$

${\hat{L}}^{\left(z\right)}=\frac{\left({\bar{w}}^{\left(z\right)}+{\underset{\_}{w}}^{\left(z\right)}\right)}{2}$

Theorem 1 For any positive integer z,

1)

$\left|L-{\hat{L}}^{\left(z\right)}\right|\le \frac{\left({\bar{w}}^{\left(z\right)}+{\underset{\_}{w}}^{\left(z\right)}\right)}{2}$

2)

${\lim }_{z\to \infty }{\hat{L}}^{\left(z\right)}=L$

Proof.

1)

$L=VF=V{A}^{Z}F={\displaystyle \sum v_i{w}_i^{(\; z\; )}}$

since $w_i^{\left(z\right)}\le {\bar{w}}^{(\; z\; )}$

then,

${\displaystyle \sum v_i{w}_i^{\left(z\right)}}\le {\displaystyle \sum v_i{\bar{w}}^{\left(z\right)}}={\bar{w}}^{\left(z\right)}{\displaystyle \sum v_i}={\bar{w}}^{(\; z\; )}$

Similarly, since

$w_i^{\left(z\right)}\ge {\bar{w}}^{(\; z\; )}$

we have,

${\displaystyle \sum v_i{w}_i^{\left(z\right)}}\ge {\displaystyle \sum v_i{\underset{\_}{w}}^{\left(z\right)}}={\underset{\_}{w}}^{\left(z\right)}{\displaystyle \sum v_i}={\underset{\_}{w}}^{(\; z\; )}$

thus

$L-{\hat{L}}^{\left(z\right)}\le {\bar{w}}^{\left(z\right)}-\frac{\left({\bar{w}}^{\left(z\right)}+{\underset{\_}{w}}^{\left(z\right)}\right)}{2}=\frac{\left({\bar{w}}^{\left(z\right)}-{\underset{\_}{w}}^{\left(z\right)}\right)}{2}$

and

$L-{\hat{L}}^{\left(z\right)}\ge {\bar{w}}^{\left(z\right)}-\frac{\left({\bar{w}}^{\left(z\right)}+{\underset{\_}{w}}^{\left(z\right)}\right)}{2}=\frac{-\left({\bar{w}}^{\left(z\right)}-{\underset{\_}{w}}^{\left(z\right)}\right)}{2}$

It follows that

$\left|L-{\hat{L}}^{\left(z\right)}\right|\le \frac{\left({\bar{w}}^{\left(z\right)}+{\underset{\_}{w}}^{\left(z\right)}\right)}{2}$

2) Let $A^z={\left(p_0^{\left(z\right)},\cdots ,p_{N-1}^{\left(z\right)}\right)}^t$, where $p_i^{\left(z\right)}$ is the $\left(i+1\right)\text{th}$ row of $A^z$. Since we are concerned with finite, irreducible, aperiodic Markov chains, we have

${\lim }_{z\to \infty }{p}_i^{\left(z\right)}=V$

For all i. It follows that

${\lim }_{n\to \infty }{w}_i^{\left(z\right)}={\lim }_{z\to \infty }{p}_i^{\left(z\right)}F=VF=L$

For all i. Let $\left(s_n\right)$ be the sequence formed by combining the N sequences $\left(w_0^{\left(z\right)}\right),\cdots ,\left(w_{N-1}^{\left(z\right)}\right)$ according to the ascendant order of z. Clearly,

$\underset{z\to \infty }{\lim }{s}_n=L$

Since $\left({\bar{w}}^{\left(z\right)}\right)$ and $\left({\underset{\_}{w}}^{\left(z\right)}\right)$ are both subsequence of $\left(s_n\right)$, it is clear that

$\underset{z\to \infty }{\lim }{\bar{w}}^{\left(z\right)}=\underset{z\to \infty }{\lim }{\underset{\_}{w}}^{\left(z\right)}=L$

It therefore follows that

$\underset{z\to \infty }{\lim }{\hat{L}}^{\left(z\right)}=\underset{z\to \infty }{\lim }\frac{\left({\bar{w}}^{\left(z\right)}+{\underset{\_}{w}}^{\left(z\right)}\right)}{2}=\frac{\left(\underset{z\to \infty }{\lim }{\bar{w}}^{\left(z\right)}+\underset{z\to \infty }{\lim }{\underset{\_}{w}}^{\left(z\right)}\right)}{2}=\frac{L+L}{2}=L.$

2. Algorithm for Estimating the Expected Number of Customers

The relationship between $\hat{L}$ and L as stated in Theorem 1 can be used to develop an iterative algorithm for estimating the expected number of customers from the system’s transition matrix.

Definition 1

The absolute error of an estimation is the absolute value of the difference between the estimation and the true value. When the true value is unknown, the largest absolute error that may occur is called the maximal absolute error.

Definition 2

The relative error of an estimation is the ratio of the absolute error of the estimation to the true value. When the true value is unknown, the largest relative error that may occur is called the maximal relative error.

The algorithm can now be stated as follows:

Step 1. Determine the allowable maximal absolute error a.

Step 2. Set $z=0$ and $W^{\left(0\right)}={\left(0,\cdots ,N-l\right)}^t$.

Step 3. Compute $W^{\left(z+1\right)}=A{W}^{\left(z\right)}$.

Step 4. If $\frac{\left({\bar{w}}^{\left(z+1\right)}-{\underset{\_}{w}}^{\left(z+1\right)}\right)}{2}\le a$, go to step 5; otherwise, increase z by 1 then go to step 3.

Step 5. The desired accuracy has been reached. Let $L={\hat{L}}^{\left(z+1\right)}=\frac{\left({\bar{w}}^{\left(z+1\right)}+{\underset{\_}{w}}^{\left(z+1\right)}\right)}{2}$. Terminate

Theorem 2 Let ${\hat{L}}^{\left(n\right)}$ be the estimation of the expected number of customers obtained from the Algorithm above. Using an allowable maximal absolute error of a, we then have that

1) The maximal absolute error of ${\hat{L}}^{\left(n\right)}$ is a,

2) The maximal relative of ${\hat{L}}^{\left(n\right)}$ is $\frac{a}{\left({\hat{L}}^{\left(n\right)}-a\right)}$

Proof. 1) Step 4 of the algorithm implies $\frac{\left({\bar{w}}^{\left(n\right)}-{\underset{\_}{w}}^{\left(n\right)}\right)}{2}\le a$. Thus, by Theorem 1, $\left|L-{\hat{L}}^{\left(n\right)}\right|\le \frac{\left({\bar{w}}^{\left(n\right)}-{\underset{\_}{w}}^{\left(n\right)}\right)}{2}\le a$. Hence, the maximal absolute error of $L^{\left(n\right)}$ is a.

2) The maximal relative error occurs when $L={\hat{L}}^{\left(n\right)}-a$. Thus, the maximal relative error $=\frac{\left|{\hat{L}}^{\left(n\right)}-L\right|}{L}=\frac{\left|{\hat{L}}^{\left(n\right)}-\left({\hat{L}}^{\left(n\right)}-a\right)\right|}{\left({\hat{L}}^{\left(n\right)}-a\right)}=\frac{a}{\left({\hat{L}}^{\left(n\right)}-a\right)}$

The allowable error associated with the algorithm above is specified in terms of the maximal absolute error, and is thus independent of the magnitude of the expected number of customers. If one needs to associate the error of the estimation with the magnitude of the expected number of customers, then the algorithm may be modified as follows:

Step 1. Determine the allowable maximal relative error r.

Step 2. Set $z=0$ and $W^{\left(0\right)}={\left(0,\cdots ,N-l\right)}^t$

Step 3. Compute $W^{\left(z+1\right)}=A{W}^{(\; z\; )}$

Step 4. If $\frac{\left({\bar{w}}^{\left(z+1\right)}-{\underset{\_}{w}}^{\left(z+1\right)}\right)}{2}\le \frac{r{\hat{L}}^{\left(z+1\right)}}{\left(1+r\right)}$, go to step 5; otherwise, increase z by 1 then go to step 3.

Step 5. The desired accuracy has been reached. Let $L={\hat{L}}^{\left(z+1\right)}=\frac{\left({\bar{w}}^{\left(z+1\right)}+{\underset{\_}{w}}^{\left(z+1\right)}\right)}{2}$. Terminate.

Theorem 3 let ${\hat{L}}^{\left(n\right)}$ be the estimation of the expected number of customers obtained from the modified algorithm above, using an allowable maximal relative error of r, then

1) The maximal absolute error of the ${\hat{L}}^{\left(n\right)}$ is $\frac{r{\hat{L}}^{\left(n\right)}}{\left(1+r\right)}$

2) The maximal relative error of ${\hat{L}}^{\left(n\right)}$ is r

Proof. 1) Step 4 of the modified algorithm 2 implies $\frac{\left({\bar{w}}^{\left(n\right)}-{\underset{\_}{w}}^{\left(n\right)}\right)}{2}\le \frac{r{\hat{L}}^{\left(n\right)}}{\left(1+r\right)}$.

Thus, by Theorem 1, $\left|L-{\hat{L}}^{\left(n\right)}\right|\le \frac{\left({\bar{w}}^{\left(n\right)}-{\underset{\_}{w}}^{\left(n\right)}\right)}{2}\le \frac{r{\hat{L}}^{\left(n\right)}}{\left(1+r\right)}$. Hence the maximal absolute error of ${\hat{L}}^{\left(n\right)}$ is $\frac{r{\hat{L}}^{\left(n\right)}}{\left(1+r\right)}$.

2) The maximal relative error occurs when $L={\hat{L}}^{\left(n\right)}-\frac{r{\hat{L}}^{\left(n\right)}}{\left(1+r\right)}$. Thus the maximal relative error $=\frac{\left|{\hat{L}}^{\left(n\right)}-L\right|}{L}=\frac{\left|{\hat{L}}^{\left(n\right)}-\left({\hat{L}}^{\left(n\right)}-\frac{r{\hat{L}}^{\left(n\right)}}{\left(1+r\right)}\right)\right|}{\left({\hat{L}}^{\left(n\right)}-\frac{r{\hat{L}}^{(n)}}{\left(1+r\right)}\right)}=r$

Thus, the initial algorithm will have a maximal absolute error of a, and a maximal relative error of $\frac{a}{\left({\hat{L}}^{\left(n\right)}-a\right)}$. The modified algorithm will have a maximal absolute error of $\frac{r{\hat{L}}^{\left(n\right)}}{\left(1+r\right)}$ and a maximal relative error of r.

3. Numerical Example (Table 1)

Consider the M/M/c/c queueing system with finite waiting space. Assume that customers arrive according to a Poisson process with rate λ, and that service times are exponential with mean 1/µ. Although the process that describe the number of customers in the system at time is a process that take place in continues time, several relevant Markov chains may be defined for this system in discrete time. For example, consider the Markov chain whose transition is given by

$A=a_{ij}=\left[\begin{array}{ccccccccc}1-\lambda & \lambda & & & & & & & \\ \mu & 1-\lambda -\mu & \lambda & & & & & & \\ & 2\mu & 1-\lambda -2\mu & \lambda & & & & & \\ & & & & & & & & \\ & & & & \ddots & & & & \\ & & & & & & & & \\ & & & & & & & & \\ & & & & & & \ddots & & \\ & & & & & & & & \\ & & & & & & \left(c-1\right)\mu & 1-\lambda -\left(c-1\right)\mu & \lambda \\ & & & & & & & c\mu & 1-c\mu \end{array}\right]$

where λ and μ have been scaled such that A is a legitimate transition matrix, a is set at 0.01, and L is computed using the following formulas for the M/M/c/c (Erlang B) system [6].

Let

$B\left(c,r\right)=p_c=\frac{\frac{r^c}{c!}}{{\displaystyle {\sum }_{i=0}^c\frac{r^i}{i!}}}$

where $r=\frac{\lambda }{\mu }$ and let

$C\left(c,r\right)=\frac{cB\left(c,r\right)}{c-r+rB\left(c,r\right)}$

then $L_q=\frac{r}{c-r}C\left(c,r\right)$ and $L=L_q+r\left(1-p_c\right)$ where $L_q$ is the expected number in the queue.

Table 1. M/M/c/c system.

These computations were made on a 64-bit Intel^Ò Core^TM m3-6Y30 CPU @ 0.90 GHZ laptop computer.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Cinlar, E. (1975) Introduction to Stochastic Processes. Prentice-Hall, New Jersey.
[2]	Brigham, G. (1955) On a Congestion Problem in an Aircraft Factory. Operations Research, 3, 412-428. https://doi.org/10.1287/opre.3.4.412
[3]	Kumin, H. (1973) On Characterizing the Minimum of a Function of Two Variables, One of Which Is Discrete. Management Science, 20, 126-129. https://doi.org/10.1287/mnsc.20.1.126
[4]	Smith, J.M. (2004) Optimal Design and Performance Modelling of M/G/1/K Queueing Systems. Mathematical and Computer Modelling, 39, 1049-1081. https://doi.org/10.1016/S0895-7177(04)90534-1
[5]	Stidham, S. (2009) Optimal Design of Queueing Systems. CRC Press, New York. https://doi.org/10.1201/9781420010008
[6]	Gross, D., Shortle, J., Thompson, H. and Harris, C. (2008) Fundamentals of Queueing Theory. John Wiley & Sons, New York. https://doi.org/10.1002/9781118625651