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

释义：文中提到的资源，是指需要完成一个生产作业（或称任务，生产任务）所需的生产条件，例如机台、原料等，称为广义资源。 

对于生产计划，常见有以下四种类型：

• 单一工序，单一资源种类.
• 单一工序，多资源种类.
• 多工序，单一资源种类(较少见).
• 多工序，多资源种类.

　　下面对上述四种生产计划进行逐一分析，本文的分析，着重于计划的优化实现，而不是硬性规则的确保。例如通过工序的就绪情况来确定资源的就绪要求，例如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排程引擎，都还是在不断探索中，有不正确的地方，还请多多提点。为谢。

本系列文章在公众号不定时连载，请关注公众号（让APS成为可能）及时接收,二维码：

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