CS 231: Project #5

Title image Fall 2019

Decision-making Simulation: Checkout Lines

The main purpose of this project is to use your Queue implementation to simulate shoppers picking a check-out line at a large store. We'll use the simulation to compare the performance of three different algorithms for selecting a queue. For example, if you are checking out at a big box store, there may be 20 queues open. How do you optimize your choice?

It turns out this question is also relevant to sending packets over a network via different paths.

You will implement and investigate the effectiveness of at least three strategies for choosing a queue:

  1. Select the shortest queue. This may seem optimal, but in practice that takes a lot of work, and by the time you're done examing the length of each queue, the situation may have changed.
  2. Pick a queue at random. This has the advantage of taking very little time to choose a queue, but following a random strategy means you may end up at the end of the longest queue, standing next to a short queue.
  3. Pick two queues randomly and then join the shorter queue. This strategy is studied in (Mitzenmacher, The Power of Two Choices in Randomized Load Balancing, TPDS, 2001). The pick two random strategy may be able to take advantage of the strengths of both earlier strategies, but it may still mean you end up in a long queue next to a short queue.

Problem Description

Implement a simulation of a multi-station checkout situation. Once you have your simulation working, compare the three strategies given below for customers selecting a checkout line.

The classes you will implement for this project include the following

Tasks

Customer Class

The Customer class should be an abstract class with private fields to keep track of how many items remain in her basket (an int) and the number of time steps it takes for her to leave the store (also an int). Ultimately, we will derive three classes from this class, each of which will implement a the line-choosing method. This class defines the data common to all customers and mandates a particular form for the line-choosing method.

The Customer class should implement the following methods

CheckoutAgent Class

The CheckoutAgent class should have fields for its x- and y-positions (ints) (so it can be drawn) and a queue of Customers (MyQueue<Customer>). It should implement the following methods:

Landscape Class

The Landscape Class should have fields for the width and height (ints) (for the purposes of drawing), an ArrayList<CheckoutAgent> to hold the list of checkout agents, and a LinkedList<Customer> to hold the Customers who have completed checking out. Use the LinkedList class you implemented last week to hold the Customers. The Landscape class should implement the following methods.

RandomCustomer Class

The RandomCustomer class should extend the Customer class because a RandomCustomer is a Customer, just a Customer with a particular strategy for choosing a checkout queue to join. The RandomCustomer class should implement the following methods:

Landscape Visualization

Visualize your Landscape with the checkout queues. Download the LandscapeDisplay.java file. It is almost identical to last week.

Test your visualization by running LandscapeDisplay as your main program. The main program generates a random number of Customers (between 1 and 5) for each of 5 CheckoutAgents, adds them to the Landscape, and then displays them.

Testing RandomCustomer.chooseLine

Test your RandomCustomer by downloading and running TestRandomCustomer.java. It generates 99 RandomCustomers and visualizes how they are added to 5 CheckoutAgents. Think about what visualization you expect to see, then make sure the output matches.

PickyCustomer Class

The PickyCustomer class should extend the Customer class and should implement the following methods:

Test your PickyCustomer by downloading and running TestPickyCustomer.java. It generates 99 PickyCustomers and visualizes how they are added to 5 CheckoutAgents. Think about how this visualization should be similar to or different from the visualization with RandomCustomers. Does it meet your expectations?

Pick2Customer Class

The Pick2Customer class should extend the Customer class and should implement the following methods:

Test your Pick2Customer by downloading and running TestPick2Customer.java. It generates 99 Pick2Customers and visualizes how they are added to 5 CheckoutAgents. Think about how this visualization should compare to those with the RandomCustomers and PickyCustomers. Does it meet your expectations?

Simulation

To move the Customers through the queue, the CheckoutAgent will update its state at every time step. Implement the method public void updateState( Landscape scape ). It should do the following.

Add a method public void updateCheckouts() to the Landscape class. It should loop through all of the CheckoutAgents, and call updateState.

Make a new class RandomCustomerSimulation that is modeled after TestRandomCustomer. All you need to do is add a call to the updateCheckouts in the main loop. Add it just after you add a customer to a queue. Run the simulation to determine whether or not it performs as expected. Fix any bugs.

Write PickyCustomerSimulation and Pick2CustomerSimulation classes to perform simulations with the remaing two Customer classes.

Evaluate the strategies

The test code that you adapted for your simulation gives each Customer 1 to 10 items. If your code is working correctly, you should see that the lines grow over time, i.e. that 1 to 10 items is too many. Adjust the maximum number of items to find a situation in which the queues don't grow over time. In your report, include an image showing the lines grow too long with too many items per Customer and another showing short lines with a more manageable number of items per Customer. In the description of each image, be sure to include the ranges that you used to create that image. Complete the remaining tasks with this new, smaller number.

Add a method public void printFinishedCustomerStatistics() to the Landscape to compute and print the average and standard deviation of the time-to-leave for all of the Customers in the finished customer list.

Run each simulation with lots of customers (at least 1000) and print out the statistics periodically, such as once every 100 time steps.

In your report, include a summary of your results, explicitly comparing the performance of the three strategies.


Extensions

The following are some suggested extensions. You should feel free to pursue your own custom extensions to your project that you find interesting. Please clearly identify your extensions in your report. In your code, make sure the baseline simulations run properly. Making a separate sub-folder for major extensions is recommended.

  1. Try other strategies for checking out, such as choosing a line based on how many items are in the line (rather than how many customers). Be sure to choose an initial time-step value that reflects the amount of time it would take to make the line choice. The item-counting example should take signficantly more time steps than the one that chooses the shortest line.
  2. Make the simulation visually interesting or more informative (such as showing how many items each Customer has).
  3. Analyze different aspects of the performance. For example, keep track of the average line length. Another idea is to see if the amount of time a Customer spends in line is related to the number of items they have.
  4. Allow each agent to choose one of the three strategies randomly. Then calculate the statistics for each strategy in the mixed situation. Which strategy does the best in a mixed situation?
  5. For any assignment, a good extension will be to implement a Java class that you have't implemented in the past projects and demonstrate that it has the same functionality as the Java class.
  6. Re-implement your Queue using an array-based method instead of a Node-based method and show the functionality is identical.

Report

Your report should have a simple format.

Handin

Make your report for the project a wiki page in your personal space. If you have questions about making a wiki page, stop by my office or ask in lab.

Once you have written up your assignment, give the page the label:

cs231f19project5

You can give any wiki page a label using the label field at the bottom of the page. The label is different from the title.

Do not put code on your writeup page or anywhere it can be publicly accessed. To hand in code, put it in your folder on the Courses fileserver. Create a directory for each project inside the private folder inside your username folder.