Friday, September 14, 2007

Waiting for Poisson

Most of us hate waiting in line. Or, at the very least, when given the choice of waiting in line or not, most of us would probably choose “not.”

Most of us probably also feel that not all lines are created equal. There’s your typical multiple-line setup at your favorite CostCo or grocery store; there’s the single-file aisle-of-impulse-buys at Fry’s Electronics or, more recently, at Best Buy. How about those tiered lines at the airport, separating the haves (first-class, super-plati-diamond-tanium members) from the have-nots (coach, me)? Have you ever stood in one of those lines, and thought, “I wish they’d line up they way they do at <put the place with your favorite type of line here>!”?

If you’ve ever felt that they aren’t the same, take heart — they’ve been proven to be different. And measurably so.

The subfield of computer science known as queueing theory (also spelled queuing theory) concerns itself with precisely this — lines, waiting in line, and servicing the “customers” that are in line. And if everyone knew just a little queueing theory, then many of us may not hate waiting in line as much as we do now.

The primary factor that affects me while waiting in line is fairness — that is, “first-come, first-served” is of paramount value. The longer you’ve been waiting in line, the sooner you should get helped. And this is where some of the lines I see everyday make me wish that everyone knew a little computer science: the single line (Fry’s, some Best Buy branches, some banks) waiting for multiple servers is known to enforce “first-come, first-served” — no matter how many tellers, cashiers, or other “servers” come and go, the client who has been waiting longest will get helped soonest. In technical terms, this type of line serializes the way customers are helped. Cut to the chase: everyone should just know to form this type of line, whenever we’re all waiting for some service that can be provided by more than one party at a time.

How many times have you groaned in frustration within a multiple-line setup, as a teller or cashier opens up at the far end of the store, and everyone who’s nearby (but who may not have necessarily been waiting as long as you have) jumps over to get helped? Or, have you ever stared longingly (or angrily) at another line, watching customers fly by because they all happened to have fewer items to check out? “Express lines” be damned — with a single queue, everyone benefits from “express” customers. With computer science, these “feelings” about multiple-line setups are no longer subjective — they’re quantifiable, objective, and provable.

Of course, we have the requisite complications. First, in a multiple-line system, we might simply try to change lines whenever we think that one line is faster than ours. This is theoretically true; however, practical issues arise. For one thing, jumping lines at our leisure in a grocery setting involves taking a shopping cart with us — this can range from being awkward to downright dangerous. For another, have you ever jumped lines like this, only to perceive that the line you just left started moving faster right after you bailed on it? Whether or not the perception is true, what matters is that it emerges — so we’re not happy. Or, at best, wistful for the line that got away. And even if line jumping weren’t potentially inconvenient or risky, there’s this final question: if more than one customer simultaneously notices a more favorable spot in another line, which one of them should take it?

Another complication is that some establishments want us to potentially hang around in line longer, to give us more of an opportunity to buy something on impulse. True, and some of us may truly enjoy the impulse experience. However, impulse buying can still be encouraged in a single line — just arrange your impulse wares along that single aisle, en masse. Bingo — less stress at the line, great chance at an impulse buy.

As mentioned, the point of all this is that if everyone knew a little bit more computer science, we’d automatically send “the man” a message that single lines are just the way to go. We would form this line automatically, without prodding, poking, or frustrating our fellow line-waiters. Daily life would be just a little easier.

For a postscript, please note that this barely scratches the surface of what queueing theory has learned about lines. The haves/have-nots line — i.e., clients with different priorities — has also been studied. Different rates at which things may happen — customer arrivals, the time it takes to perform services, etc. — are also considered and studied; this entry’s title references the Poisson distribution, which is commonly used for determining or simulating “rates of arrival” for clients and other events. But if everyone knew a little probability and statistics, then you would have known that already.   :)

No comments: