资源描述
Chapter 1Basic Simulation Modeling1Simulation Modeling and Analysis Chapter 1 Basic Simulation ModelingCONTENTS1.1 The Nature of Simulation1.2 Systems,Models,and Simulation1.3 Discrete-Event Simulation1.4 Simulation of a Single-Server Queueing System1.5 Simulation of an Inventory System1.6 Alternative Approaches to Modeling and Coding Simulations1.7 Steps in a Sound Simulation Study1.8 Other Types of Simulation1.9 Advantages,Disadvantages,and Pitfalls of Simulation2Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.1 THE NATURE OF SIMULATION Simulation:Imitate the operations of a facility or process,usually via computerWhats being simulated is the systemTo study system,often make assumptions/approximations,both logical and mathematical,about how it worksThese assumptions form a model of the systemIf model structure is simple enough,could use mathematical methods to get exact information on questions of interest analytical solution3Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.1 The Nature of Simulation(contd.)But most complex systems require models that are also complex(to be valid)Must be studied via simulation evaluate model numerically and collect data to estimate model characteristicsExample:Manufacturing company considering extending its plantBuild it and see if it works out?Simulate current,expanded operations could also investigate many other issues along the way,quickly and cheaply4Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.1 The Nature of Simulation(contd.)Some(not all)application areasDesigning and analyzing manufacturing systemsEvaluating military weapons systems or their logistics requirementsDetermining hardware requirements or protocols for communications networksDetermining hardware and software requirements for a computer systemDesigning and operating transportation systems such as airports,freeways,ports,and subwaysEvaluating designs for service organizations such as call centers,fast-food restaurants,hospitals,and post officesReengineering of business processesDetermining ordering policies for an inventory systemAnalyzing financial or economic systems5Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.1 The Nature of Simulation(contd.)Use,popularity of simulationSeveral conferences devoted to simulation,notably the Winter Simulation Conference(wintersim.org)Surveys of use of OR/MS techniques(examples)Longitudinal study(1973-1988):Simulation consistently ranked as one of the three most important techniques1294 papers in Interfaces(2019):Simulation was second only to the broad category of“math programming”6Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.1 The Nature of Simulation(contd.)Impediments to acceptance,use of simulationModels of large systems are usually very complexBut now have better modeling software more general,flexible,but still(relatively)easy to useCan consume a lot of computer timeBut now have faster,bigger,cheaper hardware to allow for much better studies than just a few years ago this trend will continueHowever,simulation will also continue to push the envelope on computing power in that we ask more and more of our simulation modelsImpression that simulation is“just programming”Theres a lot more to a simulation study than just“coding”a model in some software and running it to get“the answer”Need careful design and analysis of simulation models simulation methodology7Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.2 SYSTEMS,MODELS,AND SIMULATIONSystem:A collection of entities(people,parts,messages,machines,servers,)that act and interact together toward some end(Schmidt and Taylor,1970)In practice,depends on objectives of studyMight limit the boundaries(physical and logical)of the systemJudgment call:level of detail(e.g.,what is an entity?)Usually assume a time element dynamic systemState of a system:Collection of variables and their values necessary to describe the system at that timeMight depend on desired objectives,output performance measuresBank model:Could include number of busy tellers,time of arrival of each customer,etc.8Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.2 Systems,Models,and Simulation(contd.)Types of systemsDiscreteState variables change instantaneously at separated points in timeBank model:State changes occur only when a customer arrives or departsContinuousState variables change continuously as a function of timeAirplane flight:State variables like position,velocity change continuouslyMany systems are partly discrete,partly continuous9Simulation Modeling and Analysis Chapter 1 Basic Simulation ModelingWays to study a system1.2 Systems,Models,and Simulation(contd.)Simulation is“method of last resort?”Maybe But with simulation theres no need(or less need)to“look where the light is”10Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.2 Systems,Models,and Simulation(contd.)Classification of simulation modelsStatic vs.dynamicDeterministic vs.stochasticContinuous vs.discreteMost operational models are dynamic,stochastic,and discrete will be called discrete-event simulation models11Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.3 DISCRETE-EVENT SIMULATIONDiscrete-event simulation:Modeling of a system as it evolves over time by a representation where the state variables change instantaneously at separated points in timeMore precisely,state can change at only a countable number of points in timeThese points in time are when events occurEvent:Instantaneous occurrence that may change the state of the systemSometimes get creative about what an“event”is e.g.,end of simulation,make a decision about a systems operationCan in principle be done by hand,but usually done on computer12Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.3 Discrete-Event Simulation(contd.)Example:Single-server queueEstimate expected average delay in queue(line,not service)State variablesStatus of server(idle,busy)needed to decide what to do with an arrivalCurrent length of the queue to know where to store an arrival that must wait in lineTime of arrival of each customer now in queue needed to compute time in queue when service startsEventsArrival of a new customerService completion(and departure)of a customerMaybe end-simulation event(a“fake”event)whether this is an event depends on how simulation terminates(a modeling decision)13Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.3.1 Time-Advance MechanismsSimulation clock:Variable that keeps the current value of(simulated)time in the modelMust decide on,be consistent about,time unitsUsually no relation between simulated time and(real)time needed to run a model on a computerTwo approaches for time advanceNext-event time advance(usually used)described in detail belowFixed-increment time advance(seldom used)Described in Appendix 1AGenerally introduces some amount of modeling error in terms of when events should occur vs.do occurForces a tradeoff between model accuracy and computational efficiency14Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.3.1 Time-Advance Mechanisms(contd.)More on next-event time advanceInitialize simulation clock to 0Determine times of occurrence of future events event listClock advances to next(most imminent)event,which is executedEvent execution may involve updating event listContinue until stopping rule is satisfied(must be explicitly stated)Clock“jumps”from one event time to the next,and doesnt“exist”for times between successive events periods of inactivity are ignored15Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.3.1 Time-Advance Mechanisms(contd.)Next-event time advance for the single-server queueti=time of arrival of ith customer(t0=0)Ai=ti ti-1=interarrival time between(i-1)st and ith customers(usually assumed to be a random variable from some probability distribution)Si=service-time requirement of ith customer(another random variable)Di=delay in queue of ith customerCi=ti+Di+Si=time ith customer completes service and departsej=time of occurrence of the jth event(of any type),j=1,2,3,Possible trace of events(detailed narrative in text)16Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.3.2 Components and Organization of a Discrete-Event Simulation ModelEach simulation model must be customized to target systemBut there are several common components,general organizationSystem state variables to describe stateSimulation clock current value of simulated timeEvent list times of future events(as needed)Statistical counters to accumulate quantities for outputInitialization routine initialize model at time 0Timing routine determine next event time,type;advance clockEvent routines carry out logic for each event typeLibrary routines utility routines to generate random variates,etc.Report generator to summarize,report results at endMain program ties routines together,executes them in right order17Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.3.2 Components and Organization of a Discrete-Event Simulation Model(contd.)18Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.3.2 Components and Organization of a Discrete-Event Simulation Model(contd.)More on entitiesObjects that compose a simulation modelUsually include customers,parts,messages,etc.may include resources like serversCharacterized by data values called attributesFor each entity resident in the model theres a record(row)in a list,with the attributes being the columnsApproaches to modelingEvent-scheduling as described above,coded in general-purpose languageProcess focuses on entities and their“experience,”usually requires special-purpose simulation software19Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.4 SIMULATION OF A SINGLE-SERVER QUEUEING SYSTEMWill show how to simulate a specific version of the single-server queueing systemBook contains code in FORTRAN and C slides will focus only on C versionThough simple,it contains many features found in all simulation models20Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.4.1 Problem StatementRecall single-server queueing modelAssume interarrival times are independent and identically distributed(IID)random variables Assume service times are IID,and are independent of interarrival timesQueue discipline is FIFOStart empty and idle at time 0First customer arrives after an interarrival time,not at time 0Stopping rule:When nth customer has completed delay in queue(i.e.,enters service)n will be specified as input21Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.4.1 Problem Statement(contd.)Quantities to be estimatedExpected average delay in queue(excluding service time)of the n customers completing their delaysWhy“expected?”Expected average number of customers in queue(excluding any in service)A continuous-time averageArea under Q(t)=queue length at time t,divided by T(n)=time simulation ends see book for justification and detailsExpected utilization(proportion of time busy)of the serverAnother continuous-time averageArea under B(t)=server-busy function(1 if busy,0 if idle at time t),divided by T(n)justification and details in bookMany others are possible(maxima,minima,time or number in system,proportions,quantiles,variances)Important:Discrete-time vs.continuous-time statistics22Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.4.2 Intuitive ExplanationGiven(for now)interarrival times(all times are in minutes):0.4,1.2,0.5,1.7,0.2,1.6,0.2,1.4,1.9,Given service times:2.0,0.7,0.2,1.1,3.7,0.6,n=6 delays in queue desired“Hand”simulation:Display system,state variables,clock,event list,statistical counters all after execution of each eventUse above lists of interarrival,service times to“drive”simulationStop when number of delays hits n=6,compute output performance measures23Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.4.2 Intuitive Explanation(contd)Status shown is after all changes have been made in each case Interarrival times:0.4,1.2,0.5,1.7,0.2,1.6,0.2,1.4,1.9,Service times:2.0,0.7,0.2,1.1,3.7,0.6,24Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.4.2 Intuitive Explanation(contd)Interarrival times:0.4,1.2,0.5,1.7,0.2,1.6,0.2,1.4,1.9,Service times:2.0,0.7,0.2,1.1,3.7,0.6,25Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.4.2 Intuitive Explanation(contd)Interarrival times:0.4,1.2,0.5,1.7,0.2,1.6,0.2,1.4,1.9,Service times:2.0,0.7,0.2,1.1,3.7,0.6,26Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.4.2 Intuitive Explanation(contd)Interarrival times:0.4,1.2,0.5,1.7,0.2,1.6,0.2,1.4,1.9,Service times:2.0,0.7,0.2,1.1,3.7,0.6,27Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.4.2 Intuitive Explanation(contd)Interarrival times:0.4,1.2,0.5,1.7,0.2,1.6,0.2,1.4,1.9,Service times:2.0,0.7,0.2,1.1,3.7,0.6,28Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.4.2 Intuitive Explanation(contd)Interarrival times:0.4,1.2,0.5,1.7,0.2,1.6,0.2,1.4,1.9,Service times:2.0,0.7,0.2,1.1,3.7,0.6,29Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.4.2 Intuitive Explanation(contd)Interarrival times:0.4,1.2,0.5,1.7,0.2,1.6,0.2,1.4,1.9,Service times:2.0,0.7,0.2,1.1,3.7,0.6,30Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.4.2 Intuitive Explanation(contd)Interarrival times:0.4,1.2,0.5,1.7,0.2,1.6,0.2,1.4,1.9,Service times:2.0,0.7,0.2,1.1,3.7,0.6,31Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.4.2 Intuitive Explanation(contd)Interarrival times:0.4,1.2,0.5,1.7,0.2,1.6,0.2,1.4,1.9,Service times:2.0,0.7,0.2,1.1,3.7,0.6,32Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.4.2 Intuitive Explanation(contd)Interarrival times:0.4,1.2,0.5,1.7,0.2,1.6,0.2,1.4,1.9,Service times:2.0,0.7,0.2,1.1,3.7,0.6,33Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.4.2 Intuitive Explanation(contd)Interarrival times:0.4,1.2,0.5,1.7,0.2,1.6,0.2,1.4,1.9,Service times:2.0,0.7,0.2,1.1,3.7,0.6,34Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.4.2 Intuitive Explanation(contd)Interarrival times:0.4,1.2,0.5,1.7,0.2,1.6,0.2,1.4,1.9,Service times:2.0,0.7,0.2,1.1,3.7,0.6,35Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.4.2 Intuitive Explanation(contd)Interarrival times:0.4,1.2,0.5,1.7,0.2,1.6,0.2,1.4,1.9,Service times:2.0,0.7,0.2,1.1,3.7,0.6,36Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.4.2 Intuitive Explanation(contd)Interarrival times:0.4,1.2,0.5,1.7,0.2,1.6,0.2,1.4,1.9,Service times:2.0,0.7,0.2,1.1,3.7,0.6,Final output performance measures:Average delay in queue=5.7/6=0.95 min./cust.Time-average number in queue=9.9/8.6=1.15 custs.Server utilization=7.7/8.6=0.90(dimensionless)37Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.4.3 Program Organization and LogicC program to do this model(FORTRAN as well is in book)Event types:1 for arrival,2 for departureModularize for initialization,timing,events,library,report,mainChanges from hand simulation:Stopping rule:n=1000(rather than 6)Interarrival and service times“drawn”from an exponential distribution(mean b=1 for interarrivals,0.5 for service times)Density functionCumulative distribution function38Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.4.3 Program Organization and Logic(contd.)How to“draw”(or generate)an observation(variate)from an exponential distribution?Proposal:Assume a perfect random-number generator that generates IID variates from a continuous uniform distribution on 0,1 denoted the U(0,1)distribution see Chap.7Algorithm:1.Generate a random number U2.Return X=b ln UProof that algorithm is correct:39Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.4.5 C Program;1.4.6 Simulation Output and DiscussionRefer to pp.30,31,42-48 in the book(Figures 1.8,1.9,1.19-1.27)and the file mm1.cFigure 1.19 external definitions(at top of file)Figure 1.20 function mainFigure 1.21 function initializeFigure 1.22 function timingFigure 1.23 function arrive(flowchart:Figure 1.8)Figure 1.24 function depart(flowchart:Figure 1.9)Figure 1.25 function reportFigure 1.26 function update_time_avg_statsFigure 1.27 function exponFigure 1.28 output report mm1.outAre these“the”answers?Steady-state vs.terminating?What about time in queue vs.just time in system?40Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.4.7 Alternative Stopping RulesStop simulation at(exactly)time 8 hours(=480 minutes),rather than whenever n delays in queue are completedBefore,final value of simulation clock was a random variableNow,number of delays completed will be a random variableIntroduce an artificial“end-simulation”event(type 3)Schedule it on initializationEvent routine is report generatorBe sure to update continuous-time statistics to endChanges in C code(everything else is the same)Figure 1.33 external definitionsFigure 1.34 function mainFigure 1.35 function initializeFigure 1.36 function reportFigure 1.37 output report mm1alt.out41Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.4.8 Determining the Events and VariablesFor complex models,it might not be obvious what the events areEvent-graph method(Schruben 1983,and subsequent papers)gives formal graph-theoretic method of analyzing event structureCan analyze what needs to be initialized,possibility of combining events to simplify modelSoftware package(SIGMA)to build,execute a simulation model via event-graph representation42Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.5 SIMULATION OF AN INVENTORY SYSTEM;1.5.1 Problem StatementSingle-product inventoryDecide how many items to have in inventory for the nextn=120 months;initially(time 0)have 60 items on handDemands against inventoryOccur with inter-demand time exponential with mean 0.1 monthDemand size=1,2,3,4 with resp.probabilities 1/6,1/3,1/3,1/6Inventory review,reorder stationary(s,S)policy at beginning of each month,review inventory level=IIf I s,dont order(s is an input constant);no ordering costIf I s,order Z=S I items(S is an input constant,order“up to”S);ordering cost=32+3Z;delivery lag U(0.5,1)month43Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.5.1 Problem Statement(contd.)Demand in excess of current(physical)inventory is backlogged so(accounting)inventory could be 0Let I(t)be(accounting)inventory level at time t(+,0,)I+(t)=max I(t),0=number of items physically on hand at time tI(t)=max I(t),0=number of items in backlog at time tHolding cost:Incur$1 per item per month in(positive)inventoryTime-average(per month)holding cost=Shortage cost:Incur$5 per item per month in backlogTime-average(per month)backlog cost=Average total cost per month:Add ordering,holding,shortage costs per monthTry different(s,S)combinations to try to reduce total cost44Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.5.2 Program Organization and LogicState variables:Inventory level,amount of an outstanding order,time of the last(most recent)eventEvents:1.Arrival of an order from the supplier2.Demand for the product3.End of the simulation after n=120 months4.Inventory evaluation(maybe ordering)at beginning of a monthRandom variates neededInterdemand times:exponential,as in queueing modelDelivery lags U(0.5,1):0.5+(1 0.5)U,where U U(0,1)Demand sizes:Split 0,1 into subintervals of width 1/6,1/3,1/3,1/6;generate U U(0,1);see which subinterval U falls in;return X=1,2,3,or 4,respectivelyWhy the orderingof event types3 and 4?45Simulation Modeling and Analysis Chapter 1 Basic Simulation Modeling1.5.4 C Program;1.5.5 Simulation Output and DiscussionRefer to pp.64-66,73-79 in the book(Figures 1.43-1.46,1.57-1.67)and the file inv.cFigure
展开阅读全文