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.

With the simulations, I compared the performance of three different strategies for selecting a line which are random, pick2, and picky.

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

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

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.

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.

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.

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.

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.

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.

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.

In all the simulations, I add one Customer every one time step.

The lines grow too long with [1, 10] items per Customer:

Short lines with [1, 9] items per Customer:

The lines grow too long with [1, 10] items per Customer:

Short lines with [1, 8] items per Customer:

**RandomCustomerSimulation**

The lines grow too long with [1, 10] items per Customer:

Short lines with [1, 7] items per Customer:

I added a method `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.

I ran each simulation with 1000 customers and print out the statistics once every 100 time steps.** **

The results of the three strategies are as below:

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.

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

The result of testing is shown below:

.

In the Landscape class, I added another three LinkedList fields which are randomCusLL, pick2CusLL, and pickyCusLL.

And in my addFinishedCustomer method, I used if else statements and the instanceof operator to add three different kinds of customers into the three linked lists respectively.

I made a new ChooseRandomStrategySimulation class in which I allowed each Customer to choose a random strategy. In the for loop, I randomly generate 0, 1, or 2, and each of them is related to a condition of the if else statements. For example, if the integer generated is 0, I add a new RandomCustomer and increment a variable numRandomCust that represents the number of RandomCustomers. Since the integers are randomly generated, each Customer's strategy is also randomly chosen.

In order to calculate the statistics, initializing three variables(numRandomCust, numPick2Cust, and numPickyCust) aside, I created a new printFinishedCategorizedCustomerStatistics method in the Landscape class that calculates the average and standard deviation of the time-to-leave for all of the 3 types of Customers in their respective finished customer list.

I added 1000 customers in total to the five checkouts and I kept the maximum number of items (which is 9) the same for each customer.

In one simulation, the numbers of each kind of customers are printed in the terminal, as shown below:

.

I used three variables in the if else statements to count the numbers.

I printed out the stats every 100 time steps.

I also plotted four charts:

The three strategies take approximately the same amount of time to be checked out, specifically, random < pick2 < picky. Theoretically, pick2 should be the most temporally efficient strategy. But in this case, the maximum number of items(9) is relatively large, which could affect the results to some extent.

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

I modified my draw method in CheckoutAgent class.

In order to do so, I added a get() method that takes in an index as a parameter in MyQueue class so that in the for loop I could use a loop index i to get the number of items each Customer has in a queue.

Below are some snapshots:

.

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

The average line length refers to the average number of customers in a line.

I fixed the maximum number of items to be 8 for all three strategies.

To have a clearer idea of the average line length, I display the output statistics in a dialog box.

In the LandscapeDisplay class, I created an output method using the showMessageDialog() method of JOptionPane.

In the RandomCustomerSimulation class, I call the output method that takes in avrLineLength as a parameter on LandscapeDisplay.

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

For example:

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.

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.

I also created CountItemsCustomer and CountItemsCustomerSimulation classes.

The CountItemsCustomer class extends Customer, and the constructor takes in the total number of items as the time steps.

Based on the PickyCustomer's chooseLine method, I modified the chooseLine method for CountItemsCustomer. I initialized a variable fewest and assigned to it a large integer. In a for loop, I used an if statement to compare the total number of items in each checkout line with fewest and update the value of fewest if necessary. Finally, I return the index of the CheckoutAgent with the fewest items in its line.

In the CountItemsCustomerSimulation class, before I create a new CountItemsCustomer in the for loop, I initialized a variable totalNumItems and then used a for each loop to call each CheckoutAgent's

getNumItemsInQueue method so that I can add the total number of items in all five lines together and pass it in as the second parameter which represents the initial time steps to the CountItemsCustomer's constructor.

Another small extension I did in my CountItemsCustomerSimulation class is using Scanner to allow user to determine the maximum number of items each Customer has.

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

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.

To do so, I used a modulo operator: 2 + (j / 10) % 6.

(j / 10) % 6 gives 4, 2, 0, and the whole expression gives 6, 4, 2.

The simulation is shown below:

.

The variation of average time is little.

In order to see the pattern more clearly, I changed the modulo operator to 3 + (j / 10) % 6 so that it generates 7, 5, 3.

Now we can see the interesting pattern:

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.

Professor Taylor

Professor Maxwell and his lecture notes

Professor Layton and his lecture notes

Ethan Pullen

Tia Zhang