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:
- The
1st method is referred to as event-oriented and
- 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:
- The
1st method is referred to as next event method and
- 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:
- 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.
- 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.
- 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:
- Find
the next potential event;
- Select
an activity;
- Test
if the event can be executed;
- Change
the system image;
- 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:
- Counts- giving the number of entities of a
particular type or the number of times some event occurred.
- Summary measures- such as extreme values, mean values,
and standard deviations.
- Utilization- defined as the fraction (or
percentage) of time some entity is engaged.
- Occupancy- defined as the fraction (or
percentage) of a group of entities in use on the average.
- Distributions- of important variables, such as
queue lengths or waiting times.
- 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: