CSCI 136

CSCI 136 - Fall 2019

Data Structures & Advanced Programming

Lab 8: Queuing Simulation

The assignment this week is to complete 13.7 Laboratory: Simulating Business from Bailey pg. 341. In prior labs we have developed programs to process data or solve problems using the data structures and programming concepts we discussed in lecture. This week, we will explore the ways that data structures appear in the physical world, comparing two scenarios:

In many supermarkets and retail stores, customers select and wait in one of several available queues to purchase items. Once in a queue, they wait until the cashier has finished serving the customers ahead of them.
In many banks, customers wait in a single queue. When a teller becomes available, the customer at the front of the queue is serviced by that teller.

We will build a simulation for both scenarios and then measure the performance of each approach.

Important note: This week you may again work with a partner.

Pre-lab: Step 0

Before lab, please do the following:

As in prior labs, you should develop a design document before coming to lab. Although this is a partner lab, you should create an independent design document so that you and your partner can compare approaches. It is OK if your final design deviates from your design document.
Whether or not you decide to work with a partner, please fill out the following Google form by midnight on Monday. Please submit exactly once per pair!

Lab Assignment

Instructions for this assignment can be found on pages 341--342 in Bailey. We have posted some suggestions below. We have also posted a sample abstract base class (BusinessSimulation.java) to help you design your program to simulate the two scenarios as well as a simple customer object (Customer.java) to get you started.

We would like you extend the abstract base BusinessSimulation class with two concrete classes, say OneQueue.java and MultiQueue.java. You should implement functionality common to the single-queue and multiple-queue simulations in the abstract base class.

Suggestions:

You should have a well-organized, well-commented program that simulates the two scenarios described above.

The approach suggested by the assignment is to maintain an event queue, where each event is a customer arrival, a teller becoming free, etc. You may find it easiest to generate a single Customer class and store only Customer objects in the event queue.

A Customer must implement the Comparable interface to be stored in a Priority Queue. Customers should be ranked by their "arrival" time.
Think about what information is necessary to answer the thought questions. You may need to know when a Customer "arrives", when a Customer begins receiving service from a teller, how long it takes a teller to service a Customer, etc.

You should maintain a counter (probably an int) that keeps track of the current time step of your simulation and your simulation should proceed in rounds. During each time step:
- Available Customer objects may potentially join a teller queue. (You may want to pre-populate your event queue with Customer objects, but you should ignore them until the time step matches their designated "arrival" time.)
- Each teller should make progress towards serving the first Customer in their line (if one exists).
- You may also need to update simulation statistics in order to answer the though questions.
Be sure to implement toString() methods for each class so that you can monitor the state of your queues and debug.
Your simulation should end when (1) there are no more Customer objects in your event queue, and (2) all Customer objects have been serviced by all tellers.
Your simulations should be in the file Experiments.java, which should contain a main method that accepts command-line arguments and runs the chosen simulation with the chosen variables. You may also add separate additional classes as needed.

Thought questions

Please answer thought questions 1--4, and place your answers in the PROBLEMS.md file. Some notes:

Questions 1 and 2 ask you to compare simulation statistics. Please give the parameters that you used for your simulations (number of customers, number of tellers, min/max service times, seed, etc.) in addition to the statistics the question asks.
For thought question 2, the wait time is the difference between the time that a Customer appears in the simulation and the time that the Customer first begins receiving service from a teller. The wait time should not include the time that a Customer is actively receiving service.
For thought question 4, you should consider the multiple-queue simulation (e.g., the supermarket model) and the single-queue simulation (e.g., the bank model) separately. For the single-queue simulation, imagine that the set of tellers is partitioned so that Customers with short service times cannot be helped by tellers that serve Customers with long service times and vice versa.

Lab Deliverables

For this lab, please submit the following:

Your well-documented source code, including BusinessSimulation.java and Customer.java, and the java files for the two classes that extend BusinessSimulation.
The PROBLEMS.md file that contains answers to the four questions described above, as well as any other information about your submission.

As in all labs, you will be graded on design, documentation, style, and correctness. Be sure to document your program with appropriate comments, including your name and a general description at the top of the file, a description of each method with pre- and post-conditions where appropriate. Also use comments and descriptive variable names to clarify sections of the code which may not be clear to someone trying to understand it.

Submitting Your Lab

As you complete various milestones, you should commit your changes and push them. Commit early and often. When the deadline arrives, we will retrieve the latest version of your code. If you are confident that you are done, please include "Lab Submission" as the commit message for your final commit. If you later decide that you have more edits to make, it is OK. We will look at the latest commit before the deadline.

Be sure to push your changes to GitHub
Verify your changes on Github. Navigate in your web browser to your private repository on GitHub. It should be available at https://github.com/williams-cs/cs136f19_lab8_simulation-{USERNAME} You should see all changes reflected in the various files that you submit. If not, go back and make sure you committed and pushed.

We will know that the files are yours because they are in your git repository. Do not include identifying information in the code that you submit. Our goal is to grade the programs anonymously to avoid any bias. However, in your README.md file, please cite any sources of inspiration or collaboration (e.g., conversations with classmates). We take the honor code very seriously, and so should you. Please include the statement "I am the sole author of the work in this repository" in the comments at the top each of your java files.