机械师实时调度示例(I) - OptaPlanner实时规划

OptaPlanner创办人Geoffrey De Smet及其团队，在Red Hat 技术峰会上主题会场上，演示了一个通过OptaPlanner实现实时规划与调度的示例。Geoffrey及其团队专门为此分三篇博文描述了该程序。该程序及其相关博文是OptaPlanner在VRP领域极之经典之作。本系列也分三篇对博文进行翻译，以飨各位ORer, APSer和Planner.

目前本人正在研究该程序，未来将会进一步对该程序作更深入的分析，并形成博文，分享其中奥妙。

【以下为译文】

今年，我和我的团队在Red Hat技术峰会上作了主旨演讲。在7000人面前，我们演示了一个实时调度程序，该程序可以实现对现场观众通过手机App的输入进行实时反应。在过去两个月里，我们的团队和其它中间件的团队一起协同，在Burr Sutter的出色指导下，创建了这个实时调度程序。这个程序集成了多种技术，例如Android/iPhone的加速感应器，还有OpenShift / Kubernetes, Quarkus, KNative, TensorFlow, Kafka/Strimzi, Camel, Node.js, Godot, Infinispan, Drools等，当然少不了主角OptaPlanner.

我们写了一个模拟器，模拟一个典型的地板生产场景，场景中涉及装配线上的机械。当我第一次向我和妻子展示这个程序时，引发了一个有趣的对话:

"看，亲爱的，这是在主旨演讲上的示例程序，我们过去两周时间一直在努力（构建它）"

"看起来像小游戏，那些是Mario和Luigi在到处跑吗？"

"注意，（这些是机器维修师）它演示了OptaPlanner是如何优化他们的行走时间，使他们可以花更多的时候在维修机械上。"

"你打算就把这玩艺展示给7000多个商务客呀？"

"当然，展示将会非常精彩."

程序运行的效果如下：

车间维修工实时调度

现有10台机器（编号从A到J）运行过程中会出现磨损，并通过传感器检查发现磨损情况。（现场观众安装和我们的APP）在现场观众的帮忙下，我们通过获取他们手机上的加速感应器的数据，来模拟传感器。正所谓当事物变得越摇摇欲坠时，它就变更脆弱。当观众拼命摇晃，或用手机做出其它晃动的动作时，程序中对应的机器就会收到损坏信息。（由于人数众多），现场的每一部分观众通过晃动手机，就会向对应的一台机器发送损害信息为，对应机器的健康值就会减少。如果有一台机器的健康值降到0，那就表示这台机器崩溃了。

此时，那些受损的机器在它们崩溃之前安排维修，这就是OptaPlanner用武之地了。程序中有2到3名机械师来修复这些受损的机器，与机械师们在机器之间穿梭，及在修复机器的同时，所有机器都在持续地降低健康值（现场观众正在持续拼命地晃动他们的手机）。在安排机器时工作时，决定各个机器的维修次序是很困难的，因为损坏无时无刻地发生着。幸亏，OptaPlanner为帮我们调度这些机械师，它会实时地对机台健康的变化作出反映，如视频所示：

（下面讨论一下规划程序的具体设计）

这个规划问题的挑战

规划目标只有一个：不能让做任意一个机台的健康值掉到0%。这看起来是一个简单的约束，但事实上它存在两个冲突的约束：

1. 优先修复健康值最低的机器，因为最低健康值的机器，其崩溃的风险最高。
2. 通过让机械师走最短的穿梭路径，让机械师尽量快的时间修复就近的机器 。原因如下：
   1. 机器时需要进行修复机器之外，还需要在机器之间到处到动，通过减少他们的穿梭时间，提高他们的生产力。
   2. 若只考虑最短路径一个约束，这就是一个TSP问题（旅行商问题）。

上述两个约束存在竞争的，它们各自会偏向输出以下不同的解决方案：

这两种约束对完成时间的影响差别不太明显，即如何影响机械师一次修复所有有故障机器的所需时间。维修的时间越长，将会降低生产力：

因此，我们最终需要权衡这两种约束。我们通过对每台损坏的机器评定惩罚性分数，将损坏量乘以持续时间，直到该机器被修复为止。因此，OptaPlanner规划出来的方案中，将会尽可能地避免让机器的损坏程度增大，或尽可能将机器处于损坏状态的时间减少。

这只是一个车辆路线规划问题(VRP)

在运筹学的学术界，此类问题也被称为车辆路线规则问题（Vehicle Routing Problem - VRP), 在该类问题中，我们需要一些车辆（例如货车）发送到多个目的地。

通过上图可以看出，这些只是存在一些约束差别的相同问题。

目前OptaPlanner确实擅长于求解车辆路线规划问题的优化：通过对整个车辆运行时间达到15%甚至更多的时间减少，我们每年为一些客户节省了数亿美元。同时也大大地减少了车辆的能源消耗，从而减少了碳排放，因此对环保也相当有益。