机械师实时调度示例(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多个商务客呀?"

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

程序运行的效果如下:
RHSummit2019OptaPlanner2MechanicsDance.gif

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

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

示例视频
(下面讨论一下规划程序的具体设计)

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

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

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

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

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

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

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

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

了解更多关于OptaPlanner在VRP问题的优化
Vehicle Routing Problem

或看一下Jiri(OptaPlanner项目另一位成员)在VRP问题的最新Demo,
[
optaweb-vehicle-routing](https://github.com/kiegroup/optaweb-vehicle-routing)

(机械师调度程序中)现实的挑战
首先,实现这种车辆路线规划的变种问题其实并不复杂,但要让程序的交互与演示运行得足够流畅,我们面临着更大的挑战。毕竟,我们不能冒着在演示期间,在观众与老板,包括我们的CEO Jim Whitehurst 面前程序崩溃的险。

要了解有关我们的架构以及与所有其他技术的集成的更多信息,请阅读Musa的文章(第2部分)。
要了解有关扩展挑战以及我们运行的模拟和负载测试的基准的更多信息,请阅读Radovan的文章(第3部分)。
如果想自己调试这个程序,可以从这里下载并根据readme的介绍进行调度。

目录
相关文章
|
算法 Java 决策智能
运筹优化工具库介绍(一)
运筹优化问题有时候极其复杂,我们可以使用运筹优化工具库帮助数学建模,解决复杂的最优化问题,本文介绍几个常见的运筹优化工具库。
1915 0
|
大数据 开发者 程序员
连接真实世界,高德地图背后的算法演进和创新
出行是生活的重要部分。我们都习惯了出门用导航,但一个导航App背后,需要什么样的数据和算法来支撑呢?算法又如何来推动出行体验的进步和创新呢?在阿里CIO学院攻“疫”技术公益大咖说的第十四场直播中高德地图首席科学家任小枫将为大家讲解高德地图背后的算法的演进和创新,分别从地图制作、搜索推荐、路径规划、时
11393 1
|
Java
Java 解析cad文件数据开源免费jar整理
Java 解析cad文件数据开源免费jar整理
1609 0
Java 解析cad文件数据开源免费jar整理
|
3月前
|
存储 供应链 监控
如何开发仓库管理系统里的出入库管理板块?(附架构图+流程图+代码参考)
仓库管理系统(WMS)是企业管理库存、优化仓储运营的重要工具。本文详解WMS中出入库管理模块的开发,涵盖功能设计、业务流程、代码实现及常见问题解答,助你掌握入库出库管理的核心要点与开发技巧。
|
3月前
|
JSON 物联网 API
天气预报免费API接口【IP查询版】使用教程
IP查询天气API是一款免费实用的接口,可根据IP地址自动获取所在地天气预报,支持自定义IP查询。核心功能包括自动识别请求IP、全国IP天气查询,数据源自中国气象局,无日调用上限。提供详细的返回参数及多语言示例代码,适用于网站、APP、物联网设备等应用场景。
|
决策智能
Or-tools调用求解器介绍(三)
Or-tools调用求解器介绍(三)
765 0
|
算法 调度
关于OptaPlanner的使用(一)——简介
关于OptaPlanner的使用(一)——简介
1075 0
|
网络协议 关系型数据库 MySQL
Android Termux安装MySQL,通过内网穿透实现公网远程访问
Android Termux安装MySQL,通过内网穿透实现公网远程访问
|
达摩院 算法 API
阿里达摩院MindOpt优化求解器-月刊(2023年7月)
阿里达摩院MindOpt优化求解器-7月刊,新增人员排班、仓库选址优化的案例,包含源代码,新版本MindOpt求解器V1.0的API重大升级,邀请内测。
487 0
阿里达摩院MindOpt优化求解器-月刊(2023年7月)
|
XML Android开发 数据格式
Android 中简单计时器的实现方法(Handler和TimerTask)
Android 中简单计时器的实现方法(Handler和TimerTask)
737 0