1. Discrete Event Simulation

What a discrete-event simulation consists of — entities, events, the event list, the clock, and statistical counters — walked through on a single-server FCFS queue.

1.1. Stochastic Dynamic Systems

A discrete-event simulation model consists of:

1. entities — the objects in the system
2. attributes — properties of an entity
3. state — variables describing the system at time $t$
4. events — instants at which the state changes
5. event list — the scheduled future events, in time order
6. clock — the current simulated time
7. statistical counters — running totals used to compute the outputs

1.2. Single-server queueing system with FCFS service discipline

Here is an example:

flowchart LR
    A([arrival]) --> Q[waiting line] --> S((server)) --> D([departure])

Objective. Estimate the average delay of a customer, where

$$\text{delay} = \text{(time service begins)} - \text{(arrival time)}.$$

Let $D_i$ be the delay of the $i$-th customer. Then $\bar{D} = \dfrac{1}{n}\sum_{i=1}^n D_i$.

Entities: customer, server
Attributes: arrival time of a customer; service time of a customer
State: $N(t)$ = number of customers in the system at time $t$; $S(t) \in \{\text{busy}, \text{idle}\}$ = status of the server
Events: arrival, departure, end of simulation
Statistical counters: number of customers delayed, total delay $\sum D_i$, area under $N(t)$, area under $Q(t)$

Notation

• $X_i$: interarrival time; $a_i = a_{i-1} + X_i$ is the arrival time ($a_0 = 0$), so the 2nd customer arrives at $X_1 + X_2$.
• $Y_i$: service time.
• $d_i$: departure time (the figure writes $D_i$; it should be $d_i$).
• Delay $D_i$: time spent in the queue, excluding service.
• Waiting time $W_i$: time spent in the system, including service, so $W_i = D_i + Y_i$.

Under FCFS, customer $i$ begins service when customer $i-1$ departs (or immediately, if the server is idle):

$$D_i = \max(0,\; d_{i-1} - a_i), \qquad d_i = a_i + D_i + Y_i .$$

Sample path (from the board, $T = 180$)

$i$	1	2	3	4	5
$X_i$	55	32	24	40	12
$a_i$	55	87	111	151	163
$Y_i$	43	36	34	16	–
$d_i$	98	134	168	184	–
$D_i$	0	11	23	17	21

gantt
    title Single-server queue, T = 180
    dateFormat X
    axisFormat %s
    section Customer 1
    in service   :done, c1s, 55, 98
    section Customer 2
    in queue     :active, c2q, 87, 98
    in service   :done,   c2s, 98, 134
    section Customer 3
    in queue     :active, c3q, 111, 134
    in service   :done,   c3s, 134, 168
    section Customer 4
    in queue     :active, c4q, 151, 168
    in service   :done,   c4s, 168, 184
    section Customer 5
    in queue     :active, c5q, 163, 184

Equivalently, $N(t)$ as a step function:

interval	$[0,55)$	$[55,87)$	$[87,98)$	$[98,111)$	$[111,134)$	$[134,151)$	$[151,163)$	$[163,168)$	$[168,180]$
$N(t)$	0	1	2	1	2	1	2	3	2
$Q(t)$	0	0	1	0	1	0	1	2	1

where $Q(t) = \max(0, N(t) - 1)$ is the number in the queue.

Time-average quantities

Average number in system.

$$\hat{L} = \sum_{i} i \cdot \frac{\text{total time with } i \text{ customers in system}}{T} = \frac{1}{T}\int_0^T N(t)\,dt = \frac{193}{180}.$$

Average number in queue.

$$\hat{L}_Q = \frac{1}{T}\int_0^T Q(t)\,dt = \frac{11 + 23 + 12 + 10 + 12}{180} = \frac{68}{180}.$$

Server utilization (proportion of time the server is busy).

$$\hat{\rho} = \frac{1}{T}\int_0^T \mathbf{1}\{S(t) = \text{busy}\}\,dt = \frac{180 - 55}{180}.$$

If $X_i \sim \text{Exp}(\lambda)$ and $Y_i \sim \text{Exp}(\mu)$, this is the $M/M/1$ queue.

How the simulation is driven

flowchart LR
    U["random numbers<br/>U ~ U(0,1)"] --> Tr[transformation]
    In[input distributions] --> Tr
    Tr --> V["random variates<br/>X_i, Y_i"] --> P[simulation program] --> O["outputs<br/>D_1, D_2, ..., W_1, W_2, ..."]