作业提交时间：10月9日上课前。
Design and implement an Elevator Scheduler to aim for both correctness and performance, in managed code.
Skills to learn and practice:
a) Peer to peer collaboration
b) Requirement Analysis
c) Design by contract, Interface design and comprehension
d) Test Driven Development, Unit Test
e) Algorithm design
f) Implementation
1. Background
Imagine we’re building a tall office building, it has the following configuration about elevators:
Building has 21 floors, 4 elevators, many passengers use these elevators everyday (passenger weight: average 70kg. max 120kg, min 45kg).
Other constant data: Elevator speed, door open/close time, passenger time for going in/out of the elevator. We can make reasonable assumptions about these.
The building has 21 floors, from floor 0, 1, ... to 20. Floor 0 is the underground parking level, floor 1 is the lobby level. Most people come in/out the building via these 2 floors.
Elevator name |
Service floor list |
Passenger limit |
Weight limit |
1 |
All floors |
10 |
800 kg |
2 |
All floors |
12 |
1000 kg |
3 |
All floors |
20 |
1500 kg |
4 |
All floors |
20 |
2000 kg |
2. Requirement to Student pairs
A framework with a naive algorithm is prepared and shared to students. The core task for students is to design and implement the scheduling algorithm. Students need to write their own scheduler class (implements the IScheduler interface), Update the SchedulerFactory.CreateScheduler method so the test framework can instantiate your class.
TA will come up with a consistent testing model to test your program according to the “rush hour” scenario (see below), and record the total travel time of each passengers.
Total Travel Time = the time delta between the passenger appears in front of the elevator, and the time she gets off the elevator at this designated floor.
You (student pair) have:
1) A set of API
2) A naive solution (BUS program)
3) A set of test cases to run
Explanation of BUS program:
We can have a naive algorithm called “BUS”. BUS algorithm treats an elevator as a bus, it goes from bottom to top, stops at every floor, opens its door, to let people in and out (if any), then closes the door and moves on. After it reaches the top floor, it will go down and stop at each floor again. This algorithm can serve all requests, but it’s apparently not the fastest algorithm.
Your code is required to be managed code (C#, managed C++, etc).
It has to generate 0 (zero) VS Code Analysis warnings and errors.
It has to be correct
It has to be fast
Score guideline: TA will evaluate the “average total travel time” for all passengers in the same test case, the lower, the better. If your performance is slower than “bus” solution, you get 0 points; if your program can’t deliver any passenger to the correct destination, you get 0 points.
One hint about elevator scheduling: When total weight is within 45 kg of the max limit, or the number of passengers is already at maximum, the elevator doesn’t need to stop for more external requests.
The elevator scheduler program doesn’t know how many passengers are waiting on each floor, it doesn’t know how many passengers will show up either. This is the same with the real world situation.
3. Testing
TA will simulate a “rush hour” (上下班高峰时刻) test. The “rush hour” test is to simulate the come-to-work and leave-work scenario in a business building, which has the following 2 parts (they can be run next to each other).
1) Simple test. 20 passengers
20 people going thru random floors within 5 minutes.
2) Come-to-work. 1000 total passengers
a) 80% of them goes from floor 0 and 1 to all other floors, the destination is distributed evenly. The time each passenger arrives at the elevator can be emulated as a normal distribution.
b) 20% of them are going between any 2 floors of [2, 20], very few people travel between 2 adjacent floors (e.g. from floor 5 to 4). Other than this, the distribution is also even.
3) Leave-work. 1000 total passengers
a) 90% of them go from other floors to floor 1 or floor 0.
b) 10% of them travel between floors [2, 20], again, Very few people travel between 2 adjacent floors.
4. 作业步骤
作业 |
博客要求 (写1个博客，附加题的解法写另一个博客) 博客注明结对编程人员的名字/或学号后3位.
|
|
|
看教科书和其它参考书, 网站中关于结对编程的章节。例如: |
照至少一张照片, 展现两人在一起合作编程的情况。 说明结对编程的优点和缺点。 结对的每一个人的优点和缺点在哪里 (要列出至少三个优点和一个缺点)。 |
|
|
看教科书和其它资料中关于 Information Hiding, interface design, loose coupling 的章节
|
说明怎样利用这些好的设计方法。 |
|
|
看 Design by Contract, Code Contract 的内容: |
描述这些做法的优缺点, 说明你是如何把它们融入你的作业中的。 |
|
|
看教科书中，网上有关 unit test 的内容 http://www.cnblogs.com/xinz/archive/2011/11/20/2255830.html
|
通过截屏显示你是如何用VS 的unit test 来保证你写的类的质量的。显示unit test 对你的写的类(class) 的覆盖率 |
|
阅读有关 UML 的内容 |
画出UML 图显示各个实体之间的关系 (画一个图即可) |
|
实现你的算法 |
说明你的算法的关键 （不必列出源代码）, 以及独到之处。
把你的代码签入TFS (问老师要权限及小组的路径) |
|
[附加题] 改进电梯调度的interface 设计, 让它更好地反映现实, 更能让学生练习算法, 更好地实现信息隐藏和信息共享。 |
目前的设计有什么缺点, 你会如何改进它? Analyze the API design, and propose a better API so that Scheduler can have more freedom and students can do more realistic scheduling. |
|
[附加题] 目前的这个测试程序只有命令行界面, 请给它设计UI界面, 显示乘客/电梯的运动, 并实现之。 |
Implement a UI to show how people/elevator moves (write a blog to show your code and UI)
|
|
[附加题] 阅读有关 MVC 和 MVVM 设计模式的文章。 |
说明你写的电梯调度的UI /Algorithm/interface 如何实现了MVC 或MVVM 的算法。 |
|
[附加题] 我们现在的题目是假设所有电梯到达所有的楼层。 在现实生活中, 多部电梯到达的楼层都不一样。如果是这样 (例如3号电梯能到达10 – 20 层, 4 号电梯能到达5-15 层)，整个程序框架和你的电梯调度模块要做什么改变? |
请说明你的改进意见 |
|