waiting in line: queue structures and wait times

stats Configuration enqueuing rate restart

Here is a simulator of queues that lets you study how different configurations of lines affect overall throughput. It's still a work in progress but I think it's quite interesting to play with.

Of course, everyone likes to go to the shortest line when they have to. But having a setup wherein one line feeds into a large number of small lines can increase throughtput substantially -- because one person holding up a single line will not affect anyone else -- they can just enter another line.

This requires the ability to actually determine which line to enter -- which is not trivial. Large stores such as Whole Foods have complicated queueing systems to tell people where to go. If these aren't followed, and people join lines more randomly, then overall throughput of people and average wait time again increases substantially.

Many non-mathematical factors also affect how people perceive waiting in line. In Paco Underhill's Why We Buy , placement of screens or other distractions near lines is shown to be very effective at reducing the perceived wait time in a line.

These results aren't just limited to retail. If you have a large distributed system performing computations, queueing theory can be applied to ensure that tasks are assigned to the right computers. In frameworks such as MapReduce, queueing and requeueing of jobs is particularly important, since individual computers may die along the way, meaning that tasks have to be efficiently reassigned to other machines.