CS 231

Assignment 2: Queue Strategies

Due 4 October 2007

Overview

For this project we will be simulating real queues and different strategies for selecting which queue to use when more than one are available. The canonical example here is having multiple checkout lanes to choose from. Different queue organizations produce different results.

For example, if everyone lines up in a single line and the first person in line goes to the next available cashier, it minimizes the variance of the wait times--everyone waits about the same amount of time--and eliminates any choice by individual agents. However, constantly scanning for the next available cashier takes resources and time, and other strategies may be more efficient.

A distributed strategy allows each agent to select a queue according to their own individual algorithm. An agent might scan all of the queues and select the shortest, or the agent might simply choose a queue at random. Random selection will sometimes work well, while other times it may cost the agent a significant amount of time.

The inspiration for one of the strategies we will try--scan two randomly selected lines and pick the shorter one--comes from a paper by Mike Mitzenmacher, who looked at the performance of different strategies for queue selection.

Setup

Find a partner, if you wish. I recommend it.

Create a new project in BlueJ, or whatever your preferred IDE is. Call the project something informative. You will probably want to copy your RandomInt class over to the directory so that it is included in the project.

Procedure

The project is broken down in a number of small steps. If any step takes you longer than 30-60min, stop by and ask some questions.

Please test as you go. For each class, write a main function that tests all of the methods you've written to ensure that they do the right thing. Print statements are extremely useful, because they let you see what your program is doing, so put in lots of them.

Maxwell's style guide provides some general guidelines for writing code.

Note that you may choose your own names for classes and variable fields, for the most part the names given below are only suggestions. However, please use the method names given below.

  1. Create an Agent class to represent individuals in the store. Each Agent needs to keep track of when they entered the process, when they exited the process, their strategy, and how many steps it takes for them to check out once they reach the checkout counter. You may want a random number generator as well. Use an integer to represent different strategies.

    The Agent should implement the following methods

    • public Agent() - a default constructor that includes picking a selection strategy.
    • public Agent(int time) - a constructor that sets the queue entry time.
    • public void setEntryTime(int t) - sets the entry time.
    • public void setExitTime(int t) - sets the exit time.
    • public void setStrategy(int s) - sets the strategy.
    • public int getEntryTime() - gets the entry time.
    • public int getExitTime() - gets the exit time.
    • public void decCheckoutSteps() - decrements the number of checkout steps remaining.
    • public boolean checkoutDone() - returns true if the number of checkout steps remaining is zero.
    • public int timeInQueue() - returns the exit time less the start time.
    • public int pickQueue( Queue[] q ) - returns the index of the Queue in which to put the Agent.
    • public String toString() - returns a string representing the agent, probably their strategy.
  2. Create a Queue that can hold Agents. You can use your generic data type or create a specific implementation for this project. The queue needs to support: insert, remove, peek, empty, size, and toString. The toString function ought to create a string with the elements of the queue from front to back in order from left to right in the string. Use the Agent toString method to get the individual Agent strings.
  3. The Simulation class has similar functionality to the last project. The Simulation needs to hold an Agent Queue for the agents who have gone through the system; it needs to hold an array of Agent Queues, one for each checkout line, and it needs to have an array of Agents to hold references to the Agents who are currently checking out.

    In order to keep track of how many steps have been simulated, the simulation class needs to have a currentStep field which starts at 0 and gets incremented each time iterat() is called.

    The Simulation class needs to implement the following methods:

    • initialize() - allocate the AgentQueue array and the individual queues, allocates the checkout array, and allocates the finished queue.
    • write() - prints the set of queues to the screen and indicates how many steps are left for each Agent at a checkout counter.
    • iterate() - executes the following algorithm
      • For each checkout location i
        • if the checkout location i is not null
          • if the agent at location i is done
            • Set the exit time for the agent
            • Remove the agent from the queue
            • Insert the agent into the Finished queue
            • Set checkout location i to null
      • Put N new Agents into the process, using their pickQueue() functions to select which queue. Be sure to set the entry time for each Agent.
      • For each checkout location i
        • if the checkout location is empty and queue i is not empty, assign the front Agent from queue i to checkout location i, but do not remove it from the queue.
      • Increment currentStep

    • statistics() - Calculate the mean, variance and standard deviation of the time spent in the queue by the agents.

      mean = (sum of times) / (number of agents)

      variance = [sum over all agents of (time - mean) * (time - mean)] / (number of agents - 1)

      standard deviation = square root of variance

    • Note that you will want to run through the agents in the finished queue twice: once for the mean and once for the variance. So either you need to have a second temporary queue in which to stick the agents as you remove them from the first one (a fine solution) or you will need to actually traverse the elements in the queue without removing them from it.

  4. Test your system using a small number of agents and 3 or 4 queues.
  5. Run your simulation using the three different strategies with at least 6 checkout lines. In each run, all of the agents should use the same strategy. Run lots of agents through (e.g. > 1000). For each strategy, calculate the standard deviation and variance of time through the queue. Present the results in a table.

  6. Let the cost of examining a queue be 1. Random selection should have a cost of 0. Add the decision cost to the number of time steps it takes for an agent to get through the queue and recalculate the statistics. Is this a realistic model of the decision cost?

Extensions

Writeup

Follow the writeup instructions to create a web page for your assignment. Send the instructor an email with the code in a zip or tar file as well as a pointer to the URL for the writeup.