FIFOs in the Real World

Introduction

Chances are you spend time waiting in line almost every day. Lines are everywhere: in the supermarket, in front of the vending machine, before the ticket booth, etc. Often, there are multiple lines to chose from. Most people pick the one they think will lead to the shortest waiting time, usually the one that has fewest people in it. It's generally considered a Good Thing if people are served in the order in which they arrive (known in computer science as First In First Out, FIFO). In this essay, I propose a queuing system that has this property.

The Present Situation

People don't really like waiting. They had rather be served immediately when they arrive. However, this would require a far larger nunber of cash registers, vending machines, and other things that people queue before than is economically feasible. When it comes to it, many people even prefer to wait a little longer and have cheaper products than to pay extra for quick service. So, waiting lines are a Good Thing.

What is not good about lines is that there is frequently more than one to chose from, and you don't know in advance which one will lead you to wait shortest. It is frustrating when somebody who enters a line after you gets served before you. Yet, this is unavoidable. You never know if that man in front of you is going to need a long time to find his wallet. Or if that girl is going to spend a long time deciding which kind of coffee she will get this time.

One Line to Rule them All

The whole problem of chosing lines disappears when there is only one of them. Of course, everybody lining up in front of the same machine or counter is not going to get anyone helped quicker. What does help, though, is having one line for all machines or counters together. Newcomers join at the end, and whenever a counter or machine becomes available, the person at the front is served there. Customers are served in the order they arrive, and nobody waits longer than necessary, because they chose the wrong line.

Of course, fair queueing (customers are served depending on arrival time and time to serve) would still be better, but I have yet to devise an algorithm to accurately predict serving time.