Module 8: Next-Event Simulation

Let's now understand the details using an example:

• First consider interarrivals:

  

  • Let rv \(A_i\) denote the \(i\)-th interarrival.
  • Since all the \(A_i\)'s have the same distribution \(\expt{A_i} = \expt{A_j}\) for any \(i\) and \(j\).
              \(\Rightarrow\) We'll use \(\expt{A}\) for the mean interarrival time.
  • Suppose our random interarrival generator happens to produce the particular values \(0.9, 1.4, 1.87, 4.8\) as the first four interarrivals.
  • Let \(a_1=0.9, a_2=1.4, a_3=1.87, a_4=4.8\).
              \(\Rightarrow\) Here, \(a_i\) = the actual value produced by the generator for the \(i\)-th interarrival.
  Exercise 3: Add code in method randomInterarrivalTime() in Queue.java to estimate the average interarrival time. What does this number have to do with the value of variable arrivalRate in the program?

• Next, consider the (random) service time needed by these customers:
  • Let rv \(S_i\) represent the service time needed by the \(i\)-th customer
              \(\Rightarrow\) \(S_i\) = \(i\)-th service time.
  • As with the mean interarrival time, we'll let \(\expt{S}\) denote the mean service time.
  • As an example, the random generator for service times could produce: \(2.3, 2.11, 1.68, 1.3\) as the first four service times.
  • Let \(s_1=2.3, s_2=2.11, s_3=1.68, s_4=1.3\).
              \(\Rightarrow\) Here, \(s_i\) = the actual value produced by the generator for the \(i\)-th service time.
  Exercise 4: Add code in method randomServiceTime() in Queue.java to estimate the average service time.

• Now let us plot the departures along the time-line:

  

  • First, notice that customer 1's service begins at 0.9
              \(\Rightarrow\) It can't start earlier because customer 1 hasn't arrived yet!
  • Thus, the first departure occurs at \(t = 0.9 + 2.3 = 3.2\).
  • Since customer 2 arrives before customer 1 finishes, customer 2's service begins at \(t = 3.2\) and ends at \(t = 3.2 + 2.11 = 5.31\).
  • Note: since customer 3 finishes before customer 4 arrives, we start customer 4's service at \(t = 8.97\).
              \(\Rightarrow\) Customer 4 departs at \(t = 8.97 + 1.3 = 10.27\).

• We'll now plot the number in the system against time:

  

  • The number increases by one at each arrival, and decreases by one at each departure.
  • A contiguous block when the server is busy is called a busy period.
  Exercise 5: Suppose five customers arrived with interarrivals \(a_1=1.0, a_2=2.0, a_3=1.0, a_4=1.5, a_5=3.5\) with service times \(s_1=1.1, s_2=3.5, s_3=1.5, s_4=2.5, s_5=2.0\). For this data, draw the above graph that plots the number in the system against time.

• If we were to advance the clock in fixed, small steps, it might look like this:

  

  • The smaller the increment, the more the computation.
  • Notice that no change occurs in most time slices.

• In a next-event simulation, we will advance the clock only at event occurence times:

  

There are two key ideas in next-event simulation. Let's explore these using our queue example:

• The first idea: because the clock advances from event to event, the main loop of a simulation involves event-processing:

       while not over 
           event = getNextEvent ()        // Get the next event (from some data structure).
           clock = event.time             // Advance the clock to the next event's time of occurence.
           handleEventDetails (event)     // Update simulation variables of interest.
       endwhile
       

• In more detail, the first idea would look like this:

       // Generate all the arrival times
       for i=1 to numArrivals
           ai = randomInterrival ()
           arrivalList.add (ai)
       endfor
  
       // Generate all the service times
       for i=1 to numArrivals
           si = randomServiceTime ()
           serviceTimeList.add (si)
       endfor
       
       // Now simulate.
       while not over 
           event = getNextEvent ()        // This method will use arrivalList and serviceList.
           clock = event.time     
           handleEventDetails (event)     
       endwhile
          

  For large simulations (millions of events), this incurs a large storage cost.

• The second (better) idea: we do not need to have all events generated ahead of time.
  • Observe that we don't need to generate events until they're needed.
              \(\Rightarrow\) We'll generate as we go.
  • Thus, in pseudocode:

         while not over 
             event = getNextEvent ()
             clock = event.time     
             if event.type = arrival
                 handleArrival (event)
                 generateNextArrival ()      // Here's where the next ai is generated.
             else
                 handleDeparture (event)
                 generateNextDeparture ()    // Generate the next si.
             endif
         endwhile
            

Where are events stored?

• We will need a data structure to store events
            \(\Rightarrow\) For now, we will call this the event-list.

• Thus the method call

           event = getNextEvent ()
       

  should return the next event from this list.

• But which event?
            \(\Rightarrow\) The event with the earliest time.

• A data structure that maintains order and returns the least value is called a priority queue.

• Thus, Java code for a queue simulation might look like this:

  public class Queue {
  
      // List of forthcoming events.
      PriorityQueue<Event> eventList;
  
      // The system clock, which we'll advance from event to event.
      double clock;
  
      void simulate (int maxCustomers)
      {
          init ();                                     // Initialize stats variables.
  
          // Simulate for a given max # of customers.
          while (numCustomers < maxCustomers) {
              Event e = eventList.poll ();             // Remove event with earliest time.
              clock = e.eventTime;                     // Advance the clock. 
              if (e.type == Event.ARRIVAL) {           // Handle the event details.
                  handleArrival (e);
              }
              else {
                  handleDeparture (e);
              }
          }
  
          stats ();                                    // Print stats like "avg wait time"
      }
  }
       

Event handling details:

• First, let's ask what we need to do when an arrival occurs:
  • If the waiting area already has customers
              \(\Rightarrow\) Add new customer to waiting area.
  • If, instead, the server is available
              \(\Rightarrow\) Schedule the completion of service (departure).
  • In either case, schedule the next arrival
              \(\Rightarrow\) Create a random interarrival, add the clock and put that arrival into the event list.

• Thus, our Java code would look like:

      void handleArrival (Event e)
      {
  	numCustomers ++;
  	if ( ... ) {  // This is the only customer => schedule a departure.
              // Create a random service time, put the event on the event list.
  	    scheduleDeparture ();
  	}
          // Schedule the next arrival: create a random arrival time etc.
  	scheduleArrival ();
      }
       

• What happens with a service completion?
  • If there aren't any more customers
              \(\Rightarrow\) Nothing to be done.
  • If there are more customers waiting
              \(\Rightarrow\) Schedule the service of the one waiting longest.

• Thus, in Java

      void handleDeparture (Event e)
      {
  	numDepartures ++;
          if ( ... )  { // If there are more waiting customers
              // Create a random service time, put the event on the eventlist.
  	    scheduleDeparture ();
          }
      }
      

The other important data structure:

• Consider how we estimate a customer's system time:

  

  • When customer 3 leaves, we need to know the arrival time for that customer
              \(\Rightarrow\) Need to store this somewhere.
  • Then compute
              Customer 3's time in system = departureTime - arrivalTime

• But where do we store each customer's arrival time?
  • One option: a simple list that stores the arrival time for each customer.
  • Note: once a customer departs, we don't need the arrival time anymore.
              \(\Rightarrow\) Can remove that customer from data structure.
              \(\Rightarrow\) Only currently waiting or serviced customers in data structure.
  • Notice the operations: add and remove
  • Add operation: when a newly arriving customer is processed.
  • Remove operation: when departing customer is processed.

• Thus, what we need is a queue (the data structure, that is).

  

• At arrival time,

      void handleArrival (Event e)
      {
  	numCustomers ++;
          Customer c = new Customer ();
  	queue.add (c);                      // Add the new customer.
  	if (queue.size() == 1) {            // Is this the only customer in the system?
  	    scheduleDeparture ();           // Schedule this "only" person's service completion.
  	}
  	scheduleArrival ();                 
      }
       

• When handling a departure ...

      void handleDeparture (Event e)
      {
  	numDepartures ++;
  	Customer c = queue.removeFirst ();
  
          // This is the time from start to finish for this customer:
          double timeInSystem = clock - c.arrivalTime;
  
          // Maintain total (for average, to be computed later).
  	totalSystemTime += timeInSystem;
  
  	if (queue.size() > 0) {           // Is there a waiting customer?
  	    scheduleDeparture ();         // If so, schedule a departure.
  	}
      }
      

We're now in a position to examine a complete simulation:

• First, in pseudocode

       Algorithm: simulate (M)
       Input: M - maximum number of arrivals
       1.   initialize stats, queue, eventList;
       2.   while numArrivals < M
       3.       event = getNextEvent ()
       4.       clock = event.time     
       5.       if event.type = arrival
       6.           handleArrival (event)
       7.       else
       8.           handleDeparture (event)
       9.       endif
       10.  endwhile
       11.  print stats
  
  
       Method: handleArrival (e)
       Input:  event e
       1.  numArrivals = numArrivals + 1
       2.  c.arrivalTime = clock
       3.  queue.add (c)
       4.  if queue.size = 1
       5.      scheduleDeparture ()
       6.  endif
       7.  scheduleArrival ()
       
  
       Method: handleDeparture (e)
       Input:  event e
       1.  c = queue.remove ()
       2.  updateStats (clock - c.arrivalTime)
       2.  if queue.size > 0
       3.      scheduleDeparture ()
       4.  endif
       

• The Java version is not very different: (source file)

  public class Queue {
  
      // A data structure to store customers.
      LinkedList<Customer> queue;
  
      // A data structure for simulation: list of forthcoming events.
      PriorityQueue<Event> eventList;
  
      // The system clock, which we'll advance from event to event.
      double clock;
  
      void init ()
      {
          queue = new LinkedList<Customer> ();
          eventList = new PriorityQueue<Event> ();
          clock = 0.0;
          // Important: we need to start by scheduling the first arrival.
          scheduleArrival ();
      }
  
      void simulate (int maxCustomers)
      {
          init ();
  
          while (numArrivals < maxCustomers) {
              Event e = eventList.poll ();
              clock = e.eventTime;
              if (e.type == Event.ARRIVAL) {
                  handleArrival (e);
              }
              else {
                  handleDeparture (e);
              }
          }
  
          stats ();
      }
  
  
      void handleArrival (Event e)
      {
  	numArrivals ++;
  	queue.add (new Customer (clock));
  	if (queue.size() == 1) {
  	    // This is the only customer => schedule a departure.
  	    scheduleDeparture ();
  	}
  	scheduleArrival ();
      }
  
  
      void handleDeparture (Event e)
      {
  	numDepartures ++;
  	Customer c = queue.removeFirst ();
  
          // This is the time from start to finish for this customer:
          double timeInSystem = clock - c.arrivalTime;
  
          // Maintain total (for average, to be computed later).
  	totalSystemTime += timeInSystem;
  
  	if (queue.size() > 0) {
  	    // There's a waiting customer => schedule departure.
  	    scheduleDeparture ();
  	}
      }
  
  }
      

• The code for each event and customer is simple:

  class Customer {
      double arrivalTime;
      public Customer (double arrivalTime)
      {
          this.arrivalTime = arrivalTime;
      }
  }
  
  
  
  class Event implements Comparable {
  
      public static int ARRIVAL = 1;
      public static int DEPARTURE = 2;
      int type = -1;                     // Arrival or departure.
      double eventTime;                  // When it occurs.
  
      public Event (double eventTime, int type)
      {
  	this.eventTime = eventTime;
  	this.type = type;
      }
  
      public int compareTo (Object obj)         // This is needed to make events Comparable.
      {
          Event e = (Event) obj;
          if (eventTime < e.eventTime) {
              return -1;
          }
          else if (eventTime > e.eventTime) {
              return 1;
          }
          else {
              return 0;
          }
      }
  
  }
      

What do we want to get out of the simulation?

• First, let's examine the time-in-system:
  • This is the time from arrival to departure (including service).

    

  • Let rv \(D_i\) represent customer \(i\)'s time spent in the system.
  • We want to estimate $$ \frac{1}{n} \sum_i D_i $$
  • Notice where we accumulate such values in method handleDeparture:

        void handleDeparture (Event e)
        {
    	numDepartures ++;
    	Customer c = queue.removeFirst ();
    
            // This is the time from start to finish for this customer:
            double timeInSystem = clock - c.arrivalTime;
    
            // Maintain total (for average, to be computed later).
    	totalSystemTime += timeInSystem;
    
            // ...
        }       
            

  • Then, later we estimate

        void stats ()
        {
            // ...
    
    	avgSystemTime = totalSystemTime / numDepartures;
        }
            

  Exercise 7: Execute Queue.java to estimate the average time in system.

• Next, consider the time spent in the waiting area:
  • Let rv \(W_i\) represent customer \(i\)'s waiting time (waiting for service).
  • Notice that some customer's don't wait at all.
  • We want to estimate $$ \frac{1}{n} \sum_i W_i $$
  • Extracting waiting times needs a little thought:
              \(\Rightarrow\) We need to do this just before a customer enters service.
  • Notice where in the code this occurs:

        void handleDeparture (Event e)
        {
            // ...
    
    	if (queue.size() > 0) {
    
                // We can't yet remove this customer 
                // but we need to access this customer to extract the arrival time.
    	    Customer waitingCust = queue.get (0);
    
                // This is the time spent only in waiting:
                double waitTime = clock - waitingCust.arrivalTime; 
    
                // Accumulate total.
                totalWaitTime += waitTime;
    
                // ...
    	}
        }
             

  Exercise 8: Execute Queue.java to estimate the average waiting time. Subtract this from the estimate of the average system-time. What do you get? Is it what you expect?