English
Menu

What is Queueing theory?

The theory that models with probability how processing requests arrive at a window or server and wait until it is free to be served, and that derives waiting times and queue lengths. A model is described in Kendall's notation, which lists the arrival distribution, service time distribution and number of servers, as in "M/M/1". In the M/M/1 model, the average waiting time is ρ/(1 − ρ) × Ts, using the utilization ρ = arrival rate λ × average service time Ts. It is used in computer performance evaluation, network delay analysis and analysis of work in progress in factories.

Japanese name: 待ち行列理論

Queueing theory appears in 6 practice questions across 1 topic, including Probability, Statistics and Queueing.

Field: Probability, Statistics and Queueing

Kendall's notation and M/M/1

A queueing model is written in the form "arrival distribution/service time distribution/number of servers". M stands for the Markov property: for arrivals it means Poisson arrivals (exponentially distributed intervals), and for service times an exponential distribution. D means a constant time and G a general distribution. M/M/1 is a model with one server, random arrivals and random service times, and its basic assumptions are unlimited waiting room, first-come-first-served processing and a steady state reached after enough time.

Basic formulas

The utilization ρ = λ × Ts is the fraction of time the server is busy. For M/M/1, the average waiting time is Wq = ρ/(1 − ρ) × Ts, the average response time is W = Wq + Ts = Ts/(1 − ρ) and the average number in the system is L = ρ/(1 − ρ). These are linked by Little's law L = λW; for example, with λ = 3 per minute and Ts = 15 seconds, ρ = 0.75, Wq = 45 seconds, W = 60 seconds and L = 3.

Utilization and waiting time

Wq ÷ Ts = ρ/(1 − ρ) is 1 at a utilization of 0.5, 4 at 0.8, 9 at 0.9 and 19 at 0.95, growing sharply as the utilization approaches 1. This is because the idle time 1 − ρ available to clear queues formed by chance bunching of arrivals becomes scarce. Systems where response time matters are therefore designed with a margin in utilization.

Try it: questions about Queueing theory

Requests arrive at a service window at an average of 12 per hour, and each takes an average of 4 minutes to handle. Treating it as an M/M/1 queue, which of the following is the utilization of the window?

  1. A0.8
  2. B1.25
  3. C3
Show answer and explanation

Answer: A. 0.8

The utilization ρ is the product of the arrival rate λ and the average service time Ts, and it expresses the fraction of time the window is busy. With matching units, 4 minutes = 1/15 hour, so ρ = 12 × 1/15 = 0.8. Using the service rate μ = 15 per hour, ρ = λ/μ = 12/15 gives the same result.

Requests arrive at a server at an average of 3 per minute, and each takes an average of 15 seconds to process. Treating the server as an M/M/1 queue, which of the following is the average time from the arrival of a request until its processing is finished (the average response time)?

  1. A20 seconds
  2. B45 seconds
  3. C60 seconds
Show answer and explanation

Answer: C. 60 seconds

The utilization is ρ = 3 per minute × 15 seconds ÷ 60 seconds = 0.75. The average waiting time is Wq = ρ/(1 − ρ) × Ts = 0.75/0.25 × 15 = 45 seconds, and adding the processing time of 15 seconds gives an average response time of 45 + 15 = 60 seconds. Ts/(1 − ρ) = 15/0.25 = 60 seconds gives the same result.

FAQ

What if the M/M/1 assumptions do not hold?

A model closer to reality is used, such as M/D/1 when the service time is constant. The average waiting time of M/D/1 is exactly half that of M/M/1, and the smaller the variation in service time, the shorter the wait. Complex systems are often checked by simulation, and Little's law holds in every case.

Is it better to add servers or to make a server faster?

For the same total capacity, one server twice as fast gives a shorter average response time than two servers sharing one queue (M/M/2). Comparing only the time spent waiting in the queue, however, two servers give the shorter wait. Even with two servers, giving each its own separate queue means customers can wait at one while the other is idle, so the waiting time is longer than with a single shared queue.

Queueing theory in the explanations

Questions that mention Queueing theory (6)

  1. Requests arrive at a service window at an average of 12 per hour, and each takes an average of 4 minutes to handle. Treating it as an M/M/1 queue, which of the following is the utilization of the window?
  2. Requests arrive at a server at an average of 3 per minute, and each takes an average of 15 seconds to process. Treating the server as an M/M/1 queue, which of the following is the average time from the arrival of a request until its processing is finished (the average response time)?
  3. For a server that can be treated as an M/M/1 queue, the arrival rate increased with the average service time unchanged, and the utilization rose from 0.8 to 0.9. By what factor did the average waiting time Wq (the time spent waiting in the queue) change? Which of the following is closest?
  4. A server with an average service time of 0.2 seconds is treated as an M/M/1 queue. To keep the average response time (waiting time plus processing time) at or below 1.0 second, which of the following is closest to the maximum arrival rate that can be accepted?
  5. Requests reach a server as Poisson arrivals (independent, random arrivals) at an average of 6 per minute. Which of the following correctly combines the distribution followed by the intervals between arrivals and their mean?
  6. There are two service windows of the same speed. In scheme A, each customer picks one of the windows with equal probability on arrival and joins that window's own queue. In scheme B, customers join a single queue and are served by whichever window becomes free first. Arrivals are random, and the total arrival rate and service speed are the same in both schemes. Which of the following correctly compares the average waiting time?

Books on Probability, Statistics and Queueing Ad

As an Amazon Associate I earn from qualifying purchases.

Related terms

Exponential distribution Bayes' theorem Binomial distribution Conditional probability Confidence interval Correlation coefficient Expected value Hypothesis testing Median Normal distribution

Back to the glossary