Assignment 4: ICT Elevators (40 marks)
Due: Friday, December 1, 2017 (4:00pm)Learning Objectives
The purpose of this assignment is to learn about discrete-event simulation, event-list management, statistical output, and experimental design.
Background
The ICT building has F = 7 floors and normally has N = 3 functional elevators. People arrive to the building at random times and enter on the ground floor (Floor 1) according to a Poisson arrival process with an average aggregate arrival rate of lambda (e.g., lambda = 0.5 people per minute). They request an elevator, enter it, ride upwards, and get off at a floor that is chosen uniformly at random from the remaining (F - 1) floors. They stay at work on that chosen floor for a randomly chosen amount of time (Exponential distribution, with mean 60.0 minutes), before returning to the elevators, requesting one, riding down to Floor 1, and departing from the building. The performance metric of interest is the user-perceived response time, which is the elapsed time between requesting an elevator and getting off at the desired floor (i.e., once on the way up, and once on the way down).
There are many possible variations that can be made to the configuration and operation of elevators: number, speed, capacity, scheduling. Your goal is to explore a small subset of these possibilities, and understand the impact on user-perceived response time.
The "performance" of an elevator depends greatly on its scheduling algorithm. In particular, there are several choices for what an elevator can do when multiple user requests are pending. One choice is to serve requests strictly in timestamp order, called First-Come-First-Serve (FCFS). Another is to service the "closest" request, regardless of the direction being traveled. This is called Shortest-Seek-Time-First (SSTF). Another choice is to only service requests that are in the same vertical direction as is currently being traveled. This is called Linear Scan. The choice among these policies is especially important when load is high.
Another factor affecting elevator performance is its idling policy. That is, there are several choices for what an elevator should do when it is empty: stay where it is, go to the bottom floor, go to the top floor, or go to the "middle" floor. This policy is especially important at light(er) loads, but is less important at higher loads, when the elevator rarely empties.
Your initial simulation experiments will have just a single elevator (N = 1). In terms of other parameter settings, you can assume that F = 7, and that the movement time between adjacent floors of the building is always exactly 10.0 seconds, regardless of occupancy, distance, or direction traveled by the elevator. You can assume that the elevator can hold an unlimited number of people.
Technical Requirements
Write a discrete-event simulation that models the operation of the elevator(s) in the ICT building. Specifically, do the following:
- Design and implement a simulation model of the ICT building elevator(s), using either C, C++, or Java. Parameterize your simulation reasonably, and document any additional assumptions you make. Instrument the simulator adequately so that you can collect the timing information required for your analysis of results.
- For the single-elevator scenario, implement any two of FCFS, SSTF, or Linear Scan as possible scheduling algorithms. Conduct a simulation experiment to see which of these scheduling algorithms is best, in terms of average user-perceived response time. Use only this best scheduling algorithm in your subsequent simulation experiments.
- For N = 1, conduct simulation experiments that evaluate any two of the suggested elevator idling policies (i.e., Stay, Bottom, Middle, Top) to see the impact, if any, on the user-perceived response time. Choose the best such idling policy for your remaining simulation experiments.
- Increase the number of elevators from N = 1 to N = 2. Show the impact, if any, on the user-perceived response time. Justify any additional assumptions or design decisions that you make.
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:
- 16 marks for the design and implementation of a proper discrete-event simulator (i.e., main simulation loop, state variables, event list data structures, random number generation, statistical output, etc)
- 8 marks for simulation results providing answers to the elevator scheduling task
- 4 marks for simulation results providing answers to the elevator idling task
- 8 marks for simulation results providing answers to the two-elevator task
- 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 additional simulation experiments with N = 3 elevators, showing the impact, if any, on user-perceived response time. Summarize your key observations. Justify any additional assumptions or design decisions that you make.
Tips
- There is a LOT to this rather open-ended assignment, so please get started early. It is a bit of a head-banger. Just sayin'.
- You have a lot of flexibility in how you design your simulation, such as the choice between trace-driven, time-stepped, or next-event simulation, as well as discrete-time versus continuous-time models. You decide.
- Think carefully about the important elements of STATE in your system. Make sure that you have appropriate data structures and/or variables to represent the state(s) that you need.
- Design, debug, and test your simulation with just a single elevator (N = 1) initially. Later, you might be able to extend this to N elevators, perhaps by changing scalar state variables (e.g., occupancy, floor, direction) into indexed array variables.
- For initial debugging, it might be worth parameterizing your model to have only F = 2 or F = 3 floors, rather than F = 7. Just a suggestion.
- For debugging purposes, feel free to vary lambda, so that you can test for light load, medium load, and heavy load scenarios. Your final runs should use a reasonable load level (or range of load levels) that provides interesting results.
- The multi-server variations of your basic elevator model are tricky. Make sure you have the single-elevator model fully working and well-understood before you tackle multiple elevators. Good luck!