实现不完全规划的方法

2021-12-15

  在各种常见的规划场景中,我们经常会遇到一种不完全规划的情况。即在正常情况下,在完成了一次规划运算(甚至是CH阶段的运算中),OptaPlanner的规划实体(Planning Entity, 下称规划实体)中每个规划变量(Planning Variable,下称规划变量)必须非空,即必须被赋予规划变量取值范围(ValueRange,规划变量取值范围)范围内的值;尽管有更约束被违反,也必须实现赋值。

​  例如,在CloudBalance示例中,若一个数据集中存在足够多的进程(CloudProcess对象),以致启用所有计算机的内存无法装入所有进程。此时,引擎还是会强行把一些进程塞进一些已经内存已经不足的计算机中,从而出现内存这个约束(硬约束)被打破。但在我们的实际场景中,面对这种情况,我们并不希望输出这种违反硬约束的结果;因为在这样的业务情景中,违反硬约束的结果已经是典型的不可行方案了。我们更希望引擎能更机智灵活地识别出这种实际场景中毫无意义的方案,从而找到一个不会将资源过度分配的方案。

  这种方案在OptaPlanner中被称为 Overconstrained Planning,对于这种资源超用的处理情况,可归结为对资源的过度分配。以下用户手册的章节描述了两种方法实现方法:https://www.optaplanner.org/docs/optaplanner/latest/repeated-planning/repeated-planning.html#overconstrainedPlanning

​  从文中可以看到,要实现这种功能,OptaPlanner并没有开箱即用的方法或功能。但通过其中的一些特性我们仍然可以通过简单的方法巧妙实现。目前主要有两种办法来实现“避免资源超用”情况,分别是 - "让规划变量允许为空"和"为规划变量的取值范围提供到一些虚拟值".

让规划变量允许为空

  ​正常来说,对于一个规划问题来说,一个可能的方案(Possible Solution)是其所有规划实体(Planning Entity, 下称规划实体)的所有规划变量)都完成赋值。在规划的CH阶段就是实现对每一个规划变量进行赋值的阶段。通过在定义规划变量中加入nullable属性并将其属性值设置为true来让一个规划变量在规则过程中允许保留空值。如下代码:

@PlanningVariable(nullable = true)     
public getCloudComputer{
         return cloudComputer;     
}

​  通过该属性设置,在规划过程中规划变量除了会从规划变理取值范围中获取可能值生成方案外,空值(null)也将出现在取值范围内,这种情况下无需向取值范围列表加入空值,程序会自动空值纳入考虑范围内。

  细心的同学一定会想到,如果规划变量可以为空值,那么会不会得到的方案全部规划变量都为空,毕竟空值也是规划变量的取值范围,且满足约束。但实际业务场景中,空值对于我们来说,通常是不存在业务意义的;只不过是想让方案不过度分配资源而已(在资源分配的规划场景中),而不是我们的最终目标。通俗地讲,我们的最终规划目标,是在保证资源最大使用率的情况下,找出不超过资源最大可用的方案。从输入的方案来看,就是想找出一个尽可能所有规划变量都有值,如果分配的规划变量超过可用范围就用空值代替。因此,我们就会想到,添加一条与独立于业务的约束,用来实现上述意图,这条约束通常是是中间约束(如果使用的是“硬中软”约束结构的话),当然只要使用超过一层的约束,都可以人为地设计一个保持在硬、软约束之间的约束,来实现“尽可以少的规划变量被赋空值”的目标。

为规划变量提供一个“万能”的虚拟值

​  为了避免资源被超用,除上述将规划变量设置为空的方法外,还可以为规划变量的取值范围设置一个无限的虚拟值,在资源规划场景中,可以理解为建立一个虚拟资源,这个虚拟资源具有无限资源量。用来承担那些超出正常资源可用量的分配。还是以CloudBalancing(本文只以该示例的内存限制为唯一分配条件)为例,我们可以在可用的计算机列表中,添加一个内存无限大的计算机。目的是当可用的计算机的内存无法放在所有进程时,超出的进程可以放进这个内存无限大的虚拟计算机中。这种情况与上述将规划变量设定为可以空的情况一样,如果不作任何额外限,有可能得到一个计算结果是所有的进程都被分配到这台虚拟计算机中。因此,需要额外添加一个中间约束,其目的是在确保尽可能使用完所有真实计算机后,才启用这台虚拟计算机。

  以上是在日常跟各位网友的交流中,经常有人提出:​如果任务的资源需求比可用资源量多,希望引擎尽可能满足任务的需求、尽可能分配所有资源,但又想避免一个完全超出资源承受能力的分配方案。其实这种情况在排产、VRP等场景下相当常见。各位遇到这种场景,可以考虑上述两种办法加以处理。

 

本系列文章在公众号不定时连载,请关注公众号(搜“让APS成为可能”或扫以下QR Code)及时接收,二维码:

如需了解更多关于OptaPlanner的应用,请发电邮致:kentbill@gmail.com
或到讨论组发表你的意见:
若有需要可添加本人微信(13631823503)或QQ(12977379)实时沟通,但因本人日常工作繁忙,通过微信,QQ等工具可能无法深入沟通,较复杂的问题,建议以邮件或讨论组方式提出。(讨论组属于google邮件列表,国内网络可能较难访问,需自行解决)