What property of queuing systems does 'first-come-first-served' maximize?

'First come, first served' is a very very common way of organizing access to a limited resource or service in the real world. It can be explained by saying that whenever the resource is available the person who has been waiting the longest is served, and visualized by thinking of people standing in a single-file line, where the person at the front is always served next and new arrivals join the back of the queue. If you ask someone why this system is the best, they might instinctively say 'It is the most fair'. But can we express what this fairness means in terms of some property, which is maximized for this system and no other? It doesn't mean for instance that people all wait the same time, or even that people who arrive at nearly the same time don't get served a long time apart. Or does it optimize some other property, such as the incentive to arrive as soon as possible or the incentive not to arrive at busy times? Can we make formal why it should be preferred to other arrangements? Or is it just a human tendency to do something simple/something that most people feel is fair/something we all know?

• optimization
• queueing-theory

2 Answers 2

First-come-first-served ensures that provided that the time between served customers is bounded, any customer who enters the queue will within a worst-case wait time that can be determined based upon the number of preceding customers. Even if the time between customers is bounded only probabilistically, the wait time will still have a reasonable probabilistic bound. For example, if one flips a coin once per second, and each "heads" means someone enters the queue and each "tails" means someone is serviced (unless the queue is empty, in which case nothing happens), someone who enters when there are 39 people ahead of him will know that the time until he is serviced will be the amount of time required for a total of 40 tails to appear. That might or might not happen within 80 seconds, but will likely happen within 90. Although would be possible that the person might have to wait an hour or more, it would be exceptionally improbable. The probability of a person not having been served within a given length of time will rapidly approach zero as the time increases.

Suppose that the same parameters were applied with a LIFO stack. While someone who entered the stack would have a 50% of being served in one second, they'd have a 3/8 chance of not getting served within 3 seconds (as compared with a 1/8 chance if they'd been first in a queue), a 5/16 chance of not getting served in 5 (versus 1/32), and a 35/128 chance of not getting served in 7 (vs 1 in 128). The probability of not getting served within N seconds drops as N increases, but very slowly. One would have roughly a one in nine chance of having to wait a minute, a one in 75 chance of having to wait an hour, and a one in 251 chance of having to wait a week or more.

If one assigns priorities to different items, then other service orders become practical, but behavior modeling is much more apt to focus much more on heuristics than absolute probability calculations.

$\begingroup$ This makes sense is and pretty compelling (including from everyday experience of queues). $\endgroup$

$\begingroup$ @jwg: As I was writing the answer, I found myself trying to remember of the probability of taking longer than N seconds would in fact approach zero as N approaches infinity. I ran out of time to research that, but the probability of having to wait a week is so close to the probability of having to wait a day that I wonder if the probability of ever being served from the stack would approach something like 255/256, and how one would prove that? Of course, with a queue the probability of being served would approach unity. $\endgroup$

$\begingroup$ providing the rate of joining the queue is no greater than the rate of service, the probability of ever being served should tend to 1 as time goes to infinity. This can be worked out with an argument about random walks, and is the same as saying that with an unbiased gambling game (or one which is biased in the casino's favor), you will eventually go bankrupt, no matter how much money you start with. $\endgroup$

$\begingroup$ @jwg: The Wikipedia article on random walks makes clear that a player who has $1 , going against a house which has $N , will have a N/(N+1) probability of going broke before breaking the house, but I didn't see any formulation of the probability of the player going broke within a specified number of rounds. If the player starts with $1 , is there any closed-form calculation for the probability that the player will survive at least N coin flips? If the house has $3 or more, there will be an uncountable number of infinite coin-flip sequences will will never break the player nor the house. $\endgroup$

$\begingroup$ . and while it may be that the ratio of such coin flips sequences to total coin flip sequences is zero, I don't see any obvious reason that must be so. $\endgroup$

Queuing theory is primarily concerned with processes that have variability in arrival of jobs into the system. For example, jobs can be people needing service. The time taken to service these jobs is also generally variable. The result is congestion or waiting line. This can be measured by the average number of jobs in the queue and by the average waiting time of arrivals. There are costs associated with having jobs wait. There are also costs associated with adding more service capacity. Thus, challenge is to balance these costs. Queuing theory may be used to determine the optimum number of, say, serivce windows for a post office, Doctors available for clinic calls, number of clerks for a spare parts counter and so on. It may also be used to aid in decisions about the order in which customers should be processed to aid questions like "should there be an express lane". First in First Out, FIFO is a queuing discipline that is used in Queuing theory because of its modeling convenience. But there may be express or priority service for some jobs; an example is the express lane at many supermarkets for customers with 10 items or less in which case the service may be in random order. FIFO is a modeling convenience.

1) FIFO (First In First Out) also called FCFS (First Come First Serve) - orderly queue.

2) LIFO (Last In First Out) also called LCFS (Last Come First Serve) - stack.

3) SIRO (Serve In Random Order).

4) Priority Queue, that may be viewed as a number of queues for various priorities.

5) Many other more complex queuing methods that typically change the customer’s position in the queue according to the time spent already in the queue, expected service duration, and/or priority. These methods are typical for computer multi-access systems.

Most quantitative parameters (like average queue length, average time spent in the system) do not depend on the queuing discipline. That’s why most models either do not take the queuing discipline into account at all or assume the normal FIFO queue. In fact the only parameter that depends on the queuing discipline is the variance (or standard deviation) of the waiting time. There is this important rule (that may be used for example to verify results of a simulation experiment):

The two extreme values of the waiting time variance are for the FIFO queue (minimum) and the LIFO queue (maximum)