## It's Time for Some Queueing Theory

Queueing theory is the scientific study of waiting in line. It can apply to familiar lines like those at the grocery store or bank but also to things like web servers, highway traffic, and telecommunications...basically any situation where you have things entering a system, being processed by a system for a certain period of time, and leaving the system.

The study of queueing is necessary because the effects of waiting in line often run counter to our intuition (which causes people to get cranky about it). Take this example from John Cook of tellers serving customers at a bank:

Suppose a small bank has only one teller. Customers take an average of 10 minutes to serve and they arrive at the rate of 5.8 per hour. What will the expected waiting time be? What happens if you add another teller?

We assume customer arrivals and customer service times are random (details later). With only one teller, customers will have to wait nearly five hours on average before they are served.

Five hours?! I would not have guessed anywhere close to that, would you? Now, add a second teller into the mix. How long is the average wait now? 2.5 hours? 1 hour? According to Cook, much lower than that:

But if you add a second teller, the average waiting time is not just cut in half; it goes down to about 3 minutes. The waiting time is reduced by a factor of 93x

Our lack of intuition about queues has to do with how much the word "average" is hiding...the true story is much more complex.

Aside from the math, designers of queueing systems also have to take human psychology into account.

There are three givens of human nature that queuing psychologists must address: 1) We get bored when we wait in line. 2) We really hate it when we expect a short wait and then get a long one. 3) We really, really hate it when someone shows up after us but gets served before us.

The boredom issue has been tackled in myriad ways — from the mirrors next to elevator banks to the TVs in dentist's waiting rooms. Larson mentions a clever solution from the Manhattan Savings Bank, which once hired a concert pianist to play in its lobby as customers waited for tellers. "But Disney has been the absolute master of this aspect of queue psychology," says Larson. "You might wait 45 minutes for an 8-minute ride at Disney World. But they'll make you feel like the ride has started while you're still on line. They build excitement and provide all kinds of diversions in the queue channel." Video screens tease the thrills ahead, and a series of varied chambers that the queue moves through creates a sense of progress. Another solution: those buzzing pagers that restaurants in malls sometimes give you while you're waiting for a table. Instead of focusing on the misery of the wait, you can go off and entertain yourself-secure in the knowledge that you'll be alerted when it's your turn.

Whole Foods had to work around our expectations when it switched to "serpentine" lines that seemed longer but actually served customers more quickly.

By 7 p.m. on a weeknight, the lines at each of the four Whole Foods stores in Manhattan can be 50 deep, but they zip along faster than most lines with 10 shoppers.

Because people stand in the same line, waiting for a register to become available, there are no "slow" lines, delayed by a coupon-counting customer or languid cashier. And since Whole Foods charges premium prices for its organic fare, it can afford to staff dozens of registers, making the line move even faster.

"No way," is how Maggie Fitzgerald recalled her first reaction to the line at the Whole Foods in Columbus Circle. For weeks, Ms. Fitzgerald, 26, would not shop there alone, assigning a friend to fill a grocery cart while she stood in line.

When she discovered the wait was about 4 minutes, rather than 20, she began shopping by herself, and found it faster than her old supermarket.

See also How to Pick the Fastest Line at the Supermarket, Queue Theory and Design from 99% Invisible, and this paper from Bob Wescott, Seven Insights Into Queueing Theory. One of his insights:

It's very hard to use the last 15% of anything. As the service center gets close to 100% utilization the response time will get so bad for the average transaction that nobody will be having any fun. The graph below is exactly the same situation as the previous graph except this graph is plotted to 99% utilization. At 85% utilization the response time is about 7x and it just gets worse from there.

For grocery stores or call centers, that means you're going to have operators or cashiers sitting there "doing nothing" sometimes because if you don't, you're gonna be in trouble when a rush hits.

Update: John Frost shares an anecdote about his grandfather's team designed the queueing system for the Matterhorn Bobsleds at Disneyland:

Another fun family story is the invention of the Matterhorn's first of its kind switchback queue. Vic Greene and his team of Imagineers developed a system that would have the entrance to the switchback part of the queue be lower than the exit. When you stood at the entrance, the exit would appear closer to you in an optical illusion. The idea was to make your wait seem less cumbersome by visually shortening the queue.