Systems Simulation & Modeling
Systems Simulation & Modeling CS 6910
Popular in Course
CHEM 111 001
verified elite notetaker
Popular in ComputerScienence
This 35 page Class Notes was uploaded by Lisette Hodkiewicz on Wednesday September 30, 2015. The Class Notes belongs to CS 6910 at Western Michigan University taught by Staff in Fall. Since its upload, it has received 9 views. For similar materials see /class/216890/cs-6910-western-michigan-university in ComputerScienence at Western Michigan University.
Reviews for Systems Simulation & Modeling
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 09/30/15
Chapter 11 Output Analysis for a Single Model Banks Carson Nelson amp Nicol DiscreteEvent System Simulation Purpose I Objective Estimate system performance via simulation I If 6 is the system performance the precision of the estimator can be measured by i The standard error of 5 The width of a confidence interval CI for 6 I Purpose of statistical analysis To estimate the standard error or Cl f To figure out the number of observations required to achieve desired errorCl I Potential issues to overcome Autocorrelation eg inventory cost for subsequent weeks lack statistical independence Initial conditions eg inventory on hand and of backorders at time 0 would most likely influence the performance of week 1 Outline 39 y u Distinguish the two types of simulation transient vs steady state Illustrate the inherent variability in a stochastic discrete event simulation Cover the statistical estimation of performance measures l Discusses the analysis of transient simulations Discusses the analysis of steadystate simulations Type of Simulations 39 I l Terminating verses nonterminating simulations I Terminating simulation Runs for some duration of time TE where E is a specified event that stops the simulation Starts at time 0 under wellspecified initial conditions Ends at the stopping time TE Bank example Opens at 830 am time 0 with no customers present and 8 of the 11 teller working initial conditions and closes at 430 pm Time TE 480 minutes The simulation analyst chooses to consider it a terminating system because the object of interest is one day s operation Type of Simulations 39 I I Nonterminating simulation Runs continuously or at least over a very long period of time Examples assembly lines that shut down infrequently telephone systems hospital emergency rooms Initial conditions defined by the analyst Runs for some analystspecified period of time TE Study the steadystate longrun properties of the system properties that are not influenced by the initial conditions of the model I Whether a simulation is considered to be terminating or nonterminating depends on both The objectives of the simulation study and The nature of the system Stochastic Nature of Output Data 39 I l Model output consist of one or more random variables r v because the model is an inputoutput transformation and the input variables are rv s I MIG1 queueing example Poisson arrival rate 01 per minute service time My 95 039 175 System performance longrun mean queue length LQt Suppose we run a single simulation for a total of 5000 minutes Divide the time interval 0 5000 into 5 equal subintervals of 1000 minutes Average number of customers in queue from time 0 11000 to j1000 is Y Stochastic Nature of Output Data 39 I l MIG1 queueing example cont Batched average queue length for 3 independent replications Batching Interval Replication minutes Batchj 1 Y1i 2 Yzi 3 Y3 0 1000 1 361 291 767 1000 2000 2 321 900 1953 2000 3000 3 218 1615 2036 3000 4000 4 692 2453 811 4000 5000 5 282 2519 1262 0 5000 375 1556 1366 2 Inherent variability in stochastic simulation both within a single replication and across different replications The average across 3 replications KY2Yacan be regarded as independent observations but averages within a replication Y Y15 are not Measures of performance 39 I I Consider the estimation of a performance parameter 6or of a simulated system 27 Discrete time data Y1 Y2 Yn with ordinary mean 6 Continuoustime data Yt 0 3 ts TE with timeweighted mean I Point estimation for discrete time data The point estimator A 1 6 2 I Is unbiased if its expected value is 6 that is if A I Is biased if A E6 9 DeSIred E6 6 Point Estimator Performance Measures 39 I 3 l Point estimation for continuoustime data The point estimator 3 i Ytdt ls biased in general where E 3 2 5 I An unbiased or lowbias estimator is desired I Usually system performance measures can be put into the common framework of 60r eg the proportion of days on which sales are lost through an out ofstock situation let 1 if out of stock on day 139 7 Y0 O otherw1se Point Estimator 39 I l Performance measure that does not fit quantile or percentile PrY S 639 p o Estimating quantiles the inverse of the problem of estimating a proportion or probability 1 Consider a histogram of the observed values Y I Find 5 such that 100p of the histogram is to the left of smaller than Performance Measures 10 ConfidenceInterval Estimation I Performance Measures 1 I To understand confidence intervals fully it is important to distinguish between measures of error and measures of risk eg confidence interval versus prediction interval I Suppose the model is the normal distribution with mean 6 variance 02 both unknown Let Y be the average cycle time for parts produced on the ith replication of the simulation its mathematical expectation is 639 Average cycle time will vary from day to day but over the longrun the average of the averages will be close to 6 1 Sample variance across R replications 52 ZY 2 R l 11 ConfidenceInterval Estimation I Performance Measures I l Confidence Interval Cl A measure of error Where Y are normally distributed S Y it a2R 1 We cannot know for certain how far Y is from 6 but Cl attempts to bound that error A Cl such as 95 tells us how much we can trust the interval to actually bound the error between Yand 6 The more replications we make the less error there is in f converging to 0 as R goes to infinity 12 ConfidenceInterval Estimation I Performance Measures 1 I Prediction Interval Pl A measure of risk A good guess for the average cycle time on a particular day is our estimator but it is unlikely to be exactly right PI is designed to be wide enough to contain the actual average cycle time on any particular day with high probability Normaltheory prediction interval 1 Yila2R IS 1 The length of PI will not go to 0 as R increases because we can never simulate away risk Pl s limit is 9i zma 13 Output Analysis for Terminating Simulations 39 t i I A terminating simulation runs over a simulated time interval 0 TE I A common goal is to estimate 6 Yl for discrete output 71 11 LTE Y 0dr for continuous output Y IO S I S T E E I In general independent replications are used each run using a different random number stream and independently chosen initial conditions 14 Statistical Background 39 i 3 l Important to distinguish withinreplication data from acrossreplication data I For example simulation of a manufacturing system Two performance measures of that system cycle time for parts and work in process WIP Let Y be the cycle time for the jth part produced in the ith replication Acrossreplication data are formed by summarizing within replication data X Terminating Simulations 15 Statistical Background 39 i I Across Replication l i For example the daily cycle time averages discrete time data I The average f Y Terminating Simulations Mm olH 1 R 522 Y Y 2 R1lt gt u The confidenceinterval halfwidth i a2R71 E I Within replication o For example the WIP a continuous time data I The average 7 ZLJ39TE YUM l 0 I II u The sample variance Ht The sample variance SI 2 Ti Yi ti2dt Ez39 16 Statistical Background 39 i l Overall sample average f and the interval replication sample averages 11 are always unbiased estimators of the expected daily average cycle time or daily average WIP Terminating Simulations l Acrossreplication data are independent different random numbers and identically distributed same model but withinreplication data do not have these properties 17 Cl with Specified Precision I Terminating Simulations I l The halflength H of a 1001 a confidence interval for a mean 6 based on the tdistribution is given by H ta2R 1 e tio R R is th of 82 is the sample replica ns variance l Suppose that an error criterion 8 is specified with probability 1 a a sufficiently large sample size should satisfy lt g21 a 18 Cl with Specified Precision 39 Terminating Simulations Assume that an initial sample of size R0 independent replications has been observed Obtain an initial estimate 802 of the population variance 02 Then choose sample size R such that R 2 R0 39 Since tam R4 2 zodz an initial estimate of R R gt ZaZSO 8 t S 2 2 R is the smallest integer satisfying R 2 R0 and R 2 D lz 0 Collect R R0 additional observations 2m2 is the standard normal distribution The 1001a CI for a S Y itaZ l J 19 Cl with Specified Precision Terminating Simulations I Call Center Example estimate the agent s utilization p overthe first 2 hours of the workday i l Initial sample of size R0 4 is taken and an initial estimate of the population variance is 802 0072 000518 i39 l The error criterion is g 004 and confidence coefficient is 10 095 hence the final sample size must be at least 2 2002550 21962 020518 21214 a 004 l i For the final sample size R 13 14 15 t0025 R1 218 216 214 ta2R1SOs2 1539 151 1483 i a R 15 is the smallest integer satisfying the error criterion so R R0 11 additional replications are needed i a After obtaining additional outputs halfwidth should be checked 20 Quantiles Terminating Simulations In this book a proportion or probability is treated as a special case of a mean When the number of independent replications Y1 YR is large enough that tw2n1 2 the confidence interval for a probability p is often written as 130 f9 Aiz p 052 R1 The sample proportion A quantile is the inverse of the probability to the probability estimation problem p is iven l Find 6such that PrYlt6 p H 21 Quantiles Terminating Simulations l The best way is to sort the outputs and use the Rp l smallest value ie find 6suoh that 100p of the data in a histogram of Y is to the left of 6 2 Example If we have R10 replications and we want the p 08 quantile first sort then estimate 6by the 100 8 87 smallest value round if necessary 56 6 sorted data 71 88 89 95 97 101 122 125 129 this is our point estimate 22 Quantiles 39 I I Confidence Interval of Quantiles An approximate 1a100 o confidence interval for 60an be obtained by finding two values and b 7 6 cuts off 100p of the histogram the Rp smallest value of the sorted data Terminating Simulations i1 6L cuts off 100pu of the histogram the Rpu smallest value of the sorted data 190 p Z Z pu p 052 R1 23 Quantiles Terminating Simulations 39 I l Example Suppose R 1000 reps to estimate the p 08 quantile with a 95 confidence interval 1 First sort the data from smallest to largest 1 Then estimate of 0by the 100008 800th smallest value and the point estimate is 21203 A portion ofthe 1000 And find the confidence interval sorted values Output Rank 8128 18092 779 P2 08 196 I 1 078 1 18896 780 19055 781 818 20858 799 21699 801 The ci is the 780th and 820th smallest values 25032 819 1 25679 820 25699 821 The point estimate is The 95 ci is 18896 25679 24 Output Analysis for SteadyState Simulation 39 I 3 I Consider a single run of a simulation model to estimate a steadystate or longrun characteristics of the system The single run produces observations Y1 Y2 generally the samples of an autocorrelated time series Performance measure 1 n t9 llm ZK for dlscrete measure with probability 1 71900 i1 1 TE lln lT jO Y tdt for contlnuous measure Wlth PFObablllty 1 TE 9 C E Independent of the initial conditions 25 Output Analysis for SteadyState Simulation 39 I l The sample size is a design choice with several considerations in mind Any bias in the point estimator that is due to artificial or arbitrary initial conditions bias can be severe if run length is too short Desired precision of the point estimator 7 Budget constraints on computer resources I Notation the estimation of efrom a discretetime output process One replication or run the output data Y1 Y2 Y3 39 With several replications the output data for replication r Yr1 Yr2 Yrs 26 Initialization Bias SteadyState Simulations I l Methods to reduce the pointestimator bias caused by using artificial and unrealistic initial conditions Intelligent initialization Divide simulation into an initialization phase and datacollection phase I Intelligent initialization i Initialize the simulation in a state that is more representative of longrun conditions If the system exists collect data on it and use these data to specify more nearly typical initial conditions If the system can be simplified enough to make it mathematically solvable eg queueing models solve the simplified model to find longrun expected or most likely conditions use that to initialize the simulation 27 Initialization Bias SteadyState Simulations 3 I Divide each simulation into two phases if An initialization phase from time 0to time T0 i A datacollection phase from T0 to the stopping time T0TE The choice of T0 is important After To system should be more nearly representative of steadystate behavior is System has reached steady state the probability distribution of the system state is close to the steadystate probability distribution bias of response variable is negligible 28 Initialization Bias SteadyState Simulations 39 I I MIG1 queueing example A total of 10 independent replications were made Each replication beginning in the empty and idle state Simulation run length on each replication was T0TE 15000 minutes 7 Response variable queue length LQtr at time tof the Ith replication i Batching intervals of 1000 minutes batch means I Ensemble averages To identify trend in the data due to initialization bias 7 The average correspondin batch means across replications z Z r1 The preferred method to determine deletion point 29 Initialization Bias SteadyState Simulations U II A plot of the ensemble averages fwd versus 1000j forj 1 15 Average batch mean l l l l l l l I l I l l 000 3000 5000 7000 9000 11000 13000 15000 I i Illustrates the downward bias ofthe initial observations 30 Initialization Bias SteadyState Simulations I I No widely accepted objective and proven technique to guide how much data to delete to reduce initialization bias to a negligible level I Plots can at times be misleading but they are still recommended Ensemble averages reveal a smoother and more precise trend as the of replications R increases Ensemble averages can be smoothed further by plotting a moving average Cumulative average becomes less variable as more data are averaged The more correlation present the longer it takes for Kto approach steady state Different performance measures could approach steady state at different rates 32 Sample Size SteadyState Simulations I An alternative to increasing R is to increase total run length T0TE within each replication rm Approach Increase run length from T0TE to RR0T0TE and Delete additional amount of data from time 0to time RR0T0 i Advantage any residual bias in the point estimator should be further reduced iquot However it is necessary to have saved the state ofthe model at time T0TE and to be able to restart the model Initialization Data collection phase phase 0 Tu Tu TI Initialization Dam Collection phase phase 0 RRullli RRull39lii 439 7 42 Batch Means for Interval Estimation I SteadyState Simulations I Using a single long replication Problem data are dependent so the usual estimator is biased Solution batch means I Batch means divide the output data from 1 replication after appropriate deletion into a few large batches and then treat the means of these batches as if they were independent I A continuoustime process Yt Tog ts T0TE k batches of size m TEk batch means 1 1m 16 1mYtTOdt I A discretetime process Y i d1d2 n 39 jm k batches of Size m n dk batch means Y i 2Y1 m ij 1m1 43 Batch Means for Interval Estimation I SteadyState Simulations Yd19 39 Yll 9 quot399de quot9Yd99Ydm19quot399Yd2rpa 9Ydk 1m1939 9Ydkm 17 17 deleted I Starting either with continuoustime or discretetime data the variance of the sample mean is estimated by Z J k k l kk 1 j1 S2 1quot z k 172 le k j 1 I If the batch size is sufficiently large successive batch means will be approximately independent and the variance estimator will be approximately unbiased I No widely accepted and relatively simple method for choosing an acceptable batch size m see text for a suggested approach Some simulation software does it automatically 44 S u m ma ry 39 I I Stochastic discreteevent simulation is a statistical experiment l a Purpose of statistical experiment obtain estimates of the performance measures of the system H Purpose of statistical analysis acquire some assurance that these estimates are sufficiently precise I Distinguish terminating simulations and steadystate simulations Steadystate output data are more difficult to analyze l l Decisions initial conditions and run length l l Possible solutions to bias deletion of data and increasing run length I Statistical precision of point estimators are estimated by standard error or confidence interval I Method of independent replications was emphasized 45