Simulation engine
A discrete-event simulation is a simulation based on the idea that the process being simulated can be described as a series of discrete events, each occurring at a single point in time. Instead of advancing time in fixed increments, the simulation jumps from event to event. The following bits and pieces of java code show an easy way to implement this in Java.
The basic idea is very simple: first we define an Event interface, create some events and store them in an ordered queue. To start simulating all we have to do is take the first item off the list, update the simulation time to whatever time that event was supposed to occur, and call its fire() method to make things happen.
The Event Interface
An Event will be defined by the following interface:
/*
* Represents an event in the simulation
*/
public interface Event
{
/*
* 'Fires' IE executes the event
*/
public void fire();
}An event then, is anything that can be fired. Notably absent from this interval is the time the event occurs, instead of storing the absolute time in the event we will let the event queue (described below) handle the time events happen, making them re-usable throughout the simulation.
Because the Events are programmed in java anything can happen inside a fire() method. Including the scheduling of new events. To simulate a ten minute hair-drying process you define a StartDrying event and have its fire() method schedule a StopDrying event to be fired ten minutes later.
The Event Queue
The next things we need is a queue: a list of events and the times they occur. The following class represents a queue storing only future events, ordered ascendingly by the times they occur. This way, the next event is always the first element in the list. Adding new events is done using the schedule command which schedules an Event to happen delay seconds from now.
(By the way, when I say 'seconds' I mean 'units of simulation time'. In the hair-drying example it might be more convenient to let a unit of simulation time be a minute, or even a ten minute interval.)
Providing the list is kept ordered 'on the fly' the retrieval of the next Event object can always be done in O(1) time. This means that the time consuming part of the structure - keeping it ordered - is shifted to the schedule method. The code shown below uses a linked list structure to store events, with a pointer to the start and end of the lists. With these pointers inserting events at the start or end of the queue can be done in O(1) time.
The pointer to the last item in the list is especially useful when populating the list with a large number of events, say incoming calls in a call center, or goods arriving at a factory, before the simulation starts. Inserting any event in the middle of the queue can be done only in O(n) time, because of the need to keep the list ordered. Some increases in performances might be gained by testing if the event to be inserted is nearer to the first or last element and then searching from there, although because the time steps aren't fixed this doesn't guarantee anything. Possibly some more or less random pointers could be kept to other items in the list in order to find a good starting point.
The implentation shown here was designed explicitly to perform well after having been filled with a large number of initial events, each spaced apart about as far as the time of an average process. Under these circumstances the event scheduled during the simulation will always be closer to the start than the end of the list, so that the best starting point for the search is always the first item in the list.
public class EventQueue
{
/*
* Adds an event to the queue, to be fired after the given delay
*/
public void add(Event e, long delay)
{
long time = now + delay;
EventQueueItem newItem = new EventQueueItem(e, time);
if (first == null) {
// Empty queue
first = newItem;
last = newItem;
} else if (time >= last.time) {
// Add item to back of queue
last.right = newItem;
last = newItem;
} else if (time < first.time) {
// Add item to front of queue
newItem.right = first;
first = newItem;
} else {
// Find correct place in list & add
EventQueueItem item = first;
while (time > item.right.time) item = item.right;
newItem.right = item.right;
item.right = newItem;
}
}
/*
* Returns the next event, removing it from the queue
*/
public Event next()
{
Event e = first.event; // get first event
now = first.time; // advance simulation time
// set first to next item
first = (first.right == null) ? null : first.right;
return e;
}
/*
* Returns false only if the queue is empty.
*/
public boolean hasNext()
{
return (first != null);
}
/*
* Returns the current simulation time IE the time of the last event
*/
public long getTime()
{
return now;
}
private long now; // the current simulation time
private EventQueueItem first, last; // the first and last item in the queue
/*
* A small data holder class
*/
private class EventQueueItem
{
public EventQueueItem(Event event, long time)
{
this.event = event;
this.time = time;
}
public Event event;
public long time;
public EventQueueItem right;
}
}The only thing left to do at this point is retrieve the events from the queue and fire them. This is done using the Engine class shown below. This class also provides public access to the simulation time and the schedule method, making it the central hub of the simulation.
/**
* This is the main class in the program, it defines the structure of the model and starts
* processing events
* It has several static methods allowing other classes to queue events.
*/
public class Engine
{
public static void main(String[] args)
{
Engine.run()
}
/**
* Runs the simulation
*/
public static void run()
{
// Initialise
time = 0;
queue = new EventQueue();
// Create model here
// Create an event here, and add it to the queue
queue.add(new HelloWorldEvent(), 10);
// Start
Event e;
while (queue.hasNext()) {
e = queue.next();
time = queue.getTime()
e.fire();
}
// Post processing goes here
}
/**
* Provides public access to the current simulation time
*/
public static long getTime()
{
return time;
}
/**
* Schedule a new event
* @param e The event to schedule
* @param delay The delay (in seconds) after which the event should be fired
*/
public static void schedule(Event e, long delay)
{
queue.add(e, delay);
}
private static long time; // The simulation time
private static EventQueue queue; // The queue storing all future events
}And there you have it. Wheeee!
Jul 19th, 2008
Comments
michael wrote:
That's right, it's an interface. You got to define your own classes that implement the Event interface. You can read more about interfaces here: http://java.sun.com/docs/books/tutorial/java/concepts/interface.html
Jan 14th, 2009
moh wrote:
i put it in java put its not working
cz there is no ( class event)
Jan 14th, 2009
If you wish to add code to your comment you can use code tags, like this: <code class="php">yourCodeHere</code>.
Quite a large number of languages are supported, although I can't guarantee it'll be pretty. Inside the code tags you can use any characters except for the string "</code>".