电梯调度算法 - 程序流程图

电工技术 · 发表于 2021-3-29 21:38

不管你是在北上广还是在港澳台，甚至三四线城市，凡是有规模的地区，高楼比比皆是,不管是写字楼，还是大型商城，让你最头痛的就是乘电梯，尤其是在赶时间的时候。

每天早上，那些差5分钟就迟到的程序员，在等电梯时，一般会做两件事：

第一，在心里骂电梯慢；

第二，在心里暗算着电梯调度如何优化；

前者可能是写字楼里上班族惯有的精神类疾病，但后者肯定是程序员的职业病。本文对“骂电梯”不给予任何指导性建议，但说起
电梯调度算法，我觉得还是可以给大家科普一下，好为大家在等电梯之余，打发时间而做出一点贡献。（电梯调度算法可以参考各种硬盘换道算法）

1.问题定义

　电梯大家对于大家已经是很熟悉了，现在存在这样的问题，那就是在繁忙的上下班时间，在每层楼电梯都要停。这显然让很多办公室在高层的同志有点受不了。现在要求是这样：由于这个电梯楼层并不高，所以电梯只在一个楼层停，这样做电梯的每个人都在这个楼层走到自己想去的楼层。那么怎么知道电梯每次在哪个楼层停下来呢？在一楼的时候每个乘客选择自己的目的层，电梯可以快速的自动计算出应停的楼层。这个应停的楼层应该保证这次乘坐电梯的所有乘客的爬楼梯层数之和最少（包括上下楼）。

2.问题分析

　该问题本质上是一个优化问题。首先为这个问题找到一个合适的抽象模型。从问题中可以看出，有两个因素会影响到最后的结果：乘客的数量及需要停的楼层。因此，我们可以从统计到达各层的乘客数目开始分析。

　　假设楼层总共有N层，电梯停在第x层，要去第 i 层的乘客数目总数为total,这样，所爬楼梯的总数就是∑{total*| i - x|}（i = 1 , 2 , …… , N）。因此我们的任务就是找到一个整数x使得∑{total*| 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秒。

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

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

PS：你肯能意识到哪个算法都不是一个最佳方案，只是它确实解决了一定情况的问题，但是对一个优秀的程序员而言，研究各种算法是无比快乐的。也许你下一次面试，就有关于调度算法的问题。

账号		自动登录	找回密码
密码			立即注册

点击投放广告	点击投放广告	奥的斯通用维修手册	点击投放广告	点击投放广告
点击投放广告	点击投放广告	点击投放广告	点击投放广告	点击投放广告

电梯调度算法 - 程序流程图

相关帖子