Assignment 2: ATM queue event simulation

Assignment 2: ATM queue event simulation.
The assignment 2 deadline is Wednesday the 21th of October at 4pm

Recent updates

October 15th: Specification updated to clarify definition of utilisation rate in Tasks 3 and 4. October 10th: Another update of the testing program.

The time stamps of Transaction objects used as input to the simulators in tasks 3 and 4, and in the 6730 extra task, had not been updated to reflect the change from 0- based to 1-based indexing. This has now been fixed.

Please download and use the new testing program (assign2_test.py).

Also, a typo in the specification of Task 2 has been fixed.

October 8th: We uploaded an improved testing program (assign2_test.py) that does additional tests for task 1 to make sure your function does return a correct list of Transaction objects. Make sure you download and use this new version of the testing program. If you find any problems with this new testing program please let us know (testing the testing program is tricky, as we cannot anticipate all possible mistakes).

October 1st: Testing program updated.

(The September 25 update of the testing program, to fix the calculation of the time stamp, unfortunately was done in a way that broke the error reporting for certain task 1 failures. This has now been corrected.)

Please download and use the new version of the testing program.

September 30th: Two errors in the testing program fixed. The errors affected only the summary of testing printed at the end of the program run, and the testing of the COMP6730 extra task. Please download and use the new version of the testing program.
September 29th: The extra task for COMP6730 students has been defined. The skeleton and testing program have been updated accordingly. Please download and use the new version of the testing program even if you are not a COMP6730 student.

Sept 25: As discussed in the assignment 2 prep lecture, we fixed the wrong example calculation of time stamps in taks 1. Specifically, we updated the comment in the skeleton program for tasks 1:

We have uploaded the updated skeleton and testing programs to reflect these changes.

The objectives of this second assignment are to apply the topics learned in the middle and second part of the course, specifically to (1) load and process data sets from files, (2) use data structures such as lists and dictionaries to store and summarise the loaded data, and (3) use object oriented programming to implement an event simulator.

This assignment consists of four tasks as described below. The first two tasks will require you to implement functions that use file input as well as list and dictionary data structures. The third and fourth tasks are based on object oriented programming, the topic of the lectures in semester weeks 8 to 10.

This assignment is worth 15% of your final course mark and will be marked out of 15 as detailed below. We expect this assignment to take the average student around 15 hours of work (1 hour per mark).

Important information

Assignment submission will be done through Wattle. There will be a link (“Assignment 2 submission and marks”) in the week 12 section of the course Wattle page.

You must submit a single Python module (file) named assign2_uNNNNNNN.py, where NNNNNNN is your ANU number. The file name must be all in lowercase letters.

After you upload your solution file, remember to click on “Save Changes”. If you forget to do this the file will not be stored, and we will have NO record of your submission so you will get no marks.

Note that you can upload a new submission as many times as you wish (until the deadline). This replaces your previous submission. We will only mark the last one (i.e., the one that we find when the deadline has passed). Unfortunately, there is NO way for us to see your previous submissions, so if you make a mistake (upload the wrong file), we can not go back to an earlier version. Be careful!

Assignments are individual. You can discuss the problem with fellow students, but you write and submit your own code. Writing code together, or copying code from classmates or from the internet is plagiarism and will result in penalties.

The submission deadline is Wednesday the 21th of October at 4pm. No late submissions are allowed!

No late submissions can be accepted. If you submit 1 minute after 4pm on the 21th October, you mark will be zero.

The ANU has recently adopted a university-wide policy on late assessments. Under this new policy, lecturers must choose between not accepting late submissions, or delaying submissions (and therefore marking) by two full semester weeks. For a course the size of COMP1730/6730 (330+ students), this is not possible.

Start working early! If you plan, and work, to finish the assignment one week ahead of the deadline, you will have spare time if unforeseen issues arise.

Plagiarism
Working together with others on the assignment is not permitted. Assignments are individual. While we encourage you to discuss the problem with us, the tutors, and

other students in the labs and lectures, you must do the assignment work by yourself.
Make sure you read the COMP1730/6730 Assessment page, especially the section on plagiarism:

http://wattlecourses.anu.edu.au/mod/page/view.php?id=690489

Also make sure to look at the information given on the ANU Research School of Computer Science Current Students page, specifically the links in the section ‘Administration’:

http://cs.anu.edu.au/study/currentstudents.
The ANU Web site on Academic Honesty and Plagiarism also contains excellent resources on this topic:

http://academichonesty.anu.edu.au/. Extensions

If, due to unforeseeable circumstances out of your control (such as illness, accidents, etc) you need an extension to complete the assignment, you must contact us and request an extension before the deadline. If you could not possibly contact us before the deadline, do so as soon as possible after. Requests for extension made after the deadline will only be granted in the most exceptional circumstances. A request for an extension must be accompanied by supporting documentation (such as a medical certificate from your doctor, in case of illness). It is OK to supply documentation at a later date; if you are going to ask for an extensions, it is very important that you contact us about it as soon as possible.

Background to the problem

In many situations, a problem can be solved in several ways. For complex problems, finding an optimal solution analytically is often not possible. An alternative is to simulate the problem with different options, such as different input data sets and / or different settings of parameters.

In this assignment we will develop a simulation of people queuing at ATM machines with the aim to estimate average waiting times for a given number of ATM machines using a real log-file of ATM transactions. If there are not enough ATMs available then the queue and thus waiting times become too long and customers become unhappy, while too many ATMs that are not used incur unnecessary costs for a financial institution.

Similar problems occur in many other applications, including how many lifts there should be in a building, or how many counters should there be during checking at an airport.

Our assignment is based on real log-file of ATM transaction data as sourced from:

http://highered.mheducation.com/sites/0073521485/student_view0/big_data_sets.html

We processed this data and extracted several smaller data sets to allow for testing of the different assignment tasks described below. We also modified the data by (1) removing unnecessary fields, (2) adding a duration field, and (3) introducing errors into some of these data sets. The data sets we provide are in comma separated values (CSV) format and contain the following fields (or columns):

1. time Time of a transaction, format being HH:MM, with 00 ≤ HH ≤ 23 and 00 ≤ MM ≤ 59. 2. date Date of a transaction, a number from 1 to potentially 31.

3. weekday
4. duration
5. amount
6. type The transaction type, one of: balance, deposit, withdrawal, transfer, advance. 7. location A string of the location where the ATM is located.

Note the first line in each CSV file we provide is a header line with the names of the fields (columns). Here is an example from one of the data sets we will provide:

Assignment tasks

First of all, download:

The automated testing program: assign2_test.py The skeleton program: assign2_skeleton.py The ATM transaction data sets:

atm-transactions-all.csv (the full transaction file) atm-transactions-1-clean.csv (1000 transactions) atm-transactions-1-dirty.csv (1000 transactions with errors)

The weekday of a transaction, one of mon, tue, to sun.

How long a transaction took in minutes (where short transactions can have a value of 0 minutes). The amount of cash withdrawn, deposited, or transferred. This is always a positive number.

5

4

the transaction record.

If there is no free ATM when the customer arrives, the customer is placed at the end of a queue. For task 3 and 4, we assume there is a single queue, in which customers wait for any ATM to become free.

When a transaction finishes, the ATM that the customer was using becomes free. If there are any customers in the queue at the location, the first customer in the queue then immediately moves to and begins using the ATM that has become free (and finishes d minutes later, where d is the duration of the transaction record).

If more than one ATM becomes free at the same time and there are customers waiting, the first customer in the queue moves to the lowest numbered ATM; the next waiting customer then moves to the next free ATM, and so on until there are no free ATMs or no waiting customers.

Implementation requirements

For this task, you only need to consider the case of a single ATM at the location. (That is, you can assume N = 1.) You will have to implement the simulation in an object- oriented framework. The skeleton file defines a class called SingleATMSimulator. This class has three important methods:

__init__(self, location) is the constructor. It takes a single argument, which is the name of the location to simulate (a string).

simulate(self, atm_transaction_list) is where you should implement the simulation of a single queue for a single ATM. The argument is a time-ordered list of Transaction records, as described above. The method should only consider those records in the list whose location equals that of the simulator object (i.e., the argument that was given to the constructor); any records in the input that refer to a different location should be ignored. The simulate method does not return any value.

statistics(self) which returns the summary statistics for the simulation so far. The method should return a tuple of four values: number_of_customers, utilisation_rate, number_of_waits, average_wait
The precise meaning of these is described below.

The four values to be returned by the statistics method are:
number_of_customers is the number of customers who have used an ATM at the location during the simulation. utilisation_rate is the fraction of time that ATMs were in use. The utilisation rate at a location L is defined as

(sum of durations of Transactions at L) / (number of ATMs at L * total simulation time)
In Task 3, the number of ATMs is always 1, and there is only a single location for which to do the calculation. However, Task 4 below involves simulation of

multiple locations with multiple ATMs, in which case the utilisation rate is calculated according to this general formula.

Important: For the purpose of calculating the utilisation rate, the simulation is considered to have started at the beginning of the day of the first transaction, and to have ended at the end of the day on which the last transaction finishes. (See the example below for illustration.)

number_of_waits is the number of customers who had to wait.

average_wait is the average waiting time, for those customers who had to wait.
Every call to the simulate method runs a new simulation. The statistics method should return the statistics from the last simulation run. If statistics is called before any

simulation has been run, it should return zero for all four values.
The SingleATMSimulator class provided in the skeleton file is a subclass of the “top” class, object. You may change this if you wish; that is, you can introduce another

class to be the parent class of SingleATMSimulator.
Example
To explain how the simulation should work, here is an example. Suppose the input to the simulation is the following list of Transactions:

The simulation then proceeds as follows:

At 22:24, the first customer arrives. The ATM is free, so his transaction begins immediately.
At 22:25, the second customer arrives. Since the ATM is in use, this customer must wait.
At 22:27 (22:24 + 3), the first customer finishes, and the second customer’s transaction begins. She has then waited 2 minutes. 3 is the duration of the first transaction.
At 22:31 (22:27 + 4), the second customer’s transaction finishes. 4 is the duration of the second transaction.
At 23:48, the third customer arrives, and begins his transaction. The customer does not have to wait as the ATM is free.
At 23:50, the fourth customer arrives, and joins the queue.
At 23:55 (23:48 + 7), the third customer finishes, and the fourth customer begins his transaction. He has waited 5 minutes. 7 is the duration of the third transaction. At 23:55, the fifth customer also arrives. Since the ATM is busy, she joins the queue.
At 23:58 (23:55 + 3), the fourth customer finishes and the fifth customer can begin her transaction. She has waited 3 minutes.
At 00:02 (23:58 + 4), on the 20th, the fifth customer’s transaction finishes.

At this point, the statistics for the example are as follows:

The number of customers served is 5.
The start of the first transaction occurred on the 19th, and the end of the last transaction on the 20th. Therefore, the total simulation time is 48 hours. The sum of transaction durations is 21 minutes, so the utilisation rate is 21 / (60 * 48) = 0.00729166.
The number of customers who had to wait is 3.
The average waiting time is 10 / 3 = 3.33333333.

Testing

To test your SingleATMSimulator, you can proceed as follows: First, create a list of Transactions (for example, by reading them from a file using the function from Task 1). Suppose you have called this test_trans_list. Then, you can run:

22:24,19,sat,3,,balance,test1
22:25,19,sat,4,20,withdrawal,test1
23:48,19,sat,7,90,withdrawal,test1
23:50,19,sat,3,35,withdrawal,test1
23:55,19,sat,4,,balance,test1

my_sim = SingleATMSimulator("campusb")
my_sim.simulate(test_trans_list)
stats = my_sim.statistics()
print(stats)

Task 4: Implement queuing simulation for several ATMs in multiple locations: (2 marks)

In this task, you will extend the simulator to work with multiple locations and multiple ATMs in each location. The rules for the simulation are the same as described for Task 3 above, except that you can no longer assume a single ATM per location. Each location is independent, meaning customers will only queue and do their transaction at the location named in the Transaction record.

The skeleton file defines a class called MultiATMSimulator. This class also has methods __init__, simulate and statistics.

The __init__ method takes a single argument, which is a dictionary that has location names (strings) as keys and the number of ATMs at those locations as the corresponding values. The simulator must simulate queuing at all locations that appear in the dictionary. The simulate method takes as argument a time-ordered list of Transactions. In the same way as in Task 3, the simulate method must ignore any transactions in the list that refer to locations that are not being simulated, i.e., not found in the dictionary passed to the simulator’s constructor. The statistics method takes no argument, and must return a dictionary that maps the name of each simulated location to the the 4-tuple of statistics (number of customers served, utilisation rate, number of customers who waited, average wait time) for that location.

Important: For the purpose of calculating the utilisation rate, the simulation is considered to have started at the beginning of the first day on which there was any transaction at any of the locations being simulated (i.e., that are found in the dictionary passed to the simulator constructor). The simulation end time is the end of the day on which the last transaction at any of the simulated locations ended.

The MultiATMSimulator class provided in the skeleton file is a subclass of the “top” class, object. You may change this if you wish; that is, you can introduce another class to be the parent class of MultiATMSimulator.

Example

The following code runs a simulation using the complete transaction file, with 2 ATMs at location ‘driveup’, 1 ATM at ‘campusa’ and 3 ATMs at ‘campusb’, and prints the statistics:

atm_transaction_list = load_atm_file("atm-transactions-all.csv")
atm_num_loc_dict = {'driveup' : 2, 'campusa' : 1, 'campusb' : 3}
my_sim = MultiATMSimulator(atm_num_loc_dict)
my_sim.simulate(atm_transaction_list)

stats = my_sim.statistics()
for key,val in stats.items():

    print(key, ':', val)

It should print the following:

campusa : (658, 0.05604166666666666, 126, 3.7777777777777777)
campusb : (7285, 0.22869598765432098, 1445, 3.513494809688581)
driveup : (6970, 0.34866898148148145, 3928, 12.593431771894094)

(though not necessarily in that order).

Extension task (COMP6730 only): Scheduling ATM restocking

For this task, you will need to implement a different analysis of the ATM transaction data. There is a limit on how much money an ATM can store. The ATMs in our data set can take deposits as well as dispense cash, so over time, we may hope the two types of transactions balance out. If they do not, however, it is necessary to restock the ATM, meaning to refill it with cash, or remove some of the surplus if deposits have outweighted withdrawals. The objective of this part of the assignment is to compute, from a list of transaction records, a schedule of restocking operations.

The task is to implement the function

compute_restock_schedule(transaction_list, location, limit)

The arguments are a (time-ordered) list of Transaction objects, the location to compute a schedule for (a string), and the limit on the amount of cash that can be stored in the ATM (a positive number).

The function must return a restocking schedule. This is a list of pairs of values, (day, amount), where day (an integer) is the day on which the restock occurs (see details below) and amount (a number) is the amount of money to be moved to the ATM. A negative number means money is collected from the ATM instead.

The conditions on the schedule are as follows:

The function must only compute a restocking schedule for a single location. The transaction list may contain transactions referring to other locations, but these should be ignored.

The schedule must not contain multiple events for the same day, and the days of events in the schedule must be in increasing order.

We assume that ATMs in a single location have a shared cash storage. The amount of cash in storage must be between 0 and the given limit (inclusive) at every point. (This means after every transaction and restocking.)

Transactions are assumed to occur in the order that they are found in the list, on the day that is given in the transaction record. (This means that for this task we are ignoring queuing.)

If a restocking is scheduled on day X, it occurs between day X and X+1, i.e., after the last transaction on day X and before the first transaction on day X+1.
Days in the schedule must be between 0 and 31 (inclusive). We assume that the initial amount in storage at every location is 0. However, since the first transaction

for every location in our data occurs on day 1, it is possible (and sometimes necessary) to schedule a restocking before the first transaction, by scheduling it on day 0.

The function will only be called with arguments for which a feasible restocking schedule exists. In fact, it is almost always the case that there is more than one feasible solution. As an additional challenge (though not for additional marks), you can consider how to compute a schedule with as few restocking events as possible.

Testing

To test your implementation, add 6730 (as an integer) to TEST_TASKS_LIST in the main part of the testing program and run it.

2

Marks are divided into two categories: Functional requirements and code quality. To evaluate the functional requirements we will test your code using essentially the same testing framework that we provide to you (but using additional data sets and test cases). We will test your code on the CSIT lab computers using python3. If it does not work in this setting it is not correct.

Note: Unlike for assignment 1, task 5 is for COMP6730 students only, and COMP1730 students will not receive bonus marks if they solve this task.