0% found this document useful (0 votes)

114 views33 pages

CPSC 531: Discrete-Event Simulation Overview

This document provides an overview of discrete-event simulation (DES) and the simulation of a single-server service center. It discusses key concepts in DES including events, the simulation clock, time advance mechanisms, event routines, and performance measures. It also provides an example of a hand simulation of a single-server service center to demonstrate the simulation process and output over time as different events occur.

Uploaded by

browniezboy

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

114 views33 pages

CPSC 531: Discrete-Event Simulation Overview

Uploaded by

browniezboy

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

CPSC 531:Discrete-Event Simulation

Instructor: Anirban Mahanti

Office: ICT 745
Email: mahanti@[Link]
Class Location: TRB 101
Lectures: TR 15:30 – 16:45 hours
Class web page:
[Link]
C531/
Notes derived from “Simulation Modeling
and Analysis” by A. Law and W. Kelton,
Third edition, McGraw Hill, 2000.

CPSC 531: DES Overview 1

Objective
 Learn the basics of discrete-event simulation
 We will focus on a simple single-server service
center. Possible examples:
 Convenience store: customers, cashiers
 Airport: runways, airplanes

Customer in service

Arriving Departing
Customers in queue Server
customer customer

CPSC 531: DES Overview 2

What is Discrete-Event Simulation (DES)?
 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
 What is an event? Instantaneous occurrence
that may change the state of the system
 Arrivalof a customer
 Service completion (and departure) of a customer
 End of simulation (a “fake” event)

CPSC 531: DES Overview 3

Single-Server Service Center
Customer in service

Arriving Customers in Server Departing

customer queue 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” …
CPSC 531: DES Overview 4
Time Advance Mechanism
 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
 Fixed-increment time advance
 Next-event time advance

CPSC 531: DES Overview 5

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

CPSC 531: DES Overview 6

Next-event Time Advance
 Initialize simulation clock to 0
 Determine times of occurrence of future
events – event list
 Clock advances to next (most imminent) 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
CPSC 531: DES Overview 7
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

CPSC 531: DES Overview 8

Want to write a next-event program?
 Determine the events and understand what
happens when it occurs
 Generate events and keep a time-ordered list
of the events
 Based on the time-ordered list, we will have to
schedule events
 Track information of interest during the
simulation
 Finally, generate report when simulation ends

CPSC 531: DES Overview 9

Components of a DES Program
 Simulation clock – current value of simulated
time
 System state – variables to describe state
 Server status, number in queue, arrival times, etc
 Event list – times of future events for each
event type
 Statistical counters – to accumulate
performance measures
 Waiting time in queue, server utilization, …

CPSC 531: DES Overview 10

Components of a DES Program (cont’d.)

 Initialization routine
 Start simulation at time 0
 Timing routine
 determines next event time, type; advances clock
 Event routines
 carry out logic for each event type
 Library routines
 utility routines to generate random variates, etc.
 Report generator
 Main program
 tiesroutines together, executes them in the
correct order
CPSC 531: DES Overview 11
Organization of a DES Program
Start

Initialization Timing
Routine Main Routine Routine

Event Library
Routines Routines

Yes No
Report Simulation
Generator Done?

Stop
CPSC 531: DES Overview 12
DES Program Flow
Start

Initialization
Routine Main Routine

1. Set clock = 0
2. initialize state &
counters
3. Initialize event list
4. Return to main program
CPSC 531: DES Overview 13
DES Program Flow

Timing
Main Routine Routine

1. Determine next event

type i
2. Advance simulation
clock
3. Return to main program

CPSC 531: DES Overview 14

DES Program Flow
Main Routine

Library
Event routine i Routine

1. update system state

2. update counters
3. generate future events
& add them to the
event list

CPSC 531: DES Overview 15

DES Program Flow

Timing
Main Routine Routine

Event
Routines

No
Simulation
Done?
Return to main;
Invoke timing
routine

CPSC 531: DES Overview 16

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, …
 service times: 2.0, 0.7, 0.2, 1.1, 3.7, 0.6, …
 n = 6 delays in queue desired
 “Hand” simulation:
 Display system, state variables, clock, event list,
statistical counters … all after execution of each
event
 Use above lists of interarrival, service times to
“drive” simulation
 Stop when number of delays hits n = 6, compute
output performance measures

CPSC 531: DES Overview 17

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

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