header home
rss rss
itunes itunes
youtube Youtube
facebook facebook
twitter twitter

download video: mp4 or iPod friendly

| More

Queueing theory

Bill introduces queueing theory and uses it to design the most efficient check out line.

Learn more

Transcript I'm sure that this week you've been trapped in a slow moving line. In this box I have a gift that shows how to choose stores with the shortest wait in line ... an old-fashioned telephone!

Now, of course, it isn't the phone that's important, it's the study of early phone systems. It began in 1909 at the Copenhagen Telephone Company when an engineer there, Agner Krarup Erlang, asked the question how many trunk or main telephone lines are needed to adequately service a town.

Now, you could put in just one: That would mean huge delays because of blocked calls. You could install one for each phone. That's expensive and wasteful since not everyone calls at once. The telephone company needed a trade-off between these two extremes.

To see what Erlang did let's look at a town where there's an average of two calls an hour. You'd think two trunk lines would do, but Erlang showed that although the average rate is two an hour; the calls will bunch up.

A lot of time it will be only two calls, but also sometimes none or three or four or five will occur. He showed that given the average number of call and their average length one can estimate the number of trunk lines needed.

To make the calculation simple I'm assumed that Danes like to talk a long time - one hour on the average! Erlang showed that for only 1% of the people to have a blocked call you'd need to install 7 trunk lines.

What has this to do with our holiday season? A shopper approaching a cash register is like a phone call arriving, and an open cashier is like an available trunk line.

To keep the lines moving it would seem that the store should just measure the number of people arriving in a typical hour and then assign enough cashiers so that everyone will be served quickly, but as Erlang showed that's a recipe for

gridlock. People will arrive in bunches, not spaced out evenly. So, if stores have just the right number of cashiers for the average number of shoppers in an hour, the stores will, at times, have too few cashiers, resulting in long waits.

Instead they should make a single line feed multiple cashiers. For three cashiers its about three times faster than having a line for each cashier. Here's why: In the single line/single cashier set-up any delay - like a price check - stops the line completely. In contrast when a line feeds to multiple cashiers it's likely that only one of the three customers in front of you will have a delay - because recall that in Erlang's model delays and events are distributed randomly - and that means a register will likely be open.

Most stores don't do this, though, because it bothers customers psychologically: Customers prefer unwisely to jockey for position.

This also explains why other lines always move faster than your line - or at least why they seem to move faster. Picture yourself in a line, with a line on each side.

We'll label them A, B and C - and assume you are in line B. Now if it's random that any of these lines will have a delay there are six possible arrangements of the fastest to the slowest line at any particular moment. It could be that A moves faster, or B moves faster, or C takes the lead. Now look at your line: Only twice out of six permutations did it come out in front. Thus there's only one change in three that it will be moving faster, and greater odds - two out of three - that one of the other lines will breeze past you.

So, here is Erlang's holiday message. Sure, today that other line moves faster, but some days you'll be in the faster lane. In other words, during this season: Relax and let the odds be with you.

I'm Bill Hammack, the engineer guy.