Assignment 3: Weasley Barber Shop (40 marks)
Due: Friday, November 10, 2017 (4:00pm)Learning Objectives
The purpose of this assignment is to learn about discrete-event simulation, multi-server systems, loss models, and Markov chains.
Background
The Weasley twins, Fred and George, have opened a new barber shop at Hogwarts. Their shop has two barber chairs for customers to sit in while getting their hair cut, either by Fred (chair 1) or George (chair 2). There are also 3 regular chairs in the waiting room for customers who are waiting for service, in a First-Come-First-Serve fashion.
Customers arrive to the barber shop according to an open-loop continuous-time Poisson process with average rate lambda. If both barber chairs are empty upon arrival, arriving customers choose their barber uniformly at random (since they can't tell the twins apart). If only one barber chair is empty, the customer moves to that chair. If both barber chairs are occupied, then the arriving customer moves to the waiting room, if space is available. If the waiting room is full, the customer leaves in a huff and never returns. If there are waiting customers, they receive service by the next available barber as soon as a barber chair is vacated. The service time for a haircut is exponentially distributed. However, Fred is slightly faster than George at cutting hair. Their respective service rates are mu1 and mu2, with mu1 > mu2.
Technical Requirements
Write a discrete-event simulation (in C, C++, or Java) of the Weasley Barber Shop, using a continuous-time model. Then do the following:
- Use your simulation to determine the proportion of lost customers when lambda = 4.0, mu1 = 3.0, and mu2 = 2.0.
- Conduct a one-factor simulation experiment varying the waiting room size to see the effect on the loss of customers at high load (i.e., 80% or more).
- Use your simulation to compare your results to those for an M/M/2 queue, where the servers have homogeneous rates mu1 = mu2. Comment on your results.
- Use your simulation to compare your results to those for an M/M/1/K queue, where the single server has an aggregate service rate of mu1 + mu2. Comment on your results.
When you are finished, please submit your solution in electronic form to your TA. Your submission should include the source code for your simulation program, a brief user manual describing how to compile and use your simulator, and a description of the results generated using your program. Please remember that assignments are to be done individually, and submitted to your TA on or before the stated deadline. The penalty for late submissions is 4 marks per day (or portion thereof) beyond the deadline.
Grading Rubric
The grading scheme for the assignment is as follows:
- 20 marks for the design and implementation of a proper discrete-event simulator (i.e., main simulation loop, state variables, data structures, random number generation, statistical output, etc)
- 16 marks for simulation results providing answers to each of the tasks specified above (4 marks each, total of 16 marks)
- 4 marks for a clear and concise user manual (at most 1 page) that describes how to compile, configure, and use your simulation program. Make sure to clarify where and how the testing was done (e.g., home, university, office), what works, and what does not. Be honest!
Up to 4 bonus marks will be awarded for an analytical solution (using Markov chains) for the Weasley Barber Shop, which can be used to validate your simulation model.
Tips
- If you need some help getting started, please take a look at Algorithm 1.2.1 in the textbook for the single-server queue. Then think about how to generalize it to a two-server system.
- Multi-server models can be tricky, but the key is to find ways to represent the salient states of the system.
- Loss models differ from some of our previous models, since a portion of the generated workload can be discarded. However, this actually simplifies the state of the system, since the maximum queue size is bounded. Good luck!