2018年10月11日星期四

人工智能包括约束求解器吗?

  以下是翻译Optaplanner创始人Geoffrey De Smet的一篇文章《Does A.I. include constraint solvers?》。
  因为英语及中文表达习惯的差异,以该博文发表示Optaplanner官网,其描述的问题及概念具有一定的上下文关联性;因此,为了认还不太熟悉Optaplanner的同学更容易理解,令文章更符合中文母语读者的阅读习惯,我并没有完全按字面生硬直译。其中添加了一些扩展性的意译,基本上能在脱离Optaplanner官网上下文情况下,一定程序上表达到Geoffrey的意思吧,有不正之处请大家多多指点。为谢!

  人工智能的寒冬已经过去,这几年以来,人工智能技术的关注点又出现了增长。不仅仅是我们这些人工智能方面的极客,商界也因看到了其潜力,而进行了投资。为了获得资本青睐,一些研究项目也被重新塑造,贴上人工智能技术的名头。那么,约束求解器能否也使用人工智能的标签呢?

历史小知识:第5代(计算机)计划

  近20年以来,人工智能是个不太受人待见的语汇,要了解其原因,我们需要回到1982年,当时日本决定大力投资第5代计算机 - 一个人工智能平台,将要超越现有的计算机,并打破IBM的垄断。作为应对与跟进措施,其它国家也启动了类似的计划,突然间,研究经费从天而降,引致80年代的人工智能热潮。
  最终计划还是失败了。尽管获得了近10年的资助,但第5代计划的研究中,几乎没有展示出任何实用的成果。之前的一些研究,包括:大数据,智能电话和更高速的计划机,均未达到可行。其它一些研究则完全无用。
  这些研究失败以后,在上世纪90年代及2000年代初,人工智能的概念被彻底败坏了,人们都认为人工智能是不可行的。技术开发界很快结束了他们的人工智能技术名头。约束求解器则加强了与运筹学的相关性;搜索引擎只扮演了一个简单的字典搜索功能;规则引擎则侧重于决策表方面的发展。这些领域都避免提及它们与人工智能相关。而神经网络研究是个例外。

 神经网络算法:一项技术吃通天下?

  过去几年间,神经网络算法令人工智能技术再次神奇起来。神经网络算法模拟我们大脑中的神经元(其实不如你想象那样).它是一个黑盒,可以将输入数据转换成你想要的输出数据,这功能主要通过多层神经网络的加总相乘算法实现。数十年来,这类算法均存在精度过低的问题,但近期兴起的大数据,及对更好反向传播算法的发现,此情况出现了翻天覆地的变化。其中后者使用了多层神经网络,神经网络层越多,则相当于实现了一种深度学习。
  时至今日,神经网络算法已经可以进行人脸和声音识别,若与其它人工智能技术(例如:极小极大算法,泽者注:一种博弈算法 )混合使用,这些程序甚至可以击败(象棋)世界冠军,听起来非常神奇。但终究到底,这些都属于模式识别问题;若面对其它(泽者注:非模式识别)问题,这些技术是处理不了的。例如,神经网络算法无法找到一条从罗浮宫到罗马斗兽场的最快路径,无法创建一套美国公路旅行指南

人工智能的正确应用

  神经网络并不是一种普适的人工智能算法, 也不是一种约束求解器或生产规则系统。就此而言,每一类算法,只能解决人工智能领域中的一些部分问题。这也许是一件好事:不存在哪一种算法会把自己训练成天网(译者注:电影《终结者》中的人工智能防御系统),进而对人类构成威胁。
  因此,通过智能软件去解决业务问题,需要根据具体用例来选择合适的算法:
theRightAIForTheJob
借用的原文图 

  但这(译者注:神经网络的模式识别局限性)并没有阻止学者们的尝试,有很多关于使用神经网络算法去解决车辆路线规划雇员排班的研究,只是其符合度还不如约束求解算法,例如:禁忌搜索法和模拟退火法。当有15%的行驶时间节省量时,为什么要满足于1%的节省量呢(译者注:在车辆路线规划案例中,通过约束求解算法能得到15%的行驶时间节省,为什么还要退而求其次,满足于神经网络算法得到的1%节省量呢)
  相反,约束求解算法却无法解决臭名昭著的关于热狗的图像识别问题。

所有的算法都可以产生智能吗?

  尽管计算1234乘以5678的结果并不容易,但我们并不认为这个计算方法是一种人工智能。同理,那些排序算法也不是人工智能,为什么呢? 
  也许是因为这些问题都不存在误差容限,但人工智能却存在,例如:你给出一张哈仕奇的图片,有人把它识别为狼;当你给出一个TSP问题,需要画出最短旅行路线时,人们会给出不同质量的确定性的结果集
  或者那些计算和排序算法是可以被人类理解得到的,这些算法并不是一个黑盒,它可以相当容易地知道,计算机是如何把输入数据,一个指令接着一个指令地转化为输出结果。

约束求解决器的求解又是怎样的一个动作过程呢?

  从历史上看,约束求解器(如Optaplanner)明显是运筹学的一个分支领域,同时也不能排除它属于其它领域(泽者注:约束求解器不仅仅属于运筹学领域).我认为约束求解器也可以纳入人工智能领域,不仅仅是一些论文和书刊如是说,主要是因为掌握约束求解器的应用案例,本身就是已经是一个复杂问题。无论是人类的规划师排出来的解决方案,还是特定算法得出来的解,其质量者具有巨大的不确定性。若给定一个足够大的数据集(译者注:问题数据集),是不可能找到一个绝对最优解的。此外,尽管现有的一些算法已有40年历史了,但研究 人员仍在寻找并发现一些新的算法。
  你觉得呢?约束求解器是不是人工智能的其中一个分支?

 如需了解更多关于Optaplanner的应用,请发电邮致:kentbill@gmail.com

多工序、多机台(产线)环境下的排程要点

关于生产计划排程的种类及其特性

释义:文中提到的资源,是指需要完成一个生产作业(或称任务,生产任务)所需的生产条件,例如机台、原料等,称为广义资源。 
对于生产计划,常见有以下四种类型:
  • 单一工序,单一资源种类.
  • 单一工序,多资源种类.
  • 多工序,单一资源种类(较少见).
  • 多工序,多资源种类.
  下面对上述四种生产计划进行逐一分析,本文的分析,着重于计划的优化实现,而不是硬性规则的确保。例如通过工序的就绪情况来确定资源的就绪要求,例如MRP等,这些硬性的约束可以通过规则引擎(例如Drools)来确保在生成计划过程中,计划的安排满足各种业务规则;而无需通过规划引擎(例如Optaplanner),在满足了硬性业务规则的基础上进一步优化。

 单一工序,单一资源种类

  对于单一工序,单一种类资源的情况,是最简单的一种排程场景。即一个产品的生产过程只需使用同一种资源,进行一次加工即完成了产品的整个生产过程。这种情况下,既然是单一工序,那也就没有了工序的先后资源的限制;单一种类资源,即表示没有了资源的选择优化。在生产实践中,此类生产计划通常是对产品工序路线中,众多工序中的一个较重要的工序进行制定计划时使用。需要进行优化的主要是对资源的使用分配,例如各机之间实现负荷平衡等需求。我们在实现这类计划时,需要通过设定机台平衡的约束,让引擎在为工序分配任务时,尽可能地实现同一类机的负荷平衡。例如在印刷生产中,对排在最后的手工工序制定生产计划时,需要根据各个产线的人力安排情况,按比例安排定额任务。这些情况可使用“单一工序、单一种类”资源计划。

 单一工序,多资源种类

  单一工序 ,多种类资源情况,仅对产品的一个工序进行排产,仅可用于这个工序的资源是多种多样的,并且各种资源之间可以互换的。此类计划主要是为了实现资源的优化分配。即按照一定的原则来对各个工序进行资源安排。例如:各种资源使用成本各不相同,在制定计划时,为了降低生产成本,应该在确保其它更高优先级的约束或硬性约束的前提下,尽量使用低成本的资源进行生产。举个实际的例子,在印刷行业中,对于对印张进行印刷的工序,有些印张可以通过CMYK四色印制,也可以通过调配特殊色,通过专色印制;但前者的成本相比后者更低,前后两种印刷方式就表示两种资源。在对印刷工序定制生产计划时,就会优先使用CMYK印刷,但这个也不是绝对的,例如如果CMYK资源已经超出负荷时,不动用专色印刷就无法实现按时交货时,还是会放弃成本这个约束,来迁就交期这个更高优先级的约束的。

多工序,单一资源种类

  多个工序,单一种类资源的情况,则相对较少见。即计划中需要制定整个产品工序路线中的所有工序的资源和时间,其中资源只需要只有一种可选。可以理解到,这种情况对资源分配的要求就较低了,计划着重于对工序的前后关系制约了或工序自身的其它因素的优化。即是在资源分配上,如第一种情况:“单一资源、单一任务”一样,基于资源利用的一些原则进行资源分配。而在安排工序的加工时间问题上,则需要根据产品的工序路线,实现对前后工序在时间上的次序关系;而这种次序又受到资源分配的限制。例如:如果印刷的第二工序中(有些企业称为印后加工),有过油、过胶、过UV三个工序,如果有一种机台同时可以实现这三种工序的,那么就满足了“多个工序、单一资源种类”的场景。这时候关于工序的资源分配,会有相应的资源使用约束。但更重要的约束是:一个产品的多个工序的处理次序上,这个次序必然是根据产品的工序路线设定的资源来执行的,否则就违反了硬性约束。所以,综合上述的资源分配和工序资源两种要求,我们需要面对的是两上互相矛盾的问题:1. 对于同一个产品需要确保其执行的工序与工序路线上设定的一致, 2. 对于一个资源(例如机台)上的生产效率而言,如何可以实现更多的同工序连接生产,因为即使是使用同一资源,通常在该资源上,不同工序的生产任务之间的切换,会产生成本的,有可能是时间成本,也有可能是具体的货币成本。所以,难点就在于如何平衡上面两个问题,从而实现资源利用率最大化和工序资源不被违反。

多工序,多资源种类

  多个工序,多资源种类的和产计划,也是目前最为常见,也是最为复杂的生产计划,是本文讨论的重点。多工序与前一个问题一样,是针对整个产品的工序路线进行排产。而且生产各个工序所用的资源是不同种类的。因此,这种情况我们面对了两个相对零散也有交互的矛盾:1. 对于一个产品而言,其多个工序是依据工序路线形成生产资源的; 2. 多种资源就表示各个生产工序所使用的资源有可能不一样,也有可能一样的。因为工序的前后次序的限制原因,当引擎在对一个工序完成了资源分配后,进一步进行生产时间的分配,但因为同一产品的工序执行次序,是需要按照工序路线的先后次序来执行的,也就是说计划中,除了需要分配好的资源外,还要确保这个资源在指定的时间段内,没有被其它产品的生产任务占用。那么当同时对多个产品进行排产时,各个产品的工序路线形成的工序生产序列和资源分配方案,很容易就形成了胶着状态,甚至在多个资源之间会出现死锁状态。
   下面,我们以多个不同种类的机台,处理工序路线上多个工序的案例,来计划“多工序、多资源种类”的情况,并分析需要实现这种计划,所需的技巧、技术难点和可能出现的情况,及其应对方法.

多工序与多机台的场景描述

规划过程中用到的概念

  为了便于描述规划过程中的各种情况,现先定义以下概念:
  任务或生产任务:一个产品的一个工序的生产作业称作一个任务,例如印刷后加工有:过胶 -> 烫金 -> 丝印,则表示这个产品的后加工中有三个任务,分别是过胶任务, 烫金任务和丝印任务。
  工序路线任务链:一个产品中的不同工序对应的生产作业,其次序是由其工序路线确定的,一个产品的所有生产作业序列,即任务序列,称为工序路线任务链.
  机台任务链:多个任务被分配在一个机台上时,同一时间只能处理一个产品,即同一时间只能进行一个任务,这些同在一机台上形成的任务序列,称为机台任务链接.
  前置任务,后置任务:同一产品上多个任务,根据工序路线的规定形成与工序次序一次的生产任务次序(即工序路线任务链)。在链中两个相邻的任务,前者称作后者的前置任务;后者称作前者的后置任务。
  前一任务,后一任务:分布于同一机台上的多个工序任务(即机台任务链),在机台任务链中相个相邻的任务;前者称为后者的前一任务,后者称作前者的前一任务。

多工序、多机台排程里的限制

  下面我们来针对实用性最强,制造业面对最多的场景 :多工序、多台机台场景展开讨论。处理这类生产计划,有以下两个因素处理起来最为麻烦。
  1. 多任务与多机台的匹配
    因为在待排的计划要素中,任务与机台的种类都存在多样性,且可能存一种任务可分配到多种机台,一种机台可以做多种任务的情况,因此,任务与机台的匹配问题会相对其它三种生产计划复杂一些。但往往这也是体现出Optaplanner价值的其中一个要点。

  2. 工序路线任务链与机台任务链之间存在互相制约关系

    一个产品的工序中线确定的任务序列,与分配于同一机台上的任务序列,在加工次序上存在互相制约。加工次序体现在加工的时间先后。即一个产品的任务序列,必然按其工序路线,存在一定的先后次序。而当个产品被分配到各个机台上进行生产作业时,因为生产路线上存在时间先后次序,会令到一个机台上多个任务需要按次序生产的时候,每个任务的作业时间段可能并不是紧密连接。因为当准备在机台上启动一个任务时,这个任务的前置工序可能尚未完成,从而令到该任务所在的机台已就绪(其前一任务已完成,机台已为该任务准备就绪),但因为它的前置工序还没完成,导致它无法开始,因为一旦开始就违反了工序路线约束,从而令该机台上排在它后面的其它后任务都要推迟,而这些任务被推迟,又有可能导致它们自身的后置任务需要推迟,从而会出现机台任务链和工序路线任务链互相影响。我们称这种情况为“连锁反应”,解决好这种连锁反应,是解决排程的关键。
  因为上述描述的连锁反应的情况出现,有可能令出现环状影响的情况。因为一个正常的产计划会存在时间空间两个主要维度,其中的空间维度本文的场景中就是机台,表示为一个任务被分配到了指定机台。而时间维度则体现为任务的开始时间和结束时间(事实上结束时间可以通过开始时间推导出来),即确定一个任务的计划开始时刻。那么就需要有一个逻辑,对各个已分配空间(即机台)的任务进行时间推导。任务的时间推导我们需要通过Optaplanner的afterEntityChanged事件来进行(这个事件仅出现于Chained Through Time模式, 以后将会有专门的文章讲述Optaplanner的时间分配模式,其中Chained Through Time模式是重点),而推导的起源(就是从哪个任务开始推)我们通常是以当前Move(Move是Optaplanner的最小作业单位)所处理的任务开始,这个任务我们称为震动源。经过它的工序路线任务链传递到机台任务链,再由机台任务链的影响回工序路线任务链,当这种环状的影响线路,经过一系列的连锁反应,正好返回来对震动源进行推导的时候, 那么相当于又开始了轮与上一轮一样的推导路线,就会无限地推导下去,死循环就产生了。我们需要准确识别这种连锁反应会否产生死循环,并当确实产生死循环时,就要将当前的move标识的不合法,在开启时间推导之前,通过Optaplanner的Move Selection Filter将当前的move取消,从而避免产生程序溢出,令系统崩溃。下面会举实际的死循环例子说明这种情况。
   下面我们先明确多任务多机台生产计划的基础约束,再讨论死循环的具体产生经过。

计划约束

  1. 每个工序只能分配到指定的机台;
  2. 除产品的首个工序外,所有任务都有一个前置任务,它的开始条件是它的前置任务已结束,即同一产品的工序根据工序路线存在FS关系。
  3. 同一机台同一时间只能处理同一任务。即分配到机台上的工序生产任务,而生产时间不能重叠。

排程过程中产生的死循环

  例如下图:红框的任务Task1, Task2, Task3表示了一个产品的工序路线上的3个工序对应的任务,即表示这三个任务形成了工序路线任务链,它们分别分布于machine1, machine2, machine3三个机台。根据工序路线任务链的次序约束,其生产次序是Task1 -> Task2 -> Task3. 而蓝色背景的两个任务则是另外一个产品的工序路线任务链,根据该产品的工序路线,它的生产门外汉是TaskA -> TaskB, 可以看到这两个工序的次序跟红框工序中的Task2, Task3的次序是倒过来的。而从机台machine2的机台任务链上,我们可以看到,存在一个这样的生产次序关系:Task B -> Task 2。那么在Optaplanner通过一个Move来产生一个可能的方案,并对这个方案中各个任务的开始时间进行推导时,就有可能组合出如图中的状态,从而出现死循环,因为一个产品的工序需要按工序路线任务链的次序执行,而一个机台上生产机台任务链中的任务也是存在先后关系的,也即具有时序性的,一个机台在同一时间只能生产一个任务,也就有了一个机台自身的生产任务也是一个次序链的。从图中可以看出,存在了这么一个环状的生产任务次序: Task2 -> Task3 -> TaskA -> TaskB -> Task2,
  即当Task1, Task2, Task3, TaskA, TaskB中任意一个任务的开始时间被推导时,它都将成为上述死循环描述中的震动源,从而产生死循环。
  

实际多工序多机台生产计划中的约束

   在实际制造中,除了上述讨论的三个主要约束外,还会存在非常多企业自身业务场景相关的限制因素,会更大程度上限制生产活动的执行。而这此限制需要正确地反映到生产计划中,否则最终产生的计划就无法执行。本文只列出对生成计划的正确性有影响的、各计划均会存在的共性因素;而那些与各个行业、企业的业务相关的个性化因素,则不在本文考虑范围内,各位在自己设计系统时考虑即可。例如:印刷行业中的印刷后加工工序,做完洒金粉工序,是需要等待一定时间,令金粉固化后,才能进入下一工序的,那么也就是说这个工序与下一个工序之间存在一个最短时间间隔的限制,否则是会产生质量事故的,因此是一个硬约束。

任务死循环的检测经验

  因为生产计划的复杂性,造成工序任务链与机台任务链之间存在异常复杂的制约,需要对Optaplanner产生的可能方案进行合法性判断,识别任务的开始时间推导过程中,是否存在死循环的可能,则需要非常严谨的逻辑分析与正确的模型与算法设计。现分享一下本农在此类项目中,在这方面遇到的问题。
  当时我把机台任务链、工序路线任务链设计出来,并明确了模型中各实体的职责和关系后。发现了时间推导存在死循环的可能。因为我认为对Optaplanner将要规划出来的可能方案中的各种任务的关系已经有足够认识,就根据推导过程中可以出现的情况进行死循环检测,检测过程也相当简单。因为当一个可能方案中任务的时空关系一旦确定之后,所有的任务即构成了一个有向图(directed graph),那么我检查这个有向图是否存在环即可。我尝试过使用队列结构对这个图进行广度优先遍历,并识别环是否存在。也尝试过通过递归方式进行深度优先遍历(其实递归使用的数据结构就是栈,知晓VC++的同学应该从WinAPI32编程中学习过函数调用的机制,其实调用调用路径就是一个栈)。无论怎么尝试,检测结果就是无法完美、全面。因为我们项目中需要考虑的因素更多,出现意想不到的可能性更大。因此,有段时间我自己都觉得,不太可能解决这个问题,盟生了放弃的念头。幸好我遇到一个好领导,我的老板(我们这里都叫上级做老板)Jeffrey给了我非常多机会和支持,并不时跟我一起分析,他也了解到问题的复杂性,并给予理解与鼓励。最终我的解决办法是:对Optaplanner在规划过程中产生的每个可能方案,都进行模型上的抽象与简化,去除一些不影响死循环判断的因素,把它归约成一个正正式式的有向图,并通过一些成熟的有向图环检测的算法对其进行判断。其实思路主就是:把之前根据复杂的业务规则实现不同的逻辑进行分支检测的方法,倒过来,将含有一些业务因素的有向图,归约成数学算法可以处理的规范有向图,再对其进行检测。目前这个功能已经相当稳定,再她不会时不时出现意想不到的情况了。关于有向图的环检测算法,网上有很多,大家自己找或者自己研究都能弄出来,就不在本文深究了。

通过Selection Filter对不合法方案进行过滤

  其实若我们只研究本文中提出的多任务多机台生产任务的最基本三个约束的话,上文提到的不合法方案就只剩下任务死循环方案了。若在现实项目开发中,一个方案不合法的定义会更多,更丰富,且更复杂。一旦我们通过各种手段检测出一个方案是不合法的。我们就可以通过Selection Filter,在Optaplanner对的VariableListener对象的afterEntityChanged事件处理方法之前,把事个move放弃掉。关于Selection FIlter的用法,大家可以先从Optaplanner的开发手册中查看,我将会专门撰写Selection Filter相关的文章 对其进行说明。

小结

  自此,本文描述了基于Optaplanner设计APS排产引擎时,遇到比较棘手的问题。包括:计划类型的识别,由任务组成的工序链与机台链,任务与机台之间的匹配,工序链与机链之间的胶着可能性与循环识别与处理。希望能帮到大家。
  本人也是初初研究APS排程引擎,都还是在不断探索中,有不正确的地方,还请多多提点。为谢。

如需了解更多关于Optaplanner的应用,请发电邮致:kentbill@gmail.com

设计Optaplanner下实时规划服务的失败经历

  其实本文不知道算不算一个知识点分享,过程很美妙,但结果很失败。我们在利用Optaplanner的Real-Time planning(实时规则)功能,设计实时在线规划服务时,遇到一个属于Optaplanner7.8.0.Final版本的Bug。在实现实时在线规划服务的过程中,我做过很多尝试。因为需要实时在线的服务,因此,需要设计多线程并发为外界请求提供响应,需要实现消息队列来管理并发请求的时序等问题。这些Java方面的并发处理,我们暂时不详述,这方面的牛的人太多了,我只是新手,站在别人的肩膀上实现的代码而已。在本文我着重介绍一下,我在尝试使用Optaplanner的Real-Time Planning功能时遇到的问题,最终确认问题出自Optaplanner引擎自身, 并通过JIRA向Optaplanner 团队提交issue过程。

关于Optaplanner的Real-time planning

  先看看正常情况下,我们对Optaplanner的应用场景。平时我们使用Optaplanner时,不外乎以下几个, 构建Problem对象 + 构建Solver对象-> 启动引擎 -> 执行规划 -> 结束规划 -> 获得方案-> 获取结果方案,如下图。
  这种应用模式下,引擎处于一个非实时状态,只是一个调用 -> 获取规划结果的简单交互过程。
 

  但是有些对规划具的时间性要求较高,或在时间序列上,对规划的结果具有一定的延续性要求的情况下,这种规划方式是满足不了要求的。例如有些实时调度的场景;要求每个新的solution与上一个solution需要具有延续性,不可能每次给出的solution存在过大的差异,若产生过大的差异,这些规划出来的方案对于执行机构来说,是不可能按计划执行的。例如车辆调度系统(见下图),每隔一个时间段,就需要刷新一下车辆情况和环境情况,不可能每次刷新出来的调度方案跟前一次存在千差万别。每一次产生的方案,它必须尽最大程度上与上一次保持相近

  另外一个要求是实时性,如果按传的规划步骤,对于实时性有要求,或响应速度较高的场景,例如:车间作业的实时调度系统,可能每隔离10分钟就需要刷新一次计划,此时实时规则的作用就反映出来了。如下动图:
   Real-time planning, 顾名思义就是实时规划,它与传统的规划步骤区别在于,它并没有一个结束并退出规划的动作,面是一旦引擎启动,它将以守护进程的形式一直处于运行状态,而没有返回;当它满足规划结束条件时(例如找到符合条件的方案,或到达规划时限),会进入值守状态,不占用CPU资源。待激发事件对它发出重新启动的指令。因此,它的步骤是: [构建Problem对象] + [构建Solver对象] -> 启动引擎 -> 规划  -> 通过BestSolutionChange事件输出规则方案 -> 休眠 -> 接到重启指令 -> 规则(重重上述步骤),如下图:

  原来Optaplanner还有这种神操作,那么它的作用将进一步大增了,幻想一下大家看科幻或战争电影时,那里的指挥中心必然有一个大屏幕,上面显示了实时的战况或各方资源的部署情况,如果这些部署是需要通过规划来辅助实现的话,Optaplanner是不是可以作为后台超级计算机上不停运算规划的控制中枢系统呢?不过好像想多了。没那么神,做一下实时作业调度还是可以的。下面就看看我们的项目是如何考虑应用Real-time planning的。
  关于Real-Time Planning的具体开发步骤没办法在这里详述,在本系列的往后文章中,老农将会有一篇专门的文章介绍。它的基本步骤如下图。

  这里提供一下最重要的三个代码块,对应的场景是,当一个新的任务(Task)需要被添加进引擎的Problem中参与规则时,应该如何添加,添加完成之后,如何获得规划的结果。这三个代码块的功能分别是bestSolutionChanged事件处理程序,调用引擎Solver对象提交变更请求,和实现ProblemFactChange接口的实现,用于实现变更正在规划的Planning Entity.
 bestSolutionChanged事件处理程序
1 // solver是一个Solver对象,引擎入口
复制代码
2 solver.addEventListener(new SolverEventListener<TaskAssignmentSolution>() {
3     public void bestSolutionChanged(BestSolutionChangedEvent<TaskAssignmentSolution> event) {
4         if(solver.isEveryProblemFactChangeProcessed()) {
5             // TODO: 获取规划结果
6         }
7     }
8 });
复制代码

调用引擎Solver对象提交变更 
复制代码
1 DeleteTaskProblemFactChange taskProblemChange = new DeleteTaskProblemFactChange(task);
2 if (solver.isSolving()) {
3     solver.addProblemFactChange(taskProblemChange);
4 } else {
5     taskProblemChange.doChange(scoreDirector);
6     scoreDirector.calculateScore();
7 }
复制代码

ProblemFactChange接口的实现
复制代码
 1 /**
 2  * 添加任务到Workingsolution
 3  * @author ZhangKent
 4  *
 5  */
 6 public class AddTaskProblemChange extends AbstractPersistable implements ProblemFactChange<TaskAssignmentSolution>{
 7     private final Task task;
 8     
 9     public AddTaskProblemChange(Task task){
10         this.task = task;
11     }
12 
13     @Override
14     public void doChange(ScoreDirector<TaskAssignmentSolution> scoreDirector) {
15         
16         TaskAssignmentSolution taskAssignmentSolution = scoreDirector.getWorkingSolution();
17 
18         scoreDirector.beforeEntityAdded(this.task);
19         taskAssignmentSolution.getTaskList().add(this.task);
20         scoreDirector.afterEntityAdded(this.task);
21         scoreDirector.triggerVariableListeners();
22     }
23 }
复制代码

场景要求
   我们的项目其实挺符合实时作业的要求的,虽然我们也没有要求达到分钟级,或秒级的响应;但是如果能够每隔离10分钟,通过实时规划的模式刷新一次计划,还是更能帮助生产调度人员更准确掌握生产情况的。事实上,我们对新的计划刷新条件,并不是按固定的时间间隔来进行,而是以触发事件的方式对进行变更规划的。
  即当一个新任务产生了,或一个已计划好的任务被生产完成了,或一个已计划好的任务无法按时执行生产作业而产生计划与实际情况存在差异时,或一个机台出现计划以外的停机等诸如此类对计划足以产生影响的事件,都将会作为触发重新规则的条件。因此,我将引擎程序做成Springboot程序,部署到服务器端,并将程序设计成多线程并发的模式,主线程负责侦听Springboot接收到的WebAPI请求,当接收到请求后,就从线程池中启用一个线程对请求进行处理,这些处理是更新规划的请求,并把传送过来的Planning Enitty, Problem Fact等信息按要求进行处理,并放入队列中。所有请求产生的重新规划信息,通过队列依次被送入引擎处理。当有新的solution产生时,将它输出指定位置,并通知客户端前往获取。
系统的构件结构如下图

 遗憾

  古语有云,理想很丰满,现实很骨感。上述的设计对于Optaplanner的使用领域来说,是比较先进的(起码在国内还没听说过有人这样用法)。对业务而言也是非常符合要求的。但是我对上述所有美妙的构想完成了设计,并实现了代码,并通过Springboot运行起来之后。程序确实如我意图那样运行起来了!启动引擎 -> 开始规则 -> 找到更佳方案 -> 输出方案 -> 满足停止条件 -> 引擎进入守值状态. 好了,我就通过http发出一个删除Planning Entity的请求。Springboot的Contoller成功接收,启动子线程处理数据,向引擎对象发送doChange请求,引擎检测到请求,分出一个线程(这个线程是引擎分出来处理我那个线程请求的)处理成功,并更新Problem对象中的Planning Entity列表;引擎继续运行。Duang~~~~引擎主线程竟然抛出一个异常并停止了!提示那个被请求删除的Planning Entity未被加入Planning Entity的列表中!这下我蒙了。为什么还会报出这个Planning Entity未被加进列表的错误?回想起Optaplanner的开发说明书里,关于Planning过程中,每个新的solution都是一个clone的情况,我坚信我的程序是遇到Race condition了,一定是我的程序考虑不周导致资源竞争。Optaplanner号称经过大量单元测试,压力测试,有良好的稳定性,不可能就这样被我把错误试出来的。但切切实实地抛出了这个异常,而我却没有任何办法。错误信息如下图,下图是我截取给Optaplanner团队的:
  然后,我花了两天时间,对每一个步骤进行调试分析,对每一个solution的clone进行核对,我确实没办法从我的程序中找到任何头绪。于是我唯有求助于Geoffrey大神。通过邮件讨论组我给他留了个贴子。很快Geoffrey大神就回复了(这个得给个赞,比利时跟我们的时区相差不少吧?每次提的问题,他都能及时回复)。回复见下图,这个回复令了心被泼了一大桶冷水。它竟然确实可能是一个bug! 当然也有可能是程序产生了race condition. 可我都找了两天了,实在没办法,才想到找Optaplanner团队。然后我就把这个问题的重现步骤在Optaplanner项目的JIRA中提交了一个issue,不知道这算不算我给Optaplanner作出的一点点贡献呢,期待处理结果呀。
  其实在这两天时间时,我并不仅仅是检查我自己的代码是否出现资源竞争问题,我还Debug进了Optaplanner的源代码里(7.8.0.Final版),并找到了异常的具体来源。发现确确实实是在我提交了ProblemFactChanged请求后,引擎也进行了处理,但因为引擎在处理了请求后,在新的Solution的clone中,并没有被成功更新,也就是新的Planning Entity并没有进入新的solution clone中,而导致处理程序无法识别新的Planning Entity, 就出错了。





  现在办法有两个,一个是等Optaplanner团队在JIRA上对我提交的issue进行处理,看是不是真的在Optaplanner中存在这么一个Bug. 另一种办法是我打算将我的程序进一步简化,将它与Springboot分离,跟Optaplanner的事件程序一样,通过其它方法启动线程来尝试Real-Time Planning.
  Optaplanner引擎程序被包装成一个Springboot程序,并设置为daemon模式(守卫进程),Springboot Application启动后,引擎执行程序被一个线程启动。主线程向外提供Restful webservice,当有Web请求到达时,就启动一个线程用于执行Optaplanner的ProblemFactChange对象中的doChange方法,对现有solution中的Planning Entity列表中的对象进行增删改操作;并触发VariableListeners. 引擎在处理这些调用时,会产生新的bestSolution,并触发BestSolutionChangedEvent事件,在事件处理方法中,将最新的Solution中的Planning Entity列表输出即可获得增删改Planning Entity后的最新solution了。
这又是一篇花费不少精力的东西,尽管最终没实现实时规划服务。
创作不易,欢迎转载,请标明出处。


如需了解更多关于Optaplanner的应用,请发电邮致:kentbill@gmail.com

排产的两种方式(前推式与后拉式)在Optaplanner上的体现

生产计划的约束

  在制定生产计划过程中,必然是存在某些制约因素,满足某些需求才能进行的,或是交期保证、或是产能限制、或是关键工序制约。即TOC理论 - 任何系统至少存在着一个制约因素/瓶颈;否则它就可能有无限的产出。就是说,如果不存在这个(或这些)制约因素,生产计划就没必要“排”了,只需随意地,毫无约束地把任意一个或多个生产任务纳入生产日程,都能满足生产、营业等所有业务要求。那也不需要人的智慧参投入其中了。

两种计划模式

  而现实环境中,资源是有限的,且往往是在资源不足,并需要尽量满足制约因素情况下进行计划制定。在制定计划的时候,不同的公司,基于不同的经营策略,需要遵循不同的原则。即使是同一个公司,在不同的业务场景(例如淡/旺季),其需要遵循的原则也可能不同。例如旺季因为生产任务紧张,需要保证交期;而谈季相对来说可用产能会较充裕,保证交期就会不太困难,进而又需要遵循另外一些原则,譬如尽量降低生产成本等。而在这些原则之外,还有一种相对来说是比较固定,或者比较约定成俗的原则,就是尽早开始(As soon as possible),和即时生产(Just in time)。其中即时生产,是精益生产中的一个概念。本农上一家公司已推行了比较成熟的精益生产体系(精益绝对不是5S喔,更注重的是流程优化,识别并消除不增值活动,减省不增值但必须的活动)。所以当时设计APS系统时,很多时候就遵循即时生产的原则。此原则由整个供应链中最后一个环节驱动(例如出货环节),从而推动前工序的生产安排。而很多不太强调精益生产的制造企业,在老生产计划员来看,制定计划的时候,除了较低程度上实现批量生产,以便高资源利用率,而进行对小批量生产任务稍作停留等待外,通常是按尽早开始的原则进行的。因为通常人们的想法是,未来的生产任务和产能具有不可预见性,你不知道未来会不会突然因为客户加单,机器故障等客观且不可控因素导致产能吃紧,甚至令生产单位措手不及。如果这种意外情况真的出现,那么一开始使用尽早开始原则安排生产计划,令到后面的产能较充裕,应对起这些“意外”起来,就相对轻松多了,这类原则下的生产计划优势就体现出来了。而实时生产原则,则有可能因为预留在较后时间的资源(例如机台产能)是比较“准确”的,那就相对按尽早开始原则制定的计划来说,就更加被动了。但即时生产原则下的生产计划,应对这种“意外”,也是有很多相应措施的。例如使用适当的缓冲机制,和实时计划机制来应对。缓冲机制就是根据过往历史经验,在按即时生产原则制定生产计划时,预留一定程度的冗余资源作储备,当出现“意外”时,可以使用这些冗余的资源进行补救。而实时计划相对来说“先进”一点了(先进二字加个引号,是因为这只是我觉得这种方法先进一点)。这种所谓的先进,主要体现在通过自动化的排产引擎,将计划制定到足够细致且精确,对任务的生产情况(包括既有任务的执行情况,资源使用情况和新任务的增加量等)进行实时监控,使计划实时地对这些情况作出反映,并及时给出新的应对方案。例如:当有新任务出现时,即时更新新增的任务到计划中;有资源出现突发意外(例如机台突然故障)也可以反映到计划中,并即时作出反映,及时给出修正后的计划。但通过实时计划是相对比较复杂的的方案,在Optaplanner中也有real-time planning的功能,我将会在Optaplanner相关的系统列文章中,单独撰一篇来讲解实时计划。另外就是执行层面对实时计划的执行依从性问题了,如何制定的计划很精确,但执行过程相对来说是无法精确达到,比较粗糙的,例如:手工工序,人的执行能力相对机器来说,准时性会差很远的。

即时生产原则生产计划的价值

  既然即时生产如此繁琐,为何还要采用呢?为何不全部采用尽早生产的原则来制定计划呢?其实还真不是那么简单,相对生产环境的“繁琐”,对于老板来说商业上的利润更为重要。如果大家理解精益,就知道它很多情况下,要精简的活动就是 - “等待”,因为等待这个活动在整个价值链中,是不增值且不必要的,所以它是首个被除掉的活动。为何这样理解?因为如果对于一个并不非常紧急的产品,你一开始就完成了它的一大堆的半成品,或成品,占用了大量本来可以优先用于其它生产任务的的资源(库存、资金等资源),从而令到资源的利用率隆低了,对于老板来说,资源利用率高低可是实打实地影响到最终利润呀。本农曾参与过国内某一线生活用纸企业的产销协调平台的需求调研,记得讨论到关于目前的环境下,车间的批量生产是否能节省成本、是否仍有价值的问题时,当时的物流总监安奈不住情绪发飙了 - 你们到底会不会算帐? 少投几次料,少清几次机省出来的那点纸浆价值,大量生产出来的这些产品,放在北京一个物流仓里,一天的成本是多少?一个批次使用这种所谓的批量生产输出的成品,不到一个星期,库存成本就已经把所有生产环节省出来所有成本都吃掉了。所以,实时生产对于一些在制品成本高的企业,是能有效降低WIP,进而实打实地降整个供应链成本的。这也是即时生产的魅力所在。

尽早生产与实时生产的两处计划的具体制定方式

  上面讲解了尽早生产与实时生产两种原则的区别和各自的优劣,大家需要跟据自己的具体场景去采用,下面我们就针对这种原则的排产方式展开讨论。先不讲这两种制定计划的原则,在生成规划引擎Optaplanner上的实现方式的区别。假设我们是生产计划员,面对这两种原则,我们应该如何制定生产计划呢?
  先说尽早生产,其实说白了,就是有一个产品的一系列生产任务,一旦准备就绪了,就可以将它排入计划中,且排在时间轴上越靠前越好,不同工序对应的生产任务,在遵循固定的工序先后时间关系的基础上,越早开始越好,正常情况下上下任务之间是FS关系(即必须等上工序完成了,下工序才能开始),而在精益的优化流程中,特别是一些离散制造的场景,是可以实现SS的(即是上一工序一旦有工件完成,即可对这些工件开始下一工序的加工)。所以不同工序对应的任务是致密的,从而很好地实现了尽早生产。所以,我们可想而知,对于尽早生产原则下的生产计划,它是基于每个任务的就绪时间进行排产的,也就是说一个任务一旦就绪了,那么它在生产计划中的开始时间就是就绪时间的下一个时间单位了(这个时间单位可能是分钟或各车间自己制定的最小时间间隔)。当一个产品的首个工序时间在生产计划中确定了,按尽早生产的原则,可能推算出这个产品的后下所有生产工序对应的加工任务的最早开始时间,因为可能存在资源上的限制,并不一定能够在每个工序对应加工任务的最早开始时间开始加工,但还是遵循了尽早计划的原则,就是一旦上工序生产完了,当前这个工序的资源就位了,那就可以开始生产。如果按照上述的原则定制出来的生产计划,在甘特图上可以看到,所有生产任务都是尽可以靠前的且尽量致密的。
  再说说即时生产。上面已经说过,即时生产的原则是供应链最后一个环节来驱动的,同样地在供应链中的生产环节里,也是基于最后一个生产工序来驱动所有生产工序的加工任务的。也就是说,最后一个工序(例如包装)的生产任务要求什么时间要完成的,那就基于这个完成时刻 ,往前推算(例如,在要求完成时间,减去加工任务的时长,再减去一些准备时间等),就可以推算出前一个工序的生产任务的要求结束时间.....如此类推,就可以推算到整个产品的首个工序的生产任务的开始时间,从而得到所有生产任务的具体生产时间(包括开始时间与结束时间)。因为这种方式下制定生产计划是从后而往前推算的,所以从计划的甘特图上看,所有任务在时间思上是尽量往后靠且致密的。

Optaplanner对尽早开始与即时生产两种计划的实现方式

  上面我们已经知道,我们的生产计划人员,是如何排出尽早开始与实时生产两种计划的。如果我们使用规划引擎Optaplanner来辅助我们智能快速地制定这两种生产计划,应该如何设计呢?首先需要交待一下 Optaplanner在处理这些时间分配的要求时,它是如何实现的。通过前面Optaplanner系列文章中一些简单的示例我们知道,Optaplanner做规划的基本方法,就是对于被规划对象(例如生产任务),从可能的资源列表中,取出相应的资源对各个被规划对象进行尝试,通过分数的计算对比来确定资源应该如何分配才得到更好的方案。这里面的资源通常都是一些具体的物理物件,例如机台、工人等.没有提及时间这种资源是如何实现分配的呀。而我们所有的生产计划,事实上也就是在两个维度上的资源分配;分别是时间与空间上的分配,就是确定一个被规划对象的时空。例如确定一个任务应该分配在哪一个机台上(空间),需要在什么时候开始生产,需要在什么时间结束(时间)。事实上,Optaplanner的设计者早已考虑到这个问题,并提供了较完善的实现方案。针对时间维度的分配,Optaplanner提供了三种模式来实现(见图Assigning time to planning entitis),对于这三种模式,在Optaplanner系统列文章中,也将会有专门文章会讲解,在此不展开。在这三种模式中,其中一种叫做Chained Through Time pattern模式,我面对过一些复杂的排产场景,经过多翻尝试和掉过各种坑,还是觉得这种模式最为适合,它可以提供三种时间分配模式中最为丰富和灵活的接口,供我们实现一些特殊的需求,具体的应用再去参考相关文章,在此真的不够篇幅展开。这个模式的原理是,Optaplanner并不是分配哪个时间资源到哪个任务里去,而是对于所有的被规划对象,Optaplanner会把它们串成一个链(见图Chain principles),一个接着一个,Optaplanner要尝试规划的是这些被规划对象在链上的位置,它体现为当前的被规划对象,它的前一个对象是谁,每个对象有一个属性用于指向它在链中的前一个对象,而这个属性就是它的Planning Variable. 并且,Optaplanner提供了接口,当这个Planning Variable因当前对象在不同的链之间切换,或在同一个链中的不同位置切换的时候,这个接口可以让你告诉Optaplanner这个位置切换影响了被规划对象的另外的哪些属性(见图Planning Variable Listener),这些被Planning Variable的变化而被影响的属性就叫做Shadow Variable.这样的话,我们就可以应用这种机制,把Shadow Variable定为被规划对象(下面就以制定生产任务为案例,将被规划对象称作任务,这样更容易理解)的开始时间。那么我们就有:当一个任务处在不同链的不同位置时,它的开始时间就会受影响了。具体的实现方法是,当一个任务的位置变化前后(其实体现为它的前一个任务变化了),Optaplanner会触发关于这个前任务变的一系列事件。我们就在这些事件的处理方法中,去推算这个任务的开如时间,完成修改后,需要通知Optaplanner进程我们的修改,让它去计算分数来评价这个方案的优劣。从而实现了任务的位置变化,影响了开始时间,开始时间的变化,就可以推算出具体的结束时间。


  其实上面是我们在使用Chained Through Time pattern模式最常用的情景。如果实现了上述的方案,就已经排出了尽早生产的计划了。因为每个任务变化的时候,我们推算的都是它的开始时间。当然这个开始时间不仅仅是依据当前任务的前一个任务的结束时间推算出来的,还需要参照当前任务的就绪时间(若有的话),和当前任务的准备时间(若有的话)。但即使考虑了这些因素,它仍然是尽早开始的。那么如果我们而对的项目是需要实行精益生产的,需要实现即时生产的,应该如何做呢?其实大概的实现方式是一样的,只不过需要把生产任务形成的这条链的方向从时序上反转。在尽早生产的场景下,在链上的是以首个任务的开始时间作为基点,推算后面的其它任务的时间,进而推算其后方的其它任务的开始与结束时间。在即时生产的场景下,因为是由后工序驱动的,我们可以反过来,链的起头不再是首个任务的就绪时间了,而是最后一个任务的结束时间作为基点,往前推它的开始时间,而在链上的下一个下任务,而实在业务上对应的是它的上一个工序对应的任务,如此推算出来,就得到上一任务的结束时间,进而推算它的开始时间,如此类推,计算整条链的所有任务的结束时间与开始时间,在链尾就得到首个任务的开始时间了。把它反映在计划甘特图上,所有任务都是趋紧向后工序的,也就是实现了即时生产了。当然,上述提到的缓冲机制,大家应该很容易理解,也很容易在链中实现。

前推式计划 - 尽早生产,后拉式计划 - 即时生产

  通过上的两种计算的生成过程,大家应试注意到一个细节,就是尽早生产,它是基于第一个任务的就绪时间来向后推算后面任务的时间。形象点就是说,它一旦定好了开始时间,就按这个时间往后排计划了,就是告诉引擎,反正我这个时刻开始的,你就按这个时刻,根本必要的考虑因素和约束,从前往后推算出一个计划来吧。所以我们把它称为前推式生产计划。而另外一种即时生产原则下的生产计划,它是相反的,它确定了最后一个任务的开始时间,再往前推算前面各个任务的结束与开始时间,其实也是往前推算出来的时间。但因为它是基于供应链中的最后一个环节来驱动前面的生产活动的,所以我们形象地把它称为后拉式计划。也就是说,反正我定了哪个时刻需要完成的,你们前面的任务就贴着这个时间来安排结束时间和开始时间吧,就像从最后一点把前面的任务往后拉出一个生产序列来,因此我们把它称作后拉式生产计划
  至此,我们分别探究了尽早生产(前推式生产)和即时生产(后拉式生产)两种排产原则的考虑因素,计划方案和在规划引擎Optapalnner上的实现原理。具体的实现我将会通过两篇文章来描述,一篇用于描述Optaplanner对时间的分配模式;另一篇将会以Chained Through Time pattern模式为基础,以生产任务的制定过程,探究一下Optaplanner是如何实现复杂场景下的生产计划制定的。例如目前我负责的一个排产项目,及一些朋友的产品中,就涉及一些任务之间的先后次序制约,任务之间需要根据条件放置一些不属于常规生产任务的操作等。这些林林总总的奇怪而又现实的要求,如果仅仅使用Optaplanner最基本的Planning Entity + Problem Fact进行规划的模式,是无法实现的。需要通过Chained Through Time pattern模式提供的事件接口,来实现一些我们自己的业务逻辑,才有可能把这些现实的业务需求体现在生产计划中。


 如需了解更多关于Optaplanner的应用,请发电邮致:kentbill@gmail.com

Optaplanner规划引擎的工作原理及简单示例(2)

开篇

  在前面一篇关于规划引擎Optapalnner的文章里(Optaplanner规划引擎的工作原理及简单示例(1)),老农介绍了应用Optaplanner过程中需要掌握的一些基本概念,这些概念有且于后面的内容的理解,特别是关于将约束应用于业务规则上的理解。承上一文,在本篇中将会减一些理论,而是偏向于实践,但过程中,借助实际的场景对一些相关的理论作一些更细致的说明,也是必要的。本文将会假设我们需要对一个车间,需要制定生产计划.我们为生产计划员们设计一套智能的、自动的计划系统;并通过Optaplanner把这个自动计划系统开发出来。当然,里面的业务都是经过高度抽象形成的,去除了复杂的业务规则,仅保留可以体现规划引擎作用的一些业务需求。因此,这次我们只用一个简单的小程序即可以演绎一个自动计划系统,来呈现规划引擎Optaplanner在自动计划上的魅力。

“项目”背景与业务规则的分类

  假如我们接到一个项目,经过需求调研之后,发现其业务逻辑非常简单;但细想一下业务操作却又是异常复杂(先别砸砖,听老农缪缪道来)。它是一个生产计划系统(应该说是一个生产计划辅助系统,毕竟最终的计划,应该是人来决定,而非系统),在没有这个系统之前,计划人员(生产调试员)每天收到需要加工的生产任务之后,根据当时的机台产能情况,将这些待处理的任务合理地分配到适合的机台。对于前面这句对计划制定工作的描述,其实可以细作提练,其隐含了两个意义,分别是“合理地”和分配到“合适的”机台。对于这两个意义,我们可以把它区分为两种个方面的业务要求:
  1. “合适的机台” - 表示确定性的条件判断,是一个定性的断言,也就是非对即错。
  2. “合理地” - 表示非确定性的条件,也就是定量的,可以是非常合理,60%的合理,或完全合理,也就是说是否合理,还是有议论空间的,并没有一个完全固定的标准。
下面将对上述两项进行更深入的讨论。

确定性条件(定性)

  对于上述提到的这两个条件,其中“分配到合理机台”是相对确定的命题,只要向计划人员提供合理机台的条件指引,计划人员根据这些条件进行操作,总有一天能把所有的任务,匹配上所有条件的,只是时间问题。例如:A类任务只能放在可以处理A类任务的机台上加工;但也可能会更复杂,例如:来自某些客户的、且具有特定工一要求的、且生产量在指定范围内的, 且...,且.....,你可以一直"且"下去,令这些条件非常复杂。但无论怎么复杂,这些条件是具有确定性的判断标准,也就是说,不管有多复杂,只要能识别出来的条件,生产计划人员就可以根据这些条件进行分配;当然实际生产活动中,必然会遇到一些问题,当一些任务与机台的匹配条件非常复杂时:一来会令工作效率骤降;再就是人是有可能出错的,比较容易出问题的;甚至超出人的处理能力。
在本文,我们仅仅是为了让程序可以体现这种确定性条件的处理方法,我们把这类条件简化到最极端的情况:只有一个条件,只要机台可处理的任务类型,与任务自己的类型合适即表示机台与任务匹配。例如:有个机台M1可以做的T1, T2,这两种任务,机台2可以做T2,T3两种任务;那么,如果一个任务它是属于T1类型,则合适的机台只有M1, 如果这个任务是T3类型,则它的合适机台只有M2;如果这个任务是T2类型,则合适的机台有M1,M3两台。凡是把任务分配应类别的机台上去,都是合适的。

非确定性条件(定量)    

  非确定性条件,相对复杂一点,因为这类条件是没有绝对的对错,只有相对的优劣。例如本文中我们会使用成本这个条件因素,在确保上面的确定性因素(任务类型与机台匹配)前提下,成本越低越好。那么就存在多个可行方案的的可能,就会涉及到应该如何计算成本,用哪些方案的成本进行对比才是合理的问题。要理清这些问题,需要对业务模型有深入的理解,并能很准确地对这些因素进行归纳,把它们抽象成约束条件。为了简化问题,在本例中,成本反映在机台的启用成本上。也就是说,每个机台一旦启动它都会产生固定成本,而不会随着任务量增多而成本上升。所以作为计划定制人员,如果这是一个计划的重要指标的话,在制定计划时,就需要考虑应该如何统计一个机台的成本。本例中我们假定生个机台一旦启动,即产生固定的成本,所以我们的目标是:
  1. 用尽量小的机台来完成尽量多的任务.
  2. 这些被启用的机台,其成本尽可能低;即优先使用低成本的机台来处理任务。
当然,因应不同的场景,会有其它的要求,例如产能平衡:令尽可能多的机台被启用,以减少少空置率,搞提生产效率。本例中我们并没有使用此规则。

设计与测试数据

  为了满足上述条件,我们先建立业务模型。我们先识别出业务实体。可以识别出来的实体也只有两个,机台任务

机台

  我们假设有6个机台,分别是M1- M6, 它们分别有自己可处理的任务类型:Type_A,Type_B, Type_C 和 Type_D, 且分别有自己的产能成本。产能表示这个机台在固定时间段内,最多可以处理的任务量;成本表示如果这个机台一旦开启,即产生相应的货币成本。例如:机台M1, 
  1. 它可以处理类型为Type_A的任务(也就是说,它可以和产类型为Type_A的产品);
  2. 在固定时间段内(例如一个班次,或一天)可以处理300个任务,即产能为300。
  3. 它的成本为100, 即它一旦被启动,即产生100元的成本.
所有机台资料如下图,可以看到,有些机台它的可处理的任务类型是相同的,但两者的产能不同;有些可处理的任务类型相同,产能也相同,但成本不同;这样就进一步贴近实况。

机台列表

任务(产品)

  对于需要加工的产品(工称工件),我们把它抽象成任务,因为对于一个车间中的机台而言,以任务来识别它更贴切一些,在实际的业务建模中,一个产品不一定是一个任务,也有可能是一个产品的工序路线中的其中一个工序被定义为一个任务,即表示一个生产单位的一个生产指令, 例如:对机器外壳打孔。而在本例中,我们了为简化问题,我们假设一个任务就一个产品,每个产品只需一个任务即可。而关于一个产品存在一条完整且复杂的工序路线,从而产生多个生产任务的情况,我将在以后的文章中,关于Optaplanner的更高级的应用中,将会有相关的详细讲解。
对于任务(产品),我们的假设它具有类型和生产量两个属性。类型-表示它是属于哪一类的产品,用于识别它可以被分配到哪一个机台进行加工处理。生产量-表示这个产品需要生产多少个,当这个产品被分配到指定的机台上生产的时候,生产量这个属性将会与对应机台的产能作出对比与限制,即一个任务如果生产量超过了一个机台的产能,那么这个任务就无法放在这个机台上处理。所有任务(10个)的资料如下图:

任务列表

约束

  假如我们已经通过需求调研,确定了我们上述机台与任务两个业务实体,那么,下一步的调研目标,就是要识别出在这些任务分配到机台上的过程中,按照生产业务要求,我们需要遵循哪些规则了。本例我们假设有以下业务规则,以下称为约束,其中包括硬约束(不可违反),和软约束(尽量不要违反,但将不可避免;如果违反,尽可能令违反的程度减到最小)
硬约束:
  1. 任务只能被分配到可以处理它的机台上,以机台的“可处理任务类型”字段与任务的“类型”字段作识别,两者一致才符合条件;
  2. 一个机台处理的任务的生产量总和不能超过其产能。
软约束:
  1.  整个排产计划中,所有启用的机台成本之和尽量小。
通过上述约束的描述,可以得知,其中两个硬约束是可以避免的,但软约束是不可避免的,因为你处理任务必须启动机台,一旦启动任意机台,都会产生成本。因此,软约束的要求是尽量小,而不是不违反,不是0.

任务分本问题的解决方法(暴力穷举法与Optaplanner)

以下为理论部分,无兴趣探讨的同学可以跳过本小节。
  本“项目”的业务场景、业务实体和业务规则,我们都已经构建完成,接下来就是如何在上述给定条件的基础上,构建一个快速可用的解决方案,用于解决任务的分配问题了。至此,可能有些同学在想,其实这并不难呀,根据给定的两个硬约束和一个软件约束,以两个硬约束作为限制条件,通过暴力穷举的方法,找出一个无限趋近于符合软约束,也可以找出一个令成本最低的任务分配方案出来呀。这是对的,只要我们有明确的软硬约束要求,理论上是可以写出对应的程序,通过强大的CPU算法,甚至可以将程序写成并发运算,集成数量庞大的GPU算力,兴许能找最终方案的。但是,有这种想法,其实忽略了问题的规模与时间复杂度的关系。我们需要探讨,随着数据量(即问题规模)的增大,找到可用分配方案的耗时增长有多大,与问题规模的增长呈何种比例关系。通过上述的条件,及排列组合的知识得知,通常这类问题的时间复杂度是指数级复杂度,即O(a^n),甚至是阶乘级复杂度的,即O(n!)。当数据量有限增大之后,所需的运行时间增长,对目前技术上的计算机算力来讲,增长是指数级,甚至以今天的技术水平,是永远都无法找到最终方案的。这个在关于NPC或NP-Hard问题的文章中已有介绍,这里不再重复。
面对这类NP问题时,人类是如何解决的呢。其实人类目前也是无解的,如果哪位同学如果找到一个算法来解决这类问题,它的时间复杂度是常数级的,那么恭喜你,你已经为人类解决了不少难题了。而所谓的无解是指,无法在任何情况下找出一个绝对最优的解决方案(如果本例中的业务规则及数据量,用草稿纸都可以把所有情况列出来了,当然可以找出最优解,前提是你有足够耐性).所以,人们想到的还是通过穷举的方法,一个一个的组合方案去尝试,直找到最佳方案。但这种方法在数据量增大,或更多判断条件的时候是不可行的,而我们日常处理这类问题(例如排生产计划),当找到的排产方案只要满足了所有硬约束(其实光是满足硬约束的方案,如果不通过程序来实现,人类也很难很快找到);软约束方面只要找出一个差不多的,我们即可视作一个可用的方案并付诸执行了;因为我们不可能无限地找下去。而Optaplanner其实跟我们一样,问题规模足够大的情况下,它也是不可能找出绝对最优方案的。但是它相对人类聪明之处在于,它集成了寻找最优方案的过程诸多专门的算法。过程中使用了分阶段,分步骤的方法将问题归约成一些数学模型可处理的形式。且在寻找最佳方案(应该是寻找更佳方案)的过程中,它集成了一堆已被证明卓有成效的数学寻优算法,例如在问题初始化阶段可以使用First Fit, First Fit Decreasing等算法,在寻优阶段使用禁忌搜索法、模拟退火法等算法。从而极大地提高寻找更优方案的效率。令其在相同的时间内,找到的方案相对人类,或者相对不使用任何算法的暴力穷举法而言,质量高得多,更趋近于最优方案。

用Optaplanner解决任务分配问题

  通过Optaplanner寻找更佳分配方案,需要建立相关的类和模型,英语还可以的同学,可以直接上去它的使用说明中查看Cloud Balance示例,是一个非常好的示例,从最简单的Hellow world, 到使用了Real-time planning等近几个版本新功能,都有详细的说明与教程。我们现在这个示例也是参它来设计的。
在开始设计之前,我们需要构思一下,我们的任务分配是如何实现的。在我们的实际计划制定的业务操作中,也就是工厂的车间里,计划员是把一个产品的实物,喂进一个机台,让机台对它进行处理。所以我们会理解为:分配就是把上面10个任务分配到6个机台中。其实这样做是可行的,但我们更深入地思考一下,其实我们需要处理的是任务,而不是机台,也就是说,每个任务必须都被分配到一个机台中处理,而机台不一定。在最小化成本的原则底下,好的方案有可能出现有部分机台并没有分得任务的情况。所以,我们需要把任务与机台的关系倒过来,把任务作为我们的研究目标,理解为把一个机台分给一个任务。做过生产计划或生产管理的同学就很清楚知道,机台也是一种生产资源,针对不同的生产任务,将资源应用到这些任务上去,其中机台(或产线)是一个很常见的资源类型。
  所以,我们的设计思路是:针对一个任务,把一个适合的机台分配给它,令它满足两个条件:1. 满足所有硬约束; 2.分配好所有任务的机台之后,这些机台的成本加总尽量低。好了,理清了思路,下面我们就可以开始设计了。

按Optaplanner规范建模

  要使用Optaplanner规划引擎,就需要按它的要求建立对应的模型,包括各种类及其关系。我们这个示例跟官网上的Cloud Balance几乎一致,在它的类图基础上修改就可以了。我们先看看建立好的class diagrame如下图:


 要建立的类分别是:
  1. Task,表示任务的实体类,它被注解为@PlanningEntity, 它有三个属性:taskType - 当前任务的类型; quantity - 生产量;machine - 任务将要被分配到的机台。其中machine属性被注解为@PlanningVariable, 表示规划过程中,这个属性的值将被plan的,即通过调整这个属性来得到不同的方案。另外,作为一个Planning Entity, 它必须有一个ID属性,用于在规划运行过程中识别不同的对象,这个ID属性被注解为@PlanningId。 本例中所有实体类都继承了一个通用的类 - AbstractPersistable, 该父类负责维护此所有对象的ID。Task类也继承于它,因此,将该类的ID属性注解为@PlanningId即可。另外,作为Planning Entity, 它必须有一无参构造函数,若你在此类实现了有参构造的话,需要显式地实现一个无参构造函数。
  2. Machine, 表示机台的实体类,它属于ProblemFact,在其中保存了在规划过程中会用到的属性,此类反映一个机台相关信息的属性: taskType - 可处理的任务类型; capacity - 当前机台的产能; cost -当前机台的成本。
  3. TaskAssignment, 此类用来描述整个解决方案的固定类,它的结构描述了问题的各种信息,在Optaplanner术语中,在执行规划前,它的对象被称作一个Problem, 完成规划并获得输出之后,输出的TaskAssignment对象被称作一个Solution。它具有固定的特性要求: 必须被注解为@PlanningSolution;本例中,它至少有三个属性: machineList - 机台列表,就是可以用于分配任务的机台,本例中指的就是上述那6个机台;taskList - 就是需要被规划(或称分配机台)的10个任务,这个属性需要被注解为@PlanningEntityCollectionPropery. 还有一个是score属性,它用于在规划过程中对各种约束的违反情况进行打分,因为本例中存在了硬约束与软约束。因此我们使用的Score为 HardSoftScore.
另外,上述提到了一个的有实体类(本例只有Task与Machine为实体类)的父类AbstractPersistable, 它负责维护ID属性,对实体类的compareTo方法,toString方法进行重载。
具体的代码如下,没有Maven基础的同学,请先自补一下Maven的知识,以下内容都是基于Maven的。
 Task类:

复制代码
 1 package com.apsbyoptaplanner.domain;
 2 
 3 import org.optaplanner.core.api.domain.entity.PlanningEntity;
 4 import org.optaplanner.core.api.domain.variable.PlanningVariable;
 5 
 6 @PlanningEntity
 7 public class Task  extends AbstractPersistable{
 8 
 9     private String requiredYarnType;
10     private int amount;
11     
12     private Machine machine;
13     
14     public String getRequiredYarnType() {
15         return requiredYarnType;
16     }
17 
18     public void setRequiredYarnType(String requiredYarnType) {
19         this.requiredYarnType = requiredYarnType;
20     }
21 
22     public int getAmount() {
23         return amount;
24     }
25 
26     public void setAmount(int amount) {
27         this.amount = amount;
28     }
29 
30     @PlanningVariable(valueRangeProviderRefs={"machineRange"})
31     public Machine getMachine() {
32         return machine;
33     }
34 
35     public void setMachine(Machine machine) {
36         this.machine = machine;
37     }
38 
39     public Task(){}
40 
41     public Task(int id, String requiredYarnType, int amount) {
42         super(id);
43         this.requiredYarnType = requiredYarnType;
44         this.amount = amount;
45     }
46 }
复制代码
 Machine类:

复制代码
 1 package com.apsbyoptaplanner.domain;
 2 
 3 public class Machine extends AbstractPersistable{
 4     private String yarnType;
 5     private int capacity;
 6     private int cost;
 7     
 8     public String getYarnType() {
 9         return yarnType;
10     }
11     public void setYarnType(String yarnType) {
12         this.yarnType = yarnType;
13     }
14 
15     public int getCapacity() {
16         return capacity;
17     }
18     public void setCapacity(int capacity) {
19         this.capacity = capacity;
20     }
21     public int getCost() {
22         return cost;
23     }
24     public void setCost(int cost) {
25         this.cost = cost;
26     }
27     public Machine(int id, String yarnType, int capacity, int cost) {
28         super(id);
29         this.yarnType = yarnType;
30         this.capacity = capacity;
31         this.cost = cost;
32     }
33 }
复制代码
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(){}
}
复制代码
AbstractPersistable类

复制代码
 1 package com.apsbyoptaplanner.domain;
 2 
 3 import java.io.Serializable;
 4 
 5 import org.apache.commons.lang3.builder.CompareToBuilder;
 6 import org.optaplanner.core.api.domain.lookup.PlanningId;
 7 
 8 public class AbstractPersistable implements Serializable, Comparable<AbstractPersistable> {
 9 
10     protected Long id;
11 
12     protected AbstractPersistable() {
13     }
14 
15     protected AbstractPersistable(long id) {
16         this.id = id;
17     }
18 
19     @PlanningId
20     public Long getId() {
21         return id;
22     }
23 
24     public void setId(Long id) {
25         this.id = id;
26     }
27 
28     @Override
29     public int compareTo(AbstractPersistable other) {
30         return new CompareToBuilder().append(getClass().getName(), other.getClass().getName()).append(id, other.id)
31                 .toComparison();
32     }
33 
34     @Override
35     public String toString() {
36         return getClass().getName().replaceAll(".*\\.", "") + "-" + id;
37     }
38 }
复制代码
  到目前为止,我们已完成了所有的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(一个开源规则引擎)结合之后,就不再需要自己通过Java代码编写算分逻辑了(当然你也可以不用Drools,自行编写算分逻辑),只需要通过Drools表达业务约束,Optaplanner在规划过程中,会启自行启动Drools规划引擎对这些约束进行判断,从而进行计分。
  那么我们只需要在resource里添加一个Drools脚本文件,用于描述这些约束即可。至于Drools的应用,不在本文范围,同学们可以自行学习Drools,如有需要,我将会撰写另外一个Drools应用相关的系列文章 .
rules.drl文件
复制代码
 1 package com.apsbyoptaplanner.solver;
 2 
 3 import org.optaplanner.core.api.score.buildin.hardsoft.HardSoftScoreHolder;
 4 import com.apsbyoptaplanner.domain.Task;
 5 import com.apsbyoptaplanner.domain.Machine;
 6 import com.apsbyoptaplanner.domain.TaskAssignment;
 7 
 8 global HardSoftScoreHolder scoreHolder;
 9 
10 rule "yarnTypeMatch"
11 when
12     Task(machine != null, machine.yarnType != requiredYarnType)
13 then
14     scoreHolder.addHardConstraintMatch(kcontext, -10000);
15 end
16 
17 rule "machineCapacity"
18 when
19     $machine : Machine($capacity : capacity)
20     accumulate(
21         Task(
22             machine == $machine,
23             $amount : amount);
24         $amountTotal : sum($amount);
25         $amountTotal > $capacity
26         )
27 then
28     scoreHolder.addHardConstraintMatch(kcontext, $capacity - $amountTotal);
29 end
30 
31 rule "machineCost_used"
32 when
33     $machine : Machine($cost : cost)
34     exists Task(machine == $machine)
35 then
36     scoreHolder.addSoftConstraintMatch(kcontext, -$cost);            
37 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代码
复制代码
 1 import java.io.InputStream;
 2 import java.util.ArrayList;
 3 import java.util.List;
 4 import java.util.stream.Collectors;
 5 import org.optaplanner.core.api.solver.Solver;
 6 import org.optaplanner.core.api.solver.SolverFactory;
 7 import com.apsbyoptaplanner.domain.Machine;
 8 import com.apsbyoptaplanner.domain.Task;
 9 import com.apsbyoptaplanner.domain.TaskAssignment;
10 
11 public class App {  
12 
13     public static void main(String[] args) {
14         startPlan();
15     }
16 
17     private static void startPlan(){
18         List<Machine> machines = getMachines();
19         List<Task> tasks = getTasks();
20         
21         InputStream ins = App.class.getResourceAsStream("/taskassignmentConfiguration.xml");
22 
23         SolverFactory<TaskAssignment> solverFactory = SolverFactory.createFromXmlInputStream(ins);
24         Solver<TaskAssignment> solver = solverFactory.buildSolver();
25         TaskAssignment unassignment = new TaskAssignment(machines, tasks);
26         
27         TaskAssignment assigned = solver.solve(unassignment);//启动引擎
28         
29         List<Machine> machinesAssigned = assigned.getTaskList().stream().map(Task::getMachine).distinct().collect(Collectors.toList());
30         for(Machine machine : machinesAssigned) {
31             System.out.print("\n" + machine + ":");
32             List<Task> tasksInMachine = assigned.getTaskList().stream().filter(x -> x.getMachine().equals(machine)).collect(Collectors.toList());
33             for(Task task : tasksInMachine) {
34                 System.out.print("->" + task);
35             }
36         }
37     }
38     
39     
40     private static List<Machine> getMachines() {
41         // 六个机台
42         Machine m1 = new Machine(1, "Type_A", 300, 100);
43         Machine m2 = new Machine(2, "Type_A", 1000, 100);
44         Machine m3 = new Machine(3, "TYPE_B", 1000, 300);
45         Machine m4 = new Machine(4, "TYPE_B", 1000, 100);
46         Machine m5 = new Machine(5, "Type_C", 1100, 100);
47         Machine m6 = new Machine(6, "Type_D", 900, 100);
48 
49         List<Machine> machines = new ArrayList<Machine>();
50         machines.add(m1);
51         machines.add(m2);
52         machines.add(m3);
53         machines.add(m4);
54         machines.add(m5);
55         machines.add(m6);
56         
57         return machines;
58     }
59 
60     private static List<Task> getTasks(){
61         // 10个任务
62         Task t1 = new Task(1, "Type_A", 100);
63         Task t2 = new Task(2, "Type_A", 100);
64         Task t3 = new Task(3, "Type_A", 100);
65         Task t4 = new Task(4, "Type_A", 100);
66         Task t5 = new Task(5, "TYPE_B", 800);
67         Task t6 = new Task(6, "TYPE_B", 500);
68         Task t7 = new Task(7, "Type_C", 800);
69         Task t8 = new Task(8, "Type_C", 300);
70         Task t9 = new Task(9, "Type_D", 400);
71         Task t10 = new Task(10, "Type_D", 500);
72 
73         List<Task> tasks = new ArrayList<Task>();
74         tasks.add(t1);
75         tasks.add(t2);
76         tasks.add(t3);
77         tasks.add(t4);
78         tasks.add(t5);
79         tasks.add(t6);
80         tasks.add(t7);
81         tasks.add(t8);
82         tasks.add(t9);
83         tasks.add(t10);
84 
85         return tasks;
86     }
87 }
复制代码
  好了,上述代码懂的同学应该不难理解,就是先构建一个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的应用,请发电邮致:kentbill@gmail.com

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

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