Last modified : March 20 1997

• Discrete Event Simulation
• DES : Uses
• DES Terminology
• A General Program
• Bank Example
• Links
• References
• Java Applet
• Web Page Creators

The purpose of Discrete Event Simulation (DES) is to simulate complex systems. Throughout the centuries, there have been books and papers published on this growing concept.

DES is used for large systems that change at discrete times.

1. A Bank :Customers are waiting in line for bank tellers. The use of DES in this situation is to figure out how many tellers to employ at certain hours in order that the wait of the customers is bearable. System changes occur when a person leaves the line to go to the first free teller.

2. Elevators: The system is programmed to make sure the elevators are running at different intervals. System changes occur when either a button is pressed or when the elevator stops.

3. Air Traffic Control

4 Car Traffic Simulation : The math involved is very complex due to the great amount of lights and streets connected. The whole city's system is organized by DES. Patriotic fact: The CRT at the University of Montreal is one of the world leaders in the study and simulation of transportation systems.

5. Billiard Balls + Bouncing Balls : A system changes when one ball hits an edge or another ball. Between these changes, the balls are at constant velocity. There are no outside forces except velocity. We assume a perfectly smooth surface. WARNING This pertains to our assignment.

Simulation of how heavenly bodies and planets go around each other.

In this kind of system, one uses continous time simulation by using deltas (difference in time). Astrophysicists observe the motions of the heavenly bodies to calculate the forces acting upon them, and infer where the heavenly bodies would be at delta time later. Continous time simulation is often for systems whose behaviour is described by differential equations.

Initialize (State)

Time <= 0

Initialize (Future.Event.Set)

Future Event Set:

*subset of all future events

*next event must be included

While not empty (Future Event Set) do

- Event <= next event (Future Event Set) // Delete_Min operation

- Time <= Time (Event) // no delta’s; time moves discretely

- State <= function of old state and event // updating the state

// you may put new events in Future Event Set - insert

An example of a Future Event Set :

Customers arrive at the bank at random times. There is a queue of people waiting to be served by the first available teller. At this time, there are 5 tellers serving the customers. The tellers take customers from the queue as soon as they are free. The frustration time is the time that the customer has to wait in the queue.

Application : Compute the average length of time a bank customer has to wait for a teller as a function of the number of tellers.

Once the out times have been calculated, you can find worst time, shortest time, average time, etc.

The front points to the person in the front of the line, and rear points to the person at the end of the line.

State : A record of

(1) an array of persons

(2) a pair in the Queue

(3) an array of tellers

Event : Consists of a record of

(1) Time

(2) Person (int)

Type of Event :

0 - arrival : person (int) arrives at this time

1 - departure from teller 1

2 - departure from teller 2

3 - departure from teller 3

4 - departure from teller 4

5 - departure from teller 5

Update of State

TIME <= time[event]
p <= person[event]
TYPE <= type_of_event
case TYPE = 0 (arrival)
(1) insert (p+1, Arrival_Time (p+1), 0)	// insert into the future event set
(2) if
|Queue| > 0, or if |Queue| = 0 and all tellers are busy:
=> Queue.rear <= Queue.rear + 1;
else
{insert (p, arrival time of (p) + service time (p), I)	// i is the first idle teller
teller [I] <= busy;

TYPE = i (i > 0)	// departure from teller i
(1) Out_Time (p) <= TIME
(2) if
|Queue| = 0 : teller [i] idle
else
q <= Queue_front;
Queue_front += 1;
Insert (q, TIME + Service_time (q), i)

• Introduction to Discrete Event Simulation
This link was found using a Net Search. This link was compiled at great expense by Peter Ball and was last modified October 21, 1996.
• Hints on making a Discrete Event Simulation program
This link was found using a Net Search. The author can be reached by e-mail at ingargiola@cis.temple.edu .
• A C++ Library for Discrete Event Simulation
This link was found using a Net Search. The authors are Dirk Bolier and Anton Eliens and was last updated Tuesday Oct 31, 1995.

• Birtwistle, G.M. Discrete Event Modelling on Simula . The
  Macmillan Press Ltd : London, 1979.
• Evans, John B. Structures of discrete event simulation : an introduction to the engagement strategy . Halsted Press : New York, 1988.
• Mitrani, I. Simulation techniques for discrete event systems .
  Cambridge University Press : New York, 1982.

This web page was created by :

• Barak Salvador Queija (A.K.A. El Diablo) (bqueij@po-box.mcgill.ca)
• Kishore Anand (anak@johnabbott.qc.ca )
• Laura Barile (laura@cs.mcgill.ca)
• Vida Dujmovic (vida@cs.mcgill.ca)

Barak typed out the html. Kishore and Vida wrote the Java Applet. Laura helped Barak with the html and helped Kishore and Vida in writing the applet. Kishore and Barak found the pictures. Barak , Kishore , and Laura found the links. The text is based on class notes taken by Barak , Laura , Vida, and Kishore. The figures were drawn with Windows Paint by Vida, and converted into a Gif using Graphics Workshop .

Fact of the lecture