6 ms·

FYI: 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

by pnathan 15y ago

FYI: 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 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).
- tomkarlo 15y 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.
- philwelch 15y 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.
  - wisty 15y ago
    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.
  - nik_0_0 15y ago
    Do you have a source for that Coinstar playing jangly coin sounds?? I would love to read more about that.
    - philwelch 15y ago
      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 http://news.ycombinator.com/item?id=2007818
    - JamesAn 15y ago
      "Counting 600 coins per minute, Coinstar machines detect the metal content of the coin, as well as the size to accurately identify the coin denomination - and efficiently sort out all kinds of debris typically found in consumer coin. The company has found paper clips, key chains, wedding bands, gum wrappers, even teeth, all of which are identified quickly as non-coin." http://web.archive.org/web/20100324183932/http://www.coinstar.com/US/WebDocs/A3-2-2 http://web.archive.org/web/20100324183932/http://www.coinsta...
  - lywald 15y ago
    It's obvious that one line is faster? Well it's not. Considering all cashiers are busy all the time, if it could be faster that would mean they have to manage multiple customers at the same time... If you're in the top 50% skilled at finding a line, then you're penalized because it just averages the queuing time.
  - cynicalkane 15y ago
    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?
- cheald 15y 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.
  - prodigal_erik 15y ago
    When I have to choose a line I find myself harshly judging the people around me, because every difference can impose a cost in boredom and lost leisure time. "This guy's old and worn out. They seem kind of foreign, won't understand the cashier. That one looks poor, probably uses a lot of coupons and argues about what's discounted. They're paying all their attention to their kid instead of getting out of everyone's way." It may be the most socially corrosive thing I routinely do. Edit: and I think I just convinced myself to get a smartphone (I'm reluctant to bring a paperback, it might look like shoplifting because they sell those).
    - hn_reader 15y ago
      Indeed, since I got a smartphone I no longer dread long lines in supermarkets, etc. Just more time to read HN.
  - AndyNemmity 15y ago
    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.
    - mc32 15y ago
      --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.
- mahyarm 15y 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.
- deleted 15y ago
  [deleted]
- Semiapies 15y 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 15y ago
  Stores are focused on individual wait times, not on total throughput.
- deleted 15y ago
  [deleted]
- malvim 15y 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 15y 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 15y ago
  I'd also recommend some of the books by Neil Gunther at http://www.perfdynamics.com/ 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 15y 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 15y 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 15y 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
- gujk 15y ago
  Because no one can spell queuology or queuistics.
- JonnieCache 15y ago
  It's a common enough construction. Quantum theory, set theory and so on.
  - lightcatcher 15y ago
    Realize this is a worthless comment, but I couldn't stand the exclusion of graph theory.
    - JonnieCache 15y ago
      How could I forget chaos theory and string theory.
Avenger42 15y 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/queueing-theory-in-action-plus-frogs.aspx http://blogs.msdn.com/b/ericlippert/archive/2009/08/20/queue...

by pnathan 15y ago

rdtsc 15y 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).

tomkarlo 15y 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.
philwelch 15y 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.
- wisty 15y ago
  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.
- nik_0_0 15y ago
  Do you have a source for that Coinstar playing jangly coin sounds?? I would love to read more about that.
  - philwelch 15y ago
    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 http://news.ycombinator.com/item?id=2007818
  - JamesAn 15y ago
    "Counting 600 coins per minute, Coinstar machines detect the metal content of the coin, as well as the size to accurately identify the coin denomination - and efficiently sort out all kinds of debris typically found in consumer coin. The company has found paper clips, key chains, wedding bands, gum wrappers, even teeth, all of which are identified quickly as non-coin." http://web.archive.org/web/20100324183932/http://www.coinstar.com/US/WebDocs/A3-2-2 http://web.archive.org/web/20100324183932/http://www.coinsta...
- lywald 15y ago
  It's obvious that one line is faster? Well it's not. Considering all cashiers are busy all the time, if it could be faster that would mean they have to manage multiple customers at the same time... If you're in the top 50% skilled at finding a line, then you're penalized because it just averages the queuing time.
- cynicalkane 15y ago
  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?
cheald 15y 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.
- prodigal_erik 15y ago
  When I have to choose a line I find myself harshly judging the people around me, because every difference can impose a cost in boredom and lost leisure time. "This guy's old and worn out. They seem kind of foreign, won't understand the cashier. That one looks poor, probably uses a lot of coupons and argues about what's discounted. They're paying all their attention to their kid instead of getting out of everyone's way." It may be the most socially corrosive thing I routinely do. Edit: and I think I just convinced myself to get a smartphone (I'm reluctant to bring a paperback, it might look like shoplifting because they sell those).
  - hn_reader 15y ago
    Indeed, since I got a smartphone I no longer dread long lines in supermarkets, etc. Just more time to read HN.
- AndyNemmity 15y ago
  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.
  - mc32 15y ago
    --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.
mahyarm 15y 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.
deleted 15y ago
[deleted]
Semiapies 15y 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 15y ago
Stores are focused on individual wait times, not on total throughput.
deleted 15y ago
[deleted]
malvim 15y 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 15y 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 15y ago
I'd also recommend some of the books by Neil Gunther at http://www.perfdynamics.com/ 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 15y 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 15y 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 15y 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

gujk 15y ago
Because no one can spell queuology or queuistics.
JonnieCache 15y ago
It's a common enough construction. Quantum theory, set theory and so on.
- lightcatcher 15y ago
  Realize this is a worthless comment, but I couldn't stand the exclusion of graph theory.
  - JonnieCache 15y ago
    How could I forget chaos theory and string theory.

Avenger42 15y 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/queueing-theory-in-action-plus-frogs.aspx http://blogs.msdn.com/b/ericlippert/archive/2009/08/20/queue...