Week 13 - Simulation

Assignment:

Review this document.

Find and review a journal article that describes the development of a simulation and its application. Provide a brief written review (due Mon Dec 1).

Introduction to Simulation

Simulation is a tool that has been commonly used to assist with systems analysis. Simulation is still widely used and is often use in combination with other techniques that we have examined - including linear programming, expert systems, and neural networks.

In its broadest sense, computer simulation is the process of designing a mathematical-logical model of a real system and experimenting with this model on a computer. Thus simulation encompasses a model building process as well as the design and implementation of an appropriate experiment involving that model. These experiments or simulations, permit inferences to be drawn about systems:

In this way, simulation models can be used for design, procedural analysis, and performance assessment.

Simulation modeling assumes that we can describe a system in terms acceptable to a computing system. In this regard, a key concept is that of a system state description. If a system can be characterized by a set of variables, with each combination of variable values representing a unique state or condition of the system, then manipulation of the variable values simulates movement of the system from state to state. A simulation experiment involves observing the dynamic behavior of a model by moving from state to state in accordance with well-defined operating rules designed into the model.

Changes in the state of a system can occur continuously over time or at discrete instants in time. The discrete instants can be established deterministically or stochastically depending on the nature of model inputs. Although the procedures for describing the dynamic behavior of discrete and continuous change models differ, the basic concept of simulating a system by portraying the changes in the state of the system over time remains the same.

Example - Simulation of a Bank Teller

As an example of the concept of simulation, the processing of customers by a teller at a bank will be considered. Customers arrive at the bank, wait for service by the teller if the teller is busy, are served, and then depart the system. Customers arriving to the system when the teller is busy wait in a single queue in front of the teller. For simplicity, assume that the time of arrival of a customer and the service time by the teller for each customer are known and are shown below. Our objective is to manually simulate the above system to determine the percent of time the teller is idle and the average time a customer spends at the bank.
Customer #     Time of Arrival    Service Time
                  (Minutes)         (Minutes)
    1                 3.2              3.8
    2                10.9              3.5
    3                13.2              4.2
    4                14.8              3.1
    5                17.7              2.4
    6                19.8              4.3
    7                21.5              2.7
    8                26.3              2.1
    9                32.1              2.5
   10                36.6              3.4

Since the simulation is the dynamic portrayal of the changes in the state of a system over time, the states of the system must be defined. For this example, they can be defined by the status of the teller (busy or idle) and by the number of customers at the bank. The state of the system is changed by a customer arriving to the bank, and the completion of service by the teller and subsequent departure of the customer. To illustrate a simulation, we will determine the state of the system over time by processing the events corresponding to the arrival and departure of customers in a time-ordered sequence.

The manual simulation of this example corresponding to the values in the above table is summarized in the table below by customer number. It is assumed that initially there are no customers in the system, the teller is idle, and the first customer is to arrive at time 3.2.

Customer  Arrival   Start   Departure   Time in   Time in
Number     Time    Service    Time       Queue      Bank
 (1)        (2)    Time (3)    (4)    (5)=(3)-(2) (6)=(4)-(2)

1 3.2 3.2 7.0 0.0 3.8 2 10.9 10.9 14.4 0.0 3.5 3 13.2 14.4 18.6 1.2 5.4 4 14.8 18.6 21.7 3.8 6.9 5 17.7 21.7 24.1 4.0 6.4 6 19.8 24.1 28.4 4.3 8.6 7 21.5 28.4 31.1 6.9 9.6 8 26.3 31.1 33.2 4.8 6.9 9 32.1 33.2 35.7 1.1 3.6 10 36.6 36.6 40.0 0.0 3.4

In the above table, columns (1) and (2) are taken from the first table. The start of service time given in column (3) depends on whether the preceding customer has departed the bank. It is taken as the larger value of the arrival time of the customer and the departure time of the previous customer. Column (4), the departure time, is the sum of the column (3) value and the service time for the customer given in the first table. Values for time in queue and time in bank for each customer are computed as shown in the above table. Average values per customer for these variables are 2.61 minutes and 5.81 minutes, respectively.

The above table presents a good summary of information concerning the customer but does not provide information about the teller and the queue size for the teller. To portray such information, it is convenient to examine the events associated with the situation.

The logic associated with processing the arrival and departure events depends on the state of the system at the time of the event. In the case of the arrival event, the disposition of the arriving customer is based on the status of the teller. If the teller is idle, the status of the teller is changed to busy and the departure event is scheduled for the customer by adding his service time to the current time. However, if the teller is busy at the time of an arrival, the customer cannot begin service at the current time and, therefore, he enters the queue (the queue length is increased by one). For the departure event, the logic associated with processing the event is based on queue length. If a customer is waiting in the queue, the teller status remains busy, the queue length is reduced by one, and the departure event for the first waiting customer is scheduled. However, if the queue is empty, the status of the teller is set to idle.

An event-oriented description of the bank teller status and the number of customers at the bank is given in the table below. The events are listed in chronological order. The results indicate that the average number of customers at the bank in the first 40 minutes is 1.4525 and that the teller is idle 20 percent of the time.

Event   Customer   Event   Number   Number   Teller   Teller
Time     Number     Type  in Queue  in Bank  Status  Idle Time

0.0 Start 0 0 Idle 3.2 1 Arrival 0 1 Busy 3.2 7.0 1 Departure 0 0 Idle 10.9 2 Arrival 0 1 Busy 3.9 13.2 3 Arrival 1 2 Busy 14.4 2 Departure 0 1 Busy 14.8 4 Arrival 1 2 Busy 17.7 5 Arrival 2 3 Busy 18.6 3 Departure 1 2 Busy 19.8 6 Arrival 2 3 Busy 21.5 7 Arrival 3 4 Busy 21.7 4 Departure 2 3 Busy 24.1 5 Departure 1 2 Busy 26.3 8 Arrival 2 3 Busy 28.4 6 Departure 1 2 Busy 31.1 7 Departure 0 1 Busy 32.1 9 Arrival 1 2 Busy 33.2 8 Departure 0 1 Busy 35.7 9 Departure 0 0 Idle 36.6 10 Arrival 0 1 Busy 0.9 40.0 10 Departure 0 0 Idle

To place the arrival and departure events in their proper chronological order, it is necessary to maintain a record calendar of future events to be processed. This is done by maintaining the times of the next arrival event and the next departure event. The next event to be processed is then selected by comparing these event times. For situations with many events, an ordered list of events would be maintained which is referred to as an event file or event calendar.

There are several important concepts illustrated by the above example. We observe that at any instant in simulated time, the model is in a particular state. As events occur, the state of the model may change as prescribed by the logical-mathematical relationships associated with the events. Thus, the events define the dynamic structure of the model. Given the starting state, the logic for processing each event, and a method for specifying sample values, our problem is largely one of bookkeeping. An essential element in our bookkeeping scheme is an event calendar which provides a mechanism for recording and sequencing future events. Another point is that we can view the state changes from two perspectives: the process that the customer encounters as he seeks service (the customer's view), or the events that caused the state of the teller to change (the teller's or bank's view).

Getting Started with Simulation Projects

Models are descriptions of systems. In the physical sciences, models are usually developed based on theoretical laws and principles. The usefulness of models has been demonstrated in describing, designing and analyzing systems. Model building is a complex task but can be made easier if:

The modeling of complex, large-scale systems is often mode difficult than the modeling of physical systems for the following reasons:

The simulation approach can be used to alleviate these difficulties.

Simulation is often used at one of four levels:

Types of Simulation

Simulation can be categorized into the following types:
The above classification is based on the shape of the curve that results by plotting the item of interest with respect to time. Object-oriented simulation is another classification that is sometimes used to further describe simulation approaches that utilize object-oriented programming techniques. Object-oriented languages such as COOL (CLIPS Object Oriented Language - available within CLIPS) are often used for implementation of object-oriented simulations. Due to time constraints, we will not be examining object-oriented simulation in any additional detail.

Use of Simulation Tools vs Development of a Simulation Using a Conventional Programming Language

When developing a simulation, one must decide whether to use a simulation tool or whether to develop the simulation using a more traditional language such as Fortran or "C". The reasons for selecting one or the other approach are much the same as deciding whether to use an expert system development tool or develop an expert system from a more conventional language. Simulation tools can greatly speed the development of a simulation application by providing capabilities that are common to many simulation applications - we'll have a chance to utilize the SLAM simulation tool to simulate some simplified systems.

Deciding Whether to Use a Discrete or Continuous Approach

This section provides a brief discussion on the problem characteristics that help determine whether a discrete or continuous approach should be used.

Selection of the System for Simulation Purposes

The selection and definition of the system was examined in weeks 1 and 2. The definition of a system for use in a simulation depends on the project objectives. The purpose of the simulation is usually to explore the effects of change in or on the system before the change occurs. Proposed changes that occur both inside the system and outside the system may be evaluated.

Collection of Information from Discrete Simulation

The collection of information from a discrete simulation depends on the project objectives and the viewpoint from which information is desired. For example, if information is collected from the customers' point of view, waiting time is likely of most importance. Other important information includes the service time and the total time in the system. If information is collected from the point of view of the server, the percent of time the server is utilized is probably the most important information.

Selection of Discrete Event Simulation Lengths

Simulation lengths should be long enough to overcome start-up conditions that could bias initial results. Many random number generators that are used in sampling distributions to determine service times and entity arrivals to a system give specific strings. Thus, long runs of the simulation may be needed to overcome this problem. In addition, differing the starting seed for random number stream sampling should be done to overcome this problem.

Next-Event Scheduling

Most simulation tools that support discrete simulation use next-event scheduling as described in the banking example previously. The following example illustrates this approach and some of its advantages. Consider a simulation in which 1000 entities will be run through the system. One approach that could be used would be to determine all arrival times and service times before running the simulation. The major disadvantage of this approach is that it is wasteful of computer time and space. For large applications, CPU time and space may not be sufficient to use this approach.

In next-event scheduling, as each event is set up, it creates (schedules) the next procedure (event). Each event schedules the next event, allowing time to advance to the next scheduled event rather than advancing by some fixed time step. An event calendar is used to manage the scheduling of events. All events are scheduled and time at which they will occur is placed on the calendar. Next-event scheduling works well when one is not concerned about what happens outside of the system.

Why Model with Distributions Rather Than Averages?

In most instances, distributions are sampled rather than using the averages from the distributions. This better represents the actual system and provides results in the form of a distribution as well. Distributions can't generally be added linearly and thus the use of the distributions in the simulation is used to obtain the resulting distribution.

Collection of Statistics in Discrete Event Simulation

There are many possible statistics that one might wish to collect from a discrete event simulation. Statistics commonly collected by simulation tools without additional effort on the part of the simulation developer include information about queues (average length, minimum length, maximum length, length at end of simulation, average time spent in queue, minimum time and maximum time in queue), services (percent utilization, maximum length of utilization, maximum idle time), and entities (length of time in services and length of time in system).

Entities are objects within a discrete simulation. Entities have attributes such as size, weight, time spent in the system thus far, color, etc. For example, an entity might represent a truck and attributes might include time of arrival to the system, weight of grain in the truck, and time to unload the grain.

Events refer to actions that are associated with entities. Events can be classified into 4 types: departing, arrivals, end of service (departure from service), and start of service.