Contents

1 Introduction

A simulation is the imitation of the operation of a real-world process or system over time. Whether done by hand or on a computer, simulation involves the generation of an artificial history of a system and the observation of that artificial history to draw inferences concerning the operating characteristics of the real system.

The behavior of a system as it evolves over time is studied by developing a simulation model. This model usually takes the form of a set of assumptions concerning the operation of the system. These assumptions are expressed in mathematical, logical, and symbolic relationships between the entities, or objects of interest, of the system. Once developed and validated, a model can be used to investigate a wide variety of “what if” questions about the real-world system. Potential changes to the system can first be simulated, in order to predict their impact on system performance. Simulation can also be used to study systems in the design stage, before such systems are built. Thus, simulation modeling can be used both as an analysis tool for predicting the effect of changes to existing systems and as a design tool to predict the performance of new systems under varying sets of circumstances.

In some instances, a model can be developed which is simple enough to be “solved” by mathematical methods. Such solutions might be found by the use of differential calculus, probability theory, algebraic methods, or other mathematical techniques. The solution usually consists of one or more numerical parameters, which are called measures of performance of the system. However, many real-world systems are so complex that models of these systems are virtually impossible to solve mathematically. In these instances, numerical, computer-based simulation can be used to imitate the behavior of the system over time. From the simulation, data are collected as if a real system were being observed. This simulation-generated data is used to estimate the measures of performance of the system.

This chapter initially discusses when to use simulation, its advantages and disadvantages, and actual areas of its application. Then the concepts of system and model are explored. Finally, an outline is given of the steps in building and using a simulation model of a system.

1 When Simulation Is the Appropriate Tool

The availability of special-purpose simulation languages, of massive computing capabilities at a decreasing cost per operation, and of advances in simulation methodologies have made simulation one of the most widely used and accepted tools in operations research and systems analysis. Circumstances under which simulation is the appropriate tool to use have been discussed by many authors, from Naylor et al. [1966] to Shannon [1998]. Simulation can be used for the following purposes:

1. Simulation enables the study of, and experimentation with, the internal interactions of a complex system or of a subsystem within a complex system.
2. Informational, organizational, and environmental changes can be simulated, and the effect of these alterations on the model’s behavior can be observed.
3. The knowledge gained during the designing of a simulation model could be of great value toward suggesting improvement in the system under investigation.
4. Changing simulation inputs and observing the resulting outputs can produce valuable insights about which variables are the most important and how variables interact.
5. Simulation can be used as a pedagogical device to reinforce analytic solution methodologies.
6. Simulation can be used to experiment with new designs or policies before implementation, so as to prepare for what might happen.
7. Simulation can be used to verify analytic solutions.
8. Simulating different capabilities for a machine can help determine its requirements.
9. Simulation models designed for training make learning possible, without the cost and disruption of on-the-job instruction.
10. Animation can show a system in simulated operation so that the plan can be visualized.
11. A modern system (factory, wafer fabrication plant, service organization, etc.) is so complex that its internal interactions can be treated only through simulation.

2 When Simulation Is Not Appropriate

This section is based on an article by Banks and Gibson [1997], which gives ten rules for evaluating when simulation is not appropriate. The first rule indicates that simulation should not be used when the problem can be solved by common sense. An example is given of an automobile tag facility serving customers who arrive randomly at an average rate of 100/hour and are served at a mean rate of 12/hour. To determine the minimum number of servers needed, simulation is not necessary. Just compute 100/12 = 8.33, which indicates that nine or more servers are needed.

The second rule says that simulation should not be used if the problem can be solved analytically. For example, under certain conditions, the average waiting time in the example above can be found using the tools available at www.bcnn.net.

The next rule says that simulation should not be used if it is less expensive to perform direct experiments. The example of a fast-food drive-in restaurant is given, where it was less expensive to stage a person taking orders using a hand-held terminal and voice communication to determine the effect of adding another order station on customer waiting time.

The fourth rule says not to use simulation if the costs exceed the savings. There are many steps in completing a simulation, as will be discussed in Section 12, and these must be done thoroughly. If a simulation study costs $20,000 and the savings might be $10,000, simulation would not be appropriate.

Rules five and six indicate that simulation should not be performed if the resources or time are not available. If the simulation is estimated to cost $20,000 and there is only $10,000 available, the suggestion is not to venture into a simulation study. Similarly, if a decision is needed in two weeks and a simulation would take a month, the simulation study is not advised.

Simulation takes data, sometimes lots of data. If no data is available, not even estimates, simulation is not advised. The next rule concerns the ability to verify and validate the model. If there is not enough time or if the personnel are not available, simulation is not appropriate.

If managers have unreasonable expectations, if they ask for too much too soon, or if the power of simulation is overestimated, simulation might not be appropriate.

Last, if system behavior is too complex or cannot be defined, simulation is not appropriate. Human behavior is sometimes extremely complex to model.

3 Advantages and Disadvantages of Simulation

Simulation is intuitively appealing to a client because it mimics what happens in a real system or what is perceived for a system that is in the design stage. The output data from a simulation should directly correspond to the outputs that could be recorded from the real system. Additionally, it is possible to develop a simulation model of a system without dubious assumptions (such as the same statistical distribution for every random variable) of mathematically solvable models. For these and other reasons, simulation is frequently the technique of choice in problem solving.

In contrast to optimization models, simulation models are “run” rather than solved. Given a particular set of input and model characteristics, the model is run and the simulated behavior is observed. This process of changing inputs and model characteristics results in a set of scenarios that are evaluated. A good solution, either in the analysis of an existing system or in the design of a new system, is then recommended for implementation.

Simulation has many advantages, but some disadvantages. These are listed by Pegden, Shannon, and Sadowski [1995]. Some advantages are these:

1. New policies, operating procedures, decision rules, information flows, organizational procedures, and so on can be explored without disrupting ongoing operations of the real system.
2. New hardware designs, physical layouts, transportation systems, and so on can be tested without committing resources for their acquisition.
3. Hypotheses about how or why certain phenomena occur can be tested for feasibility.
4. Time can be compressed or expanded to allow for a speed-up or slow-down of the phenomena under investigation.
5. Insight can be obtained about the interaction of variables.
6. Insight can be obtained about the importance of variables to the performance of the system.
7. Bottleneck analysis can be performed to discover where work in process, information, materials, and so on are being delayed excessively.
8. A simulation study can help in understanding how the system operates rather than how individuals think the system operates.
9. “What if” questions can be answered. This is particularly useful in the design of new systems.

Some disadvantages are these:

1. Model building requires special training. It is an art that is learned over time and through experience. Furthermore, if two models are constructed by different competent individuals, they might have similarities, but it is highly unlikely that they will be the same.
2. Simulation results can be difficult to interpret. Most simulation outputs are essentially random variables (they are usually based on random inputs), so it can be hard to distinguish whether an observation is the result of system interrelationships or of randomness.
3. Simulation modeling and analysis can be time consuming and expensive. Skimping on resources for modeling and analysis could result in a simulation model or analysis that is not sufficient to the task.
4. Simulation is used in some cases when an analytical solution is possible, or even preferable, as was discussed in Section 2. This might be particularly true in the simulation of some waiting lines where closed-form queueing models are available.

In defense of simulation, these four disadvantages, respectively, can be offset as follows:

1. Vendors of simulation software have been actively developing packages that contain models that need only input data for their operation. Such models have the generic tag “simulator” or “template.”
2. Many simulation software vendors have developed output-analysis capabilities within their packages for performing very thorough analyses.
3. Simulation can be performed faster today than yesterday and will be even faster tomorrow, because of advances in hardware that permit rapid running of scenarios and because of advances in many simulation packages. For example, some simulation software contains constructs for modeling material handling that uses such transporters as fork-lift trucks, conveyors, and automated guided vehicles.
4. Closed-form models are not able to analyze most of the complex systems that are encountered in practice. During the many years of consulting practice by two of the authors, not one problem was encountered that could have been solved by a closed-form solution.

4 Areas of Application

The applications of simulation are vast. The Winter Simulation Conference (WSC) is an excellent way to learn more about the latest in simulation applications and theory. There are also numerous tutorials at both the beginning and advanced levels. WSC is sponsored by six technical societies and the National Institute of Standards and Technology (NIST). The technical societies are the American Statistical Association (ASA), the Association for Computing Machinery/Special Interest Group on Simulation (ACM/SIGSIM), the Institute of Electrical and Electronics Engineers: Systems, Man and Cybernetics Society (IEEE/SMCS), the Institute of Industrial Engineers (IIE), the Institute for Operations Research and the Management Sciences: Simulation Society (INFORMS-SIM), and the Society for Modeling and Simulation International (SCS). Information about the upcoming WSC can be obtained from www.wintersim.org. WSC programs with full papers are available from www.informs-cs.org/wscpapers.html. Some presentations, by area, from a recent WSC are listed next:

Manufacturing Applications

• Methodology for Selecting the Most Suitable Bottleneck Detection Method
• Automating the Development of Shipyard Manufacturing Models
• Emulation in Manufacturing Engineering Processes
• Optimized Maintenance Design for Manufacturing Performance Improvement
• Productivity Management in an Automotive-Parts Industry
• Manufacturing Line Designs in Japanese Automobile Manufacturing Plants

Wafer Fabrication

• A Paradigm Shift in Assigning Lots to Tools
• Scheduling a Multi-Chip Package Assembly Line with Reentrant Processes
• Execution Level Capacity Allocation Decisions for Assembly—Test Facilities
• Managing WIP and Cycle Time with the Help of Loop Control

Business Processing

• A New Policy for the Service Request Assignment Problem
• Process Execution Monitoring and Adjustment Schemes
• In-Store Merchandizing of Retail Stores
• Sales Forecasting for Retail Small Stores

Construction Engineering and Project Management

• Scheduling of Limited Bar-Benders over Multiple Building Sites
• Constructing Repetitive Projects
• Traffic Operations for Improved Planning of Road Construction Projects
• Template for Modeling Tunnel Shaft Construction
• Decision Support Tool for Planning Tunnel Construction

Logistics, Transportation, and Distribution

• Operating Policies for a Barge Transportation System
• Dispensing Plan for Emergency Medical Supplies in the Event of Bioterrorism
• Analysis of a Complex Mail Transportation Network
• Improving the Performance of Container Terminals
• Yard Crane Dispatching Based on Real Time Data
• Unit Loading Device Inventory in Airline Operations
• Inventory Systems with Forecast Based Policy Updating
• Dock Allocation in a Food Distribution Center

Military Applications

• Multinational Intra-Theatre Logistics Distribution
• Examining Future Sustainability of Canadian Forces Operations
• Feasibility Study for Replacing the MK19 Automatic Grenade Launching System
• Training Joint Forces for Asymmetric Operations
• Multi-Objective Unmanned Aerial Vehicle Mission Planning
• Development of Operational Requirements Driven Federations

Health Care

• Interventions to Reduce Appointment Lead-Time and Patient No-Show Rate
• Supporting Smart Thinking to Improve Hospital Performance
• Verification of Lean Improvement for Emergency Room Process
• Reducing Emergency Department Overcrowding
• Inventory Modeling of Perishable Pharmaceuticals
• Implementation of an Outpatient Procedure Center
• Infectious Disease Control Policy
• Balancing Operating Room and Post-Anesthesia Resources
• Cost Effectiveness of Colorectal Cancer Screening Tests

Additional Applications

• Managing Workforce Resource Actions with Multiple Feedback Control
• Analyzing the Impact of Hole-Size on Putting in Golf
• Application of Particle Filters in Wildfire Spread Simulation
• Predator-Prey Relationship in a Closed Habitat
• Intensive Piglet Production Systems
• Real-Time Delay Estimation in Call Centers
• Pandemic Influenza Preparedness Plans for a Public University

For an article on the future of simulation appearing in the ICS Newsletter (Banks, 2008), sixteen simulationists, including well-known experts in the field, provided their response to the following question: “What remarkable results will we observe in simulation software in the long term, say, after three years?” The responses that are shown below appeared in the referenced article:

• After new fundamental ideas and methodologies such as agent-based modeling have been adopted by the software vendors (which is going to happen within a few years), progress in simulation modeling will be driven by gains in computing power. For example, at a certain point we will be able to simulate the detailed operation of very large supply chains and manufacturing facilities.
• Simulation modeling will be more of an “assembly” activity than a “build-from-scratch” activity. Intelligent, parameterized components will be used to piece together models rather than defining lots of detailed logic.
• Progress will be made in solving hard problems. To provide tools for really hard problems, simulation software developers will have to go back to the drawing board and seriously reconsider the fundamental question: “Who provides the power, and who provides the vision?” Getting this mix right is essential to further progress. When a software developer tries to provide both power and vision, end users are saddled with the developer’s paradigms. This works well for easy problems, but poorly for hard problems. For all truly hard problems, users know more about the problems than software developers do. The obvious solution is for developers to provide well-thought-out collections of true primitives, along with ways of combining and packaging these primitives.
• Simulation software will be integrated more closely with control software.
• Modelers will have a single model that is shared across applications within the organization.
• Simulation applications will not be restricted to design applications but will also be used to make day-to-day operational decisions within an organization.
• Simulation modeling on powerful servers will be accessed with web-based interfaces.
• Better and easier modeling of human activities (e.g. embedding agent-based models into discrete-event models) will be available.
• More collaborative simulation project development can be expected.
• Interface standards and incorporation of web services allowing simulation software to not only work with each other as an integrated federation, but also standardize and simplify the way other applications interface with simulation software will be adopted.
• Analytical solving techniques (such as linear programming) will be integrated with simulation capabilities.
• The “remarkable” results will be derived from advances in other areas of computing technology and software engineering. But nothing will surpass the object-oriented paradigm that was ushered into mainstream software development by SIMULA 67, emanating from the simulation software community.

5 Some Recent Applications of Simulation

In this section, we present some recent applications of simulation. These have appeared in the literature indicated so you can find these cases and learn more details about them.

Case 1

• TITLE: “The Turkish Army Uses Simulation to Model and Optimize Its Fuel-Supply System”
• AUTHOR(S): I. Sabuncuoglu, A. Hatip
• REPORTED: November–December 2005 in Interfaces
• CHALLENGE: Analysis of the Turkish army’s fuel-supply system.
• TECHNIQUE(S): (1) Measured performance of the existing and proposed systems under various scenarios, (2) developed a simulation optimization model based on a genetic algorithm to optimize system performance, (3) conducted extensive simulation experiments.
• SAVINGS: Millions of US$.

Case 2

• TITLE: “PLATO Helps Athens Win Gold: Olympic Games Knowledge Modeling for Organizational Change and Resource Management”
• AUTHOR(S): D.A. Beis, P. Poucopoulos, Y. Pyrgiotis, K.G. Zografos
• REPORTED: January–February 2006 in Interfaces
• CHALLENGE: Develop a systematic process for planning and designing venue operations. Develop a rich library of models that is directly transferable to future Olympic organizing committees and other sports-oriented events.
• TECHNIQUE(S): Knowledge modeling and resource-management techniques and tools based on simulation and other decision analysis methodologies.
• SAVINGS: Over US$69.7 million.

Case 3

• TITLE: “Schlumberger Uses Simulation in Bidding and Executing Land Seismic Surveys”
• AUTHOR(S): P.W. Mullarkey, G. Butler, S. Gavirneni, D.J. Morrice
• REPORTED: March–April 2007 in Interfaces
• CHALLENGE: Quickly and accurately measure the cost of seismic surveys.
• TECHNIQUE(S): Developed a simulation tool to evaluate the impact of crew sizes, survey area, geographical region, and weather conditions on survey costs and durations.
• SAVINGS: US$1.5 to US$3.0 million annually.

Case 4

• TITLE: “Operations Research Helps Reshape Operations Strategy at Standard Register Company”
• AUTHOR(S): S.L. Ahire, M.F. Gorman, D. Dwiggins, O. Mudry
• REPORTED: November–December 2007 in Interfaces
• CHALLENGE: Minimize the total costs to offer competitive pricing in the highly competitive traditional print market.
• TECHNIQUE(S): (1) Regression to estimate costs and time attributes, (2) optimization modeling to determine the order-routing strategy, (3) simulation modeling of the production-distribution network.
• SAVINGS: Over US$10 million annually.

Case 5

• TITLE: “Simulation Implements Demand-Driven Workforce Scheduler for Service Industry”
• AUTHOR(S): M. Zottolo, O.M. Ulgen, E. Williams
• REPORTED: Proceedings of the 2007 Winter Simulation Conference, eds. S.G. Henderson, B. Biller, M.-H. Hsieh, J. Shortle, J.D. Tew, and R.R. Barton.
• CONDUCTED BY: PMC (www.pmcorp.com)
• CLIENT: Major US appliance company.
• CHALLENGE: As a result of a time-consuming, manual, and inefficient scheduling process the client was experiencing over- and underscheduling of workgroups, inconsistent service levels being provided, and overwhelmed site managers.
• TECHNIQUE(S): (1) Built simulation model to schedule different workgroups according to changes in customer demand during the day and servicing times, (2) determined work standards, (3) developed interface for input data as well as storing and publishing of schedules, (4) implemented and trained employees on the use of the scheduling tool.
• SAVINGS: Estimated at US$80 million for client’s US facilities.

Case 6

• TITLE: “Simulation Improves End-of-Line Sortation and Material Handling Pickup Scheduling at Appliance Manufacturer”
• AUTHOR(S): N. Kale, M. Zottolo, O.M. Ulgen, E. Williams
• CONDUCTED BY: PMC (www.pmcorp.com)
• CLIENT: Major US car rental company. (as printed in the original)
• REPORTED: Proceedings of the 2007 Winter Simulation Conference, eds. S.G. Henderson, B. Biller, M.-H. Hsieh, J. Shortle, J.D. Tew, and R.R. Barton.
• CHALLENGE: To determine the most efficient method to distribute several types of finished appliances (SKUs) into a 12-lane sortation system in order to minimize the material handling and the number of forklifts required to pick them. This sortation task and its associated material-handling tasks were of a complexity meriting discrete-event simulation analysis due to volatile product mix, the large number of SKUs, and high overhead costs.
• TECHNIQUE(S): Built simulation model and performed experimentation with respect to (1) assignment of different SKUs to the different lanes, (2) picking strategy and quantity, (3) SKU batch sizes.
• SAVINGS: Estimated US$100,000 annually for a US$50,000 one-time capital investment.

6 Systems and System Environment

To model a system, it is necessary to understand the concept of a system and the system boundary. A system is defined as a group of objects that are joined together in some regular interaction or interdependence toward the accomplishment of some purpose. An example is a production system manufacturing automobiles. The machines, component parts, and workers operate jointly along an assembly line to produce a high-quality vehicle.

A system is often affected by changes occurring outside the system. Such changes are said to occur in the system environment [Gordon, 1978]. In modeling systems, it is necessary to decide on the boundary between the system and its environment. This decision may depend on the purpose of the study.

In the case of the factory system, for example, the factors controlling the arrival of orders may be considered to be outside the influence of the factory and therefore part of the environment. However, if the effect of supply on demand is to be considered, there will be a relationship between factory output and arrival of orders, and this relationship must be considered an activity of the system. Similarly, in the case of a bank system, there could be a limit on the maximum interest rate that can be paid. For the study of a single bank, this would be regarded as a constraint imposed by the environment. In a study of the effects of monetary laws on the banking industry, however, the setting of the limit would be an activity of the system [Gordon, 1978].

7 Components of a System

In order to understand and analyze a system, a number of terms need to be defined. An entity is an object of interest in the system. An attribute is a property of an entity. An activity represents a time period of specified length. If a bank is being studied, customers might be one of the entities, the balance in their checking accounts might be an attribute, and making deposits might be an activity.

The collection of entities that compose a system for one study might only be a subset of the overall system for another study [Law, 2007]. For example, if the aforementioned bank is being studied to determine the number of tellers needed to provide for paying and receiving, the system can be defined as that portion of the bank consisting of the regular tellers and the customers waiting in line. If the purpose of the study is expanded to determine the number of special tellers needed (to prepare cashier’s checks, to conduct commercial transactions, etc.), the definition of the system must be expanded.

The state of a system is defined to be that collection of variables necessary to describe the system at any time, relative to the objectives of the study. In the study of a bank, possible state variables are the number of busy tellers, the number of customers waiting in line or being served, and the arrival time of the next customer. An event is defined as an instantaneous occurrence that might change the state of the system. The term endogenous is used to describe activities and events occurring within a system, and the term exogenous is used to describe activities and events in the environment that affect the system. In the bank study, the arrival of a customer is an exogenous event, and the completion of service of a customer is an endogenous event.

Table 1 lists examples of entities, attributes, activities, events, and state variables for several systems. Only a partial listing of the system components is shown. A complete list cannot be developed unless the purpose of the study is known. Depending on the purpose, various aspects of the system will be of interest, and then the listing of components can be completed.

Table 1 Examples of Systems and Their Components

8 Discrete and Continuous Systems

Systems can be categorized as discrete or continuous. “Few systems in practice are wholly discrete or continuous, but since one type of change predominates for most systems, it will usually be possible to classify a system as being either discrete or continuous” [Law, 2007]. A discrete system is one in which the state variable(s) change only at a discrete set of points in time. The bank is an example of a discrete system: The state variable, the number of customers in the bank, changes only when a customer arrives or when the service provided a customer is completed. Figure 1 shows how the number of customers changes only at discrete points in time.

Figure 1 Discrete-system state variable.

A continuous system is one in which the state variable(s) change continuously over time. An example is the head of water behind a dam. During and for some time after a rain storm, water flows into the lake behind the dam. Water is drawn from the dam for flood control and to make electricity. Evaporation also decreases the water level. Figure 2 shows how the state variable head of water behind the dam changes for this continuous system.

Figure 2 Continuous-system state variable.

9 Model of a System

Sometimes it is of interest to study a system to understand the relationships between its components or to predict how the system will operate under a new policy. To study the system, it is sometimes possible to experiment with the system itself. However, this is not always an option. A new system might not yet exist; it could be in only hypothetical form or at the design stage. Even if the system exists, it might be impractical to experiment with it. In the case of a bank, reducing the number of tellers to study the effect on the length of waiting lines might infuriate the customers so greatly that they will move their accounts to a competitor. Consequently, studies of systems are often accomplished with a model of a system.

We had a consulting job for the simulation of a redesigned port in Western Australia. At US$300 million for a loading/unloading berth, it is not advisable to invest that amount only to find that the berth is inadequate for the task.

A model is defined as a representation of a system for the purpose of studying that system. For most studies, it is only necessary to consider those aspects of the system that affect the problem under investigation. These aspects are represented in a model of the system; the model, by definition, is a simplification of the system. On the other hand, the model should be sufficiently detailed to permit valid conclusions to be drawn about the real system. Different models of the same system could be required as the purpose of investigation changes.

Just as the components of a system include entities, attributes, and activities, so too models are represented. However, the model contains only those components that are relevant to the study.

10 Types of Models

Models can be classified as being mathematical or physical. A mathematical model uses symbolic notation and mathematical equations to represent a system. A simulation model is a particular type of mathematical model of a system. A physical model is a larger or smaller version of an object such as the enlargement of an atom or a scaled-down version of the solar system.

Simulation models may be further classified as being static or dynamic, deterministic or stochastic, and discrete or continuous. A static simulation model, sometimes called a Monte Carlo simulation, represents a system at a particular point in time. Dynamic simulation models represent systems as they change over time. The simulation of a bank from 9:00 A.M. to 4:00 P.M. is an example of a dynamic simulation.

Simulation models that contain no random variables are classified as deterministic. Deterministic models have a known set of inputs, that will result in a unique set of outputs. Deterministic arrivals would occur at a dentist’s office if all patients arrived at their scheduled appointment times. A stochastic simulation model has one or more random variables as inputs. Random inputs lead to random outputs. Since the outputs are random, they can be considered only as estimates of the true characteristics of a model. The simulation of a bank would usually involve random interarrival times and random service times. Thus, in a stochastic simulation, the output measures—the average number of people waiting, the average waiting time of a customer—must be treated as statistical estimates of the true characteristics of the system.

Discrete and continuous systems were defined in Section 7. Discrete and continuous models are defined in an analogous manner. However, a discrete simulation model is not always used to model a discrete system, nor is a continuous simulation model always used to model a continuous system. Tanks and pipes might be modeled discretely, even though we know that fluid flow is continuous. In addition, simulation models may be mixed, both discrete and continuous. The choice of whether to use a discrete or continuous (or both discrete and continuous) simulation model is a function of the characteristics of the system and the objective of the study. Thus, a communication channel could be modeled discretely if the characteristics and movement of each message were deemed important. Conversely, if the flow of messages in aggregate over the channel were of importance, modeling the system via continuous simulation could be more appropriate. The models emphasized in this text are dynamic, stochastic, and discrete.

11 Discrete-Event System Simulation

This is a text about discrete-event system simulation. Discrete-event system simulation is the modeling of systems in which the state variable changes only at a discrete set of points in time. The simulation models are analyzed by numerical rather than analytical methods. Analytical methods employ the deductive reasoning of mathematics to “solve” the model. For example, differential calculus can be used to compute the minimum-cost policy for some inventory models. Numerical methods employ computational procedures to “solve” mathematical models. In the case of simulation models, which employ numerical methods, models are “run” rather than solved—that is, an artificial history of the system is generated from the model assumptions, and observations are collected to be analyzed and to estimate the true system performance measures. Real-world simulation models are rather large, and the amount of data stored and manipulated is vast, so such runs are usually conducted with the aid of a computer.

In summary, this text is about discrete-event system simulation in which the models of interest are analyzed numerically, usually with the aid of a computer.

12 Steps in a Simulation Study

Figure 3 shows a set of steps to guide a model builder in a thorough and sound simulation study. Similar figures and discussion of steps can be found in other sources [Shannon, 1975; Gordon, 1978; Law, 2007]. The number beside each symbol in Figure 3 refers to the more detailed discussion in the text. The steps in a simulation study are as follows:

Figure 3 Steps in a simulation study.

1. Problem formulation

Every study should begin with a statement of the problem. If the statement is provided by the policymakers or those that have the problem, the analyst must ensure that the problem being described is clearly understood. If a problem statement is being developed by the analyst, it is important that the policymakers understand and agree with the formulation. Although not shown in Figure 3, there are occasions where the problem must be reformulated as the study progresses. In many instances, policymakers and analysts are aware that there is a problem long before the nature of the problem is known.

2. Setting of objectives and overall project plan

The objectives indicate the questions to be answered by simulation. At this point, a determination should be made concerning whether simulation is the appropriate methodology for the problem as formulated and the objectives as stated. Assuming that it is decided that simulation is appropriate, the overall project plan should include a statement of the alternative systems to be considered and of a method for evaluating the effectiveness of these alternatives. It should also include the plans for the study in terms of the number of people involved, the cost of the study, and the number of days required to accomplish each phase of the work, along with the results expected at the end of each stage.

3. Model conceptualization

The construction of a model of a system is probably as much art as science. Pritsker [1998] provides a lengthy discussion of this step. “Although it is not possible to provide a set of instructions that will lead to building successful and appropriate models in every instance, there are some general guidelines that can be followed” [Morris, 1967]. The art of modeling is enhanced by an ability to abstract the essential features of a problem, to select and modify basic assumptions that characterize the system, and then to enrich and elaborate the model until a useful approximation results. Thus, it is best to start with a simple model and build toward greater complexity. However, the model complexity need not exceed that required to accomplish the purposes for which the model is intended. Violation of this principle will only add to model-building and computer expenses. It is not necessary to have a one-to-one mapping between the model and the real system. Only the essence of the real system is needed.

It is advisable to involve the model user in model conceptualization. Involving the model user will both enhance the quality of the resulting model and increase the confidence of the model user in the application of the model. (However, only experience with real systems—versus textbook problems—can “teach” the art of model building.)

4. Data collection

There is a constant interplay between the construction of the model and the collection of the needed input data [Shannon, 1975]. As the complexity of the model changes, the required data elements can also change. Also, since data collection takes such a large portion of the total time required to perform a simulation, it is necessary to begin as early as possible, usually together with the early stages of model building.

The objectives of the study dictate, in a large way, the kind of data to be collected. In the study of a bank, for example, if the desire is to learn about the length of waiting lines as the number of tellers changes, the types of data needed would be the distributions of interarrival times (at different times of the day), the service-time distributions for the tellers, and historic distributions on the lengths of waiting lines under varying conditions. This last type of data will be used to validate the simulation model. (See an excellent discussion by Henderson [2003].)

5. Model translation

Most real-world systems result in models that require a great deal of information storage and computation, so the model must be entered into a computer-recognizable format. We use the term program even though it is possible, in many instances, to accomplish the desired result with little or no actual coding. The modeler must decide whether to program the model in a simulation language, such as GPSS/H™, or to use special-purpose simulation software. For manufacturing and material handling, there exists such software as AnyLogic®, Arena®, AutoMod™, Enterprise Dynamics®, Extend™, Flexsim, ProModel®, and SIMUL8®. Simulation languages are powerful and flexible. However, if the problem is amenable to solution with the simulation software, the model development time is greatly reduced. Furthermore, most simulation software packages have added features that enhance their flexibility, although the amount of flexibility varies greatly.

6. Verified?

Verification pertains to the computer program that has been prepared for the simulation model. Is the computer program performing properly? With complex models, it is difficult, if not impossible, to translate a model successfully in its entirety without a good deal of debugging; if the input parameters and logical structure of the model are correctly represented in the computer, verification has been completed. For the most part, common sense is used in completing this step. (Sargent [2007] discusses this topic.)

7. Validated?

Validation usually is achieved through the calibration of the model, an iterative process of comparing the model against actual system behavior and using the discrepancies between the two, and the insights gained, to improve the model. This process is repeated until model accuracy is judged acceptable. In the previously mentioned example of a bank, data was collected concerning the length of waiting lines under current conditions. Does the simulation model replicate this system measure? This is one means of validation. (Sargent [2007] discusses this topic.)

8. Experimental design

The alternatives that are to be simulated must be determined. Often, the decision concerning which alternatives to simulate will be a function of runs that have been completed and analyzed. For each system design that is simulated, decisions need to be made concerning the length of the initialization period, the length of simulation runs, and the number of replications to be made of each run. (Sanchez [2007] discusses this topic extensively.)

9. Production runs and analysis

Production runs and their subsequent analysis, are used to estimate measures of performance for the system designs that are being simulated. (Software to aid in this step, include AutoStat (in AutoMod), OptQuest (in several pieces of simulation software), and SimRunner (in ProModel).)

10. More runs?

Given the analysis of runs that have been completed, the analyst determines whether additional runs are needed and what design those additional experiments should follow.

11. Documentation and reporting

There are two types of documentation: program and progress. Program documentation is necessary for numerous reasons. If the program is going to be used again by the same or different analysts, it could be necessary to understand how the program operates. This will create confidence in the program, so that model users and policymakers can make decisions based on the analysis. Also, if the program is to be modified by the same or a different analyst, this step can be greatly facilitated by adequate documentation. One experience with an inadequately documented program is usually enough to convince an analyst of the necessity of this important step. Another reason for documenting a program is so that model users can change parameters at will in an effort to learn the relationships between input parameters and output measures of performance or to discover the input parameters that “optimize” some output measure of performance.

Musselman [1998] discusses progress reports that provide the important, written history of a simulation project. Project reports give a chronology of work done and decisions made. This can prove to be of great value in keeping the project on course. Musselman suggests frequent reports (monthly, at least) so that even those not involved in the day-to-day operation can be kept abreast. The awareness of these others can often enhance the successful completion of the project by surfacing misunderstandings early, when the problem can be solved easily. Musselman also suggests maintaining a project log to provide a comprehensive record of accomplishments, change requests, key decisions, and other items of importance.

On the reporting side, Musselman suggests frequent deliverables. These may or may not be the results of major accomplishments. His maxim is that “it is better to work with many intermediate milestones than with one absolute deadline.” Possibilities prior to the final report include a model specification, prototype demonstrations, animations, training results, intermediate analyses, program documentation, progress reports, and presentations. He suggests that these deliverables should be timed judiciously over the life of the project.

The results of all the analysis should be reported clearly and concisely in a final report. This will allow the model users (now the decision makers) to review the final formulation, the alternative systems that were addressed, the criteria by which the alternatives were compared, the results of the experiments, and the recommended solution(s) to the problem. Furthermore, if decisions have to be justified at a higher level, the final report should provide a vehicle of certification for the model user/decision maker and add to the credibility of the model and of the model-building process.

12. Implementation

The success of the implementation phase depends on how well the previous eleven steps have been performed. It is also contingent upon how thoroughly the analyst has involved the ultimate model user during the entire simulation process. If the model user has been involved during the entire model-building process and if the model user understands the nature of the model and its outputs, the likelihood of a vigorous implementation is enhanced [Pritsker, 1995]. Conversely, if the model and its underlying assumptions have not been properly communicated, implementation will probably suffer, regardless of the simulation model’s validity.

The simulation-model building process shown in Figure 3 can be broken down into four phases. The first phase, consisting of steps 1 (Problem formulation) and 2 (Setting of objective and overall design), is a period of discovery or orientation. The initial statement of the problem is usually quite “fuzzy,” the initial objectives will usually have to be reset, and the original project plan will usually have to be fine-tuned. These recalibrations and clarifications could occur in this phase or perhaps will occur after or during another phase (i.e., the analyst might have to restart the process).

The second phase is related to model building and data collection and includes steps 3 (Model conceptualization), 4 (Data collection), 5 (Model translation), 6 (Verification), and 7 (Validation). A continuing interplay is required among the steps. Exclusion of the model user during this phase can have dire implications at the time of implementation.

The third phase concerns the running of the model. It involves steps 8 (Experimental design), 9 (Production runs and analysis), and 10 (More runs). This phase must have a comprehensively conceived plan for experimenting with the simulation model. A discrete-event stochastic simulation is, in fact, a statistical experiment. The output variables are estimates that contain random error, and therefore a proper statistical analysis is required. Such a philosophy is in contrast to that of the analyst who makes a single run and draws an inference from that single data point.

The fourth phase, implementation, involves steps 11 (Documentation and reporting) and 12 (Implementation). Successful implementation depends on continual involvement of the model user and on the successful completion of every step in the process. Perhaps the most crucial point in the entire process is Step 7 (Validation), because an invalid model is going to lead to erroneous results, which, if implemented, could be dangerous, costly, or both.

References

BANKS, J. [2008], “Some Burning Questions about Simulation.” ICS Newsletter, INFORMS Computing Society, Spring.

BANKS, J., and R. R. GIBSON [1997], “Don’t Simulate When: 10 Rules for Determining when Simulation Is Not Appropriate,” IIE Solutions, September.

GORDON, G. [1978], System Simulation, 2d ed., Prentice-Hall, Englewood Cliffs, NJ.

HENDERSON, S. G. [2003], “Input Model Uncertainty: Why Do We Care and What Should We Do About It?” in Proceedings of the Winter Simulation Conference, eds. S. Chick, P. J. Sánchez, D. Ferrin, and D. J. Morrice, New Orleans, LA, Dec. 7–10, pp. 90–100.

KLEIJNEN, J. P. C. [1998], “Experimental Design for Sensitivity Analysis, Optimization, and Validation of Simulation Models,” in Handbook of Simulation, ed. J. Banks, John Wiley, New York.

LAW, A. M. [2007], Simulation Modeling and Analysis, 4th ed., McGraw–Hill, New York.

MORRIS, W. T. [1967], “On the Art of Modeling,” Management Science, Vol. 13, No. 12.

MUSSELMAN, K. J. [1998], “Guidelines for Success,” in Handbook of Simulation, ed. J. Banks, John Wiley, New York.

NAYLOR, T. H., J. L. BALINTFY, D. S. BURDICK, and K. CHU [1966], Computer Simulation Techniques, Wiley, New York.

PEGDEN, C. D., R. E. SHANNON, and R. P. SADOWSKI [1995], Introduction to Simulation Using SIMAN, 2d ed., McGraw–Hill, New York.

PRITSKER, A. A. B. [1995], Introduction to Simulation and SLAM II, 4th ed., Wiley & Sons, New York.

PRITSKER, A. A. B. [1998], “Principles of Simulation Modeling,” in Handbook of Simulation, ed. J. Banks, John Wiley, New York.

SANCHEZ, S.R. [2007], “Work Smarter, Not Harder: Guidelines for Designing Simulation Experiments,” in Proceedings of the 2007 Winter Simulation Conference, eds. S. G. Henderson, B. Biller, M.-H. Hsieh, J. Shortle, J. D. Tew, and R. R. Barton, Washington, DC, Dec. 9–12, pp. 84–94.

SARGENT, R.G. [2007], “Verification and Validation of Simulation Models,” in Proceedings of the 2007 Winter Simulation Conference, eds. S. G. Henderson, B. Biller, M.-H. Hsieh, J. Shortle, J. D. Tew, and R. R. Barton, Washington, DC, Dec. 9–12, pp. 124–137.

SHANNON, R. E. [1975], Systems Simulation: The Art and Science, Prentice-Hall, Englewood Cliffs, NJ.

SHANNON, R. E. [1998], “Introduction to the Art and Science of Simulation,” in Proceedings of the Winter Simulation Conference, eds. D. J. Medeiros, E. F. Watson, J. S. Carson, and M. S. Manivannan, Washington, DC, Dec. 13–16, pp. 7–14.

Exercises

1. Name several entities, attributes, activities, events, and state variables for the following systems:

   • (a) A cafeteria
   • (b) A grocery store
   • (c) A laundromat
   • (d) A fast-food restaurant
   • (e) A hospital emergency room
   • (f) A taxicab company with 10 taxis
   • (g) An automobile assembly line

2. Consider the simulation process shown in Figure 3.

   • (a) Reduce the steps by at least two by combining similar activities. Give your rationale.
   • (b) Increase the steps by at least two by separating current steps or enlarging on existing steps. Give your rationale.

3. A simulation of a major traffic intersection is to be conducted, with the objective of improving the current traffic flow. Provide three iterations, in increasing order of complexity, of steps 1 and 2 in the simulation process of Figure 3.

4. A simulation is to be conducted of cooking a spaghetti dinner, to discover at what time a person should start in order to have the meal on the table by 7:00 P.M. Download a recipe from the web for preparing a spaghetti dinner (or ask a friend or relative for the recipe). As best you can, trace what you understand to be needed, in the data-collection phase of the simulation process of Figure 3, in order to perform a simulation in which the model includes each step in the recipe. What are the events, activities, and state variables in this system?

5. What are the events and activities associated with the use of your checkbook?

6. Numerous reasons for simulation were given in Section 1. But there may be other reasons. Look at applications in the current WSC Proceedings and see if you can discover additional reasons. (WSC Proceedings are found at www.informs-cs.org/wscpapers.html)

7. In the current WSC Proceedings available at www.informs-cs.org/wscpapers.html, read an article on the application of simulation related to your major area of study or interest, and prepare a report on how the author accomplishes the steps given in Figure 3.

8. Get a copy of a recent WSC Proceedings from the URL in Exercise 7 and report on the different applications discussed in an area of interest to you.

9. Get a copy of a recent WSC Proceedings from the URL in Exercise 7 and report on the most unusual application that you can find.

10. Locate one of the cases in Section 12 and describe the methodology used.

11. Go to the Winter Simulation Conference website at www.wintersim.org and address the following:

    • (a) What advanced tutorials were offered at the previous WSC or are planned at the next WSC?
    • (b) Where and when will the next WSC be held?

12. Go to the Winter Simulation Conference website at www.wintersim.org and address the following:

    • (a) When was the largest (in attendance) WSC, and how many attended?
    • (b) In what calendar year, from the beginning of WSC, was there no conference?
    • (c) What was the largest expanse of time, from the beginning of WSC, between occurrences of the Conference?
    • (d) Beginning with the 25th WSC, can you discern a pattern for the location of the conference?

13. What is the procedure for contributing a paper to the WSC?

14. Classify the list of vendors at a recent WSC as software vendors and others.

15. What is the purpose and history of the WSC Foundation?

16. Using your favorite search engine, search the web for ‘discrete event simulation output analysis’ and prepare a report discussing what you find.

17. Using your favorite search engine, search the web for ‘supply chain simulation’ and prepare a report discussing what you find.

18. Using your favorite search engine, search the web for ‘web based simulation’ and prepare a report discussing what you find.

2 Simulation Examples in a Spreadsheet

This chapter uses spreadsheet examples to provide an introduction to simulation. The examples are relatively simple; many can be carried out manually as well as in a spreadsheet. Our main purpose is to introduce and illustrate some of the key concepts in simulation; it is not to teach how to formulate or develop a spreadsheet model, but rather to use a few simple spreadsheet models to illustrate, by example, some of the key elements of any simulation. These key elements range from the components of a model to experimentation with the model.

Although some types of real-world simulation models, such as those for risk analysis, financial analysis, some reliability problems and others, are amenable to a spreadsheet formulation and solution, the spreadsheet has severe limitations for most complex real-world dynamic, event-based simulations. More often, these complex models are developed in a simulation package or general purpose programming language, not in a spreadsheet.

The spreadsheet examples include both Monte Carlo simulations and dynamic simulations that track events over time. Spreadsheet simulations are carried out by devising a simulation table tha provides a method for tracking system state over time. Although the simulation tables contain a number of common elements, in general they are ad hoc, meaning they are custom designed for the problem at hand. Due to its ad hoc nature, a general framework for carrying out dynamic discrete-even simulations is needed.

The key elements introduced in this chapter include the use of random numbers to represen uncertainty, the descriptive statistics used for predicting system performance in queueing and inventory models, and the advantage of thinking of a model in terms of inputs, activities, events, states, outputs and responses. These topics are introduced here via example.

Section 1 covers the basics, such as generating random samples and the basic components of a simulation model; subsequent examples depend on the concepts and techniques learned here. The examples in the remaining sections cover application areas such as coin tossing, queueing or waiting lines, inventory policies, reliability, hitting a target (bombing or a dart board), and projec network analysis. In the examples, we put limited focus on model implementation; instead, we focus on identifying model components (inputs, events, states, and so on) and conducting a simple experiment, the key concept being trials or replications.

All of the examples in this chapter have a spreadsheet solution in Excel on the text’s web site, www.bcnn.net. The spreadsheets include notes and comments, which add technical detail to each example, including implementation details, which may prove of value to a student modifying an existing model or developing a new spreadsheet simulation model, as requested in some of the exercises.

1 The Basics of Spreadsheet Simulation

In this section we cover the basic material that allows us to carry out the example simulations in the remainder of the chapter. We will learn how to generate random numbers in a spreadsheet simulation, and where to obtain them for a manual simulation. We will learn how to generate random samples for a few simple situations, such as tossing a coin, service and arrival times for queueing simulations, and random demand for inventory models. The methods learned here are sufficient for any of the simple discrete statistical distributions used in the examples in this chapter.

1.1 How to Simulate Randomness

Almost all of the simulation models considered in this text contain one or more random variables. Clearly with coin tossing, some mechanism is needed to simulate a random toss that will result in a head or a tail. In queueing models, both service times and interarrival times may be defined by a statistical distribution when the arrival times and service times are not known in advance and canno be predicted but follow a statistical pattern.

How do we get random quantities? We leave alone the theory and general explanations behind the generation of random numbers and random variables. In this chapter, we take a pragmatic, practica point of view: How do we get random quantities for a spreadsheet or manual simulation?

Generating any random quantity begins with generating a random number in the interval from 0 to 1. The term “random number” always refers to a randomly generated quantity in the unit interval between 0 and 1. In contrast, the term “random variable” refers to any randomly generated quantity with a specified statistical distribution. Any method for generating a sequence of random numbers is called a Random Number Generator (RNG).

The generation method for random numbers should produce a sequence of numbers that have two important statistical properties:

1. The numbers should be uniformly distributed between 0 and 1.

2. Subsequent numbers generated should be statistically independent of all previous numbers generated.

Uniformity implies, among other things, that the probability of falling in an interval (a, b) (with a and b between 0 and 1) equals the length of the interval, b a. Statistical independence implies, among other things, that knowing the value ofpreviously generated numbers does not help in any way in predicting the value of numbers generated subsequently. In addition, it implies that the correlation between successive numbers is zero.

The resulting numbers are often called pseudo-random numbers. One reason is the paradox that, while we want the generated numbers to be statistically uniform and independent, we also wan control. We want to be able to reproduce the sequence at any time so that simulation experiments can be controlled and reproduced, and for another practical reason: to assist in model developmen and debugging.

In general, how do we get these random numbers? Where do they come from? (In what follows, VBA stands for Visual Basic for Applications, the implementation of the VB programming language in Excel and other Microsoft Office applications.) Here are a number of standard sources for random numbers:

1. In Excel, we can use the built-in worksheet function RAND in a formula in a cell. RAND generates values between 0 and 1. Typical examples of formulas using RAND include generating a random value between 0 and 1, as follows:

or in a more complex expression such as the following for generating one of two values, 0 or 1:

Note that the IF worksheet function checks a condition in its first argument, and if the condition is true returns the first value; otherwise it returns the second value.

2. Excel also provides the worksheet function, RANDBETWEEN(), that returns uniformly distributed integer values between a specified low and high value. Excel, or some of its add-ins, provide other functions to generate random values. We use none of these.

3. In a worksheet cell in Excel, we can call a user-written VBA function that, in turn, calls an internal VBA library function such as Rnd() or the VBA function (MRG32k3a) available on the text’s web site. The spreadsheet examples in this chapter all have the VBA function Rnd01() that can be called from a cell. (Rnd01() simply calls the internal VBA library function Rnd().)

4. Simulation packages provide methods to generate both random numbers and random variables from a long list of standard statistical distributions as well as from data.

5. Most general-purpose programming languages provide a built-in library function to generate random numbers, and many provide facilities to generate samples from a variety of statistical distributions. Lacking this, the model developer can program one or more algorithms.

6. For manual (paper-and-pencil) simulations, you could use a physical RNG such as tossing one or more coins, or throwing dice. These being impractical for all but the simplest cases, another possibility is a table of random numbers or random variables from a specific distribution, such as Tables A.1 (for uniform) and A.2 (for the standard normal) in the Appendix.

Neither the worksheet function RAND() nor the VB function Rnd() should be used in professional work; they both have known deficiencies. For example, the VB function Rnd() returns a single precision value (about 5 decimal place of accuracy), while all good RNG return double precision (about 15 decimal places); secondly, Rnd() has a short period—it repeats after generating a relatively small number of values. Its period is 2^24, about 16.77 million. The RAND() function has an even shorter period and more serious deficiencies regarding the two key properties of uniformity and independence. (Note that Microsoft changed the RAND() function in Office 2003; reportedly, i has both bugs and deficiencies and has been widely criticized.) We use RAND() only in Example 1, merely for instructional purposes. Since much better generators are readily available, including the VBA function MRG32k3a, on the text’s web site in the Excel file “RandomNumberTools.xls”, we feel strongly that there is no reason (or excuse) to use a deficient generator for professional work.

Most RNG can be initialized by a user-specified number called a seed. The VBA code behind the ‘Reset Seed & Run’ button in the spreadsheet examples shows how to set the seed for VBA’s Rnd() generator. Apparently, there is no way to set the seed for Excel’s RAND generator (another reason not to use it). The MRG32k3a generator (in “RandomNumberTools.xls”) comes with the VBA function, InitializeRNSeed(), for setting that generator’s seed. By specifying the seed, the user can make a random number generator repeat a sequence of numbers. This is valuable for debugging simulation models and repeating simulation experiments. Remember that we are simulating randomness; the control given by repeatability is a feature, not a bug.

1.2 The Random Generators Used in the Examples

Each example spreadsheet has a number of VBA functions for generating random variables in a few simple cases. We advise starting with an existing spreadsheet model when developing a new model; in this way, all the VBA functions written for the examples will be available for the new model.

The VBA functions and Excel worksheet functions for generating random values in a cell in a worksheet include the following:

1. Rnd01(), to generate a random number between 0 and 1;

2. DiscreteUniform(min, max), to generate a random integer from the minimum value, min, to the maximum value, max, where min and max can be numbers or a single-cell range containing the number;

3. DiscreteEmp(rCumProb, rValues), to generate samples from a discrete distribution specified by two Excel ranges (ranges of cells), rCumProb for the cumulative probabilities, and rValues for the values;

4. Uniform(low, high), to generate a real value (not just integers) from the continuous uniform distribution between low and high, where low and high are numbers or a cel containing a number;

5. NORMSINV(Rnd01()), to generate a standard normal with mean 0 and standard deviation 1.

All of these functions, except NORMSINV(), are VBA functions written for the examples in this chapter; NORMSINV() is an Excel worksheet function that can be used (in the form given above) to generate a standard normal. We recommend not using the worksheet functions RAND() and RANDBETWEEN(). All spreadsheet solutions have access to any of the functions, whether used or not in the supplied solution; therefore, the example spreadsheets are good starting points for some of the exercises.

At this early point in the text, we do not expect the reader to completely understand how all of these work. Our goal, however, is that you understand the nature of the random values generated by each function, and be able to use them in the exercises if modifying an example or creating a new spreadsheet model. Each of these functions is explained in more detail as they are used in an example in later sections.

1.3 How to Use the Spreadsheets

The spreadsheet simulation models are in the ‘One Trial’ worksheet of each solution workbook. This sheet contains the definition and specification of model inputs, the simulation table containing the formulas to generate each row to carry the simulation forward, and some summary statistics (and usually a histogram) representing the results of one simulation run. The two buttons on the worksheet control the simulation:

1. On each click, the ‘Generate New Trial’ button makes a new run of the simulation, using a new sequence of random numbers each time.

2. On each click, the ‘Reset Seed & Run’ button sets the RNG seed to the value specified by the user in an adjacent cell, and then runs the simulation using this seed. The default seed is the arbitrary value 12,345.

You can always return to the initial results by clicking the ‘Reset Seed & Run’ button.

The ‘Experiment’ worksheet allows a user to conduct a simulation experiment by repeatedly executing the ‘One Trial’ worksheet, each time with different random numbers, and recording the designated model response (from the Link cell) to the Response Table. The user specifies the number of trials, for example, 100, meaning that the ‘One Trial’ worksheet will be executed 100 times and the 100 response values recorded in the Response Table. This is called replication; the number of replications is the number of trials.

The experimental results over all trials are summarized in the “Multi-Trial Summary” table on the ‘Experiment’ sheet. These summary statistics include frequency distributions and an accompanying histogram, and standard statistics such as sample average, median, minimum, and maximum. An example is shown in Table 6 in Section 2.

To run the experiment on the ‘Experiment’ worksheet, use the two buttons as follows:

1. On each click, the ‘Run Experiment’ button makes one run of the experiment for the specified number of trials. Each subsequent click runs the experiment using different random numbers.

2. On each click, the ‘Reset Seed & Run’ button sets the RNG seed to the specified value in an adjacent cell (default 12,345) and makes one run of the experiment. Each click reproduces the exact same original results.

The results given in all the examples in this chapter come from clicking the ‘Reset Seed & Run button; this guarantees that a reader can reproduce these same results. Each spreadsheet solution contains comments and explanations on different aspects of the solution, including the implementation of model logic; some solutions have a worksheet named ‘Explain’ with lengthier explanations of certain aspects of the model.

1.4 How to Simulate a Coin Toss

How can we simulate a coin toss in a spreadsheet model? The solution shows how to use a uniform random number generator in a spreadsheet simulation.

Example 1: Coin Tossing

We want to simulate a sequence of 10 coin tosses. The coin is a “fair” coin, meaning that the chance of getting a head is the same as getting a tail. Each has probability 0.5 of occurring. You should run the simulation multiple times and compare the results with your expectations from real-life coin tossing. This is an example of a Monte Carlo simulation; there are no events or clock times being tracked.

The solution, shown in Table 1, is in the spreadsheet “Example2.1CoinToss.xls”. In fact, there are four solutions in the spreadsheet, the first two using the RAND() random number generator, and the last two using the supplied VBA function Rnd01(). It is left as an exercise (at the end of the chapter) to devise a justification for the statistical equivalence of the 4 solutions, even though on any click of the button ‘Generate New Trial’, the 4 sets of results are different.

Table 1 Simulation Table for Coin Tossing

The spreadsheet logic for coin tossing is simple. The second solution (Column E) is:

while the fourth solution (Column I) is:

Each call to RAND() or Rnd01() produces a new random number. The ‘One Trial’ workshee records the frequency for heads versus tails in the 10 tosses and graphs the results in a histogram.

The first and third solutions are two steps, an approach that is useful when a generated random number is used more than once. Columns C and G contain the generated random number, and columns D and H the result $( ^ {66} \mathrm{H} ^ {3} \mathrm{o r} ^ {66} \mathrm{T} ^ {3} )$. The fourth solution is the basis for the Coin Tossing Game in Example 4.

For all future spreadsheet simulations, we use the supplied VBA function, Rnd01(), or one of the VBA functions based on Rnd01(), instead of RAND(). However, for serious professional work, we recommend using the generator implemented in the VBA function, MRG32k3a, from the file “RandomNumberTools.xls”. As previously mentioned, both the Excel worksheet function, RAND(), and the VBA function, Rnd(), have serious limitations and deficiencies, and should only be used for casual or educational purposes.

1.5 How to Simulate a Random Service Time

The following example shows how to generate random samples from an arbitrary discrete distribution. The example is simple, having just 3 possible values of service time. The key principle, namely, the transformation from a random number to a service time of a prescribed probability, easily generalizes to any discrete distribution with a finite number of possible values.

The methods described here and in Section 1.6 for arrival times are used in almost all of the subsequent examples in the chapter.

Example 2: Random Service Times

An automated telephone information service spends either 3, 6, or 10 minutes with each caller. The proportion of calls for each service length is 30%, 45%, and 25%, respectively. We want to simulate these service times in a spreadsheet. Our actual purpose is to learn how to generate random samples from a discrete distribution, in preparation for the queueing, inventory, and other examples to follow. This also is an example of a Monte Carlo simulation.

Table 2 shows the input specification and a portion of the simulation table (the first 4 callers), taken from the spreadsheet model, “Example2.2ServiceTimes.xls”. The input specification defines the probabilities for the service times, and also includes the cumulative probabilities. Cumulative probabilities always increase to 1.0; as we shall see, the generation method uses the cumulative probabilities. The method always starts with a random number and ends with the desired value, in this case, a random service time with the specified distribution. The simulation table in the spreadsheet shows the resulting frequency distribution (or histogram) of the generated service times for 25 callers.

Table 2 Input Specification and Simulation Table for Service Times

Figure 1 illustrates how to transform a random number to a service time. Think of it as throwing a special dart at a special dart board; the dart will always land somewhere on the unit interval, with equal probability of landing at any of the points on the line between 0 and 1. The subinterval where the dart lands determines the value generated.

In Figure 1, the probabilities (at the top) are represented by non-overlapping segments on a uni interval, and must add up to 1. The cumulative probabilities (just below the line) are represented by points on the line. The arrows represent the transformation. The algorithm works as follows: First, choose a random number, say R. If R is in the first interval, that is, if R is less than or equal to 0.30, the procedure generates a sample of 3 minutes for service time. Similarly, if R is between 0.30 and 0.75, the service time is 6 minutes, and finally, if R is greater than 0.75, then the service time is 10 minutes. This algorithm easily generalizes to any discrete distribution

To illustrate the procedure, we first generate 5 samples of random numbers, either in Exce (using RAND or Rnd01 or any other random number generator), or take 5 samples from a table of random numbers such as Table A.1 in the Appendix. Suppose the 5 samples are: 0.98710.02260.00080.21280.8586

After the transformation illustrated in Figure 1, the resulting service times are: 10333 10

In a small sample (here, size 5), we cannot expect the observed frequencies of occurrence of each value to be close to the probabilities; however, with a large enough sample, the sample frequencies should be fairly close to the probabilities. You can experiment with the spreadsheet example, “Example2.2ServiceTimes.xls”, to see how close or far small samples can be from the assumed probabilities.

Figure 1 ‘‘Random Dart’’ Transformation from Random Number to Service Time.

In Excel, we might think we could implement this transformation, at least for distributions with a small number of values (here, 3), with a nested IF worksheet function, as in:

This attempt at a solution introduces a grave error. Each reference to the Rnd01() function generates a new random number; the transformation procedure depends on usingjust one random number. (You may want to modify the spreadsheet solution in “Example2.2ServiceTimes.xls” with this incorrect solution to see the resulting probabilities.) This approach can be modified to use two cells, the first to hold the result from Rnd01, the second with a modified IF statement.

A better approach is to use the VBA function called DiscreteEmp() (for discrete empirical, meaning defined by data) supplied with all the examples. To see how this function is used, see the spreadsheet solution, “Example2.2ServiceTimes.xls”; a typical cell for generating a random service time appears as follows:

where $ D$7:$ D$9 is the range of cells containing the cumulative probabilities and $ B$7:$ B$9 is the range of cells containing the desired values for service times. Discrete means that only the values listed will be generated. Each of the two worksheet ranges must be a column vector (meaning al data in one column), with each having the same length, that is, the same number of cells. The “$” in each address in front of each row and column indicates an absolute address rather than a relative address; this makes it easier to copy and paste the formula into all the cells in the “Service Time” column after typing it into just one cell.)

The method used here with the supplied VBA function, DiscreteEmp(), easily generalizes to most of the examples (and exercises) in the chapter that use simple discrete distributions for model inputs. To use DiscreteEmp(), supply two ranges in the worksheet, one for cumulative probabilities and the second for the desired values. It works with any number of values in the distribution.

In future examples, keep Figure 1 in mind; it illustrates exactly how DiscreteEmp() works. Although its VBA implementation involves a loop and may appear complex to a non-programmer, its basic logic is the simple logic of Figure 1 — the simple logic of throwing a dart at a special dar board, the unit interval, and a transformation.

1.6 How to Simulate a Random Arrival Time

In this section our goal is to learn how to generate random interarrival times (times between successive arrivals) and compute arrival times of customers or other entities to a system. The interarrival times, as well as the service times in Example 2, are examples of simulation-generated time durations, called activity times or activities. These are distinguished from arrival times, which are times on a simulation clock representing the time-of-arrival to a facility.

A simulation clock is a key component of every dynamic discrete-event simulation. In all of the Excel spreadsheet solutions, the clock times are labeled just above the appropriate column titles of the simulation table, so that you can easily distinguish between the activity times (service or interarrival times, for example) and the computed clock times. In all cases, a clock time represents the time of occurrence of an event, such as an arrival, a service beginning, or a service completion in a queueing model.

Example 3: Random Arrival Times

Telephone calls to the telephone information service, where service times are defined in Example 2, occur at random times defined by a discrete distribution for which the interarrival times have values 1, 2, 3, or 4 minutes, all with equal probability. Our purpose here is to show how to generate both interarrival times and arrival times.

Since this example has one event, namely, the arrival event, it is our first example of a dynamic, event-based model (despite its simplicity). Dynamic simply means time-based, with system state changing over time; dynamic, event-based means that the model tracks the progression of even occurrences over time.

The interarrival times can be generated randomly in exactly the same manner as done in Example 2 for service times. The spreadsheets, however, supply a second VBA function to simplify random generation from a discrete uniform distribution. Uniform means that all the values have equal probabilities; in this example, all the interarrival times may have one of the values 1, 2, 3, or 4 minutes, each occurring with probability 0.25. For such discrete uniform distributions, the spreadsheets supply the VBA function, DiscreteUniform(), which takes two arguments: either the cell containing the minimum value followed by the cell containing the maximum value of the desired range of integers, or the actual low and high values, as in:

or

The DiscreteUniform(low, high) function is implemented by a single line of VBA code, as follows:

which becomes, for this example:

where Rnd() generates a random number between 0 and 1 (in VBA, it is always less than one bu may equal zero), and Int() is a VBA function that truncates (rounds down) its argument. (Note that 4 * Rnd() generates real values between 0.0 and 3.99999, so that truncating and then adding 1 yields the desired range 1 to 4. Why do we expect equal probabilities?)

Table 3 shows the input specification for interarrival times and a portion of the simulation table, taken from the spreadsheet model in “Example2.3ArrivalTimes.xls”. As shown in Step 1 (row 14), we assume that the first arrival occurs at simulation time 0. (The assumed arrival time for the firs customer is model-dependent; it could be any other specified time, constant or random.) The interarrival times are randomly and independently generated using the DiscreteUniform(1, 4) function. The arrival times are computed by a simple formula, by adding the current customer’s interarrival time to the previous customer’s arrival time. (You should verify the spreadsheet formula for arrival times.)

Table 3 Input Specification and Simulation Table for Arrival Times.

Example 3 is the first that contains an event, namely, the arrival event, and the event time associated with that event, namely, the CLOCK time for the time of arrival. Note that Table 3 distinguishes the activity times from the CLOCK times.

1.7 A Framework for Spreadsheet Simulation

The simulation table provides the structure, and the steps outlined below provide a set of general guidelines for carrying out a spreadsheet simulation. We have seen several examples of a simulation table, with Table 3 in Example 3 being the best so far—since it contains a clock time for the arrival event, making it one of the simplest possible dynamic, event-based simulations.

First, the model developer must define the model inputs, the system states, and the mode outputs. Inputs are the exogenous variables that are (usually) defined independently of other system characteristics; examples include the probability of a head on a coin toss, the service time and the interarrival time distributions in a queueing system, or the demand distribution in an inventory model. These input specifications are used to generate random activity times and other random variables. Other inputs, such as policy or decision parameters, may be constants.

Outputs are used to compute measures of system performance (also known as model responses, or simply responses). For example, an output could be an individual customer’s waiting time in a queue, or the cost of an individual transaction in an inventory system. The associated responses might be average waiting time in a queue, or the average cost per unit time in an inventory system, respectively.

Each simulation table is custom designed for the problem at hand. Each column in the table is one of the following types:

1. An activity time associated with a model input;

2. Any other random variable defined by a model input;

3. A system state;

4. An event, or the clock time of an event;

5. A model output;

6. Sometimes, a model response.

For the spreadsheet simulations here, the above-listed items are sufficient.

In general, model responses, also known as measures of system performance, are computed outside the simulation table after the simulation has been completed. For example, in a waiting line model, the delay in queue of each individual customer is a model output, while the average delay over all customers is a model response. The model output is tracked in the simulation table; the response is computed afterwards.

An activity time is a time defined by a constant or a statistical distribution, such as a service time, or an interarrival time. An activity is a duration of time, in contrast to event times, which are clock times.

System states include, for example, server status (busy or idle) in a queueing model and inventory levels in an inventory model. In general, the set of system states includes any information needed for the simulation to proceed through time (or from one step to the next), as well as any quantity or information that makes the simulation logic simpler or more transparent and thus easier to understand. The greatest simplicity possible, as long as the model logic is correct, assists in an ease of understanding that is of tremendous value, especially when trying to verify that a model’s logic is indeed correct.

Table 4 A Generic Simulation Table

Each row in the simulation table represents a step in the simulation and is usually associated with the occurrence of one or more events, or the progress of one entity (such as a customer) through the system. The simulation table is designed so that a given step depends solely on model inputs and/or one or more previous steps or previously computed values in the current step.

In general, a modeler develops and runs a spreadsheet or manual simulation by following these guidelines:

1. Determine the characteristics of each of the inputs to the simulation. Often encountered types of inputs include constants as well as probability distributions.

2. Determine the activities, events, and system states relevant to the problem.

3. Determine model responses or summary performance measures, depending on objectives and specific questions to meet those objectives.

4. Determine the model outputs needed for computing model responses.

5. Construct a simulation table. A generic representation of a simulation table is shown in Table 4. In this table, there are p activities and system states,$x_{i j} , j = 1 , 2 , \dotsc , p .$, and one output, y_i, for each simulation step $i = 1 , 2 , \dots , n$. Initialize the table by filling in the data for Step 1. When doing a spreadsheet model, the initial step or steps (usually just Step 1) are typically different from subsequent steps, which are defined by formulas.

6. For each Step i, generate a value for each of the activities, then compute the system states and outputs y . Random input values may be computed by sampling values from the distributions chosen in Step 1. An output typically depends on the inputs, system states, and possibly other outputs.

7. When the simulation is finished, use the outputs to compute the model responses or measures of performance.

In the following sections, we will see several examples of spreadsheet simulations carried out in a custom-designed simulation table. These include examples of a coin tossing game, plus examples in application areas such as queueing, inventory, reliability, and network analysis. The coin tossing game asks an easy question yet has an answer that we believe will be surprising to most readers.

The two queueing examples provide illustrations of single-server and two-server systems. The first ofthe inventory examples involves a problem that has a closed-form solution; thus, the simulation solution can be compared to the mathematical solution. The second inventory example pertains to the classic order-level model.

The remaining examples include a model of hitting a target, a reliability model, a Monte Carlo model to estimate the distribution of a complex random variable, namely, lead-time demand, and finally, a model of a project activity network. The target hitting model introduces the use of normally distributed random numbers.

2 A Coin Tossing Game

In a coin tossing game, is it more likely that you and your opponent each share the lead about 1/2 of the time (that is, on about 1/2 of the tosses), compared to, say, one of you being ahead most of the time?

With the following example, we explain in more detail the layout of the spreadsheet solutions, the two main worksheets (‘One Trial’ and ‘Experiment’), the buttons to run the simulations, and the terminology used: trials (or replications) and experiments. The details of model logic (formulas used, functions called, and so on) are explained in the spreadsheet itself, all of which can be found at the text’s web site, www.bcnn.net.

Example 4: A Coin Tossing Game

Charlize tosses a coin for her friends, Harry and Tom, exactly 100 times. Harry wins $1.00 when a head lands up, and Tom loses $1.00. Tom wins when the coin lands with tails up, with Harry paying $1. Charlize tracks their respective wins and losses as they play the game. On any toss, Harry could be ahead, or Tom could be ahead, or they could be even.

On any game (a game being exactly 100 tosses), is it more likely that both Harry and Tom are each ahead on about 1/2 of the tosses, or is it more likely that one of the two is ahead most of the time?

Note that we are not asking about winnings at the end of the game; we are not asking about the proportion of heads versus tails (which, as you know, should be close to 50:50 in the long run). The question concerns how often Harry or Tom is ahead or behind during the course of the game. Note also that the two possibilities in the question are not the only two possible results of a game; therefore, their probabilities will not add up to 1.

To be specific, which of these is more likely, and by about how much?

(A) Harry and Tom are each ahead on about 1/2 of the tosses; specifically, Harry is ahead on 45 to 55 of the tosses, and thus Tom is also ahead on 45 to 55 of the tosses; or

(B) Harry is ahead on 95 or more tosses; or

(C) Harry is ahead on 5 or fewer tosses.

Guess before looking at the results. Table 5 shows the input specifications and the first 14 tosses in the simulation table, taken from the spreadsheet model in “Example2.4CoinTossGame.xls” when using the default seed (12,345) and clicking the button ‘Reset Seed & Run’. The ‘One Trial’worksheet has the logic and results for one game of 100 tosses.

Table 5 Input Specification and Simulation Table for the Coin Tossing Game

If you inspect the ‘One Trial’worksheet in the spreadsheet solution (for the trial using the default seed for the RNG), you will see that on toss 13, Harry’s winnings are negative (he’s losing money) and they stay negative for the remainder of the game; in fact, in this game, Tom is ahead on 92 of the 100 tosses, yet his winnings at the end are just $6.00. Harry is ahead on just 2 of the 100 tosses, and they are even on 6 of the 100 tosses (the last time on toss 12).

Now, we cannot answer the questions asked by playing just one game (equivalent to clicking the ‘Generate New Trial’ button once, since each trial is one game of 100 tosses). To play many games, we use the ‘Experiment’ worksheet and set the Number of Trials (cell C3) to 400. (Any fairly large number of trials will do for our present purposes.) Then click the button labeled ‘Reset Seed & Run’, which sets the seed to its default value (12,345) and runs the experiment with this seed. Running the experiment means that the ‘One Trial’ worksheet is executed 400 times, and after each trial, the result of the trial is recorded in the ‘Experiment’ worksheet. The spreadsheet contains comments and explanations for the formulas, functions, and other technical details for implementing model logic and collecting the desired outputs.

Table 6 Experiment Worksheet for the Coin Tossing Game

Table 6 shows the experimental specification (400 trials and the response) plus the Response Table for the first 11 trials (first 11 games), plus the Multi-Trial Summary. Figure 2 shows the histogram based on the frequency results in the Multi-Trial Summary.

Based on the experiment with 400 trials (or replications), the results may appear surprising to many people:

Harry behind most ofthe time In 73 of the 400 games (18.3%), Harry is ahead on 5 or fewer of the 100 tosses.

Harry and Tom about the same In 28 of the 400 games (7.0%), Harry and Tom share the lead abou equally.

Harry ahead most ofthe time In 46 of the 400 games (11.5%), Harry is ahead on 95 or more of the 100 tosses.

Figure 2 Histogram for Harry’s Chances of Being Ahead.

Of course, these three possibilities are not the only possibilities; that is why the frequencies do not add up to 400 games or 100%.You may wonder: What explains that the result “0 to 5” appears to be more likely than “95 to 100”, and that both are more likely than Tom and Harry sharing the lead about half of the time? What about the magnitude of this difference? Do these results contradict the assumption that the coins are “fair” and heads and tails have equal probability? Do these results say anything about Harry or Tom’s final winnings or losses?

You may experiment by clicking the ‘Run Experiment’ button several times, to see how the results vary from one experiment to the next. With 400 games constituting each experiment, it seems intuitively that the results would not change too much. One run of the experiment is identical to an other except that a new set of random numbers is used. (You can always return to the original random numbers and original results presented here by clicking the ‘Reset Seed & Run’ button.) To verify the results quoted here based on 400 games (i.e., 400 trials), you could run an experiment with a very large number, say, 4000 trials. Accuracy increases as the number of trials increases.

3 Queueing Simulation in a Spreadsheet

We begin by describing the components of queueing or waiting line models. We follow with two examples: a single-server queue and a two-server queue; both are dynamic, event-based models.

Figure 3 Single-channel queueing system.

3.1 Waiting Line Models

A queueing system is described by its calling population, the nature of the arrivals, the service mechanism, the system capacity, and the queueing discipline. A simple single-channel queueing system is portrayed in Figure 3. The members of the calling population may be, for example, customers, telephone calls, or jobs in a repair shop; here, we refer to them as units.

In the simple models in this chapter, we assume an unlimited potential calling population and a constant arrival rate. That is, no matter how many units have already arrived or are still present in the system, the interarrival time until the next arrival follows the same statistical distribution. Arrivals for service occur one at a time in a random fashion; once they join the waiting line, they are eventually served. In addition, service times are of some random length according to a probability distribution which does not change over time. The system capacity has no limit, meaning that any number of units can wait in line. Finally, units are served in the order of their arrival (often called FIFO: firs in, first out, or FCFS: first come, first served) by a single server or multiple parallel servers.

Services and arrivals are defined by the distribution of service times and the distribution of time between arrivals, respectively, as illustrated by Examples 2 and 3. For any simple single- or multi-channel queue, the overall effective arrival rate must be less than the total service rate, or the waiting line will grow without bound. When queues grow without bound, they are termed explosive or unstable. (In some re-entrant queueing networks in which units return a number of times to the same server before finally exiting from the system, the condition that arrival rate be less than service rate might not guarantee stability. See Harrison and Nguyen [1995] for more explanation. Interestingly, this type of instability was noticed first, not in theory, but in actual manufacturing in semiconductor manufacturing plants.) More complex situations can occur—for example, arrival rates that are greater than service rates for short periods of time, or networks of queues with routing. However, this chapter sticks to the most basic queues.

How do the concepts of system state, events, and simulation clock apply to queueing models? System state for a queueing model typically consists of the number of units in the system and server status, either busy or idle. An event is a set of circumstances that causes an instantaneous change in the state of the system. In a single-channel (or any multi-channel) queueing system, the events are the arrival event, the service beginning event, and the departure event, also called the service completion event. The simulation clock is used to track simulated time.

When a departure event occurs, the simulation proceeds in the manner shown in the flow diagram of Figure 4. The departure event causes the system state to change. If there are no units waiting in the queue, server status changes to idle; if there are one or more units waiting, the next unit begins service. In both cases, the number of units in the system decreases by one.

Figure 4 Departure event flow diagram.

The flow diagram for the arrival event is shown in Figure 5. The unit finds the server either idle or busy; therefore, either the unit begins service immediately, or it enters the queue. The unit follows the course of action shown in Figure 6. If the server is busy, the unit enters the queue. If the server is idle and the queue is empty, the unit begins service. It is not possible for the server to be idle while the queue is nonempty.

Figure 5 Arrival event flow diagram.

Figure 6 Potential unit actions upon arrival.

Figure 7 Server outcomes after the completion of service.

After a service completion, the server either becomes idle or remains busy with the next unit. The relationship of these two outcomes to queue status is shown in Figure 7. If the queue is no empty, another unit engages the server, which then remains in the busy state. If the queue is empty, the server becomes idle. These two possibilities are shown as the shaded portions of Figure 7.

In most simulations, many events occur at random times, the randomness imitating uncertainty in real life. For example, it is not known with certainty when the next customer will arrive at a grocery checkout counter, or how long the bank teller will take to complete a transaction. In these cases, a statistical model of the data is developed either from data collected and analyzed or from subjective estimates and assumptions. For our purposes, we will assume simple discrete probability distributions for interarrival and service times.

Now, how can the events described here occur in simulated time? Simulations of queueing systems generally require the maintenance of an event list for determining what happens next. The event list tracks the future times at which the different types of events will occur. This chapter simplifies the simulation by tracking each unit explicitly. Note that this ad hoc approach is satisfactory for simple simulations in a spreadsheet, but the more systematic approach is essential for the more complex real-world simulations (and even the more interesting student simulations).

Table 7 was designed as a simulation table specifically for a single-channel queue that serves customers on a first-in–first-out (FIFO) basis. It keeps track of the clock time at which each even occurs. (Note that it contains no columns for outputs; these will be added in the next example.) This simulation table computes arrival times from an assumed sequence of interarrival times:

24126

Columns B, C, and E are simulation clock times. Column B, the arrival times, are computed solely from the generated interarrival times. Column E, the time for the departure (or service completion) event, is easily computed by the generated input in Column D and the time service begins in Column C. Thus we see that computing Column C, the time service begins, is the main challenge. For an arriving unit, service begins at the later of two times: its arrival time or the departure time of the previous unit. (For 2-server and other multi-server queues, it is not quite so easy to compute the service completion time.)

As shown in Table 7, the first customer arrives at clock time 0 and immediately begins service, which requires two minutes. Service is completed at clock time 2. The second customer arrives at clock time 2 and is finished at clock time 3. Note that the fourth customer arrived at clock time 7, bu service could not begin until clock time 9. This occurred because customer 3 did not finish service until clock time 9.

Table 7 Simulation Table Emphasizing Clock Times

Table 8 Chronological Ordering of Events

The occurrence of the arrival and departure events in chronological order is shown in Table 8 and Figure 8. While Table 8 is ordered by clock time, the events may or may not be ordered by customer number. The chronological ordering of events is the basis of the approach to discrete-even simulation.

Figure 8 depicts the number of customers in the system over time. It is a visual image of the event listing of Table 8. Customer 1 is in the system from clock time 0 to clock time 2. Customer 2 arrives at clock time 2 and departs at clock time 3. No customers are in the system from clock time 3 to clock time 6. During some time periods, two customers are in the system, such as at clock time 8, when customers 3 and 4 are both in the system. Also, there are times when events occur simultaneously, such as at clock time 9, when customer 5 arrives and customer 3 departs.

Figure 8 Number of customers in the system.

3.2 Simulating a Single-Server Queue

The first queueing example is a single-server queue. We illustrate how to compute typical outputs and performance measures, such as the customer’s average waiting time and the proportion of time the server is idle.

Example 5: The Grocery Checkout, a Single-Server Queue

A small grocery store has one checkout counter. Customers arrive at the checkout counter at random times that range from 1 to 8 minutes apart. We assume that interarrival times are integer-valued with each of the 8 values having equal probability; this is a discrete uniform distribution, as shown in Table 9. The service times vary from 1 to 6 minutes (also integer-valued), with the probabilities shown in Table 10. Our objective is to analyze the system by simulating the arrival and service of 100 customers and to compute a variety of typical measures of performance for queueing models.

In actuality, 100 customers may be too small a sample size to draw reliable conclusions. Depending on our objectives, the accuracy of the results may be enhanced by increasing the sample size (number of customers), or by running multiple trials (or replications). A second issue is that o initial conditions. A simulation of a grocery store that starts with an empty system may or may not be realistic unless the intention is to model the system from startup or to model until steady-state operation is reached. Here, to keep calculations simple, the starting conditions are an empty grocery, and any concerns are overlooked.

Table 9 Distribution of Time Between Arrivals

Table 10 Distribution of Service Times

How to generate service times and arrival times from the service time and interarrival time distributions has been covered in Sections 1.5 and 1.6, respectively; the same methods apply here and in subsequent examples. For manual simulations, use the random numbers in Table A.1 in the Appendix. It is good practice to start at a random position in Table A.1 and proceed in a systematic direction, never reusing the same stream of numbers in a given problem. If the same pattern is used repeatedly, statistical bias or other odd effects could affect the results.

Table 11 shows a portion of the simulation table for the single-channel queue, taken from “Example2.5SingleServer.xls”; it also shows totals and averages for selected columns (above the simulation table). The first step is to initialize the table by filling in cells for the first customer, who is assumed to arrive at time 0 with service beginning immediately. The customer finishes at time 2 minutes (the first random service time). After the first customer, subsequent rows in the table are based on the randomly generated values for interarrival time and service time of the current customer, the completion time of the previous customer, and, for the spreadsheet solution, the simulation logic incorporated in the formulas in the cells of the simulation table.

Continuing, the second customer arrives at time 5 minutes and service begins immediately. Therefore, the second customer has no wait in the queue and the server has 3 minutes of idle time.

Skipping down, we see that the fifth customer arrives at time 16 minutes and finds the server busy. At time 18, the previous customer leaves and the fifth customer begins service, having waited 2 minutes in the queue. This process continues for all 100 customers. The spreadsheet solution in “Example2.5SingleServer.xls” contains the formulas that implement the steps described here. To best understand these formulas, you should first attempt to do a manual simulation of a few steps, figure out the logic, and then study how the formulas implement the logic.

Columns G, I, and J have been added to collect three model outputs, namely, each customer’s time in queue and in system, and the server’s idle time (if any) between the previous customer’s departure and this customer’s arrival time. These model outputs are, in turn, used to compute severa measures of performance, namely, the customer’s average time in queue and in system, and the proportion of time the server is idle.

In order to compute the system performance measures, we can use the calculated responses in Table 11, which shows totals and averages for interarrival times, service times, the time customers wait in the queue, the time customers spend in the system, and idle time of the server. These results are taken from the first trial run on the ‘One Trial’ worksheet of the spreadsheet model when using the default RNG seed (12,345). With these results, we can illustrate a number of typical performance measures for waiting line models:

Ta ble 11 M od e l Res _po n ses a n d S i m u l at i o n Ta b l e (fi rst 11 cu sto m e rs) fo r t h e G roce r_y Sto re S i m u l at i o n

1. The average waiting time for a customer is 1.63 minutes, computed as follows:

2. The probability that a customer has to wait in the queue is 0.46, computed as follows:

3. The server is idle about 25% of the time, computed as follows:

Therefore, the server is busy about 75% of the time.

4. The average service time is 3.20 minutes, computed as follows:

This result can be compared with the expected service time by finding the mean of the service-time distribution, using the equation

Applying the expected-value equation to the distribution in Table 10 gives

The expected service time is exactly the same as the average service time from this trial of the simulation. In general, this will not be true; here it is a pure coincidence.

5. The average time between arrivals is 4.24 minutes, computed as follows:

Since the first arrival occurs at time 0, we divide by 99 rather than 100. This result can be compared to the expected time between arrivals by finding the mean of the discrete uniform distribution whose endpoints are a 1 and $b = 8 .$ The mean is given by

The expected time between arrivals is slightly higher than the average. However, as the simulation becomes longer, the average value of the time between arrivals tends to become closer to the theoretical mean,$E ( A )$6. The average waiting time of those who wait is 3.54 minutes, computed as follows:

Note that this is different from the average waiting time of all customers, many of whom (54 in this simulation) have no wait at all before their service begins. Over all customers, the average waiting time is $\frac {163} {100} ~ = ~ 1 . 63$ minutes.The number who wait, 46, comes from the simulation table, column G under “Waiting Time in Queue,” by counting the number of nonzero waiting times, or alternately from Figure 9, which displays a histogram of the 100 waiting times.

7. The average time a customer spends in the system is 4.83 minutes, computed in two ways. First:

The second way is to realize that the following relationship must hold:

Frequency of Individual Customer Waiting Time in Queue Figure 9 Frequency of waiting time in queue.

From findings 1 and 4, this results in

Average time customer spends in the system 1.633.204.83 minutes

We are now interested in running an experiment to address the question of how the average time in queue for the first 100 customers varies from day to day. Running the ‘One Trial’ workshee once with 100 customers corresponds to one day. Running it 50 times corresponds to using the ‘Experiment’ worksheet with “Number of Trials” set to 50, where each trial represents one day.

For Example 5, the frequency of waiting time in queue for the first trial of 100 customers is shown in Figure 9. (Note: In all histograms in the remainder of this chapter, the upper limit of the bin is indicated on the legend on the x-axis, even if the legend is shown centered within the bin.) As shown in the histogram, 54% of the customers did not have to wait, and of those who did wait, 34% waited less than four minutes (but more than zero minutes). These results and the histogram in Figure 9 represent the results of one trial, and by themselves do not constitute an answer to our question.

To answer our question, we use the ‘Experiment’sheet, setting “Number ofTrials” to 50 and click the button labeled ‘Reset Seed & Run’. This results in 50 estimates of average time in queue (each averaged over 100 customers). The overall average waiting time over 50 trials was 1.32 minutes. Figure 10 shows a histogram of the 50 average waiting times for the 50 trials. This shows how average waiting time varies day-by-day over a sample of 50 days.

By experimenting with the spreadsheet solution and doing some of the related exercises, you can discover the effects of randomness and of the assumed input data. For example, what if you run 400 trials, or 10 trials, instead of 50? How much does the shape of the distribution in Figure 10 change the number of trials? Why is the range (0 to 12 minutes) in Figure 9 so much wider than the range (0.5 to 3 minutes) in Figure 10?

Figure 10 Frequency distribution of average waiting times for 50 trials.

3.3 Simulating a Queue with Two Servers

The second queueing example is a queue with two servers that have different service times.

Example 6: The Able–Baker Call Center Problem

A computer technical support center is staffed by two people, Able and Baker, who take calls and try to answer questions and solve computer problems. The time between calls ranges from 1 to 4 minutes, with distribution as shown in Table 12. Able is more experienced and can provide service faster than Baker. The distributions of their service times are shown in Tables 13 and 14.

When both are idle, Able takes the call. If both are busy, the call goes on hold; this is basically the same as a customer having to wait in line in any queueing model. In general, arrival times, service times, and hence clock times in a simulation should be continuous (real-valued) variables; the fac that they are discrete, integer-valued here (and in other examples) is simply for ease of explanation as well as understanding the random variable generation techniques explained earlier.

Table 12 Interarrival Distribution of Calls for Technical Support

Table 13 Distribution of Able’s Service Time

Table 14 Distribution of Baker’s Service Time

The simulation proceeds in a manner similar to the single-server case in Example 5, excep that the underlying logic (the spreadsheet formulas in the simulation table) is more complex for two reasons: There are two servers, and the two servers have different service times. The complete solution is in the workbook “Example2.6AbleBaker.xls”, a portion of which is shown in Table 15, along with some totals needed to estimate caller delay (hold time). The workbook provides a detailed explanation of the simulation steps, including the underlying logic (formulas) for computing each step. (To understand the steps, it would first be helpful for you to do a manual simulation, perhaps by starting with a simulation table containing Step 1 (row 20) and the columns for interarrival and service times, and attempting to match the results in Table 15.)

Our objective is to estimate caller delay (hold time) waiting for Able or Baker to answer. To estimate this and other desired measures of system performance, a simulation of the first 100 callers is made.

Looking at Table 15, we see that Caller 1, by assumption, arrives at clock time 0. Able is idle, so Caller 1 begins service immediately. The service time, 4 minutes, is generated from the distribution given in Table 13 by following the procedure (throwing the “random dart”) in Example 2. Thus, Caller 1 completes service at clock time 4 minutes and is not delayed.

Ta b l e 15 S i m u l at i o n Ta b l e fo r Ca l l -Ce nte r Exa m _p l e (fi rst 10 of 1 00 ca l l e rs)

Figure 11 Frequency of caller delay for first trial.

An interarrival time of 1 minute, generated from Table 12 by following the procedure in Example 3, makes Caller 2 arrive at clock time 1 minute. Able is busy, so Caller 2 is served by Baker.

Looking at Caller 3, serviced by Able from clock time 4 minutes to clock time 7 minutes, we see that Caller 3 arrived at time 2 minutes to find both servers busy, hence had to wait.

For the single trial of 100 callers, the frequency chart in Figure 11 shows that 78 of 100 (78%) of the callers had no delay, 16% had a delay of one minute, while a few had to wait up to 3 minutes. Other trials, using different random numbers, might get similar or vastly different results; only experimentation can determine the inherent variability when simulating 100 customers.

The distribution of caller delay in Figure 11 is skewed to the right. On the ‘One Trial’ sheet, click the button ‘Generate New Trial’ repeatedly and note that the caller delay distribution often has a long, thin tail to the right. Along with the tall bars (high frequency) close to zero, what does this say about the nature of caller delay? One trial does not provide sufficient data on which to form reliable conclusions, but this is one of the great advantages to having the spreadsheet—the effec of variability is quite evident—and the simulation can be repeated any number of times using the ‘Experiment’ worksheet.

In Table 15, total customer delay is 73 minutes, or about 0.73 minutes per caller on the average. The histogram in Figure 11 shows, however, that the average of 0.73 minutes by itself is not a good indicator of how long a caller has to wait for Able or Baker. While 78% of the customers in this tria experienced no delay, a few experienced delays up to 3 minutes. This illustrates the importance of choosing the proper measures of system performance, depending on the model’s goals and objectives. After all, the callers who do not have to wait will not complain about waiting, but those who wai a long time will not care that the average was 0.73 minutes. (In actuality, in some later trials, the average delay is considerably higher, and the distribution is skewed even more to the right. You should click ‘Generate New Trial’ several times to see how much random variability this system may exhibit. Each trial represents a different day.)

Figure 12 Frequency of average caller delay for experiment of 400 trials.

Next, we ask the question: How does average caller delay (for the first 100 customers) vary from day to day? Using the ‘Experiment’ worksheet, and associating each day as one trial, we set the “Number of Trials” to 400 (representing 400 days). The resulting distribution of average caller delay is shown in the histogram in Figure 12. Note that this histogram is not a histogram of individua caller delay, as in Figure 11.

From Figure 12, we see that about 22% of the average delays (87 of 400) are longer than one minute, and about 78% (313 of 400) are 1 minute or less. Only about 1.25% (5 of 400) are longer than 2 minutes. We see that the result of the first trial (an average caller delay of 0.73 minutes) falls in the most frequent bin, but there are days that have much higher average delays. This example shows that a one-day (one trial) simulation may well be unrepresentative of long-term system performance.

In summary, whether, and to what extent, Able and Baker can handle the demand for service depends on your criteria, and the cost or value of the delays customers experience. We can guess that adding an additional server may well reduce caller delay (hold time) to nearly zero; however, the benefit of reduced customer delay would have to be traded off against the cost of an additiona server.

4 Inventory Simulation in a Spreadsheet

An important class of simulation problems involves inventory systems. The simple inventory system shown in Figure 13 is called an (M, N) system, which has an inventory review every N time periods and maximum inventory level M. At each N time units, the inventory level is checked and an order is made to bring the inventory up to the level M.

Figure 13 Probabilistic order-level inventory system.

For simplicity, the lead time (i.e., the length of time between the placement and receipt of an order) is shown as zero in Figure 13; orders arrive immediately after being placed. In reality, lead time may vary greatly and would need to be modeled as a known constant or as a random variable.

Demands are not usually known with certainty, so the order quantities are modeled by a probability distribution. In the graph of Figure 13, demand is shown as being uniform over the time period. In actuality, demands are not usually uniform and do fluctuate over time.

At the end of the first review period, an order quantity,$Q_{1}$, is placed to bring the inventory leve up to M. This is repeated at every inventory review.

Notice that, in the second cycle, the amount in inventory drops below zero, indicating a shortage. In Figure 13, these units are backordered; when the order arrives, the demand for the backordered items is satisfied first. To avoid shortages, a buffer, or safety, stock would need to be carried. In some inventory systems, a portion of sales may be lost rather than backordered when inventory runs out.

Inventory systems have a number of potential sources of revenue and costs:

1. Revenue from sales;

2. Cost of items sold;

3. Carrying cost, the cost of carrying stock in inventory;

4. Ordering cost, the cost associated with placing orders;

5. Cost of lost sales or backorders;

6. Cost due to scrap;

7. Salvage revenue from scrap or other damaged goods.

The carrying cost can be attributed to the interest paid on funds borrowed to buy the items (or equivalently, the loss from not having the funds available for other investment purposes). Carrying costs also include the cost for handling and storage space, hiring of guards, and other similar costs. Ordering cost may include shipping and transportation, and discounts depending on order quantity.

When trying to improve an inventory system, you face a number of trade-offs. An alternative to carrying high inventory (with high carrying costs) is to make more frequent reviews and, consequently, more frequent purchases or replenishments. This has an associated cost, the ordering cost. There may also be costs associated with running out of goods, with such shortages causing customers to become angry and a subsequent loss of good will. Larger inventories decrease the probability of a shortage. By varying the policy or decision parameters, the costs may be traded off in order to minimize the total cost of an inventory system.

The total cost (or total profit) of an inventory system is the measure of performance. This can be affected by the policy alternatives. For example, in Figure 13, the decision maker can control the maximum inventory level, M, and the length of the cycle, N.

Inventory systems and policies have a number of parameters, some controllable and some not. The controllable variables are the decision or policy variables. For each item in inventory, these include:

1. The maximum inventory level, M

2. The review period, N

3. The order quantity (for replenishment), Q

4. Lead time for replenishment, L

Lead time may be random when it cannot be controlled; in other situations, lead time may be tightly controlled, in effect a known constant (as in a just-in-time manufacturing system when ordering parts or components), in which case it becomes a policy variable.

In a model of an (M, N) inventory system, the events that may occur are the demand for items in the inventory, the review of the inventory position and resulting decision to place a replenishment order, and the arrival ofreplenishment stock. When the lead time is assumed to be zero, as in Figure 13, the last two events occur at the same time.

In the examples and exercises, we simulate a variety of inventory systems and policies.

4.1 Simulating the News Dealer’s Problem

In the following example, a news dealer must decide how many newspapers to buy. In this and similar problems, only a single time period of specified length is relevant, and only a single procurement is made. Inventory remaining at the end of the single time period is sold for scrap, discarded or recycled. A wide variety of real-world problems have similar characteristics, including the stocking of certain spare parts, perishable items, style goods, and special seasonal items [Hadley and Whitin, 1963].

Example 7: The News Dealer’s Problem

A news dealer buys papers for 33 cents each and sells them for 50 cents each. Newspapers not sold at the end of the day are sold as scrap for 5 cents each. Newspapers can be purchased in bundles of 10. Thus, the newsstand can buy 50 or 60 or 70 papers, and so on. The order quantity, Q, is the only policy decision. Unlike some inventory problems, the order quantity Q is fixed since ending inventory is always zero due to scrapping leftover papers.

Table 16 Distribution of Daily Newspaper Demand, by Type of Newsday

There are three types of newsdays: “good”, “fair”, and “poor”, but the news dealer cannot predict which type will occur on any given day. Table 16 gives the distribution of newspapers demanded by type of day. Table 17 provides the distribution for type of newsday.

Our objective is to compute the optimal number of papers the newsstand should purchase (the order quantity, Q). This will be accomplished by simulating demands for 20 days (in the ‘One Trial’ worksheet) and recording profits from sales each day for a given order quantity. After a tria is completed, total profit (the model response or performance measure) is calculated. To complete the experiment, we use the ‘Experiment’ sheet to replicate some number of times for a given order quantity (for example, 70 papers). Finally, we vary the order quantity over some reasonable range (40, 50, 60, 70, and so on) and compare different order policies based on total profit over the 20-day period.

Daily profit is given by the following relationship:

Since the revenue from sales is 50 cents per paper, and the cost to the dealer is 33 cents per paper, the lost profit from excess demand is 17 cents for each paper demanded that could not be provided.

Table 17 Distribution of Type of Newsday

Table 18 Simulation Table for Purchase of 70 Newspapers

Such a shortage cost is somewhat controversial, but makes the problem much more interesting. The salvage value of scrap papers is 5 cents each.

The simulation table for the decision to purchase 70 newspapers, taken from the solution workbook, “Example2.7NewsDealer.xls”, is shown in Table 18. On day 1, the demand is for 50 newspapers, so with 70 available, there are 20 to scrap. The revenue from the sale of the 50 newspapers is $25.00, and the scrap value is $1.00, so the first-day profit is computed as follows:

The profit from other days is easily computed in the same manner. The profit for the 20-day period is the sum of the daily profits, $114.70, as shown in Table 18. In general, because the results of one day are independent of previous days, inventory problems of this type are much easier than queueing problems to solve in a spreadsheet.

With the ‘Experiment’ worksheet from “Example2.7NewsDealer.xls”, we set up an experimen with 400 trials or replications for the order policy of ordering 70 newspapers. Figure 14 shows the result of these 400 trials, each trial being a 20-day simulation run. The average total (20-day) profit was $135.49 (averaged over the 400 trials). The minimum 20-day profit was $86.60 and the maximum was $198.00. Figure 14 shows that only 38 of the 400 trials resulted in a total 20-day profit of more than $160. (Recall that the number beneath a bin is the upper limit of the bin.)

Figure 14 Frequency of total (20-day) profit when news dealer orders 70 papers per day.

The single trial shown in Table 18 had a profit of $114.70, which is on the low side of the distribution in Figure 14. This illustrates once again that the result for one 20-day trial may not be representative of long-term performance, and shows the necessity of simulating a number of trials as well as conducting a careful statistical analysis before drawing conclusions.

On the ‘One Trial’ sheet, look how Daily Profit varies when clicking the button ‘Generate New Trial’ multiple times. The results vary quite a bit both in the histogram entitled ‘Frequency of Daily Profit’ (showing what happened on each of the 20 days) and in the total profit over those 20 days. Figure 15 shows four typical histograms for daily profit from the first four trials, whose shape varies quite a bit more than the shape for the histogram for total 20-day profit.

Exercise 28 asks you to conduct an experiment to determine the optimum number of newspapers for the news dealer to order. To solve this problem by simulation requires setting a policy of buying a certain number of papers each day and running the experiment for a large number of trials. The policy (number of newspapers purchased) is changed to other values in a reasonable range (say, 40, 50, 60, and so on) and the simulation repeated until the best value is found. To estimate with confidence whether a simulated difference is likely to be real and not a random fluke, requires additional statistical methods

Figure 15 Four typical histograms of daily profit for the News Dealer’s Problem.

4.2 Simulating an (M, N) Inventory Policy

The next example is the classic order-up-to-level (M, N) inventory policy with a fixed review period (N), a maximum inventory level (M), random demand, and random lead time.

Example 8: A Refrigerator Inventory Problem

A company selling refrigerators maintains inventory by conducting a review after a fixed number of days (say N) and making a decision about how many to order to replenish the store’s inventory. The current policy is to order up to a level (the order up to level—say, M), using the following relationship:

For example, if the order-up-to level (M) is 11 refrigerators, the review period (N) is five days, and the ending inventory on day 5 is 3 refrigerators, then on the fifth day of the cycle, 8 refrigerators will be ordered from the supplier. On the other hand, if there had been a shortage of two refrigerators on the fifth day, then 13 refrigerators would have been ordered; the first two received would be provided to the customers who placed an order and were willing to wait (a so-called backorder). (In contrast, the lost sales case occurs when customer demand is lost if inventory is not available.)

The daily demand, or number of refrigerators purchased each day by customers, is randomly distributed as shown in Table 19. After the company places an order to replenish their supply, the lead time is 1 to 3 days, randomly distributed, as shown in Table 20. Assume that the orders are placed at the end of the day. With a lead time of zero, the order from the supplier will arrive the next morning, and the refrigerators will be available for distribution that next day. With a lead time of one day (the smallest possibility in Table 20), the order from the supplier arrives the second morning after, and will be available for distribution that day.

Table 19 Distribution of Daily Demand

Table 20 Distribution of Lead Time

The simulation table for the policy to order-up-to 11 refrigerators, shown in Table 21, is taken from the spreadsheet solution in “Example2.8RefrigInventory.xls”. The simulation was started with assumed initial conditions as follows: a beginning inventory of 3 refrigerators and a previous replenishment order for 8 refrigerators to arrive in 2 days’ time. (These values can be changed in the spreadsheet solution, if desired.)

Following the simulation table for several selected days indicates the simulation logic. The order for 8 refrigerators is available on the morning of the third day of the first cycle, raising the inventory level from zero refrigerators to 8 refrigerators. Demands during the remainder of the firs cycle reduced the ending inventory level to 3 refrigerators at the end of the fifth day. Thus, an order for 8 refrigerators was placed; the lead time turns out to be 2 days. This order is added to inventory on the morning of day 7 in cycle 2.

Note that on day 10, there is a shortage, resulting in a backorder and an order for 13 refrigerators. Since the lead time is 2 days, additional shortages occur before the order arrives, so that when the order of 13 refrigerators does arrive, the backorders plus current demand take inventory down to 6.

From the simulation of 25 days, representing 5 inventory review periods, the average ending inventory is approximately 2.76 (69/25) units. On 5 of 25 days, a shortage condition existed.

Ta ble 21 S i m u l at i o n Ta b l e fo r I nve nto r_y Po l i c_y with O rd e r- U _p-To 11 Refri _g e rato rs

Frequency Distribution for Average Daily Ending Inventory of Refrigerators Figure 16 Histogram of 25-day average ending inventory.

In Example 8, there cannot be more than one order outstanding from the supplier at any one time, but there are situations where lead times are so long that the relationship shown so far needs to be modified as follows:

The inclusion of the on-order quantity guarantees that double ordering does not occur.

On the ‘One Trial’ worksheet, repeatedly clicking on ‘Generate New Trial’ will run the nex trial or replication with different random numbers, showing that, for a 25-day simulation, results are highly variable for daily ending inventory. (Watch the histogram change as you run new trials.) In contrast, setting the number of trials to 100 in the ‘Experiment’worksheet and running the experimen repeatedly, by clicking the ‘Run Experiment’ button, produces much less variability in the average daily ending inventory (the average being taken over one trial of 25 days). The 25-day average is usually in the range from 1 to 5 refrigerators, as shown in the resulting histogram in Figure 16. This difference in variability illustrates a well-known fact: averages vary less than individual observations. Which to use in any specific analysis depends on the objectives and questions being asked.

The spreadsheet solution in “Example2.8RefrigInventory.xls” allows you to change the ordering policy (i.e., the values of M and N). It also allows you to make some changes to the statistica distributions for daily demand and lead time, as long as certain restrictions are met: the lead time must be one or more days, the review period must be larger than the largest lead time, and possibly other limitations; otherwise, the formulas implementing the logic may be incorrect.

5 Other Examples of Simulation

This section includes four miscellaneous examples: a reliability problem, a bombing mission, the estimation of the distribution of lead-time demand, and a project activity network.

5.1 Simulation of a Reliability Problem

The next example compares two replacement policies for replacing bearings in a milling machine. The example is a Monte Carlo simulation, not a dynamic event-based model, since events and clock times are not included. Each bearing life is randomly generated 15 times and the resulting costs computed.

Example 9: Replacing Bearings in a Milling Machine

A milling machine has three different bearings that fail in service. The distribution of the life of each bearing is identical, as shown in Table 22. When a bearing fails, the mill stops, a mechanic is called, and he or she installs a new bearing (costing $32 per bearing). The delay time for the mechanic to arrive varies randomly, having the distribution given in Table 23. Downtime for the mill is estimated to cost $10 per minute. The direct on-site cost of the mechanic is $30 per hour. The mechanic takes 20 minutes to change one bearing, 30 minutes to change two bearings, and 40 minutes to change three bearings. The engineering staff has proposed a new policy to replace al three bearings whenever one bearing fails. Management needs an evaluation of the proposal, using total cost per 10,000 bearing-hours as the measure of performance.

Table 22 Distribution for Bearing Life

Table 23 Distribution of Delay until Mechanic Arrives

Table 24 Bearing Replacement under Current Method

The simulation table for the current policy, shown in Table 24 and taken from the spreadsheet “Example2.9CurrentBearings.xls”, represents a simulation of 15 bearing changes under the current policy of replacing only the single bearing that fails. Note that there are instances where more than one bearing fails at the same time. This is unlikely to occur in practice and is due to the crude simplifying assumption that bearing life is a multiple of 100 hours (so that we could have a simple discrete distribution rather than a more realistic one). Here, we assume that the times are never exactly the same and thus no more than one bearing is changed at any breakdown.

From this single trial (or replication) of the simulation, the cost of the current system is estimated as follows:

The total life of all 45 bearings is $( 19 , 600 + 20 , 200 + 19 , 900 ) = 59 , 700$ hours. Therefore, the tota cost per 10,000 bearing-hours is ($14,340/5.97) $2,402.

The simulation table for the proposed method, shown in Table 25, is taken from the spreadshee “Example2.9ProposedBearings.xls”. For the first set of bearings, the earliest failure is at 1,100 hours.

Table 25 Bearing Replacement under Proposed Method

All three bearings are replaced at that time, even though the remaining bearings had more life in them. For example, Bearing 1 would have lasted 200 additional hours

From this single trial (or replication) of the model, the cost of the proposed policy is estimated as follows:

The total life of the bearings is $( 16 , 600 \times 3 ) = 49 , 800$ hours. Therefore, the total cost per 10,000 bearing-hours is ($9,190/4.98) $1,845. The new policy generates a savings of $557 per 10,000 hours of bearing-life.

The spreadsheet solutions for Example 9 are in: “Example2.9CurrentBearings.xls” for the current policy and “Example2.9ProposedBearings.xls” for the proposed policy. In each spreadsheet, a user can change a number of inputs: the distribution of bearing life, the distribution of delay time unti mechanic arrival, the cost parameters, and the repair time per bearing or set of bearings.

5.2 Simulation of Hitting a Target

The next example simulates a bombing mission where the actual location a bomb hits varies from its target by a random amount defined by a normal distribution. The spreadsheet solution has a method for generating these normal random variables; the manual solution uses standard normal numbers from Table A.2 in the Appendix.

For our purposes, recall that a normal distribution (the bell-shaped curve) is symmetric around its mean with a likely range determined by its standard deviation; its use in the next example is a classic use of the normal distribution to represent an error, in this case the deviation from a target. This example is a pure Monte Carlo sampling experiment, since it contains neither events nor clock times; therefore, it is not a dynamic, discrete-event model.

Example 10: A Bombing Mission

Consider a bomber attempting to destroy an ammunition depot, as shown in Figure 17. (This bomber has conventional rather than laser-guided weapons.) If a bomb falls anywhere inside the target, a hi is scored; otherwise, the bomb is a miss. (Note that when a bomb appears visually to have touched a boundary line, it may or may not have hit the target; the model determines mathematically whether a hit has occurred, using the (X, Y) coordinates and the equations of the piecewise-linear boundary of the depot.)

Figure 17 Ammunition depot with 10 bomb locations.

The bomber flies in the horizontal direction and carries 10 bombs. The aiming point is (0,0). The actual point of impact is assumed to be normally distributed around the aiming point with a standard deviation of 400 meters in the direction of flight and 200 meters in the perpendicular direction. The problem is to simulate the operation and estimate the number of bombs on target.

Recall that the standardized normal variate $Z ,$, having mean 0 and standard deviation 1, is distributed as

where $X$ is a normal random variable,$\mu$ is the mean of the distribution of X, and σ is the standard deviation of X. Then, with mean zero and standard deviations given by $\sigma_{X} = 400$ and $\sigma_{Y} = 200$, we have

where (X, Y) are the simulated coordinates where the bomb hits.

Table 26 Simulated Bombing Run

The i and j subscripts have been added to indicate that the values of Z should be different for x and y. What are these Z values and where can they be found? The values of Z are random norma numbers with mean zero and standard deviation of one. These can be generated from uniformly distributed random numbers. For our purposes, we can use Table A.2 in the Appendix for manua simulations and the Excel formula listed in Section 1.2 for spreadsheet models.

For example, the first two random normal numbers from Table A.2, are 0.23 and -0.17, which results in (x, y) coordinates for the first bomb of (92.0, 34.0), obtained by multiplying the norma random number by the respective standard deviations of 400 and 200, as shown in the preceding formula.

Table 26 shows the results of one simulated bombing run. For our spreadsheet solution in “Example2.10Target.xls”, we use the worksheet function, NORMSINV(Rnd01()), described in Section 1.2, to generate the normal variates with the desired standard deviation, as follows:

for the x coordinate (where cell E5 contains the standard deviation in the x direction). A similar formula works for the y coordinate.

Using the spreadsheet solution in “Example2.10Target.xls” with the assumed shape and standard deviations, we ran an experiment with 400 trials (each trial being 10 bombs). The histogram in Figure 18 gives the frequency of number of hits, that is, the number of bombing runs on which there were a given number of hits (with number of possible hits ranging from 0 to 10).

From the “Multi-Trial Summary” on the ‘Experiment’ sheet of the spreadsheet model, note tha the actual results range from 2 hits to 10 hits, and the average is 6.77 hits. (Clearly, no hits or one hi are possible. Since we made 400 replications, the experiment suggests, however, that one hit or no hits are extremely unlikely to occur on a bombing mission having the assumed characteristics.) If we simulate only one mission (that is, one trial), a very misleading result could occur, but Figure 18 provides useful descriptive information. For instance, in 17% (68 of 400) of the bombing runs there are 5 or fewer hits. In about 60% of the runs (239 of 400), there were 7 or more hits.

The spreadsheet model in “Example2.10Target.xls” allows you to change the target’s shape by editing the (X, Y) coordinates of each endpoint of each side of the target, so long as a convex shape is maintained. You can also change the standard deviations, with a smaller standard deviation increasing the likelihood of being closer to the target and a larger one increasing the chances of being further from the target. In the spreadsheet solution, whether or not a bomb with a simulated (X, Y) landing spot hits the target is determined by linear inequalities using elementary algebra; the details are explained in the spreadsheet.

Frequency Distribution for Number of Hits in 400 Bombing Missions Figure 18 Histogram for number of hits on a bombing mission.

5.3 Estimating the Distribution of Lead-Time Demand

The purpose of the next example is to determine the distribution of lead-time demand, that is, the total demand received over the lead time. Lead time is the time from placement of a replenishmen order until the order is received. During this period, demands continue to arrive from customers. The total customer demand over this period is the lead-time demand.

This model is an example of a Monte Carlo simulation; it is not a dynamic, event-based simulation. Essentially, there are no events and no clock times; it is a pure sampling experiment whose purpose is to estimate a complex statistical distribution. The distribution of lead-time demand is often of use in devising better inventory policies to reduce backorders and lost sales for the least cost.

We assume that both lead time and demand are random variables. Lead-time demand is thus a random variable defined as the sum of the demands over the lead time, or $\textstyle \sum_{i = 0} ^ {T} D_{i}$, where T is the lead time and $D_{i}$ is the demand during the ith time period. The distribution of lead-time demand is found by simulating many cycles of lead time and for each period in the lead time, generating the random demand and totalling it, and building a histogram based on the results.

Example 11: Lead-Time Demand

A firm sells bulk rolls of newsprint. The daily demand is given by the following probability distribution:

Table 27 Simulation Table for Lead-Time Demand

The lead time (the number of days from placing an order until the firm receives the order from the supplier), is a random variable given by the following distribution:

Table 27 shows the simulation table, taken from “Example2.11LeadTimeDemand.xls”. One feature of this simulation, different from previous ones, is that the number of random demands generated in one cycle is itself random. If a lead time of 2 days is generated, then two random demands are generated and summed; if the lead time is 3 days, then three random demands must be generated and summed.

Using the spreadsheet solution, you can generate many cycles, sum the demands over each cycle to get the lead-time demand, and with the histogram, see the resulting distribution of lead-time demand, as illustrated in Figure 19. This result was obtained by using the ‘One Trial’ worksheet to simulate 20 cycles of lead-time demand by clicking ‘Reset Seed & Run’ in the spreadsheet solution “Example2.11LeadTimeDemand.xls”. By clicking the ‘Generate New Trial’ button several times, you can see how variable the lead-time demand can be over just 20 cycles.

Frequency Distribution for Lead Time Demand over 20 Cycles Figure 19 Frequency of lead-time demand.

Compare these results over 20 cycles to the results in the spreadsheet model on the ‘Experiment sheet, which shows the results for 200 trials, each trial being one lead-time demand. This comparison shows that, due to the small sample, the histogram in Figure 19 may not be representative of the shape of the distribution of lead-time demand. This illustrates the importance of having a sample size (number of trials) large enough to obtain accurate estimates of the desired response variable.

5.4 Simulating an Activity Network

Suppose you have a project that requires the completion of a number of activities. Each activity takes a certain amount of time, either constant or random. Some activities must be carried out sequentially, that is, in a specified order; other activities can be done in parallel. The project can be represented by a network of activities, as illustrated by Figure 20. The arcs represent activities and the nodes represent the start or end of an activity.

In the network in Figure 20, there are three paths, each going from the node labeled “Start” to the node labeled “Finish”. Each path represents a sequence of activities that must be completed in order. The activities on different paths can be carried out in parallel. The time for each activity is noted on the arc, where, for example, U(2, 4) represents a random variable that is uniformly distributed between 2 and 4 minutes. The time to complete all activities on a path is the sum of the activity times along the path. To complete the entire project, all activities must be completed; therefore, projec completion time is the maximum over all path completion times.

Unlike any of the previous examples, here we are using a continuous uniform distribution; that is, all values between the lower and upper limit are allowed, not just the integer values. The VBA function, Uniform(), supplied in the add-in file “BCNNvba.xla” and available to any spreadshee model, implements uniform generation in one line of VBA code, in a simple formula that transforms the VBA random number generator Rnd(), which is uniform on 0 to 1, to any other specified range, as follows:

' In the Uniform function, low is the lower limit,
'    high is the upper limit.
' Type ``Double'' is a real value (double precision).
Function Uniform(low As Double, high As Double) As Double
Uniform = low + (high - low) * Rnd()
End Function

We hope that this simple formula has some intuitive appeal. Basically, since Rnd() is uniform on the unit interval (0, 1), it follows that the function Uniform() will be uniformly distributed on the specified interval (low, high).

Pritsker [1995] was a pioneer in applying simulation techniques to project activity networks. While Example 12 is a Monte Carlo simulation, some activity network models, due to their greater complexity, may be implemented in a discrete-event simulation package or a specialized package designed for such models.

Example 12: Project Simulation

Suppose that three friends want to cook bacon, eggs, and toast for breakfast for some weekend visitors. They divide the work, with each friend preparing one item. Figure 20 represents the sequence of activities, with each path representing the tasks for one person, as follows:

Top path: Start → A Crack eggs
A → B Scramble eggs
B → Finish Cook eggs
Middle path: Start → C Make toast
C → Finish Butter toast
Bottom path: Start → Finish Fry bacon

The time to accomplish each activity, being somewhat uncertain, is represented by the uniform distribution shown on the associated arc in Figure 20. The friends want to estimate the distribution of total preparation time so that they can tell the visitor when to be at the breakfast table. With the distribution, and not just the mean or average total preparation time, they can estimate the probability of preparing breakfast within a specified amount of time. The model is in the spreadshee “Example2.12Project.xls”.

Figure 20 Activity network for Example 12.

Since the mean time for a continuous uniform is the midpoint between the lower and upper limit, you can see that each of the 3 paths in the project network of Figure 20 has a mean of 9 minutes. Based on the lower limit of each uniform, you can see that the minimum time for each path is 6 minutes; similarly, the maximum time is 12 minutes. Do these times provide any help in predicting the total project completion time?

For breakfast preparation, the project completion time is the maximum time over all of the paths. With the spreadsheet solution, “Example2.12Project.xls”, we can sample the task times for a large number of trials and get an idea of the range and distribution of possible project completion times. The ‘One Trial’ worksheet provides the solution for one trial or replication of the network simulation. The logic and formulas implementing it are much simpler than many of the previous examples and we leave those for the student.

With the ‘Experiment’worksheet, we can run many trials and estimate the likely range for project completion time, as well as other statistical measures. We set “Number of Trials” to 400 and run the experiment by clicking the ‘Reset Seed & Run’ button once. With 400 trials and using the default seed, the results are as follows:

Sample Mean: 10.21 minutes

Minimum: 6.65 minutes

Maximum: 11.99 minutes

The so-called critical path is the path that turns out to be the longest on a particular trial; that is, that path’s time is the project completion time. Over 400 trials with each using different random numbers, each path will have some probability of being the critical path. For each of the 400 trials, the experiment determines which path was critical, with these results:

Top path: 25.50% of the trials

Middle path: 32.25%

Bottom path: 42.25%

We conclude that the chance of the bacon being the last item ready is approximately 42.25%. Why aren’t the paths each represented about 1/3 of the time? In addition, how accurate is 42.25%? You can click the ‘Run Experiment’ button several times to get an idea of how variable this estimate tends to be; it varies by a few percent on each click. The magnitude of this random variation depends on the number of trials (400 in this example) in the experiment.

Frequency Distribution of Project Completion Time Figure 21 Histogram of project completion times based on 400 trials.

The project completion times were placed in a frequency chart or histogram, shown in Figure 21. From the chart, we draw the following inferences:

The chances are about 10.5% (42 of 400) that breakfast will be ready in 9 minutes or less.

The chances are about 24.25% (97 of 400) that it will take from 11 to 12 minutes.

Note that the bin labeled “12.0” is actually the interval from 11.0 to 12.0 minutes, since the bin labe is always the upper limit of the bin.

Recalling that the mean time along each of the 3 paths is 9 minutes, the histogram tells us that the chance of taking longer than 9 minutes is approximately 89.5%. In other words, the mean of each path tells us little about the distribution of project completion time, which, after all, is determined by the slowest sequence of tasks.

6 Summary

The purpose of this chapter was to introduce a few key simulation concepts by means of examples, to illustrate a few general areas of application.

We used the simulation table, custom designed for each problem, as the organizing principle. The columns in the simulation table represented activity times or other random input (such as demand), clock times for the occurrence of an event, system states, and model outputs. The rows represented a simulation step, for example, a customer or one day’s demand. The formulas in each cell implement the simulation logic, or compute model outputs. The examples illustrate the need for working out the characteristics of the input data, generating random variables from the input assumptions, defining and computing model responses (measures of performance), and analyzing the resulting responses.

Model inputs were defined by constant values for policy and decision parameters, or simple statistical distributions for such variables as service times, interarrival times, lead time, and demand. Separately from the simulation table, but using the model outputs and other data, model responses, also known as system performance measures, were computed based on the results of one trial or one run of the simulation. These model responses included totals, averages, and frequency distributions (used for the histograms).

In the examples, we covered how to generate random samples from four distribution types: the discrete empirical, the discrete uniform, the continuous uniform, and the normal distributions (Empirical means that the distribution is based on data and specified probabilities.) The spreadshee examples, available on the text’s web site at www.bcnn.net, provide VBA functions to generate each type of distribution. You should use these as a starting point for any of the exercises at the end of the chapter.

Events in a simulation table were generated by using the random variables and the logic (formulas) of the particular model. The queueing examples, especially the two-channel queue, illustrate some of the complex dependencies that can occur—in the examples discussed, between subsequent customers visiting the queue. Because of these complexities, the ad-hoc simulation table approach fails or becomes unbearably complex, even with relatively simple networks of queues and other moderately complex models. For this and other reasons, a more systematic methodology, such as the event-scheduling approach, is needed.

We introduced the idea, and necessity, of running an experiment consisting of multiple trials or replications. We saw the resulting statistical variability, and the need to conduct some kind of further analysis.

REFERENCES

HADLEY G., AND T.M. WHITIN [1963], Analysis ofInventory Systems, Prentice-Hall, Englewood Cliffs, NJ. HARRISON, J.M.,ANDV. NGUYEN [1995], “Some Badly Behaved Closed Queueing Networks,” Proceedings ofIMA Workshop on Stochastic Networks, eds. F. Kelly and R.J. Williams.

PRITSKER, A. A. B. [1995], Introduction to Simulation and SLAM II, 4th ed., John Wiley, New York SEILA,A.,V. CERIC,AND P. TADIKAMALLA [2003],Applied Simulation Modeling, Duxbury, Belmont, CA.

Simulation Examples in a Spreadsheet

EXERCISES

Spreadsheet and Manual Exercises

For hints on implementation in Excel, study the spreadsheet solutions at www.bcnn.net and read the ‘Explain’ worksheet for any example of interest. You may also need one or more of the VBA functions in the spreadsheet solutions. Therefore, to have these VBA functions available, it is easiest to start with an existing spreadsheet model, say, one of the examples closest to the exercise, and to have the Excel add-in file, “BCNNvba.xla”, in the same folder as your spreadsheet. The add-in file can be found on the text’s web site. As long as a VBA function is in a VB module in Excel’s VBA environment (in the spreadsheet itself, or an opened or referenced add-in), you can call it in a formula from a spreadsheet cell.

For any exercise where you are constructing a spreadsheet model, start with one of the examples, delete, modify or add to the existing inputs and simulation table in the ‘One Trial’ worksheet, and use what remains. On the ‘Experiment’ worksheet, change the response in the cell just below the word “Link”, and change any of the text in the titles and column headers as desired. The VBA implementations of all the functions described in Section 1.5 are in the add-in file “BCNNvba.xla”. Each function is available to every example spreadsheet, whether or not the example currently uses the function.

1. Consider the following continuously operating job shop. Interarrival times ofjobs are distributed as follows:

Processing times for jobs are normally distributed, with mean 50 minutes and standard deviation 8 minutes. Construct a simulation table and perform a simulation for 10 new customers. Assume that, when the simulation begins, there is one job being processed (scheduled to be completed in 25 minutes) and there is one job with a 50-minute processing time in the queue.

(a) What was the average time in the queue for the 10 new jobs?

(b) What was the average processing time of the 10 new jobs?

(c) What was the maximum time in the system for the 10 new jobs?

2. A baker is trying to figure out how many dozens of bagels to bake each day. The probability distribution of the number of bagel customers is as follows:

Customers order 1, 2, 3, or 4 dozen bagels according to the following probability distribution

Bagels sell for $8.40 per dozen. They cost $5.80 per dozen to make. All bagels not sold at the end of the day are sold at half-price to a local grocery store. Based on 5 days of simulation, how many dozen (to the nearest 5 dozen) bagels should be baked each day?

3. Develop and interpret flow diagrams analogous to Figures 4 and 5 for a queueing system with i channels.

4. Smalltown Taxi operates one vehicle during the 9:00 A.M. to 5:00 P.M. period. Currently, consideration is being given to the addition of a second vehicle to the fleet. The demand for taxis follows the distribution shown:

The distribution of time to complete a service is as follows:

Simulate 5 individual days of operation of the current system and of the system with an additional taxicab. Compare the two systems with respect to the waiting times of the customers and any other measures that might shed light on the situation.

5. The random variables X, Y, and Z are distributed as follows:

Simulate 50 values of the random variable

Prepare a histogram of the resulting values, using class intervals of width equal to 3.

6. Given A, B, and C, which are uncorrelated random variables. Variable A is normally distributed with $\mu = 100$ and $\sigma^{2} = 400$. Variable B is discrete uniformly distributed with a probability distribution given by $p ( b ) = 1 / 5$ with b 0, 1, 2, 3 and 4. Variable C is distributed in accordance with the following table:

Use simulation to estimate the mean of a new variable D, that is defined as

Use a sample of size 100.

7. Estimate, by simulation, the average number of lost sales per week for an inventory system tha functions as follows:

(a) Whenever the inventory level falls to or below 10 units, an order is placed. Only one order can be outstanding at a time.

(b) The size of each order is equal to 20 I, where I is the inventory level when the order is placed.

(c) If a demand occurs during a period when the inventory level is zero, the sale is lost.

(d) Daily demand is normally distributed, with a mean of 5 units and a standard deviation of 1.5 units. (Round off demands to the closest integer during the simulation and, if a negative value results, give it a demand of zero.)

(e) Lead time is distributed uniformly between zero and 5 days—integers only.

(f) The simulation will start with 18 units in inventory.

(g) For simplicity, assume that orders are placed at the close ofthe business day and received after the lead time has occurred. Thus, if lead time is one day, the order is available for distribution on the morning of the second day of business following the placement of the order.

(h) Let the simulation run for 5 weeks.

8. An elevator in a manufacturing plant carries exactly 400 kilograms of material. There are three kinds of material packaged in boxes that arrive for a ride on the elevator. These materials and their distributions of time between arrivals are as follows:

It takes the elevator 1 minute to go up to the second floor, 2 minutes to unload, and 1 minute to return to the first floor. The elevator does not leave the first floor unless it has a full load. Simulate 1 hour of operation of the system. What is the average transit time for a box of material A (time from its arrival until it is unloaded)? What is the average waiting time for a box of material B? How many boxes of material C made the trip in 1 hour?

9. The random variables X and Y are real-valued (not integers) and uniformly distributed over intervals as follows:

(a) Simulate 200 values of the random variable

Prepare a histogram of the resulting values. What is the range of Z and what is its average value?

(b) Same as (a), except that

10. Consider the assembly of two steel plates, each plate having a hole drilled in its center. The plates are to be joined by a pin. The plates are aligned for assembly relative to the bottom left corner (0,0). The hole placement is centered at (3,2) on each plate. The standard deviation in each direction is 0.0045. The hole diameter is normally distributed, with a mean of 0.3 and a standard deviation of 0.005. The pin diameter is also distributed normally, with a mean of 0.29 and a standard deviation of 0.004. What fraction of pins will go through the assembled plates? Base your answer on a simulation of 50 observations.

h hole diameter, i plate 1, 2

p pin diameter

x distance to center of plate hole, horizontal direction, i plate 1, 2

y distance to center of plate hole, vertical direction, i plate 1, 2

11. In the exercise above, the pin will wobble if it is too loose. Wobbling occurs if Min(h , h ) p 0.006. What fraction of the assemblies wobble? (Conditional probability—i.e., given that the pins go through.)

12. Three points are chosen at random on the circumference of a circle. Estimate the probability tha they all lie on the same semicircle, by Monte Carlo sampling methods. Perform 5 replications.

13. Two theorems from statistics are as follows:

Theorem 1 Let $Z_{1} , Z_{2} , \ldots , Z_{k}$ be normally and independently distributed random variables with mean $\mu = 0$ and variance $\sigma^{2} = 1$. Then the random variable

is said to follow the chi-squared distribution with k degrees of freedom, abbreviated $\chi_{k} ^ {2}$ Theorem 2 Let $Z \sim N ( 0 , 1 )$ and V be a chi-squared random variable with k degrees of freedom. If Z and V are independent, then the random variable

is said to follow the t distribution with k degrees of freedom, abbreviated $t_{k}$ Generate one sample of a t-distributed random variate with 3 degrees of freedom. Use as many of the following random values as needed, in the order shown:

How many random numbers and standard random normals are needed to generate one sample from a t-distribution?

14. A bank has one drive-in teller and room for one additional customer to wait. Customers arriving when the queue is full park and go inside the bank to transact business. The times between arrivals and the service-time distributions follow:

Simulate the operation of the drive-in teller for 10 new customers. The first of the 10 new customers arrives at a time determined at random. Start the simulation with one customer being served, leaving at time 3, and one in the queue. How many customers went into the bank to transact business?

15. The number of acres covered by Cedar Bog Lake is being estimated. The lake is shown next, with the scale shown in feet:

Use simulation to estimate the size of the lake. (One acre 43,560 square feet.)

16. In Example 6, assume that the average delay with another server, Charlie, is virtually zero. But another server costs $20/hour. If the average caller delay costs $200 per hour, at what point is it advisable to add another server?

17. In Example 12, why isn’t each path represented about 1/3 of the time?

18. In Example 11, the only way to have a lead-time demand of 3 or 4 is to have lead time of one day and a demand of 3 or 4. The probability of that happening is 0.36(0.200.35) 0.198. Using this logic, what is the probability of having lead-time demand equal 11 or 12? What is the probability of having it equal 18? (Use computation, not simulation.)

19. Run the experiment in Example 4 (the Coin Tossing Game) for 4000 trials. Explain why the probability for Harry being ahead on 5 or fewer of the 100 tosses should be larger than the probability that Harry is ahead for 95 or more of the tosses. And why you can say the same thing about Tom—with no contradiction.

Exercises based on the Spreadsheet Examples

20. Modify Example 2 in Section 1.5 to use the “WRONG !!” formula to generate the service times. Generate a large number of service times, say, 400, and develop a histogram of the resulting frequencies. How close are the sample frequencies to the specified probabilities for each value of service time? Explain why the results differ. That is, explain why the formula is wrong.

21. In Example 5, let the arrival distribution be uniformly distributed between 1 and 10 minutes (integers only). Run the experiment for 50 trials. Is there any difference between the bin frequencies shown and those of Figure 10?

22. In Example 5, let the service-time distribution be changed to the following:

Run the experiment for 50 trials. Is there any difference between the average waiting time here and that in Example 5 before the change was made? If there is a difference, to what do you attribute it?

23. Run the experiment in Example 5 for 25, 50, 100, 200, and 400 trials. (All trials are with different sets of random numbers.) What are the differences in the minimum and maximum values of the average waiting times? If there are differences, how do you explain them?

24. In Example 6, run 10 experiments, each with 100 trials. What was the fraction of trials in each experiment such that the callers had an average delay of three minutes or less? For the 1000 trials just simulated, what fraction of the callers had an average delay of two minutes or less?

25. In Example 6, conduct an experiment of400 trials. Explain the large spread between the minimum average delay and the maximum average delay.

26. In Example $^ {6 ,}$ run 10 experiments with 50 trials each and 10 experiments with 400 trials each. Explain the differences in output that you observe, if any, between the two experiments.

27. In Example 6, modify the spreadsheet so that the number of calls taken by Able and Baker can be displayed. What fraction did each take in an experiment of 400 trials?

28. In Example 7, determine the best policy for ordering newspapers based on experiments of 50 trials.

29. Run 10 experiments, each with 400 trials, in Example 7. What is the largest difference that you got between the maximum and minimum daily profit?

30. Use the spreadsheet for Example 8. For 100 trials, what is the average ending inventory ifM 11 and N 4, 5, 6?

31. Use the spreadsheet for Example 8. For 100 trials, what is the average ending inventory if N 5 and M 10, 11, 12?

32. Starting with the solution to Example 8, modify the solution to model the case where sales are lost; that is, instead of a shortage, those sales are lost. Keep track of the lost sales.

33. At what bearing cost in Example 9 is the total cost per 10,000 hours virtually the same for the current and proposed systems? Base your estimate on 10 experiments of the current system and of the proposed system, each experiment consisting of 400 trials.

34. Change the bin width for the histogram on the Experiment sheet for Example 9 (current or proposed) to a width of $50 beginning below the minimum value (for example, if the minimum value is $1528.46, let the first cell begin at $1500). What is the advantage of doing this?

35. Using the spreadsheet for Example 9 (proposed), run 10 experiments of 40 trials each, and record the range (maximum value minimum value) of the results. Next, compute the average range. Then do the same as before, but use 400 trials in each experiment. If there is a difference, how do you explain it?

36. Set $\sigma_{x} = 600$ meters and $\sigma_{y} = 300$ meters in the spreadsheet for Example 10. Leave the target intact. Conduct a simulation with 200 trials. What was the average number of hits?

37. Set $\sigma_{x} = 300$ meters and $\sigma _ {\mathrm{y}} = 600$ meters in the spreadsheet for Example 10. Leave the targe intact. Conduct a simulation with 200 trials. What was the average number of hits?

38. Set $\sigma_{x} = 300$ meters and $\sigma_{y} = 150$ meters in the spreadsheet for Example 10. Leave the targe intact. Conduct a simulation with 200 trials. What was the average number of hits? Explain the difference between this exercise and the previous one.

39. Set $\sigma_{x} = 2 \sigma_{y}$ meters in the spreadsheet for Example 10. Leave the target intact. What is the value of $\sigma_{x}$ if the average number of hits is to be about 6.0, based on one experiment of 400 trials

40. In Example 11, suppose you wanted a better estimate of the distribution of lead-time demand: Would you (1) increase the number of cycles on the ‘One Trial’ worksheet or (2) increase the number of trials on the ‘Experiment’ worksheet? Explain your answer.

41. In Example 11, suppose you wanted a better estimate of the mean lead-time demand? Wha would you do?

42. In Example 11, let the demand probabilities be equal for the possible values 3, 4, 5, and 6. Run an experiment with 400 trials. Compare the average lead-time demand from using the original input data and from using the new input data.

43. In Example 11, let the lead-time probabilities be equal for the possible values 1, 2, and 3. Run an experiment with 400 trials. Compare the average lead-time demand from using the origina input data and from using the new input data.

44. In Example 12, run the experiment 20 times, each with 400 trials. Record the number of times that the middle path was the longest. What is your best estimate of the probability that the middle path is taken?

45. In the above exercise, what is the smallest value and the largest value encountered for the number of times that the middle path was selected? What if you had conducted one simulation, gotten the smallest (or largest) value, and reported that as the result? How could you argue yourself ou of that jam?

46. In Example 12, suppose the third pathway (the bottom one in Figure 20) is changed so that it consists of six U(1,2) activities. Modify the spreadsheet to accommodate this. Which is the mos frequently occurring path now? What insight does this exercise provide?

47. Using Excel, generate 1000 values in a column, using the formula =-10*LN(RAND()).

(a) Compute descriptive statistics about the data in that column, including the minimum value, the maximum value, the mean, the median, and the standard deviation.

(b) Tabulate the values into 10 bins, each of width equal to 5, the first bin beginning at 0, and the eleventh bin for overflow (if any).

(c) Does the histogram resemble any distribution with which you are familiar? If so, what is its name?

Hint: Use FREQUENCY or COUNT in an Excel formula to count bin frequencies.

48. Using Excel, generate 12 columns, each with 250 values, using the formula =RAND().

In cell M1, place the formula =SUM(A1:L1)-6 and copy it to the 249 cells below M1 in column M.

(a) Compute descriptive statistics about the data in column M, including minimum value, maximum value, mean, median, and standard deviation

(b) Tabulate the values with 9 bins. The first bin will include all values less than or equal to 3.5; the next 6 bins are of width one; the last bin will include all values greater than 3.5.

(c) Does the histogram resemble any distribution with which you are familiar? If so, what is its name?

Hint 1: Use FREQUENCY or COUNT in an Excel formula to count bin frequencies.

Hint 2: The values in Column M can be used as a rough approximation to those in Table A.2.

49. Using Excel, generate a table that can be used instead of Table A.1, using the formula =INT(RAND()*100000).

50. Use Excel to devise a Monte Carlo experiment to estimate the value of π, as in the equation for the area of a circle,

Hint: Consider a quarter circle with unit radius inside a unit square. Throw a random dart onto the unit square.

51. A college student is making financial plans for the next year. Expenses include the following known costs:

Tuition $8,400

Dormitory $5,400

There are also a lot of uncertain expenses, with ranges as follows:

Meals $900–$1,350

Entertainment $600–$1,200

Transportation $200–$600

Books $400–$800

The student foresees income to pay for next year. The only certain amounts are as follows:

State scholarship $3,000

Parental contribution $4,000

Some of the income is variable, with ranges as follows:

Waiting tables $3,000–$5,000

Library aide $2,000–$3,000

The student predicts that a loan will be needed. Develop a spreadsheet model and use it with 1,000 trials to forecast the probability distribution for the size of the loan. Treat any amounts that are variable as uniformly distributed over the range indicated.

52. The 22-stop Bally 1090 slot machine had the following number of symbols on each reel:

Payoffs were as follows:

Using Excel, simulate 1,000 plays of this slot machine, each for $1.

How much was the gain or loss?

List of Materials Available on www.bcnn.net

Example2.1CoinToss.xls - Tossing a Coin

Example2.2ServiceTimes.xls - Service Times

Example2.3ArrivalTimes.xls - Arrival Time

Example2.4CoinTossGame.xls - A Coin Tossing Question

Example2.5SingleServer.xls - Grocery Store (single-server queue)

Example2.6AbleBaker.xls - Call Center (two-channel queue)

Example2.7NewsDealer.xls - News Dealer’s Inverntory Problem

Example2.8RefrigInventory.xls - Refrigerator Sales (inventory ordering)

Example2.9CurrentBearings.xls - Current Bearing Replacement Policy

Example2.9ProposedBearings.xls - Proposed Bearing Replacement Policy

Example2.10Target.xls - A Bombing Mission

Example2.11LeadTimeDemand - Lead-Time Demand Distribution

Example2.12Project.xls - Project Activity Network

BCNNvba.xla - Excel add-in (VBA code) to run examples

Chap2Excel5ed.zip - a zip file containing all Excel examples

3 General Principles

This chapter develops a common framework for the modeling of complex systems by using discreteevent simulation. It covers the basic building blocks of all discrete-event simulation models: entities and attributes, activities, and events. In discrete-event simulation, a system is modeled in terms of its state at each point in time; of the entities that pass through the system and the entities that represen system resources; and of the activities and events that cause the system state to change. Discrete-event models are appropriate for those systems for which changes in system state occur only at discrete points in time.

The discussion in this chapter focuses on the discrete-event concepts and methodologies of simulation languages and software (collectively called simulation packages).

This chapter introduces and explains the fundamental concepts and methodologies underlying al discrete-event simulation packages. These concepts and methodologies are not tied to any particular package. Many of the packages use different terminology from that used here, and most have a number of higher-level constructs designed to make modeling simpler and more straightforward for their application domain. For example, this chapter discusses the fundamental abstract concept of an entity, but not covered are more concrete realizations of entities, such as machines, conveyors, and vehicles that are built into some of the packages to facilitate modeling in the manufacturing, materia handling, or other domains

Section 1 covers the general principles and concepts of discrete-event simulation, the even scheduling/time advance algorithm, and the three prevalent world views: event scheduling, process interaction, and activity scanning. Section 2 introduces some of the notions of list processing, one of the more important methodologies used in discrete-event simulation software.

1 Concepts in Discrete-Event Simulation

This chapter deals exclusively with dynamic, stochastic systems (i.e., involving time and containing random elements) that change in a discrete manner. This section expands on these concepts and proposes a framework for the development of a discrete-event model of a system. The major concepts are briefly defined and then illustrated by examples:

System A collection of entities (e.g., people and machines) that interact together over time to accomplish one or more goals.

Model An abstract representation of a system, usually containing structural, logical, or mathematical relationships that describe a system in terms of state, entities and their attributes, sets, processes, events, activities, and delays.

System state A collection of variables that contain all the information necessary to describe the system at any time.

Entity Any object or component in the system that requires explicit representation in the mode (e.g., a server, a customer, a machine).

Attributes The properties of a given entity (e.g., the priority of a waiting customer, the routing of a job through a job shop).

List A collection of (permanently or temporarily) associated entities, ordered in some logica fashion (such as all customers currently in a waiting line, ordered by “first come, first served,” or by priority).

Event An instantaneous occurrence that changes the state of a system (such as an arrival of a new customer).

Event notice A record of an event to occur at the current or some future time, along with any associated data necessary to execute the event; at a minimum, the record includes the even type and the event time.

Event list A list of event notices for future events, ordered by time of occurrence; also known as the future event list (FEL).

Activity A duration of time of specified length (e.g., a service time or interarrival time), which is known when it begins (although it may be defined in terms of a statistical distribution).

Delay A duration of time of unspecified indefinite length, which is not known until it ends (e.g., a customer’s delay in a last-in–first-out waiting line which, when it begins, depends on future arrivals).

Clock A variable representing simulated time, called CLOCK in the examples to follow.

Different simulation packages use different terminology for the same or similar concepts—for example, lists are sometimes called sets, queues, or chains. Sets or lists are used to hold both entities and event notices. The entities on a list are always ordered by some rule, such as first-in–first-out or last-in–first-out, or are ranked by some entity attribute, such as priority or due date. The future event list is always ranked by the event time recorded in the event notice. Section 2 discusses a number of methods for handling lists and introduces some of the methodologies for efficient processing o ordered sets or lists.

An activity typically represents a service time, an interarrival time, or any other processing time whose duration has been characterized and defined by the modeler. An activity’s duration may be specified in a number of ways:

a. Deterministic—for example, always exactly 5 minutes;

b. Statistical—for example, as a random draw from the set 2, 5, 7 with equal probabilities;

c. A function depending on system variables and/or entity attributes—for example, loading time for an iron ore ship as a function of the ship’s allowed cargo weight and the loading rate in tons per hour.

However it is characterized, the duration of an activity is computable from its specification at the instant it begins. Its duration is not affected by the occurrence of other events (unless, as is allowed by some simulation packages, the model contains logic to cancel or postpone an activity in progress). To keep track of activities and their expected completion time, at the simulated instant that an activity duration begins, an event notice is created having an event time equal to the activity’s completion time. For example, if the current simulated time is CLOCK 100 minutes and an inspection time of exactly 5 minutes is just beginning, then an event notice is created that specifies the type of even (an end-of-inspection event), and the event time (1005 105 minutes).

In contrast to an activity, a delay’s duration is not specified by the modeler ahead of time, bu rather is determined by system conditions. Quite often, a delay’s duration is measured and is one of the desired outputs of a model run. Typically, a delay ends when some set of logical conditions becomes true or one or more other events occur. For example, a customer’s delay in a waiting line may be dependent on the number and duration of service of other customers ahead in line as well as the availability of servers and equipment.

A delay is sometimes called a conditional wait, an activity an unconditional wait. The completion of an activity is an event, often called a primary event, that is managed by placing an event notice on the FEL. In contrast, delays are managed by placing the associated entity on another list, perhaps representing a waiting line, until such time as system conditions permit the processing of the entity. The completion of a delay is sometimes called a conditional or secondary event, but such events are not represented by event notices, nor do they appear on the FEL.

The systems considered here are dynamic, that is, changing over time. Therefore, system state, entity attributes and the number of active entities, the contents of sets, and the activities and delays

currently in progress are all functions of time and are constantly changing over time. Time itself is represented by a variable called CLOCK.

Consider the Able–Baker call center system of Example 6 from the Simulation Examples in a Spreadsheet chapter. A discrete-event model has the following components:

System state $L_{Q}(t)$, the number of callers waiting to be served at time $t$;$L_{A}(t)$, 0 or 1 to indicate Able as being idle or busy at time $t$;$L_{B}(t)$, 0 or 1 to indicate Baker as being idle or busy at time $t$.

Entities Neither the callers nor the servers need to be explicitly represented, except in terms of the state variables, unless certain caller averages are desired (compare Examples 4 and 5).

Events Arrival event; Service completion by Able; Service completion by Baker.

Activities Interarrival time, defined in Table 12 from the Simulation Examples in a Spreadsheet chapter; Service time by Able, defined in Table 13 from the Simulation Examples in a Spreadsheet chapter; Service time by Baker, defined in Table 14 from the Simulation Examples in a Spreadsheet chapter.

Delay A caller’s wait in queue until Able or Baker becomes free.

The definition of the model components provides a static description of the model. In addition, a description of the dynamic relationships and interactions between the components is also needed. Some questions that need answers include:

1. How does each event affect system state, entity attributes, and set contents?

2. How are activities defined (i.e., deterministic, probabilistic, or some other mathematical equation)? What event marks the beginning or end of each activity? Can the activity begin regardless of system state, or is its beginning conditioned on the system being in a certain state? (For example, a machining “activity” cannot begin unless the machine is idle, not broken, and not in maintenance.)

3. Which events trigger the beginning (and end) of each type of delay? Under what conditions does a delay begin or end?

4. What is the system state at time 0? What events should be generated at time 0 to “prime” the model—that is, to get the simulation started?

A discrete-event simulation is the modeling over time of a system all of whose state changes occur at discrete points in time—those points when an event occurs. A discrete-event simulation (hereafter called a simulation) proceeds by producing a sequence of system snapshots (or system images) that represent the evolution of the system through time. A given snapshot at a given time (CLOCK t) includes not only the system state at time t, but also a list (the FEL) of all activities currently in progress and when each such activity will end, the status of all entities and current membership of all sets, plus the current values of cumulative statistics and counters that will be used to calculate summary statistics at the end of the simulation. A prototype system snapshot is shown in Figure 1. (Not all models will contain every element exhibited in Figure 1. Further illustrations are provided in the examples in this chapter.)

1.1 The Event Scheduling/Time Advance Algorithm

The mechanism for advancing simulation time and guaranteeing that all events occur in correc chronological order is based on the future event list (FEL). This list contains all event notices for events that have been scheduled to occur at a future time. Scheduling a future event means that, at the instant an activity begins, its duration is computed or drawn as a sample from a statistical distribution; and that the end-activity event, together with its event time, is placed on the future event list. In the real world, most future events are not scheduled but merely happen—such as random breakdowns or random arrivals. In the model, such random events are represented by the end of some activity, which in turn is represented by a statistical distribution

At any given time t, the FEL contains all previously scheduled future events and their associated event times (called $t_{1} , t_{2} , \ldots$ in Figure 1). The FEL is ordered by event time, meaning that the events are arranged chronologically—that is, the event times satisfy

Time t is the value of CLOCK, the current value of simulated time. The event associated with time $t_{1}$ is called the imminent event; that is, it is the next event that will occur. After the system snapshot at simulation time CLOCK t has been updated, the CLOCK is advanced to simulation time ${\mathrm{C L O C K}} = t_{1}$, the imminent event notice is removed from the FEL, and the event is executed. Execution of the imminent event means that a new system snapshot for time $t_{1}$ is created, one based on the old snapshot at time t and the nature of the imminent event. At time $t_{1} .$, new future

Figure 1 Prototype system snapshot at simulation time t.

events may or might not be generated, but if any are, they are scheduled by creating event notices and putting them into their proper position on the FEL. After the new system snapshot for time $t_{1}$ has been updated, the clock is advanced to the time of the new imminent event and that event is executed. This process repeats until the simulation is over. The sequence of actions that a simulator (or simulation language) must perform to advance the clock and build a new system snapshot is called the event-scheduling/time-advance algorithm, whose steps are listed in Figure 2 (and explained thereafter).

The length and contents ofthe FEL are constantly changing as the simulation progresses, and thus its efficient management in a simulation software package will have a major impact on the model’s computer runtime. The management of a list is called list processing. The major list processing operations performed on a FEL are removal of the imminent event, addition of a new event to the list, and occasionally removal of some event (called cancellation of an event). As the imminent event is usually at the top of the list, its removal is as efficient as possible. Addition of a new event (and cancellation of an old event) requires a search of the list. The efficiency of this search depends on the logical organization of the list and on how the search is conducted. In addition to the FEL, al the sets in a model are maintained in some logical order, and the operations of addition and remova of entities from the set also require efficient list-processing techniques. A brief introduction to lis processing in simulation is given in Section 2.

The removal and addition of events from the FEL is illustrated in Figure 2. Event 3 with event time $t_{1}$ represents, say, a service completion event at server 3. Since it is the imminent event at time t, it is removed from the FEL in Step 1 (Figure 2) of the event-scheduling/time-advance algorithm. When event 4 (say, an arrival event) with event time $t^{*}$ is generated at Step 4, one possible way to determine its correct position on the FEL is to conduct a top-down search:

(In Figure 2, it was assumed that $t^{*}$ was between $t_{2}$ and $t_{3} . )$) Another way is to conduct a bottom-up search. The least efficient way to maintain the FEL is to leave it as an unordered list (additions placed arbitrarily at the top or bottom), which would require at Step 1 of Figure 2 a complete search of the list for the imminent event before each clock advance. (The imminent event is the event on the FEL with the lowest event time.)

The system snapshot at time 0 is defined by the initial conditions and the generation of the so-called exogenous events. The specified initial conditions define the system state at time 0. For example, in Figure $2 , \operatorname{i f} t = 0$, then the state (5, 1, 6) might represent the initial number of customers at three different points in the system. An exogenous event is a happening “outside the system” tha impinges on the system. An important example is an arrival to a queueing system. At time 0, the firs arrival event is generated and is scheduled on the FEL (meaning that its event notice is placed on the FEL). The interarrival time is an example of an activity. When the clock eventually is advanced to the time of this first arrival, a second arrival event is generated. First, an interarrival time, call it $a^{*} .$, is

Old system snapshot at time t

Event-scheduling/time-advance algorithm

Step 1. Remove the event notice for the imminent event (event 3, time $t_{1} )$ from FEL.

Step 2. Advance CLOCK to imminent event time (i.e., advance CLOCK from t to t ).

Step 3. Execute imminent event: update system state, change entity attributes, and set membership as needed.

Step 4. Generate future events (if necessary) and place their event notices on FEL, ranked by event time. (Example: Event 4 to occur at time t∗, where $t_{2} < t^{*} < t_{3} . )$ Step 5. Update cumulative statistics and counters.

New system snapshot at time $t_{1}$| CLOCK | System state |$\cdots$| Future event list |$\cdots$| | — | — | — | — | — | |$t_{1}$| (5, 1, 5) | |$(1, t_{2}) - \text{Type 1 event to occur at time} t_{2}$$(4, t^{*}) - \text{Type 4 event to occur at time} t^{*}$$(1, t_{3}) - \text{Type 1 event to occur at time} t_{3}$$\cdot \cdot \cdot$$(2, t_{n}) - \text{Type 2 event to occur at time} t_{n}$| |

Figure 2 Advancing simulation time and updating system image.

generated; it is added to the current time,${\mathrm{C L O C K}} = t ;$ the resulting (future) event time,$t + a^{*} = t^{*}$ is used to position the new arrival event notice on the FEL. This method of generating an external arrival stream is called bootstrapping; it provides one example of how future events are generated in Step 4 of the event-scheduling/time-advance algorithm. Bootstrapping is illustrated in Figure 3.

Figure 3 Generation of an external arrival stream by bootstrapping.

The first three interarrival times generated are 3.7, 0.4, and 3.3 time units. The end of an interarriva interval is an example of a primary event.

A second example of how future events are generated (Step 4 of Figure 2) is provided by a service completion event in a queueing simulation. When one customer completes service, at current time $\mathrm{C L O C K} = t ,$ if the next customer is present, then a new service time,$s^{*}$, will be generated for the next customer. The next service completion event will be scheduled to occur at future time $t^{*} = t + s^{*}$, by placing onto the FEL a new event notice, of type service completion, with event time t∗. In addition, a service-completion event will be generated and scheduled at the time of an arrival event provided that, upon arrival, there is at least one idle server in the server group. A service time is an example of an activity. Beginning service is a conditional event, because its occurrence is triggered only on the condition that a customer be present and a server be free. Service completion is an example of a primary event. Note that a conditional event, such as beginning service, is triggered by a primary event’s occurring and by certain conditions prevailing in the system. Only primary events appear on the FEL.

A third important example is the alternate generation of runtimes and downtimes for a machine subject to breakdowns. At time 0, the first runtime will be generated, and an end-of-runtime even will be scheduled. Whenever an end-of-runtime event occurs, a downtime will be generated, and an end-of-downtime event will be scheduled on the FEL. When the CLOCK is eventually advanced to the time of this end-of-downtime event, a runtime is generated, and an end-of-runtime event is scheduled on the FEL. In this way, runtimes and downtimes continually alternate throughout the simulation. A runtime and a downtime are examples of activities, and end of runtime and end of downtime are primary events.

Every simulation must have a stopping event, here called E, which defines how long the simulation will run. There are generally two ways to stop a simulation:

1. At time 0, schedule a stop simulation event at a specified future time $T_{E} .$. Thus, before simulating, it is known that the simulation will run over the time interval $[ 0 , T_{E} ]$. Example: Simulate a job shop for $T_{E} = 40$ hours.

2. Run length $T_{E}$ is determined by the simulation itself. Generally,$T_{E}$ is the time of occurrence of some specified event E. Examples:$T_{E}$ could be the time of the 100th service completion

at a certain service center.$T_{E}$ could be the time of breakdown of a complex system.$T_{E}$ could be the time of disengagement or total kill (whichever occurs first) in a combat simulation.$T_{E}$ could be the time at which a distribution center ships the last carton in a day’s orders.

In case $2 , T_{E}$ is not known ahead of time. Indeed, it could be one of the statistics of primary interest to be produced by the simulation.

1.2 World Views

When using a simulation package or even when doing a manual simulation, a modeler adopts a world view or orientation for developing a model. The most prevalent world views are the eventscheduling world view, as discussed in the previous section, the process-interaction world view, and the activity-scanning world view. Even if a particular package does not directly support one or more of the world views, understanding the different approaches could suggest alternative ways to mode a given system.

To summarize the previous discussion, when using the event-scheduling approach, a simulation analyst concentrates on events and their effect on system state. This world view will be illustrated by the manual simulations of Section 1.3.

When using a package that supports the process-interaction approach, a simulation analyst thinks in terms of processes. The analyst defines the simulation model in terms of entities or objects and their life cycle as they flow through the system, demanding resources and queueing to wait for resources. More precisely, a process is the life cycle of one entity. This life cycle consists of various events and activities. Some activities might require the use of one or more resources whose capacities are limited. These and other constraints cause processes to interact, the simplest example being an entity forced to wait in a queue (on a list) because the resource it needs is busy with another entity. The process-interaction approach is popular because it has intuitive appeal and because the simulation packages that implement it allow an analyst to describe the process flow in terms of high-level block or network constructs, while the interaction among processes is handled automatically.

In more precise terms, a process is a time-sequenced list of events, activities, and delays, including demands for resources, that define the life cycle of one entity as it moves through a system. An example of a “customer process” is shown in Figure 4. In this figure, we see the interaction between two customer processes as customer n 1 is delayed until the previous customer’s “end service event” occurs. Usually, many processes are active simultaneously in a model, and the interaction among processes could be quite complex.

Underlying the implementation of the process interaction approach in a simulation package, bu usually hidden from a modeler’s view, events are being scheduled on a future event list and entities are being placed onto lists whenever they face delays, causing one process to temporarily suspend its execution while other processes proceed. It is important that the modeler have a basic understanding of the concepts and, for the simulation package being used, a detailed understanding of the built-in but hidden rules of operation. Schriber and Brunner [2003] provide understanding in this area.

Both the event-scheduling and the process-interaction approach use a variable time advance— that is, when all events and system state changes have occurred at one instant of simulated time, the simulation clock is advanced to the time of the next imminent event on the FEL. The activity-scanning approach, in contrast, uses a fixed time increment and a rule-based approach to decide whether any activities can begin at each point in simulated time.

Figure 4 Two interacting customer processes in a single-server queue.

With the activity-scanning approach, a modeler concentrates on the activities of a model and those conditions, simple or complex, that allow an activity to begin. At each clock advance, the conditions for each activity are checked, and, if the conditions are true, then the corresponding activity begins. Proponents claim that the activity-scanning approach is simple in concept and leads to modular models that are more easily maintained, understood, and modified by other analysts a later times. They admit, however, that the repeated scanning to discover whether an activity can begin results in slow runtime on computers. Thus, the pure activity-scanning approach has been modified (and made conceptually somewhat more complex) by what is called the three-phase approach, which combines some of the features of event scheduling with activity scanning to allow for variable time advance and the avoidance of scanning when it is not necessary, but keeps the main advantages o the activity-scanning approach.

In the three-phase approach, events are considered to be activities of duration zero time units. With this definition, activities are divided into two categories, which are called B and C.

B activities activities bound to occur; all primary events and unconditional activities.

C activities activities or events that are conditional upon certain conditions being true.

The B-type activities and events can be scheduled ahead of time, just as in the event-scheduling approach. This allows variable time advance. The FEL contains only B-type events. Scanning to learn whether any C-type activities can begin or C-type events occur happens only at the end of each time advance, after all B-type events have been completed. In summary, with the three-phase approach, the simulation proceeds with repeated execution of the 3 phases until it is completed:

Phase A Remove the imminent event from the FEL and advance the clock to its event time. Remove from the FEL any other events that have the same event time.

Phase B Execute all B-type events that were removed from the FEL. (This could free a number of resources or otherwise change system state.)

Phase C Scan the conditions that trigger each C-type activity and activate any whose conditions are met. Rescan until no additional C-type activities can begin and no events occur.

The three-phase approach improves the execution efficiency of the activity-scanning method. In addition, proponents claim that the activity-scanning and three-phase approaches are particularly good at handling complex resource problems in which various combinations of resources are needed to accomplish different tasks. These approaches guarantee that all resources being freed at a given simulated time will be freed before any available resources are reallocated to new tasks.

Example 2: Call Center, Back Again

For the Call Center in Example 1, ifwe were to adopt the three-phase approach to the activity-scanning world view, the conditions for beginning each activity in Phase C would be as follows:

Ifit were to take the process-interaction world view, we would view the model from the viewpoint of a caller and its “life cycle.” Considering a life cycle as beginning upon arrival, a customer process is pictured in Figure 4.

In summary, the process-interaction approach has been adopted by the simulation packages most popular in the USA. On the other hand, a number of activity-scanning packages are popular in the UK and Europe. Some of the packages allow portions of a model to be event-scheduling-based, if tha orientation is convenient, mixed with the process-interaction approach. Finally, some of the packages are based on a flow chart, block diagram, or network structure, which upon closer examination turns out to be a specific implementation of the process-interaction concept.

1.3 Manual Simulation Using Event Scheduling

In the conducting ofan event-scheduling simulation, a simulation table is used to record the successive system snapshots as time advances.

Example 3: Single-Channel Queue

Consider the grocery store with one checkout counter that is simulated in Example 5 from the Simulation Examples in a Spreadsheet chapter by an ad hoc method. The system consists of those customers in the waiting line plus the one (if any) checking out. A stopping time of 60 minutes is set for this example. The model has the following components:

System state (LQ(t), LS(t)), where LQ(t) is the number of customers in the waiting line, and LS(t) is the number being served (0 or 1) at time t.

Entities The server and customers are not explicitly modeled, except in terms of the state variables.

Events

Arrival (A);

Departure (D);

Stopping event (E), scheduled to occur at time 60.

Event notices

(A, t), representing an arrival event to occur at future time t;

(D, t), representing a customer departure at future time t;

(E, 60), representing the simulation stop event at future time 60.

Activities

Interarrival time, defined in Table 9 from the Simulation Examples in a Spreadsheet chapter; Service time, defined in Table 10 from the Simulation Examples in a Spreadsheet chapter.

Delay Customer time spent in waiting line.

The event notices are written as (event type, event time). In this model, the FEL will always contain either two or three event notices. The effect of the arrival and departure events is shown in detail in Figures 5 and 6.

Figure 5 Execution of the arrival event.

Figure 6 Execution of the departure event.

The simulation table for the checkout counter is given in Table 1. The reader should cover all system snapshots except one, starting with the first, and attempt to construct the next snapshot from the previous one and the event logic in Figures 5 and 6.

Initial conditions are that the first customer arrive at time 0 and begin service. This is reflected in Table 1 by the system snapshot at time zero $( \mathbf{C L O C K} = 0 )$, with $L Q ( 0 ) = 0 , L S ( 0 ) = 1$, and both a departure event and arrival event on the FEL. Also, the simulation is scheduled to stop at time 60. Only two statistics, server utilization and maximum queue length, will be collected. Server utilization is defined by total server busy time (B) divided by total time $( T_{E} )$). Total busy time, B, and maximum queue length, MQ, will be accumulated as the simulation progresses. A column headed “Comments” is included to aid the reader $( a^{*}$ and $s^{*}$ are the generated interarrival and service times, respectively).

As soon as the system snapshot at time CLOCK 0 is complete, the simulation begins. At time 0, the imminent event is $( \mathsf {A} , 1 )$. The CLOCK is advanced to time 1, and $( \mathsf {A} , 1 )$ is removed from the FEL. Because $L S ( t ) = 1$ for $0 \leq t \leq 1 ( \mathrm{i . e .}$, the server was busy for 1 minute), the cumulative busy time is increased from $B = 0$ to $B = 1$. By the event logic in Figure 6, set $L S ( 1 ) = 1$(the

Table 1 Simulation Table for Checkout Counter