据说程序员等电梯的时候都想过调度算法

川长思鸟来 2022-12-30 13:51 169阅读 0赞

> **作者：SUN's Cabin**
> 
> **链接：https://www.cnblogs.com/jianyungsun/archive/2011/03/16/1986439.html**

## **![format_png][]** ##

##  ##

##     ##

## **1、传统电梯调度算法** ##

### **1.1先来先服务算法(FCFS)** ###

先来先服务(FCFS-First Come First Serve)算法，是一种随即服务算法，它不仅仅没有对寻找楼层进行优化，也没有实时性的特征，它是一种最简单的电梯调度算法。

它根据乘客请求乘坐电梯的先后次序进行调度。此算法的优点是公平、简单，且每个乘客的请求都能依次地得到处理，不会出现某一乘客的请求长期得不到满足的情况\[12\]。

这种方法在载荷较轻松的环境下，性能尚可接受，但是在载荷较大的情况下，这种算法的性能就会严重下降，甚至恶化。

人们之所以研究这种在载荷较大的情况下几乎不可用的算法，有两个原因：

1.  任何调度算法在请求队列长度为1时，请求速率极低或相邻请求的间隔为无穷大时使用先来先服务算法既对调度效率不会产生影响，而且实现这种算法极其简单。
2.  先来先服务算法可以作为衡量其他算法的标准。

**1.2最短寻找楼层时间优先算法(SSTF)**

最短寻找楼层时间优先(SSTF-Shortest Seek Time First) \[14\]算法，它注重电梯寻找楼层的优化。

最短寻找楼层时间优先算法选择下一个服务对象的原则是最短寻找楼层的时间。这样请求队列中距当前能够最先到达的楼层的请求信号就是下一个服务对象。

在重载荷的情况下，最短寻找楼层时间优先算法的平均响应时间较短，但响应时间的方差较大，原因是队列中的某些请求可能长时间得不到响应，出现所谓的“饿死”现象。

### **1.3扫描算法(SCAN)** ###

扫描算法(SCAN)是一种按照楼层顺序依次服务请求，它让电梯在最底层和最顶层之间连续往返运行，在运行过程中响应处在于电梯运行方向相同的各楼层上的请求。

它进行寻找楼层的优化，效率比较高，但它是一个非实时算法。扫描算法较好地解决了电梯移动的问题，在这个算法中，每个电梯响应乘客请求使乘客获得服务的次序是由其发出请求的乘客的位置与当前电梯位置之间的距离来决定的，所有的与电梯运行方向相同的乘客的请求在一次电向上运行或向下运行的过程中完成，免去了电梯频繁的来回移动。

扫描算法的平均响应时间比最短寻找楼层时间优先算法长，但是响应时间方差比最短寻找楼层时间优先算法小，从统计学角度来讲，扫描算法要比最短寻找楼层时间优先算法稳定。

**1.4 LOOK 算法**

LOOK算法\[18\]是扫描算法的一种改进。对LOOK算法而言，电梯同样在最底层和最顶层之间运行。

但当LOOK算法发现电梯所移动的方向上不再有请求时立即改变运行方向，而扫描算法则需要移动到最底层或者最顶层时才改变运行方向。

### **1.5 SAFT 算法** ###

SATF(Shortest Access Time First)\[15,19\]算法与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)\[17\]算法首先从请求队列中找出时限最早、从当前位置开始移动又可以满足其时限要求的请求，作为下一次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 电梯按钮功能** ##

电梯内部的楼层按钮：电梯内部对应每一个楼层的按钮成为楼层按钮，即本章第一节提到的编号为-1，1，2，3，4……20的按钮。

当乘客进入电梯后按下楼层按钮，此按钮显示灰色，代表不可以用。这样就表示乘客将要去往此层，电梯将开往相应层。当电梯到达该层后，按钮恢复可以使用状态。

电梯内部开门按钮：当电梯达到乘客想要去往的某楼层后，乘客需要准备离开电梯，当电梯停稳后，乘客可以按下开门按钮，电梯门将打开，让用户离开。

如若电梯到了乘客曾经按下的楼层，但是无乘客按开门按钮，电梯将自动在停稳后1秒后自动开门。

电梯内部关门按钮：当所有想要乘坐电梯的乘客都进入电梯以后，准备让电梯开始运行的时候，乘客需要按下关门按钮，让电梯门关闭，使电梯进入运行状态。设置电梯的自动关门时间为8秒。

电梯外部向上按钮：此按钮表示上楼请求，当按下此按钮时，如果电梯到达按下此按钮的楼层，且电梯运行方向是向上的，那么电梯响将停下，并在电梯停稳之后自动开门，此请求被响应后，取消此请求信号。

电梯外部向下按钮：此按钮表示下楼请求，当按下此按钮时，如果电梯到达按下此按钮的楼层，且电梯运行方向是向下的，那么电梯响将停下，并在电梯停稳之后自动开门，此请求被响应后，取消此请求信号。

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

### **推荐阅读** ###

• [吴师兄实名吐槽 LeetCode 上的一道题目。。。][LeetCode]• [面试字节跳动时，我竟然遇到了原题……][Link 1]• [计算机专业的学生怎样练习编程才能把编程学精通？][Link 2]• [为什么 MySQL 使用 B+ 树][MySQL _ B_]• [一道简简单单的字节跳动算法面试题][Link 3]

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

欢迎关注我的公众号“**五分钟学算法**”，如果喜欢，麻烦点一下“**在看**”，点击左下方阅读原文，获取谷歌师兄的算法刷题笔记。

![format_png 1][]

[format_png]: /images/20221120/b31afbd4e9f443428a236703a439d96b.png
[LeetCode]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e75efcd79fcf9c65ebb5070122b9705e18cb1c46b06c5eb3e299520ed4a25e327bc07bb4b&idx=2&mid=2247490158&scene=21&sn=12e587a361f0df072d2dc164c219a61e#wechat_redirect
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e75aecd79fcb8b5f932c7ba5ed7a9e34a6c99f20bc129cef33774167d668e8745755d02ad&idx=1&mid=2247490095&scene=21&sn=baa0379b1ca62db17327a2cb825a1b24#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0d87aacd7a0ebc3ada34a076d1fa3943ee24097966257132b1042b7a3e4debedc78f38c8cf&idx=1&mid=2247493675&scene=21&sn=6b501ef2032ab911f0a3519eb7397017#wechat_redirect
[MySQL _ B_]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e759ccd79fc8a73c77eacfd7c8b1391b08864e2e13fdf5a6e41e218a499d5a87ee12e4e6a&idx=2&mid=2247490077&scene=21&sn=56c52b385c98c7f0ad33c2621da101eb#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e767dcd79ff6b2733dd8905f188afb19eb400d5e644f5b5127f909ee7c3583786031f9c20&idx=2&mid=2247490044&scene=21&sn=bb3610dfedbb2e0c017c3ff3d5e4684b#wechat_redirect
[format_png 1]: /images/20221120/8eecfee2f47f4660af9aa693a2073e7b.png