Pollaczek-Khinchine formula and Little's law for finite capacity queue

326 Views Asked by At

In queueing theory, for M/G/1 queue, there is Pollaczek-Khinchine formula to easily calculate the expected number of customers in the system by combining it with Little's law. I would like to know if I can use this approach to calculate the expected number of customers in the system of M/M/1/K queue (Poisson arrival with rate $\lambda$, Exponential service time with mean $\frac{1}{\mu}$, single server, finite capacity K).
I have tried to divide into two cases, where there are less than K customers in the system and where there are exactly K customers in the system. Then compute the expected number of customers in each case and weight average them using probabilities $p_k$ and $1-p_k$, where $p_k$ is the long-run probability there are K customers in the system. By this approach, I don't seem to get the solution which is $\frac{\rho[1-(K+1)\rho^K+K\rho^{K+1}]}{(1-\rho)(1-\rho^{K+1})}$, where $\rho$ is $\frac{\lambda}{\mu}$.
Can someone suggest which direction I should look into?

Edit: As suggested by Mick, I can calculate it directly. However, I am particularly interested in using Pollaczek-Khinchine formula and Little's law to get the expected number of customers.

1

There are 1 best solutions below

1
On

A more straightforward way is to treat the system as a continuous time Markov chain with statespace $\{ 0,1,\ldots,K\}$, where $i$ denotes the number of customers in the system. Let $p_k(t) = \mathbb P(X_t = k)$, where $X_t$ denotes the state that the Markov chain is in at time $t$. Now from the theory we know that $$ \dot p (t) = p(t) \cdot Q $$ where $$ Q_{kl} = \begin{cases} -\lambda & k=l=0, \\ -(\lambda+\mu) & 0<l=k<K, \\ \lambda & l= k+1\leq K, \\ \mu & l=k-1, \\ -\mu & k=l=K. \end{cases} $$ We also know that the stationary distribution $\pi=(\pi_0,\pi_1,\ldots,\pi_K)$ satisfies $$ \pi\cdot Q = 0, $$ which gives us the recursion $$ \lambda\pi_{k-1}-(\mu+\lambda)\pi_k + \mu \pi_{k+1} = 0. $$ The solution of is recursion is given by $$ \pi_k = q^k \frac{q-1}{q^{K+1}-1}, \quad q = \frac{\lambda}{\mu}. $$ Now the long-term behavior of $X_t$ is described by the distribution $\pi$, hence if $N$ denotes the number of customers in the system after some time, then $$ \mathbb E N = \sum_{k=1}^K k\pi_k =\frac{q-1}{q^{K+1}-1} \sum_{k=1}^K kq^k = \frac{q(1-(K+1)q^K+Kq^{K+1})}{(q^{K+1}-1)(q-1)} $$