Hacker News Reader

Comment by nikster | Hacker News Reader

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.

View on HN

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.

Reply on news.ycombinator.com