Skip to content
Tutorials Center
My learning

Topics

Lesson 29 of 38 ยท Simulation of Systems

Discrete-Event Simulation

Build a discrete-event simulator with a priority-queue event list, simulate a bank with two tellers and check the result against Erlang C.

A simulation could advance time in tiny fixed ticks (a millisecond at a time) and ask what changes. That wastes effort: most ticks nothing happens. Discrete-event simulation (DES) jumps straight from one event to the next. Between events the system state is constant, so nothing needs computing. Time moves in irregular leaps, and the clock always sits at the moment something happens: a customer arrives, a service finishes, a machine breaks.

DES is the method behind simulations of call centers, factories, hospitals, networks and logistics. Its structure is the same everywhere.

The ingredients

  1. State variables: the things that describe the system now (how many servers are busy, who is waiting).
  2. Simulation clock: the current time.
  3. Event list: a collection of scheduled future events, sorted by time. A priority queue (a heap) is the natural data structure.
  4. Event handlers: code for each event type that updates the state and may schedule new events.
  5. Statistics: counters that record waits, queue lengths and utilization.

The main loop is always:

flowchart TD
  A["Pop the earliest event"] --> B["Advance clock to its time"]
  B --> C["Run its handler: update state, record statistics"]
  C --> D["Schedule new events"]
  D --> E{"Event list empty or end time?"}
  E -->|No| A
  E -->|Yes| F["Report statistics"]

Every discrete-event simulator is some version of this loop.

A bank with two tellers

Customers arrive at rate ฮป (exponential gaps). There are c = 2 tellers sharing one line, each serving at rate ฮผ (exponential service). This is an M/M/c queue. There are two event types: arrival and departure.

  • Arrival: if a teller is free, start service now and schedule a departure; otherwise join the queue. Then schedule the next arrival.
  • Departure: a teller frees up. If someone is waiting, start their service and schedule their departure.

For M/M/c theory, let a = ฮป/ฮผ and ฯ = a/c < 1. The probability an arriving customer must wait is the Erlang C formula:

Text
C(c, a) = [ aแถœ / (c! (1 โˆ’ ฯ)) ] / [ ฮฃ_{k=0}^{cโˆ’1} aแต/k!  +  aแถœ / (c! (1 โˆ’ ฯ)) ]

and the mean wait in queue is W_q = C(c, a) / (cยทฮผ โˆ’ ฮป).

Python Event-driven M/M/c simulation

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 chance of waiting and the mean wait should sit close to the Erlang C values. Matching a known formula is how you gain trust in a simulator before using it on a case with no formula.

A case with no formula: constant service

The same engine handles any service-time distribution. Real tellers are not exponential: if every service took exactly one time unit, queues would be shorter. We keep the same mean service time but remove its randomness.

Python Exponential vs constant service times

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.

Both systems have the same arrival rate, mean service time and number of tellers, and so the same utilization of 0.8, yet constant service produces visibly shorter waits. Averages of inputs do not tell the whole story: variability costs time.

Tips for building simulators

  • Ties and order. If two events share a time, decide which goes first; a counter in the heap tuple makes the order deterministic and avoids comparing non-comparable items.
  • Warm-up. The system starts empty; discard the initial transient, as we did with the first 2,000 customers.
  • Replications. Run several independent replications with different seeds and report a confidence interval.
  • Common random numbers. When comparing two designs, drive both with the same random streams so differences are due to the design, not luck.
  • Libraries. For big models, packages such as SimPy handle the event list for you; the idea is exactly what you built here.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In discrete-event simulation the clock:

    State changes only at events, so the clock jumps straight to the next scheduled event.
  2. 2. Which data structure is natural for the event list?

    We always need the earliest event next, which a min-heap provides efficiently.
  3. 3. What does Erlang C give?

    It is the probability that all c servers are busy when a customer arrives.
  4. 4. Two queues have the same mean service time and arrival rate, but one has constant service. Its waiting time is:

    Less variability in service time means shorter waits, as in the Pollaczek-Khinchine formula.

Summary

  • Discrete-event simulation jumps between events using an event list, usually a heap ordered by time.
  • Each event type has a handler that updates state, records statistics and schedules new events.
  • Check a simulator against a known formula (Erlang C for M/M/c), then use it for cases without a formula.
  • Discard warm-up, replicate with different seeds, and use common random numbers to compare designs.

Next: Inventory Simulation and the Newsvendor Problem