如何设计一个电梯调度系统？

背景

最近有朋友问了我一个有意思的开放问题：如何设计一个电梯调度系统？

有两个大概的限制条件：

我们再来分析一下这个开放性问题，试着捋一捋思路。

既然给定了两个限制条件，一个是从管理者角度，一个是从用户角度，那么我们很容易联想到两个点：

从工程角度来说，我最先能想到的就是：

如最短作业优先、最长作业优先、先来先服务、多级反馈队列调度等等。

但这一些调度算法或多或少也存在着它们的问题或短板，在思考过程中，可以对每种情况的优劣进行分析，然后作出判断：「选择 or 淘汰」该方案。

最短寻道时间优先、最长寻道时间优先、扫描算法、循环扫描算法，以及针对扫描算法和循环扫描算法的优化方案：LOOK 和 C-LOOK 算法。

「扫描算法」也被称为电梯算法，从名字和应用上，是比较契合这个题目的。

OK，聊完了工程解，我们还需要再从产品角度来入手思考一些东西。

实际生活中，考虑工程性最佳的同时也需要考虑诸如其他的因素：安全性、易用性和逻辑性等。

比如，对于一个在 4 楼的电梯，有 4 楼和 3 楼的用户同时按了上去 40 楼的电梯，那么对于 4 楼用户来说，本来是要上去，但是却需要先下 3 楼，然后再到 40 楼，这样的逻辑就让人感觉疑惑，甚至担心安全相关的问题。

还有，在实际生活中，电梯的使用是有高峰期的，高峰时段的调度策略和平峰时段的调度策略应该是不一样的。这个问题类似于「秒杀」系统，高峰流量来临的时候，我们需要扩容来应对，在电梯的例子中，就是全部电梯都需要参与到其中来满足用户的用梯需求。

一台电梯的最优解好办，但是多台电梯的最优调度就增加了更大的复杂性。

多个电梯的调度又有点像旅行商问题，本质上这个问题又是个 NP(No Possibility)，即不可能问题，因为随着因素增多，可能性也变多，方案数量也是指数级增长。

我们考虑实现的时候或许得采用贪婪算法，最大程度的利用局部最优解，从而更接近整体最优解。

完全兼顾能耗和用户体验的方案或许很难找到，关键就在于在这二者之间找到那个平衡点。

以上，是我的一些回顾和思考。