Discrete-Event SimulationDiscrete-Event Simulation:A First CourseSection 3.1 Discrete-Event SimulationSection 3.1 Discrete-Event Simulation Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Discrete-Event SimulationSection 3.1 Discrete-Event Simulationssq1 and sis1 are trace-driven discrete-event simulationsBoth rely on input data from an external sourceThese realizations of naturally occurring stochastic processesare limitedWe cannot perform “what if” studies without modifying thedataWe will convert the single server service node and the simpleinventory system to utilize randomly generated inputSection 3.1 Discrete-Event Simulation Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Discrete-Event SimulationSingle Server Service NodeWe need stochastic assumptions for service times and arrivaltimesAssume service times are between 1.0 and 2.0 minutesThe distribution within this range is unknownWithout further knowledge, we assume no time is more likelythan any otherWe will use a Uniform(1.0, 2.0) random variateSection 3.1 Discrete-Event Simulation Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Discrete-Event SimulationExponential Random VariatesIn general, it is unreasonable to assume that all possiblevalues are equally likely.Frequently, small values are more likely than large valuesWe need a non-linear transformation that maps 0.0 → 1.0 to0.0 → ∞.0.0 u 1.00.0xx = −µ ln(1 − u).......................................................................................................................................................................................................................................................................................................................................................................Section 3.1 Discrete-Event Simulation Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Discrete-Event SimulationExponential Random VariatesThe transformation is monotone increasing, one-to-one, and onto0 < u < 1 ⇐⇒ 0 < (1 − u) < 1⇐⇒ −∞ < ln(1 − u) < 0⇐⇒ 0 < −µ ln(1 − u) < ∞⇐⇒ 0 < x < ∞Generating an Exponential Random Variatedouble Exponential(double µ) /* use µ > 0.0 */{return (-µ * log(1.0 - Random()));}The parameter µ specifies the sample meanIn the single-server service node simulation, we use Exponential(µ)interarrival timesai= ai −1+ Exponential(µ); i = 1, 2, 3, . . . , nSection 3.1 Discrete-Event Simulation Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Discrete-Event SimulationProgram ssq2Program ssq2 is an extension of ssq1Interarrival times are drawn from Exponential(2.0)Service times are drawn from Uniform(1.0, 2.0)The program generates all first-order statistics ¯r, ¯w,¯d, ¯s,¯l, ¯q,and ¯xIt can be used to study the steady-state behaviorWill the statistics converge independent of the initial seed?How many jobs does it take to achieve steady-state behavior?It can be used to study the transient behaviorFix the number of jobs pro cessed and replicate the programwith the initial state fixedEach replication uses a different initial rng seedSection 3.1 Discrete-Event Simulation Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Discrete-Event SimulationExample 3.1.3The theoretical averages for a single-server service no de usingExponential(2.0) arrivals and Uniform(1.0, 2. 0) se rvice timesare¯r ¯w¯d ¯s¯l ¯q ¯x2.00 3.83 2.33 1.50 1.92 1.17 0.75Although the server is busy 75% of the time, on average thereare approximately two jobs in the service nodeA job can expect to spend more time in the queue than inserviceTo achieve these averages, many jobs must pass through nodeSection 3.1 Discrete-Event Simulation Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Discrete-Event SimulationExample 3.1.3The accumulated average wait was printed eve ry 20 jobs0 100 200 300 400 500 600 700 800 900 1000Number of jobs, n0246810¯wInitial seed◦ – 12345⋄ – 54321∗ – 2121212◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦⋄⋄ ⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄ ⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄ ⋄⋄∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗∗ ∗∗∗∗The convergence of ¯w is slow, erratic, and dependent on theinitial seedSection 3.1 Discrete-Event Simulation Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Discrete-Event SimulationGeometric Random VariatesThe Geometric(p) random variate is the discrete analog to acontinuous Exponential(µ) random variateLet x = Exponential(µ) = −µ ln(1 − u)Let y = ⌊x⌋ and let p = Pr(y 6= 0).y = ⌊x⌋ 6= 0 ⇐⇒ x ≥ 1⇐⇒ −µ ln(1 − u) ≥ 1⇐⇒ ln(1 − u) ≤ −1/µ⇐⇒ 1 − u ≤ exp(−1/µ)Since 1 − u is also Uniform(0.0,1.0),p = Pr(y 6= 0) = exp(−1/µ)Finally, since µ = −1/ ln(p),y = ⌊ln(1 − u)/ ln(p)⌋Section 3.1 Discrete-Event Simulation Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Discrete-Event SimulationGeometric Random VariatesANSI C functionGenerating a Geometric Random Variatelong Geometric(double p) /* use 0.0 < p < 1.0 */{return ((long) (log(1.0 - Random()) / log(p)));}The mean of a Geometric(p) random variate is p/(1 − p)If p is close to zero then the mean will be close to zeroIf p is close to one, then the mean will be largeSection 3.1 Discrete-Event Simulation Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Discrete-Event SimulationExample 3.1.4Assume that jobs arrive at random with a steady-state arrivalrate of 0.5 jobs per minuteAssume that Job service times are composite with twocomponentsThe number of service tasks is 1 + Geometric(0.9)The time (in minutes) per task is Uniform(0.1, 0.2)Get Service Methoddouble GetService(void){long k;double sum = 0.0;long tasks = 1 + Geometric(0.9);for (k = 0; k < tasks; k++)sum += Uniform(0.1, 0.2);return (sum);}Section 3.1 Discrete-Event Simulation Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Discrete-Event SimulationExample 3.1.4The theoretical steady-state statistics for this model are¯r ¯w¯d ¯s¯l ¯q ¯x2.00 5.77 4.27 1.50 2.89 2.14 0.75The arrival rate, service rate, and utilization are identical