Discrete-Event Simulation

The M/M/1 queue has beautiful closed-form answers — but it is a rare luxury. Give the queue two servers with different speeds, a lunchtime rush, customers who give up after five minutes, and a priority lane for gold members, and every neat formula evaporates. There is no equation for the average wait. Yet you can still watch the system unfold, one event at a time, on a computer — and measure whatever you like. That is discrete-event simulation (DES): the workhorse that answers the queueing, logistics and manufacturing questions no formula can touch.

The key idea: nothing happens between events

A checkout queue seems to change continuously, but look closely and it only ever changes at discrete instants: the moment a customer arrives, the moment a service starts, the moment a customer departs. Between those instants the state — how many are in the system, whether the server is busy — sits perfectly still. So there is no point simulating the gaps. DES keeps a simulation clock that does not tick second by second; it jumps straight to the time of the next event, does whatever that event requires, and jumps again.

State — the variables that describe the system right now (number in system, server busy or idle, queue contents).
An event list (the future event set) — the scheduled events, each with a timestamp, kept sorted so the earliest is always next.
The clock — advanced to the time of the next event, never in between.

The engine is a simple loop: pop the earliest event, advance the clock to it, update the state, and schedule whatever new events it triggers (an arrival schedules the next arrival; a service-start schedules the matching departure). Repeat until the clock passes your stopping time.

A single-server queue, traced by hand

Take one server, first-come-first-served. Five customers arrive at times 0, 2, 3, 8, 12 and need service times 4, 3, 2, 1, 3 respectively. Watch the clock leap from event to event — the long axis below is time, arrivals sit above it, departures below:

The clock visits only the ten instants 0, 2, 3, 4, 7, 8, 9, 10, 12, 15 — the arrival and departure times — and skips everything in between. Here is the full trace the engine produces:

Clock	Event	Action taken	In system
0	C1 arrives	server idle → start C1, depart at 4	1
2	C2 arrives	server busy → C2 waits	2
3	C3 arrives	server busy → C3 waits	3
4	C1 departs	start C2, depart at 7	2
7	C2 departs	start C3, depart at 9	1
8	C4 arrives	server busy → C4 waits	2
9	C3 departs	start C4, depart at 10	1
10	C4 departs	server goes idle	0
12	C5 arrives	server idle → start C5, depart at 15	1
15	C5 departs	server goes idle	0

Now read off any statistic you like. The times spent waiting in the queue before service are 0, 2, 4, 1, 0 (C3 arrived at 3 but only started at 7, so it waited 4). The average wait is (0+2+4+1+0)/5 = 1.4. No formula produced that number — the simulation did.

One run is just one sample

That trace used five particular service times. Draw five different random ones and you'd get a different average wait. A single simulation run is exactly one draw of a Monte Carlo experiment — so to estimate the true average wait you must run the model many times (replications), each with fresh randomness, and average their results. Report not just the mean but a confidence interval, so you know how much the answer might wobble.

A warm-up (transient) period. A queue that opens empty is not yet in steady state; the early idle stretch drags the average down. Discard the warm-up and measure only once the system has settled.
Replications and a confidence interval. Many independent runs turn one noisy number into an estimate with error bars — the whole point of 1/\sqrt{n} convergence.

You could advance the clock in fixed steps (every second, say) and check "did anything happen?" — that is time-driven simulation, and it is how many physics and video-game loops work. But for a queue it is wasteful: almost every tick nothing changes, so you burn compute doing nothing, and if two events fall inside one tick you may get their order wrong. Event-driven simulation jumps straight to the next thing that actually happens, so it is both faster and exact about ordering. Time-stepping wins only when the state genuinely changes every instant (a moving fluid); for systems that lurch between quiet states, event-driven is the right model.

The single most common blunder in simulation is trusting a single run. One run gives one random sample, and randomness is lumpy: a quiet morning makes the system look calm, a freak burst makes it look overloaded. Without replications you cannot tell signal from noise, and without a warm-up period your averages are polluted by the empty-system start. A DES report that quotes "the average wait is 4.2 minutes" from one eight-hour run, with no interval and no warm-up, is not a result — it is an anecdote.