Queuing Theory: The Mathematical Study of Waiting in Line (2024)

Science, Tech, Math ›Math

Queuing theory is the mathematical study of queuing, or waiting in lines. Queues contain customers (or “items”) such as people, objects, or information. Queuesform when there are limited resources for providing a service. For example, if there are 5 cash registers in a grocery store, queues will form if more than 5 customers wish to pay for their items at the same time.

A basic queuing system consists of an arrival process (how customers arrive at the queue, how many customers are present in total), the queue itself, the service process for attending to those customers, and departures from the system.

Mathematical queuing models are often used in software and business to determine the best way of using limited resources. Queueing models can answer questions such as: What is the probability that a customer will wait 10 minutes in line? What is the average waiting time per customer?

The following situations are examples of how queueing theory can be applied:

• Waiting in line at a bank or a store
• Waiting for a customer service representative to answer a call after the call has been placed on hold
• Waiting for a train to come
• Waiting for a computer to perform a task or respond
• Waiting for an automated car wash to clean a line of cars

Characterizing a Queuing System

Queuing modelsanalyze how customers (including people, objects, and information) receive a service. A queuing system contains:

• Arrival process. The arrival process is simply how customers arrive. They may come into a queue alone or in groups, and they may arrive at certain intervals or randomly.
• Behavior. Howdo customers behave when they are in line? Some might be willing to wait for their place in the queue; others may become impatient and leave. Yet others might decide to rejoin the queue later, such as when they are put on hold with customer service and decide to call back in hopes of receiving faster service.
• How customers are serviced. This includes the length of time a customer is serviced, the number of servers available to help the customers, whether customers are served one by one or in batches, and the order in which customers are serviced, also called service discipline.
• Service discipline refers to the rule by which the next customer is selected. Although many retail scenariosemploy the “first come, first served” rule, other situations may call for other types of service. For example, customers may be served in order of priority, or based on the number of items they need serviced (such as in an express lane in a grocery store). Sometimes, thelast customer to arrive will be served first (such s in the case in a stack of dirty dishes, where the one on top will be the first to be washed).
• Waiting room. The number of customers allowed to wait in the queue may be limited based on the space available.

Mathematics of Queuing Theory

Kendall’s notation is a shorthand notation that specifies the parameters of a basic queuing model. Kendall’s notation is written in the form A/S/c/B/N/D, where each of the letters stand for different parameters.

• The A term describes when customers arrive at the queue – in particular, the time between arrivals, or interarrival times. Mathematically, this parameter specifies the probability distribution that the interarrival times follow. One common probability distribution used for the A term is the Poisson distribution.
• The S term describes how long it takes for a customer to be serviced after it leaves the queue. Mathematically, this parameter specifies the probability distribution that these service times follow. The Poisson distribution is also commonly used for the S term.
• The c term specifies the number of servers in the queuing system. The model assumes that all servers in the system are identical, so they can all be described by the S term above.
• The B term specifies the total number of items that can be in the system, and includes items that are still in the queue and those that are being serviced. Though many systems in the real world have a limited capacity, the model is easier to analyze if this capacity is considered infinite. Consequently, if the capacity of a system is large enough, the system is commonly assumed to be infinite.
• The N term specifies the total number of potential customers – i.e., the number of customers that could ever enter the queueing system – which may be considered finite or infinite.
• The D term specifies the service discipline of the queuing system, such as first-come-first-served or last-in-first-out.

Little’s law, which was first proven by mathematician John Little, states that the average number of items in a queue can be calculated by multiplying the average rate at which the items arrive in the system by the average amount of time they spend in it.

• In mathematical notation, the Little's law is: L = λW
• L is the average number of items, λ is the average arrival rate of the items in the queuing system, and W is the average amount of time the items spend in the queuing system.
• Little’s law assumes that the system is in a “steady state” – the mathematical variables characterizing the system do not change over time.

Although Little’s law only needs three inputs, it is quite general and can be applied to many queuing systems, regardless of the types of items in the queue or the way items are processed in the queue. Little’s law can be useful in analyzing how a queue has performed over some time, or to quickly gauge how a queue is currently performing.

For example: a shoebox company wants to figure out the average number of shoeboxes that are stored in a warehouse. The company knows that the average arrival rate of the boxes into the warehouse is 1,000 shoeboxes/year, and that the average time they spend in the warehouse is about 3 months, or ¼ of a year. Thus, the average number of shoeboxes in the warehouse is given by (1000 shoeboxes/year) x (¼ year), or 250 shoeboxes.

Key Takeaways

• Queuing theory is the mathematical study of queuing, or waiting in lines.
• Queues contain “customers” such as people, objects, or information. Queues form when there are limited resources for providing a service.
• Queuing theory can be applied to situations ranging fromwaiting in line at the grocery store to waiting for a computer to perform a task. It is often used in software and business applications to determine the best way of using limited resources.
• Kendall’s notation can be used to specify the parameters of a queuing system.
• Little’s law is a simple but general expression that can provide a quick estimate of the average number of items in a queue.

Sources

• Beasley, J. E. “Queuing theory.”
• Boxma, O. J. “Stochastic performance modelling.” 2008.
• Lilja, D. Measuring Computer Performance: A Practitioner’s Guide, 2005.
• Little, J., and Graves, S. “Chapter 5: Little’s law.” In Building Intuition: Insights from Basic Operations Management Models and Principles. Springer Science+Business Media, 2008.
• Mulholland, B. “Little’s law: How to analyze your processes (with stealth bombers).” Process.st, 2017.