Basic Simulation Modeling
The nature of simulation
Systems, Models and Simulation
Discrete-Event Simulation
Simulation of a single-server queuing
system
Steps in a sound simulation study
Advantages, disadvantages and pitfalls of
simulation
Basic Simulation Modeling
Conceptions
The Nature of Simulation
Simulation course is about techniques for using computers to
imitate or simulate the operations of various kinds of real world
facilities or processes
Conceptions
Application areas
Academic level
Impediments
System: the facility or process of interest
Model: a set of assumptions about how the system works, which
usually take the form of mathematical or logical relationships,
constitute a model that is used to try to gain more understanding
of how the corresponding system behaves.
Analytic soulution: to obtain exact information on questions of
intresets.
Simulation: use a computer to evaluate a model numerically,
and data are gathered in order to estimate the desired true
characteristics of the model.
3
MAK_Stat_RU
Application areas
Example
a manufacturing company contemplates building
a large extension onto one of its plants, but is
not sure if the potential gain in productivity would
justify the construction cost.
Designing and analyzing manufacturing systems
evaluating military weapons systems or their logistics requirements
determining hardware requirements or protocols for communication
networks
Determining hardware and software requirements for a computer
system
Designing and operating transportation systems such as airports,
freeways, ports and subways
Evaluating designs for service organizations such as call centers,
fast-food restaurants, hospitals, and post offices
Reengineering of business processes
Determining ordering polices for an inventory system
Analyzing financial or economic systems
6
Academic level
Impediments
Winter Simulation Conference (600-700 people every year)
Is one of the three important operations-research
techniques (in serveys related to the use of operations
research techniques: math programming, statistics,
simulation)
The second only to math programming among 13
techniques considered (in 1294 papers from the journal
Interfaces from 1970 through 1992)
MAK_Stat_RU
Models used to study large-scale systems tend to be very
complex, and writing computer programs to execute them
can be an arduous task indeed. (excellent software products)
Large amount of computer time is sometimes required.
(cheaper and faster computer)
An unfortunate impression that simulation is just an exercise
in computer programming, albeit a complicated one.
(attitude, simulation methodology)
Systems, Models and Simulation
Continue...
System is defined to be a collection of entities, e.g., people or
machines, which act and interact together toward the
accomplishment of some logical end.
System depends on the objectives of a particular study.
State of a system: collection of variables necessary to describe a
system at a particular time, relative to the objectives of a study.
(the number of busy tellers, the number of customers in the bank,
the time of arrival of each customer in the bank)
Study on a system: try to gain some insight into
the relationships among various components, or to
predict performance under some new conditions
being considered.
Ways to study a system
discrete system: the state variables change instantaneously
at separated points in time. (a bank, e.g., the number of
customers in the bank)
continuous system: the state variables change continuously
with respect to time. (an airplane moving through the air, e.g.,
position and velocity )
10
Example
System
Experiment with
the actual system
One study on a bank to determine the number of tellers
needed to provide adequate service for customers who
want just to cash a check or make a savings deposite,
the system can be defined to be that portion of the bank
consisting of the tellers and the customers waiting in line
or being served.
If the loan officer and the safety deposite boxes are to be
included, the definition of the system must be expanded
in an obvious way.
Experiment with a
model of the system
Physical model
Mathematical model
Analytical solution
Simulation
11
MAK_Stat_RU
12
Definitions
Discrete Event Simulation
Definition
Time-Advance Mechanisms
Components and Organization of a Discrete-Event
Simulation Model
Components
Discrete-event simulation concerns the modeling of a
system as it evolves over time by a representation in
which the state variables change instantaneously at
separate points in time. Or the system can change at only
a countable number of points in time.
Event is defined as an instantaneous occurrence that may
change the state of the system.
Logic Organization.
13
14
Time-Advance Mechanism
Example 1.1
Single-server queuing system: a barbershop, to
estimate the (expected) average delay in queue (line) of
arriving customers
State variables: the status of the server (busy or
idle), the number of customers waiting in queue to be
served, the time of arrival of each person waiting in
queue.
Events: the arrival of a customer and the completion
of service for a customer, which results in the
customers departure.
15
MAK_Stat_RU
Simulation clock: the variable in a simulation model that
gives the current value of simulated time.
to keep track of the current value of simulated time as
the simulation proceeds
to advance simulated time from one value to another
Advancing the simulation clock
next-event time advance (mostly used)
fixed-increment time advance (a special case of the first)
Next-event time-advance approach
simulation clock is initialized to zero
the times of occurrence of future events are determined.
16
Example 1.2
Notations:
: time of arrival of the ith customer ()
: inter-arrival time between (i-1)st and ith arrivals of
customers
e1
e0
: time that server actually spends serving ith customer
(exclusive of customers delay in queue)
: delay in queue of ith customer
: time that ith customer completes service and departs
: time of occurrence of ith event of any type (ith value the
simulation clock takes on, excluding the value )
e4
e5
t2
t3
c2
Time
t1
A1
e2 e3
A2
c1
A3
S1
S2
18
17
Components and Organization of a Discrete -Event
Simulation Model
Continue...
Initialization routine: A subprogram to initialize the
Components (10)
simulation model at time 0
Systems state: The collection of state variables
Timing routine: A subprogram that determines the
necessary to describe the system at a particular
time
Simulation clock: A variable giving the current
value of simulated time
Event list: A list containing the next time when
each type of event will occur
Statistical counters: Variables used for storing
statistical information about system performance
next event from the event list and then advances the
simulation clock to the time when that event is to occur
19
MAK_Stat_RU
Event routine: A subprogram that updates the system
state when a particular type of event occurs (there is
one event routine for each event type)
Library routines:
A set of subprograms used to
generate random observations from probability
distributions that were determined as part of the
simulation model
20
Continue...
Start
Initialization routine
Report generator: A subprogram that computes
estimates (from the statistical counters) of the desired
measures of performance and produces a report
when the simulation ends
Main program
Time routine
1. Set simulation
0. Invoke the initialization routine
0
clock=0
2. Initialize system state
1. Invoke the timing routine
and statistical counters
Repeatedly
2. Invoke event routine
3. Initialize event list
2
Event routine i
1.Update system state
2.Update statistical counters
3.Generate future events and add to
event list
Main program: A subprogram that invokes the timing
routine to determine the next event and then transfers
control to the corresponding event routine to update
the system state appropriately. The main program
may also check for termination and invoke the report
generator when the simulation is over.
Is
simulation
over?
1. Determine the next
event type, say, i
2. Advance the
simulation clock
Library routines
Generate random
variates
No
Report generator
Yes
1. Compute estimates of interest
2. Write report
Stop
21
22
Components of a queueing system
1.
Simulation of A Single-Server
Queueing System
2.
3.
23
MAK_Stat_RU
Arrival process:
Inter-arrivals: Ai
Mean interarrival time: E(A)
Arrival rate: = 1 / E(A)
Service mechanism
Service time: Si
Number of servers: s
Mean service time: E(S)
Service rate: = 1 / E(S)
Queue discipline
FIFO
LIFO
Priority
* D. Gross, and C.M. Harris, Fundamentals of Queuing Theory,
3rd ed., John Wiley, New York, 1998
24
Notation for queueing systems
GI/G/s queue
1.
s servers in parallel and one FIFO queue feeding all servers
GI (general independent): the distribution of the Ais
2.
A1, A2, are IID random variables
G (general): the distribution of the Sis
3.
S1, S2,are IID random variables
4.
The Ais and Sis are independent
Symbols: M (exponential),
(deterministic times)
. . .
Ek
(k-Erlang),
M/M/1: a single-server queueing system with exponential
inter-arrival and service times and a FIFO discipline
= /(s) : the utilization factor of the queueing system
FIGURE 1.71
A GI/G/s queue
26
25
Measures of Performance for Queueing Systems
Di : delay in queue of ith customer
A departure customer
Wi = Di + Si : waiting time in system of ith customer
Q(t) : number of customers in queue at time t
Server
L(t) : number of customers in system at time t [Q(t) plus number of
customers being served at time t]
Customer in service
lim
lim
Customers in queue
w.p.l : steady-state time-average number in queue
lim
w.p.l : steady-state time-average number in system
FIGURE 1.4 : A single-server queueing system.
MAK_Stat_RU
Q
27
w.p.l : steady-state average waiting time
lim
An arrival customer
w.p.l : steady-state average delay
d and L =
d + E(S)
28
e1, e2, , e13 : 13 successive events
n=6 : delays in queue
Measures of Performance for the example
Interarrival times:
: delay in queue of ith customer
A1=0.4, A2=1.2, A3=0.5, A4=1.7, A5=0.2,
: the expected proportion of the time that Q(t) is equal to i
: number of customers in queue at time t
A6=1.6, A7=0.2, A8=1.4, A9=1.9,
The expected average delay in queue
Service times:
The expected average number of customers in queue
S1=2.0, S2=0.7, S3=0.2, S4=1.1, S5=3.7, S6=0.6,
29
Q(t)
30
Measures of Performance for the example
The expected utilization of the server
1
0
e1=0.4
Arrivals
e2=1.6
e8=4.0
e3=2.1
e7=3.8
e11=5.8
e10=5.6
e12=7.2
e6=3.3
Departures
e4=2.4 e5=3.1
e9=4.9
e13=8.6=T(6)
FIGURE 1.5
Q(t), arrival times, and departure times for a realization of a single-server queueing system.
MAK_Stat_RU
31
32
B(t)
Intuitive Explanation
1
0
e1=0.4
Arrivals
e2=1.6
e11=5.8
e10=5.6
e8=4.0
e3=2.1
e7=3.8
e12=7.2
e6=3.3
Departures
e4=2.4 e5=3.1
e13=8.6=T(6)
e9=4.9
FIGURE 1.6
B(t), arrival times, and departure times for a realization of a single-server queueing system.
33
Initialization
time = 0
Arrival
time = 0.4
System state
Sever
status
Time
of last
event
0.4
Event list
Number
in
Times
queue
of
arrival
Sever
status
Area
Number Total
Area
delayed delay under Q(t) under B(t)
Computer Representation
System
Event list
0.4
Number
in
Times
queue
of
arrival
Time
of last
event
Statistical counters
1
Area
Area
Number Total
delayed delay under Q(t) under B(t)
Computer Representation
(b)
(a)
35
MAK_Stat_RU
D 2.4
Clock
1
Statistical counters
0
A 1.6
0.4
Clock
0
System state
A 0.4
0
System
34
36
Arrival
time = 1.6
Arrival
time = 2.1
System state
1.6
0.4
1
1.6
Sever
status
Time
of last
event
0.4
Event list
1.6
Number
in
Times
queue
of
arrival
Statistical counters
1
1.6
1.2
Sever
status
2.1
Area
Number Total
Area
delayed delay under Q(t) under B(t)
Computer Representation
System
A 3.8
2.1
D 2.4
Clock
System state
A 2.1
1.6
1.6
2.1
D 2.4
Clock
Event list
2.1
Number
in
Times
queue
of
arrival
Time
of last
event
Statistical counters
1
0.5
1.7
Area
Area
Number Total
delayed delay under Q(t) under B(t)
Computer Representation
System
(c)
(d)
37
Departure
time = 2.4
Departure
time = 3.1
System state
2.1
1.6
1
System
Sever
status
2.4
Number
in
Times
queue
of
arrival
Time
of last
event
2.1
Event list
0.8
1.1
Sever
status
2.0
Area
Number Total
Area
delayed delay under Q(t) under B(t)
Computer Representation
System
(e)
3.1
Number
in
Times
queue
of
arrival
Time
of last
event
Event list
Statistical counters
3
1.8
1.8
2.7
Area
Number Total
Area
delayed delay under Q(t) under B(t)
Computer Representation
(f)
39
MAK_Stat_RU
D 3.3
Clock
1
Statistical counters
2
A 3.8
3.1
D 3.1
Clock
System state
A 3.8
2.4
2.1
38
40
10
Arrival
time = 3.8
Departure
time = 3.3
System state
Sever
status
3.3
Number
in
Times
queue
of
arrival
Time
of last
event
3.8
Event list
1.8
1.8
Sever
status
2.9
Area
Number Total
Area
delayed delay under Q(t) under B(t)
Computer Representation
System
D 4.9
Clock
1
Statistical counters
3
A 4.0
3.8
Clock
0
System state
A 3.8
3.3
3.8
Number
in
Times
queue
of
arrival
Time
of last
event
Event list
Statistical counters
4
1.8
1.8
2.9
Area
Number Total
Area
delayed delay under Q(t) under B(t)
Computer Representation
System
(h)
(g)
41
Departure
time = 4.0
Departure
time = 4.9
System state
4.0
3.8
1
System
Sever
status
4.0
Number
in
Times
queue
of
arrival
Time
of last
event
4.0
Event list
1.8
1.8
Sever
status
3.1
Area
Number Total
Area
delayed delay under Q(t) under B(t)
Computer Representation
System
(i)
4.9
Number
in
Times
queue
of
arrival
Time
of last
event
Event list
Statistical counters
5
2.7
2.7
4.0
Area
Number Total
Area
delayed delay under Q(t) under B(t)
Computer Representation
(j)
43
MAK_Stat_RU
D 8.6
Clock
1
Statistical counters
4
A 5.6
4.9
D 4.9
Clock
System state
A 5.6
4.0
4.0
42
44
11
Arrival
time = 5.6
Arrival
time = 5.8
System state
5.6
4.0
1
5.6
Sever
status
5.6
Number
in
Times
queue
of
arrival
Time
of last
event
4.0
Event list
Statistical counters
5
2.7
2.7
5.6
4.7
Sever
status
5.8
Area
Number Total
Area
delayed delay under Q(t) under B(t)
Computer Representation
System
A 7.2
5.8
D 8.6
Clock
System state
A 5.8
5.6
5.6
5.8
D 8.6
Clock
5.8
Number
in
Times
queue
of
arrival
Time
of last
event
Event list
Statistical counters
5
2.7
2.9
4.9
Area
Area
Number Total
delayed delay under Q(t) under B(t)
Computer Representation
System
(k)
(l)
45
Arrival
time = 7.2
Departure
time = 8.6
System state
4.0
1
5.8
7.2
System
Sever
status
5.6
5.8
7.2
7.2
Time
of last
event
5.6
Event list
Statistical counters
5
2.7
5.7
5.8
6.3
7.2
Area
Area
Number Total
delayed delay under Q(t) under B(t)
Computer Representation
System
(m)
Sever
status
5.8
7.2
D 9.2
Clock
8.6
Number
in
Times
queue
of
arrival
Time
of last
event
Event list
Statistical counters
6
5.7
9.9
7.7
Area
Area
Number Total
delayed delay under Q(t) under B(t)
Computer Representation
(n)
47
MAK_Stat_RU
A 9.1
8.6
D 8.6
Clock
Number
in
Times
queue
of
arrival
System state
A 9.1
7.2
5.6
46
48
12
1.4.3 Program Organization and Logic
Comments
Interaction between the simulation clock and the event list
Why general-purpose language
Model being simulated: M/M/1 queue
Process updates of the state variables and statistical counters
n=1000
Interarrival and service times
Contingencies
A departing customer could leave behind an empty queue
Termination conditions
Interarrival: exponential distribution (mean=1 min)
Service: exponential distribution (mean=0.5 min)
Time ties
49
Arrival
Event
Is
the server
busy?
Write error
Yes
message and stop
simulation
Yes
No
Set delay=0
for this customer
and gather statistics
Add 1 to the
number in queue
Departure
Event
FIGURE 1.8
Flowchart for arrival routine, queueing model
Schedule the next
arrival event
Yes
50
Is
the queue
empty?
No
Subtract 1 from
the number
in queue
Eliminate departure
event from
consideration
Compute delay of
customer entering service
and gather statistics
Add 1 to the
number of customers
delayed
Make the
server busy
Store time of
arrival of this
customer
Schedule a
departure event
for this customer
Schedule a
departure event
for this customer
Return
MAK_Stat_RU
No
Make the server idle
Add 1 to the
number of
customers delayed
Is
the queue
full?
FIGURE 1.9
Flowchart for arrival routine, queueing model
Move each customer
in queue (if any) up
one place
51
Return
52
13
C Program for Queueing Model
Simulation Output and Discussion
(Fig 1.19 Fig. 1.27)
(Fig. 1.28 Output report, queueing model)
Single-server queueing system
External definitions
Main functions
Function initialize
Function timing
Function arrive
Function departure
Function report
Function update_avg_stats
Function expon
Mean interarrival time
Mean service time
Number of customers
1.000 mins
0.500 mins
1000
Average delay in queue
Average number in queue
Server utilization
Time simulation ended
0.430 mins
0.418
0.460
1027.915 mins
53
Alternative Stopping Rules
54
Determining the Events and Variables
(Fig. 1.33 Fig. 1.37)
Event-graph
Stop: fixed run time 480 mins
External definitions
Main functions
Function initialize
Function report
Output report
Arrival
FIGURE 1.38
Event graph, queueing model
55
MAK_Stat_RU
Departure
56
14
Determining the Events and Variables
Determining the Events and Variables
Event-graph
Event-graph
Arrival
Arrival
Enter
service
Departure
Departure
End
simulation
FIGURE 1.39
Event graph, queueing model with separate enter-service event
FIGURE 1.40
Event graph, queueing model with fixed run length
57
58
STEPS
STEPS IN A SOUND SIMULATION STUDY
1. Formulate the problem and plan the study
a. Problem of interest is stated by manager.
b. One or more kickoff meeting for the study are conducted,
with the project manager, the simulation analysts, and
subject-matter experts (SMEs) in attendance. The
following issues are discussed:
Overall objectives of the study
Specific questions to be answered by the study
Performance measures that will be used to evaluate the
effeciency of different system configurations
Scope of the model
System configurations to be modeled
Software to be used
Time frame for the study and the required resources 59
MAK_Stat_RU
2. Collect data and define a model.
a. Collect information on the system layout and operating procedures.
No single person or document is sufficient.
Some people may have inaccurate information---make sure that ture SMEs are identified.
Operating procedures may not be formalized.
b. Collect data (if possible) to specify model parameters and input probability distributions
c. Delineate the above information and data in an assumptions document, which is the
conceptual model
d. Collect data (if possible) on the performance of the existing systsem (for validation purpose
in Step 6)
e. The level of model detail should depend on the following:
Project objectives
Performance measures
Data availability
Credibility concerns
Computer constraints
Opinions of SMEs
Time and money constraints
f.
There need not be a one-to-one correspondence between each element of the model and
the corresponding element of the system.
g. Interact with the manager (and other key project personnel) on a regular basis
60
15
STEPS
STEPS
3. Is the conceptual model valid?
5. Make pilot runs.
a. Make pilot runs for validation purposes in Step 6.
a. Perform a structured walk-through of the conceptual model using the
assumptions document before an audience of managers, analysts, and
SMEs
Helps ensure that the models assumptions are correct and complete
Promotes ownership of the model
Take place before programming begins to avoid significant
reprogramming later
4. Construct a computer program and verify.
a. Program the model in a programming language or in simulation
software. Benefits of using a programming language are that one is
often known, they have a low purchase cost, and they may result in a
smaller model execution time. The use of simulation software, on the
other hand, reduces programming time and results in a lower project
cost.
b. Verify (debug) the simulation computer program.
6. Is the programed model valid?
a. If ther is an existing system, then compare model and system (from
Step 2) performance measures for existing system
b. Regardless of whether there is an existing system, the simulation
analysts and SMEs should review the model results for correctness.
c. Use sensitivity analyses to determine what model factors have a
significant impact on performance measures and, thus, have to be
modeled carefully.
7. Design experiments.
a. Specify the following for each system configuration of interest:
Length of each run
Length of the warmup period, if one is appropriate
Number of independent simulation runs using different random numbers--facilitates construction of confidence intervals
61
62
Formulate problem
and plan the study
STEPS
Collect data and
define a model
8. Make production runs.
Conceptual
model valid?
a. Production runs are made for use in Step 9.
9. Analyze output data.
Yes
Construct a computer
program and verify
a. Two major objectives in analyzing output data are:
Determining the absolute performance of certain system configurations
Comparing alternative system configurations in a relative sense
Make pilot runs
10. Document, present, and use results.
Programmed
Model valid?
a. Document assumptions (see Step 2), computer program, and studys
results for use in the current and future projects.
b. Present studys results.
No
Yes
Design experiments
Use animation to communicate model to managers and other people who
are not familiar with all of the model details.
Discuss model building and validation process to promote credibility.
c. Results are used in decision-making process if they are both valid and
credible.
63
MAK_Stat_RU
No
Make production runs
FIGURE 1.68
Steps in a simulation study.
Analyze output data
Document, present,
and use results
64
16
ADVANTAGES OF SIMULATION
DISADVANTAGES OF SIMULATION
Most complex, real-world systems with stochastic elements cannot be
accurately described by a mathematical model that can be evaluated
analytically. Thus, a simulation is often the only type of investigation
possible.
Simulation allows one to estimate the performance of an existing system
under some projected set of operating conditions.
Alternative proposed system designs (or alternative operating policies for a
single system) can be compared via simulation to see which best meets a
specified requirement.
In a simulation we can maintain much better control over experimental
conditions than would generally be possible when experimenting with the
system itself.
Simulation allows us to study a system with a long time frame---e.g., an
economic system---in compressed time, or alternatively to study the
detailed workings of a system in expanded time.
65
Pitfalls to the successful completion of
a simulation study
Pitfalls to the successful completion of a
simulation study
Failure to have a well-defined set of objectives at the beginning of
the simulation study
Inappropriate level of model detail
Failure to communicate with management throughout the course of
the simulation study
Misunderstanding of simulation by management
Treating a simulation study as if it were primarily an exercise in
computer programming
Failure to have people with a knowledge of simulation methodology
and statistics on the modeling team
Failure to collect good system data
Inappropriate simulation software
Obliviously using simulation software products whose complex
marco statement may not be well documented and may not
implement the desired modeling logic
67
MAK_Stat_RU
Each run of a stochastic simulation model produces only
estimates of a models true characteristics for a particular set
of input parameters. If a valid analytic model is available or
can be easily de developed, it will generally be preferable to a
simulation model.
Simulation models are often expensive and time-consuming to
develop.
If a model is not a valid representation of a system under
study, the simulation results, no matter how impressive they
appear, will provide little useful information about the actual
system.
In some studies both simulation and analytic models might
be useful. In particular, simulation can be used to check the
validity of assumptions needed in an analytic mode. On the
other hand, an analytic model can suggest reasonable
66
alternatives to investigate in a simulation study.
Belief that easy-to-use simulation packages, which require little or
no programming, require a significantly lower level of technical
competence
Misuse of animation
Failure to account correctly for sources of randomness in the actual
system
Using arbitrary distributions (e.g., normal, uniform, or trianglar) as
input to the simualation
Analyzing the output data from one simulation run (replication) using
formulas that assume independence
Making a single replication of a particular system design and treating
the output statistics as the true answers
Comparing alternative system design on the basis of one replication
for each design
Using the wrong performance measures
68
17
Notes
Tarea 1: Simulation of a Single server queueing system
In some studies both simulation and
analytic models might be useful. In
particular, simulation can be used to
check the validity of assumptions needed
in an analytic model. On the other hand,
an analytic model can suggest reasonable
alternatives to investigate in a simulation
study.
Modify the code for the single-server queue in Chapter 1 to
compute and write in addition the following measures of
performance:
69
MAK_Stat_RU
1.
The time-average number in the system
2.
The average total time in the system
3.
The maximum queue length
4.
The maximum delay in quque
5.
The maximum time in the system
6.
The proportion of customers having a delay in queue in excess of 1 minute
Entegar: report on the simulation including simulation model description, design of
the experiments, results of above measures after the simulation, conclusion on
the simulation, and program code.
Fecha limite: 18 de Febrero de 2005
70
18
