From Sigma

(Difference between revisions)
Jump to: navigation, search
(File Name Extensions)
(File Name Extensions)
Line 4: Line 4:
==File Name Extensions==
==File Name Extensions==
The specific function of SIGMA files are identified by the extensions to their filenames as in following table. .
The specific function of SIGMA files are identified by the extensions to their filenames as in following table:
{| border=3 cellspacing=0 cellpadding=0
{| border=3 cellspacing=0 cellpadding=0

Revision as of 19:59, 21 July 2008



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.

File Name Extensions

The specific function of SIGMA files are identified by the extensions to their filenames as in following table:

File Name Extensions
Extension File Type Indicated
.BAK Backup copy of the last saved model
.BAT Batch files
.BMP Bitmaps used for animations
.C Source code in C
.DAT Data files for SIGMA models
.EXE Executable programs
.EXP Experiment file for batched runs (chpt. 11)
.H Source code in C
.LIB SIGMA C Function Library
.MOD Sample SIGMA models
.OUT SIGMA output files (if any)

The SIGMA Modeling Environment

SIGMA is a unique and powerful simulation environment. Developed primarily for discrete event simulations, SIGMA has been proven able to represent any computer program, with modeling power referred to in computer science as Turing Complete.

SIGMA is based on the concept of an Event (Relationship) Graph. Event Graphs graphically capture the events taking place within a system and the relationships among these events. While Event Graphs may look similar to flow graphs, they are very different: Event Graphs are relationship graphs. Thus, a simple model can represent a very large and complex system.

SIGMA’s most striking feature is that simulation models can be created, enriched, and edited while they are running. Events can be added, altered, or even deleted during a simulation run. Logic can be changed and errors corrected without stopping a run to change code and recompile. You can even pause and "replay" interesting events. Using SIGMA, a simulation model can be developed and verified in a fraction of the time it would take using conventional simulation languages.

Animation support is fundamentally different in SIGMA than in other simulation modeling environments. Animations are not created from simulation models using conventional add-on software; in SIGMA, the animation and the simulation model are identical.

In addition to graphical modeling, analysis, and animation, SIGMA also includes state-of-the-art graphical data tracking tools and allows pictures, graphs, plots, and data to be pasted into spreadsheets and word processors.

For speed and portability, SIGMA models can be automatically translated (with a mouse click) into a fast C code. Not only does this code allow models to run thousands of times faster, models can then be run from a spreadsheet and multiple experimental runs can be batched together. A SIGMA model can even write a description of itself in English.

Multiple SIGMA sessions can be run concurrently. You can copy and paste objects from one modeling session to another. In fact, models can be developed in one SIGMA session and then graphically integrated into another simulation model while that model is executing.

SIGMA supports the full simulation model life cycle: from model building and testing to output analysis, animation, documentation, and report writing. Discrete event simulation model building has never been easier, and the results from simulations have never before been so easy to observe and understand.

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.


It will be sufficient for our purposes to define a system as:

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

The system may already exist, or it may be proposed. Using simulation, even theoretical systems can be studied. We intentionally do not define a system by the specific entities in it. Rather, we define a system by its purpose. Thus, we speak of a communications system, a health care system, a production system, etc. Using a functional definition of a system helps us avoid thinking of a system as having a fixed structure. Consequently, we view a system in terms of how it ought to function rather than how it has traditionally worked in the past. To design a new system it is necessary to free our thinking from the status quo.

The entities making up the system may be either physical or mathematical. A physical entity might be a patient in a hospital or a part in a factory; a mathematical entity might be a variable in an equation.

When developing simulation models of systems, it is useful to classify entities as being either resident entities or transient entities. Resident entities remain part of the system for long intervals of time, whereas transient entities enter into and depart from the system with relative frequency. In a factory, a resident entity might be a machine; a transient entity might be a part. Depending on the level of detail desired, a factory worker might be regarded as a transient entity in one model and a resident entity in another.

In describing a particular aspect of the dynamic behavior of a system, it is often useful to focus on the cycles of the resident entities. For example, we might describe the busy-idle cycles of machines or workers. Alternatively, we might focus on the paths along which transient entities flow as they pass through the system (e.g., parts moving through a factory). Transient entity system descriptions tend to be more detailed (and more informative) than resident entity descriptions. Each type of modeling has advantages: modeling resident entity cycles tends to be easy and efficient, while modeling the details of transient entity flow gives more information. Typically, a mixture of both viewpoints is used, but one or the other predominates.

In systems where there are relatively few resident entities and a great many transient entities, it is usually most efficient to study the cycles of the resident entities. Examples include semiconductor factories with thousands of wafers, communication systems with millions of messages, and transportation systems with tens of thousands of vehicles. In simulating such systems, the cycles of resident entities might be described by the values of only a few variables, while the flow of transient entities might require a great many variables to describe. On the other hand, systems where there are only a few transient entities and many resident entities (a power line inspection system or an airline maintenance facility) may be efficiently studied by examining the flow of transient entities.

It will often be the case that an initial model consisting only of resident entities is appropriate. Thus, first-cut system experiments can be done with a simple and efficient model. After a design has been roughed out and more details are desired, the model can be enriched into a transient entity flow model. Enriching the model to explicitly include transient entities generally makes the model larger, more complex, more prone to errors, and slower to execute. It may be wiser to use detailed transient entity models only for final refinements of a design. A well-designed simulation may have some sections that model only resident entity cycles and other sections that model the detailed flow of transient entities.

Entities are described by their characteristics (referred to as attributes). Attributes can be quantitative or qualitative. Moreover, they can be static and never change (the speed of a machine), or they can be dynamic and change over time (the length of a waiting line). Dynamic attributes can further be classified as deterministic or stochastic depending on whether or not the changes in their values can be predicted with certainty. It is sometimes useful to think of entities as belonging in sets owned by other entities. For example, in a factory a set of parts might be waiting in a line (queue) for a particular machine. Also, a set of machines (routing) might be required to process each part. Thus, each machine owns a set of parts, and each part owns a set of machines.

The Entity/Attribute Hierarchy for a Health Care System
The Entity/Attribute Hierarchy for a Health Care System

The level of detail with which we choose to describe a system determines whether a particular system component is thought of as an entity or an attribute of some entity. For example, we can examine regional health care systems at various levels. (See Figure 2.1.) We might think of the number of hospitals in the region as an attribute of the region. For greater detail, we might want to consider each hospital as a separate entity with the clinics offered as attributes. At an even finer level of detail, we might think of the clinics in the hospitals as distinct entities, with the physicians and patients as attributes of each clinic. Still greater detail is obtained by thinking of individual physicians and patients as entities described by their attributes of specialty, schedule, affliction, etc. The level of detail desired depends on our reasons for studying the system. It would not make sense to model a nationwide health care system at the level of individual patients; likewise, it would not be meaningful to model the laundry at a particular hospital from a national viewpoint.

The rules that govern the interaction of entities in a system that are not under our control are called laws. Similar laws are grouped in families, members of which are distinguished by parameters. Rules that are under our control are called policies; a family of similar policies may be distinguished by the values of their factors. When we experiment to determine the effects of changes in parameters, we are doing sensitivity analysis. When we experiment with changes in factors, we are doing optimization or design. Sensitivity analysis might examine changes in the rate of patient demand for an emergency room. Optimization in the same setting might focus on adjusting nurses' schedules to provide adequate coverage during peak periods. Unlike the real world, in simulation studies both types of experiments are conducted in much the same manner.

Often throughout this book we will use examples of simple, random systems consisting of a waiting line with one or more servers. (Notable exceptions are the financial risk analysis model, the critical path model, and the continuous time simulation of an aquatic ecosystem found in Chapter 5.) These stochastic, dynamic queues are found in many of the systems we are interested in studying: parts waiting for a machine, patients waiting for a doctor, jobs waiting for a computer, messages waiting for transmission, etc. The resident entities in the system are the machines, doctors, computers, data busses, . . . generically referred to as servers. The transient entities are the parts, patients, jobs, messages, . . . generically referred to as customers. Although not as obvious, the waiting lines, buffers, and queues are also resident entities in a queueing system. Laws describing the system might include the probability distribution of the time between successive customer arrivals. Policies might include the number of servers, the amount of waiting space, and the priority level different types of customers receive for service.

The state of a system is a complete description of the system and includes values of all attributes of entities, parameters of laws, factors for its policies, time, and what might be known about the future. The state space is the set of all possible system states. A process is an indexed sequence of system states; typically the index is time, but it might be a count of customers or some other system characteristic.


We will define a model simply as

A system used as a surrogate for another system.

In typical computer simulation models, a system with mathematical entities is used as a surrogate for a system with physical entities. In this book when we use the word system, without qualification, we are referring to a real or hypothetical system that is the subject of the simulation study.

Mathematical models are conceptual abstractions of a particular aspect of a system. The mathematics we will be using include probability, statistics, and graphs. When we use the word model, without qualification, we will be referring to a graphical description of a system called an event graph. Finally, simulations will refer to computer programs developed from event graph models. Simulations will be our methodology for studying the model. A model serves as the interface between a system and a methodology for studying the system.

When evaluating a simulation, it is important to differentiate modeling a system from coding a model. Whether or not a simulation is "good" is more or less objective. A good simulation is a completely faithful rendition of a good model; nothing in the model is lost in the code. The process of testing if the simulation is good is called simulation verification, which is discussed in more detail later. This is often much more complicated than verification of other types of computer programs. However, there is no conceptual difficulty in defining a good program as being error free. Of course, the most one can honestly certify about any computer program is that it currently has no known errors.

Defining what constitutes a "good" model is much more subjective. A good model is based on good assumptions. Good assumptions make the simulation more efficient or the system easier to understand while costing little in terms of validity. Driving a good bargain between model simplicity and model validity is the essence of the art of modeling.

A purist view of validity is that a model will be valid as long as it is based on explicit assumptions and the implications of the assumptions are well understood. From this academic viewpoint, a modeling error is not correctly stating and applying all model assumptions. If we take the pragmatist's view of a good model as contributing to correct decisions, it is possible to test the effects of including a particular detail or making a certain assumption by comparing the behavior of the simulation with and without the detail or assumption. Simulation is one of the few methodologies that allows testing the robustness of models with different assumptions. Perhaps the biggest danger in simulation modeling is including too much detail in the model. An experienced consultant in the field once remarked that he could tell a novice at simulation by the excessive amount of detail in his or her models.

A technique for keeping model details at a reasonable level is to focus on the similarities among the entities in the system rather than the differences. If transient entities (customers, jobs, messages, etc.) can be treated as identical, you can develop a valid model that merely keeps track of the numbers of transient entities at various stages of their progress through a system. This makes it unnecessary to have a detailed record for each individual entity. Such a model would require updating relatively few integers (the counts) instead of creating and maintaining separate records for every transient entity in the system. Similarly, treating resident entities (servers, machines, buffers, etc.) as identical allows you to maintain counts of the numbers of resident entities in the various states of their process cycles rather than keeping a record of the status of each entity. In situations where there are a great many transient entities in the system at one time, it might be necessary to treat transient entities as identical. It is certainly more efficient to have a single integer variable that counts transient entities than it is to create and maintain thousands of complete records.

It is natural to notice differences between entities in a system. However, a valuable modeling skill is the ability to recognize similarities. Differences are modeled only when they are essential to the validity of the study results. It is also natural to include detail unless there are solid reasons for assuming that it can be omitted. When building simulation models of complicated systems, it is good practice to require justification for including detail. Even when the differences in entities are thought to be important, a skilled modeler will be able to define groups of entities that can be treated as identical.

Sometimes the activity of developing a simulation model has as much value as the model itself. Building a model forces us to identify our objectives, determine constraints, quantify our knowledge, and expose our misconceptions. It could be argued that a study has merit even if its recommendations are never implemented and that a simulation model has value even if it never runs. Of course, this is of little comfort to the student who fails a homework assignment or an engineer who must try to find another job. It is vastly more satisfying to professors and employers if the simulation model runs and the recommendations from the study are adopted. The motivation for the development of event graphs was to make simulation models easier to build and verify. With event graphs, it is much easier to verify that your simulation program reflects the way you have modeled the system than it is to validate that the model actually can be used to imitate the relevant behavior of the real system.

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.

There is a trade-off involved between validation and verification of a simulation model. Adding detail to a model makes the code more complicated. If correctly implemented, this detail will perhaps improve model validity. However, adding complex details can make code verification more difficult if not impossible. Identifying only the substantive details that are important to include in a simulation model is important and often subject to negotiation.

Really gross errors in a simulation code can be detected using standard statistical testing. For example, a classical paired t-test between the means of samples from the real world and those from simulation runs might be conducted. (A description of a t-test can be found in any introductory statistics textbook.) However, there may not be enough real-world data to reject a hypothesis that the model and real world data have nearly the same parameters. Moreover, the data itself may not be valid. (See the "Five Dastardly D's of Data" in Chapter 9.)

Translating a model from computer code into clear language is a good exercise. It is interesting to contrast what two different people think a model is doing. You can also compare what you think your model is doing with what it thinks it is doing using the English translations generated by SIGMA.

An excellent tool for helping to verify a simulation model is an informal exercise called a "Turing test," named after a man who conjectured on the possibility of not being able to distinguish computing machines from real people. For a Turing test, actual blank forms used in the day-to-day management of a system are filled in with either simulated or real data. Only the blanks that are relevant for the purposes of the study are different. Managers and other people familiar with the system are then asked to identify the real and simulated documents and tell how each form was identified. It is vital that everyone know in advance that this exercise is likely to be repeated several times.

People familiar with these forms are usually more comfortable doing this exercise than they are in reviewing a computer code, evaluating a statistical analysis, or even observing an animation. Just the process of determining what data on each form are relevant to the study can make this exercise worthwhile.

A typical experience with a Turing test has been that the manager can immediately identify most, if not all, of the bogus forms! This is actually a good outcome; it indicates that the manager is paying attention, and it can lay the foundation for effective communication. A non-technical manager "winning" the first round may also help diffuse any antagonism that they may have developed toward the simulation project. What happens next is critical: when the manager tells how the simulated data was identified, changes to the simulation model should be made and the exercise repeated. It is the repetition of the exercise that is important, not the outcome of each iteration.

Statistical analysis to assess whether or not the outcome of the exercise is likely to result from guessing is presented in Schruben (1980). However, such formal analysis can actually be detrimental. It could easily inhibit communication and alienate the manager by moving the discussion to the unfamiliar ground of mathematical statistics.

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

We will follow the changes in a typical future events list by examining a simulation of a machine center with three identical machines (numbered 0, 1, and 2) and two workers (worker 0 and worker 1).

The types of events that might occur in this example are the ARRIVAL of the next part at the machining center, a machine "STARTing" or "FINISHing" work on a part, a BREAKDOWN of a machine, and a broken machine being REPAIRED. An actual simulation model would, of course, have other types of events.

For each event that pertains to a specific machine and/or operator, the machine number followed by the operator number (if appropriate) are listed as event attributes. At a particular time during a simulation run, the future events list might look like the one pictured in Table 2.1. The future events are logically sorted according to times that events are scheduled to occur. Here time will be measured in minutes.

The current time in this example is 3.00, and the ARRIVAL of a part has just occurred at the center. This ARRIVAL event has "scheduled" the next ARRIVAL event to occur at time 3.37. We can determine the status of each machine by scanning down the future events list and checking what lies in the future for each machine. (Recall that the machine number is designated by the first event attribute.) Machine 0 is due to FINISH processing the part it is currently working on at time 3.20, so machine 0 must be busy. Likewise, machine 1 is busy and due to FINISH working on a part at time 3.40. Finally, machine 2 will be REPAIRED at time 3.43, so it is currently being fixed by the repair crew. We can see from the future events list in Table 2.1 that when the part arrived at time 3.00 none of the machines were available to start working on it. Thus, the part will join other parts in a queue waiting to be processed.

Future Events List for a System with Three Machines (Time = 3.00)
Time Event Type Event Attributes
(Current time) 3.00 Arrival
3.20 Finish 0,1
3.35 Breakdown 1
3.37 Arrival
3.40 Finish 1,0
3.43 Repaired 2
9.01 Breakdown 0

Note that machine 0 is due to experience its next BREAKDOWN at time 9.01 and machine 1 is due for a BREAKDOWN at time 3.35 - before it can FINISH its current operation. Therefore, when machine 1 breaks down at time 3.35, the FINISH event for this machine at time 3.40 will have to be cancelled.

To see how this machining center simulation might proceed, we will now advance the current time to 3.20 and execute the FINISH event on machine 0. Looking at the second attribute of this FINISH event, we see that operator 1 becomes idle. Since we know that there is at least one part waiting, we can immediately START processing the next part. A new START event for machine 0 has been scheduled to occur at the current time of 3.20 with operator 1. The future events list is now like Table 2.2.

Future Events List for a System with Three Machines (Time = 3.20)
Time Event Type Event Attributes
(Current time) 3.20 Finish 0,1
3.20 Start 0,1
3.35 Breakdown 1
3.37 Arrival
3.40 Finish 1,0
3.43 Repaired 2
9.01 Breakdown 0

We next execute the START event for machine 0 at time 3.20 with operator 1. Suppose that a stored (or randomly generated) machine processing time for machine 0 is 1.20 minutes, then the FINISH event for this machine will be scheduled to occur 1.20 minutes from the current time of 3.20 or at time 4.40. The future events list after executing the START event at time 3.20 is shown in Table 2.3.

Future Events List for a System with Three Machines (Time = 3.20)
Time Event Type Event Attributes
(Current time) 3.20 Start 0,1
3.35 Breakdown 1
3.37 Arrival
3.40 Finish 1,0
3.43 Repaired 2
4.40 Finish 0,1
9.01 Breakdown 0

Next, we advance the time to 3.35 and execute the BREAKDOWN event for machine 1. This BREAKDOWN event will cause the FINISH event for machine 1 scheduled at time 3.40 to be cancelled. We will assume here that the part is destroyed when the machine breaks down and that the worker becomes available for other work. If it takes five minutes for a repair crew to repair machine 1, the future events list after the BREAKDOWN occurs is like that in Table 2.4. (Note the REPAIRED event for machine 1 has been scheduled at 8.35, five minutes beyond the current time of 3.35.) The simulation will now advance to time 3.37 when the next ARRIVAL event will occur.

Future Events List for a System with Three Machines (Time = 3.35)
Time Event Type Event Attributes
(Current time) 3.35 Breakdown 1
3.37 Arrival
3.43 Repaired 2
4.40 Finish 0,1
8.35 Repaired 1
9.01 Breakdown 0

Do not worry if this all seems a bit mysterious for now. Discrete event simulation modeling is more than a simple exercise in computer programming. It is initially somewhat confusing for everyone. You will soon discover that it is relatively straightforward once you grasp the concept of an event and understand the relationships between events. For this, we will use event graphs.

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.

The basic unit of an event graph is an edge connecting two vertices. Suppose the edge represented in Figure 2.3 is part of an event graph. We interpret the edge between A and B as follows:

Whenever event A occurs, it might cause event B to occur.

Basically, edges represent the conditions under which one event will cause another event to occur, perhaps after a time delay.

Simple Event Graph Edge
Simple Event Graph Edge

Using this notation, we can build a model that simulates a simple waiting line with one server (e.g., a ticket booth at a theater, the drive-in window at a fast-food restaurant, etc.). For our example, we will model an automatic carwash with one washing bay. The event graph of our carwash is represented in Figure 2.4.

We will begin our examination of this graph by discussing each vertex. The RUN vertex models the initialization of the simulation, the ENTER vertex models a car entering the carwash line, the START vertex models the start of service, and the LEAVE vertex models the end of service.

The state variables chosen to describe this system are:

SERVER  = 	the status of the washing bay (busy, idle), initially set idle.
QUEUE   = 	the number of cars waiting in line, initially set equal to zero.

To make our model more readable, we also define the constants, IDLE=1 and BUSY=0.

Back to Main Page
Personal tools