Hacker News new | comments | show | ask | jobs | submit login
A single line to 3 cashiers is ~3x faster than a separate line for each cashier (wsj.com)
241 points by blakehill 2114 days ago | hide | past | web | 163 comments | favorite

FYI: This is an example of the branch of mathematics called 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.

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

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.

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).

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.

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.

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.

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.

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.

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?

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

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

"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."


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.

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).

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

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.)

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.

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.

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.

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.

--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.

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.

Best Buy has been doing that, too.

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.

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. :/

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.

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.

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

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.

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:


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

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

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

How could I forget chaos theory and string theory.

Because no one can spell queuology or queuistics.

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...

scala> import org.apache.commons.math.distribution.{ExponentialDistributionImpl=>expo}

//pc = process customer, with a mean time mu per customer

scala> def pc(mu:Int):Double= new expo(mu).sample

// q = queue of n customers with mean process time mu

scala> def q(n:Int,mu:Int):Double=(1 to n).map(_=>pc(mu)).sum

scala> // put 3000 people in 1 queue with mean process time 50

scala> (1 to 1000).map(_=>q(3000,50)).sum/1000

res43: Double = 83107.37275937156

scala> //now put 1000 people each in 3 separate queues with the same mean process time as before

scala> (1 to 1000).map(_=>(1 to 3).par.map(_=>q(1000,50)).sum).sum/1000

res45: Double = 200010.29627921886

200010 = ~3x83107, so yeah, single line to 3 cashiers is ~3x faster than a separate line for each cashier.

// Now make 1 queue that feeds into shortest of the 3 queues

scala> def qq(n:Int,mu:Int)=(1 to 3).par.map(_=>{(1 to n/3).map(_=>pc(mu)).sum}).sum

scala> (1 to 10000).map(_=>qq(3000,50)).sum/10000

res70: Double = 141824.974765643

So our single queue feeding into 3 separate queues still beats 3 separate independent queues.

edited to address MaysonL's question.

Okay, someone with some Scala expertise needs to jump in here. The code as written is _clearly_ incorrect. q(n,mu) sums a distribution with mean mu n times. The expected value of this is mu * n. Then we run this 1000 times and average the results. If this is not extremely close to mu*n then I will eat my hat. In R, sum(replicate(1000,sum(rexp(3000,1/50)))) / 1000 returns ~150000 (using sum for clarity instead of mean). Maybe scala is caching the seed or something?

I don't know what the "par" function does, but assuming it doesn't do anything crazy, the answer for all three of those expressions should be exactly 150,000, because they just reorder the order of summation.

Ok, I realized that I wrote something like this without seeing your post first.

The poster is a quant working with Scala so I am certain I have just misunderstood something. Nevertheless, my humble bachelor's degree has led me to the same conclusion as you.

But of course this is BS, because the three queues are not independent. Try it with 1 queue which feeds into whichever of the three queues is currently shortest. And of course, in grocery stores, where one can unload one's cart while the person ahead is being processed, there's an advantage to multiple lines.

Isn't this essentially equivalent to having a single queue though... except now you have a kind of cache at each register holding a small number of customers?

Yes, and it is how real stores work, which is the point.

Except that the "primary" queue doesn't feed into the shortest register queue, it feeds into the register queue that the person at the front of the primary queue anticipates will empty the fastest. That's the premise that underlies the whole article: people get in the line they predict will move the fastest, and everyone uses different variables and judgment to make that prediction. Those variables and those predictions don't show up when your model is based on distributions.

The register queues are not independent, but they are not related as simply as you say.

>everyone uses different variables and judgment to make that prediction. Those variables and those predictions don't show up when your model is based on distributions.

Sorry but that's simply not true. everyone uses different variables and judgment to make a phone call, yet phone calls follow an exponential distribution! everyone uses different variables and judgment to hit the internet, yet network traffic follows a Lavalette distribution. everyone uses different variables and judgment to buy stocks, yet equity prices follow a lognormal distribution.

Individual behavior in aggregate will almost always follow some distribution, regardless of each individual using different variables and judgment for himself. The whole point of statistics is to uncover the underlying probability distribution given tons of (seemingly random) data. Math does the opposite ( ie. given the distribution, a mathematician can tell you how to derive nice things like the moment generating function & the first & second moments & density functions & related family of distributions & so on, & in general give you n sample variates that fit the distribution. By saying "everyone uses different variables and judgment" you are in essence saying its just too complicated, but even if that were true, that is just another distribution ( white noise )

"Phone calls follow an exponential distribution"

I'm confused as to the meaning there. What is it about phone calls that follow an exponential distribution? Their duration? Their quantity per capita per time of day?

>I'm confused as to the meaning there. What is it about phone calls that follow an exponential distribution?

Sorry for the confusion. Lemme clarify a bit. Say you work at an office. 9am to 5pm. 8 hours a day.

scala> 60x60x8

res45: Int = 28800

So a phone call can arrive in any one of those 28,800 seconds. Putting it another way, the probability p of getting a phone call at any particular second is very remote, but the number of seconds aka trials is n=28800 ie. very large. Anytime you have very small p and very large n, that's a nice candidate for a particular member of the exponential family of distributions. In this case, the arrival times of phone calls to your office will be Poisson.

Say you hire an office assistant to count the number of phone calls every day, and she tells you after a month that your office averages say 24 calls a day. That 24 is your mu, the mean of the Poison distribution.At that point you know everything you need to know about the distribution, because Poisson is a discrete distribution whose probability p is specified entirely by the mean mu!

So you can go off and compute the probability p like so:

scala> import scala.math.{exp,pow}

scala> def fact(n:Int):Int = { if( n>1) nfact(n-1) else 1}

scala> def p(mu:Int,n:Int) = {pow(mu,n)exp(-mu)/fact(n)}

The chances of your office getting 4 or fewer phone calls by noon is then easy to figure out. Since you average 24 calls in 8 hours, you should average 9 calls by noon. So the probability of getting 4 or fewer calls would be

scala> (0 to 4).map(p(9,_)).sum

res46: Double = 0.05496364149510491

So you have a 5% chance of getting 4 or fewer calls by noon. If someone offers to bet a million dollars that your office will get 4 or fewer calls by noon, the odds of winning that bet are 1 in 19.

edit:formatted for better readability.

Thanks for explaining it that way, I think I understand better now.

Would you agree, though, that customers wouldn't simply enter the shortest available line?

>Would you agree, though, that customers wouldn't simply enter the shortest available line?

I don't agree with that at all. In reality, some would and some wouldn't do what you suggest. If all of them did exactly what you are suggesting ( some sort of extreme rational agent), the distribution wouldn't be exponential. But then, all human beings don't buy low & sell high, nor do all of us withdraw money from the same ATM at the same time, nor do we make phone calls at the same time, or hit the internet at the same time. Aggregate behavior distributions modelling aggregate behavior of individual humans work well except in very extreme conditions such as 911 when everybody does indeed make the phone call at the same time thus jamming up the airwaves and killing the shape of the nice Erlang distribution at the telephone exchange.

Right. I wonder what would happen if we try to include a measure of perceived fairness from the customer's point of view into this type of analysis. I always feel I'm picking the wrong queue at stores... single queues going to whatever cash is open seem fairer, if that makes sense.

Perceived fairness is very hard to quantify objectively. Is it fair if there are queues for people buying less than X items? If there are queues for people not paying cash? For frequent flyers? That you, by sheer misfortune, end up in the slow queue three times in a row? Should pensioners wait for people having work to do? Should fit people make room for the elderly? To what extent? Etc.

Instead, I think you should do the math; it will teach you that the probability that a given queue is slow is smaller than the probability that, given a person in a queue, that person is in a slow queue.

So, you spend more time in slow queues than in fast ones. Once you know that, train yourself to accept it.

That's because if there are 4 lines there is generally a 75% chance that one of the other lines was faster.

>Try it with 1 queue which feeds into whichever of the three queues is currently shortest

I have edited my original response to include that scenario as well. btw for M/M/1 vs M/M/3, here's a good reference: http://people.brunel.ac.uk/~mastjjb/jeb/or/queue.html

I'm having a hard time following the scala.

Do you mind writing out what you're doing in pseudocode or in words? Intuitively, this result doesn't seem obvious to me.

Imagine where you have a one line scenario - you watch which register people go to. Label people who went to registers A,B,C with A, B and C respectively. Then, repeat the situation, but instead of one line, use 3, where everyone labeled A stands in one line, B in the other, and C in the third.

The transactions play out exactly like before. I realize we're dealing with probabilities and expected values, but it's definitely not obvious to me.

Sorry, here's some R code ( profusely commented ) http://www.stanford.edu/class/cs109l/code/week5/exponential....

>Intuitively, this result doesn't seem obvious It isn't obvious because human arrival times at checkout counters follow a Poisson distribution and their service times follow an Exponential distribution. The stated results follow immediately if you look at the cumulative density function for the exponential.

Stated another way, suppose service times followed a Uniform distribution. Then none of this would hold. But because they are Exponential, these results come into play. Intuitively, we think in terms of Uniform distribution. So your mind is saying, wait a minute, if there are 1000 people in a queue, they probably average a 10 to 15 service minute per person. But that's like saying if there are 1000 people in an office, they probably make 100k on average because that's about what you (might) make. In reality incomes follow a Pareto, so your janitors will take home 30k and your managers will pull in a couple mil. A similar sort of dynamic applies here with the exponential distribution. The key takeaway is: Service times are not uniform but exponential.

Can you elaborate on your code? Why are you summing the 3 parallel queues total time of processing together? Those processes occur in parallel, so I am uncertain what the sum of times is supposed to represent. Total time to clear all lines? That should be the nearly same number as one line with 3 people processing. So long as all 3 cashiers are constantly engaged, average wait time per customer for the entire system must remain unchanged independent of the queueing system used. Even a LIFO model for processing customers will have the same mean wait time per customer.

I am also very curious why the total time to process 3000 customers with mean time 50 is not closer to 3000*50. Perhaps I have missed something on the technical side.

You need whole distribution of process time, not just mean for simulation.

A blend is probably a better choice.

It's obvious that single queues for each cashier isn't very efficient, but the tradeoff is that lines are visibly shorter, and progress to the goal is clear.

Having a single line for all cashiers (ala Fry's Electronics or an airline ticket agent) is more efficient, but the long line, logistics of finding the next available cashier, and uncertainty of completion make for a frustrating experience as well.

I posit that having N banks of 4-6 cashiers is a good balance between both. You get the efficiency gains of not being blocked by a bottleneck, and you also get visibly shorter lines and the benefits of estimating when you are next (ok, looks like cashier 1 and 2 are almost done, I should be out of here in a few minutes).

Someone here mentioned this kind of setup with self-checkout at grocery stores, and I think it works well, as long as the number of self-checkout stands in the "bunch" is not too large. There's a local grocery store where there's 8 of them, and it's a little too chaotic (IMO, anyway).

Having more than one line materially increases stress for shoppers, because the choice implies they might be on the "wrong" line. So they worry more about how fast they're moving, etc. If you only have one line, you can tell people exactly how long the wait is (because the average transaction time is very stable) and customers don't have to worry about making the right choice.

Having one combined line can increase stress for shoppers too, especially if the line isn't clearly marked by barriers.

What happens is, another customer comes along, sees three cashiers and one queue (in the middle) and decides to join the "empty queue" in front of the cashier at either end.

Of course they know there's only one queue and that they are queue jumping, but they calculate that they can pretend they didn't know.

I assume there's a cultural factor here. I'm in the UK and have seen this many times in one store nearby, but I imagine that in some parts of the world you would be beaten or shot for it. I have never seen anybody complain about it, they just temporarily disperse into three queues (which is awkward because there is not really enough room.)

This is why you really need a new store design. At Best Buy and Whole Foods here, there's a long line that channels into a checkout area that's only reachable via that line. So there's now worry about cutting, and customers naturally form the line as they follow the route into the checkout area.

It's worth noting that WF does use 2-3 lines in a lot of stores where they don't have a long enough space. But then what they do is have a system that signals which line gets to head a register next (and does so in a set rotation), so it's effectively the same as a single long line.

I thought the British were the world champions of queuing, even in situations where there are no affordances, Brits instinctively know how to queue and suffer no jumper.

Most of the grocery stores in my area have installed self-checkout systems that are especially great if you just have a handful of items that all have UPCs (no produce or bagged bulk), don't have any items requiring an age check and possess at least the intelligence of a fifth grader.

I mention this not just because it's relevant to the idea of waiting in line at a store, but because in every store where I've seen these systems installed, the entire bank of scanners has a single line, unlike the rest of the store. I imagine it's mostly because they place the self-check scanners so close together (because they can) that it doesn't make sense to try to form multiple lines, whereas a single queue system for the real checkers would take up a huge amount of space.

Here in San Diego we've had self-checkout systems in most major stores for a few years now.

At first they were awesome because nobody used them, so you could zip right through and avoid the lines. But now, after they've been here for a few years, a lot more people feel comfortable using them but many of those people use them poorly and far too many people will use them even when they have an entire cart full of groceries. That's an entire cart full of stuff they have to scan without accidentally voiding the whole order (which I've seen happen multiple times), a lot of trial and error on trying to figure out how to scan their produce, etc, etc.

It has reached the point where I rarely bother with self checkout anymore unless there is absolutely no line for it because while the system works great when nobody else is using it, it doesn't scale that well because most people are terribly slow checkers relative to dedicated workers doing that job.

I've seen similar things in my local store. They've finally upgraded to newer self-checkout machines, which means there's less hassle. The worst with the machines is them always telling you "please put the item in the bag" because it can't register a gravy packet and it keeps telling you until a worker overrides it. Then there's always the fuck ups where the item doesn't scan, you put it in a bag and have to pull it back out, and then it tells you "please put the item back in the bag" and won't let you scan it so you can.

The one problem with the theory described above is that most walmarts have a 6 cashier express with a single line, and besides 'rush hour' when the store is packed it's often faster to go to a till to get <10 items scanned. I've ran in before and been out in minutes by going through a regular cashier and avoiding the express because the single line holds the problem that people are stupid, don't pay attention or can't hear and hold up the line, then they have to unpack their cart.

Theory is great, but it's useless when you're stuck behind a bunch of old women who can't hear them being called and spend 20 minutes chatting with the cashier.

Most of the grocery stores in my area have installed self-checkout systems that are especially great if you just have a handful of items that all have UPCs (no produce or bagged bulk), don't have any items requiring an age check and possess at least the intelligence of a fifth grader.

I love these, because I can be done in 10 seconds. The people in front of me in line to use these, however, are rarely able. It's actually faster to wait in the non-self-checkout line these days because the people in the self-checkout line use them so slowly.

Around here, the grocery self-checkout works the same as the normal checkouts, mainly because they just replaced the normal ones in place.

(Also, self-checkouts suck. I bet their throughput is terrible compared to manned checkout lines. That teenage checkout girl is WAY better than I am at scanning stuff.)

Ah, but you see, anyone who writes checks (hellooooo, slowdown!) and anyone who is scared of technology (I think the two groups overlap a lot) will go wait in another line. So at least at my store, the self-checkout lanes have a lot of young people buying one or two items and paying with credit cards, which works out to a pretty good speed. Occasionally you get somebody who sits and stares at each screen of instructions for a good 30 seconds, but in general it moves well.

I guess it depends on the quality of the self-checkout system. At my Stop & Shop, there are four or six self-checkout lanes staffed by a single person (Go go union job elimination!) If you get through a purchase without running into "wait for attendant", sure it's fast. But if you do have to wait, because their fundamental distrust of the customers makes the system get many false positives for stealing, now you are in a secondary line of people waiting for the attendant, and the time for checkout is terrible.

Wow, that sucks. My local store only ever does "wait for assistance" when you buy booze... and half the time the attendant will just gleefully press "ok" on his terminal without even checking my ID, so it goes even faster :)

Implementation details matter, I guess. (Pretend I made some interesting reference to Steve Jobs' managing style here)

In some stores if you scan alcohol the machine will freeze until the attendant turns the key.

In others, it flashes a light to alert the attendant. It allows you to carry on scanning, but the attendant must turn the key before you pay.

I just hope that isn't patented.

Yup.. the system tends to bump into that mode any time it notices a disparity between the weight of the bag you're filling and the items you've scanned. I had that trigger last night because I brushed the top of my paper bag while scanning the next item.

The short term problem is that there's only one attendant and many customers run into problems with the process - I was stuck behind an elderly couple that couldn't figure out the card payment terminal. All I needed was for the attendant to press one button on her screen so I could keep scanning. If they're going to switch to these new systems they should at least use 2-3 attendants for a while until customers get used to them.

As much better as the teenage checkout girl is than I am at scanning, it's nothing compared to how much better she is at pricing produce.

If they know what its. I've had a lot of checkouts turn into a game of "what's this vegetable." Or they just enter it as some other, more familiar vegetable.

If it's one that costs less, you win.

I found at my old grocery store that self-checkouts had much better throughput than real lines due to self-selection. People who have many items, or who have coupons / are paying by check / need special help, will avoid the self-checkouts.

Self-checkouts are not just about speed. They also appeal to specific kind of people.

I use them because I don't want to interact with someone just to get some groceries. I know, it's kind of sad, but I don't want to say 'Hi' and 'Thank you' and I don't want 5 bags when 2 would suffice and don't want to explain that, so I just do it myself.

You must be very popular at parties.

(Let the downvoting begin)

Downvote for what? Bad character?

To design is shop is not about math or throughput, it's all about psychology. You don't want lines to move fast, you just want them to appear like moving fast.

My point is merely that self-checkout is not only about speed, it's about personal comfort too.

"""Downvote for what? Bad character?"""

No, I was referring to me being down-voted, for my snarky comment.

"""My point is merely that self-checkout is not only about speed, it's about personal comfort too."""

Sure, could be, but the particular "irritations" you mentioned I see as belonging to persons too self-absorbed, being the very definition of "first-world problems" for the Monk types among us.

In my experience, the slow down is the cost of the extra features of the self-checkout system running on (I'm guessing) weak hardware. There is a rather large delay when choosing payment sources or in between bagging items.

Between bagging items, it has to wait for the scales underneath the bagging area to register a consistent weight. When choosing a payment source, it probably has to do a network call to the PIN-pad system. It's not like it's running on a slow CPU.

Good point. At any rate, there is room for improvement, especially considering the normal checkout systems appear to perform more quickly.

Because cashiers are trusted and customers aren't. There's still the delay during checkout, though.

Self-checkouts don't have to suck, though. The version where you scan all your items at a single location is clearly crap, but there are systems where you get a small hand-held device when entering the store so you can scan your items as you go along.

> Self-checkouts don't have to suck, though. The version where you scan all your items at a single location is clearly crap, but there are systems where you get a small hand-held device when entering the store so you can scan your items as you go along.

This is presumably much better for throughput, but much worse for making sure that what you're leaving with is what you purchased. (Also, how does it accommodate a decision to put something back? I've never seen such a system.)

> This is presumably much better for throughput, but much worse for making sure that what you're leaving with is what you purchased.

Admittedly, yes. But there are usually random checks.

> (Also, how does it accommodate a decision to put something back? I've never seen such a system.)

You press the "put back" button and scan the thing you want to put back.

In stores in Sweden with self-scanning there are scales in the vegetable department that will print out an appropriate UPC for you to scan (with your hand-held scanner). People who don't self-scan are also recommended to use these to let the cashier avoid weighing all goods. You still have to contact a cashier for age-restricted merchandise such as beer and tobacco, though.

To self-scan you need to register with the store, and in the beginning you're manually checked a couple of times. They track how many errors you have and on what kind of merchandise, and determine how trust-worthy you are and how often you should be manually checked.

I can't remember if this was already implemented or just a suggestion from somewhere, but the self-scanning devices could track your location in the store, both to analyze customer behaviour but also to monitor any suspicious activity. If you spend 15 minutes in the electronics department without scanning anything, maybe that warrants a manual check.

As a side note, I wonder how much time self-scanning and self-checkout really saves in the end, for the consumer, and how much of it is just letting us do more unpaid labour under the impression of efficiency.

The most interesting fact about the self-checkout systems, in my mind, is that they actually have no designated area or instructions for how lines should form. People just intuitively wait outside the general self-checkout area, and use the machines as they become available. So, at least in some circumstances, the single queue system obviously can make a lot of sense to people.

This is the interesting part to me as well, although I do have a couple of anecdotes:

- I have seen at least one store where a single sign is placed at the front of the full collection of scanners stating "line forms here" or something similar, regardless of how many there are or how they are arranged. - I have seen at least one case where, in a store that did not have the above sign, one line formed for each "vertical" bank of scanners. For example, in my local Safeway, there are six scanners: two rows of three each, lined up next to each other, parallel to the checkstands. It is pretty intuitive/obvious that they don't intend for people to line up at each individual unit in a single row, but often a queue will form for each row.

what's interesting to me about the single queue that forms at the self checkouts is that there is no explicit instructions to do this. everybody intuitively lines up in a single queue, despite having lined up in separate queues their entire lives until the self checkouts were introduced. i'm sure none of them have read studies telling them that this is the most efficient method, they just do it. and every now and then somebody tries to start a second line and gets glared at.

It seems to me to be a function of how the machines are spaced. People need a certain amount of personal space. The single line is the only way to provide it given how tightly the self-checkout machines are packed.

An excellent video on the phenomenon from the "Engineer Guy" series: http://www.youtube.com/watch?v=F5Ri_HhziI0

And just in case you feel like killing about 20 minutes of your day, check out the rest of his videos. They are excellent.

I love his videos. I wish he would make more. The harddrive one was interesting.

The biggest queue problem I see in a large store is McDonald's.

In the early days, the food was all built asynchronously from the orders. Cashiers would walk back and fill the order themselves from the bin full of burgers and fries in pretty quick fashion and the customer would be on their way.

When the whole "made as you go" approach was started, McDs decided to keep the 1:1 cashier-customer model (unlike Burger King or Wendy's, who do it 1:N style).

So now you have customers ordering and standing around next to their cashier waiting for the food to be made, which the cashier has no control over. The order of filled requests is also somewhat random. If the kitchen is having trouble, people start piling up by the counter.

I've noticed that some stores are experimenting with a numbering system that is encouraging you to step back and watch a monitor for your order when it is ready.

Wouldn't it be 3x the velocity, but the line is 3x longer, so your total wait time is the same? The article is mainly saying that people like moving faster, but is that really a phenomenon?

Yes. The bottleneck is the total throughput of the cashiers. Now, better deployment of cashiers can help. If you have N people come into your store, you're going to have to check them all out at some point. The problem is that if you always have enough cashiers to help people as soon as they are ready, you'll be paying cashiers to stand around during lulls. Stores try to avoid this by moving cashiers to other jobs when there's a lull, but this only helps for fluctuations with timescales long compared to the time it takes to start and finish a job.

hrabago's point is important, but it certainly doesn't justify the linkbait title. A single line will decrease the variance of the wait time. Since the customer's impression of the wait time is very non-linear, this might significantly reduce customer unhappiness. But that isn't some brilliant insight into the process of handling customers faster.

No, because the cashiers handling smaller transactions finish quicker and can process more people. If you're stuck behind a guy which takes 2 minutes to check out, people in other lanes will be in their cars before you even begin checking out.

Here's a concrete example to make harabago's point clearer (since I think it is a little tricky). Imagine 9 people in line. Each person takes 1m to checkout except the first guy takes 10m. With three lines it looks like this (these are their wait times before being serviced):

   0   0   0  (first person in each line has no wait time)
   10  1   1
   11  2   2
If you sum up the total wait times you get: 27m

Now do this with a single file line with three cashiers:

   0   (first three people have no wait time)
   1   (only two people get processed at a time now)
What you see is that one guy basically blocked one of the cashiers for the whole time, but the other two cashiers could continue to process. The total wait time: 12m

Change the numbers and you can create different factors for which the single file line is more efficient.

EDIT: Made a typo the first time on the wait times for the 3-line scenario. The wait time is actually 27m, not 25m.

Good point, well made. In reality, the situation in your example of a multi-line queue is not usually as dire as your example portrays, because the delayed people in queue #1 are likely to jump ship sometime after the other two queues. have cleared. Nonetheless, this queue-jumping behaviour confuses the circulation pattern and causes congestion in the vicinity of the tills, which itself slows down the throughput. There's no doubt that a single-file call-forward queue is more efficient for both the customers and the shop.

One point I didn't see made in the article: single-file queues are also a fair amount more space-efficient, which has value to retailer that is separate from the issue of throughput. This spatial opportunity cost is something that also needs to be considered when designing a queuing system.

I've seen subtle & sophisticated studies which do say that customers prefer multi-line queues to single-line queues, but I rarely see any that bring the other factors into play. Retailers really should base their decisions on the following formula:

average revenue per customer * (% improved customer throuhgput - % of customers you'll lose because of multi-line queues) + extra retail m^2 * average revenue per m^2

In most cases, you'll find that that the value of a single-line queue is a good deal greater than the value of a multi-line queue. So this is one of those cases where it's likely a good idea to not cater to customer preferences.

(I'll also note that single-line queues are much more common here in the UK than in the US; I've become quite accustomed to them and in fact dread multi-line queues and the inevitable idiots that I get stuck behind in them. It seems likely to me that a large part of the American aversion to them is simply a bias against the unfamiliar; this is likely to subside as they become more accustomed to it.)

The problem with your first example is that in real life the queues will rebalance. The two people behind the first guy won't just stand there for 10 minutes with the other two checkouts empty; they'll switch lines.

If they do that, they'll each wait for 3 minutes, giving the same distribution as in the single line.

Ah, you say, but what if other people have entered those lines already? Then you have to count their wait times too, which will be shorter in the three-line case than the one-line case.

Using one line doesn't reduce the mean wait time; it's always the number of people waiting divided by the throughput. What it reduces is the variance in wait times, making the system more fair.

Sure, if the line perfectly rebalances then three lines is almost identical to the single line.

BUT as I'm sure you know, it's sometimes hard to know when to move. Is it after you've waited one minute, then hop to the back of another line?

Let me give you a concrete example: Imagine you enter a line with 15 people in it. Your line moves 14 people through perfectly. You're next, but the guy in front of you takes longer -- maybe he can't make up his mind about wanting some bubble gum. Do you hop to the back of another line and wait 15 more minutes (because the average queue length is 15m) or do you wait it out while this guy in front of you goes? How long will this guy take? 1 more minute or 30 minutes?

And of course, once you hop to the back of another line, the guy from your previous line finishes, and there's someone else in your new line who takes forever. Then you're even more upset that you switched lines!! :-)

With a single line you remove the need for an oracle, which you need for the n-line scenario.

To add to your examples, there's also the case that you've already unloaded your cart, but the idiot in front of you sends the cashier on a wild goose chase to get cigarettes for him and they spend ten minutes sorting that out. Or you're behind some "extreme couponer" who splits their order into six separate orders to maximize their coupon savings, and you have to resist the urge to just pay for their entire order just to shame them into being less of a goddamn miser.

And then you CAN'T leave the slow line because there are people boxing you in from behind, even though you chose this line because the guy ahead of you had only one item... until he decided to make the cashier search the entire store to make sure they were actually out of his favorite cigarettes.

Perfect. You've even touched on the sunk cost fallacy which plays into one's mind in a slow line like you've described.

This is theoretically appealing but the data does not always back it up: http://blog.mrmeyer.com/?p=4646

Even if the overall mean time ends up being the same, you are reducing variance, making wait times more predictable.

There is a good amount of psychological research on waiting, and people in lines are much happier if certain things can be relied on. One of these things is fairness, as in, my wait time should be as long as everyone else's. Another thing is knowing how long the wait will be, which reduces anxiety over the wait. Single queue feeders enable those two things to happen much better than multiple queues. So even if the math ends up being the same either way, the customer will likely be happier with the single queue.


Because when you pick a line you don't know which line will go the fastest ahead of time. Neither do others on average, so everyone ends up spending more time.

I was at a Home Depot this summer in the garden section, 2 checkouts. I was straddling the middle, waiting for the next open lane. Some lady starts bumping into me with a large cart, pushing her way up my right. I looked at her with a frown, and she told me to pick a line. I told her I was 'next' and she scoffed and went into the right lane, and was serviced more quickly (but only randomly)

These little mental models of efficiency always make the nervous introvert in me worry that I am wrong, or if society in general publishes people who try something different.

The naive answer is to avoid retail interactions.

The clever answer is to stop worrying about the loss/gain of an insignificant couple of minutes and to use the time for introspection, problem solving, daydreaming, or whatever else it is you like to do in the comfort of your own skull. Although, for many here, that probably includes "worrying about queueing theory" so maybe my point is moot.

I would agree with you even if I came up in line behind you.

But I would fully expect the majority to find fault in it. And reasonably so. The system is in place and it is multiple queues. The consequence of bucking the system is, at its most polite, a sneer and a scoff.

Leading left hand turns at a vehicular intersection may be the wiser alternative, but to flout a trailing left hand turn and jump through at the green is dangerous, rude and illegal.

What I didn't see in this article is why retailers don't do this today. I see a lot of positives listed and no negatives, so it seems like a no-brainer, right? Yet the biggest retailers like Walmart and Target have tons of lanes, and even do staggered front/back lanes which are terrible for the customers. Is it because there are negative feelings to seeing a long line, and that people do not expect it to be fast so they abandon their purchase?

There are many pros and cons other than just time-efficiency in a store.

Spatially, its actually quite complex to make one long line (it will probably have to snake around your store, and you'll need those awful movable tape barriers everywhere to make sure everyone keeps in line - customers hate these) and then to make one long line split evenly into several end points is not easy either (doing this may also take up a lot of valuable floor space).

Also, you could just have a store layout inherited from the 60s and its too expensive to change it right now...

Some places do this. Fry's Electronics, for example. It works fine. Some supermarkets I've been in do this for their express lines ("10 items or less").

Oh, and airline ticket counters are routinely run this way.

Add to this, Fry's also stacks the "wait line" area with lots of high-margin low-cost goodies like candies and trinkets. I myself have succumbed to grabbing some trail mix or a thumbdrive while waiting there.

I always figured it was because of the layout problem of getting many cashier stations clustered together at the end of a long queue area. I hadn't thought about the psychological effect of a single long line though.

Illusion of choice.

Well no. There's no illusion to it. Customers do get a choice. Of course, the important question is how much that choice gets them.

It's being rolled out slowly. Target in Emeryville has a rather advanced queuing system like this, but customers definitely don't like it and don't necessarily realize it's faster, perhaps because Target has less cashiers as a result of the decreased wait.

Edit: Yelp says this line system has been eliminated. http://www.yelp.com/biz/target-emeryville-2

I went through that system a few times. They had a set of three lines (A,B,C) that fed a bank of cashiers; a screen overhead flashed instructions like "A => cashier 7", then "B => cashier 5" and then "C => cashier 1".

It felt more stressful, efficiency be damned. You spend more time at the "front" of your line (A,B,C) , waiting for the board to change. In a traditional system you can hook in behind someone and "zone out" / chat with your SO until you reach the register. In this system I felt like I had to pay attention the whole time and I was interrupted every time the bell rang, even if it was A's turn and I was in line C.

Yes, you're right. The first time I did it I actually did zone out and had basically no idea what was going on. I think I missed my turn and eventually accidentally brazenly walked up to a cashier that probably wasn't assigned to me. The second time I did it I was more appropriately stressed and obedient.

Actually, the article did mention one strike against using one line (albeit briefly):

And they prefer to choose their own line rather than wait in a single-file line for the next available register—even though that set-up has proven to be faster, research on queuing shows.

In the UK, Tesco and other grocery retailers do this. I've seen this in place in the USA at the Whole Foods at Columbus Circle (an enormously crowded store that moves along well).

Based on these data points, it would seem as though more crowded places use this optimization.

Lund's (a snooty high-end grocery chain in Minneapolis) set up their new store in Old St Anthony (a fairly high-density area) this way too.

Besides the other reasons, retailers have incentives to keep you in the store as long as possible without you getting so annoyed you won't come back, especially near the checkout where they put their most shiny things out for you to impulse buy.

It becomes even more obvious if you think of it like scheduling processes on a CPU. Why needlessly set CPU affinity and only run on a single CPU when you could just take the next available timeslice on any CPU?

Except there are reasons for CPU affinity, such as the cache.

That doesn't mean every process should set affinity to a single CPU when it first starts, particularly in a batch-processing run-to-completion system.

> Why needlessly set CPU affinity

There are practical reasons to do that. That is common in realtime systems. Trying to isolate the cpu for a particular process. So that is available faster when that process needs it. You could also have n-realtime processes. You don't want them competing for the same CPU if you know ahead of time you can allocate a CPU for each one of them.

Another reason is caching. For example you can assign a CPU to process network interrupt requests from a particular network device. Then you might or might not want to also assign the process that consumes that data to that CPU.

CPU affinity certainly has a useful purpose; however, I said "needlessly". As in, what if every process on your system selected a CPU when it started, and just waited for that CPU, to the point of leaving other CPUs idle or underutilized? And what happens when you get stuck behind a process which requires a huge pile of CPU resources? The problem becomes even worse with batch processing: every process must run to completion before the next one for that CPU can run.

In a typical real-time system you don't have to deal with random processes screwing things up. Resources are meticulously allocated to individual tasks, and the tasks aren't allowed to randomly grab resources in the scenario you describe. It all has to be planned out in advance.

Okay, I am confused.

Assuming rebalancing, it seems to me that your wait time EV is the same either way, with less variance in the single queue case. Thus the shopper throughput should remain the same. Can someone explain to me if/why this is wrong?

Also, where did the HN title come from? I could not find that claim in the article.


The author writes about a Little's Law

It also has an engineering analogy in Apache Passenger Global queuing. And this article explains why it works the way it does http://blog.phusion.nl/2008/10/29/phusion-passenger-now-with...

As an aside: The Fry's Electronics store in my city does this and the line does move at a pretty brisk pace, but I had always thought it a rather odd setup till I read this and made the connection to global queuing in Passenger. fascinating.

The Fry's system also gives them a 1/4 mile (ok maybe that's an exaggeration) of opportunity to sell you impulse purchases.

There's interesting work on queuing theory. In practice, each shopper picks the queue that she thinks is least loaded. How many queue lengths do you need to sample? It turns out that if you sample just two queue lengths, you get a huge benefit (in terms of reducing the avg queue length), but not so much if you sample more.

See "Power of two random choices": http://www.eecs.harvard.edu/~michaelm/postscripts/handbook20...

EDIT: link

It's not a matter of logic.

When there is one cashier and a dozen customers waiting, that tells me the store is too cheap or too mismanaged to have other cashiers scheduled.

The best thing a store can do for customer relations is to open additional registers when too many customers are waiting, it implies the customer's time is important.

I also enjoy discovering it was the store manager themselves running the extra register - it means they stay in touch with how things are done (and how hard the cashiers have to work).

Yes, but that's not the point. How do you allocate the extra cashiers? Do they just take customers one by one from the existing queue, or do they split the queue awkwardly and encourage customers to form additional queues?

Parent point is that once you have a nontrivial queue, very already lost, so it doesn't matter which style is faster.

There are two Trader Joe's near me. One does a single line and the others have one for each cashier. I never go to the one with multiple lines. I hate it. The big, huge like that goes to the back of the store for the one with a single line.... I love it. I moves fast and I don't need to worry about picking a line. Even if it went just as fast as the other type, I'd prefer it, but now there's reason to love it even more.

When I went out for fast food as a kid with my grandfather (an engineer), he would send me and my brother and sister to each stand in one line. He would then come over to join whomever got to the front first. That was my first lesson in queueing theory ...

How many times have you been standing in a queue with the money in your hand, wishing you could just drop the money and get out, who cares about change, you just want to get the hell out of here.

This is my proposal for a "no change given" line.

You walk up, you plop down at least the amount of money that the items are worth, they quickly scan the <5 items, check the money is at least as much as the total, then you move on. You don't get change, you don't get a receipt, they don't take cards. Just drop the money and run.

Good for business as they would collect many extra $$ from impatient shoppers, and good for shoppers who are impatient. All-round good.

This always seems intuitive to me. You see a single queue feeding multiple processors fairly often such as in banks and security queues at airports. They seem "fairer" to me as you are not disadvantaged by picking the "wrong" queue through a bad prediction. In a classic supermarket queuing scenario, you could pick the shortest queue but find that the person in front is incredibly slow, so the three people who came to checkout after you at other checkouts progress through the process faster. This is first come, first served.

So at least there's one thing that most big banks get right.

I first encountered this in non-banks at Fry's Electronics over a decade ago. It struck me as odd initially, but I quickly realized how much more efficient it was and began to prefer it -- especially when I ended up stuck behind a 10 minute checkout in which the person insisted on paying with a cheque.

It's really important at Fry's, when often as not you just get an empty box or a piece of paper saying "Give this man a monitor" and they have to send somebody out across the store to actually pick up your item. Or when you bring out your government purchasing card and they don't believe it's real, so you have to stand there for an hour while they try and figure it out (true story).

Immigration lines at various international airports do a remarkably good job at this.

With the exception of JFK.

Chapters also does this (here in Canada anyway).

The Wholefoods in NYC at TimeWarner does this. While Wholefoods in California doesn't.

All the wholefoods in NYC (that I've been to anyway) have done this. You know the voice that tells you which register to go to? That guy used to work (maybe still does?) at the one on 7th and 24th, and his job was to direct people to check outs.

He was replaced with an LCD screen and a speaker.

This is not new, search for "MM1 queue" and you will get a lot of mathemathical results explaining why this effect happens. Is a study case of queueing models.

The article cites Apple's roving check out approach as an attempt to "solve line issues". Isn't this close to the most inefficient way to organize the checkout/queuing experience in terms of creating uncertainty and the need for everyone (even their staff) to move around? I can see that it has a lot of psychological value, though.

Another change: As soon as there are three or more people waiting in a line, the retailer deploys "line busters," employees who scan items in shoppers' carts before they reach the cashier, says Mr. Carey, who works closely with the retailer's operations team on line speed.

This isn't really news. WalMart's been doing this forever.

When I interviewed for a PM job, one of my full hours was spent being asked to design a better checkout system for a grocery store, and show the math around how many registers were needed to ensure a certain maximum wait on line. It was definitely an interesting case study to use.

The parallel vs serial queuing problem is very well established within the operations research community.

And, IIRC, it's not that there's much impact to average performance, but rather that the variation (sigma) drops by a factor of n.

I love studies like these. But I have a real problem trying to read it, the screen was so crowded. Does anyone knows a firefox extension that gives me only the text?

Back in 1989 as one of our projects in a data structures course, we solved this problem and reached the same conclusions. We did it using Pascal!

There are other factors which aren't typically considered. The latency of someone walking from the head of the single queue to the cashier each time matters, especially if the person at the front isn't alert or is confused by trying to figure out which till to go to. People are smart enough to pick short queues to join and there is no latency. Also psychology, nobody wants to join a long queue even if it moves fast, they go to another store.

which is exactly how the queue design on the ck scheduler is, people == tasks ofcourse...

Remarkably similar in design to hyper-threading. Lol!

any first year CS student who's done queueing theory knows that SQMS is more efficient than MQMS and SQSS

More time efficient: avoid ever being in a queue. Think Amazon, or, in meatspace go shopping at odd hours.

Applications are open for YC Winter 2018

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact