2/28/2024

Chapter 5. Discrete Event Simulation

Nguyen VP Nguyen, Ph.D.

Department of Industrial & Systems Engineering, HCMUT
Email: nguyennvp@[Link]

Objective

1. We will focus on a simple single-server service

center. Possible examples:
− Convenience store: customers, cashiers
− Airport: runways, airplanes

1
 2/28/2024

What is Discrete-Event Simulation (DES)?

• DES includes basic building blocks of all discrete-

event simulation models that contains:
entities, and
attributes,
activities, and
System
events.

• Modeling of a system as it evolves over time by a

representation where the state variables change
instantaneously at separated points in time
− More precisely, state can change at only a countable
number of points in time
− These points in time are when events occur

System simulation by arena

• Arena Simulation Software in Supply Chain

[Link]
au/products/software/arena‐simulation/discrete‐event‐
modeling/supply‐[Link]
• Arena Simulation Software in Food & Beverage
[Link]
au/products/software/arena‐simulation/discrete‐event‐
modeling/food‐[Link]
• Arena Software in the Academic Environment
[Link]
in/products/software/arena-simulation/[Link]
• Arena Simulation Software in Packaging
[Link]
us/products/software/arena-simulation/discrete-event-
modeling/[Link]

2
 2/28/2024

System: A collection of entities (e.g., people and

machines) that interact together over time to accomplish
one or more goals.

Model: An abstract
representation of a system
entities and their attributes
sets
1. structural relationships processes
2. logical or mathematical
relationships events
activities
delays
state

• Model: An abstract representation of a system, usually

containing structural, logical, or mathematical relationships
that describe a system in terms of state, entities and their
attributes, sets, processes, events, activities, and delays.

3
 2/28/2024

System state: A collection of variables that contain all the

information necessary to describe the system at any time.
Entity Any object or component in the system that requires explicit
representation in the model (e.g., a server, a customer, a machine) by the
following components
Attributes The properties of a given entity (e.g., the priority of a
waiting customer, the routing of a job through a job shop).
Event An instantaneous occurrence that changes the state of a system
(such as an arrival of a new customer).
List ~ (also called) sets, queues, or chains : A collection of
(permanently or temporarily) associated entities, ordered in some logical
fashion (such as all customers currently in a waiting line
Activity A duration of time of specified length (e.g., a service time or
interarrival time), which is known when it begins (may be defined in terms
of a statistical distribution).
Delay A duration of time of unspecified indefinite length, which is not
known until it ends (e.g., a customer’s delay in a last-in–first-out waiting
line which, when it begins, depends on future arrivals).
Clock A variable representing simulated time, called CLOCK in the
examples to follow.

Modeling a system depending on the states

• A system is modeled in terms of its state at each
point in time
• This is appropriate for systems where changes
occur only at discrete points in time

4
 2/28/2024

Activity
• An activity typically represents a service time, an
interarrival time, or any other processing time
• An activity’s duration may be specified in a
number of ways:
1. Deterministic—for example, always exactly 5
minutes;
2. Statistical—for example, as a random draw from the
set {2, 5, 7} with equal probabilities;
3. A function depending on system variables and/or
entity attributes—for example, loading time for an
iron ore ship as a function of the ship’s allowed cargo
weight and the loading rate in tons per hour.

Activity vs. Delay

• Activity
− Activity is known as unconditional wait
− End of an activity is an event, for this an event notice
is placed in the future event list
• Delay
− Delay is known as conditional wait
− Completion of delay is a secondary event, but they are
not placed in the future event list (FEL)

5
 2/28/2024

12

future event list (FEL)

• all events occur in correct chronological order is

based on the future event list (FEL)

system snapshot at simulation time t

12

Example: Single-Server Service Center

Interarrival customers
Service completion
Service time by Server

Arriving Customers in queue Server Departing

customer customer

entities activities activities entities

events delays system state:

1. number of customers waiting
to be served
current simulated time is 2. indicate the Server as being
CLOCK = 1 minutes idle or busy at time t;

13

6
 2/28/2024

Example: Single-Server Service Center

Interarrival customers
Service completion
Service time by Server

Arriving Customers in queue Server Departing

customer customer

current simulated time is CLOCK = 0 minutes

system state:
1. number of customers waiting to be served =?
2. indicate the Server as being idle or busy at time t=?

Clock System Entities Queue Future event list Statistics

state
t=0 #cusinque 1 List={} 1, t1=0: arriving cus
=0
Server=0
15

Example: Single-Server Service Center

Interarrival customers
Service completion
Service time by Server

Arriving Customers in queue Server Departing

customer customer

current simulated time is CLOCK = 1 minutes

system state:
1. number of customers waiting to be served =?
2. indicate the Server as being idle or busy at time t=?

Clock System Entities Queue Future event list Statistics

state
t=1 #cusinque 1 List={} 1, t1=0: arriving cus
=0 1, t2=1: served
Server=1
16

7
 2/28/2024

Example: Single-Server Service Center

Interarrival customers
Service completion
Service time by Server

Arriving Customers in queue Server Departing

customer customer

current simulated time is CLOCK = 1.5 minutes

system state:
1. number of customers waiting to be served =?
2. indicate the Server as being idle or busy at time t=?
Clock System Entities Queue Future event list Statistics
state
t=1.5 #cusinque 1 List={} 1, t1=0: arriving cus
=0 2 1, t2=1: served
Server=1 2, t3=1.5: arriving
cus
17

Example: Single-Server Service Center

Interarrival customers
Service completion
Service time by Server

Arriving Customers in queue Server Departing

customer customer

current simulated time is CLOCK = 2 minutes

system state:
1. number of customers waiting to be served =?
2. indicate the Server as being idle or busy at time t=?
Clock System Entities Queue Future event list Statistics
state ID
t=2 #cusinque=1 1 List={2} 1, t1=0: arriving cus
Server=1 2 1, t2=1: served
3 2, t3=1.5: arriving cus
3, t4=2: arriving cus
18

8
 2/28/2024

Example: Single-Server Service Center

Interarrival customers
Service completion
Service time by Server

Arriving Customers in queue Server Departing

customer customer

current simulated time is CLOCK = 2.7 minutes

system state:
1. number of customers waiting to be served =?
2. indicate the Server as being idle or busy at time t=?
Clock System Entities Queue Future event list Statistics
state ID
t=2.7 #cusinque=2 1 List={2} 1, t1=0: arriving cus
Server=1 2 1, t2=1: served
3 2, t3=1.5: arriving cus
4 3, t4=2: arriving cus
3, t5=2.7: arriving19cus

Example: Single-Server Service Center

Interarrival customers
Service completion
Service time by Server

Arriving Customers in queue Server Departing

customer customer

current simulated time is CLOCK = 3.2 minutes

system state:
1. number of customers waiting to be served =?
2. indicate the Server as being idle or busy at time t=?

Clock System Entities Queue Future event list Statistics

state ID
t=2.7 #cusinque=? 1 List={2} 1, t1=0: arriving cus
Server=? 2 1, t2=1: served
3 2, t3=1.5: arriving cus
4 3, t4=2: arriving cus
3, t5=2.7: arriving20cus

9
 2/28/2024

Example: Single-Server Service Center

Customer in service

Arriving Customers in queue Server Departing

customer customer

• Performance measures of interest:

− Average customer waiting time
− Average number of customers in queue
− Average server utilization
• How do we simulate this system and obtain
measures of interest?
− Need to simulate “time” …
21

Time Advance Algorithm

• A discrete-event simulation proceeds by
producing a sequence of system snapshots over
time
• A snapshot of the system at a given time includes
− System state
− Status of all entities
− Status of all sets: Sets are used to collect required
information for calculating performance metrics
− Future event list (FEL)
− Statistics

10
 2/28/2024

Time-Advance Mechanisms
• Simulation clock: Variable that keeps the current
value of (simulated) time in the model
− Must decide on, be consistent about, time units
− Usually no relation between simulated time and (real)
time needed to run a model on a computer
• Two approaches for time advance
− Next-event time advance (usually used) … described
in detail below
− Fixed-increment time advance (seldom used) …
Described in Appendix 1A
– Generally introduces some amount of modeling
error in terms of when events should occur vs. do
occur
– Forces a tradeoff between model accuracy and
computational efficiency

See Chapter 1 (Simulation & Modeling)

Page 10 (29 / 800)

11
 2/28/2024

Fixed-Increment Time Advance

0 Δt 2Δt 3Δt 4Δt 5Δt 6Δt Time

e0 e1 e2

• Events occur at a fixed increment

• Events occurring between time increments must
be moved to an increment boundary
• Simple to implement, but not an accurate
realization of occurrence of events

27

Next-event Time Advance

• Initialize simulation clock to 0
• Determine times of occurrence of future events
– event list
• Clock advances to next event, which is
executed
− Event execution may involve updating event list
• Continue until stopping rule is satisfied (must be
explicitly stated)
• Clock “jumps” from one event time to the next,
and doesn’t “exist” for times between successive
events … periods of inactivity are ignored

28

12
 2/28/2024

Next-event time-Advance (cont’d.)

• Consider the single-server service center example

ti = time of arrival of ith customer (t0 = 0)
Ai = ti – ti-1 = interarrival time between (i-1)st and ith
customers
Si = time spent serving the ith customer
Di = delay in queue of ith customer
Ci = ti + Di + Si = time ith customer completes service
and departs

30

Problem Statement

• Recall single-server queueing model

• Assume interarrival times are
independent and identically distributed
(IID) random variables
• Assume service times are IID, and are
independent of interarrival times
• Queue discipline is FIFO
• Start empty and idle at time 0
• First customer arrives after an interarrival
time, not at time 0
• Stopping rule: When nth customer has
completed delay in queue (i.e., enters
service) … n will be specified as input

13
 2/28/2024

Problem Statement (cont’d.)

• Quantities to be estimated
− Expected average delay Di in queue (excluding service time) of the n
customers completing their delays
− Expected average number of customers Q(t) in queue (excluding any
in service)
– A continuous-time average
– Area under Q(t) = queue length at time t, divided by T(n) = time
simulation ends … see book for justification and details
− Expected utilization (proportion of time busy) B(t) of the server
– Another continuous-time average
– Area under B(t) = server-busy function (1 if busy, 0 if idle at time t),
divided by T(n)
• Important: Discrete-time vs. continuous-time statistics

Performance Measures

• “Expected” average delay in

^ 1 n
d (n)   Di
queue (excluding service time)
of the n customers completing
their delays n i 1
• Expected average number of T (n)
^ 1 1 
customers in queue (excluding
any in service)
q ( n) 
T ( n)  Q (t )   iTi
T (n) i 1
0
 A continuous-time average

T (n)
• Expected utilization (proportion ^ 1
of time busy) of the server
 Another continuous-time
u ( n) 
T ( n)  B(t )
0
average

33

14
 2/28/2024

Hand Simulation of a Single Server Service

Center
• Interarrival times (all times are in minutes):
0.4, 1.2, 0.5, 1.7, 0.2, 1.6, 0.2, 1.4, 1.9, 2
• Service times:
2.0, 0.7, 0.2, 1.1, 3.7, 0.6, 0.2, 0.6, 0.4, 0.4
• n = 5 delays in queue desired
• Mô phỏng bằng tay (“Hand” simulation) theo bảng mẫu
được cung cấp, trong đó
− Thể hiện: system, state variables, clock, event list, statistical
counters … sau mỗi sự kiện xảy ra (event)
− Sử dụng dữ liệu phía trên để thực hiện từng bước mô phỏng (rời
rạc)
− Dừng mô phỏng khi số delays n = 5 hoặc sử dụng hết dữ liệu được
cung cấp
− Tính các chỉ số hiệu năng hệ thống (output performance measures)
• Tham khảo bài đọc Event-Driven Hand Simulation, từ
trang 35 đến trang 40, textbook Simulation with Arena
by W. David Kelton

34

15
 2/28/2024

Assignment 5

16