(this simulation example is given in the carrano textbook, ch8.5p402) Simulation

Question

(this simulation example is given in the carrano textbook, ch8.5p402)
Simulation is a powerful tool for analysing, evaluating and comparing algorithms and different solution for many problems. The goal of a simulation system is to generate statistics that summarize the performance of a system or to predict the performance of a proposed system. As an example we look at a simulation of the behavior of a bank. The aim of the simulation system is to predict waiting times for customers. We will use the so called event driven simulation.
Event-driven simulation: Simulated time is advanced to the time of the next event Events are generated by a mathematical models based on statistics and probability.
A time-driven simulation: Simulated time is advanced by a single time unit. The time of an event, such as an arrival or departure, is determined randomly and compared with a simulated clock.
Generating events events to reflect the real world is a difficult problem that requires a bit of mathematical sophistication. For our purposes we will assume that the events are given to us in a text file describing customer arrivals and service times. For example the data

indicates that first customer arrives at time step 20, and that his transaction (once it begins) will require 5 minutes. The simulation system should read the arrival events described in this file and simulate the queueing system to find the departure events (when each customer will finish with their transaction) We will assume that the bank system only has one queue. Arrival events indicate the arrival at the bank of a new customer. These are external events: specified in an input file giving the times at which the arrival events occur. Departure events, indicate the departure from the bank of a customer who has completed a transaction. These are internal events: the simulation determines the times at which the departure events occur
An event list is needed to implement an event-driven simulation. An event list: (1) Keeps track of arrival and departure events that will occur but have not occurred yet and (2) Contains at most one arrival event and one departure event. The main task of the simulation algorithm is to determine when events occur and to process the events when they do occur. Roughly this is what we do:

In a time-driven simulation we would increase time by one step (such a simulation would be useful if the arrival and/or departure/transaction events were generated randomly according to some distribution). In an event driven simulation we can advance time directly to the time of the next event. Here is the pseudo-code:

In order to determine the time of the next event we can maintain an event list that contains all arrival and departure events that will occur. The event list is sorted by time.
arriving customers are added to a queue. We need to store for each customer the time of arrival and the transaction time required. Processing events is as follows:

Putting everything together, the pseudo code for the simulation is as follows:

Explanation / Answer

// SimulationQueue.java

import java.util.Queue;
import java.util.List;
import java.util.LinkedList;
import java.util.Scanner;
import java.io.File;
import java.io.FileNotFoundException;

public class SimulationQueue {
    private String arrivalFilePath;
    private int currentTime;
   
    private class Event {
        private boolean arrival;
        private int start;
        private int span;
       
        public Event() {
            this.arrival = true;
            this.start = 0;
            this.span = 0;
        }
       
        public Event(boolean isArrival, int startTime, int span) {
            this.arrival = isArrival;
            this.start = startTime;
            this.span = span;
        }
       
        public int at() { return start; }
        public boolean isArrival() { return arrival; }
        public int duration() { return span; }
       
        public void getArrivalEvent(Scanner arrivalFile) {
            this.arrival = true;
            this.start = arrivalFile.nextInt();
            this.span = arrivalFile.nextInt();
        }
    }
   
    public SimulationQueue(String arrivalFilePath) {
        this.arrivalFilePath = arrivalFilePath;
        this.currentTime = 0;
    }
   
    private void addEventToList(Event event, List<Event> eventList) {
        if (eventList.isEmpty()) eventList.add(0, event);
        else if (eventList.get(0).at() < event.at()) eventList.add(event);
        else eventList.add(0, event);
    }
   
    public void simulate() throws FileNotFoundException {
        Queue<Event> bankQueue = new LinkedList<Event>();
        List<Event> eventList = new LinkedList<Event>();
        Scanner arrivalFile = new Scanner(new File(arrivalFilePath));
        Event newEvent = new Event();
        newEvent.getArrivalEvent(arrivalFile);
        addEventToList(newEvent, eventList);
       
        while (!eventList.isEmpty()) {
            newEvent = eventList.get(0);
            if (newEvent.isArrival()) {
                System.out.printf("Arrival at %d ", newEvent.at()); //comment out this line to turn off console messages
                processArrival(newEvent, arrivalFile, eventList, bankQueue);
            } else {
                System.out.printf("Departure at %d ", newEvent.at()); //comment out this line to turn off console messages
                processDeparture(newEvent, eventList, bankQueue);
            }
        }
    }
   
    private void processArrival(Event newEvent, Scanner arrivalFile, List<Event> eventList, Queue<Event> bankQueue) {
        boolean atFront = bankQueue.isEmpty();
        bankQueue.add(newEvent);
        eventList.remove(0);
        if (currentTime < newEvent.at()) currentTime = newEvent.at();
       
        if (atFront) {
            addEventToList(new Event(false, currentTime+newEvent.duration(), 0), eventList);
        }
       
        if (arrivalFile.hasNext()) {
            Event event = new Event();
            event.getArrivalEvent(arrivalFile);
            addEventToList(event, eventList);
        }
    }
   
    private void processDeparture(Event newEvent, List<Event> eventList, Queue<Event> bankQueue) {
        bankQueue.remove();
        eventList.remove(0);
        if (currentTime < newEvent.at()) currentTime = newEvent.at();
       
        if (!bankQueue.isEmpty()) {
            if (currentTime < bankQueue.peek().at()) currentTime = bankQueue.peek().at();
            addEventToList(new Event(false, currentTime+bankQueue.element().duration(), 0), eventList);
        }
    }
   
   
    public static void main(String [] args) {
        SimulationQueue simulation = new SimulationQueue("arrival.txt");
        try {
            simulation.simulate();
        } catch (FileNotFoundException e) {
            System.out.println(e);
        }
    }
}

//proper indentation: http://ideone.com/LjmoWR

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.