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

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

#121

Post by alsocasey » Thu, Dec 08, 2011, 8:37 PM UTC

gujk wrote: post #113

alsocasey wrote: post #108

Earlier quoted context omitted.

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.

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.

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

#122

Post by gujk » Thu, Dec 08, 2011, 8:41 PM UTC

philwelch wrote: post #81

ck2 wrote: post #65

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…

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.

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

#123

Post by bluesmoon » Thu, Dec 08, 2011, 8:43 PM UTC

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

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

#124

Post by Muzza » Thu, Dec 08, 2011, 8:43 PM UTC

JadeNB wrote: post #91

Muzza wrote: post #31

Earlier quoted context omitted.

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 de…

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

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

#125

Post by dxbydt » Thu, Dec 08, 2011, 8:48 PM UTC

narkee wrote: post #115

dxbydt wrote: post #79

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…

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…

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.

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

#126

Post by lywald » Thu, Dec 08, 2011, 8:54 PM UTC

philwelch wrote: post #73

rdtsc wrote: post #43

Earlier quoted context omitted.

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 appe…

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…

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.

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

#127

Post by Avenger42 » Thu, Dec 08, 2011, 9:01 PM UTC

pnathan wrote: post #27

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.

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

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

#128

Post by Semiapies » Thu, Dec 08, 2011, 9:02 PM UTC

cheald wrote: post #74

rdtsc wrote: post #43

Earlier quoted context omitted.

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 appe…

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…

Best Buy has been doing that, too.

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

#129

Post by Semiapies » Thu, Dec 08, 2011, 9:08 PM UTC

rdtsc wrote: post #43

pnathan wrote: post #27

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.

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 appe…

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.

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

#130

Post by mattmcknight » Thu, Dec 08, 2011, 9:14 PM UTC

nhebb wrote: post #97

cheald wrote: post #74

Earlier quoted context omitted.

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…

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.