Skip to content
Tutorials Center
My learning

Topics

Lesson 33 of 38 ยท Simulation and Applications

Simulating an M/M/1 Queue from Scratch

Write a queue simulation in a few lines with Lindley's recursion, compare it with theory, and learn about warm-up bias, run length and random seeds.

Formulas exist for only a few queues. Everything else, such as priorities with preemption costs, finite buffers with balking, and networks with rework, is studied by simulation: build a computer model, run it for many virtual customers, and measure. Before relying on a big simulator, you should be able to write a tiny one and prove it matches a case with a known answer. M/M/1 is that case.

Lindley's recursion

For a single-server FCFS queue, you do not even need an event list. Let W_n be the time customer n waits in the queue, S_n the service time of customer n, and A_{n+1} the gap between the arrival of customers n and n + 1. Customer n + 1 arrives A_{n+1} after customer n. When n arrived, they waited W_n and then were served for S_n. So customer n + 1 has to wait the part of that time that has not yet passed, if any:

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

That is Lindley's recursion. Feed it random numbers and you have a queue.

Python M/M/1 by Lindley's recursion versus theory

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 estimates scatter around the theoretical Wq = 4, and tend to come closer as n grows. A single short run can be far off, which is the first lesson: one run is one sample.

Random numbers and seeds

A computer uses a pseudo-random generator. Fixing a seed makes the run reproducible: same seed, same numbers, same answer. That is good for debugging. To estimate the uncertainty, run several independent replications with different seeds and look at how much the answers differ.

Python Replications show the sampling noise

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 spread between replications is the honest measure of how much to trust any single run.

Warm-up (initial transient) bias

The recursion above starts with an empty queue, W_0 = 0. Early customers see a shorter queue than the steady state, which biases the average downward. This initial transient matters more at high utilization, where the queue takes a long time to fill. The usual fix is to discard the first part of the run (a warm-up period) and average the rest. A rough guide is to plot a moving average of waits and discard data until it levels off.

Python Warm-up: the early average is too low

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.

Averaged over 400 replications, the first block of customers has a clearly lower mean wait than the long-run value of 9, and later blocks settle near it. At ฯ = 0.9 a single run is also very noisy: the variance of an estimate grows roughly like 1/(1 - ฯ)ยฒ, so high utilization needs both a warm-up and long runs.

Always validate a simulator against a case with a known answer (M/M/1, M/D/1, Erlang B) before using it for something new. A simulator that matches theory in the easy case earns trust in the hard case.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Lindley's recursion is

    The next customer waits for what remains of the previous customer's wait plus service after the gap between arrivals.
  2. 2. Why use several replications with different seeds?

    Independent replications give a sample from which we can measure the noise.
  3. 3. Starting the simulation with an empty queue makes the early average

    The first customers see less congestion than the steady state, so the early average is biased downward.
  4. 4. Which utilization needs the longest simulation for the same accuracy?

    At high utilization the queue is slow to converge and the variance of estimates is large.

Summary

  • Lindley's recursion simulates a single-server FCFS queue in a few lines.
  • Validate against known results; one run is a single noisy sample.
  • Use different seeds for independent replications; fix a seed to reproduce a run.
  • Discard a warm-up period to reduce initial-transient bias.

Next: A Discrete-Event Simulation Engine