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 Wal-Mart, 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 picking, the situation may have changed.
The simplest strategy is to pick a line at random. Of course, that 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).
Documentation for Java 1.5 is located at: Java 1.5 SE API.
Documentation for Java 1.6 is located at: Java 1.6 SE API
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.
You can design this simulation however you like. The tasks are simply hints as to one design approach within the general framework.
- 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, putting in 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 customers.
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. After it is created, in the first
call to its updateRule it will need to pick and join a checkout
line. After that, it should take the Customer one iteration per item
of stuff to check out. When starting, just give each Customer one
The Customer has to be able to tell other classes how much stuff it has left to check out. The checkout agent needs to be able to decrement the number of items left to check out.
When the customer is finished checking out, it will need to remove itself from the simulation, but make sure to save how long it took to get through the queue.
The most complex part of the Customer class will be picking a checkout line. It will need to implement the three strategies above.
The simulation will also need a checkout agent. The checkout agent
needs to maintain a queue of Customers. For this lab, you need to
write the queue class yourself (we'll do this largely during the lab
time). You may not use a Java library type to implement the queue.
To enable the customer to make decisions, the Checkout agent must be able to tell the customer the length of its queue. The checkout agent also needs to set the spatial position of the customer each iteration since the customer will always be situated relative to the (non-moving) checkout counters.
In addition, the checkout agent needs to have methods so the Customer can join the queue. It will use the Customer's methods to see how many items are left to check out and reduce that number by one each iteration.
- Because there are several different types of agents on the Landscape, it is probably a good idea to create a new neighbors method in Landscape that, in addition to a vision distance, also takes in the type of agents to return. One method of making agent types easier is to use an enumerated type. Attached is an Agent interface that includes an enumerated AgentType.
- Finally, you'll need a new child class of Simulation to initialize it. I've attached a sample of what it might look like. It may help you to put together a top-down design if you look at the arguments to each type of agent and think about how those affect the fields and methods of the different agent types.
As a last note, you'll want to plan out the interaction between agents
before writing code. Think about the narrative of a customer.
- The customer is created
- The customer finds the set of Checkout agents
- The customer makes a choice of checkout station
- The customer joins the queue for that checkout station
- When the customer is at the head of the queue, the checkout agent begins to decrement the number of items held by the customer.
- When the customer has no more items, the checkout agent should remove it from its queue and the customer should remove itself from the simulation and store its timing data somewhere.
- Once your simulation is working, run lots of customers and calculate the average and standard deviation of the time to check out for different strategies.
- Make your queue class generic.
- Try other strategies for checking out. Keep track of how complex they are.
- Make the simulation visually interesting.
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 most interesting bits for this week are your three agents and their methods of communication. The final results are also important. Any extensions you did are interesting.
- Printouts, pictures, or results to show what you did. You can do screen captures of your terminal to show the initial and final landscapes.
- 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:
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, please put it on the Academics server in your folder within the COMP/CS231 directory.