據(jù)說程序員等電梯的時候都想過調(diào)度算法
作者：SUN's Cabin
鏈接：https://www.cnblogs.com/jianyungsun/archive/2011/03/16/1986439.html
1、傳統(tǒng)電梯調(diào)度算法
1.1先來先服務(wù)算法(FCFS)
先來先服務(wù)(FCFS-First Come First Serve)算法，是一種隨即服務(wù)算法，它不僅僅沒有對尋找樓層進(jìn)行優(yōu)化，也沒有實(shí)時性的特征，它是一種最簡單的電梯調(diào)度算法。
它根據(jù)乘客請求乘坐電梯的先后次序進(jìn)行調(diào)度。此算法的優(yōu)點(diǎn)是公平、簡單，且每個乘客的請求都能依次地得到處理，不會出現(xiàn)某一乘客的請求長期得不到滿足的情況[12]。
這種方法在載荷較輕松的環(huán)境下，性能尚可接受，但是在載荷較大的情況下，這種算法的性能就會嚴(yán)重下降，甚至惡化。
人們之所以研究這種在載荷較大的情況下幾乎不可用的算法，有兩個原因：
任何調(diào)度算法在請求隊列長度為1時，請求速率極低或相鄰請求的間隔為無窮大時使用先來先服務(wù)算法既對調(diào)度效率不會產(chǎn)生影響，而且實(shí)現(xiàn)這種算法極其簡單。
先來先服務(wù)算法可以作為衡量其他算法的標(biāo)準(zhǔn)。
1.2最短尋找樓層時間優(yōu)先算法(SSTF)
最短尋找樓層時間優(yōu)先(SSTF-Shortest Seek Time First) [14]算法，它注重電梯尋找樓層的優(yōu)化。
最短尋找樓層時間優(yōu)先算法選擇下一個服務(wù)對象的原則是最短尋找樓層的時間。這樣請求隊列中距當(dāng)前能夠最先到達(dá)的樓層的請求信號就是下一個服務(wù)對象。
在重載荷的情況下，最短尋找樓層時間優(yōu)先算法的平均響應(yīng)時間較短，但響應(yīng)時間的方差較大，原因是隊列中的某些請求可能長時間得不到響應(yīng)，出現(xiàn)所謂的“餓死”現(xiàn)象。
1.3掃描算法(SCAN)
掃描算法(SCAN)是一種按照樓層順序依次服務(wù)請求，它讓電梯在最底層和最頂層之間連續(xù)往返運(yùn)行，在運(yùn)行過程中響應(yīng)處在于電梯運(yùn)行方向相同的各樓層上的請求。
它進(jìn)行尋找樓層的優(yōu)化，效率比較高，但它是一個非實(shí)時算法。掃描算法較好地解決了電梯移動的問題，在這個算法中，每個電梯響應(yīng)乘客請求使乘客獲得服務(wù)的次序是由其發(fā)出請求的乘客的位置與當(dāng)前電梯位置之間的距離來決定的，所有的與電梯運(yùn)行方向相同的乘客的請求在一次電向上運(yùn)行或向下運(yùn)行的過程中完成，免去了電梯頻繁的來回移動。
掃描算法的平均響應(yīng)時間比最短尋找樓層時間優(yōu)先算法長，但是響應(yīng)時間方差比最短尋找樓層時間優(yōu)先算法小，從統(tǒng)計學(xué)角度來講，掃描算法要比最短尋找樓層時間優(yōu)先算法穩(wěn)定。
1.4 LOOK 算法
LOOK算法[18]是掃描算法的一種改進(jìn)。對LOOK算法而言，電梯同樣在最底層和最頂層之間運(yùn)行。
但當(dāng)LOOK算法發(fā)現(xiàn)電梯所移動的方向上不再有請求時立即改變運(yùn)行方向，而掃描算法則需要移動到最底層或者最頂層時才改變運(yùn)行方向。
1.5 SAFT 算法
SATF(Shortest Access Time First)[15,19]算法與SSTF算法的思想類似，唯一的區(qū)別就是SATF算法將SSTF算法中的尋找樓層時間改成了訪問時間。
這是因?yàn)殡娞菁夹g(shù)發(fā)展到今天，尋找樓層的時間已經(jīng)有了很大的改進(jìn)，但是電梯的運(yùn)行當(dāng)中等待乘客上梯時間卻不是人為可以控制。
SATF算法考慮到了電梯運(yùn)行過程中乘客上梯時間的影響。
2、實(shí)時電梯調(diào)度算法
2.1最早截止期優(yōu)先調(diào)度算法
最早截止期優(yōu)先(EDF-Earliest Deadline First)調(diào)度算法是最簡單的實(shí)時電梯調(diào)度算法，它的缺點(diǎn)就是造成電梯任意地尋找樓層，導(dǎo)致極低的電梯吞吐率。
它與FCFS調(diào)度算法類似，EDF算法是電梯實(shí)時調(diào)度算法中最簡單的調(diào)度算法。
它響應(yīng)請求隊列中時限最早的請求，是其它實(shí)時電梯調(diào)度算法性能衡量的基準(zhǔn)和特例。
2.2 SCAN-EDF 算法
SCAN-EDF算法是SCAN算法和EDF算法相結(jié)合的產(chǎn)物。
SCAN-EDF 算法先按照EDF算法選擇請求列隊中哪一個是下一個服務(wù)對象，而對于具有相同時限的請求，則按照SCAN算法服務(wù)每一個請求。
它的效率取決于有相同deadline 的數(shù)目，因而效率是有限的。
2.3 PI 算法
PI(Priority Inversion)算法將請求隊列中的請求分成兩個優(yōu)先級，它首先保證高優(yōu)先級隊列中的請求得到及時響應(yīng)，再搞優(yōu)先級隊列為空的情況下在相應(yīng)的優(yōu)先級隊列中的請求。
2.4 FD-SCAN 算法
FD-SCAN(Feasible Deadline SCAN)[17]算法首先從請求隊列中找出時限最早、從當(dāng)前位置開始移動又可以滿足其時限要求的請求，作為下一次SCAN的方向。
并在電梯所在樓層向該請求信號運(yùn)行的過程中響應(yīng)處在與電梯運(yùn)行方向相同且電梯可以經(jīng)過的請求信號。
這種算法忽略了用SCAN算法相應(yīng)其它請求的開銷，因此并不能確保服務(wù)對象時限最終得到滿足。
3、電梯調(diào)度的高水平研究
以上兩個小結(jié)介紹了幾種在目前本人的能力上能進(jìn)行研究的、簡單的電梯調(diào)度算法。但是并不是說目前電梯調(diào)度只發(fā)展到這個層次。
目前電梯的控制技術(shù)已經(jīng)進(jìn)入了電梯群控的時代。
隨著微機(jī)在電梯系統(tǒng)中的應(yīng)用和人工智能技術(shù)的發(fā)展，智能群控技術(shù)得以迅速發(fā)展起來。
由此，電梯的群控方面陸續(xù)發(fā)展出了一批新方法，包括：基于專家系統(tǒng)的電梯群控方法、基于模糊邏輯的電梯群控方法、基于遺產(chǎn)算法的電梯群控方法、基于勝景網(wǎng)絡(luò)的電梯群控方法和基于模糊神經(jīng)網(wǎng)絡(luò)的電梯群控方法。
4、電梯問題的需求分析
4.1 電梯的初始狀態(tài)
本人設(shè)置的電梯的初始狀態(tài)，是對住宅樓的電梯的設(shè)置。
建筑共有21層，其中含有地下一層（地下一層為停車場及貨物運(yùn)送場所）。
建筑內(nèi)部設(shè)有兩部電梯，編號分別為A梯、B梯。
電梯內(nèi)部有23個按鈕，其中包括開門按鈕、關(guān)門按鈕和樓層按鈕，編號為-1，1，2，3，4……20。
電梯外部含有兩個按鈕，即向上運(yùn)行按鈕和向下運(yùn)行按鈕。建筑頂層與地下一層例外，建筑頂層只設(shè)置有向下運(yùn)行按鈕，地下一層只設(shè)置有向上運(yùn)行按鈕。
電梯開關(guān)門完成時間設(shè)定為1秒。電梯到達(dá)每層后上下人的時間設(shè)定為8秒。電梯從靜止開始運(yùn)行到下一層的時間設(shè)置為2秒，而運(yùn)行中通過一層的時間為1秒。
在凌晨2：00——4：30之間，如若沒有請求信號，A梯自動停在14層，B梯自動停在6層。
當(dāng)電梯下到-1層后，如果沒有請求信號，電梯自動回到1層。
4.2 電梯按鈕功能
電梯內(nèi)部的樓層按鈕：電梯內(nèi)部對應(yīng)每一個樓層的按鈕成為樓層按鈕，即本章第一節(jié)提到的編號為-1，1，2，3，4……20的按鈕。
當(dāng)乘客進(jìn)入電梯后按下樓層按鈕，此按鈕顯示灰色，代表不可以用。這樣就表示乘客將要去往此層，電梯將開往相應(yīng)層。當(dāng)電梯到達(dá)該層后，按鈕恢復(fù)可以使用狀態(tài)。
電梯內(nèi)部開門按鈕：當(dāng)電梯達(dá)到乘客想要去往的某樓層后，乘客需要準(zhǔn)備離開電梯，當(dāng)電梯停穩(wěn)后，乘客可以按下開門按鈕，電梯門將打開，讓用戶離開。
如若電梯到了乘客曾經(jīng)按下的樓層，但是無乘客按開門按鈕，電梯將自動在停穩(wěn)后1秒后自動開門。
電梯內(nèi)部關(guān)門按鈕：當(dāng)所有想要乘坐電梯的乘客都進(jìn)入電梯以后，準(zhǔn)備讓電梯開始運(yùn)行的時候，乘客需要按下關(guān)門按鈕，讓電梯門關(guān)閉，使電梯進(jìn)入運(yùn)行狀態(tài)。設(shè)置電梯的自動關(guān)門時間為8秒。
電梯外部向上按鈕：此按鈕表示上樓請求，當(dāng)按下此按鈕時，如果電梯到達(dá)按下此按鈕的樓層，且電梯運(yùn)行方向是向上的，那么電梯響將停下，并在電梯停穩(wěn)之后自動開門，此請求被響應(yīng)后，取消此請求信號。
電梯外部向下按鈕：此按鈕表示下樓請求，當(dāng)按下此按鈕時，如果電梯到達(dá)按下此按鈕的樓層，且電梯運(yùn)行方向是向下的，那么電梯響將停下，并在電梯停穩(wěn)之后自動開門，此請求被響應(yīng)后，取消此請求信號。
推薦閱讀：
完全整理 | 365篇高質(zhì)技術(shù)文章目錄整理
專注服務(wù)器后臺技術(shù)棧知識總結(jié)分享
歡迎關(guān)注交流共同進(jìn)步