使用OptaPlanner解决多工序、多机台(资源)排程的新思路

在解决多工序联动、多机台共享的场景下排程过程中，常用同时把所有存在前后接续关系的任务，和存在共用特性的机台，一起建模成为规划变量(Planning Entity)与问题事实(Problem Fact)，并一次性提供给引擎进行求解运算。但这种方法，因为双链（下文详述）特性的存在，规划问题过于复杂，导致问题规模过大，从而令引擎的搜索究竟指数级增大，进行各种性能改善后，仍难以获得满意解；甚至部分情况下规划运算所得结果还不如人工排程方案。

双链模型可简述如下：将工序路线上前后工序形成的任务链（下称工序任务链），与机台上的接续的任务形成的机台任务链（下称机台任务链）综合在一起。对每个任务的开始时间（前推式计划）或结束时间（后拉式计划）进行优化，以缩短整体时间（以提升效率作为优化目标）。下图是本人在一开始的排程项目中对双链规划问题的描述，在以往的文章，及向Geoffrey的求教过程中均以该图说明双链模型及其可能遇到的问题；有兴趣者可查看更早前的文章 。

机台链与工序链互相发生连锁反应

在使用OptaPlanner的时间链模式对多工序、多机台任务进行排程时，对问题规划造困扰的难题有:

1. 进行各个Move运算过程中进行时间推导时，当任务的机台任务链与工序任务链之间形成死循环时，会导致时间推导程序无法跳出，从而卡死该Move中。需要通过有向图的查环方法解决，并且这些Move置为undoable，会造成一定机率的运算性能损失和寻优机率损失。
2. 每个任务的相对位移都需要大量的双链推导计算（最晚开始时间或最晚结束时间计算），且推导结果分布差异性极大，从而造成每个可能方案的计算量徒增；导致同等时间内，遍历的可能方案数量减少，从而优化效率低下。
3. 由于双链的存在，在进行时间推算时，机台任务链与工序任务链会造成互相影响，极容易出现Score Corruption，Listener Corruption或Undo Corruption等异常，需细致处理各链及其节点之间的制约关系。

在经过多轮项目试验后发现上述使用双链的办法，虽然建模上能较完整地反映排程结构，并可贴切以仿真排程过程；但上述几个难题目前仍未有好的解决办法，特别是第3个问题，几乎稍复杂的工序路线或机台共用情况，很难避免出现各种Corruption异常。

经过分析后，本人对这种多工序、多机台场景下的排程，构思了一个新的设想。其思路并不复杂，就是设法把上述模型中的双链化简成单链，从而实现只对单一的时间链进行优化，再把各个时间链的优化结果综合起来形成一个同时满足工序制约与机台共用的生产计划。但该想法目前还在构思、设计阶段，正在抽时间进行验证。但因近半年项目工作特别紧张，目前仍未完成实际编码。本文先简述一下该思路，待完成设计和编码后，再给大家分享结果。

工序路线上多个工序形成前后制约，多个机台存在共用，即同一机台上可能存在多种工序的任务共存，从而形成双链胶着结构，该结构可视作一个有向图(Directed Graph)，它的每个节点有0个或两个入度，并有0个或2个出度，在生产计划排程中是极为常见的现象。那么如何把这个有向图拆分成一个一个链呢？在对这个有向图的每个节点（即任务）进行时间推算（前推式）时我们知道，推导是以每个任务所在的工单的最早可开始时间作为起点推算的，那么也就是工序任务链中必然存在一个最起始时间；后拉式同理得到最后一个工序的最晚结束时间。同时，一个机台作为一个可用资源，必然存在一个就绪时间。那么我们可以把每个工单对应工序路线上的首个工序的任务作为首批需要排程的任务，先对这些任务进行一次排程；每个工单首个任务排得结果。再把排在第二位的所有任务进行排程，排在第二位的所有任务排程时的最早开始时间，就是其工序路线上的前置任务结束时与同相台前置任务的结束时间中较迟者；如此类推把所有工序上的任务均排完。那么，在每一步排程时，只需要进行机台链进行规划优化即可，即实现了把工序链截断，消除双链。

但此方案也存在不足：

1. 因为把工序上的任务分成多个部分进行排程，同一工序路线上存在的一些约束关系无法满足。
2. 因为需要分步骤规划，最终把多个步骤综合起来才能形成完成的生产计划方案，因此，无法在排程过程中动态变更任务或机台，即无法实现实时规划。

上述方案是本人目前想到的最佳解决双链排程问题的办法，若验证后可行，将会分享更多细节。