Sunday, March 17, 2013

Discrete System Simulation


Chapter 08:(Discrete System Simulation)

8-1:: Discrete Events::
Question: Define the following terms with respect to discrete system simulation: (‘01)
i)                    State descriptor
ii)                  Discrete event
Answer:
State descriptor: The model used in discrete system simulation has a set of numbers to represent the state of the system. A number used to represent some aspect of the system state is called a state descriptor.
For example, In a document processing system, some state descriptors range over values that have physical significance, such as the number representing the count of documents. Others represent conditions, such as the flag denoting whether a break in work is due.

Discrete events: As the simulation proceeds, the state descriptors change value. We can define a discrete event as a set of circumstances, that causes an instantaneous change in one or more system script descriptors. It is possible that two different events occur simultaneously, or are modeled as being simultaneous. The simulation proceeds by executing all the changes to the system descriptors associated with each event, as the events occur, in chronological order.

8-2:: Representation of Time::
Question: How time is represented in discrete system simulation? (M.Sc.- ’97,’99)
Answer: In simulation, the passage of time is recorded by a number referred to as clock time. It is usually set to zero at the beginning of a simulation and subsequently indicates how many units of simulated times has passed since the beginning of the simulation. The term simulation time means the indicated clock time and not the time a computer has taken to carry out the simulation. As a rule, there is no direct connection between the simulated time and the time taken to carry out the computations. Depending upon the nature of the system being simulated, and the detail to which it is modeled, the ratio to the simulated time to the real time taken can very enormously.
For example, the simulation of an economic system, where events have been aggregated to occur once a year, a hundred years of operation could easily be performed in a few minutes of calculations.

Question: Discuss the basic methods used for updating clock time (simulation clock time) in (discrete) system simulation. (M.Sc.- ’97,’99)
Answer: Two basic methods exist for updating simulation clock time:
  1. The 1st method is referred to as event-oriented and
  2. The 2nd method is referred to as interval-oriented.

# Event-oriented method advance the clock to the time at which the next event is due to occur.
# Interval-oriented method advance the clock by small (usually uniform) intervals of time and determine at each interval whether an event is due to occur at that time.

Discrete system simulation is usually carried out by using the event-oriented method, while continuous system simulation normally uses the interval-oriented method. However, there are no firm rule about the way time is represented in simulations for discrete and continuous systems. An interval-oriented program will detect discrete changes and can therefore simulate discrete systems, and an event-oriented program can be made to follow continuous changes by artificially introducing events that occur at regular time intervals. Farther, the event-oriented method is not necessary faster than the interval-oriented method for discrete systems.

# Significant event simulation: It is an approach to representing the passage of time in system simulation. The method is applicable to continuous systems in which there are quiescent periods. The significant event approach assumes that simple analytic functions, such as polynomials of low order, can be used to project the span of a quiescent period. The event that ends the period could be any one of several alternatives, each of which has a projected span. The significant event is the one with the least span. Determining this event, by simple comparisons of the projections, allows the clock to be updated by an extended period of time; achieving the same thing would otherwise have cost the effort of executing the updating of many intervals of fixed size.
For example, an automobile traveling at constant acceleration. Its movement might result in a significant event for several reasons: the automobile might approach the preceding vehicle closer than a specific limit, it might reach the end of the road, its velocity might reach some limit, or it might come to rest. If the initial conditions are known, the elapsed time for each of these possible events can be calculated from simple formulae. Conditions relating to all other vehicles must be evaluated before deciding on the next significant event for the entire system.

Question: Compare between fixed time step and next event methods of time representation in discrete system simulation. Mention the properties of system where these methods are preferable. (‘98)
Answer:
Answer: Two basic methods exist for updating/advancing simulation clock:
  1. The 1st method is referred to as next event method and
  2. The 2nd method is referred to as fixed time step method.
Next event method also called event-oriented method and fixed time step method also called interval-oriented method.

# Next event method advance the clock to the time at which the next event is due to occur. This method is used by all major simulation software. With the next-event approach, the simulation clock is initialize to zero and the times of occurrence of future events are determined. The simulation clock is then advanced to the time of occurrence of the most imminent (first) of those future events, at which point the state of the system is updated to account for the fact that an event has occurred. This process of advancing the simulation clock from one event time to another is counted until eventually some pre-specified stopping condition is satisfied.
# Fixed time step method advance the clock by small (usually uniform) intervals of time and determine at each interval whether an event is due to occur at that time. If one or more events were scheduled to have occurred during this interval, these events are considered to occur at the end of the interval and system state (and statistical counters) are updated accordingly. Two disadvantages of fixed time step method are the errors introduced by processing events at the end of the interval in which they occur and the necessity of deciding which event to process first when events are not simultaneous in reality are treated as such by the model. This problems can be made less severe by making the interval smaller, but these increases the amount of checking for event occurrences that must be done and results in increase in execution time.

Discrete system simulation is usually carried out by using the event-oriented method, while continuous system simulation normally uses the interval-oriented method. However, there are no firm rule about the way time is represented in simulations for discrete and continuous systems. An interval-oriented program will detect discrete changes and can therefore simulate discrete systems, and an event-oriented program can be made to follow continuous changes by artificially introducing events that occur at regular time intervals. Farther, the event-oriented method is not necessary faster than the interval-oriented method for discrete systems.


8-3:: Generation of Arrival Patterns::
Question: Briefly describe the generation of arrival patterns and in discrete system simulation. (M.Sc.- ’97,’99)
Answer: An important aspect of discrete system simulation is the generation of exogenous arrivals. One approach is trace driven simulation. In this approach the sequence of arrival patterns have been generated from observations on a system. Program monitors can be incorporated with, or attached to, the running system to extract the data with little or no disturbance of the system operation.
When there is no interaction between the exogenous arrivals and the endogenous events of the system, it is permissible to create a sequence of arrivals in preparation for the simulation. Usually, the simulation proceeds by creating new arrivals as they are needed.

Another approach is called bootstrapping. This is the process of making one entity create its successor. The method requires keeping only the arrival time of the next entity. In this method the exogenous arrival of an entity is defined as an event and the arrival time of the next entity is recorded as one of the event times. When the clock time reaches this event time, the event of entering the entity into the system is executed, and the arrival time of the following entity is immediately calculated from the inter-arrival time distribution.
The arrival entity usually needs to have some attribute values generated, in which case, attention must be paid to the time at which the values are generated. They could be generated at the time the arrival time is calculated, or they could be generated when the entity actually arrives.



Question: Why bootstrapping method is preferred in generating arrival pattern? (’98, ’01)
Answer: This is the process of making one entity create its successor. The method requires keeping only the arrival time of the next entity. In this method the exogenous arrival of an entity is defined as an event and the arrival time of the next entity is recorded as one of the event times. When the clock time reaches this event time, the event of entering the entity into the system is executed, and the arrival time of the following entity is immediately calculated from the inter-arrival time distribution.
The arrival entity usually needs to have some attribute values generated, in which case, attention must be paid to the time at which the values are generated. They could be generated at the time the arrival time is calculated, or they could be generated when the entity actually arrives.

8-4 Simulation of a Telephone System

Question: While simulating a Telephone System which entities do you consider as temporary entity and permanent entity and why?
Answer:
                To model a telephone system we consider the following entities: Telephone Lines, Links (through which call can be established), Phone Calls. Temporary entities are those that are created and destroyed during the simulation whereas permanent entities remain during the run. Usually entities declared as permanent are stored collectively rather than in individually identifiable records. Unlike temporary entities, permanent entities are not destroyed individually; they are destroyed collectively. In this respect telephone lines and links should be permanent entities because they are usually permanent and can be handled collectively. But individual phone call created for a short period of time and after that they should be destroyed. So we can consider phone call as temporary entity.

8-6:: Simulation Programming Tasks::
Question: Outline the general tasks involved in preparing a computer program for a simulation. (’01)
Answer: There are three major tasks:
  1. The first is to generate a model and initialize it. From the description of the system, a set of numbers must be created to represent the stare of the system. This set of numbers called the system image.
  2. The second task is to program the procedure that executes the cycle of actions involved in carrying out the simulation. This procedure is referred to as simulation algorithm.
  3. The third task is to generate the output report.





Question: Illustrate the general flow of control during the executions of a simulation program. (’01)
Answer: The steps are:
  1. Find the next potential event;
  2. Select an activity;
  3. Test if the event can be executed;
  4. Change the system image;
  5. Gather statistics.

`                                   Figure: Execution of simulation algorithm.





8-7:: Gathering Statistics::
Question: Mention the common statistics which are usually generated as the output of a simulation. (’01)
Answer: Commonly required statistics which are usually included in the output of a simulation are as follows:
  1. Counts- giving the number of entities of a particular type or the number of times some event occurred.
  2. Summary measures- such as extreme values, mean values, and standard deviations.
  3. Utilization- defined as the fraction (or percentage) of time some entity is engaged.
  4. Occupancy- defined as the fraction (or percentage) of a group of entities in use on the average.
  5. Distributions- of important variables, such as queue lengths or waiting times.
  6. Transit times- defined as the time taken for an entity to move from one part of the system to some other part.

8-8:: Counters and Summary Statistics::
Mean: The mean of a set of N observations is defined as
                                   

Variance: If there are N observations taking the values and having the mean value m, the variance is estimated with the formula
                                   

Standard Deviation: Standard deviation (SD) is the (positive) square root of the variance
                                   

Sum of squares:
                                   

8-9:: Measuring Utilization and Occupancy::
Question: How can we measure the utilization/ occupancy for a entity or for a group of entities.
Answer: Measuring utilization of occupancy:

Utilization (for single entity): Defined as the fraction (or percentage) of time some entity is engaged. To measure the utilities, it is necessary to keep a record of the time  at which the item last becomes busy. When the item become free at time , the interval  is derived and added to a counter. If entity is used N times, the utilization U is derived by dividing the accumulated total by the total time T:
                                   
 SHAPE
Figure: Utilization of equipment.

Utilization (for a group of entities): To find the average number of entities in use, a record must be kept of the number of entities currently in use and the time at which the last change occurred. If the number changes at time  to the value , then, at the time of the next change , the quantity  must be calculated and added to an accumulated total. The average number of entities in use, is then calculated by dividing the total time T:
                                                         [N: Number of times the value of  changed]
 SHAPE
Figure:

Occupancy: The term occupancy is used to describe the average number of entities is use as a ratio to the maximum. If there are M entities and the quantity in the number of entities busy in the interval  to  and the number  is changed N times, then the occupancy B is:
                                   

Question: Compare between fixed time step and next event methods of time representation in discrete system simulation. Mention the properties of system where these methods are preferable. (‘98)
Answer:



No comments:

Post a Comment

Total Pageviews