Abstract:
The goal of this project was to
create a simulation of a store in which there are several queues. Agents
(representing customers) use one of three strategies to select which line to
enter. The first strategy is to randomly select a queue, the second strategy is
to select the shortest queue, and the third strategy is to consider two random
queues and select the shorter queue. In the simulation, each Agent had a number
of checkout steps, which was a random number between the values of 1 and 6 inclusive. For agents at the front of the queue,
the number of checkout steps was decremented by 1 step per iteration of the
simulation. When the number of checkout steps reached 0, the agent was removed
from the queue. Each Agent stored data regarding its entrance and exit time.
This data was used to calculate the mean time each Agent spent waiting in line.
The total time was increased by 1 for each queue the Agent analyzed when
picking a queue. Strategy 3 (selection between two queues) was the most
efficient strategy, while Strategy 1 (random selection) was the next most
efficient, and Strategy 2 (choice selection) was the least efficient.
Problem:
The purpose of this simulation
was to model a store with several queues. The queues are populated by Agents,
which choose a queue based on a designated strategy. There were three
strategies that were tested in this Simulation:
1.) Random
Selection.
2.) Selection of
the shortest queue.
3.) Selection of
the shortest queue between two random queues.
The simulation stored data about
the total time that each agent spent in line. This data was averaged to
determine the relative efficiency of each line. To make the simulation more
accurately depict real time, a weighting system was implement in which the
total time to checkout was incremented by 1 unit of time for each queue that
was analyzed in the selection process. E.g. agents using strategy 1 would not
be affected, but agents using strategy 3 would have their total checkout time
incremented by two.
Theory and Algorithms:
This simulation used the Queue
data structure to represent the queues in the store. Six queues were stored in
an array, and Agents were added to those queues following their queue selection
strategy. The front element of each queue was stored in a separate array of agents,
which represented the front of the line. The iterate function simulated the
passing of one unit of time. The iterate function used a for-loop to view each
Agent at the front of the line.
for(i=0; i<agentArray.length; i++)
After entering this for-loop, the
iterate method considered each index of the agentArray to check if it contained
an Agent.
if(agentArray[i] != null)
If the agentArray contained an
Agent at index i, it would go on to check if the Agent was done with being
checked out (via the Agent classes accessor method, checkoutDone(), which
returns true if the remaining checkout steps is equal to zero).
if(agentArray[i].checkoutDone())
If the Agent was done, then it
would be added to the finishedQueue LinkedList, and its exit time would be set
to the current time of the Simulation. Then the front agent of the
corresponding Queue would be removed to reflect this change.
finishedQueue.add(agentArray[i]);
Agent a =
(Agent)finishedQueue.getLast();
a.setExitTime(currentSteps);
qArray[i].removeFirst();
The method would then see if
there were any more remaining Agents on the queue. If so, the method would send
the next Agent to the front of the line, otherwise the front of the line would
be set to null.
if(!qArray[i].isEmpty())
agentArray[i]=(Agent)qArray[i].getFirst();}
else
{agentArray[i]=null;}
Next, the iterator would
increment he Ònumber of removesÓ value to keep track of the number of Agents
removed from the queue in this iteration. After this was completed, the
iterator would check if the front of the queue was not null. If it was not
null, this would mean that there is an Agent at the front of the line, and its
steps remaining was decremented.
if(agentArray[i]!=null)
agentArray[i].decCheckoutSteps();
The next check was to see if the
front of the queue was null. If so, the iterator would replace the null value
with the value of the next Agent in the queue. If the queue was empty, the
value would stay null.
if(agentArray[i]==null)
{
if(!qArray[i].isEmpty())
{
agentArray[i]=(Agent)qArray[i].getFirst();
}
}
The next step was to re-populate
the queues with new agents. This used the Ònumber of removesÓ value, and added
a number of Agents equal to the number that were removed in this iteration.
This made sure that the number of agents in the queue were constant.
for(i=0; i < numberOfRemoves; i++)
{
Agent a = new Agent(strategy);
a.setStepsLeft();
a.setEntryTime(currentSteps);
qArray[a.pickQueue(qArray)].addLast(a);
}
Finally, the number of total time
of the system was incremented, and then the iterate function was exited.
currentSteps++;
return;
Results:
The results for this simulation
indicated that the best method of selecting a queue was Strategy 3, which was
selecting the shortest queue between two randomly selected queues. The next
best was Strategy 2, random selection. The worst method was Strategy 1, which
was selecting the shortest queue. The explanation for this was that the extra
time taken to analyze each and every queue added more to the total time than
was saved by entering the shortest queue. The data for the three strategies is
as follows:
Strategy: 0 (Random Selection)
Mean:
26.03919491525424
Variance: 342.3621948972806
Standard Deviantion: 18.50303204605344
Strategy: 1 (Choice Selection from all 6 queues)
Mean:
28.46090909090909
Variance: 44.38882537844318
Standard Deviantion: 6.6624939308372495
Strategy: 2 (Choice selection from two random
queues)
Mean:
24.78104875804968
Variance: 66.29824088804408
Standard Deviantion: 8.142373172978752
When comparing the fastest method (Strategy Two) with the slowest method (Strategy one), Strategy two is 14.51% faster on average. The standard deviation values show the standard deviation from the mean for the checkout times of Agents. The random selection had the largest standard deviation, which means that although the average time is 26.03, there were many Agents that made it through in significantly less time, and other Agents in significantly more time. Strategy one had the lowest standard deviation, which means that even though it is the slowest strategy, it is the most stable as far as conformity of checkout times.
Discussion:
It is important to keep in mind
that the Simulation did a relatively short-sighted study of the situation. For
example, it did not accurately simulate a realistic store, in which people
would be pursuing different strategies on an individual basis. Also, the number
of agents in the line was held constant at 25. In larger queues, the tax for
evaluating each line would become smaller relative to the total time spent in
the line. This would change the effectiveness of Strategy 2 (selecting the
shortest of all six queues). Also, the amount of time it takes to analyze each
queue is not the most accurate representation of a real life situation. In the
case of the simulation, the amount of time taken to analyze each queue is
constant at 1 unit of time, regardless of the size of the queue in question.
Also, the actual method of analyzing the queue is not the most accurate
representation of a real life strategy. The simulation only took into account
the length of the queue, while in real life, one might want to analyze how many
items people have in each queue, the nature of the cashier at the front of the
line (if the cashier is particularly slow, it might be a line to be avoided),
etc. Although the simulation completed its task of providing a very basic
simulation for the effectiveness of different strategies for selecting a queue
in a store, it did not provide a very accurate depiction of a real life situation,
in which there are countless more variables that were not considered in this
exercise. Overall, while the data collected in this simulation is interesting,
it should not be taken as an accurate representation of the viability of the
three different strategies.