CMPT 225 Assignment 1: Waiting In Line

Your are to write a bank ATM simulation program in C++.  The simulation's purpose is to determine the average waiting time for customers using the ATMs.  This assignment is worth 3% of your final grade.

Start by downloading the assignment files. This zipfile contains a makefile, a test script and inputs/ground truths, and stubs for all of the .h and .cpp files you need. Please do not create any additional .h and .cpp files.

Problem Description

There are three inputs to the program:

Note

You should not use M and N as variable names in your program, uses some other, more descriptive name starting with a lower case letter.

Transaction Time

Different customers may spend different amounts of time at the ATM, one customer may just want to make a quick withdrawal, while another (always the one you get stuck behind when you are in a hurry) may want to do his / her entire banking for the last three months.

Choosing an ATM

Whenever a customer arrives he/she should be assigned to an ATM queue. We will assume the customers are rational, want to wait for as little time as possible, but don't know how long other customers are going to take.  Therefore if an ATM is free (i.e. there is no one using it) a customer will go to that ATM (or one of the other available ATMs if there is more than one), otherwise the customer will go to the ATM with the smallest lineup (queue).

If there is a tie, the customer always chooses the lowest numbered ATM. E.g. if there are 3 ATMs, numbered 0-2, and ATM 0 has 2 customers waiting, and ATMs 1 and 2 have no customers waiting, ATM 1 will be chosen.

Customers do not switch queues once they have chosen one, even if another ATM becomes available.

Treat each minute as a discrete event (i.e. minutes should not be further divided into seconds).

When To Stop

When the simulation reaches M minutes no more new customers should be accepted.  However, the simulation should continue until all the customers who were at an ATM or waiting in an ATM queue at M minutes have completed their transactions.

Output

For each simulation you should output the total number of customers and the average wait time. Please use the provided code for the output.

The simulation program atm_sim should return the total wait time for all customers over the simulation. This is done in the main function provided (in atm_sim.cpp).

Top level Simulation Loop

The simulation control loop (which would be in, or called from, the main function) can be written as a while loop like this:

while (min < M or there are still customers to process)
	// Process new customers
	if (min < M and new customers arrive - based on list)
		for each new customer
			assign customer to shortest queue
			increment customer count
	
	// Process ATMs
	for (i = 0 to N)
		process each ATM (see below for more details) and increment wait time
	increment min
output statistics

Note that the above is not written in a programming language, it is just a pseudocode description of what I expect your main loop to be doing.

Simulation Components

Here are some thoughts about what data you will need to keep track and where:

Top Level (the main program file atm_sim.cpp)

The top level program needs to contain the main simulation loop (described above).  It also needs variables for M and N (not called M and N).  In addition you will need to record the following:

Note that you may want to use functions in the main program to break the program into easily manageable pieces

ATM Class (ATM.h, ATM.cpp)

Each ATM needs to keep track of data related to it, that is:

You may also want to record some other attributes in the ATM class

You should create an ATM class with the member variables noted above, and appropriate methods to set and retrieve values for those variables.  The class methods will probably include the following:

Processing a Customer in an ATM

The following needs to be performed to process an ATM's customers 

if (ATM is in use)
    decrement transaction time of its current customer by 1

if (current customer is finished)
    remove the customer at the front of the queue
    set the ATM's remaining transaction time to that customer's transaction time
    increase the ATM's total wait time by the time that the customer waited (current time - arrival time)

Customer Queue (ATMQueue.h, ATMQueue.cpp)

You should create a customer queue class to record data required for waiting customers.  This data consists of:

Your queue must be implemented using a linked list, and the insert and remove methods must run in constant (O(1)) time.

Other Classes

Testing

The zipfile contains a testing script, test.py. You should run this, and other test cases, to verify correctness of your simulation.

As you are developing and testing your application you may find it useful to print some data about the current contents of the ATMs, for example:

Grading

The assignment is worth 3% and marks are allocated to the assignment as follows:

Submission

You should submit your assignment online to the CourSys submission server.  You should submit the following:

Please read the documentation on the submission site for further information. The assignment is due at 11:59pm on Friday February 8.

Back to the CMPT 225 homepage.