A single line to 3 cashiers is ~3x faster than a separate line for each cashier

http://online.wsj.com/article/SB10001424052970204770404577082933921432686.html

by blakehill • 15 years ago

241 163 15 years ago

online.wsj.com

blakehill• 15 years ago

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

DTanner• 15 years ago

Chapters also does this (here in Canada anyway).

gdilla• 15 years ago

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

robflynn• 15 years ago

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.

jff4• 15 years ago

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

orky56• 15 years ago

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

jonnii• 15 years ago

With the exception of JFK.

parfe• 15 years ago

http://en.wikipedia.org/wiki/Little%27s_law

The author writes about a Little's Law

bryanh• 15 years ago

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.

missing_cipher• 15 years ago

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

smackfu4• 15 years ago

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?

hrabago• 15 years ago

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.

kenjackson2• 15 years ago

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)
   0
   0
   1   (only two people get processed at a time now)
   1
   2
   2
   3
   3

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.

tgrass2• 15 years ago

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

jessriedel• 15 years ago

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.

rdtsc3• 15 years ago

Nope.

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.

ssharp• 15 years ago

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.

nlawalker4• 15 years ago

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.

smackfu4• 15 years ago

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

neutronicus• 15 years ago

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.

gwillen• 15 years ago

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.

jff4• 15 years ago

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.

Muzza2• 15 years ago

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.

yesimahuman2• 15 years ago

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.

eiji2• 15 years ago

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.

jrockway• 15 years ago

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.

georgemcbay• 15 years ago

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.

electromagnetic• 15 years ago

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.

ryusage• 15 years ago

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.

nlawalker4• 15 years ago

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.

notatoad• 15 years ago

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.

heliodor• 15 years ago

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.

jacobr• 15 years ago

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.

digitalsushi• 15 years ago

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.

JonnieCache3• 15 years ago

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.

tgrass2• 15 years ago

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.

JoshTriplett3• 15 years ago

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?

jff4• 15 years ago

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

JoshTriplett3• 15 years ago

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.

rdtsc3• 15 years ago

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

JoshTriplett3• 15 years ago

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.

santimt• 15 years ago

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.

pnathan• 15 years ago

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.

rdtsc3• 15 years ago

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

tomkarlo6• 15 years ago

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.

philwelch7• 15 years ago

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.

cheald• 15 years ago

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.

mahyarm• 15 years ago

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.

Semiapies2• 15 years ago

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• 15 years ago

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

malvim• 15 years ago

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

NyxWulf• 15 years ago

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• 15 years ago

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.

guyzero• 15 years ago

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

scott_s• 15 years ago

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.

brown9-2• 15 years ago

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

gujk4• 15 years ago

Because no one can spell queuology or queuistics.

JonnieCache3• 15 years ago

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

Avenger42• 15 years ago

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

smackfu4• 15 years ago

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?

getsat• 15 years ago

Illusion of choice.

j_baker3• 15 years ago

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.

Zaak• 15 years ago

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.

twelvechairs• 15 years ago

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

ScottBurson2• 15 years ago

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.

r00fus• 15 years ago

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.

theorique• 15 years ago

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.

afiler• 15 years ago

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.

rms2• 15 years ago

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

xsmasher• 15 years ago

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.

Jach• 15 years ago

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.

j_baker3• 15 years ago

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.

trustfundbaby• 15 years ago

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.

tlrobinson• 15 years ago

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

signa11• 15 years ago

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

buckwild• 15 years ago

Remarkably similar in design to hyper-threading. Lol!

xtacy• 15 years ago

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

e40• 15 years ago

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.

Splines• 15 years ago

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

tomkarlo6• 15 years ago

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.

finnw2• 15 years ago

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

ck2• 15 years ago

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

philwelch7• 15 years ago

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?

gujk4• 15 years ago

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

joezydeco• 15 years ago

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.

dxbydt6• 15 years ago

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.

MaysonL• 15 years ago

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.

dxbydt6• 15 years ago

>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

alsocasey2• 15 years ago

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?

narkee• 15 years ago

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.

dxbydt6• 15 years ago

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.

andrewla• 15 years ago

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.

hermannj3142• 15 years ago

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.

hermannj3142• 15 years ago

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.

adobriyan• 15 years ago

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

j_baker3• 15 years ago

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.

tomkarlo6• 15 years ago

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.

keithg• 15 years ago

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!

SWengineer• 15 years ago

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.

mkramlich• 15 years ago

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

bluesmoon• 15 years ago

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

seiwyn• 15 years ago

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.

finisterre• 15 years ago

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.

adamgravitis• 15 years ago

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.

dudurocha• 15 years ago

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?

mikecsh• 15 years ago

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.

secoif• 15 years ago

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.

URSpider942• 15 years ago

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

A single line to 3 cashiers is ~3x faster than a separate line for each cashier

Related Stories