Skip to content
Tutorials Center
My learning

Topics

Lesson 31 of 38 ยท Scheduling and Queueing

Queueing Fundamentals and the M/M/1 Queue

Learn queueing theory basics: arrival and service processes, Kendall notation, utilization, Little's law and the M/M/1 formulas, verified with a simulation in Python.

Waiting lines are everywhere: customers at a checkout, calls to a support center, requests to a web server, patients in an emergency room, jobs in a print queue. Queueing theory is the mathematics of waiting. It explains why queues grow even when servers are on average fast enough, why a small increase in load can double the wait, and how many servers you need to meet a service target.

Operations research uses queueing models to size staff, buffers and machines. This lesson builds the vocabulary and the simplest model, the M/M/1 queue. The next lesson extends it to several servers and simulation (Multi-Server Queues and Simulation).

The elements of a queue

Every queueing system has:

  • an arrival process: how customers show up. The usual model is a Poisson process with rate lambda (arrivals per unit time): inter-arrival times are independent and exponential with mean 1/lambda.
  • a service process: how long each customer needs. Exponential service with rate mu (mean 1/mu) is the classic choice.
  • the number of servers c.
  • the queue discipline: FIFO (first in, first out), priority, random and so on.
  • a capacity: the maximum number in the system (often infinite).
flowchart LR
    A["Arrivals<br/>rate lambda"] --> Q["Waiting line<br/>(queue)"] --> S["Server<br/>rate mu"] --> D["Departures"]

Kendall notation

A queue is described as A/B/c/K/N/D. The first three letters are the key ones:

  • A arrival distribution, B service distribution: M (Markovian: Poisson arrivals or exponential service), D (deterministic) or G (general).
  • c number of servers.

So M/M/1 has Poisson arrivals, exponential service, one server; M/M/c has c servers; M/D/1 has constant service times; M/G/1 has any service distribution.

Utilization and stability

The utilization (traffic intensity) of a single server is:

TEXT
rho = lambda / mu

It is the long-run fraction of time the server is busy. If rho >= 1, the work arrives at least as fast as it can be done, and the queue grows without bound. For a steady state you need rho < 1. Note that this holds even though every individual customer is served quickly: randomness alone creates waiting.

Little's law

For any stable system (almost no assumptions needed):

TEXT
L = lambda * W

where L is the average number of customers in the system and W the average time each spends there. The same law holds for the queue alone: Lq = lambda * Wq. It is a simple and powerful accounting identity: if 30 customers per hour arrive and each stays 20 minutes on average, then on average 30 * (1/3) = 10 are inside.

M/M/1 results

For the M/M/1 queue in steady state (rho < 1):

Quantity Formula
Probability the system is empty P0 = 1 - rho
Probability of n in system Pn = (1 - rho) * rho^n
Average number in system L = rho / (1 - rho)
Average number in queue Lq = rho^2 / (1 - rho)
Average time in system W = 1 / (mu - lambda)
Average wait in queue Wq = rho / (mu - lambda)

The number in the system follows a geometric distribution. And notice the denominators: as rho approaches 1, waiting times explode.

Python How waiting explodes as utilization rises

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

At 50% utilization a customer waits about 6 minutes in the queue; at 90% it is 54 minutes; at 99% it is nearly 10 hours. The lesson for managers: run a server at 100% busy and queues become infinite. Aim for utilizations well below 85% when waiting is costly.

Checking the formulas by simulation

A single-server FIFO queue can be simulated with the Lindley recursion. If the n-th customer waits W_n in the queue, brings a service time S_n, and the next customer arrives A_{n+1} time units later, then:

TEXT
W_{n+1} = max(0, W_n + S_n - A_{n+1})
Python Simulating an M/M/1 queue with the Lindley recursion

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The simulated averages land close to theory (random variation depends on the seed and run length). Simulation is a universal tool: when a model has no formula, you simulate it, and when it has one, you simulate to check yourself.

Waiting time distribution

In M/M/1 with FIFO, the time in the system is exponentially distributed with rate mu - lambda. So P(T > t) = exp(-(mu - lambda) t). The probability that a customer spends more than 30 minutes in the system when lambda = 8, mu = 10 per hour is exp(-2 * 0.5) = 0.37. Averages hide long tails: even when the mean wait is acceptable, many customers can still wait much longer.

Finite capacity and balking

Real systems often cap the queue. In the M/M/1/K queue, a customer arriving when K are present is turned away (blocked). Then Pn = (1 - rho) rho^n / (1 - rho^(K+1)) for n = 0..K, and the system is stable even when rho >= 1, because arrivals are lost instead of piling up. The blocking probability P_K tells you how much business you lose; you pick K (a buffer size, parking spaces, waiting seats) to keep it low.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A server completes 12 jobs per hour on average and 9 jobs arrive per hour. What is the utilization?

    rho = lambda / mu = 9 / 12 = 0.75.
  2. 2. What does Little's law say?

    The average number in the system equals the arrival rate times the average time spent in the system.
  3. 3. What happens to the M/M/1 queue when rho >= 1?

    Work arrives at least as fast as it is served, so no steady state exists.
  4. 4. In Kendall notation, what does the first M in M/M/1 stand for?

    M stands for Markovian: Poisson arrivals, i.e. exponential inter-arrival times.

Summary

  • A queue is defined by its arrival process, service process, number of servers, discipline and capacity; Kendall notation abbreviates this (M/M/1, M/M/c, M/G/1).
  • Utilization rho = lambda / mu must be below 1 for a stable single-server queue.
  • Little's law L = lambda * W holds for stable systems in general.
  • M/M/1 has closed forms: L = rho/(1-rho), Wq = rho/(mu-lambda); waiting times blow up as rho approaches 1.
  • The Lindley recursion simulates a single-server queue and checks theory.

Next: Multi-Server Queues and Simulation