Skip to content
Tutorials Center
My learning

Topics

Lesson 34 of 38 · Simulation and Applications

A Discrete-Event Simulation Engine with Confidence Intervals

Build a reusable event-list simulator for M/M/c queues with heapq, compare it with Erlang C, and report results with confidence intervals from replications.

Lindley's recursion works only for one FCFS server. For several servers, priorities, blocking or networks we need a general method: discrete-event simulation (DES). The state changes only at specific instants called events (an arrival, a service completion). Between events nothing happens, so the simulator jumps from one event to the next.

The ingredients

  1. A clock (the current simulated time).
  2. An event list: events waiting to happen, ordered by time. In Python, heapq gives a priority queue.
  3. State: number of busy servers, the waiting line.
  4. Event handlers: what each event type changes, and which new events it schedules.
  5. Statistics: for example, the waiting time of each customer.

The main loop: pop the earliest event, advance the clock to its time, run its handler, repeat.

Python An M/M/c queue simulated with an event list

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.

When a server finishes and someone is waiting, the next customer starts service immediately. Their wait is the current time minus their arrival time. The first warmup customers are discarded.

Comparing with Erlang C

For M/M/c with a = λ/μ and ρ = a/c < 1, the probability that an arrival must wait is the Erlang C formula:

Text
C(c, a) = [ a^c / (c! (1 - ρ)) ] / [ Σ_{k=0}^{c-1} a^k / k!  +  a^c / (c! (1 - ρ)) ]
Wq = C(c, a) / (c μ - λ)

The multi-server chapter derives this; here we use it to validate the simulator.

Confidence intervals from replications

Run R independent replications and let x̄ be the mean of the R estimates and s their sample standard deviation. A 95 percent confidence interval for the true mean is:

Text
x̄ ± t · s / √R

where t is the Student-t critical value with R - 1 degrees of freedom (t = 2.262 for R = 10).

Python Replications, a confidence interval, and the Erlang C check

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.

If the exact value falls inside the confidence interval, the simulator agrees with theory; if it does so about 95 percent of the time over many experiments, the interval is doing its job.

Practical advice

  • Seeds: use a different seed per replication; keep a list so results can be reproduced.
  • Run length vs replications: long runs reduce bias from the start, many replications give an honest interval. Ten to thirty replications of reasonable length is a common choice.
  • Common random numbers: when comparing two designs, use the same seeds for both, so that differences come from the design and not from luck.
  • Units: keep time units consistent across rates and statistics.

An event list can be reused for any system: add new event types, such as a breakdown or a timeout, and handlers that change the state. The engine itself does not change.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What are the two basic event types in an M/M/c simulation?

    Arrivals add customers; service completions free servers and start the next waiting customer.
  2. 2. Why is a heap (priority queue) used for the event list?

    heapq.heappop returns the smallest time first in logarithmic time.
  3. 3. A 95% confidence interval from R = 10 replications uses which margin?

    With R - 1 = 9 degrees of freedom, the t critical value is 2.262, and the standard error of the mean is s/√R.
  4. 4. Common random numbers are used to

    Sharing seeds across designs makes the difference between designs less affected by chance.

Summary

  • DES jumps from event to event using an event list (a heap), a clock, state and handlers.
  • Validate against Erlang C or other known results.
  • Use independent replications to build a confidence interval x̄ ± t s/√R.
  • Discard warm-up, fix seeds for reproducibility, and use common random numbers when comparing designs.

Next: Staffing a Call Center with Erlang C