I have been promising a book on Discrete Event Simulation with ExtendSim. I am waiting on the new version of ExtendSim to be released, but here is a start on chapter 1:
Simulation in general is to pretend that one deals with a real thing while really working with an imitation. In operations research the imitation is a computer model of the simulated reality. A flight simulator on a PC is also a computer model of some aspects of the flight: it shows on the screen the controls and what the "pilot" (the youngster who operates it) is supposed to see from the "cockpit" (his armchair).
What are a models and simulations?
Models
In order to understand what it means to model a phenomena or process, we must first understand the term “model” and understand its limitation. A model is a physical, mathematical, or otherwise logical representation of a system, entity, phenomenon, or process (DoDD5000.59). A model can also be thought of as an abstraction of the real world, or an approximation of it. If you think about the problem of modeling a human being, or just the mind of a human, you can immediately see the limitations of modeling. We will use the term “system” to encompass systems, entities, phenomenon, or process. Since a modeling is a representation, abstraction, or approximation of the “system” being modeled, we must understand that it is not an “exact” representation, i.e., we can’t model every aspect of the system. First, we don’t know everything we need to know in order to model the system. We may not be able to define a process of the system with mathematical precision, or with heuristic algorithms, and many of the processes may not appear logical. Second, even if we were to know everything about the system, we may not have enough computing power to model every process, at least for complex systems, e.g., a human being, the earth’s ecosystem, etc.
Yet with their limitations, models are a good way to gain understanding of how a system operates. George E.P. Box said, “All models are wrong; some models are useful.” They are wrong in that there is not a one-to-one mapping form the real system to the model; they are useful in that we can use them to understand the system, or at least certain aspects of the system. Even though we often use models to predict behavior, this is a dangerous process, and we must do it with caution.
There are many types of models that one can use when trying to represent a system. These can be divided into several classes, and for simplicity we will consider two classes: physical models and symbolic models (see Figure 1.1). Physical models include mock-up models (e.g., a vehicle mock-up), scale models (e.g., a 1:48 scale aircraft model), Iconic model, natural model, or a fashion model (which represent what we all want to look like).
Symbolic models include narrative models, graphical models, tabular models, software models, and mathematical models. These models are not necessarily mutually exclusive. For example a tabular model might contain data derived from a mathematical model, or a mathematical model may be embedded in software code.
Models can also be classified by contrast, e.g., a conceptual model (flowchart, picture, UML diagram) versus a computational model (spreadsheet, computer software) or static models that do not use time as a primary input, versus dynamic models based on time.
Simulations
A simulation is the execution of a model over time. Simulation involves designing a model of a system and carrying out experiments on it. The purpose of these "what if” experiments is to determine how the real system performs and to predict the effect of changes to the system as time progresses. For example, you use simulation to answer questions like:
- Will this change to our process result in higher yields or quality?
- How many people are required to maintain service at a specified level, for example, in a processing station?
- Can we design this weapon system with fewer components and still maintain measures of performance, such as availability or lethality?
- Does this force structure meet the capability requirement specified by the commander?
Definition 1: A method for implementing a model over time. Also, a technique for testing, analysis, or training in which real-world systems are used, or where real-world and conceptual systems are reproduced by a model.
Another definition is given by Winston & Albright, in Practical Management Science, 2001:
Definition 2: A simulation model is a computer model that imitates a real-life situation
- It is like other mathematical models, but it explicitly incorporates uncertainty in one or more input quantities.
- When we run a simulation, we allow these random quantities to take on various values, and we keep track of any resulting output quantities of interest.
- In this way, we are able to see how the outputs vary as a function of the varying inputs.
To fly a simulator is safer and cheaper than the real airplane. For precisely this reason, models are used in industry commerce and military: it is very costly, dangerous and often impossible to make experiments with real systems. Provided that models are adequate descriptions of reality (they are valid), experimenting with them can save money, suffering and even time.
When to use simulations
Simulations are appropriate with systems that change with time, such as a gas station where cars come and go (called dynamic systems) and involve randomness. Nobody can guess at exactly which time the next car should arrive at the station, so one can simulate the arrival or cars. Modeling complex dynamic systems theoretically requires too many simplifications and the emerging models may not be valid. Simulation does not require that many simplifying assumptions, making it a useful tool, even in absence of randomness.
How to simulate
Suppose we are interested in studying cars receiving service at a gas station. We may describe the behavior of this system graphically by plotting the number of cars in the station; the state of the system, either arriving, starting service, or completing service. Every time a car arrives the graph increases by one unit while a departing car causes the graph to drop one unit. This graph (called sample path), could be obtained from observation of a real station, but could also be artificially constructed. Such artificial construction and the analysis of the resulting sample path (or more sample paths in more complex cases) consist of the simulation.
Types of simulations:
Discrete Event Simulation
The above sample path consisted of only horizontal and vertical lines, as car arrivals and departures occurred at distinct points of time, what we refer to as events. Between two consecutive events, nothing happens - the graph is horizontal. When the number of events is finite, we call the simulation "discrete event."
Discrete Time Step Simulation
In discrete time step simulations, instead of looking at state changes that occur at discrete events, we choose a time step before starting a run an observe what happens as time progresses. Unlike discrete event simulation, it is possible to have no state change at one or more time steps. This form of simulation is often used to approximate continuous systems, since we would expect state changes at each time step.
Continuous Simulation
In some systems the state changes all the time, not just at the time of some discrete events. For example, the water level in a reservoir with given in and outflows may change all the time. In such cases "continuous simulation" is more appropriate, although discrete event simulation can serve as an approximation.
How is simulation performed?
Simulations may be performed manually. Most often, however, the system model is written either as a computer program (for an example click here) or as some kind of input into simulator software.
System terminology
• System: A facility or process either actual or planned, comprised of a collection of entities that act together toward the accomplishment of some logical goal.
- State: A variable characterizing an attribute in the system such as level of stock in inventory or number of jobs waiting for processing.
- Event: An occurrence at a point in time which may change the state of the system, such as arrival of a customer or start of work on a job.
- Entity: An object that passes through the system, such as cars in an intersection or orders in a factory. Often an event (e.g., arrival) is associated with an entity (e.g., customer).
- Queue: A queue is not only a physical queue of people, it can also be a task list, a buffer of finished goods waiting for transportation or any place where entities are waiting for something to happen for any reason.
- Creating: Creating is causing an arrival of a new entity to the system at some point in time.
- Scheduling: Scheduling is the act of assigning a new future event to an existing entity.
- Random variable: A random variable is a quantity that is uncertain, such as interarrival time between two incoming flights or number of defective parts in a shipment.
- Random variate: A random variate is an artificially generated random variable.
- Distribution: A distribution is the mathematical law which governs the probabilistic features of a random variable.
Consider building a simulation gas station with a single pump served by a single service man (see Figure 1.3). Assume that arrival of cars as well their service times are random. At first identify the:
- states: number of cars waiting for service and number of cars served at any moment
- events: arrival of cars, start of service, end of service
- entities: these are the cars
- queue: the queue of cars in front of the pump, waiting for service
- random realizations: interarrival times, service times
- distributions: we shall assume exponential distributions for both the interarrival time and service time.
Some initiation is still required, for example, the creation of the first arrival. Lastly, the above is translated into code. This is easy with an appropriate library which has subroutines for creation, scheduling, proper timing of events, queue manipulations, random variate generation and statistics collection.
Besides the above, the program records the number of cars in the system before and after every change, together with the length of each event.
The Importance of Simulation
Simulation provides a method for checking your understanding of the world around you and helps you produce better results faster. It is an important tool that you can use to:
- Predict the course and results of certain actions.
- Understand why observed events occur.
- Identify problem areas before implementation.
- Explore the effects of modifications.
- Confirm that all variables are known.
- Evaluate ideas and identify inefficiencies.
- Gain insight and stimulate creative thinking.
- Communicate the integrity and feasibility of your plans.
Verification and Validation
Verification is the process of determining that a model implementation and its associated data accurately represents the developer's conceptual description and specifications (DoDI 5000.61). There are a number of ways to achieve verification. Some methods are:
- Debug the computer program in modules. Start with a simple model and move toward complexity as needed.
- Use a “structured walk-through” or group involvement methodology in order to gain another simulator’s perspective to avoid not so obvious errors.
- Perform hand calculation checks.
- Use “Trace” to evaluate each possible program path as well as the contents of the events list, the state variables, statistical counters, and “extreme” conditions.
- Initially run the model under simplified conditions or assumptions for which the model’s true conditions are known or can be easily computed for comparison.
- Use graphics and animation to analyze the movement of entities thus lending credibility to the model.
- Develop a model with a high face value. That is, a model which is approved by people who are knowledgeable about the system under study. Make use of existing information such as:
o Existing theory
o Observations of the system
o General knowledge
o Intuition
- Test the assumptions of the model empirically. Make use of input distribution tests to determine proper goodness-of-fit. Use sensitivity analysis to determine how much the model will vary with a small change in an input parameter.
- Determine how representative the simulation output data are. Test the output data from the simulation with real world output results.
Benefits of Simulation
Simulation allows managers and analysts to evaluate proposed systems without building them. In some cases it offers the only way to solve the problem. Once built a model can easily be run repeatedly and changed to examine alternatives. Generally, it is less costly than other methods, if sufficient data is available. Also, simulation gives insight into how randomness affects a system and can be used to verify analytical solutions. Finally, simulation models are generally easier to understand than many analytical approaches.
Limitations of Simulation
In spite of its benefits, simulation carries with it certain limitations. Simulation may require a significant amount of time and resources. Lack of precise answers due to sampling errors may occur with simulations. As already mentioned, computer simulations can be difficult to validate. Also, simulations may be difficult to interpret. A major limitation is that some things cannot be simulated, in that either the system is too complex to simulate, or there are too many unknowns. Finally, simulation requires special training and experience.
References
- Theory of Modeling and Simulation (Second Edition), by Zeigler, Praehofer, & Kim. San Diego: Academic Press, 2000.
- Handbook of Simulation, Jerry Banks, Ed. New York: John Wiley & Sons, 1998.
- Simulation Modeling Design and Execution, by Paul A. Fishwick. Englewood Cliffs, NJ: Prentice Hall, 1995.
- Applied Simulation Modeling, by Seila, Ceric, & Tadikamalla. Belmont, CA: Brooks/Cole, 2003.
- Introduction to Simulation and Risk Analysis, by Evans & Olson. NJ: Prentice Hall, 2002.
- Spreadsheet Modeling and Applications, by Albright & Winston. Belmont, CA: Brooks/Cole, 2005.
- Simulation Modeling and Analysis (Third Edition), by Averill M. Law & W. David Kelton. New York: McGraw-Hill, 2000.
No comments:
Post a Comment