2020年2月25日星期二

OptaPlanner 7.32.0.Final版本彩蛋 - SolverManager之批量求解

上一篇介绍了OptaPlanner 7.32.0.Final版本中的SolverManager接口可以实现异步求解功能。本篇将继续介绍SolverManager的另一大特性 - 批量求解。

适用场景

在日常的规划系统中,求解一个问题,绝大多数情况下,容许运行的时间较有限,特别是在实时性较高的场景中,可让引擎运算时间不多。因此,这种情况下,会在启动了规划运算后,稍等片刻,即需要从求解程序中获取结果。但有些情况下,当我们遇到问题规模较大时,引擎无法在较短时间内找到相对最优解;甚至某些情况下,没有足够长的运行时间,可行解都可能无法找到。至于原因,可以参考我前面关于OptaPlanner入门文章中关于NPC, NP-Hard问题规模的说明。
因此,在一些规模大、时间要求不高的场景下,我们可以让引擎在空余时间自动运算。例如通过定时作业的方式,在非工作时间(例如晚间、节假日等)启动引擎对大多个规模的问题进行规划运算;第二天上班的时候,就可获得运算结果。在发布SolverManager之前,我们也完全可以针对不同的场景,设计相应的定时作业程序,让引擎运算自动运行。当然,这种方法与异步规划的问题一样,需要一定的系统设计经验才能把架构设计完美。而7.32.0.Final版本提供的SolverManager接口,则提供一种更简便的方法来实现些需求。

SolverManager批量规划特性

详细一下SolverManager接口,你应该会发现,与Solver对象的solve方法不同,使用SolverManager的sovle方法对一个问题进行求解时,除了把问题对象作为参数传入solve方法外,还需要传入一个problemID作为参数。其实对于这个参数很好理解,因为SolverManager可以同时对多个问题进行解,必须存在一种方法来识别不同的问题,规划完成后,调用方也需要通过指定的识别号,来获取相应的方案。SolverManager同时对多个问题进行求解时,对问题个数有何要求?它的求解行为是怎么样的呢?

SolverManager批量求解的行为

可同时求解多少个问题?

其实SolverManager不仅可以实现批量求解问题,而且可以实现同时对多 问题并行求解。通过设置SolverManager的parallelSolverCount属性,可以设置引擎在批量运算时,可以并行求解的问题数。即当SolverManger启动求解运算时,会将parallelSolverCount设定的数量的问题载入运算空间并行求解。通常parallelSolverCount值可以根据CPU、内存等计算机资源的情况,及问题的复杂度而推算。若无法判断此数量,也可以将parallelSolverCount设置为AUTO,引擎会根据具体情况,自动确定并行运算问题的数量,通常情况下,并行数是CPU核心数量的一半。
值得注意的是,此处的多个问题并行运算,与之前的求解过程多线程运算(Multithreaded incremental solving)是两个概念。多线程并行运算,指的是引擎在求解一个问题时,会将不同的可能解的子集分成多个线程同时计算(主要是计算约束分数和执行启发式算法)。而SolverManager的批量求解过程中,parallelSolverCount属性设定的,是引擎在面对多个问题时,同时求解的问题个数。大家可以设想,如果把Multithreaded incremental solving也启动起来,令引擎在对一个问题求解时可使用多个CPU核心,同时对多个问题并行求解。这种情况涉及的问题就没那么简单。因此,除非你对问题的复杂程度,CPU的核心和运算能力非常清晰,否则上述两个功能,还是设置为自动更好,引擎会根据计算资源运算时的工况,动态地自动确定并行求解的问题个数,及每个问题求解过程中应启动的线程个数。经历过单CPU多线程编程的朋友应该知道,多线程可以提高资源利用率,但有时候线程数量控制得不好,性能上却是起反效果的,最简单的是CPU的线程切换会消耗一定资源的。

批量求解的作用

在一些不太需要实时规划,规划求解不需要太频繁,运算需时较长的情况,批量求解就可以发挥较好作用。例如需要做一些季度或年度的大型供应链计划,因规划实休数量较大,问题空间可能非常巨大,需要花费相当长的时间才能得行相对最优解,甚至只能是可行解。可通过批量求解的方式,让引擎在空余时间(例如晚上、非工作日)进行运算,从而提高服务器资源的利用率。

基本用法

以下例子是OptaPlanner用户指南的例子,大家先作参考,目前还没有时间去研究SolverManager在示例程序中的代码,暂时也不知道官方示例中是否已经有SolverManager相关代码;若没有,稍后的时候我自己试用一下这些功能,再写一篇东西出来分享给大家。
public class TimeTableService {

    private SolverManager<TimeTable, Long> solverManager;

    // Returns immediately, call it for every dataset
    public void solveBatch(Long timeTableId) {
        solverManager.solve(timeTableId,
                // Called once, when solving starts
                this.findById,
                // Called once, when solving ends
                this.save);
    }

    public TimeTable findById(Long timeTableId) {...}

    public void save(TimeTable timeTable) {...}

}

原创不易,如果觉得文章对你有帮助,欢迎点赞、评论。文章有疏漏之处,欢迎批评指正。
本系列文章在公众号不定时连载,请关注公众号(让APS成为可能)及时接收,二维码:

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

OptaPlanner 7.32.0.Final版本彩蛋 - SolverManager之异步求解

因为工作和其它原因,很长一段时间没有出新的、关于OptaPlanner的文章了,但工余时间并没有停止对该引擎的学习。与此同时Geoffrey大神带领的KIE项目团队并没有闲下来,尽管在工业可用性、易用性和使用门槛方面,OptaPlanner相对传统的求解器已经做得相当出色;特别是在规划过程交互、和各种操作接口方面,更是目前最为容易使用的规划求解器。
以第7版一系列子版本中,OptaPlanner很多子版只作了细微的更新,如优化规划性能,改善Business Center集成水平等。而在作为OptaPlanner直接使用者的我们而言,第7版的所有子版本中,目前本人认为最大最有意义的更新有2个。一个是7.9.0版本提供内了置的多线程规划,从而实现了规划过程中的多CPU同时对同一问题进行运算,大大地发挥了多CPU(核)服务器的并行运算能力。而今天本文需要详解的新增接口SolverManager则是在系统集成方面的另一次重大创新。SolverManager接口在7.32.0版本中发布。

规划服务的常见场景与异步服务

OptaPlanner的核心是一个运筹优化求解器,可以对各领域的规划问题(NPC, NP-Hard问题)进行规划求解,寻找出问题的近似最优解。OptaPlanner规划组件提供了相当完善的求解运算功能。但在实际的规划系统设计中,除了设计相应的规划模型,还需要考虑规划程序部署问题,便于与现有系统集成。这类部署问题并非OptaPlanner求解器自身的功能焦点。因此,对于我们软件开发、工程人员而言,还需要设计好相应的架构系统,才能实现规划程序与现有信息系统之间良好数据交互。
通常情况下规划运算需要使用大量的运算资源,也即CPU运算能力。我们会把基于OptaPlanner的规划程序部署成独立的规划服务,以接口方式与外界系统进行数据通讯。部署成独立的服务除了有利于降低系统模块间低耦合外,另一个重要原因是有利于运算资源的扩展。当问题规划增大时,程序所需的CPU运算能力也会大副提升;独立存在的规划服务更有利于硬件资源的更新。当然,需要在Client端进行即时规划的场景(例如手机导航软件)除外。
因为规划服务大多数情况下,需要一定的运算周期才能得到可行、且相对最优方案。若根据上述的场景需求,在常见的项目中,可以把规划程序做成一个轻量级的Jar包,再过Web和应用服务器,以Web服务的方式对外提供服务。例如使用Spring Boot进行封装,对外提供Web API服务。通过使Spring Boot的Controller与规划程序包在进程上相互独立,从而实现规划服务的异步性。当然也可以通过在Spring Boot程序中通过多线程方式实现异常调用的特性。不同的实现方法视实际需要而定。

SolverManager特性解决异步问题

对于上述场景,OptaPlanner是否可提供Out-Of-The-Box的解决方案呢?在7.32.0.Final版本之前,求解器规划问题时的接口方法是Solver.solve(),这个方法是同步的,需要规划完成后才能返回。若需要实现异步功能,就需要自己想办法实现了,例如上面提到的将服务进程与规划进程相互独立,或使用不同的线程来响应服务和启动规划,实现起来对软件架构设计需要有一定的经验才能做得相对完善。很幸运,在7.32.0.Final版本中,终于从OptaPlanner内置功能上实现了此特性,这个就是SolverManager。SolverManager是7.32.0.Final版本提供的新接口,通过此接口我们可以在调用规划核心程序进行问题求解时,调用线程即时返回,从而实现调用线程与规划线程异步执行。具体访求是:通过SolverManager.solve()方法可以启动一个异步规划方法,调用方可以即时返回,通过轮询的方式调用SolverManager的其它方法来查询规划状态(SolverManger.getSolverStatus)并获取结果(SoverJob.getFinalBestSolution)。SolverManager的基本用法如下:
CloudBalance problem1 = ...;
UUID problemId = UUID.randomUUID();
// Returns immediately
SolverJob<CloudBalance, UUID> solverJob = solverManager.solve(problemId, problem1);
...
CloudBalance solution1;
try {
    // Returns only after solving terminates
    solution1 = solverJob.getFinalBestSolution();
} catch (InterruptedException | ExecutionException e) {
    throw ...;
}
可以看出,使用SolverManager 对一个问题进行求解时,与Solver对象的solve方法有以下区别:
  1. 异步执行,当solve方法被调用后,方法会马上返回,而不待引擎运行结果。调用者需要通过轮询或回调方法(bestSolutionChanged事件)获取运行结果。
  2. 每个问题对应一个ID,因为SolverManager会启动线程池同一时间对多个问题进行求解,因此每个问题需要有一个唯一的标识做识别,在下一篇文章中的SolverManger批量求解中将会详解。
因此,在7.32.0.Final版本中,SolverManager的出现,将会在进行求解服务的设计过程中,大大简化引擎与服务的设计复杂度。希望在未来的应用过让OptaPlanner在工业场景的可能性上更胜一筹。
关于SolverManager接口的详细介绍见以下使用说明:
原创不易,如果觉得文章对你有帮助,欢迎点赞、评论。文章有疏漏之处,欢迎批评指正。
本系列文章在公众号不定时连载,请关注公众号(让APS成为可能)及时接收,二维码:


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

2019年8月22日星期四

APS实现的要点与难点

在前一篇关于文章中讨论了不同层级、粒度的生产计划,在各行业中受重视程度的差异问题。
Kent Zhang:关于APS在企业生产计划上的应用zhuanlan.zhihu.com图标
承蒙大家热烈讨论。本文则在收集各方高见的基础上,对于供应链上各个环节的运营、生产计划再作稍微深入一点的探讨。本文将列举APS技术中常见的重点难点作展开讨论,基保重点的计划场景是制造业的生产计划。本文将基于APS技术、APS项目及APS系统(产品)相关的信息进行探讨。

为何需要APS

APS(高级计划与排程)技术,可以在保证工作安排的可行性基础上,对安排作进一步优化,从而获得一个比人类手动规划更佳的计划方案。该技术的终极目标是,从天文数字多的可能计划方案中,尝试找出最佳的计划方案。但基于NP-Hard问题的特性,可以找到的方案无法证明是最佳的。可是对于实际应用环境而言,APS系统只要可以找到一个计划方案,被证明相对人们手工编排的计划方案更优,即到APS项目的最基本目标;且不论寻找这种优化计划方案的效率远高于人工方式。这种“智能”优化能力,是APS技术的核心价值所在。为了应对市场快速变化、降低成本,制造企业对生产管理提出进一步的精细化管理要求(例如精益生产,在下一篇文章中会对APS技术在精益生产中的应用作详细讨论)。而ERP,MRP等技术日催成熟,从中可获取用于改善管理效果、提高管理精细度的价值越来越小。随着计算机算力的提升,结合各种运筹优化算法(主要是启发式算法)的成熟应用,让信息系统更深入地参与到精细化管理的条件日渐成熟。APS技术则是其中一种将运筹规划技术应用于生产管理的典型案例。
在供应链的生产管理环节(其它环节亦然),形成的生产计划越精细,对生产能力的预判越准确;为市场销售人员提供的产能与资源信息越准确,可推算出越准确可行的交期承诺。在生产管理活动中,编排生产计划时考虑越周全,对突发情况的变应越迅速,对生产作业的安排越精准;越能减少各种资源的不必要等待与浪费,越能减少生产过程中的不增值作业(精益生产的基本要求)。从而降低生产成本,提高产品竞争力。在运营管理活动中,因应市场的需求变化,越快作出最适当的反应,重新确定新的、优化的生产、物流和资源方案的计划方案,越能帮助客户把握商机;更有利于赢取市场。因此,APS技术具有对供应链各环节的周全预测能力,对生产计划作出极度精细化的编排,对需求快速反应等特性;逐渐受到制造业和其它具有规划优化需求行业的青睐。但与很多新兴技术一样,风险、困难往往与价值伴生。那么,要成功实施一个APS项目,并令其发挥预期的效用,需要面临哪些问题呢?

APS项目对企业的信息、流程环境与人员的要求

尽管APS技术存在相当多的优点,可为企业带来其它IT技术以往难企及的收益和管理助力;但这仅仅是基于APS项目能成功部署实施,并正确发挥作用的前提下。因为APS项目的高要求特性,目前各行业能成功将APS技术应用到运营、生产活动中的企业还是小数。原因众多,APS技术的各种困难因素和企业自身的条件均有可能阻碍APS项目的成功实施与应用。传统的企业信息化项目(ERP,CRM,MRP等),通常具有较明显的方案可行性,和效益确定性等特点。相对较容易量化项目的投资及收益。而APS技术是运筹规划领域在企业中的应用,本身带着一定的学术专业性,对项目实施人员有一定的专业要求。另外企业自身的信息化、标准化水平,和供应链各环节的数据和流程完备性,均是APS项目依赖的关键因素。APS项目对部署、实施环境和人员的要求甚高。详细分析如下:
  1. 1. 对APS项目人员的要求甚高。在自研APS系统情况下的项目,项目的关键工作在于规划核心的设计与开发。对于一般规模的商用APS项目而言,企业不可能自主投资开发优化核心(求解器),而是会选购现有的求解器产品,作为运筹优化核心。目前成熟应用于商业的求解器有CPLEX, Gurobi等。开源免费的求解器较具代表性的则有OptaPlannerGoogle OR-Tools,国内的开源求解器目前较知名的有杉数科技的COPT(非开源)。项目组的研发人员掌握这类求解器(或称规划引擎)的应用有一定困难。毕竟运筹优化中的数学规划属于应用数学领域,因此,对于研发人员的数学规划专业能力有一定的要求。同时懂得IT与数学规划的技术人才,是普通企业极度稀缺的人力资源。

  2. 2. 对企业供应链数据质量要求甚高。APS系统能准确地生成生产计划,资源分配方案和产能预测结果;除了建立高质量的规划模型,对被规划的对象要求甚高。一个高质量的规划模型,能准确反映企业供应链的各种约束与优化要求。但在使用这个模型进行规划运算时,提供给它的数据是否准确反映企业的真实情况,数据表达的各种业务状态是否全面,是影响规划效果的另一个要素。尽管建立了精准的规划模型,但作为规划原料的输入数据准确性不佳,或这些输入数据并未能真实全面反映企业真正的业务状况;则系统的输出不可能正确,项目则无法产生应有的价值。

  3. 3. 企业应用部门需对APS技术有正确的理解。若已成功部署一套APS系统,那么如何合理、准确地应用这些APS的输出方案,是另一个难题。APS在制造业上的应用,目前主要的应用于对生产计划进行可行性约束和方案优化。APS输出这此优化后的计划方案,可作为MRP,销售预测,库存控制及生产计划的原始数据。细粒度、规划精细合理的原始数据,甚至可以作为车间作业指令,在自动化程度高的行业,作为车间机台控制和运输调度之用。但在各方面的应用是否合理,则需要各领域的专业人员正确地理解APS的输出数据,将这些数据作为编制各领域的计划方案的基础。若某个领域的专业人员对APS的输出理解不足,则无法充分发挥其价值。

APS项目实施重点与难点

对业务实体与规则的提炼

APS技术不像其它企业信息系统,其重点已经不在于将生产数据的信息化、流程自动化,以达到提高效率的目标。而是着重于根据现有的生产要素,对生产计划作出快速、自动且“智能”的编排,并从中对计划作出进一步的优化。因此,对数据(包括资源信息,订单信息等)的准确性与全面性要求更高。对业务规则、计划的优化目标的理解也要求更准确。因为APS技术实现计划优化的过程,本质上是运筹学上的一种数学规划、寻找极值过程。相应的数学规划模型的质量越高,能获取的优计划方案与实际业务实况越匹配。因此,如何对业务实况进行精确分析,定义准确的业务实体,提炼并综合设计各种业务规则,确定计划的优化目标等工作,成了APS系统开发过程中的关键工作。这些工作也成了APS项目成败的关键因素。

定义评价APS输出结果质量的KPI

此外,因为APS系统输出的原始数据,可作为生产计划、MRP、产能及资源能力评估等不同领域工作的基础数据,所以为APS系统的输出定义好一个合理、客观、可量化的KPI非常重要。这此KPI应该在系统设计之初就确定(这是一个相当大的难点)。用于在对每一个APS的输出进行评估,以确保APS系统的输出是否符合设计预期。因为APS技术中的优化功能,目前主要是通过一些约束求解器的运算获得。而这些求解器中使用的优化算法主要是启发式算法,这类算法可以在绝大多数情况下,在一定程度上对NP-Hard问题找出一个相对优算,但它们不是一种精确算法,即它找到的解,并不确保,也无法证明是最优解(对于NP-Hard问题,目前的技术不可能获得或证明最优解)。因此,对于一个APS项目中,关于APS系统的输出,应该定义一套合理的评估机制与KPI,以确定APS的输出是否达到可行性和相对优化要求。而要定义这些KPI并非易事,因为现实生产环境中,要实现的往往是多目标优化,对于多目标优化,大部分求解器都能找出帕累托最优,但是要确定不同的目标之间的制衡、取舍则需要APS项目人员与用户,在充分理解企业业务现状的前提下,共同努力才能制定;才从多个优化目标的方案集中,找到满足业务要求,并相对优化的计划方案;并确定对这些方案进行评估的KPI。
因为APS技术对于企业提供的流程、数据信息敏感度极高,本小节将进一步将APS所需数据作细分讨论。包括数据的准确性、全面性,业务规则的准确性,和优化目标的合理性。

要求获取准确、全面的“数据”

与其它任何企业信息系统一样,数据是APS系统的主要处理对象与运算基础。这里的数据相对ERP系统而言,是狭义上的“数据”概念,是指企业信息管理系统中的交易数据,例如订单、工单、机台信息、产能等。而那些用于控制管理流程和约束规则相关的数据,则在下一小段讨论。这些交易数据将会作为生成工单的重要信息(工单是APS系统在编排生产计划的主要规划对象);工单需要精确、全面反映生产的各种要求,包括工艺属性、订单要求等。这些信息都能全面就位,才能通过APS对工单的资源、时序和依赖关系进行优化,从而产生可行且优化的生产计划所需的原始数据 。
APS系统的目的,是对生产计划(包括车间、工厂、公司等级别的生产计划)、乃至整个供应链的运营、生产活动进行高质量、高可用性的预判和规划。需要实现该类预判和通盘规划,要求被规划的对象(工单)保证一定程度上的确定性、准确性和全面性,否则有可能差之毫厘之千里。

需要提炼准确、切实的业务约束

每个行业,甚至每个企业都有着千百种不同的业务约束规则。不同的行业生产工序有着不同的工艺要求,相同的行业不同的企业也有着各定制化的业务和工艺约束。针对一个行业或一个企业,可以提炼出的来通用业务规则,通常只占一个APS项目的业务规则中极少部。因此,不同APS项目之间,面对的业务规则千差万别。几乎不存在两个业务约束规则完全相同的APS项目。一些APS产品,在其设计时也不可能针对具体的业务逻辑,设计相应的规则约束。而是提供一些可二次开发的功能、接口针对具体的APS项目作定制开发。例如提供业务实体定制、约束条件定制,甚至提供可表达约束规则的脚本语言,作为复杂业务规则的体现和输出方式。
APS项目过程中,通过对企业业务场景的深入需求调研,分析并识别其中与APS项目相关的业务流程、业务实体与业务约。并从中提炼出APS系统主要的规划对象,归纳影响规划行为的业务制约条件;从而生成规划模型中的约束条件,作为APS引擎的输入。这些约束将会作为规约一个可行生产计划,或资源分配方案的主要参考体系。

需要归纳合理的优化目标

每个考虑需要实施APS项目,以改善供应链质量的企业,其供应链必然面临着一些亟需改善的痛点。如交期达成率低,运营效率过低,生产成本过高。甚至希望在整个供应链中实现完整的精益生产体系。而这些问题,必然是经过一定程度的发展,并通过其它途径的改善,发现仍无法取得理想成效。这些追求更深入更广泛效益的问题,并不是普通企业信息化项目可以解决的。
与上述痛点对应的问题清单中,某一个或数个问题,形成了一个APS项目的优化目标体系。但在实际的企业生产环境中,人们往往对这些目标的理解并未深刻和全面。在APS项目(例如生产计划优化相关的项目)的初期调研时,用户往往把APS的一些功能神化,对未来的系统提出一些不太符合常理的要求与期望。这固然有部分原因是APS厂商,在售前环节中,为了提高自己产品、方案的宣传效果,在未对用户的需求进行深入分析时,对客户提供的不合理需求作出过分许诺有关。一些不切实际的诺言,有可能误导用户,令用户误以为APS技术可以解决他们所有问题的灵丹妙药。而忽视了APS是用于提高计划的可行性、合理性和预判性的,而不是解决生产环节中所有问题。
例如,用户遇到的问题很多是计划执行层面的问题,而非计划制定时可以左右。APS只能在制定计划时,把这些执行层面的问题作为制定计划的考虑因素纳入建模体系,令计划与实际执行活动关联更紧密,降低计划与执行脱节的情况。而具体执行的情况及其控制,严格意义上并不属于APS系统处理范畴。再如,在APS项目中,用户仅收集并提供一些日常生产活动中较表象的问题,而没有分析它们的内在联系,更没有作出归纳总结;随即将这些问题视作APS的优化需求。如:要求订单准时交付率提升到指定的百分比,且成本下降到指定的数值。订单的准时交货率与成本,在某些情况下是一对竞争因素。在一定程度上,通过找到更佳优的计划方案,这两者的竞争程度可以降低,这也是APS的其中一个优化方向。但正确的要求方式,应该是:成本限制在指定范围内,准时交货率最大化。或准时交货率不低于指定值的基础上,成本最小化。也就是,APS可以指定一个因素作为制约条件的前提下,将另一个竞争性的因素作为优化目标,通过运筹优化算法的运算,取得最佳值,从而形成最佳方案。如果要把两个竞争条件都规定为一个固定值,当这两个条件的指定值都在客观许可范围内,APS系统是可能找到同时满足这两个条件的方案的;但若两个竞争因素的固定值所对应的方案客观上是不存在的,那么APS系统也无能为力。
此外,现实环境中,我们面临的问题并不如教科书上的案例那么简单。我们遇到的问题绝大部分规划问题,都是多目标规划问题。正如上述提到的同时对按时交付率与成本都有要求,两者都是优化的目标,那么问题就会复杂得多。其中涉及将如果衡量多个目标的权重,或将多个目标归一为单个目标。具体的业务情况有不同的处理方法,后续将会有文章讨论企业业务环境下的多目标规划问题。

准确掌握计划的松紧度

生产计划,或其它规划行为,都是基于指定约束条件下,对未来事物的一种预判。但从获得这种预判结果,到实际按计划执行,必然存在时间差。在这个差异的时间段内,有可能实际的情况已发生变化,从而让原来已生成的计划与实际情况有所脱节,从而影响计划的可行性 。另一种情况是,计划所产生的约束条件与实际的情况并非完全一致。这种不一致会导致生成的计划发布到实际环境执行时,与实际环境的制约条件存在冲突,从而令计划无法按预定的条件执行。
在上一篇文章中,有些老师就企业生产计划的这个问题提出了一个高尔夫球棒理论,或抓鸟理论。将一只小鸟抓在手里,力度要适中,太松了小鸟会飞走,抓得太紧会把小鸟憋死。计划的制定存在同样的问题。一个计划如果在资源与时间上精确度过高,而不留任何余地,则有可能现实执行环境出现些许微少的变化,都会导致计划不可行。而制定得过于宽松,则失去了计划的意义,在APS生成的优化计划中,更失去了APS的价值。
这种计划遇到变化的情况,不管是人工计划,还是通过APS生成的自动计划,都有可能遇见。通常我们的处理方法有以下3种:
  1. 1. 以滚动计划的方式对计划进行逐步细化。即对于与当前时间较接近的时段,实行详细的计划方案。因为计划执行的时点距当前时间越短,发生条件变更的可能性越低,且时间越接近,获得的环境制约要素越准确,越能确保工作可按计划执行。而对于计划执行时点距当前时间较远的部分,则仅提供粒度较粗,存在较大冗余的高层次计划;以应对这段较长时段内产生的不可见的情况,令计划就对环境变更的能力更高。

  2. 2. 为计划中高可变性的工作项,设定合理的冗余量。对于一些约束条件变更可能性较高的计划,为了让计划不至于稍有少许环境条件变更,即变得无法执行,可以在制定计划时,为这些工作项设定一个冗余量(或称缓冲)。在执行时遇到的环境条件变化,这些工作项也具有一定的应对空间,从而降低计划变为不可执行的可能性。

  3. 3. 采用实时计划对环境条件变化作出快速反应,并保持非易失性(连贯性)。有些APS产品或规划引擎,可提供不间断的规划功能。如OptaPlanner规划引擎就提供了Real Time Planning特性。这种特性非常适合于一些对规划动作要求作出实时、不间断应变的场景。例如VRP,车间作业指令等规划场景。实时规划系统在完成一轮规划后,系统并未结束运行,而仅结束了规划运算行为,进程仍处于就绪状态,一旦因计划的对象或其它要素发生变化,即会触发新一轮规划运算。在实践中发现,实时规划运算不仅能让系统具,对变化具备实时反应能力,且对于前后两次的规划行为,可以好地保持规则的连贯性(后续将会相关文章详解规划的易失性问题)。即非实时计划前后两次规划的连贯性,在实时规划中更容易实现。因为对于非实时规划,前后两轮的规划运算面对是两个不同的数据环境,第一轮规划的上下文无法完全传递到第二次规划运算中。而实时规划因为其系统的规划进程并没有结束,仅仅是结束了规划运算,处于“暂停”状态。因此,实时规划当接收到重启指令后,它是完全沿用上一轮规划所得的上下文环境,从而更能确保规划的连贯性。其实需要保持计划的连贯性并非易事,需要在建模时作出一定的考量,并以相关的约束或其它限制方式,对引擎的规划行为作出一定程序的限制。

APS的输出反馈于输入,改善约束与目标

无论何种系统,从设计到上线过程,伴随着需求的不断变更,这并不是说项目范围控制得不好,而是软件项目本身存在极高的不确定性。有可能是未到具体设计实践阶段,需求本身无法得到验证而体现出来的不确定性;从而需要在设计开发过程中作出一定程度的修正。也有可能项目开发周期足够长久,原来的需求在设计实现阶段,已经产生一定的变化。因此,软件项目的开发实施过程,或多或少都伴随着变化。
而APS项目这种变化更甚。APS项目在成功上线后,必然存在一段比其它信息系统项目更长的磨合期。APS系统在这个磨合期内,不仅是对需求的进一步细化、优化和改进;更是对规划约束的进一步明确和修正,更多明显的是对优化目标的进一步调整。因为APS项目的目标,本身是为生产计划等规划工作,寻找一些人类难以获取的更佳方案;而获得这些方案后,人们会基于这些以往无法获得的方案作更深入的思考,会构思出一些以往不会产生的想法或优化目标。因此,APS项目在系统上线后的使用过程中,都伴随着不断的优化,甚至一直延续在整个系统生命周期。
在用户对APS系统的优化行为,输出结果有一定的认识,并收集、更新并总结了一定的规律后,就会在根据掌握的信息,对其优化目标进行进一步的优化,从而令系统输出与现实业务场景更匹配的方案。
随着近年APS相关资料的普及,很多用户在项目开始前,已经懂得提出要求系统输出多种不同的优化目标的方案,从中比较不同的优化策略,经过分析后选用适合的方案。经常会有用户以导航软件为例提出需求:系统应该可以提供不同情况下的规划方案,就如我需要导航去某地,导航软件可以根据路程、费用和路况,提供不同的路线方案。我们可以视情选取合适的方案。事实上这是业界的一种进步,反映了用户已经懂得APS的基本原理和作用。它并不是按照既定要求找出一个固定计划方案,而是从限定条件中找出目前找到的最佳方案。

APS产生的计划真的可行吗?可行条件如何变化?

计划是否可行,需要进行多方案、多维度的考量。主要包:
  1. 计划的时效性丧失。计划可被执行的一些必要条件,在执行时已消失。计划变成不再可行,上文已讨论过。
  2. 对规划模型中的考数据把握不准确、考虑不周全;令引擎在生成计划时,寻找到一些人们未能预想的情况。计划变成不可行, 上文已讨论过。
  3. 可行计划的约束条件转变。一些本认为是可妥协、可让步的限制条件被设计成软约束,但所得的方案中,该类条件的违反程度远超预期。
下面对第3种情况作详细论述。
在数学规划中,规划模型通常由限定条件(Subject To)和目标函数两部分。在APS技术中的规划模型中,通常也有对于业务的硬性约束条件,即计划必须在满足这些硬性约束条件的前提下,计划才能执行。这部分的约束对应于数学规划模型中的限定条件。而APS的另一个作用,则是寻找一个更优的计划方案,在APS规划模型中被称为软约束。它对应于数学规划模型中的目标函数,即规划过程中用于求解限定条件下的极值函数。因此,对于数学规划的目标函数,APS规划模型中相应地以软约束的形式体现。也即是软约束是为了寻找最佳计划方案设定在的。
在APS的规划述语中,违反硬性约束的方案被称为不可行方案,满足所有硬性约束的方案被称为可行方案。在APS生成的计划方案中,一个可行计划往往是一个所有硬性约束都没有违反的计划,在实际生产活动中,理论上是具有可执行性的。而一些违反了硬性约束的方案则不具有可执行性,在此不必详议不可行计划。但在实际的生产经营活动中,可行性计划的定义会更狭窄。一些虽然所有硬性约束都符合,但对于软性约束违反达到一定程度的计划方案,也有可能被划定为不可行。也就是说,软约束在实际的计划方案中,有可能出现“由量变达到质变”的过程;因为软约束的量过大,而质变成不可行计划。
例如:一个简单的生产计划仅有一个优化目标(事实上这是理想状态,多目标规划才是世界的实况) - 降低成本。也就是APS规划出来的计划,需要尽可能降低成本。那么在设计规划模型时,成本因素就会变成唯一一个软约束,而其它交期、工艺参数等因素则作为硬约束。理论上无论按计划生产的成本多高,只要计划安排符合了交期和工艺参数的要求,它就是一个可行的计划。但实现的生产活动中,成本是有上限的。例如,如果满足了交期和工艺参数两个硬性条件,按该生产计划生产出来的产品,其成本却侵蚀了最低利润。那么在单纯的商业角度来看,该计划已经不可行了。此时,这个方案则有可能成为一个“符合了所有硬约束的不可行方案”。对于实际的生产经营活动,这种计划方案是无法执行,不具备价值的。当然,读者可能会想到,那到成本应该也被定义为一个硬约束,只不过这个硬约束不是定性的,而是定量的。也就是达到一定的量才会被视作违反。这是正确的,在后续的文章中,我会对软硬两种约束的关系展开讨论,这是APS领域的另一大课题。
以上是本人在APS项目实践及一些前人的基础上稍作总结的要点,希望可以将各种零散的问题放在一起,让大家可以更容易了解探讨一下APS技术,APS项目和APS系统中常见的问题,难点,重点及常见的处理办法。希望大家共同探讨。
End

2019年7月2日星期二

Optaplanner与Google OR-Tools的区别

在规划相关的项目工作中,近两年我们的项目主要使用的是Optaplanner作为规划引擎,其核心也是一个的规划求解器(Solver)。但作为另一个著名开源求解器Google OR-Tools(下称OR-Tools)也日渐流行。且因Google自带流量的支持,OR-Tools有更多专门研究运筹的学者使用和研究。而Optaplanner则更偏向工程实践上的应用。本文就二者在技术特性、使用方法与场景等方面,列出若干差异。希望为需要使用开源求解器进行项目工作的同行提供初步入门参考与选择。

简介

Optaplanner

Optaplanner目前是Apache基金会的一款开源软件,JBOSS社区,基于Apache开源软件协议,该协议对商用友好,因此可以自由地将该技术的部门或全部应用于商用软件项目中。该项目目前由受雇于Redhat的团队在维护.其创业人Geoffrey De Smit先生作为该项目的Leader. 其实Optaplanner已发展了十余年,最初是由Geoffrey在参加运筹规划大赛中,针对各种竞赛题目 开发的一个求解器。后来将它贡献给开源社区,并作为开源项目一直维护至今,其版本发布仍十分高效,除进行一些对用户透明不可视的算法与架构优化外,不时还有极具价值的新功能与新特征发布,如7.09版本发布的多线程支持,本人认为是极具里程碑意义的新特征,可以令对运算资源敏感的求解过程,最大程度上提高对CPU的利用率。

Google OR-Tools

Google OR-Tools, 顾名思义是由Google提供的一套运筹规划的运算工具,它针对不同的规划场景,提供了不同的求解器(以组件方式提供)。OR-Tools同样是基于Apache开源软件协议,它是由受雇于Google的Laurent Perron博士带领团队维护。OR-Tools的讨论区讨论相当热烈,主要原因是它的使用方法与传统商用的求解器(如Cplex, Gurobi等)相当类似,因此相当一些运筹学的学者、学生对该软件比较感兴趣。
下面,从使用方法,结构构成等方面,分别对两个规划引擎进行分别讨论。

开发技术与使用方式的区别

Optaplanner的技术特性

Optaplanner是使用Java语言开发,是基于纯Java技术。因此,使用它的时候也只需要使用Java语言本身的特性,即可满足几乎所有基本的建模、开发及求解过程;而无需使用其它第三方的技术或框架。当然当你在实际的工程实践中,还是需要依赖强大的Java生态圈,才能让项目事半功倍。例如通过第三方组件实现日志,数据的持久化、Web服务等。
Optaplanner的评分逻辑,需要使用Drools作为规则描述语言,实现约束的评分。事实上Optaplanner同时支持Java语言实现约束评分的,即Easy Java Score Calculation与Incremental Java Score Calculation,使用这两种评分方式,评分逻辑可直接使用Java语言实现。仅需通过POJO即可对业务实体进行建模,通过Java程序代码即可描述业务约束。Optaplanner的核心程序以Jar包方式提供;当然你也可以获取它的源代码,从源代码级把它的核心集成到你自己的系统中去。但作为商业软件项目,此方法并非最佳实践,直接使用官方发布的Jar 包即可。Optaplanner不支持MiniZinc作为建模语言,OR-Tools则支持该种约束建模语言。在对MiniZinc的支持方面,可能各位ORer感觉有些许遗憾。

与既有系统集成成

从另一个角度来看,纯Java技术实现的Optaplanner,对使用环境起到简化作用的同时,又会形成了一种限制。例如对于一些非Java技术开发的系统(例如一些旧系统),要与Optaplanner集成到同一个程序中,则无法实现尝试结合。对于这种情况,解决办法是将Optaplanner独立成一个Web服务,以WebAPI 的方式对外提供服务。事实上这种系统结构即使是在整个项目都是用Java开发,也是值得推荐的方法。因为规划服务程序在运行的时候,主要占用的资源是CPU的运算资料,在一些规模大,规则复杂的规划程序中,对CPU资源的占用更明显。从另一方面来看,在某些复杂的规划场景中,CPU的性能,直接决定了在固定时间内,找到相对最优方案的质量。因此,将规划服务独立成一个服务,使用独立的服务器资源作为运行环境,为规划引擎提供充足的CPU资源;同时也消除了规划运算对系统其它部分的影响。

Google OR-Tools的技术特性

OR-Tools内核是使用C++开发,因此,其兼任性相对Optapalnner来说好很多。目前Google OR-Tools支持C++, C#, Java和Python四种语言接口。即它具有动态链接库存(DLL), Jar包和Python包三种提供提供形式。当然因为它的原始形式是dll文件,用过Java对它进行调用的时候,就需要通过JNI对它进行装载,下文的示例中会展示。因为OR-Tools提供丰富的兼容形式,因此,与不同系统集成较容易。可直接将它的源代码或DLL嵌入到自己的系统中去。当然,如果使用源代码的方式集成,只能嵌入到C++开发的系统中。
建模语言方面,OR-Tools同时支持使用程序语言(Python, C++, Java, C#)描述模型,如上文提到,它同时也支持MiniZinc作为约束建模语言。各位科班出身的ORer应该对此较有亲切感。也因此在OR-Tools的讨论区,其中提出讨论的问题,除了工程实践的问题,还有非常多是运筹学方面较专业的理论问题。这也许反映了世界各地存在着大量的ORer正在使用OR-Tools作为他们的研究工具。

与既然有系统的体成

在系统集成方面,因为OR-Tools接口相对开放,集成的问题则基本上不存在任何问题。其核心(规划求解器)可以作为系统的一个组件存在于任何系统中;也可以将其封装成一个服务对外提供服务。

建模方式的区别

在建模方式方面,两者都可以使用程序设计语言进行规则、约束描述。同时也可使用使用其它专用的约束或建模语言;Optaplanner支持Drools, OR-Tools支持MiniZinc。但两者面对的场景,或说偏向解决的具体问题,还是有区别的。

Optaplanner更偏向于面向对象

使用Optaplanner进行系统开发的时候(例如开发APS系统),如其它商用软件一样,先对业务进行分析,设计出具体的业务实体,识别出需要规则的实体和因素(字段),提炼出业务规则,归纳出哪些规则是硬约束,哪些是可以优化的软约束。然后根据Optaplanner的固定对象结构模式,建立Planning Entity, Planning Variable,Problem Fact和Solution等类;并配置好求解器的各种参数。整个核心系统的设计就差不多完成了。

Google OR-Tools偏向于传统的数据建模

OR-Tools除了同样需要进行业务分析与设计外,还需要加多一步工作 - 数学建模。因为OR-Tools求解规划问题时,输出的必须是一个完整的数学模型。也就是在使用OR-Tools进行系统开发时,需要先进行业务分析设计,获得各种业务要素和约束后,需要对这些业务要素进行数学建模,并将这个模型以程序语言(Python, C++, Java, C#)或MiniZinc进行模型描述。然后才能启动规划求解器进行寻找优势方案。实现Optaplanner在使用其求解器进行规划求解时,也需要有相应的数学模型的,只不过它可以在求解之前,把用Java对象表示的业务模型,转换成数学模型;而这个步骤对使用都来说是透明的,因此无需关心。

使用场景的区别

基于上一节中两者建模方式上的差别,对于偏向于理论研究、学习的学者来说,OR-Tools更接近于他们日常接触的各类规模模型,与CPLEX和Gurobi等知名商用(有免费的学术用途授权)求解器的应用方法与设计思想均较接近。因此,对于一些考研类的应用场景,OR-Tools来得更直接。
而Optaplanner则更趋向解决具体的业务问题,从其诞生的背景可以得知,它主要是为解决具体问题而生的。关于 Optaplanner的来历,可以参考其作者Geoffrey的一篇博文《A decade of OptaPlanner》。尽管Optaplanner与OR-Tools其核心是相当接近的,都是通过各种启发式算法,对NP-Hard问题寻找相对最优解。但Optaplanner考虑到非运筹专业人员的数学功底,对问题多做了一层封装,将程序中描述业务问题的各种对象,转换成相应的规划模型,再进行规划求解。从而在商用软件开发环境中,普通的程序设计人员,只需要关注具体的业务细则,根据Optaplanner提供的模式,建立合理的对象模型,来反映业务模型,确保这些业务模型能准确地反映业务需求即可。而无需再将这些业务模型转换成可运筹学上数学规划所需的数学规划模型。从而大大降低了规划程序的开发难度。

从规划到AI

目前两个引擎都号称自己属于AI约束求解器,OR-Tools被纳入作为Google AI的其中一个产品。也难惨,毕竟这两个引擎的规划求解器都是基于启发式算法,确实有对于NP-Hard问题,启发式算法是目前较常用的算法,而这些算法对数据的各要素的具体分布情况依赖较大。一定程度上体现了“智能”的感觉。不过我更觉得这是为了蹭近年AI的火,觉得没必要呀,虽然AI的核心算法追溯回去与运筹规划是同源的。但运筹毕竟已经是一个很成熟独立的分支了。


Google OR-Tools最基础入门

以下代码是OR-Tools的一个最基本的入门示例,它解决的是《Excel与Google Sheets中实现线性规划求解》一文中的生产资源优化问题。读者可以结合这篇文章中相关的模型,来对照这些代码进行理解,从中理解OR-Tools在进行规划求解时所需的规划模型的建立方法。

数学模型

import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;

public class HelloOR {
        // 通过JNI调用OR-Tools包
 static { System.loadLibrary("resources/jniortools"); }

         // 创建求解器对象
  private static MPSolver createSolver (String solverType) {
     return new MPSolver("my_program", MPSolver.OptimizationProblemType.valueOf(solverType));
  }

          // 程序入口,创建一个线性规划求解器,并求解规模模型。
          public static void main(String[] args) throws Exception {
     solverTest("GLOP_LINEAR_PROGRAMMING");
   }

   private static void solverTest(String solverType) {
     MPSolver solver = createSolver(solverType);
     // 创建决策变量,Optaplanner中称为Planning Variable, 规划变量.
     double infinity = MPSolver.infinity();
     MPVariable x = solver.makeIntVar(0.0, infinity, "x");
     MPVariable y = solver.makeIntVar(0.0, infinity, "y");
     
     // 创建约束
     //资源1限制: 5x + 3y <= 280
     MPConstraint c1 = solver.makeConstraint(-infinity, 280);
     c1.setCoefficient(x, 5);
     c1.setCoefficient(y, 3);
     
     //资源2限制: 4x + 8y <= 580
     MPConstraint c2 = solver.makeConstraint(-infinity, 580);
     c2.setCoefficient(x, 4);
     c2.setCoefficient(y, 8);
     
     //资源3限制: 3x + 5y <= 360
     MPConstraint c3 = solver.makeConstraint(-infinity, 360);
     c3.setCoefficient(x, 3);
     c3.setCoefficient(y, 5);
     
     // 创建目标函数,求20*x + 25*y 的最大值.
     MPObjective objective = solver.objective();
     objective.setCoefficient(x, 20);
     objective.setCoefficient(y, 25);
     objective.setMaximization();
     
     // 调用求解器求解模型,并输出结果.
     solver.solve();
     System.out.println("Solution:");
     System.out.println("x = " + x.solutionValue());
     System.out.println("y = " + y.solutionValue());
     System.out.println("20x + 25y = " + (20 * x.solutionValue() + 25 * y.solutionValue()));
   }

  
}

可以看到,使用OR-Tools里,需要先建立Solver对,并将模型中的各不等式以系数方式体现到程序中,最后求解得出结果。因为这是一个线性规划问题,因此代码中创建的是一个线性求解器(以GLOP_LINEAR_PROGRAMMING参数表示)。尽管都是规划问题,但针对不同同的类型,OR-Tools提供不同的Solver解,例如线性规划问题,TSP问题等,有专用的Solver对象解决。
输出结果为:

关于Optaplanner的使用方法,则可以《Optaplanner规划引擎的工作原理及简单示例(2)》。
  • End.
如需了解更多关于Optaplanner的应用,请发电邮致:kentbill@gmail.com或到讨论组发表你的意见:
https://groups.google.com/forum/#!forum/optaplanner-cngroups.google.com
若有需要可添加本人微信(13631823503)或QQ(12977379)实时沟通,但因本人日常工作繁忙,通过微信,QQ等工具可能无法深入沟通,较复杂的问题,建议以邮件或讨论组方式提出。(讨论组属于google邮件列表,国内网络可能较难访问,需自行解决)

OptaPlanner 7.32.0.Final版本彩蛋 - SolverManager之批量求解

上一篇介绍了OptaPlanner 7.32.0.Final版本中的SolverManager接口可以实现异步求解功能。本篇将继续介绍SolverManager的另一大特性 - 批量求解。 适用场景 在日常的规划系统中,求解一个问题,绝大多数情况下,容许运行的时间较有限...