Event Graph Modeling

From Support

Jump to: navigation, search

Contents

Event Graph Modeling

Numerous ways to enrich and modify the basic queueing model are presented here. The basic single server queue model, CARWASH.MOD, can serve as a template for very sophisticated models. With a few modifications and enrichments, the carwash model can be made to simulate many systems, including those with multiple servers with identical capabilities, multiple servers working in parallel with different capabilities, batching operations, assembly operations, service failures, and closing times. Furthermore, SIGMA is not limited to modeling discrete event simulations. Indeed, any computer simulation can be modeling using SIGMA Here demonstration models have been included that represent continuous time modeling of an aquatic ecosystem, financial risk analysis in coupon bond pricing for an investment bank, and critical path evaluation of a construction project. Several important features of event graphs are expanded upon including edge attributes, event parameters, and event canceling as well as methods for modeling multiple resources and transient entities. This section includes a discussion of the modeling technique of using Boolean variables, which allow alternatives to be expressed more easily, as in "if-then-else" statements, "do-while" loops, and nested loops.

Basic Model Enrichments

This section presents a number of important fundamental skills in event graph modeling. Several important examples are included. Parallel service, batched service, rework, limited waiting space, assembly operations, non-identical servers, and resource failure are all discussed.

You will find that the following discussions are much easier to understand if you read while looking at the models on your computer. The name of the model(s) corresponding to each section is given in the title of that section. You only need to consider one vertex at a time and its exiting edges. One of the major advantages of event graphs is that you do not have to look at the whole graph to understand what is happening Look at one vertex at a time along with its exiting edges—the graph takes care of connecting the model correctly.

Further information Basic Model Enrichments

Event Cancellation

In some cases, the occurrence of an event will cause some previously scheduled event to be cancelled. For example, if a machine in a factory simulation happens to break, the completion of the current job will have to be cancelled. In event graphs, cancelling edges are shown as dashed arrows. Conditions under which the originating vertex will cancel the destination vertex are shown in the same manner as scheduling edges. If the edge condition for a cancelling edge is true, cancellation of the destination vertex is assumed to occur immediately; all the delay times for cancelling edges are equal to zero.

Important examples of event cancelling are included here.

Further information: Event Cancellation

Event Parameters and Edge Attributes

An important enrichment of our basic model is the parameterization of event vertices: similar events can be represented by a single vertex with different parameter values. For example, say there are several machines working in a factory. A "start processing" event might be parameterized to indicate which machine is involved. We might call this event START(M). START(3) would indicate that machine number 3 is starting. Similarly, a "finish processing" event might be parameterized to indicate which machine has just become idle. We might call this event FINISH(M); FINISH(6) would indicate the end of service on machine 6.

Conditional Edge with Delay Time and Parameter Passing
Conditional Edge with Delay Time and Parameter Passing

We parameterize event graphs using the notation in the above figure. The edge on a simulation event graph is now "read" as follows:

If condition (i) is true at the instant when A occurs, then event B(j) will be scheduled to occur t
minutes later with parameter, j, equal to k.

Event parameters and edge attributes are illustrated in the following examples.

Furter information: Event Parameters and Edge Attributes

Multiple Resources

Sometimes several resources must be available for an event to happen. For example, in a factory it may be necessary that both a worker and a machine be idle before a part can be processed. Assigning 0 to the "not-available state" makes multiple resource constraints very simple to model. If several types of resources are needed to schedule an event, simply list the names of these resources on the scheduling edge in your SIGMA graph. If WORKERS is the number of idle workers, PARTS the number of parts available, and MACHINES the number of idle machines, then the edge condition, WORKERS & PARTS & MACHINES, is sufficient to check if all three resources are simultaneously available (assuming, of course, that there are no codes for states of the workers and machines that are negative numbers).

The reason this works is that in SIGMA (like C) zero indicates a condition is false and any non-zero value indicates it is true. Thus, the implicit condition (WORKERS & PARTS & MACHINES) is equivalent to the explicit condition (WORKERS>0 & PARTS>0 & MACHINES>0) - as long as there is no logic error that makes the number of workers, parts, or machines become negative! In fact, the implicit test is preferred to the explicit one in that it allows variables to go negative which turns out to be a great help in detecting errors in logic.

A Problem in Finance: BONDRATE.MOD

So far we have focused on models of queueing systems that are applicable to such areas as manufacturing, health care, and communications. The applications of SIGMA are by no means limited to these systems. Here we will use SIGMA to analyze a problem in finance: determining fair pricing for coupon bonds in the presence of randomly fluctuating interest rates. The simple model we will develop can serve as a basis for more complicated cash stream analysis; indeed, this model can be enriched to study financial risk in general cash flow scenarios.

Further information: A Problem in Finance: BONDRATE.MOD

Project Management (PERT/CPM): PERT.MOD

In a large project, such as the construction of a new building or the development of a major software package, there are typically several activities that may proceed in parallel as well as some precedence constraints among the different activities. When erecting a building, it might be possible to have the windows installed at the same time as the plumbing and electrical wiring; if so, these three activities can proceed in parallel. On the other hand, there might also be precedence requirements among activities: the scaffold must be finished and secured before starting the outside facing; the frame must be finished before starting work on the roof, etc. When planning or bidding for a large project it is important to know as much as you can about how long it might take to finish before resources are committed.

A popular technique for managing large projects is to study activity precedence networks, which use graphs showing the activities that must be completed before others can start.

Further information Project Management (PERT/CPM): PERT.MOD

Modeling Transient Entities

Most of our models so far have dealt primarily with resident entities: the servers and the waiting lines. Suppose that we want to know the average waiting time in line for each customer. The easy way to do this in SIGMA is to use the PUT and GET functions. If we modeled each customer, their average waiting times would be easy to compute (as in BANK2.MOD). However, modeling transient entities in a queueing simulation may require more computer memory and significantly greater processing time. Furthermore, as the simulation becomes more congested, it will become less efficient. It is not uncommon for transient-entity-oriented network simulation languages to become so congested that they abort a run. When the run aborts, there is often no useful information given about that run, possibly just the message that the run has terminated with an error! Thus, the most interesting runs of the simulation (when the system was the busiest) and the most expensive (when the most customers were simulated) are exactly those runs that are aborted. Not observing the simulated system when it is congested can lead to an overly optimistic evaluation of system performance. Pure resident entity models are considerably more efficient; furthermore, this efficiency does not degrade as the system becomes congested.

An important tool for capturing aggregate information about the transient entities (such as average waiting time), Little's Law, is discussed here. Also, the notion behind Little's Law is generalized to capture distributions of waiting times in DELAY.MOD

Further information: Modeling Transient Entities
See also: Using Ranked Lists

Programming with Event Graphs

An event graph can be used as a general flow chart for designing computer programs that have nothing to do with simulation models. If all the edge delay times are zero, each vertex would be a block of assignment statements; edge conditions would show the logic flow. All branching is represented by edges in the graph, including goto's, if-then-else, and function calls. The values of edge attributes passed to the vertex parameter variables act like values passed to functions, as in a C program. The main difference, and it is an important difference, between event graphs and traditional flow charts is branching. In SIGMA more than one branch might be taken, or perhaps none of a set of possible branches might be followed. Recall that when edge conditions are tested they are considered false only if they are equal to zero. Expressions for edge conditions that are non-zero are always considered true.

Topics include boolean variables, conditional expressions , and loops (do, while, and nested).

Further information: Programming with Event Graphs

Model Complexity and Model Size

Although some of the models discussed here may appear complicated at first, keep in mind that a large model is not necessarily a complex model. When building simulations, it is important to distinguish between a model that is inherently complicated and a model that is large but otherwise simple. Complexity occurs when a model is composed of many different types of events; a large simulation might be made up of many events but only a few different types of events.

A large simple model might be built from many copies of a few, essentially identical, subgraphs. It is the commonalities of these subgraphs that keep the model simple. Indeed, special-purpose-simulators are developed by focusing on the commonalities of the elementary components of a particular type of system. For instance, a typical commercial factory simulation package will have a generic subgraph to represent a machine as its basic building block. A crude model of a factory is built by putting together many machine subgraphs, each of which is distinguished only by different parameter values. The parameters for each machine (processing time, distribution of the time between failures, repair time distributions, etc.) can be selected from simple menus. The fundamental differences between simple simulators like that just described and block-oriented, general-purpose simulation languages are the number and the richness of the building blocks available with the language; however, both are limited to a finite set of preprogrammed modules. If you want to simulate a situation not already anticipated by the software vendor, you are out of luck.

Using event graphs, we can construct a simulator of a large scale queueing network by first developing an event graph of the basic building block for the network, a single service center. Using this approach, we can develop a simulation of an arbitrarily large queueing network of service operations with several different types of customers. Each customer will follow a different path through the service network and will have different sets of service times. (See the SIGMA NETWORK model NETWORK.MOD where the PUT and GET functions are discussed.) Starting with a simple queueing system model like those presented in this section, we will quickly build a simulator of an entire queueing network.

Once we are satisfied with the richness of the event graph of a basic building block, we can then use edge attributes and vertex parameters to make as many distinct copies of this subgraph as we want (the picture of our graph will not change). The complexity of our model will be determined by the detail we put into the basic building block; the size of our model is determined only by the number of parameterized copies of this basic event graph that our model generates during a run. It is useful to visualize the basic subgraph of a simulation model as a simulation "molecule" from which a larger model can be developed, much like a "crystal" made up of many molecules.

Continuous Time Simulations: FISHTANK.MOD

Our concern has been mainly with simulating discrete event systems. However, there is another class of systems where the values of state variables are modeled as changing continuously. Simulations of such systems are referred to as continuous time simulations. Continuous time systems can also be simulated using event graphs and the SIGMA software; an example is presented here.

While discrete event models typically are used to study systems that are on a "human scale," continuous time simulations are popular for very large scale and very small scale systems. On a small scale, continuous time simulations are used in the sciences and engineering to study such things as the stress on a robot arm or the dynamics of a collection of molecules. On a large scale, this type of simulation is used to study interactions in social, astronomical, or economic systems.

Further information: Continuous Time Simulations: FISHTANK.MOD

Process Modeling

Many popular simulation packages are based on what is known as a process worldview. (The process approach is also sometimes called network modeling.) With this modeling philosophy, the focus is typically on transient entities, such as customers in a service system or parts flowing through a factory. Steps followed by these transient entities as they move through a system are identified. A simulation model is developed by placing preprogrammed blocks of code in a sequence that approximates the actual processing sequence being modeled. The processing of a transient entity is conceptually viewed as the entity flowing from block to block. The process modeling viewpoint is possibly the purest form of transient entity modeling.

Process-oriented simulation languages provide a series of preprogrammed blocks that represent some of the typical processing stages in a queueing system. Examples of such blocks include a block to represent the entity waiting (i.e., a QUEUE block) and another to represent the start of service (i.e., a SEIZE block). Popular software packages that include a process-oriented feature include GPSS, SIMAN, and SLAM.

Although each of the popular process modeling software packages is similar in function, each has its own terminology. For example, GPSS provides a GENERATE block, which introduces a transient entity into the system; SIMAN calls this a CREATE block. Time delay is modeled using an ADVANCE block in GPSS and a DELAY block in SIMAN. GPSS and SIMAN both have QUEUE blocks to collect waiting time statistics, and both represent the entity waiting for service using SEIZE and RELEASE blocks. (Separate ENTER and LEAVE blocks are used in GPSS to model several identical parallel servers, which they call a "storage facility.") Time delays are modeled on the network arrows in SLAM, similar to the edge delay times used in event graphs.

Further information: Process Modeling


Back to Topics

Personal tools
Navigation