电梯调度算法总结

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)是一种按照楼层顺序依次服务请求，它让电梯在最底层和最顶层之间连
续往返运行，在运行过程中响应处在于电梯运行方向相同的各楼层上的请求。它进行寻找
楼层的优化，效率比较高，但它是一个非实时算法。扫描算法较好地解决了电梯移动的问
题，在这个算法中，每个电梯响应乘客请求使乘客获得服务的次序是由其发出请求的乘
客的位置与当前电梯位置之间的距离来决定的，所有的与电梯运行方向相同的乘客的请
求在一次电向上运行或向下运行的过程中完成，免去了电梯频繁的来回移动[2]。
扫描算法的平均响应时间比最短寻找楼层时间优先算法长，但是响应时间方差比最短寻
找楼层时间优先算法小，从统计学角度来讲，扫描算法要比最短寻找楼层时间优先算法
稳定。

1.4 LOOK 算法

LOOK 算法[18]是扫描算法的一种改进。对 LOOK 算法而言，电梯同样在最底层和最顶层
之间运行。但当 LOOK 算法发现电梯所移动的方向上不再有请求时立即改变运行方向，而
扫描算法则需要移动到最底层或者最顶层时才改变运行方向。

1.5 SAFT 算法

SATF(Shortest Access Time First)[15,19]算法与 SSTF 算法的思想类似，唯一的区别
就是 SATF 算法将 SSTF 算法中的寻找楼层时间改成了访问时间。这是因为电梯技术发展