Expected waiting time in M/M/1 queue

Question

What is the expected waiting time in an $M/M/1$ queue where order service is last-in-first-out? On service completion, the next customer served is the most recent arrived. Suppose we do not know the order of service (think of a busy retail shop that does not have a "take a number" system).

I tried many things like using $L = \lambda w$ but I am not able to make progress with this exercise. I am new to queueing theory and will appreciate some help. I can't find very much information online about this scenario either.

I found this online: https://people.maths.bris.ac.uk/~maajg/teaching/iqn/queues.pdf

It helped me understand more.

But it does help me with this problem.

I think that the expected waiting time (time waiting in queue plus service time) in LIFO is the same as FIFO. But I am not completely sure. I remember reading this somewhere. Maybe this can help?

Answer 1

In terms of service times, the average service time of the latest customer has the same statistics as any of the waiting customers, so statistically it doesn't matter if the server is treating the latest arrival or any other arrival, so the busy period distribution should be the same. I think that implies (possibly together with Little's law) that the waiting time is the same as well.

Answer 2

Let $X(t)$ be the number of customers in the system at time $t$, $\lambda$ the arrival rate, and $\mu$ the service rate. Assume $\rho:=\frac\lambda\mu<1$. We have the balance equations $$ \lambda \pi_n = \mu\pi_{n+1},\ n=0,1,\ldots, $$ which yield the recurrence $\pi_n = \rho^n\pi_0$. From $\sum_{n=0}^\infty\pi_n=1$ we see that $\pi_0=1-\rho$ and hence $\pi_n=\rho^n(1-\rho)$. The expected size in system is $$ L = \mathbb E[\pi] = \sum_{n=1}^\infty n\pi_n = \sum_{n=1}^\infty n\rho^n(1-\rho) = \frac\rho{1-\rho}. $$ By Little's law, the mean sojourn time is then $$ W = \frac L\lambda = \frac1{\mu-\lambda}. $$ Now, the waiting time is the sojourn time (total time in system) minus the service time:

$$ W_q = W - \frac1\mu = \frac1{\mu-\lambda}-\frac1\mu = \frac\lambda{\mu(\mu-\lambda)} = \frac\rho{\mu-\lambda}. $$

We can further derive the distribution of the sojourn times. Let $L^a$ be the number of customers in the system immediately before an arrival, and $W_k$ the service time of the $k^{\mathrm{th}}$ customer. It follows that $W = \sum_{k=1}^{L^a+1}W_k$. Conditioning on $L^a$ yields \begin{align} \mathbb P(W>t) &= \sum_{n=0}^\infty \mathbb P(W>t\mid L^a=n)\mathbb P(L^a=n)\\ &= \sum_{n=0}^\infty \mathbb P\left(\sum_{k=1}^{L^a+1}W_k>t\mid L^a=n\right)\mathbb P(L^a=n). \end{align} By the so-called "Poisson Arrivals See Time Averages" property, we have $\mathbb P(L^a=n)=\pi_n=\rho^n(1-\rho)$, and the sum $\sum_{k=1}^n W_k$ has $\mathrm{Erlang}(n,\mu)$ distribution. So we have $$ \mathbb P(W>t) = \sum_{n=0}^\infty \sum_{k=0}^n\frac{(\mu t)^k}{k!}e^{-\mu t}\rho^n(1-\rho) $$ Since the summands are all nonnegative, Tonelli's theorem allows us to interchange the order of summation: \begin{align} \mathbb P(W>t) &= \sum_{k=0}^\infty\frac{(\mu t)^k}{k!}e^{-\mu t}(1-\rho)\sum_{n=k}^\infty \rho^n\\ &= \sum_{k=0}^\infty\frac{(\mu t)^k}{k!}e^{-\mu t}\rho^k\\ &= e^{-\mu t}\sum_{k=0}^\infty\frac{(\mu\rho t)^k}{k!}\\ &= e^{-\mu(1-\rho)t}\\ &= e^{-(\mu-\lambda) t}. \end{align} So $W$ is exponentially distributed with parameter $\mu-\lambda$. To find the distribution of $W_q$, we condition on $L$ and use the law of total probability: \begin{align} \mathbb P(W_q\leqslant t) &= \sum_{n=0}^\infty\mathbb P(W_q\leqslant t, L=n)\\ &= \sum_{n=0}^\infty \mathbb P(W_q\leqslant t\mid L=n)\mathbb P(L=n)\\ &= (1-\rho)\cdot\mathsf 1_{\{t=0\}}+(1-\rho)\cdot\mathsf 1_{\{t=0\}} + \sum_{n=1}^\infty (1-\rho)\rho^n \int_0^t \mu e^{-\mu s}\frac{(\mu s)^{n-1}}{(n-1)!}\\ &= (1-\rho)\cdot\mathsf 1_{\{t=0\}}+\rho(1-\rho)\sum_{n=1}^\infty\rho^n\int_0^t \mu e^{-\mu s}\frac{(\mu\rho s)^{n-1}}{(n-1)!}\ \mathsf ds\\ &= (1-\rho)\cdot\mathsf 1_{\{t=0\}}+\rho(1-\rho)\int_0^t \mu e^{-\mu(1-\rho)s}\ \mathsf ds\\ &= (1-\rho)\cdot\mathsf 1_{\{t=0\}} + 1-\rho e^{-\mu(1-\rho)t)}\cdot\mathsf 1_{(0,\infty)}(t). \end{align}