In business or scientific contexts, it's sometimes very costly to make changes to the way that you're doing things, yet sometimes the changes you consider might yield great benefits; but sometimes, you don't know if they'll yield those benefits without some experimentation. But if the experimentation is too costly, you might never be willing to pay the cost of finding out whether the changes you're considering are worthwhile or not.
Computers have a role to play in situations like this. If you can write a program that will show you how things would be different after you make your changes, and compare that result to how things are now, you can more cheaply find the answer you're looking for — should I make this change or not? — and, if it turns out to be a positive change, you can proceed with making it happen.
In this project, we'll consider a situation like this one. Suppose that the movie theater chain Millennium Cinemas is interested in finding ways to attract customers away from their larger, more well-established rivals. With the proliferation of "megaplex" movie theaters during the last couple of decades, Millennium management believes that one problem that movie-goers face is the long wait in line to buy tickets. They seek a solution that will allow their customers to spend less time in line, hoping that this will dramatically improve their sales. It's not in their best interest to spend a lot of time running experiments, especially since some of the things they might want to try could well end up lengthening their customers' waits in line, ultimately hurting their business. (When you're a large company, you can spend money trying things that might have a negative impact, absorb the loss, and move on. When you're small, you don't have this kind of freedom.)
So, to aid in their analysis of the time that customers spend in line, you'll build a program that will simulate various arrangements of lines and ticket windows, to allow them to find the optimal combinations for its theaters. The project will give you practice implementing queues, as well as introduce you to the concept of a simulation, a program that approximates a real-world situation (in this case, the movement of customers as they arrive at the theater, stand in line, and buy tickets) and keeps track of statistics about it. You'll also have a chance to gain some design skills, as you'll be starting this project from scratch. Don't worry, though; we'll give you plenty of help along the way.
Millennium requires a program that will allow them to simulate a variety of arrangements of ticket lines, ticket windows, and patterns of customer arrival. You will write a program that gives them this flexible simulation ability. It will allow the user to specify the number of ticket windows, whether there will be a single line or one per window, and the speed at which each ticket attendant can process customers. Once these simulation parameters have been specified, the program processes a file that indicates the arrival of customers, simulating their arrival into the ticket lines, tracking how long each customer spends in line, and ultimately calculating statistics about them.
Millennium has many different styles of theaters, from single-screen theaters showing classic or foreign films to larger multi-screen varieties showing the latest releases. To support its various sizes and styles of theaters, it wishes to investigate two arrangements of ticket windows and lines:
For each arrangement of lines, they will also be interested in investigating the number of windows necessary to support various numbers and patterns of customers. They will use the simulator to determine the contexts in which each arrangement will be appropriate.
In order to simulate different types of theaters, the simulator will need to accept a set of parameters, specified in an input file. The input file specifies the number of ticket windows, and whether there is a single ticket line or a separate line for each window. In addition, the input file will contain a list of customer arrivals, specifying how many customers will arrive at the theater at which times. Here is an example of an input file. The italicized portions are included here for descriptive purposes, and should not be included in the actual input file. See image.
The input file is broken into two parts: the setup section, which describes the arrangement of ticket windows and lines, and the customer arrival section, which lists the arrival of customers.
The first line of the setup section is a brief description, perhaps a sentence or so, that explains the purpose of the simulation. The next line specifies the length of the simulation. Following that, the next line specifies how many ticket windows there will be during the simulation. This is followed by either "S" or "M" on a line by itself, which specifies whether there is a single ticket line or one ticket line per window. Finally, there is a line for each of the windows — they should be numbered from 1..n — that states how many seconds it takes the attendant at that window to sell a ticket to a single customer.
There must be a positive number (i.e., greater than zero) of ticket windows, though there is no pre-defined maximum. The number of seconds that each attendant takes to process a customer must also be a positive number.
After reading the setup section, the simulator should be ready to begin processing the arrival and departure of customers, so any applicable data structures should have been created and initialized appropriately.
Each line in the customer arrival section of the input file describes the arrival of a number of customers at a particular time. The time is specified as the number of seconds since the simulation started, and they must increase as the file is processed (i.e., the time on each line in the file must be greater than the time on the line that came before it). The number of customers must be positive.
When customers arrive, they get into one of the ticket lines. If there is only a single line, obviously they get into that line. If there are multiple lines, each customer should be processed one by one; each one should get into the line which has the fewest number of customers already in it. In the event of a tie, they should always get into the one corresponding to the lowest-numbered window. There is no maximum number of customers that can be in a particular line.
When a window is unoccupied, a customer immediately moves from its corresponding ticket line to the window. That customer will stay for the appropriate number of seconds. At that time, the customer will leave the window and will immediately be replaced by another.
For the sake of simplicity, we'll assume for our simulator that customers may not move from one ticket line to another. In other words, suppose there is one ticket line per window. If there is no one at the first window and no one in the first line, but there are three customers in the second line, we will assume that the customers in the second line will not go to the first window. (Obviously, this is a non-issue when there is only one single line.)
You may assume that the input file is formatted as described above. You may not assume that it will be exactly the file that we're showing as an example, but you may assume that there won't be a word where a number is expected, and that there will always be exactly two integers on a line that's supposed to have two integers. Further, you may assume that other restrictions, such as customer arrivals being in ascending order with respect to time, will hold.
The name of the input file should be specified as a command-line argument. The class with your main() method should be called Simulator, so we'll be able to run your program in a predictable way.
When the simulation is complete, your simulator should print out the final report. The final report prints out some summary statistics about the simulation to System.out. The final report must contain the following information:
What follows is a step-by-step explanation of the processing of the example file shown in the previous section. At the conclusion of the example, the statistics are shown. All times are reported in terms of seconds. The final output of your program does not need to look like this, but I do suggest that you include something like this in your program's output; there is simply no way you'll get the final statistics to come out correctly if customers aren't moving to the right places at the right times during the simulation. (This also provides us the ability to give you partial credit if you're not able to get the entire program finished; as problems get more complex, it's worth considering ways to reach stable ground and have partial solutions working, and this partial output is a great example of that.) See image.
These are the statistics that you should see after processing the example file. Note that the decimal numbers may be off by a hundredth in some cases for you, depending on how (and whether) you handle rounding, and that's fine.
To test your simulation, you'll want to run more examples than just the one example file that I provided. However, I'm only going to be providing you with the one example. Part of the goal of writing a program is to find a way to be sure that it works; that means that you need to test it. In the case of a simulation, that means you need to come up with some interesting inputs, figure out for yourself what the output should be, then see if your program generates the right output. That's part of what I'm expecting you to do for this project, though you will not be required to submit your additional input files. In fact, because it can be an arduous task to build input files and figure out what their expected output is, I encourage you to share your input files and expected outputs with one another, so that everyone can benefit from one another's insights about testing the program.
There are many ways that you could implement your simulator, and I will not impose any particular one on you, though I will make a few specific requirements. For the most part, you're on your own for this project. However, here are some suggestions which might help you get started, along with a few design requirements.
A somewhat simplistic, but often effective, way to break a large design into classes is to consider a description of the desired system and "look for the nouns." While this technique won't give you a complete or perfect design, it will at least give you a good feel for what the major abstractions in your program are. Using that approach for this program, you might discover some of the following ideas (and probably others). Of course, depending on how you describe your program, you may discover different abstractions than these.
You are required to build a queue class for this project and use it to implement your ticket line. The queue should be generic (e.g., Queue) so that it could be used in other programs. It is required to be implemented as a linked list, with the major operations (enqueue, dequeue, and front) written so that they will run in O(1) time.
Separately, you'll probably find the need to define a ticket line class that specifically deals with customers and keeps track of the statistics that are necessary for this program. (There are two reasons why it's wise to separate the queue from the ticket line: so that the queue can be reused in other programs and so that you can separate the logic that stores and manipulates the queue of customers from the logic that tracks the statistics.)
Your program should load the setup information from the input file first, and then setup the simulation (i.e., create the theater object with the appropriate initial state) based on those values. From there, you can implement the simulation in various ways, but I suggest the following approach. (This is by no means the most efficient way to implement such a simulation, but is efficient enough for our purposes, striking a good balance between efficiency and ease of implementation for this course.)
Write a simulation loop, each iteration of which simulates one second. Each second, the loop performs the following major tasks:
When the specified number of seconds of simulation time elapse, the simulation ends, and the accumulated statistics should be printed out.
You may not load all of the customer arrivals into memory at the beginning of the simulation. Instead, you should read the customer arrivals into memory one line at a time, when necessary. Reading all of the customer arrivals into memory ahead of time will yield a substantial penalty on your Quality of solution score for this project.
To satisfy the testing portion of this project, write a JUnit-based test class that tests your Queue implementation. It is not necessary to test other parts of your program, but you're welcome to test anything else you wish using JUnit.
One thing to understand about unit testing is that how you design your program has a big effect on whether unit tests are easy (or even possible) to write. This is a positive feedback loop: a design that permits unit tests to be written is one that is usually, on balance, better than the alternative. Consider ways that you can make as much of your code unit-testable as possible.
You must implement your own linked list functionality. You may not use pre-existing linked list implementations, such as java.util.LinkedList in your solution. If you'd like, you may reuse your LinkedList class from previous projects, though you will need to make it a singly-linked list with both head and tail references, so that the various queue operations will run in constant time; you may also need to add one or more methods to it.