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.

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.

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

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.

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