?

Pair Project: Elevator Scheduler [電梯調(diào)度算法的實現(xiàn)和測試]?

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	10	800 kg
3	All floors	20	1600 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

?

2.3? 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 floor1 or floor0.

b)??????? 10% of them travel between floors [2, 20], again, Very few people travel between 2 adjacent floors.

?

?

4.???????????????? 作業(yè)步驟

?

作業(yè)	博客要求 (寫1個博客, 附加題的解法寫另一個博客) 博客注明結(jié)對編程人員的名字/或?qū)W號后3位.
看教科書和其它參考書, 網(wǎng)站中關(guān)于結(jié)對編程的章節(jié)。例如: http://www.cnblogs.com/xinz/archive/2011/08/07/2130332.html	照至少一張照片, 展現(xiàn)兩人在一起合作編程的情況。 說明結(jié)對編程的優(yōu)點和缺點。 結(jié)對的每一個人的優(yōu)點和缺點在哪里 (要列出至少三個優(yōu)點和一個缺點)。
看教科書和其它資料中關(guān)于 Information Hiding, interface design, loose coupling 的章節(jié) ?	說明怎樣利用這些好的設(shè)計方法。
看 Design by Contract, Code Contract 的內(nèi)容: http://en.wikipedia.org/wiki/Design_by_contract http://msdn.microsoft.com/en-us/devlabs/dd491992.aspx	描述這些做法的優(yōu)缺點, 說明你是如何把它們?nèi)谌肽愕淖鳂I(yè)中的。
看教科書中，網(wǎng)上有關(guān) unit test 的內(nèi)容 http://www.cnblogs.com/xinz/archive/2011/11/20/2255830.html ?	通過截屏顯示你是如何用VS 的 unit test 來保證你寫的類的質(zhì)量的。顯示unit test 對你的寫的類 (class) 的覆蓋率
閱讀有關(guān) UML 的內(nèi)容	畫出UML 圖顯示各個實體之間的關(guān)系 (畫一個圖即可)
實現(xiàn)你的算法	說明你的算法的關(guān)鍵 （不必列出源代碼）, 以及獨到之處。 ? 把你的代碼簽入TFS (問老師要權(quán)限及小組的路徑) ?
[附加題]改進電梯調(diào)度的interface? 設(shè)計, 讓它更好地反映現(xiàn)實, 更能讓學(xué)生練習(xí)算法, 更好地實現(xiàn)信息隱藏和信息共享。	目前的設(shè)計有什么缺點, 你會如何改進它?? Analyze the API design, and propose a better API so that Scheduler can have more freedom and students can do more realistic scheduling.?
[附加題] 目前的這個測試程序只有命令行界面, 請給它設(shè)計UI 界面, 顯示乘客/電梯的運動, 并實現(xiàn)之。	Implement a UI to show how people/elevator moves? (write? a? blog to show your code and UI) ?
[附加題]? 閱讀有關(guān) MVC 和? MVVM 設(shè)計模式的文章。	說明你寫的電梯調(diào)度的UI /Algorithm/interface 如何實現(xiàn)了MVC 或MVVM 的算法。
[附加題] 我們現(xiàn)在的題目是假設(shè)所有電梯到達所有的樓層。? 在現(xiàn)實生活中,? 多部電梯到達的樓層都不一樣。如果是這樣 (例如3號電梯能到達10 – 20 層,? 4 號電梯能到達5-15 層)，整個程序框架和你的電梯調(diào)度模塊要做什么改變??	請說明你的改進意見

?

作業(yè)期限: 由老師決定。

?

第二次結(jié)對編程作業(yè) (同學(xué)們重新組合成為新的兩人對)

?

?

1) 以實際項目為例, 完成這一個軟件測試，用戶調(diào)查，項目分析和規(guī)劃的作業(yè):

　　http://www.cnblogs.com/xinz/archive/2012/03/26/2417699.html?

???? 截止日期: 12/28/2012 晚11:00pm.? (如果你到這時候還沒做, 那熬夜做和第二天做是一樣的，都是0 分。 不交作業(yè)倒扣分。)

?

2)? 有了電梯的調(diào)度算法和電梯的測試模擬框架, 我們可以從數(shù)據(jù)層面模擬并測試算法的正確性和效率。 那么現(xiàn)在我們要加上展現(xiàn)的部分 – 用GUI ?展現(xiàn)電梯系統(tǒng)從運送所有乘客的過程。 想象一幢大樓全都是透明的,? 有許多乘客通過電梯上上下下,? 電梯外墻的指示燈 (通常有上/下)? 兩個標(biāo)識隨著乘客的需求或亮或滅。?

實現(xiàn): ?根據(jù)第一次結(jié)對項目的電梯測試系統(tǒng), 和你自己的調(diào)度模塊 (兩個同學(xué)各帶一個調(diào)度模塊)，任選一種編程語言實現(xiàn) GUI.?

?

能跑起來就是成功!?? 詳細評分標(biāo)準(zhǔn):

1)??? 能完整而準(zhǔn)確地反映調(diào)度算法運行的過程，并動態(tài)顯示系統(tǒng)的基本數(shù)據(jù)? (當(dāng)前活躍的乘客數(shù)量,? 乘客的平均旅行時間, 等)

2)??? 能轉(zhuǎn)換電梯調(diào)度模塊，通過簡單的命令參數(shù)就可以調(diào)用不同模塊進行演示。

3)??? 在程序啟動時，能自動調(diào)節(jié)UI 以適應(yīng)不同的樓層和電梯數(shù)目的限制。

4)??? UI 方面, 樓層, 電梯, 乘客, 指示燈的設(shè)計要讓觀眾看得清楚,? 比例協(xié)調(diào), ?同時有一定的美感。如能支持乘客進出電梯，電梯運行的動畫，則可加分。

5)??? 支持啟動, 暫停，繼續(xù)，結(jié)束等控制。

6)??? 按照 GUI 實現(xiàn)語言的種類分別給程序排序, 鼓勵用比較新的語言/框架來實現(xiàn)。

7)??? 獎勵分數(shù): 如果能支持局部放大, 鼠標(biāo)點擊電梯/乘客能顯示具體數(shù)據(jù);? 如果能設(shè)計API? 讓不同的展示模塊能使用同一個API, 不用重新編譯, 就可以加載不同展示模塊 (特別是用不同的語言實現(xiàn)的展示模塊)

?

演示要求:

1)??? 啟動電梯測試框架程序和測試數(shù)據(jù) (建議數(shù)據(jù)規(guī)模:?? 6 層樓,? 2 部電梯, 10 乘客 ) , 載入調(diào)度算法1, ????

2)??? 同樣啟動電梯測試框架程序和同樣的測試數(shù)據(jù), 載入調(diào)度算法 2 (此算法必須和前一個不同),

3)??? 同時開始運行兩個模擬情景, 查看 GUI 模塊的顯示是否滿足各項評分標(biāo)準(zhǔn)。

4)??? 再載入不同的測試數(shù)據(jù)重復(fù) ( 建議數(shù)據(jù)規(guī)模:?? 10 層樓,? 4 部電梯， 500 人)

?

提交程序/文檔:

1)?? 程序要簽入TFS? 截至日期: 1/9/2013

2)?? 把設(shè)計/源程序架構(gòu)/代碼行數(shù)/運行時的截屏/設(shè)計心得/等等 寫成博客。? 1/9/2013

?

?

總結(jié)

以上是生活随笔為你收集整理的北航 2012 秋季 现代软件工程 两人结对 作业要求的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。