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 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 random variables, so it has distribution. To see this, note that if and are independent with distribution, then for any ,

so that has distribution. The general result follows by induction.

Let be the time it takes to be seen in this queue. Then where and have distribution. Let , , and be probability densities of , , and . Then for any ,

Let be the time it takes to be seen in the second queue. By a similar computation, we can show that has distribution, i.e. has probability density

Then

Since , . Therefore we should choose the second queue.

To generalize this a bit, suppose the the queue has servers and people waiting for service, for . Then , where is the waiting time having chosen queue , and

Since is fixed, it is clear that in order to minimize the expected waiting time, we should choose queue

### Like this:

Like Loading...