IST 3208: Modelling and Simulation
Module 2 General Principles
in Simulation
Discrete Event Simulation
Outline
▪ Concepts in discrete-event simulation
— Terminology and concepts
— Two pedagogical examples
▪ Components of discrete-event simulation
— Time advance approaches
— Event scheduling approach
▪ Manual simulation
— Grocery store example
▪ Simulation program
— Simulation of queueing systems
— Infinite and finite population model
▪ Verification and validation of simulation models
2
Components of a Queueing System
1. Arrival 2. Service time
process distribution
5. Service
discipline
4. Waiting
positions 3. Number of
servers
3
Arrival Definition
▪ Arrival time
— Time at which a customer arrives at a service facility
▪ Inter-arrival time
— Time between two successive arrivals to a service facility
▪ Arrival rate
— Number of arrivals per unit of time
4
Timing Diagram
5
Service Disciplines
Examples:
▪ First-Come-First-Serve (FCFS) (a.k.a. FIFO)
▪ Last-Come-First-Serve (LCFS)
▪ Round-Robin (RR) with a fixed quantum
Infinitesimal quantum ⇒ Processor Sharing (PS)
▪ Shortest Job First (SJF)
▪ Shortest Remaining Processing Time (SRPT)
▪ And many more…
6
Typical Performance Measures
▪ Response time
— Elapsed time from arrival to departure
▪ Waiting time
— Time spent in queue
▪ Number of customers in system
▪ Number of customers in queue
▪ Server utilization
— Proportion of time that the server is busy
▪ Throughput
— Rate at which customers leave the service facility after completing service
7
Utilization
■ Proportion of time that the server is busy
s1 s2 s3 s4 sn
••
Time
0 •
L
— Total busy time =
— U = proportion of time server is busy =
Note: U ≤ 1
8
Single Server Queue Example
time
Events arrival start service departure
Activities waiting receiving
in queue service
9
Single Server Queue Model
▪ Assumptions
— Inter-arrival times are independent of system state
— Inter-arrival times are iid (independent and identically distributed)
— Service times are independent of system state
— Service times are iid
— FCFS scheduling
— System is empty at time zero
— Arrival of first customer occurs after the first inter-arrival time
— Simulation terminates when the m-th customer starts service
10
Single Server Queue Model
11
Sequence of Events
C1 C2 C3
departures
serve
r
C1 C2 C3 C4 start
service
queue
0 1 3 4 6 9 10 11
arriva
l
C1 C2 C3 C4
Cj - customer j
time
number of 2
customers
in system 1
12
0 1 3 4 6 9 10 11
time
Manual Trace of Single Server Queue Example
clock event status n event list queue nw sw
0 -- idle 0 (A, 1) empty 0 0
1 A busy 1 (A, 3), (D, 4) empty 1 0
3 A busy 2 (D, 4), (A, 6) (C2, 3) 1 0
4 D busy 1 (A, 6), (D, 9) empty 2 1
6 A busy 2 (D, 9), (A, 11) (C3, 6) 2 1
9 D busy 1 (D, 10), (A, 11) empty 3 4
10 D idle 0 (A, 11) empty 3 4
11 A busy 1 (A, 15), (D, 17) empty 4 4
mean waiting time = sw/nw = 1.0
13
Notation: A - arrival event, D - departure event
(Cj, x) - customer j in queue, time of arrival of this customer is x
n - number of customers in system
Finite Population Model
▪ Assumptions
— Service times are iid and independent of system state
— Think times are iid and independent of system state
— FCFS scheduling
— System is empty at time zero
— For each of the N users, the first request is submitted after a think time
— Subsequent arrivals depend upon prior service completions
— Simulation terminates at time term_sim
14
Example: Tandem Queue with Blocking
15
Tandem Queue with Blocking
▪ Two stages
▪ Finite waiting room at stage 2 (number of customers in system < K)
▪ Blocking
— Server 1 is blocked if a customer completing service at stage 1 finds no queuing space
at stage 2
16
Tandem Queue with Blocking
▪ Subsystems and interaction
— 2 subsystems – one for each stage
— Server 1 is blocked if a customer completing service at stage 1 finds no queuing space
at stage 2
— If server 1 is in the “blocked” state, it becomes “not blocked” when a departure
occurs at stage 2
— A departure from stage 1 becomes an arrival to stage 2
17
Outline
▪ Concepts in discrete-event simulation
— Terminology and concepts
— Two pedagogical examples
▪ Components of discrete-event simulation
— Time advance approaches
— Event scheduling approach
▪ Manual simulation
— Grocery store example
▪ Simulation program
— Simulation of queuing systems
— Infinite and finite population model
▪ Verification and validation of simulation models
18
Verification and Validation
Abstraction = Simulation
System Model
Program
Validation Verification
19
Verification
▪ Increase the level of confidence in the correctness of simulation program
▪ Approaches
— Use a “trace” to debug simulation program
▪ Trace is obtained by printing state variables, statistical counters, etc., after each
event
— Verify simulation output using analytic results
20
Fundamental Results
▪ Use fundamental results of queuing systems
▪ Examples
— For any subsystem, mean arrival rate, mean number in system, and mean response
time must be consistent with Little’s formula
21
Analytic Results
▪ Check results for cases where analytic results are known
▪ Examples
— Simulation model: open networks with exponential interarrival time distribution and
uniform service time distribution
— Run simulation for the case of exponential service time distribution (analytic solution
is available)
— Verify if the simulation output is consistent with known analytic results
22
Validation
▪ Model should be “good enough” (subjective)
▪ Seek expert opinion on system components that need to be carefully modeled, e.g.,
bottleneck
▪ A model should be valid for the performance measures
▪ The most valid model may not be the most cost-effective model
23
Three Step Approach to Validation
1. Build a model with high face validity
— Appears to be reasonable to people who are knowledgeable about the system being
modeled
2. Validation of model assumptions
— Structural assumptions: entities, attributes, sets, etc.
— Data assumptions
▪ Collect reliable data
▪ Identify appropriate distribution
▪ Validate the assumed distribution
24
Three Step Approach to Validation
3. Validation of input-output relationship
— Model should be able to predict system behavior under existing conditions
Input Data
(from system Model Output Data
measurement) (from model)
=?
Output Data
(from system
measurement)
Could be done using historical data collected 25
for validation purposes.
