开篇
在前面一篇关于规划引擎 Optapalnner 的文章里(Optaplanner 规划引擎的工作原理及简单示例(1) https://www.jianshu.com/p/f9ec79916794 ), 老农介绍了应用 Optaplanner 过程中需要掌握的一些基本概念, 这些概念有且于后面的内容的理解, 特别是关于将约束应用于业务规则上的理解. 承上一文, 在本篇中将会减一些理论, 而是偏向于实践, 但过程中, 借助实际的场景对一些相关的理论作一些更细致的说明, 也是必要的. 本文将会假设我们需要对一个车间, 需要制定生产计划. 我们为生产计划员们设计一套智能的, 自动的计划系统; 并通过 Optaplanner 把这个自动计划系统开发出来. 当然, 里面的业务都是经过高度抽象形成的, 去除了复杂的业务规则, 仅保留可以体现规划引擎作用的一些业务需求. 因此, 这次我们只用一个简单的小程序即可以演绎一个自动计划系统, 来呈现规划引擎 Optaplanner 在自动计划上的魅力.
"项目" 背景与业务规则的分类
假如我们接到一个项目, 经过需求调研之后, 发现其业务逻辑非常简单; 但细想一下业务操作却又是异常复杂 (先别砸砖, 听老农缪缪道来). 它是一个生产计划系统(应该说是一个生产计划辅助系统, 毕竟最终的计划, 应该是人来决定, 而非系统), 在没有这个系统之前, 计划人员(生产调试员) 每天收到需要加工的生产任务之后, 根据当时的机台产能情况, 将这些待处理的任务合理地分配到适合的机台. 对于前面这句对计划制定工作的描述, 其实可以细作提练, 其隐含了两个意义, 分别是 "合理地" 和分配到 "合适的" 机台. 对于这两个意义, 我们可以把它区分为两种个方面的业务要求:
"合适的机台" - 表示确定性的条件判断, 是一个定性的断言, 也就是非对即错.
"合理地" - 表示非确定性的条件, 也就是定量的, 可以是非常合理, 60% 的合理, 或完全合理, 也就是说是否合理, 还是有议论空间的, 并没有一个完全固定的标准.
下面将对上述两项进行更深入的讨论.
确定性条件(定性)
对于上述提到的这两个条件, 其中 "分配到合理机台" 是相对确定的命题, 只要向计划人员提供合理机台的条件指引, 计划人员根据这些条件进行操作, 总有一天能把所有的任务, 匹配上所有条件的, 只是时间问题. 例如: A 类任务只能放在可以处理 A 类任务的机台上加工; 但也可能会更复杂, 例如: 来自某些客户的, 且具有特定工一要求的, 且生产量在指定范围内的, 且..., 且....., 你可以一直 "且" 下去, 令这些条件非常复杂. 但无论怎么复杂, 这些条件是具有确定性的判断标准, 也就是说, 不管有多复杂, 只要能识别出来的条件, 生产计划人员就可以根据这些条件进行分配; 当然实际生产活动中, 必然会遇到一些问题, 当一些任务与机台的匹配条件非常复杂时: 一来会令工作效率骤降; 再就是人是有可能出错的, 比较容易出问题的; 甚至超出人的处理能力.
在本文, 我们仅仅是为了让程序可以体现这种确定性条件的处理方法, 我们把这类条件简化到最极端的情况: 只有一个条件, 只要机台可处理的任务类型, 与任务自己的类型合适即表示机台与任务匹配. 例如: 有个机台 M1 可以做的 T1, T2, 这两种任务, 机台 2 可以做 T2,T3 两种任务; 那么, 如果一个任务它是属于 T1 类型, 则合适的机台只有 M1, 如果这个任务是 T3 类型, 则它的合适机台只有 M2; 如果这个任务是 T2 类型, 则合适的机台有 M1,M3 两台. 凡是把任务分配应类别的机台上去, 都是合适的.
非确定性条件(定量)
非确定性条件, 相对复杂一点, 因为这类条件是没有绝对的对错, 只有相对的优劣. 例如本文中我们会使用成本这个条件因素, 在确保上面的确定性因素 (任务类型与机台匹配) 前提下, 成本越低越好. 那么就存在多个可行方案的的可能, 就会涉及到应该如何计算成本, 用哪些方案的成本进行对比才是合理的问题. 要理清这些问题, 需要对业务模型有深入的理解, 并能很准确地对这些因素进行归纳, 把它们抽象成约束条件. 为了简化问题, 在本例中, 成本反映在机台的启用成本上. 也就是说, 每个机台一旦启动它都会产生固定成本, 而不会随着任务量增多而成本上升. 所以作为计划定制人员, 如果这是一个计划的重要指标的话, 在制定计划时, 就需要考虑应该如何统计一个机台的成本. 本例中我们假定生个机台一旦启动, 即产生固定的成本, 所以我们的目标是:
用尽量小的机台来完成尽量多的任务.
这些被启用的机台, 其成本尽可能低; 即优先使用低成本的机台来处理任务.
当然, 因应不同的场景, 会有其它的要求, 例如产能平衡: 令尽可能多的机台被启用, 以减少少空置率, 搞提生产效率. 本例中我们并没有使用此规则.
设计与测试数据
为了满足上述条件, 我们先建立业务模型. 我们先识别出业务实体. 可以识别出来的实体也只有两个, 机台和任务.
机台
我们假设有 6 个机台, 分别是 M1- M6, 它们分别有自己可处理的任务类型: Type_A,Type_B, Type_C 和 Type_D, 且分别有自己的产能和成本. 产能表示这个机台在固定时间段内, 最多可以处理的任务量; 成本表示如果这个机台一旦开启, 即产生相应的货币成本. 例如: 机台 M1,
它可以处理类型为 Type_A 的任务(也就是说, 它可以和产类型为 Type_A 的产品);
在固定时间段内 (例如一个班次, 或一天) 可以处理 300 个任务, 即产能为 300.
它的成本为 100, 即它一旦被启动, 即产生 100 元的成本.
所有机台资料如下图, 可以看到, 有些机台它的可处理的任务类型是相同的, 但两者的产能不同; 有些可处理的任务类型相同, 产能也相同, 但成本不同; 这样就进一步贴近实况.
机台列表
任务(产品)
对于需要加工的产品(工称工件), 我们把它抽象成任务, 因为对于一个车间中的机台而言, 以任务来识别它更贴切一些, 在实际的业务建模中, 一个产品不一定是一个任务, 也有可能是一个产品的工序路线中的其中一个工序被定义为一个任务, 即表示一个生产单位的一个生产指令, 例如: 对机器外壳打孔. 而在本例中, 我们了为简化问题, 我们假设一个任务就一个产品, 每个产品只需一个任务即可. 而关于一个产品存在一条完整且复杂的工序路线, 从而产生多个生产任务的情况, 我将在以后的文章中, 关于 Optaplanner 的更高级的应用中, 将会有相关的详细讲解.
对于任务 (产品), 我们的假设它具有类型和生产量两个属性. 类型 - 表示它是属于哪一类的产品, 用于识别它可以被分配到哪一个机台进行加工处理. 生产量 - 表示这个产品需要生产多少个, 当这个产品被分配到指定的机台上生产的时候, 生产量这个属性将会与对应机台的产能作出对比与限制, 即一个任务如果生产量超过了一个机台的产能, 那么这个任务就无法放在这个机台上处理. 所有任务(10 个) 的资料如下图:
任务列表
约束
假如我们已经通过需求调研, 确定了我们上述机台与任务两个业务实体, 那么, 下一步的调研目标, 就是要识别出在这些任务分配到机台上的过程中, 按照生产业务要求, 我们需要遵循哪些规则了. 本例我们假设有以下业务规则, 以下称为约束, 其中包括硬约束(不可违反), 和软约束(尽量不要违反, 但将不可避免; 如果违反, 尽可能令违反的程度减到最小)
硬约束:
任务只能被分配到可以处理它的机台上, 以机台的 "可处理任务类型" 字段与任务的 "类型" 字段作识别, 两者一致才符合条件;
一个机台处理的任务的生产量总和不能超过其产能.
软约束:
整个排产计划中, 所有启用的机台成本之和尽量小.
通过上述约束的描述, 可以得知, 其中两个硬约束是可以避免的, 但软约束是不可避免的, 因为你处理任务必须启动机台, 一旦启动任意机台, 都会产生成本. 因此, 软约束的要求是尽量小, 而不是不违反, 不是 0.
任务分本问题的解决方法(暴力穷举法与 Optaplanner)
以下为理论部分, 无兴趣探讨的同学可以跳过本小节.
本 "项目" 的业务场景, 业务实体和业务规则, 我们都已经构建完成, 接下来就是如何在上述给定条件的基础上, 构建一个快速可用的解决方案, 用于解决任务的分配问题了. 至此, 可能有些同学在想, 其实这并不难呀, 根据给定的两个硬约束和一个软件约束, 以两个硬约束作为限制条件, 通过暴力穷举的方法, 找出一个无限趋近于符合软约束, 也可以找出一个令成本最低的任务分配方案出来呀. 这是对的, 只要我们有明确的软硬约束要求, 理论上是可以写出对应的程序, 通过强大的 CPU 算法, 甚至可以将程序写成并发运算, 集成数量庞大的 GPU 算力, 兴许能找最终方案的. 但是, 有这种想法, 其实忽略了问题的规模与时间复杂度的关系. 我们需要探讨, 随着数据量 (即问题规模) 的增大, 找到可用分配方案的耗时增长有多大, 与问题规模的增长呈何种比例关系. 通过上述的条件, 及排列组合的知识得知, 通常这类问题的时间复杂度是指数级复杂度, 即 O(a^n), 甚至是阶乘级复杂度的, 即 O(n!). 当数据量有限增大之后, 所需的运行时间增长, 对目前技术上的计算机算力来讲, 增长是指数级, 甚至以今天的技术水平, 是永远都无法找到最终方案的. 这个在关于 NPC 或 NP-Hard 问题的文章中已有介绍, 这里不再重复.
面对这类 NP 问题时, 人类是如何解决的呢. 其实人类目前也是无解的, 如果哪位同学如果找到一个算法来解决这类问题, 它的时间复杂度是常数级的, 那么恭喜你, 你已经为人类解决了不少难题了. 而所谓的无解是指, 无法在任何情况下找出一个绝对最优的解决方案 (如果本例中的业务规则及数据量, 用草稿纸都可以把所有情况列出来了, 当然可以找出最优解, 前提是你有足够耐性). 所以, 人们想到的还是通过穷举的方法, 一个一个的组合方案去尝试, 直找到最佳方案. 但这种方法在数据量增大, 或更多判断条件的时候是不可行的, 而我们日常处理这类问题(例如排生产计划), 当找到的排产方案只要满足了所有硬约束(其实光是满足硬约束的方案, 如果不通过程序来实现, 人类也很难很快找到); 软约束方面只要找出一个差不多的, 我们即可视作一个可用的方案并付诸执行了; 因为我们不可能无限地找下去. 而 Optaplanner 其实跟我们一样, 问题规模足够大的情况下, 它也是不可能找出绝对最优方案的. 但是它相对人类聪明之处在于, 它集成了寻找最优方案的过程诸多专门的算法. 过程中使用了分阶段, 分步骤的方法将问题归约成一些数学模型可处理的形式. 且在寻找最佳方案(应该是寻找更佳方案) 的过程中, 它集成了一堆已被证明卓有成效的数学寻优算法, 例如在问题初始化阶段可以使用 First Fit, First Fit Decreasing 等算法, 在寻优阶段使用禁忌搜索法, 模拟退火法等算法. 从而极大地提高寻找更优方案的效率. 令其在相同的时间内, 找到的方案相对人类, 或者相对不使用任何算法的暴力穷举法而言, 质量高得多, 更趋近于最优方案.
用 Optaplanner 解决任务分配问题
通过 Optaplanner 寻找更佳分配方案, 需要建立相关的类和模型, 英语还可以的同学, 可以直接上去它的使用说明中查看 Cloud Balance https://docs.optaplanner.org/7.8.0.Final/optaplanner-docs/html_single/index.html#quickStart 示例, 是一个非常好的示例, 从最简单的 Hellow world, 到使用了 Real-time planning 等近几个版本新功能, 都有详细的说明与教程. 我们现在这个示例也是参它来设计的.
在开始设计之前, 我们需要构思一下, 我们的任务分配是如何实现的. 在我们的实际计划制定的业务操作中, 也就是工厂的车间里, 计划员是把一个产品的实物, 喂进一个机台, 让机台对它进行处理. 所以我们会理解为: 分配就是把上面 10 个任务分配到 6 个机台中. 其实这样做是可行的, 但我们更深入地思考一下, 其实我们需要处理的是任务, 而不是机台, 也就是说, 每个任务必须都被分配到一个机台中处理, 而机台不一定. 在最小化成本的原则底下, 好的方案有可能出现有部分机台并没有分得任务的情况. 所以, 我们需要把任务与机台的关系倒过来, 把任务作为我们的研究目标, 理解为把一个机台分给一个任务. 做过生产计划或生产管理的同学就很清楚知道, 机台也是一种生产资源, 针对不同的生产任务, 将资源应用到这些任务上去, 其中机台 (或产线) 是一个很常见的资源类型.
所以, 我们的设计思路是: 针对一个任务, 把一个适合的机台分配给它, 令它满足两个条件: 1. 满足所有硬约束; 2. 分配好所有任务的机台之后, 这些机台的成本加总尽量低. 好了, 理清了思路, 下面我们就可以开始设计了.
按 Optaplanner 规范建模
要使用 Optaplanner 规划引擎, 就需要按它的要求建立对应的模型, 包括各种类及其关系. 我们这个示例跟官网上的 Cloud Balance 几乎一致, 在它的类图基础上修改就可以了. 我们先看看建立好的 class diagrame 如下图:
要建立的类分别是:
Task, 表示任务的实体类, 它被注解为 @PlanningEntity, 它有三个属性: taskType - 当前任务的类型; quantity - 生产量; machine - 任务将要被分配到的机台. 其中 machine 属性被注解为 @PlanningVariable, 表示规划过程中, 这个属性的值将被 plan 的, 即通过调整这个属性来得到不同的方案. 另外, 作为一个 Planning Entity, 它必须有一个 ID 属性, 用于在规划运行过程中识别不同的对象, 这个 ID 属性被注解为 @PlanningId. 本例中所有实体类都继承了一个通用的类 - AbstractPersistable, 该父类负责维护此所有对象的 ID.Task 类也继承于它, 因此, 将该类的 ID 属性注解为 @PlanningId 即可. 另外, 作为 Planning Entity, 它必须有一无参构造函数, 若你在此类实现了有参构造的话, 需要显式地实现一个无参构造函数.
Machine, 表示机台的实体类, 它属于 ProblemFact https://docs.optaplanner.org/7.8.0.Final/optaplanner-docs/html_single/index.html#problemFact , 在其中保存了在规划过程中会用到的属性, 此类反映一个机台相关信息的属性: taskType - 可处理的任务类型; capacity - 当前机台的产能; cost - 当前机台的成本.
TaskAssignment, 此类用来描述整个解决方案的固定类, 它的结构描述了问题的各种信息, 在 Optaplanner 术语中, 在执行规划前, 它的对象被称作一个 Problem, 完成规划并获得输出之后, 输出的 TaskAssignment 对象被称作一个 Solution. 它具有固定的特性要求: 必须被注解为 @PlanningSolution; 本例中, 它至少有三个属性: machineList - 机台列表, 就是可以用于分配任务的机台, 本例中指的就是上述那 6 个机台; taskList - 就是需要被规划 (或称分配机台) 的 10 个任务, 这个属性需要被注解为 @PlanningEntityCollectionPropery. 还有一个是 score 属性, 它用于在规划过程中对各种约束的违反情况进行打分, 因为本例中存在了硬约束与软约束. 因此我们使用的 Score 为 HardSoftScore https://docs.optaplanner.org/7.8.0.Final/optaplanner-docs/html_single/index.html#hardSoftScore .
另外, 上述提到了一个的有实体类 (本例只有 Task 与 Machine 为实体类) 的父类 AbstractPersistable, 它负责维护 ID 属性, 对实体类的 compareTo 方法, toString 方法进行重载.
具体的代码如下, 没有 Maven 基础的同学, 请先自补一下 Maven 的知识, 以下内容都是基于 Maven 的.
Task 类:
- package com.apsbyoptaplanner.domain;
- import org.optaplanner.core.api.domain.entity.PlanningEntity;
- import org.optaplanner.core.api.domain.variable.PlanningVariable;
- @PlanningEntity
- public class Task extends AbstractPersistable{
- private String requiredYarnType;
- private int amount;
- private Machine machine;
- public String getRequiredYarnType() {
- return requiredYarnType;
- }
- public void setRequiredYarnType(String requiredYarnType) {
- this.requiredYarnType = requiredYarnType;
- }
- public int getAmount() {
- return amount;
- }
- public void setAmount(int amount) {
- this.amount = amount;
- }
- @PlanningVariable(valueRangeProviderRefs={"machineRange"})
- public Machine getMachine() {
- return machine;
- }
- public void setMachine(Machine machine) {
- this.machine = machine;
- }
- public Task(){}
- public Task(int id, String requiredYarnType, int amount) {
- super(id);
- this.requiredYarnType = requiredYarnType;
- this.amount = amount;
- }
- }
- View Code
Machine 类:
- package com.apsbyoptaplanner.domain;
- public class Machine extends AbstractPersistable{
- private String yarnType;
- private int capacity;
- private int cost;
- public String getYarnType() {
- return yarnType;
- }
- public void setYarnType(String yarnType) {
- this.yarnType = yarnType;
- }
- public int getCapacity() {
- return capacity;
- }
- public void setCapacity(int capacity) {
- this.capacity = capacity;
- }
- public int getCost() {
- return cost;
- }
- public void setCost(int cost) {
- this.cost = cost;
- }
- public Machine(int id, String yarnType, int capacity, int cost) {
- super(id);
- this.yarnType = yarnType;
- this.capacity = capacity;
- this.cost = cost;
- }
- }
- View Code
TaskAssignment 类
- package com.apsbyoptaplanner.domain;
- import java.util.List;
- import org.optaplanner.core.api.domain.solution.PlanningEntityCollectionProperty;
- import org.optaplanner.core.api.domain.solution.PlanningScore;
- import org.optaplanner.core.api.domain.solution.PlanningSolution;
- import org.optaplanner.core.api.domain.solution.drools.ProblemFactCollectionProperty;
- import org.optaplanner.core.api.domain.valuerange.ValueRangeProvider;
- import org.optaplanner.core.api.score.buildin.hardsoft.HardSoftScore;
- @PlanningSolution
- public class TaskAssignment extends AbstractPersistable{
- private HardSoftScore score;
- private List<Machine> machineList;
- private List<Task> taskList;
- @PlanningScore
- public HardSoftScore getScore() {
- return score;
- }
- public void setScore(HardSoftScore score) {
- this.score = score;
- }
- @ProblemFactCollectionProperty
- @ValueRangeProvider(id = "machineRange")
- public List<Machine> getMachineList() {
- return machineList;
- }
- public void setMachineList(List<Machine> machineList) {
- this.machineList = machineList;
- }
- @PlanningEntityCollectionProperty
- @ValueRangeProvider(id = "taskRange")
- public List<Task> getTaskList() {
- return taskList;
- }
- public void setTaskList(List<Task> taskList) {
- this.taskList = taskList;
- }
- public TaskAssignment(List<Machine> machineList, List<Task> taskList) {
- //super(0);
- this.machineList = machineList;
- this.taskList = taskList;
- }
- public TaskAssignment(){}
- }
- View Code
AbstractPersistable 类
- package com.apsbyoptaplanner.domain;
- import java.io.Serializable;
- import org.apache.commons.lang3.builder.CompareToBuilder;
- import org.optaplanner.core.api.domain.lookup.PlanningId;
- public class AbstractPersistable implements Serializable, Comparable<AbstractPersistable> {
- protected Long id;
- protected AbstractPersistable() {
- }
- protected AbstractPersistable(long id) {
- this.id = id;
- }
- @PlanningId
- public Long getId() {
- return id;
- }
- public void setId(Long id) {
- this.id = id;
- }
- @Override
- public int compareTo(AbstractPersistable other) {
- return new CompareToBuilder().append(getClass().getName(), other.getClass().getName()).append(id, other.id)
- .toComparison();
- }
- @Override
- public String toString() {
- return getClass().getName().replaceAll(".*\\.", "") +"-" + id;
- }
- }
- View Code
到目前为止, 我们已完成了所有的 Java 代码了, 注意, 这里指的是 Java 代码, 事实上要成功启动 Optaplanner 的规划引擎, 只有 Java 代码是远远不够的. 还需要更多的配置与其它内容.
对于上述代码, 眼尖的同学应该会看到, 在 TaskAssignment 类中, machineList 的 getter - getMachineList(), 除了被注解为 @ProblemFactCollectionProperty, 还有另外一个注解 @ValueRangeProvider(id="machineRange"), 满脑疑惑的同学先不急, 大家再看看 Task 类的 machine 成员的 getter - getMachine(). 奇怪了上文不是提到, 它只需被注解为 @PlanningVariable 的吗? 怎么后面还有个参数呢, 整个注解是 @PlanningEntity(valueRangeProviderRefs={"machineRange"}), 没错了, 大家应该猜到, 这两个注解的意义了. 它们的意义是: 对于每个 Planning Entity (task) 对象中的 PlanningVariable(machine), 它的取值范围是 TaskAssignment 对象中的 machineList 中的内容. 从业务上讲, 就是说, 对于每一个任务而言, 它可以分配的机台, 是那 6 个机台之一. 这样大家是否恍然大悟呢?
好了, 上面已经巧妙地通过各个注解, 将 Planning Entity, Problem Fact 和 Problem 等对象关联起来, 那么大家是不是觉得有些地方漏了? 对了, 那就是约束规则 (2 硬 1 软的约束) 如何在这些类的关系中体现呢? 其实上面这些类关系是没办法表达这些业务约束的; 如果需要表达这些约束, 还需要创建一些用于计分数的类, 用于对每个约束的违反情况进行记分. 但自从 Optaplanner 与 Drools(一个开源规则引擎) https://www.drools.org/ 结合之后, 就不再需要自己通过 Java 代码编写算分逻辑了(当然你也可以不用 Drools, 自行编写算分逻辑), 只需要通过 Drools 表达业务约束, Optaplanner 在规划过程中, 会启自行启动 Drools 规划引擎对这些约束进行判断, 从而进行计分.
那么我们只需要在 resource 里添加一个 Drools 脚本文件, 用于描述这些约束即可. 至于 Drools 的应用, 不在本文范围, 同学们可以自行学习 Drools, 如有需要, 我将会撰写另外一个 Drools 应用相关的系列文章 .
rules.drl 文件
- package com.apsbyoptaplanner.solver;
- import org.optaplanner.core.api.score.buildin.hardsoft.HardSoftScoreHolder;
- import com.apsbyoptaplanner.domain.Task;
- import com.apsbyoptaplanner.domain.Machine;
- import com.apsbyoptaplanner.domain.TaskAssignment;
- global HardSoftScoreHolder scoreHolder;
- rule "yarnTypeMatch"
- when
- Task(machine != null, machine.yarnType != requiredYarnType)
- then
- scoreHolder.addHardConstraintMatch(kcontext, -10000);
- end
- rule "machineCapacity"
- when
- $machine : Machine($capacity : capacity)
- accumulate(
- Task(
- machine == $machine,
- $amount : amount);
- $amountTotal : sum($amount);
- $amountTotal> $capacity
- )
- then
- scoreHolder.addHardConstraintMatch(kcontext, $capacity - $amountTotal);
- end
- rule "machineCost_used"
- when
- $machine : Machine($cost : cost)
- exists Task(machine == $machine)
- then
- scoreHolder.addSoftConstraintMatch(kcontext, -$cost);
- end
好了, 实体模型我们创建好了, 约束也已通过 Drools 脚本表达出来了, Optapalnner 是如何将两者结合起来, 从而达到计分效果的呢? 其实我们还是缺了一块, 那就是 Optaplanner 的配置, 因为需要创建 Optaplanner 的引擎对象进行规划的时候, 是有一大堆参数需要指定给引擎的. 按照 Optaplanner 的接口设计要求, 需要设计一个称作 Solvder Configuration 的 XML 文件, 用于描述引擎的参数及行为.
- taskassignmentConfiguration.xml:
- <?xml version="1.0" encoding="UTF-8"?>
- <solver>
- <!-- Domain model configuration -->
- <solutionClass>com.apsbyoptaplanner.domain.TaskAssignment</solutionClass>
- <entityClass>com.apsbyoptaplanner.domain.Task</entityClass>
- <!-- Score configuration -->
- <scoreDirectorFactory>
- <scoreDrl>taskAssignmentDools.drl</scoreDrl>
- </scoreDirectorFactory>
- <!-- Optimization algorithms configuration -->
- <termination>
- <secondsSpentLimit>10</secondsSpentLimit>
- </termination>
- </solver>
好了, 通过上述的步骤, 一个 Optaplanner 程序基本上就完成了. 且慢! 一个 Java 程序竟然没有 main 入口? 没错, 除了 main 入口外, 我们还没有构建引擎对象并启动它呢. 因为是示例, 我就将构造引擎对象, 业务实体对象都放在入口程序 App 里.
App.java 代码
- import java.io.InputStream;
- import java.util.ArrayList;
- import java.util.List;
- import java.util.stream.Collectors;
- import org.optaplanner.core.api.solver.Solver;
- import org.optaplanner.core.api.solver.SolverFactory;
- import com.apsbyoptaplanner.domain.Machine;
- import com.apsbyoptaplanner.domain.Task;
- import com.apsbyoptaplanner.domain.TaskAssignment;
- public class App {
- public static void main(String[] args) {
- startPlan();
- }
- private static void startPlan(){
- List<Machine> machines = getMachines();
- List<Task> tasks = getTasks();
- InputStream ins = App.class.getResourceAsStream("/taskassignmentConfiguration.xml");
- SolverFactory<TaskAssignment> solverFactory = SolverFactory.createFromXmlInputStream(ins);
- Solver<TaskAssignment> solver = solverFactory.buildSolver();
- TaskAssignment unassignment = new TaskAssignment(machines, tasks);
- TaskAssignment assigned = solver.solve(unassignment);// 启动引擎
- List<Machine> machinesAssigned = assigned.getTaskList().stream().map(Task::getMachine).distinct().collect(Collectors.toList());
- for(Machine machine : machinesAssigned) {
- System.out.print("\n" + machine + ":");
- List<Task> tasksInMachine = assigned.getTaskList().stream().filter(x -> x.getMachine().equals(machine)).collect(Collectors.toList());
- for(Task task : tasksInMachine) {
- System.out.print("->" + task);
- }
- }
- }
- private static List<Machine> getMachines() {
- // 六个机台
- Machine m1 = new Machine(1, "Type_A", 300, 100);
- Machine m2 = new Machine(2, "Type_A", 1000, 100);
- Machine m3 = new Machine(3, "TYPE_B", 1000, 300);
- Machine m4 = new Machine(4, "TYPE_B", 1000, 100);
- Machine m5 = new Machine(5, "Type_C", 1100, 100);
- Machine m6 = new Machine(6, "Type_D", 900, 100);
- List<Machine> machines = new ArrayList<Machine>();
- machines.add(m1);
- machines.add(m2);
- machines.add(m3);
- machines.add(m4);
- machines.add(m5);
- machines.add(m6);
- return machines;
- }
- private static List<Task> getTasks(){
- // 10 个任务
- Task t1 = new Task(1, "Type_A", 100);
- Task t2 = new Task(2, "Type_A", 100);
- Task t3 = new Task(3, "Type_A", 100);
- Task t4 = new Task(4, "Type_A", 100);
- Task t5 = new Task(5, "TYPE_B", 800);
- Task t6 = new Task(6, "TYPE_B", 500);
- Task t7 = new Task(7, "Type_C", 800);
- Task t8 = new Task(8, "Type_C", 300);
- Task t9 = new Task(9, "Type_D", 400);
- Task t10 = new Task(10, "Type_D", 500);
- List<Task> tasks = new ArrayList<Task>();
- tasks.add(t1);
- tasks.add(t2);
- tasks.add(t3);
- tasks.add(t4);
- tasks.add(t5);
- tasks.add(t6);
- tasks.add(t7);
- tasks.add(t8);
- tasks.add(t9);
- tasks.add(t10);
- return tasks;
- }
- }
好了, 上述代码懂的同学应该不难理解, 就是先构建一个 Solver 对象, 一个 taskList, 一个 machineList; 及一个 taskAssignment 对象, 并 taskAssignment 对象对应的成员分别指向 taskList 与 machineList. 然后就启动 solver 对象的 solver 方法. 引擎就哄哄地被启动, 去帮我们找最优解了.
如果配置好 log 组件, 大家将会看到如下输出:
- 22:20:25.687 [main] DEBUG LS step (26556), time spent (9999), score (0hard/-800soft), best score (0hard/-700soft), accepted/selected move count (1/5), picked move (Task-1 {Machine-2} <-> Task-4 {Machine-1}).
- 22:20:25.687 [main] DEBUG LS step (26557), time spent (9999), score (0hard/-800soft), best score (0hard/-700soft), accepted/selected move count (1/1), picked move (Task-3 {Machine-2 -> Machine-1}).
- 22:20:25.688 [main] DEBUG LS step (26558), time spent (10000), score (0hard/-800soft), best score (0hard/-700soft), accepted/selected move count (1/22), picked move (Task-3 {Machine-1} <-> Task-4 {Machine-2}).
- 22:20:25.688 [main] INFO Local Search phase (1) ended: time spent (10000), best score (0hard/-700soft), score calculation speed (31205/sec), step total (26559).
- 22:20:25.689 [main] INFO Solving ended: time spent (10001), best score (0hard/-700soft), score calculation speed (30447/sec), phase total (2), environment mode (REPRODUCIBLE).
- Machine-2:->Task-1->Task-2->Task-3->Task-4
- Machine-4:->Task-5
- Machine-3:->Task-6
- Machine-5:->Task-7->Task-8
- Machine-6:->Task-9->Task-10
从上面的日志内容, 我们可以看到, 以时间开始的行, 是 Optaplanner 引擎在一步一步帮我们找最优方案时的过程输出. 到最后结束时, 它显示 best score (0hard/-700soft). 意思是说, 它帮我们找到的方案的评价是: 没有违反任何硬约束(0hard), 软约束的违反分数是 700 分(-700soft). 也就是我们用这些机台做完这 10 个任务需要 700 元的要台成本. 那么这 700 元是怎么来的呢? 那就得看看它给出我们的分配方案是什么了:
- Machine-2:->Task-1->Task-2->Task-3->Task-4
- Machine-4:->Task-5
- Machine-3:->Task-6
- Machine-5:->Task-7->Task-8
- Machine-6:->Task-9->Task-10
意思是说 M2(Machine-2)上分配了 Task1, Task2, Task3, Task4; 其它机台如此类推. 即应用了 M2,M3,M4,M5,M6 共 5 个台机, 大家可以回到上面的机台列表, 这 5 个机台的成本加起来就是 700 元.
至此, Optaplanner 已经帮大家找到最佳方案了, 大家可以自行验证一下, 试试如何将上面分配方案的一些任务移到其它机台, 它能否保持不违反 2 个硬约束的前提下, 得到比 700 更小的机台成本?
另外, 关于 Maven 需要的依赖包, 我将 POM 文件的内容也贴出来. 大家照着上, 应该可以运行起来了.
POM.XML 文件内容:
<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
<modelVersion>4.0.0</modelVersion>
<parent>
<groupId>org.optaplanner</groupId>
<artifactId>optaplanner</artifactId>
<version>7.8.0.Final</version>
</parent>
<groupId>com.apsbyoptaplanner</groupId>
<artifactId>OptaplannerTest</artifactId>
<version>0.0.1-SNAPSHOT</version>
<dependencies>
<dependency>
<groupId>org.optaplanner</groupId>
<artifactId>optaplanner-core</artifactId>
</dependency>
<dependency>
<groupId>org.kie</groupId>
<artifactId>kie-api</artifactId>
</dependency>
<dependency>
<groupId>com.thoughtworks.xstream</groupId>
<artifactId>xstream</artifactId>
</dependency>
<dependency>
<groupId>ch.qos.logback</groupId>
<artifactId>logback-classic</artifactId>
<scope>runtime</scope>
</dependency>
</dependencies>
</project>
此文经历了超过两个星期的时间才完成, 其实思路与目标在行文前均已很明确, 耐何近段时间确定太忙无法抽身. 还请各位见谅. 接下来, 该系列文章将按两个方案开展, 一方面按 Optaplanner 的各个特性, 详细讲解各种功能的使用方法与工作原理. 另一方面将会类似于本文, 将撰写数篇相对深入的应用文章, 分享给对 Optaplanner 有一定认识的同学. 如果对此, 大家有何建议, 欢迎大家加我企鹅一起探讨: 12977379 或 V 信: 13631823503.
其实 Optaplanner 不需要对 Java 过份精通即可使用, 因为它使用到的都是 Java 最基本的知道, 但还是需要有基本的 Java 知识才行, 希望大家找我研究讨论时, 如果 Java, Maven 等方面仍接触较少, 请大家先行自补该方面的知识, 本猿暂时只能跟大家探讨 Optaplanner, Drools 的应用, 而 Java 相关的知识, 恕无法提供有效的帮助, 毕竟本猿也只是个 Java 新手. 先谢了.
来源: https://www.cnblogs.com/kentzhang/p/9362859.html