10 ms·
A single line to 3 cashiers is ~3x faster than a separate line for each cashier
- URSpider94 15y agoWhen 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 ...
- blakehill 15y agoSo at least there's one thing that most big banks get right.
- DTanner 15y agoChapters also does this (here in Canada anyway).
- gdilla 15y agoThe Wholefoods in NYC at TimeWarner does this. While Wholefoods in California doesn't.
- aplusbi 15y agoAll 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.
- robflynn 15y agoI 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.
- jff 15y agoIt'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 15y agoImmigration lines at various international airports do a remarkably good job at this.
- jonnii 15y agoWith the exception of JFK.
- parfe 15y agohttp://en.wikipedia.org/wiki/Little%27s_law http://en.wikipedia.org/wiki/Little%27s_law The author writes about a Little's Law
- bryanh 15y agoAn excellent video on the phenomenon from the "Engineer Guy" series: http://www.youtube.com/watch?v=F5Ri_HhziI0 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 15y agoI love his videos. I wish he would make more. The harddrive one was interesting.
- deleted 15y ago[deleted]
- smackfu 15y agoWouldn'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 15y agoNo, 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.
- kenjackson 15y agoHere'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.
- ScottBurson 15y agoThe 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.
- nlawalker 15y agoMost 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.
- smackfu 15y agoAround 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 15y agoAs 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 15y ago
- digitalsushi 15y agoI 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.
- JonnieCache 15y agoThe 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.
- tgrass 15y agoI 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.
- JoshTriplett 15y agoIt 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?
- jff 15y agoExcept there are reasons for CPU affinity, such as the cache.
- JoshTriplett 15y agoThat 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.
- rdtsc 15y 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.
- JoshTriplett 15y agoCPU 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.
- 15y ago
- deleted 15y ago[deleted]
- santimt 15y agoThis 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 15y agoFYI: This is an example of the branch of mathematics called queueing theory. http://en.wikipedia.org/wiki/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.
- rdtsc 15y agoNot 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).
- tomkarlo 15y agoStores 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.
- philwelch 15y agoIt'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.
- smackfu 15y agoWhat 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 15y agoIllusion of choice.
- j_baker 15y agoWell 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 15y agoI 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 15y agoThere 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...
- ScottBurson 15y agoSome 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.
- trustfundbaby 15y agoIt 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-global-queuing/ 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 15y agoThe Fry's system also gives them a 1/4 mile (ok maybe that's an exaggeration) of opportunity to sell you impulse purchases.
- signa11 15y agowhich is exactly how the queue design on the ck scheduler is, people == tasks ofcourse...
- buckwild 15y agoRemarkably similar in design to hyper-threading. Lol!
- xtacy 15y agoThere'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/handbook2001.pdf http://www.eecs.harvard.edu/~michaelm/postscripts/handbook20... EDIT: link
- e40 15y agoThere 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 15y agoA 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).
- tomkarlo 15y agoHaving 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.
- finnw 15y agoHaving 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 15y agoIt'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).
- philwelch 15y agoYes, 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?
- gujk 15y agoParent point is that once you have a nontrivial queue, very already lost, so it doesn't matter which style is faster.
- joezydeco 15y agoThe 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.
- deleted 15y ago[deleted]
- dxbydt 15y agoscala> 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.
- deleted 15y ago[deleted]
- MaysonL 15y agoBut 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.
- dxbydt 15y 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 http://people.brunel.ac.uk/~mastjjb/jeb/or/queue.html
- alsocasey 15y agoIsn'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?
- j_baker 15y agoAnother 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.
- tomkarlo 15y agoWhen 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 15y agoBack 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 15y agoThere 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 15y agoMore time efficient: avoid ever being in a queue. Think Amazon, or, in meatspace go shopping at odd hours.
- bluesmoon 15y agoany first year CS student who's done queueing theory knows that SQMS is more efficient than MQMS and SQSS
- seiwyn 15y agoOkay, 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 15y agoThe 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 15y agoThe 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 15y agoI 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 15y agoThis 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 15y agoHow 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.
- donnawarellp 15y agopeople like me that have been in telecom for 30+ year are amazed that this garnered 146 comments. Erlang-C, no not the language Erlang, before that...