McGill University :
School of Computer Science
Winter 1997 Class Notes for 308-251B

DATA STRUCTURES AND ALGORTITHMS

Topic # 17: DISCRETE EVENT SIMULATION (DES)

Last modified : March 20 1997


For you lazy people

A quick link to the subtitles of our page


Discrete Event Simulation: The Purpose

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: Uses

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

Examples

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.

What it won't work for

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

A picture of our solar system

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.


DES Terminology

State of a System : All variables that describe a system
Event : Causes a change
ex. Billiard balls are set in motion. A change in velocity of any of the balls due to collisions with each other or the side of the table constitutes an event .


A General Program

Initialize (State)
Time <= 0
Initialize (Future.Event.Set)
Future Event Set
Future Event Set:
*subset of all future events
*next event must be included

The Execution

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 :

You are at a traffic light, and travelling at constant velocity. The timing of the light switches is known. Then it is possible to calculate when the next traffic light will be hit, by putting it in the Future Event Set. Events come out in sequence, i.e. in the proper order.


Bank Example

A picture of the Bank of Canada A picture of shiny happy customers in a 
queue in a bank
We would like to thank Linda Reid and her employees at the Bank of Montreal, Baie D'Urfe for allowing us to take a picture.

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.

Arrival time : The arrival time is the exact moment when the customer steps his foot into the opening of the bank.
Service time : The service time is the time a customer spends with a teller.
Out time : The out time is the exact moment when the customer steps his foot outside the bank

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

State
Persons Arrival Time Service Time Out Time Teller
1 Given Given Unknown Not Required
2 Given Given Unknown Not Required
3 Given Given Unknown Not Required
4 Given Given Unknown Not Required
5 Given Given Unknown Not Required
6 Given Given Unknown Not Required

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

Ex.
Queue : (front, rear) (3 , 5)

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

Tellers
1 2 3 4 5
Busy Idle Idle Idle Busy

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
We assume that there is no time lapse between a person leaving a teller and the next person in line visiting that teller.

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)


Links


References


Java Applet

To our beautiful Java Applet

Web page creators

This web page was created by :

If you have found any errors, or just wish to contact us to say hello, please feel free to write us to the addresses above.

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

In some banks, there are infrared scanners at each teller, telling them how long a customer is being served. There used to be also scanners in the queues, but they have removed them because they were not accurate.


Next time that you are in the bank, and you are waiting in line, and you're frustrated because you’ve been in line for a half an hour, go up to the teller and demand to see the manager. When the bank manager comes, tell him that he didn't learn his Discrete Event Simulation, and to visit our site to learn more about this important subject. Last updated March 11, 1997 by Barak Salvador Queija.

Copyright © 1997, Barak Salvador Queija, Kishore Anand, Laura Barile, Vida Dujmovic(Try saying her last name ten times fast). All rights reserved. Reproduction of all or part of this work is permitted for educational or non commercial research use provided that this copyright notice is included in any copy. If you wish to use the applet for commercial purposes, send a bag of money to the creators. Disclaimer : this collection of notes is experimental, and does not serve as-is as a substitute for attendance in the actual class.