1.問題定義
電梯大家對于大家已經是很熟悉了，現在存在這樣的問題，那就是在繁忙的上下班時間，在每層樓電梯都要停。這顯然讓很多辦公室在高層的同志有點受不了?，F在要求是這樣：由于這個電梯樓層并不高，所以電梯只在一個樓層停，這樣做電梯的每個人都在這個樓層走到自己想去的樓層。那么怎么知道電梯每次在哪個樓層停下來呢？在一樓的時候每個乘客選擇自己的目的層，電梯可以快速的自動計算出應停的樓層。這個應停的樓層應該保證這次乘坐電梯的所有乘客的爬樓梯層數之和最少（包括上下樓）。
2.問題分析
該問題本質上是一個優化問題。首先為這個問題找到一個合適的抽象模型。從問題中可以看出，有兩個因素會影響到最后的結果：乘客的數量及需要停的樓層。因此，我們可以從統計到達各層的乘客數目開始分析。
假設樓層總共有N層，電梯停在第x層，要去第 i 層的乘客數目總數為total[i],這樣，所爬樓梯的總數就是∑{total[i]*| i - x|}(i = 1 , 2 , …… , N)。因此我們的任務就是找到一個整數x使得∑{total[i]*| i - x|}(i = 1 , 2 , …… , N)的值最小。
2.問題解法
2.1解法一
按照面試的思路是，先考慮最簡單的解決方案，然后優化，那我們也這樣。先來看一個簡單的解法，可以第一層開始枚舉x一直第N層，然后計算如果電梯在第x層停的話所有乘客總共要爬多少層樓。這是最為直接的一個解法。
很容易想到吧，程序代碼就是兩重循環，找到最大值。對于一個問題的解法是枚舉那么，肯定這個解法基本是最容易想，但同時也是效率不太高的解法。這個算法的時間復雜度O(N^2)。
2.2解法二
現在我們來更仔細的分析一下這個問題，看看怎么樣優化一下。假設電梯停在第 i 層樓，我們計算出所有乘客總共爬樓梯的層數是Y。如果有N1個乘客想去的樓層在第 i 層之下，有N2個乘客正好想去的樓層是第 i 層，有N3個乘客想去的樓層在第 i 層之上。這個時候，重點來了：如果電梯改停在i-1層，所有目的地在第i - 1層以下的乘客可以少爬1層，總共少爬N1層，所有在i層及以上的乘客要多爬一層，總共多爬N2+N3層，這時總共需要爬Y-N1+N2+N3。
反之，如果電梯在i+1層停所有目的地在第 i 層以上的乘客可以少爬1層，總共少爬N3層，所有在 i 層及以下的乘客要多爬一層，總共多爬N1+N2層，這時總共需要爬Y+N1+N2-N3層。
可見，當N1 > N2+N3 時，電梯在第i-1層樓停更好；當N1+N2 < N3 時，電梯在i+1層停更好。其他情況在第i層更好。
如此一來，問題的解法就出來了，從第一層開始考察，計算各位乘客走的樓層的數目，然后根據N1，N2，N3之間的關系進行調整，知道找到最佳樓層，這樣算法時間復雜度優化到了O（N）
1.傳統電梯調度算法
1.1 先來先服務算法（FCFS）
先來先服務（FCFS-First Come First Serve）算法，是一種隨即服務算法，它不僅僅沒有對尋找樓層進行優化，也沒有實時性的特征，它是一種最簡單的電梯調度算法。
它根據乘客請求乘坐電梯的先后次序進行調度。此算法的優點是公平、簡單，且每個乘客的請求都能依次地得到處理，不會出現某一乘客的請求長期得不到滿足的情況。
這種方法在載荷較輕松的環境下，性能尚可接受，但是在載荷較大的情況下，這種算法的性能就會嚴重下降，甚至惡化。
人們之所以研究這種在載荷較大的情況下幾乎不可用的算法，有兩個原因：
任何調度算法在請求隊列長度為1時，請求速率極低或相鄰請求的間隔為無窮大時使用先來先服務算法既對調度效率不會產生影響，而且實現這種算法極其簡單。
先來先服務算法可以作為衡量其他算法的標準。
1.2 最短尋找樓層時間優先算法（SSTF）
最短尋找樓層時間優先（SSTF-Shortest Seek Time First）算法，它注重電梯尋找樓層的優化。
最短尋找樓層時間優先算法選擇下一個服務對象的原則是最短尋找樓層的時間。
這樣請求隊列中距當前能夠最先到達的樓層的請求信號就是下一個服務對象。
在重載荷的情況下，最短尋找樓層時間優先算法的平均響應時間較短，但響應時間的方差較大，原因是隊列中的某些請求可能長時間得不到響應，出現所謂的“餓死”現象。
1.3 掃描算法（SCAN）
掃描算法（SCAN） 是一種按照樓層順序依次服務請求，它讓電梯在最底層和最頂層之間連續往返運行，在運行過程中響應處在于電梯運行方向相同的各樓層上的請求。
它進行尋找樓層的優化，效率比較高，但它是一個非實時算法。掃描算法較好地解決了電梯移動的問題，在這個算法中，每個電梯響應乘客請求使乘客獲得服務的次序是由其發出請求的乘客的位置與當前電梯位置之間的距離來決定的。
所有的與電梯運行方向相同的乘客的請求在一次電向上運行或向下運行的過程中完成，免去了電梯頻繁的來回移動。
掃描算法的平均響應時間比最短尋找樓層時間優先算法長，但是響應時間方差比最短尋找樓層時間優先算法小，從統計學角度來講，掃描算法要比最短尋找樓層時間優先算法穩定。
1.4 LOOK 算法
LOOK 算法是掃描算法（SCAN）的一種改進。對LOOK算法而言，電梯同樣在最底層和最頂層之間運行。
但當 LOOK 算法發現電梯所移動的方向上不再有請求時立即改變運行方向，而掃描算法則需要移動到最底層或者最頂層時才改變運行方向。
1.5 SATF 算法
SATF（Shortest Access Time First）算法與 SSTF 算法的思想類似，唯一的區別就是 SATF 算法將 SSTF 算法中的尋找樓層時間改成了訪問時間。
這是因為電梯技術發展到今天，尋找樓層的時間已經有了很大地改進，但是電梯的運行當中等待乘客上梯時間卻不是人為可以控制。
SATF 算法考慮到了電梯運行過程中乘客上梯時間的影響。
2.實時電梯調度算法
2.1 最早截止期優先調度算法
最早截止期優先（EDF-Earliest Deadline First）調度算法是最簡單的實時電梯調度算法，它的缺點就是造成電梯任意地尋找樓層，導致極低的電梯吞吐率。
它與 FCFS 調度算法類似，EDF 算法是電梯實時調度算法中最簡單的調度算法。
它響應請求隊列中時限最早的請求，是其它實時電梯調度算法性能衡量的基準和特例。
2.2 SCAN-EDF 算法
SCAN-EDF 算法是 SCAN 算法和 EDF 算法相結合的產物。SCAN-EDF 算法先按照 EDF 算法選擇請求列隊中哪一個是下一個服務對象，而對于具有相同時限的請求，則按照 SCAN 算法服務每一個請求。它的效率取決于有相同 deadline 的數目，因而效率是有限的。
2.3 PI 算法
PI（Priority Inversion）算法將請求隊列中的請求分成兩個優先級，它首先保證高優先級隊列中的請求得到及時響應，再搞優先級隊列為空的情況下在相應地優先級隊列中的請求。
2.4 FD-SCAN 算法
FD-SCAN（Feasible Deadline SCAN）算法首先從請求隊列中找出時限最早、從當前位置開始移動又可以買足其時限要求的請求，作為下一次 SCAN 的方向。
并在電梯所在樓層向該請求信號運行的過程中響應處在與電梯運行方向相同且電梯可以經過的請求信號。
這種算法忽略了用 SCAN 算法相應其它請求的開銷，因此并不能確保服務對象時限最終得到滿足。
3.電梯調度高水平研究
以上兩結介紹了幾種簡單的電梯調度算法。
但是并不是說目前電梯調度只發展到這個層次。目前電梯的控制技術已經進入了電梯群控的時代。
隨著微機在電梯系統中的應用和人工智能技術的發展，智能群控技術得以迅速發展起來。
由此，電梯的群控方面陸續發展出了一批新方法，包括：基于專家系統的電梯群控方法、基于模糊邏輯的電梯群控方法、基于遺產算法的電梯群控方法、基于勝景網絡的電梯群控方法和基于模糊神經網絡的電梯群控方法。
4.電梯問題的需求分析
4.1 電梯的初始狀態
本人設置的電梯的初始狀態，是對住宅樓的電梯的設置。
(1)建筑共有21層，其中含有地下一層（地下一層為停車場）。
(2)建筑內部設有兩部電梯，編號分別為A梯、B梯。
(3)電梯內部有23個按鈕，其中包括開門按鈕、關門按鈕和樓層按鈕，編號為-1，1，2，3，4……20。
(4)電梯外部含有兩個按鈕，即向上運行按鈕和向下運行按鈕。建筑頂層與地下一層例外，建筑頂層只設置有向下運行按鈕，地下一層只設置有向上運行按鈕。
(5)電梯開關門完成時間設定為1秒。電梯到達每層后上下人的時間設定為8秒。電梯從靜止開始運行到下一層的時間設置為2秒，而運行中通過一層的時間為1秒。
(6)在凌晨2：00——4：30之間，如若沒有請求信號，A梯自動停在14層，B梯自動停在6層。
(7)當電梯下到-1層后，如果沒有請求信號，電梯自動回到1層。
4.2 電梯基本功能
每一架電梯都有一個編號，以方便監控與維修。每一架電梯都有一實時監控器，負責監控電梯上下，向電梯升降盒發送啟動、制動、加速、減速、開關電梯門的信號。若電梯發生故障，還應向相應的電梯負責人發送求救信號。
4.3 電梯按鈕功能
電梯內部的樓層按鈕：電梯內部對應每一個樓層的按鈕成為樓層按鈕，即本章第一結提到的編號為 -1，1，2，3，4……20的按鈕。當乘客進入電梯后按下樓層按鈕，此按鈕顯示灰色，代表不可以用。
這樣就表示乘客將要去往此層，電梯將開往相應層。當電梯到達該層后，按鈕恢復可以使用狀態。
電梯內部開門按鈕：當電梯達到乘客想要去往的某樓層后，乘客需要準備離開電梯，當電梯停穩后，乘客可以按下開門按鈕，電梯門將打開，讓用戶離開。
如若電梯到了乘客曾經按下的樓層，但是無乘客按開門按鈕，電梯將自動在停穩后1秒后自動開門。
電梯內部關門按鈕：當所有想要乘坐電梯的乘客都進入電梯以后，準備讓電梯開始運行的時候，乘客需要按下關門按鈕，讓電梯門關閉，使電梯進入運行狀態。設置電梯的自動關門時間為8秒。
電梯外部向上按鈕：此按鈕表示上樓請求，當按下此按鈕時，如果電梯到達按下此按鈕的樓層，且電梯運行方向是向上的，那么電梯響將停下，并在電梯停穩之后自動開門，此請求被響應后，取消此請求信號。
電梯外部向下按鈕：此按鈕表示下樓請求，當按下此按鈕時，如果電梯到達按下此按鈕的樓層，且電梯運行方向是向下的，那么電梯響將停下，并在電梯停穩之后自動開門，此請求被響應后，取消此請求信號。
