程式扎記: [ Data Structures with Java ] Section 15.5 : Event-Driven Simulation

標籤

2011年3月7日 星期一

[ Data Structures with Java ] Section 15.5 : Event-Driven Simulation

Preface : 
A simulation creates a model of a real-world situation so that we can better understand it. The simulation uses computer objects with methods that model real-world objects and their behaviors. One very popular type of simulation is an event-driven simulation that uses a minimum priority queue to process events that occur over time. The priority queue consists of different types of event objects that are time-stamped to indicate when they are to occur. The simulation identifies an event, notes its time and circumstances, and adds it to the priority queue. Often, the occurrence of an event triggers other related and subsequent events which are added to the queue. The simulation runs by repeated removing and analyzing the next (earliest time) event from the priority queue until the queue is empty of a specified length of time elapses. The simulation provides a progression of discrete events that highlight the key activities in the real world situation. 
In the following sections, we will present design principles for all event-driven simulations and use a bank simulation as the example. Code segments that declare variables and implement key methods will aid our discussion.  

A Bank Simulation : 
In this section, we will describe a bank simulation that looks at the flow of customers through a bank as they are served by a group of tellers. In the process, we will measure the efficiency of service by computing the average waiting time of each customer and the percentage of time each teller is busy. Instead of collecting actual customer data, we introduce probabilistic values that describe different expected arrival rates for customers and different expected service times for a teller to handle a customer. We use a random number generator to mirror the arrival and departure of customers during a bank day. The simulation allows us to introduce new parameters and thus measure the relative effect on service if we change customer or teller behavior. For instance, suppose the bank estimates that a gift promotion would increase customer traffic by 20%. A simulation study would increase the expected arrival rate and measure the effect on waiting times and teller utilization. The result may indicate that customers experience unacceptable wait times, creating dissatisfaction that would diminish the effect of the promotion. The bank could repeat the simulation with additional tellers until reasonable wait times are established. 
The bank simulation produces arrival, service and departure events for each customer. Associated variables maintain an ongoing record of service time that each teller is committed to provide customers that are already in the bank. When a customer enters, the simulation creates an arrival event(A) that marks the time. This event spawns a service event(S) indicating when the customer reaches a teller. The time for the service event depends on prior teller commitments. If a teller is free, service begins immediately. Otherwise, the simulation must evaluate the backlogged service times for each teller and select the minimal value. In effect, the value represents the first time a teller is free. The interval between arrival time and service time denotes waiting time for the customer. The service event spawns a departure event that takes into account the time required by the teller to handle the customer. The service time becomes a further commitment for the teller and is used to update the backlogged service time for the teller, which could affect waiting times for subsequent customers. 
Below figure looks at four customers who enter a bank that employs two tellers. A time line lays out times for events from the start of the simulation, measured in minutes. The line segments above the timeline detail the events for each customer. The line segments below the timeline track service provided by each teller. 
 

Simulation Design Pattern : 
The key components of a simulation are events. These objects are instances of different types of activities and behaviors that occur in the simulation. The object type for the different events are part of an inheritance hierarchy that defines Event as a superclass. The Event class includes a single integer time, which denotes when the event occurs. An abstract method doEvent() is included for polymorphism. The method is overwritten in each subclass to carry out our tasks each time a specific event occurs. The Event superclass implements the Comparable interface by having compareTo() compare the relative times when two events occur. This allows the simulation to store events in a minimum priority queue. The simulation runs by extracting events from the priority queue in order of their times. The simulation is thus like a compressed video recording of a day's activities in which successive frames in the video are the events : 

- Event.java :
  1. package DSwJ.S15.apps;  
  2.   
  3. public abstract class Event implements Comparable{  
  4.     protected int time;  
  5.     public Event(int t) {  
  6.         time = t;  
  7.     }  
  8.   
  9.     abstract void doEvent();  // describes activity  
  10.     public int compareTo(Event e) {  
  11.         if(time > e.time)  
  12.             return -1;  
  13.         else if(time == e.time)  
  14.             return 0;  
  15.         else  
  16.             return 1;  
  17.     }  
  18.     public int getTime(){return time;}  
  19. }  

In our example, the inheritance hierarchy includes the Event superclass and subclasses for ArrivalEvent, ServiceEvent and DepartureEvent. 
The actual running of the simulation is handled by an EventDrivenSimulation class, which provides a priority queue of Event references. The class features the method pushEvent(), which inserts a new event in the priority queue and the method run() which proceeds to empty the queue in a progressive time sequence of events. Each event that is popped from the queue is processed using doEvent(). 

- EventDrivenSimulation.java :
  1. package DSwJ.S15.apps;  
  2.   
  3. import DSwJ.S15.OrderedPQueue;  
  4.   
  5. public class EventDrivenSimulation {  
  6.     private int finishTime=1;  
  7.       
  8.     private OrderedPQueue eventQueue =   
  9.         new OrderedPQueue();  
  10.       
  11.     public void pushEvent(Event e) {  
  12.         eventQueue.push(e);  
  13.     }  
  14.       
  15.     public void run() {  
  16.         while(!eventQueue.isEmpty()) {  
  17.             Event nextEvent = eventQueue.pop();  
  18.             nextEvent.doEvent();  
  19.             finishTime = nextEvent.getTime();  
  20.         }  
  21.     }  
  22.       
  23.     public int getFinishTime(){return finishTime;}  
  24. }  

BankSimulation Class : 
The BankSimulation class drives the bank simulation. By extending EventDrivenSimulation, it has access to the priority queue and the method run() in the superclass that processes events in a time sequence. BankSimulation defines user-supplied parameters that specify the length of the simulation, the number of tellers and the range (high-low) for expected arrival times and service times. The class defines variables that are updated during execution; for instance, number of customers and total wait time. It also supplies supporting variables such as a random number generator and an array of Teller objects. The method startSimulation() inputs parameters for the simulation and creates and stores events in the priority queue(Here is hard code). It then calls run() to execute the simulation and concludes by displaying a summary of the results : 

- BankSimulation.java :
  1. package DSwJ.S15.apps;  
  2.   
  3. import java.util.Random;  
  4.   
  5. public class BankSimulation extends EventDrivenSimulation {  
  6.     // parameters used to describe the simulation  
  7.     int simulationLength = 40;  
  8.     int numTellers = 3;  
  9.     int arrivalLow = 3, arrivalHigh = 6;  
  10.     int serviceLow = 15, serviceHigh = 20;  
  11.       
  12.     // variables used to monitor the simulation  
  13.     public int numCustomers = 0;  
  14.     public int totalWaitTime = 0;  
  15.     public int waitCount=0;  
  16.     int prevArrTime = 0;  
  17.       
  18.     public static boolean verboseRun = true;  
  19.     Random rnd = new Random();  
  20.     public static Teller[] tList = null;  
  21.       
  22.     public void startSimulation(){  
  23.         inputParameters();  
  24.         tList = new Teller[numTellers];  
  25.         for(int i=0; i
  26.             tList[i] = new Teller(serviceLow, serviceHigh, i+1);  
  27.         }  
  28.         int t=0;  
  29.         while(t < simulationLength) {  
  30.             t += randomTime(arrivalLow, arrivalHigh);  
  31.             if(t >= simulationLength) break;  
  32.             pushEvent(new ArrivalEvent(t, prevArrTime, this));  
  33.             prevArrTime = t;                          
  34.         }  
  35.         run();  
  36.         displayResults();  
  37.     }  
  38.       
  39.     public  int randomTime(int low, int high) {  
  40.         return arrivalLow + rnd.nextInt(arrivalHigh-arrivalLow+1);   
  41.     }  
  42.       
  43.     public void inputParameters(){}  
  44.     public void displayResults() {  
  45.         System.out.println("\t***Simulation Summary***");  
  46.         System.out.println("Number of customers is "+numCustomers);  
  47.         if(waitCount>0)System.out.printf("Average waiting time is %.1f minutes\n", totalWaitTime*1.0/waitCount);  
  48.         System.out.println("Service time for tellers: ");  
  49.         for(int i=0; i
  50.             System.out.print("  Teller "+i+": Service time="+tList[i].totalService);  
  51.             System.out.printf(" (Busy rage=%.1f%s)\n", tList[i].totalService*1.0/getFinishTime()*100"%");  
  52.         }  
  53.     }  
  54.     public static void main(String args[]) {  
  55.         BankSimulation bank = new BankSimulation();  
  56.         bank.startSimulation();  
  57.     }  
  58. }  

For whole source code, please refer to attachment(Including three event class). The execution result just like below : 

Customer #01 Arrival 5 and Wait 0
Customer #01 Begin service at 5 by teller 0 Service time 20
Customer #02 Arrival 9 and Wait 0
Customer #02 Begin service at 9 by teller 1 Service time 18
Customer #03 Arrival 15 and Wait 0
Customer #03 Begin service at 15 by teller 2 Service time 19
Customer #04 Arrival 21 and Wait 4
Customer #04 Begin service at 25 by teller 0 Service time 17
Customer #01 Departs at 25 Served by teller 0
Customer #02 Departs at 27 Served by teller 1
Customer #05 Arrival 27 and Wait 0
Customer #05 Begin service at 27 by teller 1 Service time 20
Customer #06 Arrival 32 and Wait 2
Customer #06 Begin service at 34 by teller 2 Service time 17
Customer #03 Departs at 34 Served by teller 2
Customer #07 Arrival 35 and Wait 7
Customer #08 Arrival 39 and Wait 8
Customer #07 Begin service at 42 by teller 0 Service time 18
Customer #04 Departs at 42 Served by teller 0
Customer #08 Begin service at 47 by teller 1 Service time 19
Customer #05 Departs at 47 Served by teller 1
Customer #06 Departs at 51 Served by teller 2
Customer #07 Departs at 60 Served by teller 0
Customer #08 Departs at 66 Served by teller 1
***Simulation Summary***
Number of customers is 8
Average waiting time is 5.3 minutes
Service time for tellers:
Teller 0: Service time=55 (Busy rage=83.3%)
Teller 1: Service time=57 (Busy rage=86.4%)
Teller 2: Service time=36 (Busy rage=54.5%)

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!