Introduction_to_Modeling_and_Simulation[1]

ed. S. Andradóttir, K. J. Healy, D. H. Withers, and B. L. Nelson

INTRODUCTION TO MODELING AND SIMULATION

Anu Maria

State University of New York at Binghamton

Department of Systems Science and Industrial Engineering

Binghamton, NY 13902-6000, U.S.A.

ABSTRACT

This introductory tutorial is an overview of simulationmodeling and analysis. Many critical questions areanswered in the paper. What is modeling? What issimulation? What is simulation modeling and analysis?What types of problems are suitable for simulation? Howto select simulation software? What are the benefits andpitfalls in modeling and simulation? The intendedaudience is those unfamiliar with the area of discreteevent simulation as well as beginners looking for anoverview of the area. This includes anyone who isinvolved in system design and modification - systemanalysts, management personnel, engineers, militaryplanners, economists, banking analysts, and computerscientists. Familiarity with probability and statistics isassumed.1

WHAT IS MODELING?

Modeling is the process of producing a model; a modelis a representation of the construction and working ofsome system of interest. A model is similar to butsimpler than the system it represents. One purpose of amodel is to enable the analyst to predict the effect ofchanges to the system. On the one hand, a model shouldbe a close approximation to the real system andincorporate most of its salient features. On the otherhand, it should not be so complex that it is impossible tounderstand and experiment with it. A good model is ajudicious tradeoff between realism and simplicity.Simulation practitioners recommend increasing thecomplexity of a model iteratively. An important issue inmodeling is model validity. Model validation techniquesinclude simulating the model under known inputconditions and comparing model output with systemoutput.

Generally, a model intended for a simulation studyis a mathematical model developed with the help ofsimulation software. Mathematical model classificationsinclude deterministic (input and output variables arefixed values) or stochastic (at least one of the input or

output variables is probabilistic); static (time is not takeninto account) or dynamic (time-varying interactionsamong variables are taken into account). Typically,simulation models are stochastic and dynamic.2

WHAT IS SIMULATION?

A simulation of a system is the operation of a model ofthe system. The model can be reconfigured andexperimented with; usually, this is impossible, tooexpensive or impractical to do in the system it represents.The operation of the model can be studied, and hence,properties concerning the behavior of the actual systemor its subsystem can be inferred. In its broadest sense,simulation is a tool to evaluate the performance of asystem, existing or proposed, under differentconfigurations of interest and over long periods of realtime.

Simulation is used before an existing system isaltered or a new system built, to reduce the chances offailure to meet specifications, to eliminate unforeseenbottlenecks, to prevent under or over-utilization ofresources, and to optimize system performance. Forinstance, simulation can be used to answer questionslike: What is the best design for a newtelecommunications network? What are the associatedresource requirements? How will a telecommunicationnetwork perform when the traffic load increases by 50%?How will a new routing algorithm affect itsperformance? Which network protocol optimizesnetwork performance? What will be the impact of a linkfailure?

The subject of this tutorial is discrete eventsimulation in which the central assumption is that thesystem changes instantaneously in response to certaindiscrete events. For instance, in an M/M/1 queue - asingle server queuing process in which time betweenarrivals and service time are exponential - an arrivalcauses the system to change instantaneously. On theother hand, continuous simulators, like flight simulatorsand weather simulators, attempt to quantify the changesin a system continuously over time in response to

7

8Maria

controls. Discrete event simulation is less detailed(coarser in its smallest time unit) than continuoussimulation but it is much simpler to implement, andhence, is used in a wide variety of situations.

Figure 1 is a schematic of a simulation study. Theiterative nature of the process is indicated by the systemunder study becoming the altered system which thenbecomes the system under study and the cycle repeats. Ina simulation study, human decision making is required atall stages, namely, model development, experimentdesign, output analysis, conclusion formulation, andmaking decisions to alter the system under study. Theonly stage where human intervention is not required isthe running of the simulations, which most simulationsoftware packages perform efficiently. The importantpoint is that powerful simulation software is merely ahygiene factor - its absence can hurt a simulation studybut its presence will not ensure success. Experiencedproblem formulators and simulation modelers andanalysts are indispensable for a successful simulationstudy.

RealSimulationWorldStudySystemSimulationUnderModelStudySimulationExperimentSimulationAnalysisConclusionsAlteredSystemFigure 1: Simulation Study Schematic

The steps involved in developing a simulationmodel, designing a simulation experiment, andperforming simulation analysis are:

Step 1.Identify the problem.Step 2.Formulate the problem.

Step 3.Collect and process real system data.Step 4.Formulate and develop a model.

Step 5.Validate the model.

Step 6.Document model for future use.

Step 7.Select appropriate experimental design.Step 8.Establish experimental conditions for runs.Step 9.Perform simulation runs.Step 10.Interpret and present results.

Step 11.Recommend further course of action.

Although this is a logical ordering of steps in asimulation study, many iterations at various sub-stagesmay be required before the objectives of a simulationstudy are achieved. Not all the steps may be possibleand/or required. On the other hand, additional steps mayhave to be performed. The next three sections describethese steps in detail.

3HOW TO DEVELOP A SIMULATIONMODEL?

Simulation models consist of the following components:system entities, input variables, performance measures,and functional relationships. For instance in a simulationmodel of an M/M/1 queue, the server and the queue aresystem entities, arrival rate and service rate are inputvariables, mean wait time and maximum queue lengthare performance measures, and 'time in system = waittime + service time' is an example of a functionalrelationship. Almost all simulation software packagesprovide constructs to model each of the abovecomponents. Modeling is arguably the most importantpart of a simulation study. Indeed, a simulation study isas good as the simulation model. Simulation modelingcomprises the following steps:

Step 1.Identify the problem. Enumerate problemswith an existing system. Produce requirements for aproposed system.

Step 2.Formulate the problem. Select the boundsof the system, the problem or a part thereof, to bestudied. Define overall objective of the study and a fewspecific issues to be addressed. Define performancemeasures - quantitative criteria on the basis of whichdifferent system configurations will be compared andranked. Identify, briefly at this stage, the configurationsof interest and formulate hypotheses about systemperformance. Decide the time frame of the study, i.e.,will the model be used for a one-time decision (e.g.,capital expenditure) or over a period of time on a regularbasis (e.g., air traffic scheduling). Identify the end userof the simulation model, e.g., corporate managementversus a production supervisor. Problems must beformulated as precisely as possible.

Step 3.Collect and process real system data.Collect data on system specifications (e.g., bandwidth fora communication network), input variables, as well as

Introduction to Modeling and Simulation 9

performance of the existing system. Identify sources ofrandomness in the system, i.e., the stochastic inputvariables. Select an appropriate input probabilitydistribution for each stochastic input variable andestimate corresponding parameter(s).

Software packages for distribution fitting andselection include ExpertFit, BestFit, and add-ons in somestandard statistical packages. These aids combinegoodness-of-fit tests, e.g., χ2 test, Kolmogorov-Smirnovtest, and Anderson-Darling test, and parameterestimation in a user friendly format.

Standard distributions, e.g., exponential, Poisson,normal, hyperexponential, etc., are easy to model andsimulate. Although most simulation software packagesinclude many distributions as a standard feature, issuesrelating to random number generators and generatingrandom variates from various distributions are pertinentand should be looked into. Empirical distributions areused when standard distributions are not appropriate ordo not fit the available system data. Triangular, uniformor normal distribution is used as a first guess when nodata are available. For a detailed treatment of probabilitydistributions see Maria and Zhang (1997).

Step 4.Formulate and develop a model. Developschematics and network diagrams of the system (How doentities flow through the system?). Translate theseconceptual models to simulation software acceptableform. Verify that the simulation model executes asintended. Verification techniques include traces, varyinginput parameters over their acceptable range andchecking the output, substituting constants for randomvariables and manually checking results, and animation.Step 5.Validate the model. Compare the model'sperformance under known conditions with theperformance of the real system. Perform statisticalinference tests and get the model examined by systemexperts. Assess the confidence that the end user placeson the model and address problems if any. For majorsimulation studies, experienced consultants advocate astructured presentation of the model by the simulationanalyst(s) before an audience of management and systemexperts. This not only ensures that the modelassumptions are correct, complete and consistent, butalso enhances confidence in the model.

Step 6.Document model for future use. Documentobjectives, assumptions and input variables in detail.4 HOW TO DESIGN A SIMULATIONEXPERIMENT?

A simulation experiment is a test or a series of tests inwhich meaningful changes are made to the input

variables of a simulation model so that we may observeand identify the reasons for changes in the performancemeasures. The number of experiments in a simulationstudy is greater than or equal to the number of questionsbeing asked about the model (e.g., Is there a significantdifference between the mean delay in communicationnetworks A and B?, Which network has the least delay:A, B, or C? How will a new routing algorithm affect theperformance of network B?). Design of a simulationexperiment involves answering the question: what dataneed to be obtained, in what form, and how much? Thefollowing steps illustrate the process of designing asimulation experiment.

Step 7.Select appropriate experimental design.Select a performance measure, a few input variables thatare likely to influence it, and the levels of each inputvariable. When the number of possible configurations(product of the number of input variables and the levelsof each input variable) is large and the simulation modelis complex, common second-order design classesincluding central composite, Box-Behnken, and full-factorial should be considered. Document theexperimental design.

Step 8.Establish experimental conditions for runs.Address the question of obtaining accurate informationand the most information from each run. Determine if thesystem is stationary (performance measure does notchange over time) or non-stationary (performancemeasure changes over time). Generally, in stationarysystems, steady-state behavior of the response variable isof interest. Ascertain whether a terminating or a non-terminating simulation run is appropriate. Select the runlength. Select appropriate starting conditions (e.g., emptyand idle, five customers in queue at time 0). Select thelength of the warm-up period, if required. Decide thenumber of independent runs - each run uses a differentrandom number stream and the same starting conditions -by considering output data sample size. Sample size mustbe large enough (at least 3-5 runs for each configuration)to provide the required confidence in the performancemeasure estimates. Alternately, use common randomnumbers to compare alternative configurations by using aseparate random number stream for each samplingprocess in a configuration. Identify output data mostlikely to be correlated.

Step 9.Perform simulation runs. Perform runsaccording to steps 7-8 above.

5 HOW TO PERFORM SIMULATIONANALYSIS?

10Maria

Most simulation packages provide run statistics (mean,standard deviation, minimum value, maximum value) onthe performance measures, e.g., wait time (non-timepersistent statistic), inventory on hand (time persistentstatistic). Let the mean wait time in an M/M/1 queueobserved from n runs be W1,W2,...,Wn. It is important tounderstand that the mean wait time W is a randomvariable and the objective of output analysis is toestimate the true mean of W and to quantify itsvariability.

Notwithstanding the facts that there are no datacollection errors in simulation, the underlying model isfully known, and replications and configurations are usercontrolled, simulation results are difficult to interpret. Anobservation may be due to system characteristics or justa random occurrence. Normally, statistical inference canassess the significance of an observed phenomenon, butmost statistical inference techniques assumeindependent, identically distributed (iid) data. Most typesof simulation data are autocorrelated, and hence, do notsatisfy this assumption. Analysis of simulation outputdata consists of the following steps.

Step 10.Interpret and present results. Computenumerical estimates (e.g., mean, confidence intervals) ofthe desired performance measure for each configurationof interest. To obtain confidence intervals for the meanof autocorrelated data, the technique of batch means canbe used. In batch means, original contiguous data setfrom a run is replaced with a smaller data set containingthe means of contiguous batches of original observations.The assumption that batch means are independent maynot always be true; increasing total sample size andincreasing the batch length may help.

Test hypotheses about system performance.Construct graphical displays (e.g., pie charts, histograms)of the output data. Document results and conclusions.Step 11.Recommend further course of action. Thismay include further experiments to increase the precisionand reduce the bias of estimators, to perform sensitivityanalyses, etc.

6AN EXAMPLE

A machine shop contains two drills, one straightener, andone finishing operator. Figure 2 shows a schematic of themachine shop. Two types of parts enter the machine shop.

StraightenerDrill #1Drill #2FinishingOperatorLegend:Type 1 partsType 2 partsFigure 2: Schematic of the Machine ShopType 1 parts require drilling, straightening, and finishingin sequence. Type 2 parts require only drilling andfinishing. The frequency of arrival and the time to berouted to the drilling area are deterministic for both typesof parts.

Step 1.Identify the problem. The utilization ofdrills, straightener, and finishing operator needs to beassessed. In addition, the following modification to theoriginal system is of interest: the frequency of arrival ofboth parts is exponential with the same respective meansas in the original system.

Step 2.Formulate the problem. The objective is toobtain the utilization of drills, straightener, and finishingoperator for the original system and the modification. Theassumptions include:

♦The two drills are identical

♦There is no material handling time between the three

operations.

♦Machine availability implies operator availability.♦Parts are processed on a FIFO basis.♦All times are in minutes.

Step 3.Collect and process real system data. Atthe job shop, a Type 1 part arrives every 30 minutes, and aType 2 part arrives every 20 minutes. It takes 2 minutes toroute a Type 1 part and 10 minutes to route a Type 2 partto the drilling area. Parts wait in a queue till one of the twodrilling machines becomes available. After drilling, Type 1parts are routed to the straightener and Type 2 parts are

Introduction to Modeling and Simulation 11

routed to the finishing operator. After straightening, Type1 parts are routed to the finishing operator.

The operation times for either part were determined tobe as follows. Drilling time is normally distributed withmean 10.0 and standard deviation 1.0. Straightening timeis exponentially distributed with a mean of 15.0. Finishingrequires 5 minutes per part.

Step 4.Formulate and develop a model. A modelof the system and the modification was developed usinga simulation package. A trace verified that the partsflowed through the job shop as expected.

Step 5.Validate the model. The utilization for asufficiently long run of the original system was judged tobe reasonable by the machine shop operators.

Step 6.Document model for future use. Themodels of the original system and the modification weredocumented as thoroughly as possible.

Step 7.Select appropriate experimental design.The original system and the modification describedabove were studied.

Step 8.Establish experimental conditions for runs.Each model was run three times for 4000 minutes andstatistical registers were cleared at time 1000, so thestatistics below were collected on the time interval [1000,4000]. At the beginning of a simulation run, there were noparts in the machine shop.

Step 9.Perform simulation runs. Runs wereperformed as specified in Step 8 above.

Step 10.Interpret and present results. Table 1contains the utilization statistics of the three operations forthe original system and the modification (in parentheses).

Table 1: Utilization Statistics

Drilling Straightening FinishingMean Run #1 0.83 (0.78) 0.51 (0.58) 0.42 (0.39)Mean Run #2 0.82 (0.90) 0.52 (0.49) 0.41 (0.45)Mean Run #3 0.84 (0.81) 0.42 (0.56) 0.42 (0.40)Std. Dev. Run #1 0.69 (0.75) 0.50 (0.49) 0.49 (0.49)Std. Dev. Run #2 0.68 (0.78) 0.50 (0.50) 0.49 (0.50)Std. Dev. Run #3 0.69 (0.76) 0.49 (0.50) 0.49 (0.49)Mean utilization represents the fraction of time a server isbusy, i.e., busy time/total time. Furthermore, the averageutilization output for drilling must be divided by thenumber of drills in order to get the utilization per drill.Each drill is busy about 40% of the time and straighteningand finishing operations are busy about half the time. Thisimplies that for the given work load, the system is

underutilized. Consequently, the average utilization did notchange substantially between the original system and themodification; the standard deviation of the drillingoperation seems to have increased because of the increasedrandomness in the modification. The statisticalsignificance of these observations can be determined bycomputing confidence intervals on the mean utilization ofthe original and modified systems.

Step 11.Recommend further course of action. Otherperformance measures of interest may be: throughput ofparts for the system, mean time in system for both types ofparts, average and maximum queue lengths for eachoperation. Other modifications of interest may be: theflow of parts to the machine shop doubles, the finishingoperation will be repeated for 10% of the products on aprobabilistic basis.

7 WHAT MAKES A PROBLEM SUITABLE FORSIMULATION MODELING AND ANALYSIS?In general, whenever there is a need to model andanalyze randomness in a system, simulation is the tool ofchoice. More specifically, situations in which simulationmodeling and analysis is used include the following:

♦ It is impossible or extremely expensive to observe

certain processes in the real world, e.g., next year'scancer statistics, performance of the next spaceshuttle, and the effect of Internet advertising on acompany's sales.

♦ Problems in which mathematical model can be

formulated but analytic solutions are eitherimpossible (e.g., job shop scheduling problem, high-order difference equations) or too complicated (e.g.,complex systems like the stock market, and largescale queuing models).

♦ It is impossible or extremely expensive to validate

the mathematical model describing the system, e.g.,due to insufficient data.

Applications of simulation abound in the areas ofgovernment, defense, computer and communicationsystems, manufacturing, transportation (air trafficcontrol), health care, ecology and environment,sociological and behavioral studies, biosciences,epidemiology, services (bank teller scheduling),economics and business analysis.8 HOW TO SELECT SIMULATIONSOFTWARE?

Although a simulation model can be built using generalpurpose programming languages which are familiar tothe analyst, available over a wide variety of platforms,and less expensive, most simulation studies today areimplemented using a simulation package. The

12Maria

advantages are reduced programming requirements;natural framework for simulation modeling; conceptualguidance; automated gathering of statistics; graphicsymbolism for communication; animation; andincreasingly, flexibility to change the model. There arehundreds of simulation products on the market, manywith price tags of $15,000 or more. Naturally, thequestion of how to select the best simulation software foran application arises. Metrics for evaluation includemodeling flexibility, ease of use, modeling structure(hierarchical v/s flat; object-oriented v/s nested), codereusability, graphic user interface, animation, dynamicbusiness graphics, hardware and software requirements,statistical capabilities, output reports and graphical plots,customer support, and documentation.

The two types of simulation packages are simulationlanguages and application-oriented simulators (Table 2).Simulation languages offer more flexibility than theapplication-oriented simulators. On the other hand,languages require varying amounts of programmingexpertise. Application-oriented simulators are easier tolearn and have modeling constructs closely related to theapplication. Most simulation packages incorporateanimation which is excellent for communication and canbe used to debug the simulation program; a \"correctlooking\" animation, however, is not a guarantee of avalid model. More importantly, animation is not asubstitute for output analysis.

Table 2: Simulation Packages

Type OfExamples

SimulationPackageSimulationArena (previously SIMAN), AweSim! (previously

languages

SLAM II), Extend, GPSS, Micro Saint,SIMSCRIPT, SLX

Object-oriented software: MODSIM III, SIMPLE++Animation software: Proof AnimationApplicationManufacturing: AutoMod, Extend+MFG,

-OrientedFACTOR/AIM, ManSim/X, MP$IM,Simulators

ProModel, QUEST, Taylor II, WITNESSCommunications/computer: COMNET III,

NETWORK II.5, OPNET Modeler, OPNETPlanner, SES/Strategizer, SES/workbenchBusiness: BP$IM, Extend+BPR, ProcessModel,

ServiceModel, SIMPROCESS, Time machineHealth Care: MedModel

9BENEFITS OF SIMULATION MODELINGAND ANALYSIS

According to practitioners, simulation modeling andanalysis is one of the most frequently used operationsresearch techniques. When used judiciously, simulationmodeling and analysis makes it possible to:

♦Obtain a better understanding of the system by

developing a mathematical model of a system of

interest, and observing the system's operation indetail over long periods of time.

♦Test hypotheses about the system for feasibility.♦Compress time to observe certain phenomena overlong periods or expand time to observe a complexphenomenon in detail.

♦

Study the effects of certain informational,organizational, environmental and policy changes onthe operation of a system by altering the system'smodel; this can be done without disrupting the realsystem and significantly reduces the risk ofexperimenting with the real system.

♦Experiment with new or unknown situations aboutwhich only weak information is available.

♦Identify the \"driving\" variables - ones thatperformance measures are most sensitive to - and theinter-relationships among them.

♦Identify bottlenecks in the flow of entities (material,people, etc.) or information.

♦Use multiple performance metrics for analyzingsystem configurations.

♦Employ a systems approach to problem solving.♦

Develop well designed and robust systems andreduce system development time.

10WHAT ARE SOME PITFALLS TO GUARDAGAINST IN SIMULATION?

Simulation can be a time consuming and complexexercise, from modeling through output analysis, thatnecessitates the involvement of resident experts anddecision makers in the entire process. Following is achecklist of pitfalls to guard against.♦Unclear objective.

♦Using simulation when an analytic solution is

appropriate.♦Invalid model.

♦Simulation model too complex or too simple.♦Erroneous assumptions.

♦Undocumented assumptions. This is extremely

important and it is strongly suggested thatassumptions made at each stage of the simulationmodeling and analysis exercise be documentedthoroughly.

♦Using the wrong input probability distribution.

♦Replacing a distribution (stochastic) by its mean

(deterministic).

♦Using the wrong performance measure.♦Bugs in the simulation program.

♦Using standard statistical formulas that assume

independence in simulation output analysis.♦Initial bias in output data.

♦Making one simulation run for a configuration.

Introduction to Modeling and Simulation 13

♦ Poor schedule and budget planning.

♦ Poor communication among the personnel involved

in the simulation study.REFERENCES

Banks, J., J. S. Carson, II, and B. L. Nelson. 1996.

Discrete-Event System Simulation, Second Edition,Prentice Hall.

Bratley, P., B. L. Fox, and L. E. Schrage. 1987. A Guide

to Simulation, Second Edition, Springer-Verlag.Fishwick, P. A. 1995. Simulation Model Design and

Execution: Building Digital Worlds, Prentice-Hall.Freund, J. E. 1992. Mathematical Statistics, Fifth Edition,

Prentice-Hall.

Hogg, R. V., and A. T. Craig. 1995. Introduction to

Mathematical Statistics, Fifth Edition, Prentice-Hall.Kleijnen, J. P. C. 1987. Statistical Tools for Simulation

Practitioners, Marcel Dekker, New York.

Law, A. M., and W. D. Kelton. 1991. Simulation

Modeling and Analysis, Second Edition,McGraw-Hill.

Law, A. M., and M. G. McComas. 1991. Secrets of

Successful Simulation Studies, Proceedings of the1991 Winter Simulation Conference, ed. J. M.Charnes, D. M. Morrice, D. T. Brunner, and J. J.Swain, 21-27. Institute of Electrical and ElectronicsEngineers, Piscataway, New Jersey.

Maria, A., and L. Zhang. 1997. Probability Distributions,

Version 1.0, July 1997, Monograph, Department ofSystems Science and Industrial Engineering, SUNYat Binghamton, Binghamton, NY 13902.

Montgomery, D. C. 1997. Design and Analysis of

Experiments, Third Edition, John Wiley.

Naylor, T. H., J. L. Balintfy, D. S. Burdick, and K. Chu.

1966. Computer Simulation Techniques, John Wiley.Nelson, B. L. 1995. Stochastic Modeling: Analysis and

Simulation, McGraw-Hill.AUTHOR BIOGRAPHY

ANU MARIA is an assistant professor in the departmentof Systems Science & Industrial Engineering at the StateUniversity of New York at Binghamton. She receivedher PhD in Industrial Engineering from the University ofOklahoma. Her research interests include optimizing theperformance of materials used in electronic packaging(including solder paste, conductive adhesives, andunderfills), simulation optimization techniques, geneticsbased algorithms for optimization of problems with alarge number of continuous variables, multi criteriaoptimization, simulation, and interior-point methods.