Elevator Scheduling (1)

下午去吃飯回來搭電梯時，因為電梯剛好在二樓，我就直接按鈕進去了

當我到了六樓，一出來就發現有人在等電梯，我突發奇想，思考一個可能性，就是會不會他們其實剛好正要按電梯按鈕，但是就只是差那麼個幾秒鐘，導致我先搶到電梯了？

那麼假如今天剛好相反過來，我慢了一點，電梯明明在二樓，我就只能眼睜睜看著它先到六樓再下來載我嗎？

我開始思考延遲電梯反應時間的可能性

讓可能只是誤差非常小的時間範圍內，可以讓慢了一點的我還是可以先搭到電梯，然後到了六樓以後再換六樓的人搭下來，結果光是在Word上邊寫邊想就花了我兩個小時左右的時間，以下是我的思考結果，之前在圖書館搭電梯就曾經對三部電梯的調度提過問題，可惜當時沒有那麼無聊好好思考和紀錄，現在就可以當參考了

有聽過電梯演算法 (Elevator Algorithm)，還有個有名的人物 Theresa Christy，會不會其實這個問題早就克服了呢？

情境：目前電梯正位於1F，當一位使用者正準備按下電梯向上按鈕進入電梯，由於6F亦有乘客愈搭乘電梯下樓，假設兩造於相差半秒內的時間按下電梯按鈕，事實是6F乘客較晚按下按鈕，則電梯可能因為反應時間快速，使得收到6F訊號以後立即向上，1F乘客需等待6F使用者下樓以後方可上樓

相關數據假設：

按鈕時間差 0.5 sec

電梯反應時間 0.1 sec (電梯接收到按鈕訊號並判斷該打開門讓1F乘客進入或是上樓的處理時間)

電梯自 1F 至 6F運行時間 15 sec

電梯門開門或關門時間 2 sec

乘客進或出電梯時間(在此假設兩樓層各只有一位乘客，且在進入電梯後立刻按下樓層按鈕) 2 sec

1F乘客 P1

6F 乘客 P6

電梯完成運送兩位乘客抵達愈前往樓層總耗時：

= 第一位乘客按下按鈕 至 送最後一位乘客抵達樓層並開啟門使其離開

= 電梯反應時間 + 電梯總運行時間 + 電梯開關門總時間 + 乘客進出電梯時間

= 0.1 + 15 x 3 (上樓2次，下樓1次) +  2 x 5 (*1) + 2 x 4 (兩位乘客各進與出1次) 

= 63.1 sec

乘客等待時間(從乘客按下按鈕開始至乘客抵達愈前往樓層*2):

P1 等待時間

= 電梯運行至6F + 電梯於6F開關門總時間 + P6進出總時間 + 電梯運行至1F + P1進出總時間 + 電梯於1F開關門總時間 + 電梯運行至6F + 電梯於6F 開門時間 (*3)

= (15 – 0.4 (*4))+ 2 x 2 (開關各一次) + 2 x 2 (6F進，1F出) + 15 + 2 x 2 (1F進，6F出) + 2 x 2 (開關各一次) + 15 + 2

= 62.6 sec

P6等待時間

= 電梯反應時間 + 電梯運行至6F時間 + 電梯於6F開關門總時間 + P6進出總時間 + 電梯運行至1F + 電梯於1F開門時間

= 0.1 + 15 + 2 x 2 + 2 x 2+ 15 + 2

= 40.1 sec

平均等待時間 = (63 + 40.1) ÷ 2 = 51.55 sec

改善想法：由以上討論可發現，電梯反應時間對於一位乘客的等待時間影響並不是很大，所以假如增加電梯反應時間至1 sec，企圖使電梯可在較慢的乘客也按下電梯按鈕以後，再做出判斷(因為較慢的乘客會是在0.5sec時按下按鈕，電梯則是在1sec時完成判斷)，如此一來，便可以於第一次由1F運行至6F時服務1F乘客抵達6F

改善後電梯完成運送兩位乘客抵達愈前往樓層總耗時：

= 第一位乘客按下按鈕 至 送最後一位乘客抵達樓層並開啟門使其離開

= 電梯反應時間 + 電梯總運行時間 + 電梯開關門總時間 + 乘客進出電梯時間

= 1 + 15 x 2 (上下樓各1次) +  2 x 5 (*5) + 2 x 4 (兩位乘客各進與出1次) 

= 49 sec

乘客等待時間(從乘客按下按鈕開始至乘客抵達愈前往樓層)：

P1 等待時間

= 電梯反應時間(*6) + 電梯於1F開關門總時間 + P1進出總時間 + 電梯運行至 6F時間 + 電梯於 6F 開門時間

= 0.5 + 2 x 2 + 2 x 2 + 15 + 2

= 25.5 sec

P6等待時間

= 電梯反應時間 + 電梯於1F開關門總時間 + P1進出總時間 + 電梯運行至 6F 時間 + 電梯於6F 開關門時間 + P6 進出總時間 + 電梯運行至1F 時間 + 電梯於 1F 開門時間

= 1 + 2 x 2 + 2 x 2 + 15 + 2 x 2 + 2 x 2 + 15 + 2

= 49 sec

改善後平均等待時間 = (25.5 + 49) ÷ 2 = 37.25 sec

 ------------------------------------------------------------------------------------------------------------ 

*1  第一次抵達6F，開與關各一次，接著抵達1F，開與關各一次，第二次抵達6F，僅計算開門時間，故計一次，所以總共是5次

*2 與作業系統討論的不同，這裡的討論包含了運送乘客時間(CPU Turnaround Time)      

*3 P1因為較慢按下按鈕，此時電梯已經完成反應，因此P1無須等待電梯反應時間       

*4 電梯開始移動是第一個乘客按下之後的0.1秒，從這0.1秒到第二位乘客按下按鈕間的0.4秒，電梯已經移動了一段時間，所以要從電梯運行至6F的15秒鐘扣掉這0.4秒

*5 因為電梯會判斷成應該先在1F開門載客，所以於1F開與關各一次，抵達6F開與關各一次，第二次回到1F時開門一次

*6 對於P1而言，他按下按鈕的時間是電梯反應時間開始之後過了0.5秒，因此實際上他的等待時間只有0.5秒