Queues

We're going to work through the methods that define a queue in lab. The queue should implement the functions listed under the Queue interface in the java documentation, but it does not need to implement the Queue<T> interface. It should implement the Iterable<T> interface.

We're not implementing the Queue<T> interface because for this project we're ignoring the larger set of Collection methods required by the Queue<T> interface.

You can use your existing linked list implementation (single or double) to implement this in a class called something like MyQueue.

Documentation for Java 1.6 is located at: Java 1.6 SE API

---

Tasks

1. Find the Queue interface documentation and see what the key functions are. What is the difference between them?
2. Implement the six interface functions. The add and offer methods should put the new node on the end of the queue, and the remove and poll methods should remove and return the data in the node at the head of the queue.
3. Make sure your iterator loops over the linked list from the head to the tail of the queue.

This week we'll take advantage of the fact we have a general framework for simulations. 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?

The optimal process would be to select the queue with the shortest line. However, in practice that takes a lot of work, and by the time you're done looking, the situation may have changed.

The simplest strategy is to pick a line at random. While it takes nearly no time, following a random strategy means you may end up at the end of the longest line, standing next to a short line.

It turns out that a much better strategy than picking randomly is to pick two queues randomly and then select the shorter queue (Mitzenmacher, The Power of Two Choices in Randomized Load Balancing, TPDS, 2001).

Problem Description

Design and implement a simulation of a multi-station checkout situation. Once you have your simulation working, test out the three strategies given below for customers selecting a checkout line.

• Randomly select one checkout line.
• Scan all of the checkout stations and pick the shortest checkout line.
• Randomly select two checkout lines. Of the two, pick the one with the shortest line.

For each case, run lots of customers through the simulation and calculate the average and standard deviation of the time to checkout.

Tasks

You can design this simulation however you like. The tasks are simply hints as to one design approach within the general framework.

1. This simulation involves adding and removing agents each turn. One method of adding agents to a simulation is to have a Spawner agent class that has no visual representation but that adds a certain number of agents to the Landscape each iteration. When you set up the simulation, adding a single Spawner agent takes care of adding whatever other kinds of agents are needed for the simulation. In this case, the Spawner would be creating Customer agents.
2. The simulation obviously needs a Customer agent. The Customer agent needs to know how many items it has and also needs to keep track of what it is doing each iteration. When starting, give each Customer just one item.

   The trajectory a Customer agent should following is the following. These should be implemented as part of the Customer's updateState method.

   1. After spawning, the Customer should be in the selection phase. Depending on the strategy it is using, the selection phase should take 1 time step (random), 2 time steps (best of 2 random choices), or 4 time steps (check all counters). An extension is to design the class to the wait time for the check-all strategy is proportional to the number of checkout counters.
   2. At the end of the selection phase, the Customer should join a CheckoutQueue, entering the wait phase.
   3. When the Customer is at the head of a CheckoutQueue, the Checkout agent should decrement the number of items in the Customer's basket. When there is nothing left in the Customer's basket, the Customer should remove itself from the simulation.

   To achieve the above trajectory, the Customer agent must have fields for its current phase, how much time is left until it can select a queue, and how many items fit has in its basket. The Customer should also keep track of how many turns it takes from spawning to completing its checkout. For flexibility, it may also be useful to have a field that determines the agent's selection strategy, although this could be a global class variable.

   The Customer must have methods to allow a Checkout agent to both test and decrement the number of items in its basket.

3. The simulation will also need a Checkout agent. The checkout agent needs to maintain a queue of Customers. For this project, use the CheckoutQueue class you wrote yourself. You may not use a Java library type to implement the queue (except during debugging, if you wish).

   To enable the customer to make decisions, the Checkout agent must be able to tell a Customer agent the length of its queue. You can decide whether the length of a queue is modified by the number of items in each Customer's basket.

   In its updateState method, the Checkout agent needs to set the spatial position of each Customer agent in its queue on each iteration since each Customer agent will always be situated relative to the (non-moving) Checkout agents. The Checkout agent's updateState method should implement the following rules.

   • There is no one in line: do nothing.
   • There is a Customer at the head of the line with more than zero items in their basket: decrement the number of items in the Customer's basket.
   • There is a Customer at the head of the line with zero items in their basket: remove this Customer from the checkout queue and update the positions of all other Customer agents in the queue.

   The Checkout agent class needs to have methods so a Customer can join a checkout queue.

4. Because there are several different types of agents on the Landscape, you may want to create a new getNeighbors method in Landscape that takes in the type of agents to return. When a Customer is looking for Checkout agents, it should always receive a list of all of the Checkout agents, at least for the default simulation.
5. Create a new CheckoutSimulation class that initializes a Landscape with several Checkout agents and a single Spawner agent. Place all of the Checkout agents at the bottom of the Landscape, regularly spaced, with the lines growing upwards. The simulation should continue until the application is closed. Make sure to balance the number of Customers being spawned with the number of items per customer and the number of Checkout agents. On the first turn it is reasonable to create extra Customer agents to populate the store.
6. Once your simulation is working, run lots of customers (at least 2000) and calculate the average and standard deviation of the time to check out for the three different strategies. You may want to add some type of list to the Landscape to either hang on to all Customers removed from the simulation, or store just the time to checkout for each Customer that completes the process. Have the statistics periodically print out during the simulation, such as once every 100 customers..

---

Extensions

1. Try other strategies for checking out. Keep track of how complex they are.
2. Make the simulation visually interesting.
3. 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?

---

Handin

Before handing in your code, double check that it is well-styled:

• All variable names and function names use camelCase.
• All class names are in PascalCase.
• All public classes and methods use complete JavaDoc. (Double-check this by hand; the javadoc will only point out malformed Javadoc, not alert you to missing documentation!)
• All private class members (fields and methods) have their own descriptive comment (but not JavaDoc).
• Comments are added to explain complicated code blocks.
• All variable and function names are appropriately descriptive.
• All indenting and squigly-braces are properly placed.
• Each concrete (non-abstract) class should have a unit test (main method) that calls and tests all methods in the class.

Make your writeup 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.

Your writeup should have a simple format.

• A brief description of the overall task, in your own words.
• As explanation of your solution, focusing on the interesting bits. The interesting bits here are how you modified the basic design and implemented different simulations.
• Printouts, pictures, animations, or results to show what you did.
• Other results to demonstrate extensions you undertook.
• A brief conclusion and description of what you learned.

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

cs231f13project6

You can give any page a label when you're editing it using the label field at the bottom of the page.

Do not put code on your writeup page or anywhere it can be publicly accessed. To hand in code, put it on the Courses volume in your folder within the COMP/CS231 directory.