Encyclopedia of Computer Science
4th Edition, July 2000
New York, New York
"Few people are aware of the enormous scope of the science and engineering of the Information Technology field...The Encyclopedia of Computer Science lets everyone in on this awesome secret. It is a must-have." Peter J. Denning, Past President of the ACM
"Of all my general reference books, the Encyclopedia of Computer Science is the one I use most, and I am looking forward to having the fourth edition on my desk." Maurice V. Wilkes, Professor of Computing at the University of Cambridge, UK
"With this new edition, Ralston, Reilly and Hemmendinger continue to make the Encyclopedia of Computer Science even more valuable. The field of computer science is changing with unprecedented speed and it is difficult to keep up with all the new emerging areas. This book will allow scholars and students quick access to articles that will explain a broad range of areas across the discipline. It should be part of every technical library." John Hopcroft, Dean of Engineering College of Engineering, Cornell University, USA
Simulation Article Reviews:
"Congratulations on a very detailed article on simulation ... an article like this is sorely needed and I found it very informative." Israel del Rio, General Manager, Abstraction Software
"The article is truely an impressive piece of work. I wish I had had something similar when I was getting started in simulation." Hugh Henry, NASA Jet Propulsion Laboratories
"[The article] is very well written. It meets the goal of being accessible to the general audience without catering to the lowest common denominator. We plan to refer people to this article." Kathi Hunt, Imagine That Inc.
"You are to be congratulated for having written an entire article without using the word "paradigm" ... I appreciate your writing this article in plain English." Joe Manning, Computer Sciences Corporation
by Roger D. Smith
(Copyright Roger D. Smith, 1998)
Definition. Simulation is the process of designing a model of a real or imagined system and conducting experiments with that model. The purpose of simulation experiments is to understand the behavior of the system or evaluate strategies for the operation of the system. Assumptions are made about this system and mathematical algorithms and relationships are derived to describe these assumptions - this constitutes a "model" that can reveal how the system works. If the system is simple, the model may be represented and solved analytically. A single equation such as DISTANCE = (RATE * TIME) is an analytical solution representing the distance traveled by an object at constant rate for a given period of time.
However, problems of interest in the real world are usually much more complex than this. In fact, they may be so complex that a simple mathematical model can not be constructed to represent them. In this case, the behavior of the system must be estimated with a simulation. Exact representation is seldom possible in a model, constraining us to approximations to a degree of fidelity that is acceptable for the purposes of the study. Models have been constructed for almost every system imaginable, to include factories, communications and computer networks, integrated circuits, highway systems, flight dynamics, national economies, social interactions, and imaginary worlds. In each of these environments, a model of the system has proved to be more cost effective, less dangerous, faster, or otherwise more practical than experimenting with real system.
For example, a business may be interested in building a new factory to replace an old one, but is unsure whether the increased productivity will justify the investment. In this case, simulation would be used to evaluate a model of the new factory. The model would describe the floor space required, number of machines, number of employees, placement of equipment, production capacity of each machine, and the waiting time between machines. Simulation runs would then evaluate the system and provide an estimate of the production capacity and the costs of a new factory. This type of information is invaluable in making decisions without having to build an actual factory to arrive at an answer.
Simulations are usually referred to as either discrete event or continuous, based on the manner in which the state variables change. Discrete event refers to the fact that state variables change instantaneously at distinct points in time. In a continuous simulation, variables change continuously, usually through a function in which time is a variable. In practice, most simulations use both discrete and continuous state variables, but one of these is predominant and drives the classification of the entire simulation.
History. One of the pioneers of simulation concepts was John von Neumann. In the late 1940?s he conceived of the idea of running multiple repetitions of a model, gathering statistical data, and deriving behaviors of the real system based on these models. This came to be known as the Monte Carlo method because of the use of randomly generated variates to represent behaviors that could not be modeled exactly, but could be characterized statistically. von Neumann used this method to study the random actions of neutrons and the effectiveness of aircraft bombing missions. These methods wee first used in industry to determine the maximum potential productivity of factories.
Concepts for Discrete Event Simulations (DES) were developed in the late 1950's. The first DES-specific language was developed at General Electric by K.D. Tocher and D.G. Owen. The General Simulation Program (GSP) was created to study manufacturing problems at General Electric and was shared with the rest of the world at the Second International Conference on Operations Research.
Purpose. Simulation allows the analysis of a system?s capabilities, capacities, and behaviors without requiring the construction of or experimentation with the real system. Since it is extremely expensive to experiment with an entire factory to determine its best configuration, a simulation of the factory can be extremely valuable. There are also systems, like nuclear reactions and warfare, which are too dangerous to carry out for the sake of analysis, but which can be usefully analyzed through simulation.
Advantages and Disadvantages. When conducting a simulation or contriving a model, certain limitations must be acknowledged. Primary among these is the ability to create a model that accurately represents the system to be simulated. Real systems are extremely complex and a determination must be made about the details that will be captured in the model. Some details must be omitted and their effects lost or aggregated into other variables that are included in the model. In both cases, an inaccuracy has been introduced and the ramifications of this must be evaluated and accepted by the model developers. Another limitation is the availability of data for describing the behavior of the system. It is common for a model to require input data that is scarce or unavailable. This issue must be addressed prior to the design of the model to minimize its impact once the model is completed.
Both of the limitations above lead to a simulation that provides approximate results or that describes system behavior statistically. For this reason, simulation usually provides measurements of general trends, rather than exact data for specific situations or individuals. A simulation would be hard pressed to determine which piece of material will be ruined by a milling machine. But, it would be an excellent tool for determining the impacts of machine failure on factory productivity, using known statistical distributions for the failures of many machines.
(Click to continue to the next page)