Transcript Discrete Event Simulation

Discrete Event Simulation
CS1316: Representing
Structure and Behavior
Story


Discrete event simulation
•
Key ideas:
•
•
•

Simulation time != real time
A Queue
•
A Queue is a queue, no matter how implemented.
Different kinds of random
Straightening time
• Inserting it into the right place
• Sorting it afterwards
Building a discrete event simulation
•
Graphics as the representation, not the real thing: The
Model and the View
Imagine the simulation…

There are three Trucks that bring product from the
Factory.
•
•

We’ve got five Distributors who pick up product from the
Factory with orders.
•


On average, they take 3 days to arrive.
Each truck brings somewhere between 10 and 20
products—all equally likely.
Usually they want from 5 to 25 products, all equally likely.
It takes the Distributors an average of 2 days to get back
to the market, and an average of 5 days to deliver the
products.
Question we might wonder: How much product gets sold
like this?
Don’t use a Continuous
Simulation




We don’t want to wait that number of days in real time.
We don’t even care about every day.
•
There will certainly be timesteps (days) when nothing
happens of interest.
We’re dealing with different probability distributions.
•
Some uniform, some normally distributed.
Things can get out of synch
•
•
A Truck may go back to the factory and get more product
before a Distributor gets back.
A Distributor may have to wait for multiple trucks to fulfill
orders (and other Distributors might end up waiting in line)
We use a Discrete Event
Simulation


We don’t simulate every moment
continuously.
We simulate discrete events.
What’s the difference?
No time loop

In a discrete event simulation: There is
no time loop.
• There are events that are scheduled.
• At each run step, the next scheduled event
with the lowest time gets processed.
• The current time is then that time, the time that that
event is supposed to occur.

Key: We have to keep the list of
scheduled events sorted (in order)
What’s the difference?
Agents don’t act()

In a discrete event simulations, agents
don’t act().
• Instead, they wait for events to occur.
• They schedule new events to correspond to
the next thing that they’re going to do.

Key: Events get scheduled according to
different probabilities.
What’s the difference?
Agents get blocked


Agents can’t do everything that they want to do.
If they want product (for example) and there isn’t any,
they get blocked.
•

Many agents may get blocked awaiting the same
resource.
•

They can’t schedule any new events until they get
unblocked.
More than one Distributor may be awaiting arrival of Trucks
Key: We have to keep track of the Distributors waiting in
line (in the queue)
Key Ideas



A Queue
•
A Queue is a queue, no matter how implemented.
Different kinds of random
Straightening time
•
•
Inserting it into the right place
Sorting it afterwards
Key idea #1:
Introducing a Queue

First-In-First-Out List
• First person in line is first person served
I got here
third!
This is the tail
of the queue
I got here
second!
I got here
first!
This is the
front or head
of the queue
First-in-First-out

New items only get added to the tail.

Items only get removed from the head.
• Never in the middle
I got here
third!
This is the tail
of the queue
I got here
second!
I got here
first!
This is the
front or head
of the queue
As items leave, the head shifts
I got here
third!
I got here
second!
This is the tail
of the queue
Now, this is
the front or
head of the
queue
I got here
first! AND
NOW I’M UP!
Served!
As new items come in, the tail
shifts
I got here
fourth!
Now, this is
the tail of the
queue
I got here
third!
I got here
second!
Now, this is
the front or
head of the
queue
What can we do with queues?




push(anObject): Tack a new object onto
the tail of the queue
pop(): Pull the end (head) object off the
queue.
peek(): Get the head of the queue, but
don’t remove it from the queue.
size(): Return the size of the queue
Building a Queue
> Queue line = new Queue();
> line.push("Fred");
> line.push("Mary");
> line.push("Jose");
> line.size()
3
Accessing a Queue
> line.peek()
"Fred"
> line.pop()
"Fred"
> line.peek()
"Mary"
> line.pop()
"Mary"
> line.peek()
"Jose"
> line.pop()
"Jose"
> line.pop()
java.util.NoSuchElementException:
We don’t really
want to peek()
or pop() an
empty queue,
so we should
probably check
its size first.
Building a
Queue
import java.util.*; // LinkedList representation
/**
* Implements a simple queue
**/
public class Queue {
/** Where we'll store our elements */
public LinkedList elements;
/// Constructor
public Queue(){
elements = new LinkedList();
}
Queue methods
/// Methods
/** Push an object onto the Queue */
public void push(Object element){
elements.addFirst(element);
}
/** Peek at, but don't remove, top of queue */
public Object peek(){
return elements.getLast();}
/** Pop an object from the Queue */
public Object pop(){
Object toReturn = this.peek();
elements.removeLast();
return toReturn;
}
/** Return the size of a queue */
public int size() { return elements.size();}
We’re using a linked
list to implement the
Queue.
The front of the
LinkedList is the tail.
The last of the
LinkedList is the
head.
A queue is a queue, no matter
what lies beneath.

Our description of the queue minus the
implementation is an example of an abstract
data type (ADT).
•

An abstract type is a description of the methods that a
data structure knows and what the methods do.
We can actually write programs that use the
abstract data type without specifying the
implementation.
•
•
There are actually many implementations that will
work for the given ADT.
Some are better than others.
Array-oriented Queue
/**
* Implements a simple queue
**/
public class Queue2 {
private static int ARRAYSIZE = 20;
/** Where we'll store our elements */
private Object[] elements;
/** The indices of the head and tail */
private int head;
private int tail;
Queue = array + head index +
tail index
/// Constructor
public Queue2(){
elements = new Object[ARRAYSIZE];
head = 0;
tail = 0;
}
Queue2
methods
As the queue gets
pushed and
popped, it moves
down the array.
/** Push an object onto the Queue */
public void push(Object element){
if ((tail + 1) >= ARRAYSIZE) {
System.out.println("Queue underlying implementation
failed");
}
else {
// Store at the tail,
// then increment to a new open position
elements[tail] = element;
tail++; } }
/** Peek at, but don't remove, top of queue */
public Object peek(){
return elements[head];}
/** Pop an object from the Queue */
public Object pop(){
Object toReturn = this.peek();
if (((head + 1) >= ARRAYSIZE) ||
(head > tail)) {
System.out.println("Queue underlying implementation
failed.");
return toReturn;
}
else {
// Increment the head forward, too.
head++;
return toReturn;}}
/** Return the size of a queue */
public int size() { return tail-head;}
Same methods,
same behavior
But can only handle up
to 20 elements in the
queue! Less if pushing
and popping. Could shift
elements to always
allow 20.
Not as good an
implementation as the
linked list
implementation. (But
uses less memory.)
Welcome to DrJava.
> Queue2 line = new Queue2();
> line.push("Mary")
> line.push("Kim")
> line.push("Ron")
> line.peek()
"Mary"
> line.pop()
"Mary"
> line.peek()
"Kim"
> line.size()
2
> line.pop()
"Kim"
> line.pop()
"Ron"
Key idea #2:
Different kinds of random


We’ve been dealing with uniform random
distributions up until now, but those are
the least likely random distribution in real
life.
How can we generate some other
distributions, including some that are
more realistic?
Visualizing
a uniform
distribution
import java.util.*; // Need this for Random
import java.io.*; // For BufferedWriter
public class GenerateUniform {
public static void main(String[] args) {
Random rng = new Random(); // Random Number Generator
BufferedWriter output=null; // file for writing
// Try to open the file
try {
// create a writer
output =
new BufferedWriter(new FileWriter("D:/cs1316/uniform.txt"));
} catch (Exception ex) {
System.out.println("Trouble opening the file.");
}
// Fill it with 500 numbers between 0.0 and 1.0, uniformly
distributed
for (int i=0; i < 500; i++){
try{
output.write("\t"+rng.nextFloat());
output.newLine();
} catch (Exception ex) {
System.out.println("Couldn't write the data!");
System.out.println(ex.getMessage());
}
}
// Close the file
try{
output.close();}
catch (Exception ex)
{System.out.println("Something went wrong closing the file");}
By writing out a
tab and the
integer, we don’t
have to do the
string conversion.
}
}
How do we view a distribution?
A Histogram
Then graph the result
A Uniform Distribution
Frequency
70
60
50
40
Frequency
30
20
10
1
0.
8
0.
6
0.
4
0.
2
0
0
A Normal
Distribution
// Fill it with 500 numbers between -1.0 and 1.0, normally distributed
for (int i=0; i < 500; i++){
try{
output.write("\t"+rng.nextGaussian());
output.newLine();
} catch (Exception ex) {
System.out.println("Couldn't write the data!");
System.out.println(ex.getMessage());
}
}
Graphing the normal distribution
Frequency
30
25
20
15
Frequency
10
5
0
-2
.
-1
6
.
-1
2
.
-0
8
.
-0
4
0
4
0.
8
0.
2
1.
6
1.
2
The end aren’t
actually high—
the tails go
further.
How do we shift the distribution
where we want it?
// Fill it with 500 numbers with a mean of 5.0 and a
//larger spread, normally distributed
for (int i=0; i < 500; i++){
try{
output.write("\t"+((range * rng.nextGaussian())+mean));
output.newLine();
} catch (Exception ex) {
System.out.println("Couldn't write the data!");
System.out.println(ex.getMessage());
}
}
Multiply the random nextGaussian()
by the range you want, then add the
mean to shift it where you want it.
A new normal distribution
Frequency
18
16
14
12
10
8
6
4
2
0
10
9.5
9
8.5
8
7.5
7
6.5
6
5.5
5
4.5
4
3.5
3
2.5
2
1.5
1
0.5
0
-0.5
-1
-1.5
-2
Frequency
Key idea #3: Straightening Time

Straightening time

We’ll actually do these in reverse order:
• Inserting it into the right place
• Sorting it afterwards
• We’ll add a new event, then sort it.
• Then we’ll insert it into the right place.
Exercising
an EventQueue
public class EventQueueExercisor {
public static void main(String[] args){
// Make an EventQueue
EventQueue queue = new EventQueue();
// Now, stuff it full of events, out of order.
SimEvent event = new SimEvent();
event.setTime(5.0);
queue.add(event);
event = new SimEvent();
event.setTime(2.0);
queue.add(event);
We’re stuffing the EventQueue
with events whose times are out of
order.
event = new SimEvent();
event.setTime(7.0);
queue.add(event);
event = new SimEvent();
event.setTime(0.5);
queue.add(event);
event = new SimEvent();
event.setTime(1.0);
queue.add(event);
// Get the events back, hopefull in order!
for (int i=0; i < 5; i++) {
event = queue.pop();
System.out.println("Popped event
time:"+event.getTime());
}
}
}
If it works right, should look like
this:
Welcome to DrJava.
> java EventQueueExercisor
Popped event time:0.5
Popped event time:1.0
Popped event time:2.0
Popped event time:5.0
Popped event time:7.0
Implementing an EventQueue
import java.util.*;
/**
* EventQueue
* It's called an event "queue," but it's not really.
* Instead, it's a list (could be an array, could be a linked list)
* that always keeps its elements in time sorted order.
* When you get the nextEvent, you KNOW that it's the one
* with the lowest time in the EventQueue
**/
public class EventQueue {
private LinkedList elements;
/// Constructor
public EventQueue(){
elements = new LinkedList();
}
Mostly, it’s a queue
public SimEvent peek(){
return (SimEvent) elements.getFirst();}
public SimEvent pop(){
SimEvent toReturn = this.peek();
elements.removeFirst();
return toReturn;}
public int size(){return elements.size();}
public boolean empty(){return this.size()==0;}
Two options for add()
/**
* Add the event.
* The Queue MUST remain in order, from lowest time to
highest.
**/
public void add(SimEvent myEvent){
// Option one: Add then sort
elements.add(myEvent);
this.sort();
//Option two: Insert into order
//this.insertInOrder(myEvent);
}
There are lots of sorts!

Lots of ways to keep things in order.
• Some are faster – best are O(n log n)
• Some are slower – they’re always O(n2)
• Some are O(n2) in the worst case, but on
average, they’re better than that.

We’re going to try an insertion sort
How an insertion sort works


Consider the event at some position (1..n)
Compare it to all the events before that
position backwards—towards 0.
•
•

If the comparison event time is LESS THAN the
considered event time, then shift the comparison
event down to make room.
Wherever we stop, that’s where the considered event
goes.
Consider the next event…until done
Insertion
Sort
public void sort(){
// Perform an insertion sort
// For comparing to elements at smaller
indices
SimEvent considered = null;
SimEvent compareEvent = null; // Just for use
in loop
// Smaller index we're comparing to
int compare;
// Start out assuming that position 0 is "sorted"
// When position==1, compare elements at
indices 0 and 1
// When position==2, compare at indices 0, 1,
and 2, etc.
for (int position=1; position < elements.size();
position++){
considered = (SimEvent)
elements.get(position);
// Now, we look at "considered" versus the
elements
// less than "compare"
compare = position;
Trace this out to convince yourself it
works!
// While the considered event is greater than the
compared event ,
// it's in the wrong place, so move the
elements up one.
compareEvent = (SimEvent)
elements.get(compare-1);
while (compareEvent.getTime() >
considered.getTime()) {
elements.set(compare,elements.get(compar
e-1));
compare = compare-1;
// If we get to the end of the array, stop
if (compare <= 0) {break;}
// else get ready for the next time through
the loop
else {compareEvent = (SimEvent)
elements.get(compare-1);}
}
// Wherever we stopped, this is where
"considered" belongs
elements.set(compare,considered);
} // for all positions 1 to the end
} // end of sort()
Useful Links on Sorting



http://ciips.ee.uwa.edu.au/~morris/Year2/
PLDS210/sorting.html
http://www.cs.ubc.ca/spider/harrison/Jav
a/sorting-demo.html
http://www.cs.brockport.edu/cs/java/apps
/sorters/insertsort.html
This include simulations that help to
see how it’s all working
Option #2: Put it in the right
place
/**
* Add the event.
* The Queue MUST remain in order, from lowest time to
highest.
**/
public void add(SimEvent myEvent){
// Option one: Add then sort
//elements.add(myEvent);
//this.sort();
//Option two: Insert into order
this.insertInOrder(myEvent);
}
Again, trace it out to convince
yourself that it works!
insertInOrder()
/**
* Put thisEvent into elements, assuming
* that it's already in order.
**/
public void insertInOrder(SimEvent
thisEvent){
SimEvent comparison = null;
// Have we inserted yet?
boolean inserted = false;
for (int i=0; i < elements.size(); i++){
comparison = (SimEvent)
elements.get(i);
// Assume elements from 0..i are less than
thisEvent
// If the element time is GREATER,
insert here and
// shift the rest down
if (thisEvent.getTime() <
comparison.getTime()) {
//Insert it here
inserted = true;
elements.add(i,thisEvent);
break; // We can stop the search loop
}
} // end for
// Did we get through the list without
finding something
// greater? Must be greater than any
currently there!
if (!inserted) {
// Insert it at the end
elements.addLast(thisEvent);}
}
Finally: A Discrete Event
Simulation

Now, we can assemble queues, different
kinds of random, and a sorted
EventQueue to create a discrete event
simulation.
Running a DESimulation
Welcome to DrJava.
> FactorySimulation fs = new
FactorySimulation();
> fs.openFrames("D:/temp/");
> fs.run(25.0)
What we see (not much)
The detail tells the story
Time:
1.7078547183397625
Time:
1.7078547183397625
>>> Timestep: 1
Time:
1.727166341118611
Time:
1.727166341118611
>>> Timestep: 1
Time:
1.8778754913001443
Time:
1.8778754913001443
>>> Timestep: 1
Time:
1.889475045031698
Time:
1.889475045031698
>>> Timestep: 1
Time:
3.064560375192933
Time:
3.064560375192933
>>> Timestep: 3
Time:
3.444420374970288
Time:
3.444420374970288
Time:
3.444420374970288
>>> Timestep: 3
Time:
3.8869697922832698
Time:
3.8869697922832698
Time:
3.8869697922832698
>>> Timestep: 3
Distributor: 0
Distributor: 0
Arrived at warehouse
is blocking
Distributor: 3
Distributor: 3
Arrived at warehouse
is blocking
Distributor: 4
Distributor: 4
Arrived at warehouse
is blocking
Distributor: 2
Distributor: 2
Arrived at warehouse
is blocking
Distributor: 1
Distributor: 1
Arrived at warehouse
is blocking
Truck: 2
Arrived at warehouse with load
13
Distributor: 0
unblocked!
Distributor: 0
Gathered product for orders of
11
Truck: 0
Arrived at warehouse with load
18
Distributor: 3
unblocked!
Distributor: 3
Gathered product for orders of
12
How DESimulation works
Turtle
LinkedList
-heading
-XPos
-YPos
+forward()
+turn()
+setColor()
+setPenDown()
+frames
*
1
1
+init()
+die()
+getClosest()
+countInRange()
+act()
1
#output
*
#simulation
*
1
-blocked
-blocked
+isBlocked()
+isReady()
+validTime()
+waitFor()
+unblocked()
+processEvent()
-world
Simulation
Queue
DEAgent
+show()
+replay()
#agents
Agent
#speed
FrameSequence
+push()
+peek()
+pop()
+empty()
+size()
1
+getAgents()
+add()
+remove()
+openFrames()
+setUp()
+openFile()
+run()
+endStep()
+lineForFile()
+closeFile()
1
+setPicture()
1
EventQueue
*
-events
1
*
Resource
-amount
+amountAvailable()
+consume()
+add()
+addToList()
World
DESimluation
-now
+getTime()
+addEvent()
+log()
+run()
*
+peek()
+add()
+pop()
+size()
+empty()
+insertInOrder()
+sort()