Project 3

Project#3

The purpose of this project is to give you some experience programming with queues. In this project, you will write the Simulation procedure that is explained in Chapter 7.7 “Application: An Event-Driven Simulation” of the textbook.

It is very important to read the procedure specification carefully so that you fully understand the simulation environment before implementing it.

1. Copying files from the program directory.
According to the textbook, the Simulation procedure uses two generic packages; Queues_Circular_Generic and Queues_Priority_Generic. These two packages DO NOT exist under the “programs131” directory.

1.1 Copy “simulation.adb”, “simulation-process_arrival.adb”, and “simulation-process_departure.adb” files to your directory.

    1.2 Copy “queues_generic.ads” and “queues_generic.adb” files and use them instead of Queues_Circular_Generic package. Delete “WITH Queues_Circular_Generic;” in the “simulation.adb” and put “WITH Queues_Generic;”.

    1.3 For the Queues_Priority_Generic package, write one by yourself. It has been implemented as a lab assignment. DO NOT use “Queues_Generic_Priority” package in the directory. “Queues_Generic_Priority” calls “Heaps_Generic”, which has not been covered yet in the class.

    1.4 Write the bodies of “simulation.adb”, “simulation-process_arrival.adb”, and “simulation-process_departure.adb”.

2. IO and data requirements
    2.1 IO requirements

        2.1.1 Input: a number of open checkout counters and a file name provided by the user
        2.1.2 Output: average checkout time to the screen

    2.2 Data requirements

        2.2.1 Your procedure must receive an input file name from the user and read customer information from the file. If the file does not exist let the user know. An input file contains one customer at a line as follows;

5     10
6     4
7     25

The first column indicates Arrival Times and the second one indicates number of items.

        2.2.2 “NumQueues” in the Simulation procedure is set to 10.
Although we assume that there are 10 checkout counters, your procedure has to receive a number of “open” checkout counters (1-10) from the user before running a simulation, which will be used for the simulation. When it places a “departure event”, one of the “open” checkout counters should be assigned to the event.

    2.3 Your procedure should
- keep checking open counters so as to assign a counter that has the shortest line to a customer.
- calculate a “departure time” for a customer who is waiting at the front of a counter.
- place a “departure event”, which indicates a counter number and departure time, for a customer.

3. Submission and grading
    3.1 What to submit
        3.1.1 File submission: zip all files into an archive file using your last name and email it to your TA.
        - Packages (4 files): queues_generic.ads, queues_generic.adb, queues_priority_generic.ads, queues_priority_generic.adb
        - Procedures (3 files): simulation.adb, simulation-process_arrival.adb, simulation-process_departure.adb
        - Listing files (4 files): queues_priority_generic.lsb, simulation.lsb, simulation-process_arrival.lsb, simulation-process_departure.lsb
        - Test files: all test files in your test plan
        - Turnin script(s)

        3.1.2 PAPER submission: hand in the following items in paper form.
- Project signature page
- Algorithm with DETAILED explanations
- Test plan

    3.2 Grading
    The grader will run your procedures with his/her test files. To get full points from the Implementation part, your procedures must     produce correct simulation results from the testing.
    - Design: 0 – 2
    - Test plan: 0 – 4
    - Implementation: 0 – 10
    - Code style and layout: 0 – 4

There is an error in the book, you should have received an email about it, the tesxt of the email follows:

've included the text of the changed procedures at the end of this message

Begin forwarded message:

From: David Portnoy <portnoy@gwu.edu>
Date: Mon Nov 18, 2002 4:55:17 PM US/Eastern
To: John Sibert <sibert@gwu.edu>
Cc: HyunJu Kim <hkim@gwu.edu>
Subject: Project #3 Algorithm Corrections

Hi All;

There seems to be an error in the algorithm for the event-driven simulation
in the book, which is to be used for project #3.

Basically, the algorithm as described will never build up any customers in
any of the lines. There will be at most one customer in any of the queues at
any one time.

To fix this three changes have to be made:

1) In the Process_Arrival procedure "departure time = arrival time" should
be changed to "departure time = arrival time + number of items"

2) In the Proccess_Departure procedure "CheckoutTime := DepartureTime +
NumItems - ArrivalTime" should be changed to "CheckoutTime := DepartureTime
- ArrivalTime"

2) In the Proccess_Departure procedure "NextDepartureTime := DepartureTime +
NumItems" the NumItems is for the next customer in the queue not the one
currently being processed. (i.e. The NumItems is not for the customer
currently departing, but for the customer next in line).

And just for clarification, the timestamps for the arrivals in the input
file should be sorted:

Acceptable:

1 3
1 4
1 2
3 5
4 6
4 2
4 1
5 1
5 5
6 3

Not Acceptable:

1 3
4 5
2 3
1 4
1 5

Sorry for the inconvenience,

David Portnoy

SEPARATE (Simulation)
PROCEDURE Process_Arrival(ArrivalTime: Positive;
                         NumItems:    Positive) IS

-- sketch of procedure to process arrival event

BEGIN -- Process_Arrival

-- find k, index of shortest queue
-- enqueue ArrivalTime and NumItems on Queues(k)

IF -- p is the only node on Queues(k) THEN
    -- this customer can be served immediately, so
    -- departure time = arrival time + number of items; therefore
    -- place departure event (from Queues(k))
    -- on event list (ordered by time)
END IF;

IF -- customer file is not empty THEN
    -- read ArrivalTime and NumItems from customer file
    -- place arrival event on event list (ordered by time)
END IF;

END Process_Arrival;

SEPARATE (Simulation)
PROCEDURE Process_Departure(DepartureTime : Positive;
                           Q : IN OUT Queue) IS

-- sketch of procedure to process departure from queue k

BEGIN -- Process_Departure

-- dequeue node from Queues(k); store its info in
-- ArrivalTime and NumItems

-- calculate elapsed checkout time
CheckoutTime := DepartureTime - ArrivalTime;

-- update values which contribute to the average
TotalCheckoutTime := TotalCheckoutTime + CheckoutTime;
NumCustomers := NumCustomers + 1;

IF -- Queues(k) is not empty THEN
    -- compute departure time for next node
    NextDepartureTime := DepartureTime + NumItems;

    -- place departure event (from queue k) on event list
    -- using NextDepartureTime, ordered by time

END IF;

END Process_Departure;