Section 3.

1: Discrete–Event Simulation

Discrete-Event Simulation: A First Course

c 2006 Pearson Ed., Inc. 0-13-142917-5

Discrete-Event Simulation: A First Course Section 3.1: Discrete–Event Simulation 1/1

Section 3.1 Discrete-Event Simulation

ssq1 and sis1 are trace-driven discrete-event simulations

Both rely on input data from an external source
These realizations of naturally occurring stochastic processes
are limited
We cannot perform “what if” studies without modifying the
data
We will convert the single server service node and the simple
inventory system to utilize randomly generated input

Discrete-Event Simulation: A First Course Section 3.1: Discrete–Event Simulation 2/1

Single Server Service Node

We need stochastic assumptions for service times and arrival

times
Assume service times are between 1.0 and 2.0 minutes
The distribution within this range is unknown
Without further knowledge, we assume no time is more likely
than any other
We will use a Uniform(1.0, 2.0) random variate

Discrete-Event Simulation: A First Course Section 3.1: Discrete–Event Simulation 3/1

Exponential Random Variates

In general, it is unreasonable to assume that all possible

values are equally likely.
Frequently, small values are more likely than large values
We need a non-linear transformation that maps 0.0 → 1.0 to
0.0 → ∞.
..
...
...
...
.
...

x = −µ ln(1 − u)
..
...
...
...
...
.
x
..
...
...
...
.....
...
...
....
...
...
.....
.
....
.....
.....
......
......
...
........
......
.......
.......
........
0.0 ........

0.0 u 1.0

Discrete-Event Simulation: A First Course Section 3.1: Discrete–Event Simulation 4/1

Exponential Random Variates
The transformation is monotone increasing, one-to-one, and onto
0<u<1 ⇐⇒ 0 < (1 − u) < 1
⇐⇒ −∞ < ln(1 − u) < 0
⇐⇒ 0 < −µ ln(1 − u) < ∞
⇐⇒ 0<x <∞

Generating an Exponential Random Variate

double Exponential(double µ) /* use µ > 0.0 */
{
return (-µ * log(1.0 - Random()));
}

The parameter µ specifies the sample mean

In the single-server service node simulation, we use Exponential(µ)
interarrival times
ai = ai −1 + Exponential(µ); i = 1, 2, 3, . . . , n
Discrete-Event Simulation: A First Course Section 3.1: Discrete–Event Simulation 5/1
Program ssq2

Program ssq2 is an extension of ssq1

Interarrival times are drawn from Exponential(2.0)
Service times are drawn from Uniform(1.0, 2.0)
The program generates all first-order statistics r̄ , w̄ , d̄, s̄, l̄ , q̄,
and x̄
It can be used to study the steady-state behavior
Will the statistics converge independent of the initial seed?
How many jobs does it take to achieve steady-state behavior?
It can be used to study the transient behavior
Fix the number of jobs processed and replicate the program
with the initial state fixed
Each replication uses a different initial rng seed

Discrete-Event Simulation: A First Course Section 3.1: Discrete–Event Simulation 6/1

Example 3.1.3

The theoretical averages for a single-server service node using

Exponential(2.0) arrivals and Uniform(1.0, 2.0) service times
are

r̄ w̄ d̄ s̄ l̄ q̄ x̄
2.00 3.83 2.33 1.50 1.92 1.17 0.75
Although the server is busy 75% of the time, on average there
are approximately two jobs in the service node
A job can expect to spend more time in the queue than in
service
To achieve these averages, many jobs must pass through node

Discrete-Event Simulation: A First Course Section 3.1: Discrete–Event Simulation 7/1

Example 3.1.3

The accumulated average wait was printed every 20 jobs

10 Initial seed
◦◦ ◦ – 12345
8 ◦
◦◦
◦
◦◦ ⋄ – 54321
◦◦
6 ◦◦◦
◦◦◦◦◦◦◦ ∗ – 2121212
w̄ ∗ ◦
⋄⋄⋄⋄⋄⋄⋄⋄⋄
◦◦◦◦◦◦ ◦
◦ ◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦
∗∗∗∗∗
4 ∗ ∗
⋄◦◦∗ ◦∗
◦ ∗ ∗
⋄ ∗
⋄ ⋄
∗ ∗ ∗
⋄⋄⋄⋄⋄∗
∗∗∗∗∗∗∗∗∗∗∗∗
⋄∗
⋄∗ ⋄∗
⋄∗⋄∗
⋄∗⋄∗
⋄∗⋄∗
⋄⋄ ⋄∗
∗∗ ⋄∗
⋄∗⋄∗
⋄∗⋄∗
⋄∗ ⋄⋄
⋄∗ ⋄
∗∗
◦⋄⋄⋄ ⋄⋄⋄⋄⋄⋄⋄
2
0
0 100 200 300 400 500 600 700 800 900 1000
Number of jobs, n

The convergence of w̄ is slow, erratic, and dependent on the

initial seed

Discrete-Event Simulation: A First Course Section 3.1: Discrete–Event Simulation 8/1

 Geometric Random Variates
y = Equilikely (a,b) = floor(Uniform(a,b+1)) = floor(x) Equilikely(a,b) is the ``discrete'' analog of
Uniform(a,b)
The Geometric(p) random variate is the discrete analog to a
continuous Exponential(µ) random variate
Let x = Exponential(µ) = −µ ln(1 − u)
Let y = ⌊x⌋ and let p = Pr(y 6= 0).

y = ⌊x⌋ 6= 0 ⇐⇒ x ≥1
The cdf (Cumulative Distribution function), ⇐⇒ −µ ln(1 − u) ≥ 1
F(p)=Pr(U<=p) =Pr(1-u<=p) = p
⇐⇒ ln(1 − u) ≤ −1/µ
indeed: F(p)=Int(0,p,1/(1-u))=p/(1-u)=p
⇐⇒ 1 − u ≤ exp(−1/µ)
because u is Uniform(0,1)

Since 1 − u is also Uniform(0.0,1.0)

(Int == )
p = Pr(y 6= 0) = exp(−1/µ)

Finally, since µ = −1/ ln(p), (and y=floor(-nu ln(1-u))

y = ⌊ln(1 − u)/ ln(p)⌋

Discrete-Event Simulation: A First Course Section 3.1: Discrete–Event Simulation 9/1

Geometric Random Variates

ANSI C function

Generating a Geometric Random Variate

long Geometric(double p) /* use 0.0 < p < 1.0 */
{
return ((long) (log(1.0 - Random()) / log(p)));
}

The mean of a Geometric(p) random variate is p/(1 − p)

If p is close to zero then the mean will be close to zero
If p is close to one, then the mean will be large

Discrete-Event Simulation: A First Course Section 3.1: Discrete–Event Simulation 10/1

Example 3.1.4

Assume that jobs arrive at random with a steady-state arrival

rate of 0.5 jobs per minute
Assume that Job service times are composite with two
components
The number of service tasks is 1 + Geometric(0.9)
The time (in minutes) per task is Uniform(0.1, 0.2)

Get Service Method

double GetService(void)
{
long k;
double sum = 0.0;
long tasks = 1 + Geometric(0.9);
for (k = 0; k < tasks; k++)
sum += Uniform(0.1, 0.2);
return (sum);
}

Discrete-Event Simulation: A First Course Section 3.1: Discrete–Event Simulation 11/1

Example 3.1.4
w = 3.83, d=2.33, l=1.92, q=1.17 (previous values)

The theoretical steady-state statistics for this model are

r̄ w̄ d̄ s̄ l̄ q̄ x̄
2.00 5.77 4.27 1.50 2.89 2.14 0.75
The arrival rate, service rate, and utilization are identical to
Example 3.1.3
The other four statistics are significantly larger
Performance measures are sensitive to the choice of service
time distribution

Discrete-Event Simulation: A First Course Section 3.1: Discrete–Event Simulation 12/1

Simple Inventory System

Program sis2 has randomly generated demands using an

Equilikely (a, b) random variate
Using random data, we can study transient and steady-state
behaviors
If (a, b) = (10, 50) and (s, S) = (20, 80), then the
approximate steady-state statistics are

d̄ ō ū l̄ + l̄ −
30.00 30.00 0.39 42.86 0.26

Discrete-Event Simulation: A First Course Section 3.1: Discrete–Event Simulation 13/1

Example 3.1.6

The average inventory level l̄ = l̄ + − l̄ − approaches steady

state after several hundred time intervals
55
⋄ Initial seed
◦ – 12345
50 ⋄ ⋄ – 54321
∗ – 2121212
⋄ ⋄
∗ ⋄ ∗ ⋄ ⋄ ⋄ ⋄
l̄ 45 ∗
⋄ ∗
∗ ∗ ∗ ∗ ∗
⋄ ⋄ ⋄ ∗ ∗ ⋄ ∗ ∗ ∗ ∗ ∗ ∗
◦ ∗ ∗ ∗ ⋄ ⋄ ∗ ⋄ ∗
⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ∗ ∗ ⋄ ∗
⋄ ⋄ ∗ ⋄ ∗ ⋄ ∗
⋄ ∗
⋄ ∗ ⋄ ∗ ⋄ ⋄ ∗
⋄ ∗ ⋄ ⋄ ∗
∗ ⋄ ∗ ⋄ ∗
⋄ ∗ ⋄
◦ ◦ ◦ ∗
◦ ◦ ◦ ◦
∗ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦
40 ◦ ◦ ◦ ◦ ◦
◦
◦
◦
35
0 20 40 60 80 100 120 140 160 180 200
Number of time intervals, n

Convergence is slow, erratic, and dependent on the initial seed

Discrete-Event Simulation: A First Course Section 3.1: Discrete–Event Simulation 14/1

Example 3.1.7

If we fix S, we can find the optimal cost by varying s

Recall that the dependent cost ignores the fixed cost of each
item
•
2400 • S = 80 •
•
◦◦◦ ◦ – n = 100 •◦
◦◦◦
•
◦◦ ◦ ◦••
◦•
2200 • – n = 10000 ◦•◦•
•◦◦◦ •
• •
◦
◦ ••
◦◦
dependent • ◦•
◦◦
•
2000 • ••
◦◦
cost, $ • ◦◦ ◦•
••
◦
• ◦
•
• ◦ •◦
◦◦
•
1800 •◦ ••
◦
•
•• •••
◦◦
◦◦◦ ◦
••◦
◦◦◦ ••
•• ◦◦◦◦◦ •◦ •• ◦
◦◦◦
••◦
••••• • •
◦◦◦
••
1600

0 5 10 15 20 25 30 35 40 45 50 55 60
Inventory parameter, s

Discrete-Event Simulation: A First Course Section 3.1: Discrete–Event Simulation 15/1

Example 3.1.7

Using a fixed initial seed guarantees the exact same demand

sequence
Any changes to the system are caused solely by the change of s
A steady state study of this system is unreasonable
All parameters would have to remain fixed for many years
When n = 100 we simulate approximately 2 years
When n = 10000 we simulate approximately 192 years
I.E., it is not real considering a world where things never changes,
--> steady state statistics is not very "meaningful" in this case

Discrete-Event Simulation: A First Course Section 3.1: Discrete–Event Simulation 16/1

Statistical Considerations

With Variance Reduction, we eliminate all sources of variance

except one (this approach allow us to "isolate" the variability of our interest)
Transient behavior will always have some inherent uncertainty
We kept the same initial seed and changed only s
Robust Estimation occurs when a data point that is not
sensitive to small changes in assumptions
Values of s close to 23 have essentially the same cost
Would the cost be more sensitive to changes in S or other
assumed values?

Discrete-Event Simulation: A First Course Section 3.1: Discrete–Event Simulation 17/1