CS1181-Project3
CS 1181
Programming Project 3
CS 1181 Project 3: Data Science (Grocery Store Simulation)
PURPOSE: This assignment explores simulation of a real world situation which leads to meaningful actions to solve a
problem. A very common use of computers is to run simulations to answer practical questions with no easy closed-form
mathematical solution. A simulation is a program designed to model a real system of interest. By setting parameters and
selecting an appropriate model, results are produced that model the behavior of the real system. If the model is a valid
epresentation of the real system, then the simulation can even predict the future performance of the real system.
PROBLEM: In this project, you will construct a program to optimize efficiency of a grocery store. Your goal is to use
your simulation to answer a specific question. A grocery store cu
ently has 12 checkout lanes. Some of those lanes allow
customers to purchase any number of items. Some of the lanes are ‘express lanes’, which only allow customers who are
purchasing twelve items or less. If our goal is to minimize the overall time that customers wait in line, how many of our
12 lanes should be express lanes?
Assume that we collected data from a ‘normal/average’ set of customers during a normal/average day of operation. We
observe the customers and determine that they are characterized by:
(1) Time of a
ival at the store (in minutes relative from the store opening)
(2) Their order size (the number of items that they purchase)
(3) The average time it takes for them to select each grocery item (their total time spent
owsing divided by their
order size)
We provide this information in a text file. Each customer is one line of the data file, characterized by these three
measurements in that order.
For example, the line “ XXXXXXXXXX” in the data file represents a customer that a
ives at the store 2.0 minutes after the
store opens. The customer picks up 15 items and on average takes 0.5 minutes to pick up each item. The customer
therefore spends 15 * 0.5 = 7.5 minutes shopping and then is ready to check out at 9.5 minutes after the store opens.
The customer then moves to the checkout area. We will assume that customers will always select the checkout area with
the shortest number of other customers in line (no matter how many items those customers are purchasing). Customers
with more than 12 items can only use the regular checkout lanes. Customers with 12 or fewer items can use any lane. If
there is a tie in line length, then customers will select any of the lines of equal length. Customers with 12 or fewer items
will select an express lane over a regular lane if the two lanes are tied in the length of their line.
If there is no one in line for a checkout lane, then the customer can immediately begin checking out. If there is anyone in
line, then the customer must wait for everyone in front of them in their line to check out before they can begin to check
out.
The time to check out is determined by the characteristics of the type of lane (regular or express) and the size of the order.
Regular lanes have an average checkout time of 0.05 minutes per item in the order plus 2.0 minutes to process payment
and coupons. Express lanes have an average checkout time of 0.10 minutes per item in the order plus 1.0 minutes to
process payment and coupons.
Continuing the example, our customer with 15 items moves to check out at 9.5 minutes after the store opens. Since they
have 15 items, they must use a regular checkout lane. They select the checkout lane with the shortest line. Let us assume
that there is a regular checkout lane with no line (0 wait time). They immediately begin to check out. The time to check
out is 15 (items) * 0.05 (minutes per item XXXXXXXXXXminutes to process payment) = 2.75 minutes. The customer leaves the
store at 12.25 minutes after the store opens (9.5 min a
ival at checkout + 0 wait XXXXXXXXXXminute checkout). If all lanes had
at least one customer already in the lane, then our example customer could not begin to check out until every customer in
line in front of them had first completed _their_ checkout.
We will use a discrete event simulation to simulate the grocery store. This means time is managed by using a simulation
clock that is advanced whenever an interesting event occurs. For example, if the simulation time is 0.0 minutes and a
customer enters the store at a time 2.0 minutes, we mark the passage of time by advancing the simulation clock to 2.0
| P a g e 1
CS 1181
Programming Project 3
minutes (cu
ent time = 0.0 + time of a
ival event = 2.0). If a customer reaches a checkout line 7.5 minutes later, we
advance the simulation clock to XXXXXXXXXXOur assumption is no interesting activities occur between events (i.e.
nothing significant happens in the intervals (0.0, 2.0) or (2.0, 9.5) so we can record the passage of time by moving the
simulation clock forward to the time when the next important event occurs).
The diagram shown below outlines the flow of events in our simulation.
To begin, set the simulation clock to 0.0 and schedule the first customer a
ival. We place each new event on a list (a
priority queue might be a good choice) that contains the sequence of pending activities ordered by increasing simulation
time.
The actions associated with our example customer are (1) create customer object containing the customer’s data and (2)
schedule the customer’s a
ival. The setup after scheduling the first customerA
ival event might appears as follows:
simClock = 0.0
event list = (
{2.0, customer 1 a
ives}
other customers/events not shown – the event list should start with all customer a
ivals!
)
To process an event, simply remove the first event from the list, update the simulation clock to the time of the event and
perform the action needed to simulate the event. After removing the event the list appears as follows:
simClock = 2.0 Note simulation time has advanced to the time of the event
event list = (
other custome
events not shown
)
Since the first event is an a
ival, perform the actions associated with a new a
ival. This customer is selecting 15 items
and will take an average of 0.5 minutes to select each item so you will need to schedule an end shopping event for this
customer in 15 * 0.5 = 7.5 minutes. Now the event list looks like this:
simClock = 2.0
event list = (
{9.5, customer 1 done shopping},
other custome
events not shown
)
Customer
A
ival Event
Customer
End Shopping
Customer
End Checkout
Customer has a
ived –
schedule the next a
ival
Customer starts shopping–
schedule this customer to
end shopping
Customer ends shopping – put
the customer in a checkout line
and if he/she is the first in line
schedule this customer to end
checkout
Customer ends checkout – if
another customer is wai;ng
in line, schedule the next
customer to end checkout
| P a g e 2
CS 1181
Programming Project 3
Events will be processed in scheduled ‘time’ order… there may be other customer a
ivals or other events before our
example customer 1 is done shopping. When their ‘event’ is next, then we will remove them from event list and assign
them to a lane.
simClock = 9.5
event list = (
other custome
events not shown… for the example we will assume that one of them is
using our assigned lane until 10.0
)
If that lane is full, then we place that custome
event in a queue for that lane. Eventually they will get to the front of their
checkout line at which point we can schedule their checkout. For this example, we will assume that they were assigned to
checkout lane #3 and that the person ‘in front’ of them finishes _their_ checkout at time 10.0 minutes after the store opens.
Now that they are at the head of the checkout line, we start their checkout by scheduling its completion.
simClock = 10.0
event list = (
{12.75, customer 1 done with checkout}
other custome
events not shown
)
simClock = 12.75
event list = (
other custome
events not shown
)
Once the customer completes checkout then we have finished processing that customer. We remove them from the event
queue and check to see if there is anyone behind them in their checkout lane. If there is, then we’ll schedule that next
customer for checkout. We might want to save the customer to provide data to calculate statistics at the end of the
simulation.
To summarize, the actions to perform for each event are:
customerA
ival -- When an a
ival occurs, create a