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

编者按

本文对于单一工序、单一资源，单一工序、多资源，多工序、单一资源(较少)，多工序、多资源这四种常见的生产计划类型进行逐一分析，着重于计划的优化，而非硬性规则的确保。其中，针对多工序、多资源生产计划类型具体描述了基于Optaplanner设计APS（进阶生产规划及排程系统）排产引擎时遇到的棘手问题，包括：计划类型的识别，由任务组成的工序链与机台链，任务与机台之间的匹配，工序链与机链之间的存在胶着可能性，以及循环识别与处理的问题。

一  单一工序，单一资源种类

对单一工序、单一资源种类的情况，是最简单的一种排产场景。即一个产品的生产过程只需使用同一种资源，进行一次加工即完成了产品的整个生产过程。这种情况下，既然是单一工序，那也就没有了工序的先后资源的限制；单一种类资源，即没有了资源的选择优化。

这里提到的资源，是指需要完成一个生产作业（或称任务，生产任务）所需的生产条件，例如机台、原料等，即广义资源。生产实践中，这类计划通常是对产品众多工序路线中的一个较重要的工序进行制定计划时使用。需进行优化的主要目的是对资源的使用分配，比如各机之间实现负荷平衡等需求。

实现这类计划时，需要通过设定机台平衡的约束，让引擎在为工序分配任务时，尽可能实现同一类机的负荷平衡。比如印刷生产中对排在最后的手工工序制定生产计划时，需要根据各个产线的人力安排情况，按比例安排定额任务。

二  单一工序，多资源种类

对单一工序、多资源种类的情况，仅对产品一个工序进行排产，仅可用于这个工序的资源是多种多样的，并且各种资源之间可以互换。此类计划主要为了实现资源的优化分配，即按照一定原则对各个工序进行资源安排。各种资源使用成本各不相同，在制定计划时，为了降低生产成本，应在确保其它更高优先级的约束或硬性约束的前提下，尽量使用低成本的资源进行生产。

例如，在印刷行业印刷印张的工序中，有些印张可以通过CMYK四色印制，也可通过调配特殊色通过专色印制，但前者成本相比后者更低，前后两种印刷方式就表示两种资源。在对印刷工序定制生产计划时，就会优先使用CMYK印刷，但并非绝对，如果CMYK资源已经超出负荷，不动用专色印刷就无法实现按时交货时，还是会放弃成本这个约束，来迁就交期这个更高优先级的约束。

三  多工序，单一资源种类

多个工序，单一种类资源的情况，则相对较少见。即计划中需要制定整个产品工序路线中的所有工序资源和时间，其中资源要求只有一种可选。可以理解，这种情况对资源分配的要求较低，计划着重于对工序的前后关系制约或工序自身其它因素的优化。即在资源分配上，如第一种情况“单一资源、单一任务”一致，基于资源利用的一些原则进行资源分配。而在安排工序的加工时间问题上，则需要根据产品的工序路线，实现对前后工序在时间上的次序关系，而这种次序又受到资源分配的限制。

例如：如果印刷的第二工序中（有些企业称为印后加工），有过油、过胶、过UV三个工序，如果有一种机台同时可以实现这三种工序，那就满足“多个工序、单一资源种类”的场景。这时关于工序的资源分配，会有相应的资源使用约束。但更重要的约束是：一个产品多个工序的处理次序上，这个次序必然是根据产品的工序路线设定的资源来执行的，否则就违反了硬性约束。

所以，综合上述的资源分配和工序资源两种要求，我们需要面对的是互相矛盾的问题：其一，对于同一个产品需要确保其执行的工序与工序路线上设定的一致；其二，对于一个资源（例如机台）上的生产效率而言，如何实现更多的同工序连接生产。

即使使用同一资源，通常在该资源上，不同工序的生产任务之间的切换会产生成本，可能是时间成本，也可能是具体的货币成本。所以，难点就在于如何平衡上述两个问题，从而实现资源利用率最大化和工序资源不被违反。

四  多工序，多资源种类

多个工序，多资源种类的和产计划，是目前最为常见，也最为复杂的生产计划，是本文讨论的重点。多工序与前一个问题一样，是针对整个产品的工序路线进行排产，而且生产各个工序所用的资源属于不同种类。

这种情况面对两个相对零散也有交互的矛盾：其一，对于一个产品而言，其多个工序是依据工序路线形成生产资源的；其二，多种资源表示各个生产工序所使用的资源有可能不一样，也有可能不同。

因工序前后次序的限制原因，当引擎对一个工序完成资源分配后，进一步进行生产时间的分配。但因为同一产品的工序执行次序，需要按照工序路线的先后次序来执行，也就是计划中除了需要分配好的资源外，还要确保这个资源在指定的时间段内，没有被其它产品的生产任务占用。那么当同时对多个产品进行排产时，各个产品的工序路线形成的工序生产序列和资源分配方案，很容易就形成胶着状态，甚至在多个资源之间出现死锁状态。

下面，我们以多个不同种类的机台，处理工序路线上多个工序的案例，来计划“多工序、多资源种类”的情况，并分析需要实现这种计划，所需的技巧、技术难点和可能出现的情况，及其应对方法。

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

规划过程中用到的概念。为了便于描述规划过程中的各种情况，现先定义以下概念：

(1) 任务或生产任务：一个产品的一个工序的生产作业称作一个任务，例如印刷后加工有：过胶 -> 烫金 -> 丝印，则表示这个产品的后加工中有三个任务，分别是过胶任务， 烫金任务和丝印任务。

(2) 工序路线任务链：一个产品中的不同工序对应的生产作业，其次序是由其工序路线确定的，一个产品的所有生产作业序列，即任务序列，称为工序路线任务链。

(3) 机台任务链：多个任务被分配在一个机台上时，同一时间只能处理一个产品，即同一时间只能进行一个任务，这些同在一机台上形成的任务序列，称为机台任务链接。

(4) 前置任务，后置任务：同一产品上多个任务，根据工序路线的规定形成与工序次序一次的生产任务次序（即工序路线任务链）。在链中两个相邻的任务，前者称作后者的前置任务；后者称作前者的后置任务。

(5) 前一任务，后一任务：分布于同一机台上的多个工序任务（即机台任务链），在机台任务链中相个相邻的任务；前者称为后者的前一任务，后者称作前者的前一任务。

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

下面我们来针对实用性最强，制造业面对最多的场景 ：多工序、多台机台场景展开讨论。处理这类生产计划，以下两个因素最为麻烦。

(1) 多任务与多机台的匹配

在待排的计划要素中，任务与机台的种类都存在多样性，且可能存一种任务可分配到多种机台，一种机台可以做多种任务的情况，因此，任务与机台的匹配问题会相对其它三种生产计划复杂一些，但往往这也是体现出Optaplanner价值的一个要点。

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

 一个产品的工序中先确定的任务序列，与分配于同一机台上的任务序列，在加工次序上互相制约。加工次序体现在加工的时间先后，即一个产品的任务序列，必然按其工序路线，存在一定的先后次序。而单个产品被分配到各个机台上进行生产作业时，因生产路线上存在时间先后次序，会令到一个机台上多个任务需要按次序生产的时候，每个任务的作业时间段可能并不紧密连接。

当准备在机台上启动一个任务时，这个任务的前置工序可能尚未完成，从而令到该任务所在的机台已就绪（其前一任务已完成，机台已为该任务准备就绪），但因为它的前置工序还没完成，导致它无法开始，一旦开始就违反了工序路线约束，令该机台上排在后面的其它后任务都要推迟，而这些任务被推迟，又可能导致它们自身的后置任务需要推迟，从而会出现机台任务链和工序路线任务链互相影响。这种情况称为“连锁反应”，解决好这种连锁反应是解决排程的关键。

上述描述的连锁反应的情况出现，有可能出现环状影响的情况。因为一个正常的生产计划存在时间与空间两个主要维度，其中空间维度本文的场景就是机台，表示一个任务被分配到了指定机台。时间维度则体现为任务的开始和结束时间（事实上结束时间可以通过开始时间推导出来），即确定一个任务的计划开始时刻。那么就需要有一个逻辑，对各个已分配空间（即机台）的任务进行时间推导。

任务的时间推导我们需要通过Optaplanner的afterEntityChanged事件来进行（这个事件仅出现于Chained Through Time模式，以后将会有专门的文章讲述Optaplanner的时间分配模式，其中Chained Through Time模式是重点），而推导的起源（就是从哪个任务开始推）通常以当前Move（Optaplanner的最小作业单位）所处理的任务开始，这个任务称为震动源。

经过它的工序路线任务链传递到机台任务链，再由机台任务链的影响回工序路线任务链，当这种环状的影响线路，经过一系列连锁反应，正好返回来对震动源进行推导时候，就相当于又开始了与上一轮一样的推导路线，便会无限推导下去，死循环就产生了。

我们需要准确识别这种连锁反应会否产生死循环，并当确实产生死循环时，就要将当前的move标识的不合法，在开启时间推导之前，通过Optaplanner的Move Selection Filter将当前的move取消，从而避免产生程序溢出，令系统崩溃。下面会举实际的死循环例子说明这种情况。

下面我们先明确多任务多机台生产计划的基础约束，再讨论死循环的具体产生经过。

3、计划约束

每个工序只能分配到指定的机台。

(1) 除产品的首个工序外，所有任务都有一个前置任务，它的开始条件是前置任务已结束，即同一产品的工序根据工序路线存在FS关系。

(2) 同一机台同一时间只能处理同一任务。即分配到机台上的工序生产任务，而生产时间不能重叠。

4、排程过程中产生的死循环

例如下图：红框的任务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中任意一个任务的开始时间被推导时，它都将成为上述死循环描述中的震动源，从而产生死循环。

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

在实际生产制造场景中，除了上述讨论的三个主要约束外，还会存在很多企业自身业务场景相关的限制因素，会更大程度上限制生产活动的执行。而此限制需要正确反映到生产计划中，否则最终产生的计划就无法执行。本文只列出对生成计划的正确性有影响、各计划均会存在的共性因素，那些与各个行业、企业的业务相关的个性化因素，则不在本文考虑范围内。

例如：印刷行业中的印刷后加工工序，做完洒金粉工序，是需要等待一定时间，令金粉固化后，才能进入下一工序的，那么也就是说这个工序与下一个工序之间存在一个最短时间间隔的限制，否则是会产生质量事故的，因此是一个硬约束。

6、任务死循环的检测

因为生产计划的复杂性，造成工序任务链与机台任务链之间存在异常复杂的制约，需要对Optaplanner产生的可能方案进行合法性判断，识别任务的开始时间推导过程中，是否存在死循环的可能，则需要非常严谨的逻辑分析与正确的模型与算法设计。现举例说明此类项目中在这方面遇到的问题。

当机台任务链、工序路线任务链设计出来，并明确了模型中各实体的职责和关系后，如果发现了时间推导存在死循环的可能，就根据推导过程中可以出现的情况进行死循环检测，检测过程相当简单。

当一个可能方案中任务的时空关系确定之后，所有任务便构成了一个有向图（directed graph），那么我们检查这个有向图是否存在环即可。可以尝试使用队列结构对这个图进行广度优先遍历，并识别环是否存在；也可以尝试通过递归方式进行深度优先遍历（递归使用的数据结构就是栈，即从WinAPI32编程中学过的函数调用机制，调用路径实质就是一个栈)。

如果无论怎么尝试，检测结果就是无法完美、全面，可能原因是项目中需要考虑的因素更多，出现意想不到的可能性更大。此时解决办法是：对Optaplanner在规划过程中产生的每个可能方案，都进行模型上的抽象与简化，去除一些不影响死循环判断的因素，把它归约成一个有向图，并通过一些成熟的有向图环检测的算法对其进行判断。

有向图的思路是：把之前根据复杂的业务规则，实现不同的逻辑进行分支检测的方法倒过来，将含有一些业务因素的有向图归约成数学算法能够处理的规范的有向图，再对其进行检测。目前这个功能已经相当稳定，一般不会出现意想不到的意外情况。关于有向图的环检测算法，网上有很多，这里不在本文深究。

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

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

本文描述了基于Optaplanner设计APS排产引擎时，遇到比较棘手的问题，包括：计划类型的识别，由任务组成的工序链与机台链，任务与机台之间的匹配，工序链与机链之间的存在胶着可能性，及循环识别与处理。

本人也是初始研究APS排程引擎，还在不断探索中，有不正确的地方，还请多多指正。