轻量化规划调度引擎——OptaPlanner简介
轻量化规划调度引擎——OptaPlanner简介
苦逼博士僧一枚，从去年起开始使用OptaPlanner 7.0.0做一些工程项目，最近将引擎更新到最新7.10.0版本，发现国内使用OptaPlanner的人越来越多，所以想把一些简单粗略的心得体会写下了分享交流，希望对新入门的童鞋有一点帮助，也希望大神前来讨论，帮助我解决难题 ๑乛◡乛๑
经过一段时间的内核引擎比选、内核引擎能力测试、工程调度问题建模和约束封装，我们实验室选择OptaPlanner作为工程使用与研究的主要工具。我们通过实例仿真验证，发现OptaPlanner具备灵活的场景与约束配置能力、良好的算法优化能力和动态调度能力，以及一定的可集成性与推广价值。
OptaPlanner是什么？
引用OptaPlanner官网上的介绍：
OptaPlanner是一个约束求解器，它能够对商业资源规划问题进行优化，例如车辆路径规划问题（VRP），雇员排班问题（Employee Rostering），云计算资源调度问题（Cloud Optimization），任务分配问题（Task Assignment），车间调度问题（JSP）和背包问题（Bin Packing）等。许多公司都面临着这样一个调度难题：分配一组有限的资源（员工、资产、时间和金钱）来提*品或服务。OptaPlanner做的就是提供更有效的规划方案，以提高服务质量并降低成本。
OptaPlanner是一个轻量化、可嵌入的规划引擎，它让普通的Java工程师能够有效地解决优化问题，它还与其他JVM语言（如Kotlin和Scala）兼容。在问题建模方面，OptaPlanner的约束作用在普通的域对象上，且无需键入复杂的数学公式，可以重复使用现有代码。在问题求解方面，OptaPlanner结合了许多复杂的启发式和元启发式算法（如禁忌搜索、模拟退火、逾期接受和变邻域搜索），能够提供非常有效的优化服务。
OptaPlanner是一款开源软件，100%由Java编写，可以在任何JVM上运行，也可以在Maven*存储库中使用。
OptaPlanner的功能与原理是什么？
所以，结合引擎官方说明，引擎提供的21个例子以及自己使用的心得，我个人将OptaPlanner能够有效解决的问题分为，一类是规划问题，一类是调度问题。调度问题可以通俗理解为是为任务分配资源的过程，任何一个待完成的任务，都具有有限的候选资源，调度问题的目的就是为每一个任务分配其拥有的候选资源；而规划问题更关注任务执行的顺序和先后关系（先干什么后干什么）。不过，实际上规划问题与调度问题往往密不可分，一刀切的划分方式也必然是不合理的，我这里只是结合OptaPlanner的使用特点，对其算例中的问题进行了这样的一个分类（下图21个例子中，红框内为规划问题，其余为调度问题）：
| 求解问题类型 | 引擎使用特点 | 例子 |
|---|---|---|
| 规划问题 | 主要使用影子变量（shadow variable） | 旅行商问题、车辆路径规划问题等路径规划问题 |
| 调度问题 | 较少使用影子变量 | 护士排班、会议调度、排课问题、考场安排、赛程安排、任务指派、病床分配、车间调度等资源调度问题 |
这里简单介绍一下OptaPlanner求解问题的原理，未来会详细介绍。OptaPlanner把问题中的对象主要分为了规划实体（planning entity）、规划变量（planning variable）和问题常量（problem fact） 3类。由于理解起来较为抽象，我以云计算资源调度（Cloud Balancing）为例介绍。该问题就是有一组计算程序（Process）和一组计算机（Computer），每个Process需要占用计算资源而每个Computer资源有限，故需要将不同的Process放在不同Computer上运行的这样一个问题。换言之，就是为每一个程序（Process）分配一个计算机（Computer）（注意不是为每一个计算机分配一个程序，因为一个计算机可能需要完成多个程序）。由此，在优化过程中，对每一个Process而言，Computer是可变的，问题的优化过程就是为全局Process选择最佳Computer的过程，故：
- 规划实体：程序（Process），与规划变量通常是多对1的关系；
- 规划变量：计算机（Computer）；
-
问题常量：程序的资源占用量，计算机的资源容量，其他约束条件等。
那么再回到上面规划问题与调度问题的讨论中，规划变量又分为常规变量（genuine variables）和影子变量（shadow variable）两种。影子变量会受常规变量的影响，若常规变量发生改变，影子变量则相应的变化。由于规划问题中主要决策规划实体（planning entity）的先后顺序，优化过程中将有许多对象随着规划变量而发生改变，故影子变量（shadow variable）将会广泛使用于规划问题中。
不过，由于影子变量的使用相对常规变量较为复杂，上手不易，建议新入门的童鞋从简单的调度问题（NQueens，CloudBalancing）入手，这两类问题在OptaPlanner User Guide（可在官网在线阅读，或下载软件后的reference_manua目录下）中均有比较详细的介绍。
为什么选择OptaPlanner？
我们在工程实践的过程中发现了许多任务管理系统存在模型兼容性与可拓展性有限、算法优化能力有限、动态与不确定性调度能力有限等不足，同时我们在为一些单位设计研发的系统也暴露出代码重用性低的现实问题。所以我们希望能够设计或者集成一款通用性的规划调度引擎，能够快速高效地解决一些简单的工程问题，令工作可积累并具有连续性，并且能够对其进行一定程度的开发与封装。考虑到新引擎开发的难度与成本，所以我们还是打算站在巨人的肩膀上:.ﾟヽ(｡◕‿◕｡)ﾉﾟ.:｡+ﾟ
我们前期也对国外一些规划调度引擎进行了比选，例如：
- Cplex：IBM开发的一款基于整数规划模型的通用式规划调度引擎，只能输出精确结果，规划效率有限，无法在有限的时间内求解大规模的任务调度问题。
- Heuristic Lab：HEAL开发的一款基于启发式和进化算法的优化问题求解软件，问题建模受经典模型约束较大，自定义模型能力有限，适用性不足。
- 其他一些专业性软件：有的以动作规划为目标，输出无约束冲突的规划方案，缺乏收益函数的评价能力；有的模型、算法及约束不易于更改，可集成性和拓展性有限；有的动态调度能力有限；有的不再更新。
针对许多引擎在求解规划调度问题时所表现出的不足，同时考虑到新引擎开发的难度与成本，所以我们选择了OptaPlanner作为任务规划与调度引擎。与上述商业引擎相比，OptaPlanner的优势我总结为：
- 100 % Java编写，引擎可拓展性与集成性强
- 具备一套完整的建模与求解方法论，问题适用性强
- 支持算法配置和一定的自定义功能，算法适应性强
- 支持动态调度与滚动调度功能
- 支持并行运算
- 轻量化、开源、更新频率高
OptaPlanner入门难么？
由于我本人并不是科班出身，刚接触OptaPlanner的时候确实天天抓狂，当然现在也只是属于初级阶段，只能解决一些不算太难的工程问题。我总结几点OptaPlanner的使用难点：
- Java：如果你不会Java，那就头疼了 (╥╯^╰╥)。
- OptaPlanner建模套路：引擎中NQueens和Cloud Balancing是两个非常适合入门的例子，VRP问题则是学习影子变量使用方法的非常好的例子。
- 实际问题的抽象能力：在掌握建模套路的基础上，就需要把实际问题进行抽象。当然同一问题也可以抽象为不同的模型，例如我做了一个航班调度问题，分别抽象为任务分配问题和VRP问题，优化效果也是不一样的。
- 规则引擎drools的使用：drools是OptaPlanner推荐使用的约束描述与收益函数计算的一个工具，但上手可能也有一点小难，网上也有许多入门介绍。当然drools也不是进行约束描述的唯一方法，引擎也可以用Java直接进行约束检查，而且亲测在某些drools很难描述的约束场景下（也可能是我菜（//▽//）），用Java直接进行约束检查效果会更好。
- 算法的改进：我一直希望能够对其内置算法进行一些改进，目前OptaPlanner提供了TS、SA、LA和VNS等几类基于局部搜索的元启发式算法，能够对其中一些算法参数进行调整，并且TS策略与其他几类算法均可混合使用（我用的TS与LA混合效果一般较好）。但进一步的算法改进还实现不了。
以上就是我个人对OptaPlanner规划调度引擎的一些拙见，希望对即将入门的童鞋们有一点帮助，更希望OptaPlanner使用高手与大神们能对我的工作提出指导与建议。以上的心得如果有什么不当之处，希望大家批评指正，也欢迎大家进行讨论。
下一次更新的时候，我会介绍一下OptaPlanner安装与使用步骤，并且结合CloudBalancing或一个停机位调度问题，介绍一下OptaPlanner的建模方法 ♪（＾∀＾●）