Event Graph Reduction

From Support

Jump to: navigation, search

It is sometimes possible to reduce the number of vertices in an event graph without changing the behavior of the model. Simulations with few events will often run faster than models with more events, although this is not always the case. An event graph with fewer vertices may lead to a more efficient simulation program; however, the graph may be more difficult to understand. Generally, models with a large number of very simple vertices will be easier to debug or modify than models with fewer but more complicated vertices.

It is possible, however, to increase the efficiency of a simulation without increasing the complexity. This is done by using pre-emptive vertex execution, a scheduling delay time for an edge given by an asterisk (*). Recall that a delay time of * means that the scheduled destination vertex is executed immediately, without being placed on the future events list. It pre-empts any other events that might be scheduled at the same time. This often results in a significant reduction in simulation execution time.

We will use our basic single server model to illustrate event graph reduction. The START vertex can be eliminated if we redefine Q (queue) to be the number of customers in the system, including any customers in service, rather than the length of the waiting queue. The resulting graph is shown below.

STATE VARIABLE:
Q = Number of Customers in the System
Event Graph Without a START Event
Event Graph Without a START Event

To get the same run time efficiency, the START vertex can be effectively eliminated without changing the graph except to make the delay times on the edge from ENTER to START and the edge from LEAVE to START asterisks (*) rather than zero. This would cause the execution of the START event to occur without ever scheduling it on the list of future events.

It is possible to eliminate all of the vertices in our model except the RUN vertex (which is executed only once anyway) and the LEAVE vertex. This would require that we generate the (random) number of arrivals to the queue during the time that a single customer is served. We will call this number of arrivals during a service interval, A. In some simple cases, a value for A can be generated very easily (e.g., if the times between customer arrivals are exponentially distributed, A will have a Poisson distribution). The single-event model for our queue is shown below.

STATE VARIABLES:
Q = Number of Customers in the System
A = Number of Arrivals During a Service
Single Vertex Model (RUN and LEAVE)
Single Vertex Model (RUN and LEAVE)

While the model above might run very fast, it is difficult to enrich; therefore, it is not as useful as some of our earlier models for this system.

It is possible to use edge attributes to assign values to vertex parameters rather than using state changes. At first glance, this might seem like a complicated way to do things, but it is useful. Sometimes edge attributes make the model clearer; sometimes they do not. We will illustrate this technique with our single server queue, where the status of the server, S, and length of the waiting line, Q, will become parameters of the START and LEAVE vertices. The values of these parameters are passed as edge attributes. When an entering customer finds the server idle (S>0), the customer will begin service, making the server busy; the value 0 is passed as an attribute of the edge from ENTER to START into the START parameter, S. The result is the same as having the state change S=0 in the START vertex. Similarly, when the server finishes service, its status will change back to idle (1). This is done by passing the edge attribute value, 1, along the edge from START to LEAVE into the parameter, S, of the LEAVE vertex. This is shown in the event graph below (NOSTATEQ.MOD).

STATE VARIABLES:
Q = Number of Customers Waiting in Line, initial value set to zero, by default.
S = Status of Server (0=busy/1=idle), initially set equal to 1=idle.
Event Graph That Uses Edge Attributes to Assign Values to Vertex Parameters
Event Graph That Uses Edge Attributes to Assign Values to Vertex Parameters

We can do this since there is no chance of the state variable, S, changing during the time intervals represented by the delay times of the edges from ENTER to START and from START to LEAVE. If we had more than one server in this system (S initially greater than one), we would not be able to do this since S might be changed by more than one instance of an event vertex.


Back to Technical References

Personal tools
Navigation