MODUL PERKULIAHAN

Simulasi Sistem

Discrete-Event Simulation

Tatap
Fakultas Program Studi Kode MK Disusun Oleh
Muka
Fakultas Teknik Teknik Industri 05610001 Dr. Nova Indah Saragih, S.T., M.T.

04
Abstrak Kompetensi
Modul ini membahas pengertian Mahasiswa mampu menjelaskan
simulasi kejadian diskrit beserta konsep simulasi kejadian diskrit.
contoh-contohnya.

1
 Discrete-Event Simulation

Discrete-event simulation concerns the modeling of a system as it evolves over

time by a representation in which the state variables change instantaneously at
separate points in time. (In more mathematical terms, we might say that the
system can change at only a countable number of points in time.) These points in
time are the ones at which an event occurs, where an event is defined as an
instantaneous occurrence that may change the state of the system. Although
discrete-event simulation could conceptually be done by hand calculations, the
amount of data that must be stored and manipulated for most real-world systems
dictates that discrete-event simulations be done on a digital computer.

Example 1

Consider a service facility with a single server---e.g., a one operator

barbershop or an information desk at an airport-for which we would like to
estimate the (expected) average delay in queue (line) of arriving customers,
where the delay in queue of a customer is the length of the time interval from
the instant of his arrival at the facility to the instant he begins being served.
For the objective of estimating the average delay of a customer, the state
variables for a discrete·event simulation model of the facility would be the
status of the server, i.e., either idle or busy, the number of customers waiting
in queue to be served (if any), and the time of arrival of each person waiting in
queue. The status of the server is needed to determine, upon a customer's
arrival , whether the customer can be served immediately or must join the end
of the queue. When the server completes serving a customer, the number of
customers in the queue is used to determine whether the server will become
idle or begin serving the first customer in the queue. The time of arrival of a
customer is needed to compute his delay in queue, which is the time he begins
being served (which will be known) minus his time of arrival. There are two
types of events for this system: the arrival of a customer and the completion of
service for a customer, which results in the customer's departure. An arrival is
an event since it causes the (state variable) server status to change from idle to
busy or the (state variable) number of customers in the queue to increase by 1.

2
 Correspondingly, a departure is an event because it causes the server status to
change from busy to idle or the number of customers in the queue to decrease
by 1.

In the above example both types of events actually changed the state of the
system, but in some discrete-event simulation models events are used for purposes
that do not actually effect such a change. For example, an event might be used to
schedule the end of a simulation run at a particular time or to schedule a decision
about a system's operation at a particularn time and might not actually result in a
change in the state of the system. This is why we originally said that an event may
change the state of a system.

1. Time-Advance Mechanisms

Because of the dynamic nature of discrete-event simulation models, we must

keep track of the current value of simulated time as the simulation proceeds,
and we also need a mechanism to advance simulated time from one value to
another. We call the variable in a simulation model that gives the current value
of simulated time the simulation clock. The unit of time for the simulatioc
clock is never stated explicitly when a model is written in a general-purpose
language such as FORTRAN, Pascal, or C, and it is assumed to be in the same
units as the input parameters. Also, there is generally no relationship between
simulated time and the time needed to run a simulation on the computer.

Historically, two principal approaches have been suggested for advancing the
simulation clock: next-event time advance and fixed-increment time advance.
Since the first approach is used by all major simulation languages and by most
people coding their model in a general-purpose language, and since the second
is a special case of the first, we shall use the next-event time-advance
approach for all discrete-event simulation models discussed in this book.

With the next-event time-advance approach, the simulation clock is initialized

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 these future events, at which point the state of the system is

3
updated to account for the fact that an event has occurred, and our knowledge
of the times of occurrence of future events is also updated. Then the
simulation clock is advanced to the time of the (new) most imminent event,
tbe state of the system is updated, and future event times are determined, etc.
This process of advancing the simulation clock from one event time to another
is continued until eventually some prespecified stopping condition is satisfied.
Since all state changes occur only at event times for a discrete-event
simulation model, periods of inactivity are skipped over by jumping the clock
from event time to event time. (Fixed-increment time advance does not skip
over these inactive periods, which can eat up a lot of computer time) It should
be noted that the successive jumps of the simulation clock are generally"
variable (or unequal) in size.

Example 2

We now illustrate in det'ail the next-event time-advance approach for the

single-server queueing system of Example 1. We need the following notation:

▪ ti = time of arrival of the ith customer (to = 0)

▪ Ai = ti – to = interarrival time between (i -l)st and ith arrivals of customers
▪ Si = time that server actually spends serving ith customer (exclusive of
customer's delay in queue)
▪ Di = delay in queue of ith customer
▪ ci = fi + Di + Si = time that ith customer completes service and departs
▪ ei = time of occurrence of ith event of any type (ith value the simulation
clock takes on, excluding the value eo = 0)

Each of these, defined quantities will generally be a random variable. Assume

that the probability distributions of the interarrival times A1, A2, ... and the
service times S1, S2, ... are known and have cumulative distribution functions
denoted by FA and Fs respectively. (In. general, FA and Fs would be
determined by collecting data from the system of interest and then fitting
distributions to these data using the techniques). At time eo = 0 the status of
the server is idle, and the time t1 of the first arrival is determined by generating

4
A1 from FA and adding it to 0. The simulation clock is then advanced from eo
to the time of the next (first) event, e1 = t1. Since the customer arriving at time
t1 finds the server idle, she immediately enters server and has a delay in queue
of Dt = 0 and the status of the server is changed from idle to busy. The time,
c1, when the arriving customer will complete service is computed by
generating S1 froni Fs and adding it to t1. Finally, the time of the second
arrival, t2, is computed as t2 = t1 + A2, where A2 is generated from FA . If t2 < c1
as depicted in Fig. 1, the simulation clock is advanced from e1 to the time of
the next event, e2 = t2 (If c1 were less than t2 the clock would be advanced -
from e1 to c1). Since the customer arriving at time t2 finds the server already
busy, the immber of customers in the queue is increased from 0 to 1 and the
time of arrival of this customer is recorded; however, his service time S2 is not
generated at this time. Also, the time of the third arrival, t3 is computed as t3 =
t2 + A3. If c1 < t3, as depicted in the figure, the simulation clock is advanced
from e2 to the time of the next event, e3 = c1, where the customer completing
service departs, the customer in the queue (i.e. the one who arrived at time t2)
begins service and his delay in queue and service-completion time are
computed as D2 = c1 - t2 and c2 = c1 + S2 (S2 is now generated from Fs), and
the number of customers in the queue is decreased from 1 to 0. If t3 < c2 , the
simulation clock is advanced from e3 to the time of the next event, e4 = t3 , etc.
The simulation might eventually be tenninated when, say, the number of
customers whose delays have been observed reaches some specified value.

Figure 1. The next-event time-advance approach illustrated for the single-

server queueing system.

2. Components and Organization of a Discrete-Event Simulation Model

5
Although simulation has been applied to a great diversity of real-world
systems, discrete-event simulation models all share a number of common
components and there is a logical organization for these components that
promotes the coding, debugging, and future changing of a simulation model's
computer program. In particular, the following components will be found in
most discrete-event simulation models using the next-event time-advance
approach:

▪ System state: The collection of state variables necessary to describe the

system at a particular time.
▪ Simulation clock: A variable giving the current value of simulated time.
▪ Event list: A list containing the next time when each type of event will
occur.
▪ Statistical counters: Variables used for storing statistical information about
system performance.
▪ Initialization routine: A subprogram to initialize the simulation model at
time zero.
▪ Timing routine: A subprogram that determines the next event from the
event list and then advances the simulation clock to the time when that
event is to occur.
▪ Event routine: A subprogram that updates the system state when a
particular type of event occurs (there is one event routine for each event
type).
▪ Library routines: A set of subprograms used to generate random
observations from probability distributions that were determined as part of
the simulation model.
▪ Report generator: A subprogram that computes estimates (from the
statistical counters) of the desired measures of performance and produces a
report when the simulation ends.
▪ Main program: A subprogram that invokes the timing routine to determine
the next event and then transfers control to the corresponding event routine
to update the system state appropriately. The main program may also

6
 check for termination and invoke the report generator when the simulation
is over.

The logical relationships (flow of control) among these components is shown

in Fig. 2. The simulation begins at time 0 with the main program invoking the
initialization routine, where the simulation clock is set to zero, the system state
and the statistical counters are initialized, and the event list is initialized. After
control has been returned to the main program, it invokes the timing routine to
determine which type of event is most imminent. If an event of type i is the
next to occur, the simulation clock is advanced to the time that event type i
will occur and control is returned to the main program.men the main program
invokes event routine i, where typically three types of activities occur:

1) the system state is updated to account for the fact that an event of type
i has occurred;
2) information about system performance is gathered by updating the
statistical counters; and
3) the times of occurrence of future events are generated and this
information is added to the event list.

Often it is necessary to generate random observations from probability

distributions in order to determine these future event times; we will refer to
such a generated observation as a random variate. After all processing has
been completed, either in event routine i or in the main program, a check is
typically made to determine (relative to some stopping condition) if the
simulation should now be terminated. If it is time to terminate the simulation,
the report generator is invoked from the main program to compute estimates
(from the statistical counters) of the desired measures of performance and to
produce a report. If it is not time for termination, control is passed back to the
main program and the main program-timing routine-main program-event
routine-termination check cycle is repeated until the stopping condition is
eventually satisfied.

7
Before concluding this section, a few additional words about the system state
may be in order. A system is a well-defined collection of entities. Entities are
characterized by data values called attributes, and these attributes are part of
the system state for a discrete-event simulation model. Furthermore, entities
with some common property are often grouped together in lists (or files or
sets). For each entity there is a record in the list consisting of the entity's
attributes, and the order in which the records are placed in the list depends on
some specified rule. For the single-server queueing facility of Examples 1 and
2, the entities are the server and the customers in the facility. The server has
the attribute "server status" (busy or idle), and the custo·mers waiting in queue
have the attribute "time of arrival." . (The number of customers in the queue
might also be considered an attribute of the server.)

The organization and action of a discrete-event simulation program using the

next-event time-advance mechanism as depicted above .is fairly typical when
coding such simulations· in a general-purpose programming language such as
FORTRAN, Pascal, or C; it is called the event-scheduling approach to
simulation modeling, since the times of future events are explicitly coded into
the model and are scheduled to occur in the simulated future: It should be
mentioned here that there is an alternative approach to simulation modeling,
called the process approach, that instead views the simulation in terms of the
individual entities involved, and the code written describes the "experience" of
a "typical" entity as it "flows" through the system; coding simulations
modeled from the process point of view usually requires the use of special-
purpose simulation software. Even when taking the process approach,
however, the simulation is actually executed behind the scenes in the event-
scheduling logic as described above.

8
 Figure 2. Flow of control for the next-event time-advance approach

Sumber:

1. Law, A.M. and Kelton, W.D. (1991): Simulation Modeling And Analysis,
McGraw-Hill.