Part 1: Design document -- due Monday, February 13, 2012 at 11:59pm
Part 2: Minimart -- due Thursday, February 16, 2012 at 11:59pm
Part 3: Full supermarket -- due Thursday, February 23, 2012 at 11:59pm
You have been hired by Stop and Shop to evaluate the efficiency of their checkout configuration. The supermarket would like make sure that customers move as quickly as possible through the registers, which improves the customer experience and helps the supermarket stay profitable.
To solve this problem, you will build a discrete event simulator, which models the behavior of the supermarket. A simulator is not a general solution to the problem, but instead tells us what will happen in a specific scenario -- in our case, how a specific sequence of customers is served by a particular checkout configuration. We can try different configurations and different sequences of customers, and compare the results.
Our model will simplify many of the elements of how a supermarket works, but will preserve enough details that we can evaluate the efficiency. Our model will focus on the number and kinds of lines (regular vs express). We will simulate the same set of customers on each configuration and compare them by looking at the average and maximum wait times for customers, and the total time required to serve all customers.
Simulators are an important class of computer programs and are used for a range of applications in business and entertainment. In fact, the core functionality of most computer games is a simulator.
What are the units of time?
The units of time are not important -- you can think of them as minutes or seconds, whatever you like. The key is that all units are the same. Time starts at 1 when the store opens.
Do I need to sort the customers in the input file?
No, the input file will list customers in order of arrival time.
How long does a customer spend at the register?
Exactly the same number of time units as items they have. Someone with 6 items spends 6 time units at the register.
What is the wait time if the lane is empty?
Someone arriving at an empty line has a wait time of zero. Note that they still have to spend at the register (which is what causes people behind them to have to wait).
Do I really need a queue for the Minimart?
Not really, but you don't want to leave all of the queue-related coding for the more complex parts of the project. The Minimart is a good way to make sure your queue and register design works correctly.
In configuration 3, can people with 5 or fewer items go to the regular lanes?
Yes! This is a change from the description below. People with 5 items or fewer should go the shortest lane, regardless of whether it is an express line or not. People with more than 5 items should go to the shortest non-express lane.
We will simulate four checkout configurations:
1. Minimart: A simple configuration with a single register that takes all customers.
2. No-Express: A supermarket with four regular registers, each with its own line.
3. Express: A supermarket with two regular lines and two express lines. Only customers with 5 items or fewer can use the express lines.
4. Bank: A supermarket with four registers, but only one line. The front customer goes to the next available register when it becomes free.
Each customers arrives at the checkout area at a specified time with some number of items (see Input below). They always start at the back of the line. For configurations 2 and 3, if they have multiple lines to choose from, they go into the shortest line. Customers wait in line until they reach the front.
Time spent at the register is equal to the number of items.
The goal is to compute the wait time for each customer (that is, just the time spent waiting, not the time spent at the register). When a customer enters an empty line, they go straight to the register and their wait time is zero.
The core functionality of this project is the simulation engine. Its main task is to keep track of and advance time, and move customers through the checkout accordingly. The main idea is to advance time one unit at a time, and then see what needs to be done at each time step. You can think of time as "minutes" if you like, but the exact units are not important. The overall algorithm looks like this:
At start:
Main loop:
Look out for tricky cases, such as when a line is empty.
NOTE: It is very important that the input and output of your program conform to the specifications below.
With over 150 students in the class, it is important that we be able to compile and test your program without having to spend time figuring out how it works. That way, we can spend more time giving you feedback on your code.
Your program should ask the user for two pieces of information: a configuration (1 through 4, corresponding to the four configurations above), and the name of a file containing the customer information.
The customer file consists of a list of customer entries, where each entry has three parts: customer name (a string), number of items (and int), and an arrival time (also an int). Arrival time is the time the customer arrives at the check-out and gets into a line. The list of customers will be provided in order of arrival time, so you do not need to worry about sorting them.
The format of the customer file is simple: one customer per line (name, number of items, arrival time). For example:
Sam 17 2 Ben 4 6 Norman 11 9 Bruce 2 11 Diane 9 15 Carla 3 16 Lenore 14 18 ...etc...
Your output should be a list of customers in the order they finished checking out. The format will be the same, except for an additional column that gives the wait time for each customer. Note that this order will often be different than the input order because some customers may move through the lines more quickly (e.g., through the express lines).
While you are developing and debugging your simulator, feel free to add extra output that helps you understand what's going on. When you submit, however, make sure the only output is the sequence of customers as they finish checking out.
I recommend that you implement this project as three classes: customer,
queue, and supermarket. For each class you should have
a header file that contains the class declaration and a cpp file that contains
the method impelementations.
The queue class is the central data structure used in this assignment, so I want you to focus on designing a clean, modular interface. The goal is to provide the queue capabilities without exposing the details of the implementation (i.e., whether it uses an array or a linked list). The public methods of your queue class should look like this:
// Constructor queue(); // Add a customer to the back of the line void add(Customer * c); // Remove the customer at the front of the line Customer * remove(); // Return the front customer (without removing them) Customer * front(); // Return the length of the queue int length(); // Return true if the queue is empty bool empty();}
Notice that you cannot tell from this interface how the queue is implemented -- for example, there are no Node pointers anywhere in the public interface. All of the details are hidden inside the methods, or in private data and private methods.
Notice also that the queue takes and returns Customer pointers. The queue is only responsible for managing those pointers, not creating or deleting customers. That job is up to the main supermarket simulator code.
You can build and test the queue independently just like we do in lab: make a simple main that creates some customers, adds and removes them, and prints out the results.
In addition, you will need a main that asks the user for the configuration and the customer input file. I picture the main function looking like this:
int main() { // -- Ask the user which configuration they want int config; cout << "Enter configuration (1-4): " << endl; cin >> config; if (config >= 1 and config <= 4) { // -- Create a supermarket with that configuration Supermarket * ps = new Supermarket(config); string filename; cout << "Enter customer file name: " << endl; cin >> filename; // -- Load customer data ps->load_customers(filename); // -- Run simulation // All the action happens in here, including printing // customer information as customers leave the line ps->run_simulation(); } else { // -- Not a valid choice cout << "Invalid configuration " << config << endl; } return 0; }
Please comment your code! Add reasonable comments that explain what
each function/method does. Also add comments in the code to explain how it
works. Don't go overboard: the statement t = 0; does not
need a comment that says "Assign the value 0 to variable t". Write things that
are not immediately obvious, or are assumptions required for the code to
work.
Compile frequently!
Don't try to write all the code, and then compile and test it. That's like trying to get a hole-in-one in golf every time you play. No one can do it. What I recommend is that you design the queue and customer interfaces without worrying about their implementation -- remember, you can compile the main and supermarket code with just the queue and customer header files. This approach will also help you decide what you need the queue and customer to do, before you invest a lot of time in coding the implementation.
Next, write and test the queue and customer classes without the simulator. You can write a simple main function that adds and removes a few customers from a queue (like the lab) to make it works before you try to test the whole system.
I also recommend writing a compile script or makefile to build your simulator -- this will make your life easier and avoid annoying mistakes (like forgetting to recompile part of the program).
Testing: I will provide you with a test input file and sample output that you can compare to your output. In addition, you should create your own inputs that test your system -- in particular, try out different mixes of kinds of customers to see how they affect the different configurations.
Can you avoid incrementing time by 1?
Can you design a system that is completely configurable (i.e., we decide the number and kinds of check out lines at runtime)?
Before you start writing any code I would like you to write a document describing, in English, how you're planning to solve the problem. You design document should be detailed, but still high level and informal. Here are the specific questions you should answer:
provide comp15 a1-design design.txt
In part 2 of the assignment you will implement just the simple 1-register Minimart (configuration 1).
provide comp15 a1-minimart main.cpp supermarket.h supermarket.cpp \
queue.h queue.cpp customer.h customer.cpp
Finally, complete the implementation of the three other configurations. Run test files through them and find out which configutations work better. Write a brief summary of your findings in a text file.
provide comp15 a1-full findings.txt main.cpp supermarket.h supermarket.cpp \
queue.h queue.cpp customer.h customer.cpp
Back to Comp15.