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