不管你是在北上廣還是在港澳臺，甚至三四線城市，凡是有規(guī)模的地區(qū)，高樓比比皆是。
不管是寫字樓，還是大型商城，讓你最頭痛的就是乘電梯，尤其是在趕時間的時候。
每天早上，那些差5分鐘就遲到的程序員，在等電梯時，一般會做兩件事：
第一，在心里罵電梯慢；
第二，在心里暗算著電梯調(diào)度如何優(yōu)化；
前者可能是寫字樓里上班族慣有的精神類疾病，但后者肯定是程序員的職業(yè)病。
本文對“罵電梯”不給予任何指導(dǎo)性建議。
但說起電梯調(diào)度算法，我覺得還是可以給大家科普一下，好為大家在等電梯之余，打發(fā)時間而做出一點貢獻。
傳統(tǒng)電梯調(diào)度算法
1.1 先來先服務(wù)算法（FCFS）
先來先服務(wù)（FCFS-First Come First Serve）算法，是一種隨即服務(wù)算法，它不僅僅沒有對尋找樓層進行優(yōu)化，也沒有實時性的特征，它是一種最簡單的電梯調(diào)度算法。
它根據(jù)乘客請求乘坐電梯的先后次序進行調(diào)度。此算法的優(yōu)點是公平、簡單，且每個乘客的請求都能依次地得到處理，不會出現(xiàn)某一乘客的請求長期得不到滿足的情況。
這種方法在載荷較輕松的環(huán)境下，性能尚可接受，但是在載荷較大的情況下，這種算法的性能就會嚴重下降，甚至惡化。
人們之所以研究這種在載荷較大的情況下幾乎不可用的算法，有兩個原因：
任何調(diào)度算法在請求隊列長度為1時，請求速率極低或相鄰請求的間隔為無窮大時使用先來先服務(wù)算法既對調(diào)度效率不會產(chǎn)生影響，而且實現(xiàn)這種算法極其簡單。
先來先服務(wù)算法可以作為衡量其他算法的標準。
1.2 最短尋找樓層時間優(yōu)先算法（SSTF）
最短尋找樓層時間優(yōu)先（SSTF-Shortest Seek Time First）算法，它注重電梯尋找樓層的優(yōu)化。
最短尋找樓層時間優(yōu)先算法選擇下一個服務(wù)對象的原則是最短尋找樓層的時間。
這樣請求隊列中距當前能夠最先到達的樓層的請求信號就是下一個服務(wù)對象。
在重載荷的情況下，最短尋找樓層時間優(yōu)先算法的平均響應(yīng)時間較短，但響應(yīng)時間的方差較大，原因是隊列中的某些請求可能長時間得不到響應(yīng)，出現(xiàn)所謂的“餓死”現(xiàn)象。
1.3 掃描算法（SCAN）
掃描算法（SCAN） 是一種按照樓層順序依次服務(wù)請求，它讓電梯在最底層和最頂層之間連續(xù)往返運行，在運行過程中響應(yīng)處在于電梯運行方向相同的各樓層上的請求。
它進行尋找樓層的優(yōu)化，效率比較高，但它是一個非實時算法。掃描算法較好地解決了電梯移動的問題，在這個算法中，每個電梯響應(yīng)乘客請求使乘客獲得服務(wù)的次序是由其發(fā)出請求的乘客的位置與當前電梯位置之間的距離來決定的。
所有的與電梯運行方向相同的乘客的請求在一次電向上運行或向下運行的過程中完成，免去了電梯頻繁的來回移動。
掃描算法的平均響應(yīng)時間比最短尋找樓層時間優(yōu)先算法長，但是響應(yīng)時間方差比最短尋找樓層時間優(yōu)先算法小，從統(tǒng)計學(xué)角度來講，掃描算法要比最短尋找樓層時間優(yōu)先算法穩(wěn)定。
1.4 LOOK 算法
LOOK 算法是掃描算法（SCAN）的一種改進。對LOOK算法而言，電梯同樣在最底層和最頂層之間運行。
但當 LOOK 算法發(fā)現(xiàn)電梯所移動的方向上不再有請求時立即改變運行方向，而掃描算法則需要移動到最底層或者最頂層時才改變運行方向。
1.5 SATF 算法
SATF（Shortest Access Time First）算法與 SSTF 算法的思想類似，唯一的區(qū)別就是 SATF 算法將 SSTF 算法中的尋找樓層時間改成了訪問時間。
這是因為電梯技術(shù)發(fā)展到今天，尋找樓層的時間已經(jīng)有了很大地改進，但是電梯的運行當中等待乘客上梯時間卻不是人為可以控制。
SATF 算法考慮到了電梯運行過程中乘客上梯時間的影響。
實時電梯調(diào)度算法
2.1 最早截止期優(yōu)先調(diào)度算法
最早截止期優(yōu)先（EDF-Earliest Deadline First）調(diào)度算法是最簡單的實時電梯調(diào)度算法，它的缺點就是造成電梯任意地尋找樓層，導(dǎo)致極低的電梯吞吐率。
它與 FCFS 調(diào)度算法類似，EDF 算法是電梯實時調(diào)度算法中最簡單的調(diào)度算法。
它響應(yīng)請求隊列中時限最早的請求，是其它實時電梯調(diào)度算法性能衡量的基準和特例。
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）算法首先從請求隊列中找出時限最早、從當前位置開始移動又可以買足其時限要求的請求，作為下一次 SCAN 的方向。
并在電梯所在樓層向該請求信號運行的過程中響應(yīng)處在與電梯運行方向相同且電梯可以經(jīng)過的請求信號。
這種算法忽略了用 SCAN 算法相應(yīng)其它請求的開銷，因此并不能確保服務(wù)對象時限最終得到滿足。
電梯調(diào)度高水平研究
以上兩結(jié)介紹了幾種簡單的電梯調(diào)度算法。
但是并不是說目前電梯調(diào)度只發(fā)展到這個層次。目前電梯的控制技術(shù)已經(jīng)進入了電梯群控的時代。
隨著微機在電梯系統(tǒng)中的應(yīng)用和人工智能技術(shù)的發(fā)展，智能群控技術(shù)得以迅速發(fā)展起來。
由此，電梯的群控方面陸續(xù)發(fā)展出了一批新方法，包括：基于專家系統(tǒng)的電梯群控方法、基于模糊邏輯的電梯群控方法、基于遺產(chǎn)算法的電梯群控方法、基于勝景網(wǎng)絡(luò)的電梯群控方法和基于模糊神經(jīng)網(wǎng)絡(luò)的電梯群控方法。
結(jié)束語
你肯能意識到哪個算法都不是一個最佳方案，只是它確實解決了一定情況的問題。
暫無評論，快來評論吧!