Scribd Logo
Upload

Welcome to Scribd!

  • 115 views

    CS301 Lec10

    Uploaded by

    ism33
    The document describes a simulation of customer transactions at a bank with 4 tellers. In the simulation, customers arrive at certain times and require a certain duration to complete their transactions. If a teller is available, the customer is served immediately, otherwise they join the shortest queue. The simulation can be run using either timeline-based or event-based approaches. Event-based simulation maintains a priority queue of future arrival and departure events. The C++ code presented processes customers by adding arrival events to the queue and removing the next event to add customers to queues and track waiting times.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd

    CS301 Lec10

    Uploaded by

    ism33
    115 views33 pages
    The document describes a simulation of customer transactions at a bank with 4 tellers. In the simulation, customers arrive at certain times and require a certain duration to complete their transactions. If a teller is available, the customer is served immediately, otherwise they join the shortest queue. The simulation can be run using either timeline-based or event-based approaches. Event-based simulation maintains a priority queue of future arrival and departure events. The C++ code presented processes customers by adding arrival events to the queue and removing the next event to add customers to queues and track waiting times.

    Original Description:

    data structure

    Original Title

    CS301-lec10

    Copyright

    © © All Rights Reserved

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document describes a simulation of customer transactions at a bank with 4 tellers. In the simulation, customers arrive at certain times and require a certain duration to complete their transactions. If a teller is available, the customer is served immediately, otherwise they join the shortest queue. The simulation can be run using either timeline-based or event-based approaches. Event-based simulation maintains a priority queue of future arrival and departure events. The C++ code presented processes customers by adding arrival events to the queue and removing the next event to add customers to queues and track waiting times.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    115 views33 pages

    CS301 Lec10

    Uploaded by

    ism33
    The document describes a simulation of customer transactions at a bank with 4 tellers. In the simulation, customers arrive at certain times and require a certain duration to complete their transactions. If a teller is available, the customer is served immediately, otherwise they join the shortest queue. The simulation can be run using either timeline-based or event-based approaches. Event-based simulation maintains a priority queue of future arrival and departure events. The C++ code presented processes customers by adding arrival events to the queue and removing the next event to add customers to queues and track waiting times.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    of 33

    Lecture No.

    10
    Data Structures
    Dr. Sohail Aslam

    Simulation of a Bank
    A customer enters the bank at a specific
    time (t1) desiring to conduct a transaction.
    Any one of the four tellers can attend to
    the customer.
    The transaction (withdraw, deposit) will
    take a certain period of time (t2).
    If a teller is free, the teller can process the
    customers transaction immediately and
    the customer leaves the bank at t1+t2.

    Simulation of a Bank
    It is possible that none of the four tellers is
    free in which case there is a line of
    customers are each teller.
    An arriving customer proceeds to the back
    of the shortest line and waits for his turn.
    The customer leaves the bank at t2 time
    units after reaching the front of the line.
    The time spent at the bank is t2 plus time
    waiting in line.

    Simulation of a Bank
    teller 1

    teller 2

    teller 3

    teller 4

    Simulation of a Bank
    teller 1

    teller 2

    teller 3

    teller 4

    Simulation of a Bank
    teller 1

    teller 2

    teller 3

    teller 4

    Simulation of a Bank
    teller 1

    teller 2

    teller 3

    teller 4

    Simulation of a Bank
    teller 1

    teller 2

    teller 3

    teller 4

    Simulation of a Bank
    teller 1

    teller 2

    teller 3

    teller 4

    Simulation of a Bank
    teller 1

    teller 2

    teller 3

    teller 4

    Simulation Models
    Two common models of simulation are
    time-based simulation and event-based
    simulation.
    In time-based simulation, we maintain a
    timeline or a clock.
    The clock ticks. Things happen when the
    time reaches the moment of an event.

    Timeline based Simulation


    Consider the bank example. All tellers are free.
    Customer C1 comes in at time 2 minutes after
    bank opens.
    His transaction (withdraw money) will require 4
    minutes.
    Customer C2 arrives 4 minutes after the bank
    opens. Will need 6 minutes for transaction.
    Customer C3 arrives 12 minutes after the bank
    opens and needs 10 minutes.

    Timeline based Simulation


    Events along the timeline:
    Time (minutes)
    0

    C1 in

    10

    11

    12

    C1 out
    C2 in

    C2 out
    C3 in

    13

    14

    15

    Timeline based Simulation


    We could write a main clock loop as follows:
    clock = 0;
    while( clock <= 24*60 ) { // one day
    read new customer;
    if customer.arrivaltime == clock
    insert into shortest queue;
    check the customer at head of all four queues.
    if transaction is over, remove from queue.
    clock = clock + 1;
    }

    Event based Simulation


    Dont wait for the clock to tic until the next
    event.
    Compute the time of next event and
    maintain a list of events in increasing order
    of time.
    Remove a event from the list in a loop and
    process it.

    Event based Simulation


    Events
    Time (minutes)
    0

    C1 in

    10

    11

    12

    C1 out
    C2 in

    Event 1:
    Event 2:
    Event 3:
    Event 4:
    Event 5:

    C2 out

    2 mins
    4 mins
    6 mins
    10 mins
    12 mins

    C1 in
    C2 in
    C1 out
    C2 out
    C3 in

    C3 in

    13

    14

    15

    Event based Simulation


    Maintain a queue of events.
    Remove the event with the earliest time
    from the queue and process it.
    As new events are created, insert them in
    the queue.
    A queue where the dequeue operation
    depends not on FIFO, is called a priority
    queue.

    Event based Bank Simulation


    Development of the C++ code to carry out
    the simulation.
    We will need the queue data structure.
    We will need the priority queue.
    Information about arriving customers will
    be placed in an input file.
    Each line of the file contains the items
    (arrival time,transaction duration)

    Arriving Customers File


    Here are a few lines from the input file.
    00 30 10 <- customer 1
    00 35 05 <- customer 2
    00 40 08
    00 45 02
    00 50 05
    00 55 12
    01 00 13
    01 01 09
    00 30 10 means Customer 1 arrives 30 minutes after bank opens
    and will need 10 minutes for his transaction.
    01 01 09 means customer arrives one hour and one minute after
    bank opens and transaction will take 9 minutes.

    Simulation Procedure
    The first event to occur is the arrival of the
    first customer.
    This event placed in the priority queue.
    Initially, the four teller queues are empty.
    The simulation proceeds are follows:
    When an arrival event is removed from the
    priority queue, a node representing the
    customer is placed on the shortest teller
    queue.

    Simulation Procedure
    If that customer is the only one on a teller
    queue, a event for his departure is placed
    on the priority queue.
    At the same time, the next input line is
    read and an arrival event is placed in the
    priority queue.
    When a departure event is removed from
    the event priority queue, the customer
    node is removed from the teller queue.

    Simulation Procedure
    The total time spent by the customer is computed:
    it is the time spent in the queue waiting and the
    time taken for the transaction.
    This time is added to the total time spent by all
    customers.
    At the end of the simulation, this total time divided
    by the total customers served will be average time
    spent by customers.
    The next customer in the queue is now served by
    the teller.
    A departure event is placed on the event queue.

    Code for Simulation


    #include <iostream>
    #include <string>
    #include <strstream.h>
    #include
    #include
    #include
    #include

    "Customer.cpp"
    "Queue.h"
    "PriorityQueue.cpp"
    "Event.cpp"

    Queue q[4];
    // teller queues
    PriorityQueue pq; //eventList;
    int totalTime;
    int count = 0;
    int customerNo = 0;

    Code for Simulation


    main (int argc, char *argv[])
    {
    Customer* c;
    Event* nextEvent;
    // open customer arrival file
    ifstream data("customer.dat", ios::in);
    // initialize with the first arriving
    // customer.
    readNewCustomer(data);

    Code for Simulation


    while( pq.length() > 0 )
    {
    nextEvent = pq.remove();
    c = nextEvent->getCustomer();
    if( c->getStatus() == -1 ){ // arrival event
    int arrTime = nextEvent->getEventTime();
    int duration = c->getTransactionDuration();
    int customerNo = c->getCustomerNumber();
    processArrival(data, customerNo,
    arrTime, duration , nextEvent);
    }
    else { // departure event
    int qindex = c->getStatus();
    int departTime = nextEvent->getEventTime();
    processDeparture(qindex, departTime, nextEvent);
    }
    }

    Code for Simulation


    void readNewCustomer(ifstream& data)
    {
    int hour,min,duration;
    if (data >> hour >> min >> duration) {
    customerNo++;
    Customer* c = new Customer(customerNo,
    hour*60+min, duration);
    c->setStatus( -1 ); // new arrival
    Event* e = new Event(c, hour*60+min );
    pq.insert( e ); // insert the arrival event
    }
    else {
    data.close(); // close customer file
    }
    }

    Code for Simulation


    int processArrival(ifstream &data, int customerNo,
    int arrTime, int duration,
    Event* event)
    {
    int i, small, j = 0;
    // find smallest teller queue
    small = q[0].length();
    for(i=1; i < 4; i++ )
    if( q[i].length() < small ){
    small = q[i].length(); j = i;
    }
    // put arriving customer in smallest queue
    Customer* c = new Customer(customerNo, arrTime,
    duration );
    c->setStatus(j); // remember which queue the
    customer goes in
    q[j].enqueue(c);

    Code for Simulation


    // check if this is the only customer in the.
    // queue. If so, the customer must be marked for
    // departure by placing him on the event queue.
    if( q[j].length() == 1 ) {
    c->setDepartureTime( arrTime+duration);
    Event* e = new Event(c, arrTime+duration );
    pq.insert(e);
    }
    // get another customer from the input
    readNewCustomer(data);
    }

    Code for Simulation


    int processDeparture(
    int qindex, int departTime,
    Event* event)
    {
    Customer* cinq = q[qindex].dequeue();
    int waitTime = departTime - cinq->getArrivalTime();
    totalTime = totalTime + waitTime;
    count = count + 1;
    // if there are any more customers on the queue, mark
    the
    // next customer at the head of the queue for departure
    // and place him on the eventList.
    if( q[qindex].length() > 0 ) {
    cinq = q[qindex].front();
    int etime = departTime + cinq>getTransactionDuration();
    Event* e = new Event( cinq, etime);
    pq.insert( e );
    }}

    Code for Simulation


    // print the final avaerage wait time.
    double avgWait = (totalTime*1.0)/count;
    cout << "Total time:
    " << totalTime << endl;
    cout << Customer:
    " << count << endl;
    cout << "Average wait: " << avgWait << endl;

    You may be thinking that the complete picture of simulation is


    not visible. How will we run this simulation? Another
    important tool in the simulation is animation. You have seen
    the animation of traffic. Cars are moving and stopping on the
    signals. Signals are turning into red, green and yellow. You can
    easily understand from the animation. If the animation is
    combined with the simulation, it is easily understood.
    We have an animated tool here that shows the animation of the
    events. A programmer can see the animation of the bank
    simulation. With the help of this animation, you can better
    understand the simulation.

    In this animation, you can see the Entrance of the customers,


    four tellers, priority queue and the Exit. The customers enter the
    queue and as the tellers are free. They go to the teller straight.
    Customer C1<30, 10> enters the bank. The customer C1 enters
    after 30 mins and he needs 10 mins for the transaction. He goes
    to the teller 1. Then customer C2 enters the bank and goes to
    teller 2. When the transaction ends, the customer leaves the
    bank. When tellers are not free, customer will wait in the queue.
    In the event priority queue, we have different events. The entries
    in the priority queue are like arr, 76 (arrival event at 76 min) or
    q1, 80 (event in q1 at 80 min) etc. Lets see the statistics when a
    customer leaves the bank. At exit, you see the customer leaving
    the bank as C15<68, 3><77, 3>, it means that the customer C15
    enters the bank at 68 mins and requires 3 mins for his
    transaction. He goes to the teller 4 but the teller is not free, so
    the customer has to wait in the queue. He leaves the bank at 77
    mins.

    This course is not about the animation or simulation. We


    will solve the problems, using different data structures.
    Although with the help of simulation and animation, you
    can have a real sketch of the problem.

    You might also like