Java-simulation-Events_Processes_Activities(1).pdf

(396 KB) Pobierz
Discrete Event Simulation in Java
Keld Helsgaun
E-mail: keld@ruc.dk
Department of Computer Science
Roskilde University
DK-4000 Roskilde, Denmark
Abstract
This report describes
javaSimulation
, a Java package for
process-based discrete event simulation. The facilities of the
package are based on the simulation facilities provided by the
programming language SIMULA. The design of the package
follows the SIMULA design very closely. The package is easy to
use and relatively efficient. In addition, Java packages for co-
routine sequencing, event-based simulation and activity-based
simulation are presented.
Keywords:
simulation, Java, process, discrete event, coroutine
1. Introduction
The Java platform comes with several standard packages. No package, how-
ever, is provided for discrete event simulation. This is unfortunate since dis-
crete event simulation constitutes an important application area of object ori-
ented programming. This fact has convincingly been demonstrated by
SIMULA, one of the first object-oriented programming languages [1][2][3].
SIMULA provides the standard class SIMULATION, a very powerful tool
for discrete event simulation. A simulation encompasses a set of interacting
processes.
A process is an object associated with a sequence of activities or-
dered logically in simulated time. Each process has its own life cycle and may
undergo active and inactive phases during its lifetime.
1
Processes represent the active entities in the real world, e.g., customers in a
supermarket. Thus, the process concept may be used to describe systems in a
natural way.
This report describes
javaSimulation
, a Java package for process-based
discrete event simulation. The package may be seen as an implementation of
class SIMULATION in Java. In addition to the simulation facilities, the pack-
age also includes the facilities for list manipulation and random number
drawing as found in SIMULA.
When designing the package, great emphasis has been put into following the
SIMULA design as closely as possible. The advantage of this approach is that
the semantics of facilities are well-known and thoroughly tested through
many years’ use of SIMULA. A SIMULA user should easily learn to use the
package.
The rest of this report is structured as follows.
Chapter 2 provides a short introduction to discrete event simulation by means
of a concrete example, a car wash simulation. The example is used to demon-
strate the use of three different approaches to discrete event simulation:
event-
based, activity-based
and
process-based.
In relation to these approaches sev-
eral packages have been developed. These packages are described from the
user’s point of view and their use is demonstrated by means of the car wash
example.
Implementing a process-based simulation package in Java is not a trivial task.
A process must be able to suspend its execution and have it resumed at some
later time. In other words, a process should be able to act like a coroutine.
Chapter 3 describes the development of a package,
javaCoroutine
, for
coroutine sequencing in Java. The package provides the same coroutine fa-
cilities as can be found in SIMULA. Its implementation is based on Java’s
threads.
This coroutine package is then used in Chapter 4 for the implementation of a
package for process-based simulation,
javaSimulation
.
javaSimulation
is evaluated in Chapter 5, and some conclusions are
made in Chapter 6.
The appendices contain Java source code and documentation.
2
2. Discrete event simulation in Java
Simulation may be defined as the experimentation with a model in order to
obtain information about the dynamic behavior of a system. Instead of ex-
perimenting with the system, the experiments are performed with a model of
the system. Simulation is typically used when experimentation with the real
system is too expensive, too dangerous, or not possible (e.g., if the real sys-
tem does not exist).
The system components chosen for inclusion in the model are termed
entities.
Associated with each entity are zero or more
attributes
that describe the state
of the entity. The collection of all these attributes at any given time defines the
system state
at that time.
There are three categories of simulation models, defined by the way the sys-
tem state changes:
•
Continuous:
the state varies continuously with time. Such systems are
usually described by sets of differential equations.
•
Discrete:
the state changes only at discrete instances of time (event times).
3
•
Combined continuous and discrete:
the state changes instantaneously at
event times; in between consecutive event times the system state may vary
continuously [4].
In this report we will only consider so-called
discrete event simulation.
In
discrete event simulation the model is discrete, and the simulated clock always
jumps from one event time to the most imminent event time. At each event
time the corresponding action (state change) is performed, and simulated time
is advanced to the next time when some action is to occur. Thus, discrete
event simulation assumes that nothing happens between successive state
changes.
In order to make the following description easier to comprehend, a concrete
simulation example will now be presented.
2 . 1 The car wash problem
This example has been taken from [1].
A garage owner has installed an automatic car wash that services cars one at a
time. When a car arrives, it goes straight into the car wash if this is idle; oth-
erwise, it must wait in a queue. The car washer starts his day in a tearoom
and return there each time he has no work to do. As long as cars are waiting,
the car wash is in continuous operation serving on a first-come, first-served
basis. All cars that have arrived before the garage closes down are washed.
Each service takes exactly 10 minutes. The average time between car arrivals
has been estimated at 11 minutes.
The garage owner is interested in predicting the maximum queue length and
average waiting time if he installs one more car wash and employs one more
car washer.
4
2 . 2 Three approaches for discrete event simulation
There are basically three approaches that can be used for discrete event simu-
lation: the
event-based,
the
activity-based
and the
process-based
approach [5].
(1) The event-based approach
In the event-based approach the model consists of a collection of events. Each
event models a state change and is responsible for scheduling other events
that depend on that event.
Each event has associated an event time and some actions to be executed
when the event occurs.
In the car wash problem the
arrival of a car
is an example of an event. Actions
associated with this event are the inclusion of the car into the waiting line and
the scheduling of the next car arrival.
Event-based simulation is the simplest and most common implementation
style of discrete event simulation because it can be implemented in any pro-
gramming language.
(2) The activity-based approach
In the activity-based approach the model consists of a collection of activities.
Each activity models some time-consuming action performed by an entity.
Each activity has associated a starting condition, some actions to be executed
when the activity starts, the duration of the activity, and some actions to be
executed when the activity finishes.
In the car wash problem the
washing of a car
is an example of an activity. The
condition for starting this activity is that one of car washers is idle and the
waiting line is not empty. When the activity starts, an idle car washer is re-
moved from the tearoom, and the first waiting car is removed from the wait-
ing line. The duration of the activity is 10 units of simulated time. When it
ends, the car washer is put back into the tearoom.
Whilst the activity approach is relatively easy to understand, it normally suf-
fers from poor execution efficiency compared to the event-based approach.
5

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin