Discrete event simulation
P.J. Drongowski
26 November 2004
Simulation and modelling
* Important for business and engineering analysis
* Build a computer-based model that mimics a real-world situation
+ Perform experiments to improve system design
+ Cheaper to build model than perform real-world experiments
+ Faster to implement experiments
+ Try variations on system design -- "What if?"
* Run and observe model, take measurements
* Time is an important dimension in analysis
Kinds of models
* Continuous system model
+ Attempts to model real-world "analog" behavior
+ Time advances in very small steps of (non-)uniform duration
+ Based upon mathematical model (PDEs, linear equations, etc.)
+ Examples: electronic circuits, heat transfer
* Discrete-event model
+ System behavior is characterized by events
- An event is a significant action
- Events start and end at known times
- Simulation proceeds from event to event
+ Time advances in discrete steps of non-uniform duration
from event to event
+ Event time and duration is frequently determined according to
random distribution
+ Examples
- Job scheduling (factories, OS processes, network packets)
- Customer service (waiting lines)
- Telecommunications (phone calls)
Kinds of objects
* Simulation inspired object-oriented design and programming
* Five main kinds of objects:
+ Job
- Represents an entity that moves through the system
- Example: Job to be performed, customer, data packet
+ Source
- New jobs enter the system through a source
+ Server
- A server processes a job in some way
- Example: Machine, bank teller, router
+ Queue
- A job awaits service in a queue
+ Sink
- Existing jobs leave the system through a sink
Kinds of events
* Arrival event
+ A new job arrives into the system
+ Example: A new customer or job arrives
* Departure event
+ An existing job leaves the system
+ Example: A customer or job is finished and leaves
* Start service
+ A server begins to service a job
+ Example: An idle teller begins to handle a customer transaction
* End service
+ A server completes a job
+ Example: The teller finishes a transaction
* Enter waiting line (queue)
+ An existing job must wait for an idle server
+ Example: A customer must wait for a teller
* Exit waiting line (queue)
+ A job leaves a queue to go to an idle server
+ Example: A customer walks up to an idle teller
Events and the event list
* Event model
+ Kind of event
+ Event time
+ Participant such as job or server
* Event list
+ Future events are kept on an "event list"
+ Events are kept in order from earliest to latest
+ Plays a key role in simulation control and advancement of time
Discrete-event simulation
* Simulation proceeds by scheduling and handling events
* Simulation terminates when:
+ A certain amount of simulated time has past
+ A certain number of jobs have been processed
* Basic simulation algorithm
+ Create the event list
+ Create initial objects
- Sources
- Servers
- Queues (waiting lines)
- Sinks
+ Generate the first arrival event for each source and
put the arrival events in the event list
+ While simulated time is less than the termination time:
- Remove the first event from the event list
- Advance simulated time to the time of that event
- Perform the activity specified by the event type
* The "controller" implements the simulation algorithm
Variations
* Number of queues
+ Single queue feeding multiple servers
+ One queue per server
* Queueing strategy
+ First come, first served
+ Priority
+ Longest queue first
+ Preemption (interrupt job being serviced in favor of other job)
+ Reneging (job leaves the waiting line)
* Job routing
+ Finished job leaves system
+ Jobs recirculate (feedback)
+ Probabilistic routing
Characteristics to measure and analyze
* Job transit time
+ How long did it take for a job to progress from arrival
to departure?
+ What is the distribution of job transit times?
* Job waiting time
+ How long did jobs wait in a queue?
+ What is the distribution of job waiting times?
* Queue length
+ What was the average queue length?
+ What was the maximum queue length?
* Service time
+ How long did it take to serve a job?
+ What is the distribution of service times?
* Server utilization
+ What percentage of simulated time was a server busy?
+ What percentage of simulated time was a server idle?
Descriptive statistics
* Quantitative measurement of system behavior
* A "sample" is a single observation
* Samples are tallied (accumulated) for post-processing after
the simulation run
+ Running sum
+ Running sum of squares
+ Running sum of busy intervals (i.e., duration of activity)
+ Bins to tally frequency of occurence of sample value
+ Object timestamps to remember service start time, queue entry time, etc.
* Typical numeric measurements
+ Number of samples (observations)
+ Minimum sample
+ Maximum sample
+ Mean
- (Sum of samples) / (number of samples)
+ Variance
- ((Sum of squares) - (mean*mean)) / (number of samples)
+ Standard deviation
- Square root of the variance
+ Coefficient of variation
- Measures the degree to which samples are dispersed about the mean
- Zero means no dispersal (constant)
- (Standard deviation) / (mean)
+ Utilization
- (Busy time) / (total simulated time)
* Post-processing
+ Display numeric summary statistics
+ Display histogram
- Shows frequency of occurence of samples graphically
- Can see the shape / distribution of sample values
Arrival patterns
* Real systems have fluctuations in arrival rate
+ Random fluctuations (customers do not arrive like clockwork!)
+ Time sensitive fluctuations (more customer during the lunch hour)
* Random variations
+ Measure real world arrival pattern to design simulation model
+ Define probability functions that describe the arrival pattern
* Characterization
+ Mean arrival rate, lambda (e.g., 35 customers per hour)
+ Mean interarrival time, Ta
+ lambda = 1 / Ta
* Arrival distribution
+ A(t) is the probability that an inter-arrival time is greater than t
+ F(t) is the cumulative distribution function (the probability that
an inter-arrival time is less than t)
+ A(t) = 1 - F(t)
* Possion arrival pattern
+ Arrival can occur randomly at any time
+ The next arrival is completely independent of the previous arrival
+ Inter-arrival times is exponentially distributed
-lamda*t
+ A(t) = e where lambda is the mean arrival rate
* Normal (or Gaussian) distribution
+ Completely symmetric around the mean
+ Is characterized by the mean and standard deviation
* Erlang distribution
+ Characteristizes telephone traffic
* Hyper-exponential distribution
Service time
* Service time may be constant or it may vary stochastically
* Characterization
+ Mean service time (Ts)
+ Mean service rate (mu)
* Exponential distribution
+ Service time is completely random
+ Service time of next job is completely independent of the previous job
Terminology
* If statistical properties of arrivals and service are independent of time,
the system is "stationary"
* If statistical properties are not independent of time, the system is
"nonstationary" or "time-variant"
+ May be dependent on time-of-day
+ May be dependent on queue length or some other factor
* Traffic intensity (rho)
+ rho = Ts/Ta = lambda/mu = (mean service time) / (mean interarrival time)
Pseudo-random number generation
* Need pseudo-random numbers to simulate stochastic system behavior
* Uniformly distributed integer numbers
* Basic technique: linear congruential method
+ Given: Three constants, a, b, and M
+ Generate a sequence of numbers, Ci, where Ci+1 = ((a * Ci) + b) mod M
+ C0 is the first number and is usually chosen by the user
+ C0 is called the "seed"
* Variants
+ M is determined by the length of an integer machine word
+ If b is zero, the method is called "additive"
+ If a is zero, the method is called "multiplicative"
* It is hard to choose good values of a, b, M and C0
+ Want sequence values that are uniformly distributed
+ Want extremely long "period" before the sequence values repeat
+ Try multiplicative method where a = 1220703125, M = 2^31-1
* Uniformly distributed floating point numbers
+ Generate uniformly distributed integer numbers
+ Divide by the maximum integer number allowed
+ Multiply by 0.4656613e-9 when M=2^31-1
Example: ANSI C standard
* Is an implementation suggested by the ANSI C standard
* It's offered as an example of a portable implementation
* It is *not* the best pseudo-random number generator
* The range of values is only 0..32767
static unsigned long int next = 1;
int rand(void) // RAND_MAX assumed to be 32767
{
next = next * 1103515245 + 12345;
return (unsigned int)(next/65536) % 32768;
}
void srand(unsigned int seed)
{
next = seed;
}
Non-uniformly distributed random numbers
* Can be derived from uniformly distributed random numbers
* Exponentially distributed floating point numbers
+ Simple method: Return value = - Ta * log( uniform )
- Ta: Mean Inter-arrival time
- uniform: Uniformly distributed random number
- log: Natural logarithm function
+ Longer method: Return value = -log( 1.0 - uniform ) / lambda
- lambda: Mean arrival rate
- uniform: Uniformly distributed random number
- log: Natural logarithm function
* Normal (Gaussian) distribution
+ Sum several (e.g., twelve) uniformly distributed random numbers
+ Return value = (sum - 6.0) * stddev + mean
- Sum: Sum of twelve uniformaly distributed random numbers
- stddev: Standard deviation of the normal distribution
- mean: Mean of the normal distribution