Skip to content
Tutorials Center
My learning

Topics

Lesson 28 of 38 · Simulation of Systems

Simulating a Queue

Simulate a single-server queue with Lindley's recursion, compare with the M/M/1 formulas, and see why waits explode as utilization nears 100%.

Queues are everywhere: shoppers at a till, calls at a help desk, packets at a router, patients in a clinic. Customers arrive at random, wait if the server is busy, and are served one at a time. Management questions follow naturally. How long will people wait on average? How many staff do we need? What happens on a busy day?

Some queues have clean formulas. Most real ones do not, but simulation answers all of them, and the formula-friendly cases let you check your simulator. We start with the classic M/M/1 queue: arrivals form a Poisson process with rate λ (so the gaps between arrivals are exponential with mean 1/λ), service times are exponential with rate μ (mean 1/μ), and there is one server. Customers are served first come, first served.

Lindley's recursion

You do not need a full event simulator for a single FIFO server. Let W_n be the time customer n waits in the queue before service begins. Customer n+1 arrives A time units after customer n. When customer n arrives, they wait W_n and then take service time S_n. So when customer n+1 arrives, the work ahead of them is W_n + S_n − A, unless that is negative, in which case the server is idle and they wait zero:

Text
W_{n+1} = max( 0,  W_n + S_n − A_{n+1} )

This one line is Lindley's recursion. It simulates the whole queue.

The quantity ρ = λ/μ is the utilization, the fraction of time the server is busy. The queue is stable only if ρ < 1. For M/M/1 in steady state the textbook results are:

Quantity Formula
Mean wait in queue W_q ρ / (μ − λ)
Mean time in system W 1 / (μ − λ)
Mean number in system L ρ / (1 − ρ)

and Little's law L = λ·W links the number in the system to the time in it.

Simulating and checking

Take λ = 0.8 and μ = 1, so ρ = 0.8. Theory says W_q = 0.8/0.2 = 4 and W = 5.

Python M/M/1 queue by Lindley's 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 numbers should be near the theory. The fraction of customers who do not wait equals the fraction of time the server is idle, 1 − ρ = 0.2, a fact that comes from the PASTA property (Poisson arrivals see time averages).

Why congestion explodes near full utilization

Wait times are not linear in load. In M/M/1 the mean wait ρ/(μ − λ) blows up as λ → μ. Going from ρ = 0.5 to ρ = 0.9 does not nearly double the wait, it multiplies it by 9. Simulation near ρ = 1 also converges slowly, because the queue's memory is long.

Python Waiting time 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 ρ = 0.95 the theoretical wait is 19 service times, and the simulated value is typically noisier than at the lower loads. Note the lesson for system design: running a server at 95% load leaves no slack for random bursts.

Statistics from a queue simulation are not independent: customer n+1's wait depends on customer n's. To get honest error bars, run several independent replications (different seeds) and use the spread of their means, or use batch means.

Making it your own

The recursion works for any distributions, not just exponential. Replace rng.exponential with another sampler (constant service times, lognormal times, a mix) and you have an M/G/1 or G/G/1 queue, which often has no clean formula. For a queue with several servers or priorities, use the event-driven method in the next lesson, discrete-event simulation.

A famous partial formula, the Pollaczek-Khinchine result for M/G/1, says W_q = λ·E[S²] / (2(1 − ρ)). It shows that service-time variability matters, not only its mean: with the same mean, constant service gives half the waiting time of exponential service. You can test this in a TryIt by swapping the sampler.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Lindley's recursion for waiting times is:

    The next customer waits for the leftover work, but never a negative time.
  2. 2. For an M/M/1 queue with lambda = 0.5 and mu = 1, the utilization is:

    rho = lambda / mu = 0.5.
  3. 3. As utilization approaches 1, the mean wait in an M/M/1 queue:

    W_q = rho / (mu - lambda) tends to infinity as lambda approaches mu.
  4. 4. Why can't you treat all waits in one run as independent samples?

    Each wait depends on the previous one, so use replications or batch means for error bars.

Summary

  • A single FIFO server follows Lindley's recursion W_{n+1} = max(0, W_n + S_n − A_{n+1}).
  • For M/M/1: ρ = λ/μ, W_q = ρ/(μ − λ), W = 1/(μ − λ), L = ρ/(1 − ρ); Little's law L = λW.
  • Waiting times grow explosively as ρ → 1; high utilization means long waits.
  • Use independent replications for honest error bars; swap distributions to model non-exponential systems.

Next: Discrete-Event Simulation