[pnathan]

FYI: This is an example of the branch of mathematics called queueing theory.

http://en.wikipedia.org/wiki/Queueing_theory

It's a fascinating study requiring a good knowledge of probability to use beyond the simplified models. It turns out from the math that throughput using a single queue is better than using multiple queues.

[NyxWulf]

Queueing theory is a prominent topic in Operations Research. If you want to read a detailed book on it, Fundamentals of Queueing theory by Thompson et al is the bible.

A couple of additional thoughts, pooling queues like this only works if the changeover time to process different types of things is low. So in the case of a grocery store where there is no separate changeover or batch setup time it works well. If you are pooling work to people though it breaks down if only certain people can do certain types of work or the change over time to switch to a different task exceeds a certain threshold.

The other thing is the title of this post is almost certainly incorrect. Switching to a single queue reduces average queue time, but it does not reduce work time. In order to be 3x faster you would have to reduce both. The other factor at play is that people continuously rebalance from slow lines to fast lines, which also helps mitigate some of the problems.

* some grammatical edits

[swalberg]

I'd also recommend some of the books by Neil Gunther at http://www.perfdynamics.com/, notably the PDQ one and Guerrilla capacity planning.

He takes queuing theory down to a slightly non-academic level and applies it to modelling computer systems such as web applications. From that you can fit observed data to your model and predict capacity on shorter cycles.

[rdtsc]

Not trying to be condescending but doesn't it surprise anyone here that this is _not_ obvious? At least on this site, there are still people doubting or debating this.

So I am wondering why don't stores do this already. And I believe it is because of perceptions. They understand that time will be saved, however, they realize that most people will be scared by a long line.

One long line that moves fast will still appear terrible compared to a bunch of small lines that crawl. Because people don't look long enough to estimate the rate of movement. They see both lines as static (not moving).

[philwelch]

It's another instance of "people are stupid". Yes, for any educated person it's obvious that one line is faster, that's the first thing about queueing theory, but most people don't know the first thing about queueing theory.

Other instances of "people are stupid" leading to poor design:

* Some cars come with a CVT (continuously variable transmission) rather than having to shift gears. The audible pitch of the engine just gradually goes up as the accelerator is depressed, rather than revving up and then shifting back down again. Since people were used to the gear-shifting behavior, they thought CVT's were underpowered, so they were actually redesigned to simulate the shifting behavior even though it was suboptimal.

* Coinstar machines are actually much, much faster than they appear. But people don't trust them if they don't take three times as long and make jangly coin sounds, so it just silently sorts the coins as fast as it can and plays a recording of jangly coin sounds, all the while delaying when it displays the final count onscreen.

[wisty]

A university lecturer of mine actually interviewed people in a bank, and asked them how long they thought they had stood in line. She found it was proportional to the line length, not the time they actually stood in line. Note, the bank didn't believe her, so she used some modelling package to animate it ... then they believed her.

[nandemo]

It's not at all obvious to me that one line is always faster (but then I only have a master's degree :-)). It might be faster in some situations, maybe slower in others.

In particular, the one-line system might significantly increase the average distance between (first-in-line) customer and nearest free cashier. Also, when there's a lot of cashiers, the customer might take more time to notice where is the nearest free cashier. I saw that happening the last time I checked-in for a flight.

In contrast, at immigration there is a long, single line but also short lines (1 to 2 persons) in front of each "cashier". These work as "caches" that minimize the delay I mentioned above.

[URSpider94]

As others have mentioned, one line feeding small cache lines is probably closer to reality, for the reasons that you mention -- buffering so that the cashier is always occupied.

The main goal is to prevent a single "price check" from jamming an entire line of people -- keep the queues at each station as small as possible so that most customers can route around the blockage.

[lywald]

It's obvious that one line is faster? Well it's not. Considering all cashiers are busy all the time, if it could be faster that would mean they have to manage multiple customers at the same time... If you're in the top 50% skilled at finding a line, then you're penalized because it just averages the queuing time.

[cynicalkane]

Most Nissans have a CVT now, and the ones I've driven seem to shift continuously. BMW tried implementing a discrete-shifting CVT like the one you describe for one of their semihybrids, and though I've never driven it, it got slammed in reviews. Do you have a citation for your claim?

[nik_0_0]

Do you have a source for that Coinstar playing jangly coin sounds?? I would love to read more about that.

[philwelch]

Well, this is embarrassing: I remembered that story from somewhere, and it turns out somewhere was another Hacker News thread: http://news.ycombinator.com/item?id=2007818

[JamesAn]

"Counting 600 coins per minute, Coinstar machines detect the metal content of the coin, as well as the size to accurately identify the coin denomination - and efficiently sort out all kinds of debris typically found in consumer coin. The company has found paper clips, key chains, wedding bands, gum wrappers, even teeth, all of which are identified quickly as non-coin."

http://web.archive.org/web/20100324183932/http://www.coinsta...

[cheald]

Fry's Electronics does the single line thing, and any time there is a line, I feel like I end up standing in it longer than I would at a grocery story. I suspect this is probably psychological, but letting me, as the shopper, pick the line I want to stand in puts me in charge of how long I wait. If I pick a bad line, it's my fault for picking the bad line. When there's just one line available, I don't get that choice.

Single-queue might be faster, the the psychology of customer satisfaction is much more complex than that.

[prodigal_erik]

When I have to choose a line I find myself harshly judging the people around me, because every difference can impose a cost in boredom and lost leisure time. "This guy's old and worn out. They seem kind of foreign, won't understand the cashier. That one looks poor, probably uses a lot of coupons and argues about what's discounted. They're paying all their attention to their kid instead of getting out of everyone's way." It may be the most socially corrosive thing I routinely do.

Edit: and I think I just convinced myself to get a smartphone (I'm reluctant to bring a paperback, it might look like shoplifting because they sell those).

[hn_reader]

Indeed, since I got a smartphone I no longer dread long lines in supermarkets, etc. Just more time to read HN.

[anamax]

The single line has another property that fry's exploits.

The single line is longer, so it has more space in which to pitch impulse purchases. (It's probably shorter than the sum of the "equivalent" individual lines.)

[nhebb]

Fry's might not be a good example because many of their orders are ticketed items, so the cashier does more than just ring you up. For example, last week I bought a hard drive there, and it took a minute for the cashier to retrieve the item then print out the warranty disclaimer/waiver. Target, on the other hand, has checkout arrangement that looks like a rabbit warren.

[mattmcknight]

The Target near me is an interesting case, because the set of registers is so spread at least 30 checkouts, maybe 75m across. The time it would take some of these bumblers to get to the single line and then walk to the check out would cancel out a lot of the gain.

[AndyNemmity]

I go to Fry's a ton, and it always seems to go much quicker, but I agree, psychologically standing in a tremendously huge line feels worse.

[squidfood]

My experience is exactly opposite.

Sure a big line is initially discouraging. But while in line, if I've chosen one of several lines, I fixate: is my chosen cashier a slow idiot? is a customer ahead of me fumbling for change? Should I jump? There's another line opening, should I get ready to run for it? I invariably end up at the front more directly annoyed and snippy at "my" cashier and the whole process. With a single line, I can see everything humming along, moving forward more often, if one transaction takes a while, so what, it's not a race, I relax more, I'll get there.

[mc32]

--which is why Delis‡ traditionally give you a numbered tag. It's a single line, but you can go about and not feel "constricted" to the queue (tail).

Don't forget, Frys also has a "semaphore" who cues people to the next register.

‡among many places like hospitals, information centers (DMVs), etc.

[MartinCron]

My favorite hardware store (Dunn Lumber in Seattle) does the same thing. It was difficult to get used to at first, but it's really nice to just take a number, wander around, and then not feel like you're holding anyone up if you don't order your lumber as fast as is humanly possible.

[Semiapies]

Best Buy has been doing that, too.

[tomkarlo]

Stores are moving towards this, but very slowly. The retail industry doesn't tend to innovate quickly. Generally, you see the more innovative / aggressive stores doing this now (Whole foods, some drug chains, Apple stores, Best Buy) but it could take a decade or more to spread widely, in particular because in many stores it requires a significant layout change to accomodate one long line - generally you need additional space between the front of the line and the registers so that customers can go to the open checkout, and some stores don't have that much space.

[malvim]

I used to be very afraid of long single lines, until I studied a bit of queue theory in college. I now feel angry whenever I see lots of small lines, and relieved when I'm in a store that has a larger single line with a bunch of "servers" at the end.

Unfortunately that is the ONLY thing I got from that subject: "single line with lots of servers better than lots of lines with one server each". I can't really remember anything else, like WHY this is the case or how queues work. :/

[mahyarm]

At a walmart in Canada, they had an express line which had 6 cashiers and one line. A LCD screen chimed with the number of the next cashier when they were ready.

[Semiapies]

The layout of the store may make switching to a single line tricky. You need enough area for people to line up, and stores I've seen with this layout usually had a larger area between the aisles and registers than most grocery stores. Also the largest big-box stores would have to go with multiple multi-register lines due to the sheer number of registers.

[clord]

Stores are focused on individual wait times, not on total throughput.

[scott_s]

The problem with learning even basic queuing theory is that, for the rest of your life, you will think "There is a much better way to do this, and I can prove it" after having to choose a single line.

[Avenger42]

Eric Lippert (C# designer at MS) wrote up a post titled "Queueing Theory In Action, plus, frogs" a couple of years ago, regarding his experience with lines like this at airports:

http://blogs.msdn.com/b/ericlippert/archive/2009/08/20/queue...

[brown9-2]

This is a bit of an aside, but something I've always wondered is: why does this branch of mathematics get labeled as Queueing "theory"?

From my brief understanding, when someone talks about Queueing theory they are not talking about a singular "theory" but they mean something much broader. It doesn't seem as if there is something here that needs to be proved or disproved.

This is a part of naming in mathematics that has always perplexed me.

edit: not sure why this would get downvoted, seems like a simple neophyte question

[JonnieCache]

It's a common enough construction. Quantum theory, set theory and so on.

[lightcatcher]

Realize this is a worthless comment, but I couldn't stand the exclusion of graph theory.

[JonnieCache]

How could I forget chaos theory and string theory.

[gujk]

Because no one can spell queuology or queuistics.

[guyzero]

And if anyone was wondering, it's not exactly new. When did I learn the proof that single queue is faster than multi-queue? In undergrad 20 years ago. And yet so many multi-queue setups out there...