# Queueing theory problem

Here is an interesting little queueing theory problem:

There are two lines at the supermarket automated checkout machines.

One line has four people waiting in it. They are waiting for one of a group of three currently occupied checkout machines. i.e. when any one of the three machines becomes vacant, the first person in the line takes that one, whichever one it is.

The other line has eight people waiting in it. They are waiting for one of a group of six checkout machines.

You don’t know how long the people currently using the machines have been there and you don’t know how long any particular person is going to take to buy their groceries.

Which line should you choose?

Let us assume that the service times are i.i.d. with ${\mathrm{Exp}(\lambda)}$ distribution. Then the time it takes for a service to complete and the queue to advance in the first system is the minimum of three ${\mathrm{Exp}(\lambda)}$ random variables, so it has ${\mathrm{Exp}(3\lambda)}$ distribution. To see this, note that if ${X_1}$ and ${X_2}$ are independent with ${\mathrm{Exp}(\lambda)}$ distribution, then for any ${t>0}$,

\displaystyle \begin{aligned} \mathbb P(X_1\wedge X_2 > t) &= \mathbb P(X_1 > t, X_2 > t)\\ &= \mathbb P(X_1 > t)\mathbb P(X_2>t)\\ &= e^{-\lambda t}e^{-\lambda t}\\ &= e^{-2\lambda t}, \end{aligned}

so that ${X_1\wedge X_2}$ has ${\mathrm{Exp}(2\lambda)}$ distribution. The general result follows by induction.

Let ${T}$ be the time it takes to be seen in this queue. Then ${T = X_1 + X_2}$ where ${X_1}$ and ${X_2}$ have ${\mathrm{Exp}(\lambda)}$ distribution. Let ${f}$, ${g}$, and ${h}$ be probability densities of ${X_1}$, ${X_2}$, and ${T}$. Then for any ${t>0}$,

\displaystyle \begin{aligned} h(t) &= (f\star g)(t)\\ &= \int_0^t g(t-x)f(x)\mathsf dx\\ &= \int_0^t 3\lambda e^{-3\lambda(t-x)}3\lambda e^{-3\lambda x}\mathsf dx\\ &= (3\lambda)^2 e^{-3\lambda t}\int_0^t \mathsf dx\\ &= (3\lambda)^2 t e^{-3\lambda t}. \end{aligned}

Let ${S}$ be the time it takes to be seen in the second queue. By a similar computation, we can show that ${S}$ has ${\mathrm{Erlang}(3, 6\lambda)}$ distribution, i.e. ${S}$ has probability density

$\displaystyle s(t) = \frac{(6\lambda)^3}{2} t^2 e^{-6\lambda t},\quad t>0.$

Then

\displaystyle \begin{aligned} \mathbb E[T] &= \frac2{3\lambda}\\ \mathbb E[S] &= \frac3{6\lambda} = \frac1{2\lambda}. \end{aligned}

Since ${\lambda>0}$, ${\mathbb E[T]>\mathbb E[S]}$. Therefore we should choose the second queue.

To generalize this a bit, suppose the the ${i^{\mathrm{th}}}$ queue has ${n_i}$ servers and ${k_i}$ people waiting for service, for ${i=1,2}$. Then ${T_i\sim\mathrm{Erlang}(k_i, n_i\lambda)}$, where ${T_i}$ is the waiting time having chosen queue ${i}$, and

$\displaystyle \mathbb E[T_i]= \frac{k_i}{n_i\lambda}.$

Since ${\lambda>0}$ is fixed, it is clear that in order to minimize the expected waiting time, we should choose queue

$\displaystyle i^* = \mathrm{argmin}_{i\in\{1,2\}}\left\{\frac{k_i}{n_i} \right\}.$