About

From Sigma

Revision as of 23:49, 10 August 2008 by 76.254.39.92 (Talk)
Jump to: navigation, search

Contents

Discrete Event System Modeling

"A process cannot be understood by stopping it. Understanding must move with the flow of the process,
must join it and flow with it"
                                                                  -First Law of Mentat

This chapter contains an introduction to the key concepts and terminology of discrete event simulation. The event graph, a method of concisely organizing the elements of a discrete event simulation, is introduced. Using a simple waiting line as an example, an elementary event graph is developed and explained. The future events list, which is the master scheduler of events in a discrete event simulation, is examined in detail. A verbal description of an event graph is introduced as a first step in developing a formal event graph.

Background and Terminology for Systems Modeling

Here we will use computer simulation to study the dynamic behavior of systems –i.e., how systems change over time. Our focus will be on those systems where the status of a system changes at a particular instant of time; such systems are called discrete event systems. Discrete event systems can be found in areas as diverse as manufacturing, transportation, computing, communications, finance, medicine, and agriculture. Engineers, scientists, managers, and planners use simulation methodologies to design and test new systems and to evaluate existing ones, thus avoiding the expense and risks of physical prototypes and pilot studies.

Systems

A system can be defined as:

     A collection of entities that interact with a common purpose according to sets of 
     laws and policies.

To learn more about systems, click here.

Models

A model can be defined as:

A system used as a surrogate for another system.

To learn more about models, click here.

Model Verification

An absolutely valid simulation model with all the detail and behavior of real life is probably not attainable, or even desirable. However, every simulation model should do what its creator intended. Ensuring that the computer code for the simulation model does what you think it is doing is referred to as the process of model verification.

To learn more about model verification, click here.

Discrete Event Systems and Simulations

As stated earlier, systems in which changes occur at particular instants of time are called discrete event systems. In a simulation of a discrete event system, time is advanced in discrete (variable and often random length) steps to the next interesting state change; uninteresting time intervals are skipped over. This coarse level of detail permits the modeling of very large systems such as airports and factories.

A description of the state of a discrete event system will include values for all of its numerical attributes as well as any schedule it might have for the future. Changes in the state are called events. In a production system, events might include the completion of a machining operation (the state of a machine would change from "busy" to "idle"), the failure of a machine (the machine state would change to "broken"), the arrival of a repair crew (the machine state would change to "under repair"), the arrival of a part at a machining center (the machine might again become "busy"), etc.

The ability to identify the events in a discrete event system is an important skill, one that takes practice to acquire. Initially, you might use the following simple steps as a guide to identify system events:

  1. State the purpose of your system. Be aware that there might be several (conflicting) purposes.
  2. State the objectives of your study.
  3. Design, at least qualitatively, the experiments you might want to run with your simulation.
  4. Identify the resident and transient entities in your system and their important attributes; assign names to the attributes.
  5. Identify the dynamic attributes and the circumstances that cause their values to change . . . these will be the events.

The building blocks of a discrete event simulation program are event procedures. Each event procedure makes appropriate changes in the state of the system and, perhaps, may trigger a sequence of other events to be scheduled in the future. Event procedures might also cancel previously scheduled events. An example of event cancelling might occur when a busy computer breaks down. End-of-job events that might have been scheduled to occur in the future must now be cancelled (these jobs will not end in the normal manner as originally expected).

The event procedures describing a discrete event system are executed by a main control program that operates on a master appointment list of scheduled events. This list is called the future events list and contains all of the events that are scheduled to occur in the future. The main control program will advance the simulated time to the next scheduled event. The corresponding event procedure is executed, typically changing the system state and perhaps scheduling or cancelling further events. Once this event procedure has finished executing, the event is removed from the future events list. Then the control program will again advance time to the next scheduled event and execute the corresponding event procedure. The simulation operates in this way, successively calling and executing the next scheduled event procedure until some condition for stopping the simulation run is met. The operation of the main simulation event scheduling and execution loop is illustrated in Figure 2.2.

Main Event-Scheduling Algorithm
Main Event-Scheduling Algorithm


Extended Example

For an extended example of how a future events list is processed, click here.

Event Graphs

The three elements of a discrete event system model are the state variables, the events that change the values of these state variables, and the relationships between the events (one event causing another to occur). An event graph organizes sets of these three objects into a simulation model. In the graph, events are represented as vertices (nodes) and the relationships between events are represented as edges (arrows) connecting pairs of event vertices. Time sometimes elapses between the occurrence of events.

To learn more about event graphs, click here.

Verbal Event Graphs

Before designing your own event graph model, it is a vital that you develop a verbal description of your system. This description would include state changes associated with each vertex along with a verbal description of each edge condition and delay time on the graph. A verbal event graph for a generic single server queueing system is shown in Figure 2.7.

Developing a verbal description of your system is a necessary first step toward building a realistic and accurate simulation model. It will help you conceptualize the major components in the system, determine the key events and their interrelationships, and identify the state variables, edge conditions, and time delays necessary for the model. Note that state variables will need to be defined that permit testing of all edge conditions in your verbal event graph. Once you have constructed a detailed verbal description, the event graph model will be much easier to build.

Verbal Event Graph of a Single Server Queue
Verbal Event Graph of a Single Server Queue

Visual Power of Event Graphs

The visual modeling power of event graphs is most appreciated after one recognizes the complicated details involved in a discrete event simulation. The fundamental concept in event graph modeling is to use a directed graph as a picture of the relationships among the elements in sets of expressions characterizing the dynamics of the system. Each vertex of the graph is identified with a set of expressions for the state changes that result when the corresponding event occurs. Each edge in the graph identifies sets of logical and temporal relationships between a pair of events.

SIGMA

SIGMA is based on the simple and intuitive Event Relationship Graph (sometimes called an ERG or Event Graph) approach to simulation modeling. The SIGMA project began as an effort to implement the notion of Event Relationship Graphs on personal computers and has evolved into a powerful and practical method for simulation modeling. SIGMA, the Simulation Graphical Modeling and Analysis system, is an integrated, interactive approach to building, testing, animating, and experimenting with discrete event simulations, while they are running. SIGMA is specifically designed to make the fundamentals of simulation modeling and analysis easy. SIGMA is able to translate a simulation model automatically into fast C source code that can be compiled and linked to the sigmalib.lib library to run from a spreadsheet or web interface. SIGMA can also write a description of a simulation model in English. SIGMA was developed without external or University funding.

To learn more about SIGMA, visit the About SIGMA page.


Back to Main Page

Personal tools