Versions Compared

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.

1. Summary

In this project, I used my Queue to simulate shoppers picking check-out lines. A queue is a First In First Out sequence where we add a thing only at the tail and remove a thing only at the head. It has three key methods—offer, poll, and peek. For the project, I used a node-based doubly linked list to implement a queue.

...

The results are overall as expected and relatable to our daily life.

2. Tasks

Customer Class

The Customer class is an abstract class from which I derive three classes that implement their own chooseLine methods.

CheckoutAgent Class

The CheckoutAgent class incorporates a queue of customers. The draw method draws the CheckoutAgent as a rectangle, but I later modified it so that the simulation becomes visually attractive and informative. I also added a getNumItemsInQueue method that returns the total number of items in a queue for one of my extensions. In the updateState method, I used if else statements and a for each loop.

Landscape Class

The Landscape Class uses ArrayList and LinkedList. In the draw method, I used a for each loop to loop through the CheckoutAgent ArrayList, calling each CheckoutAgent's draw method.

RandomCustomer Class

The RandomCustomer extends the Customer class and implements the random line-choosing strategy. Its chooseLine method returns an integer randomly chosen from the range 0 (inclusive) to the length of the list (exclusive). I used the Random package to generate a random integer.

PickyCustomer Class

The PickyCustomer class extends the Customer class and implements the strategy in which the customer chooses to join the shortest queue. In the chooseLine method, I initialized a large integer named 

shortest and an integer with the initial value 0 that represents the index of the shortest line. And then I used a for loop to in which I compared the number of Customers in each checkout line with the variable shortest, and update the value of shortest if necessary. Finally, I returned  the index of the CheckoutAgent with the shortest line.

Pick2Customer Class

The Pick2Customer class extends the Customer class and implements the strategy in which the customer randomly chooses two lines, then joins the shorter of those two. In the chooseLine method, I first generate two random integers in the range of [0, 5). To ensure that there are two different lines chosen, I use a while loop to renew one of the integers if the two integers are the same. Then I use an if else statement to compare the two different integers and return the index accordingly.

Simulation

I made three new classes--RandomCustomerSimulation, PickyCustomerSimulation, and Pick2CustomerSimulation. And I added an updateCheckouts method in the Landscape class that loops through all of the CheckoutAgents, calling updateState.

Evaluate the strategies 

Initially, each Customer has 1 to 10 items. The lines grow over time, which means that 1 to 10 items is too many. So I adjust the maximum number of items to find a situation where the queues don't grow over time. 

...


Picky Customers spend the longest time in average because they need to scan all of the checkout stations.

Pick2 Customers spend the shortest time in average because they only compare two lines and choose the shorter one.

Random Customers spend the shortest time on choosing to join a line, but the line they choose may be very long. So the time they spend is not the shortest overall.

 

In terms of standard deviation, the time spent varies little among each Picky Customer.

Pick2 is the most stable strategy.

Random is unpredictable and thus unstable, so its standard deviation is the largest.

3. Extensions

1) Re-implement your Queue using an array-based method instead of a Node-based method and show the functionality is identical. 


I made my ArrayQueue generic and implemented an iterator and a reverse iterator.

...

The result of testing is shown below:

.

 

2) 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 the Landscape class, I added another three LinkedList fields which are randomCusLLpick2CusLL, and pickyCusLL

...

Additionally, Picky is the most reliable strategy due to its small standard deviation.

 

3) Make the simulation visually interesting or more informative.


I modified my draw method in CheckoutAgent class.

...

Below are some snapshots:
.

4) Analyze different aspects of the performance. For example, keep track of the average line length.

 

In my RandomCustomerSimulationPick2CustomerSimulationPickyCustomerSimulation classes, I calculated the average line length every 100 time steps using a for each loop.

...

When I ran the simulation, a dialog box would pop up, informing me of the average line length every 100 time steps.

For example:

          


5) Analyze different aspects of the performance. For example, see if the amount of time a Customer spends in line is related to the number of items he has.

In order to analyze the relationship between the amount of time and the number of items, I created a chooseNumItems() method using JOptionPane in LandscapeDisplay and assigned the result of calling chooseNumItems() to a variable maxNumItems in my ChooseRandomStrategySimulation class. 

...

From the statistics, we can observe that the fewer items each customers has, the less it takes a customer to be checked out.

    

6) 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 significantly more time steps than the one that chooses the shortest line.

Firstly, I added a getNumItemsInQueue method in CheckoutAgent class that loops through each Customer in a CheckoutAgent's queue to get the sum of items in the queue and returns the total number of items.

...

The average time is around or above 20. Since the customers count the number of items, they spend significantly more time in a line.

 

7) Gaussian distribution

Inspired by Professor Maxwell, in my Pick2CustomerSimulation class, instead of choosing the max number of items from 1 to 8 uniformly, I chose 6, 4, and 2 recurrently, simulating a Gaussian distribution.

...

Now we can see the interesting pattern:

4. Reflection

At the end of the project, I became more familiar with data structures such as doubly-linked lists, arrays, array lists, and queues. I also learned a lot of GUI functions like showMessageDialog and showInputDialog. Additionally, I tried to improve the visualization using functionalities of Graphics. Besides, I learned how to design a new strategy and facilitate the process of user controlling variables and receiving information. I also spent a lot of time collecting and analyzing data. Overall, the project was super fun.

5. Sources

Professor Taylor

Professor Maxwell and his lecture notes

...