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.


\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\}.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s