Hacker News Reader

Comment by jfb | Hacker News Reader

I've largely given up trying to optimize my shopping time, but I do find the subject interesting. I'd be interested in seeing the effect of the (to me intuitively superior) one line, many cashiers setup, like at Fry's. I realize supermarkets make a boatload of cash from the geegaws sold in line that you hounded your parents into buying you as a kid, but I can't help but think that the many lines/many cashiers setup is less an optimal setup and more an artifact of some Lionel Hutz type who sold the cabal of Evil Grocery Barons a bag of magic beans in the 1960's.

As usual, I am too lazy to go look it up for myself. Back to hacking.

View on HN

One queue minimizes the average wait time - it's the fairest and fastest system. Any CS person should know this, it's pretty basic.

Say we have 100 people and 10 servers. Everyone takes 1 minute to process, except one guy who needs 10 minutes.

With 10 queues and the long taking guy ahead of 9 other people he's blocking all those for 10 minutes. Total processing time 19 minutes. With 1 queue and the long taking guy first (blocking 1 counter for 10 minutes) total processing time is 11 Minutes.

Another way to look at it is that with one queue, everyone gets the minimum possible wait time. In the many queues case you get that only occasionally. You could optimize the many queues so they're just as efficient as the one single queue but you'd have to know everyone's processing time in advance - impossible in a real world setting.

One queue adds an overhead for the time it takes for the person at the front of the queue to notice a cashier is free and walk to that cashier. I have watched this system in action at the Post Office, Rail stations, and one supermarket and this overhead can be significant. One supermarket actually employs somebody at the head of the queue just to tell them which cashier to go to and when.

jfb - It also doesn't have any negative effect on "the geegaws sold in line" as they just put the "geegaw" displays along the side of the one queue. In fact it is better for the store in that respect as they can show more variety.

The best way I can think of to get rid of this overhead is to have a rule where each cashier has a queue depth 2 that is fed from a single queue. But how would you get people to stick to just 2 people? And it would be very annoying to be just behind a slow person.

In theory people should naturaly start moving forward when they notice that somebody is finishing up but at least in the Rail station and Post office the counter staff have a tendency to shut their counter without warning or start processing some other task before they are ready to serve the next person.

Whole Foods in NYC has solved this problem by having one queue, but when you get towards the front, there are five separate, color-coded lines. At the front of the queue is a giant television that shows a bar of color for each lane. When a register opens up, the number for that register slides into the color bar for the next person in the sequence, and a voice announces "Register 12". It's fairly efficient at keeping the queue moving as well as managing people's psychological need for multiple lines. It also prevents cashiers from wasting time, because as soon as a transaction is finished, their register is automatically assigned to the next person in the queue. The only "wasted" time is the time walking from queue to register, and pleasantries.

I've seen the two level queue in use at some airports for security and immigration. But they do have a person splitting the head of the long queue into the short queues immediately in front of each x-ray machine/agent.

It works pretty well, but can still be a little frustrating when you see a person who was behind you in the main queue get through first because your sub-queue took longer.

People usually won't act to optimize for the best throughput, just minimize their relative wait times. The behaviour of drivers on congested roads tends to confirm this.

It's always the fastest, but whether or not it's the fairest depends on how you define "fair." The simplest example I can use to illustrate this is the case where there is 1 server, and 2 people. One person will take 60 minutes to process, and the other, 1 minute. The 60 minute person gets in line a millisecond before the 1 minute person. Is it fair for the person who will take 1 minute to wait for the slow 60 minute guy?

If you define fairness as the average user-wait, I think fastest first is actually optimal. This is still the case with one-queue systems: If you let the 10-minute person go first, you'll have blocked 1/10th of throughput for everyone behind him, and thus increase their wait time. Fastest job first is generally not a bad way to handle queues; it works great for things where "jobs completed per unit of time" is of importance, like chores or fixing bugs (of equal or similar priority).

Besides average user-wait, you could start inventing your own units for fairness depending on the problem. Maybe its average user-wait per processing minute, or something like that, in which case the solution might be more complicated (or might not be, I'm not too concerned with it).

The fairest and most useful thing to do then seems to be to train everyone at the checkout counter to be fast. Pass a minimum serving speed threshold before you can serve the main counters.

One queue is fairest. From your example if there is only one server then there is no difference between one queue/one queue per server.

You could optimize the many queues so they're just as efficient as the one single queue but you'd have to know everyone's processing time in advance - impossible in a real world setting.

Not quite impossible. You might not know individually, but on average for a group or segment you could get this information and optimize. Banks can do this by splitting consumer and merchant lines. Merchants typically take longer (who knows by how much), and get their own queue.

With this system, you have 2 queues, 1 for each group. There may be a lot of variation within each group, but the averages work out. Consumers wait the average minimum processing time for the consumer group, and merchant wait the average processing time for the merchant group.

This still leaves room for underutilization. What if the merchant line is backed up and the consumer line is empty? Ideally, the extra tellers would work to pick up the slack, but if this isn't possible then it's still not an ideal system.

Another common example would be airport check-in. You have economy and first-class.

Often the first-class line is empty - do you let 'the rabble' check-in there and risk a first class passenger having to (gasp) wait a couple of minutes behind them; or make the long line of economy passengers stare at the unused desk and mutter about the airline.

(Though given that airports are really just a series of queues feeding each other the different in practice is pretty minimal.)

I think you would be able to reduce the total time on your 10-queue example if you factor in/allow jockeying.

Fry's wraps their mono-line with geegaw displays as well (usually electronics consumer geegaws, but it could be adapted to candy and trashy magazines). A cynic might wonder if they might actually want to maximize wait time, but I imagine it is, as someone points out below, a question of space limitations (carts require lots of space to navigate a rope maze). I note that the self-service stations slowly taking over the mega-grocery stores here employ a mono-line protocol. But, I find these inconvenient unless I only get a small number of items, which, of course, would require me to make more frequent trips, nulling out any possible time savings).

Grocery delivery would seem the only way out.

Commissaries on U.S. military bases use a one line multi-cashier setup, yet each cashier has a bunch of novelty items near their section. I seem to remember that setup be a little bit faster too, though it's not immediately apparent when standing in line.

The problem is the limited resource of space. One line, multiple cashiers takes up more space than several cashiers, one line. The store needs to add the queue system and have a person standing at the front to make sure the line moves smoothly. Think about that large waiting area Fry's has.

Another point is that 6 people standing on a single line for 2 cashiers seems like a longer wait than 3 people standing on two lines.

I cant easily look it up myself right now (am on a mobile device) but I believe that the many cashiers many lines approach is faster from an average wait time perspective. However people tend to prefer the many cashiers one line approach because it instills a sense of fairness (first come first served).

From what I recall of queuing theory that's not actually correct. From wikipedia:

"One observational insight provided by comparing queuing models is that a single queue with multiple servers performs better than each server having their own queue and that a single large pool of servers performs better than two or more smaller pools, even though there are the same total number of servers in the system"

http://en.wikipedia.org/wiki/Queueing_model#Multiple-servers...

It seems you're correct. A quick search is giving me nothing to disagree with you.

That being said: My understanding was that the many-line system worked better primarily because of the potential for a lot of lost time between the server saying "Can I help whose next" and the order actually starting. This time is obviously hugely dependent on factors such as floor layout, space around the registers, customers familiarity with the system, etc. The idea was that if you have one line for multiple registers (a la Wendy's) than when the second register opened up the next customer in line had to notice, go to the register, probably walk around the person ordering at the first register, and then start ordering. Whereas in the multi-line system (a la McDonald's) the next customer in line will likely be focusing on the register in front of them ready to take the one step forward when their time comes. These factors can certainly be minimized but in stores that are busy/crowded/not well laid out it they can make a noticeable difference. That's my $.02 anyways.

Reply on news.ycombinator.com