摘要
机器人柔性流水车间的调度属于组合优化问题, 涉及在指数增长的事件序列集合中寻找最优路径. 为了借助机器学习和启发式搜索的优势, 提高调度优化的求解质量和效率, 本文提出了一种基于库所赋时Petri网和监督学习的启发式优化方法. 首先, 利用库所赋时Petri网的运行规律, 设计了启发式数据集的生成算法; 其次, 设计库所赋时Petri网的全连接神经网络学习模型, 从数据集中学习Petri网行为的启发式; 再次, 以全连接神经网络模型作为启发式函数, 设计了库所赋时Petri网A ∗和集束搜索算法; 最后, 以某机器人柔性流水车间为例, 进行了系列数值实验. 本文方法获得了该流水车间库所赋时Petri网的高精度启发式, 其平均相对误差低于0.05%, 基于该启发式的A ∗和集束搜索算法均能快速求解给定任务的最优或近似最优的调度策略.
关键词
Abstract
The scheduling of robot flexible flow shops is a combinatorial optimization problem, which involves searching for an optimal path in the exponentially growing set of event sequences. In order to improve the quality and efficiency of scheduling optimization by taking advantage of the machine learning and heuristic search, a heuristic optimization method is proposed based on the place-timed Petri nets and supervised learning. Firstly, the algorithm is presented to generate a heuristic data set by the executing rules of place-timed Petri nets. Secondly, the fully connected neural network is designed to learn the heuristic function to predict Petri net behavior from data sets. Thirdly, the neural network is used as the heuristic function, and the A ∗ and beam search algorithms are presented for a place-timed Petri net. Finally, taking a robot flexible flow shop as an example, numerical experiments are carried out. The experimental results show that a high-precision heuristic is obtained by the proposed method for the flow shop’s place-timed Petri net model, whose average relative error is less than 0.05%. Both A ∗ and beam search algorithms designed by us can be used to quickly solve the optimal or nearly optimal scheduling strategies for the flow shop.
1 引言
工业4.0在世界范围内越来越受到重视，旨在构建一个智能化生产系统，来保证生产的灵活性和高效率. 在传统刚性自动化生产中，面对单一大批量订单时，能够保证较高的设备利用率和生产效率，以及较低的单件生产成本，但在应对多种零件的小规模生产时，需要大量人工干预，生产成本快速升高，企业运营成本效率低下. 而机器人柔性流水车间是机械与电子技术的结合，能满足定制化、多品种、小批量、多批次的柔性生产需求，可以达到更高的操作效率、生产力和自动化水平，其中调度策略的求解面临着更大挑战，尤其是机器人柔性流水车间的调度比经典的流水车间和单件车间调度问题要复杂的多，因为它不仅要合理优化各种不同类型工件的加工顺序，还要有效地规划机器人的物料运送作业 [1] . 因此，机器人柔性流水车间的调度属于加工任务指派和机器人动作规划的联合优化问题.
由于机器人柔性流水车间的状态空间是离散集，状态转移是事件的驱动，可以通过Petri网对机器人柔性流水车间进行建模. Petri网对描述并发、同步和异步等现象有很大的优势 [2]，可以直观展示系统的动态行为和刻画信息空间 [3-5] . 近年来，Petri网在研究离散事件系统的建模、分析、控制以及调度等方面表现出了巨大的优势和潜力.
为了描述优化问题，需要将成本因素表示到Petri 网模型当中，可以通过给库所或变迁赋上时间，来表示调度优化问题 [6-8]，即通过搜索赋时Petri网可达图，找到最小执行时间，求解出系统的最优调度策略. 文献 [9-10]根据特定网络结构，利用赋时事件图所有可能的回路来进行调度. 文献 [11]通过递归方案获得可达状态的完整枚举，有效避免状态空间重复探索. 但现有研究更多的是将赋时Petri网与A∗、集束等 [12-13] 启发式搜索算法相结合，通过启发式进行图搜索实现调度的优化. 涉及的启发式包括: 状态方程 [14-15]、最小路径长度 [16-17]、关键路径 [18]、加权允许函数 [19-20] 和最大剩余时间 [21-22]，均是Petri网运行规律的人为经验，存在两大问题: 一是启发式估计精度有限，搜索效率不足; 二是往往局限于某种Petri网子类，不利于实际应用. 而机器学习为启发式设计提供了智能化选择，使得可以利用Petri网行为数据，进行启发式规则的挖掘学习.
近年来，出现了用图同构网络、双层调度器等描述生产环境，利用深度强化学习进行流水车间调度优化问题 [23-26]，也有一些学者开始以Petri网模拟生产环境，研究深度强化学习调度方法. 文献 [27] 提出了一种基于有色Petri网和强化学习的制造系统调度方法，调度智能体使用 Q-learning计算指令. 文献 [28] 通过神经网络计算Petri网任意状态下最佳动作，从而实现对机器人流水车间的快速动态调度. 针对单机器人流水车间循环调度问题，文献 [29-30] 提出了在强化学习环境下构建赋时Petri网模型来定义状态、行动和奖励的方法. 但是目前还没有出现利用机器学习训练启发式的工作，无法发挥智能搜索的优势. 为此，笔者 [31] 尝试利用神经网络训练启发式，用于A∗搜索的调度方法研究，但工序选择特征偏少，启发式精度训练不足，搜索效率有待提高.
针对机器人柔性流水车间的调度优化问题，本文提出了一种基于库所赋时 Petri网和监督学习的启发式优化方法. 首先，设计机器人柔性流水车间的库所赋时Petri网模型，利用Petri网的运行规则，开发启发式数据集的生成算法; 然后，给出了库所赋时Petri网的启发式监督学习方法; 神经元连接关系表示库所赋时Petri网结构，利用启发式数据集对神经网络进行有监督训练，将库所赋时Petri网运行规律拟合到神经网络中，从而获得机器学习启发式; 再次，以全连接神经网络作为启发式，设计了库所赋时Petri网A∗搜索算法，来计算最优调度策略，并进行了系列仿真实验，结果表明: 使用本文设计的神经网络启发式，A*算法获得的调度策略与最优策略的平均误差为4.201%，其平均求解效率是Dijkstra算法的38.7倍，是文献 [17] 中效率最高的启发式A∗算法12.2倍，这说明本文的神经网络启发式能够有效提升机器人柔性流水车间A∗优化方法的计算效率. 随着系统规模的增大，任务数量的增多，A∗也面临着内存溢出的状态空间爆炸难题，为此，本文设计了库所赋时Petri网集束搜索算法，实验结果表明: 集束算法获得的调度策略与最优策略的平均误差为7.388%，其平均求解效率是 Dijkstra算法的 109倍. 这也说明集束算法能够有效减少状态数量，在有限时间内求解近似最优的可行调度策略.
相较于现有的 Petri 网启发式搜索研究工作 [12-13，15，17-18，22]，本文贡献主要体现在两个方面: 1）将机器学习引入启发式设计，从而为启发式设计提供了一条数据驱动的新途径，更有可能获得高精度启发式，而启发式精度越高，A∗算法的搜索效率越高; 2）不仅考虑了加工站的加工工序的时间消耗，还考虑机器人搬运工件的时间消耗，是一类更为复杂的工作站工序和机器人动作联合优化问题.
2 基本概念
普通Petri网结构是一个三元组，记为N =（P，T，F），其中: P 是库所集; T 是变迁集; F ⊆（P × T）∪（T × P）是一个库所和变迁组成的二元组的集合，表示库所与变迁之间的有向弧. 有向弧上的权值用W表示，本文中所有弧的权值W默认为1. 前置关联矩阵C− : P × T → {0，1}，表示库所到变迁的有向弧的权值; 后置关联矩阵C + : P × T → {0，1}，表示变迁到库所的有向弧的权值; 关联矩阵由前后置关联矩阵计算得到，即C = C + − C−.
库所赋时Petri网是一个三元组其中: N是一个普通Petri网结构; 时延d : P → {0} ∪是一个库所集到非负实数集的函数; 初始标识m0 :表示初始状态下各库所拥有的托肯数目.
如果一个变迁t的所有输入库所p的托肯数目大于等于其有向弧的权值W（p，t），并且t的所有输入库所p 内的托肯已在p内的等待时间不小于d（p），那么t是使能的. 当且仅当一个变迁状态使能时，它才可以激发，记作m[t⟩. 如果变迁t在标识m下激发，则系统到达新标识m′= m + C（·，t），记作m[t⟩m′.
神经网络由大量神经元和相互关联的结构组成，包含3层结构: 输入层、隐藏层和输出层. 如果相邻两层之间任意两个神经元都有连接，那么这样的神经网络也称为全连接神经网络.
A∗是一种启发式图搜索算法，启发式函数h（n）是从任意状态 n 到目标状态的最小路径代价估计，若 ∀n，h（n）≤ h ∗（n），则h（n）是允许的启发式，其中 h ∗（n）是从任意状态 n 到目标状态的实际最小消耗. g（n）是从初始状态到任意状态n的路径代价，评价函数f（n）= g（n）+ h（n）表示从初始状态到目标状态总的路径代价估计，A∗搜索优先扩展f（n）最小的状态.
集束搜索也是一种启发式图搜索算法，评价函数负责评估每个状态的优劣，只保留B个最好的状态，每次选择最好的状态进行扩展，如果其后继状态中出现目标状态，则算法终止，否则重复上述状态扩展过程.
3 问题描述
对于一个机器人柔性流水车间，当给定生产任务时，由于存在并发过程和资源争夺问题，因此加工顺序不同，完成整个任务所用的时间也是不同的. 在满足工艺约束和资源受限约束的前提下，对机器人动作序列以及零件的加工顺序进行合理有效的规划，从而获取最少任务完工时间，是本文研究的调度优化问题.
如图1所示，这是一个机器人柔性流水车间，包含输入站（I）、4台加工站（S1，S2-1，S2-2，S3）、输出站（O）和搬运零件的机械臂（A）. 每个加工站只能容纳一个零件，机械臂只能抓取一个零件. 每个零件的生产均需要经历一系列加工工序、搬运操作. 如表1所示，该车间可以生产I，II和III型零件，分别表示为J1，J2和 J3. J1有9个生产操作，其中: J1，1表示将I型零件存放在输入站I，其耗费时间为0 s; J1，2表示机械臂A将型零件从输入站I搬运到S1，其耗费时间为2 s; J1，3表示I型零件在S1进行加工，其耗费时间为2 s; J1，4表示机械臂将I型零件从S1搬运到S2-1或S2-2，其耗费时间为2 s; J1，5表示I型零件在S2-1或S2-2进行加工，其耗费时间是 17 s; J1，6表示机械臂将 I型零件从 S2-1或 S2-2搬运到S3，其耗费时间为2 s; J1，7表示I型零件在 S3进行加工，其耗费时间为39 s; J1，8表示机械臂将I 型零件从S3搬运到输出站O，其耗费时间为2 s; J1，9 负责将I 型零件存放在输出站O，其耗费时间为0 s. 类似地，J2和J3分别也有9个生产操作，其耗费时间可见表1.
图1一个机器人柔性流水车间示意图
Fig.1A schematic of a robot flexible flow shop
表13种类型产品制造工序
Table1Three types of product manufacturing processes
说明: 所需资源S2-i中的i = 1，2.
当机器人柔性流水车间同时加工多个零件时，有限的加工站和机械臂资源必然会导致多个任务竞争同一个资源，任务指派存在指数增长的排列组合，而且机械臂动作规划和加工站任务规划之间紧密的耦合在一起，共同影响订单生产的完工时间.
如图2所示，本文为图1中的机器人柔性流水车间设计了库所赋时Petri网模型. I型零件的生产过程是个开环的路径子网，由10个库所p0 ∼ p9组成，其中p0内的托肯表示产品类型I的原始零件个数，p1 ∼ p9分别表示其9个生产操作. 类似地，II和III 型零件的生产过程描述为开环的路径子网，而机械臂的移动过程表示为环状结构.
图2机器人柔性流水车间的赋时Petri网模型
Fig.2Timed Petri net model of the robot flexible flow shop
当p0，p10 和p20内的托肯分别转移到p9，p19和p29 时，3种类型的零件全部加工完毕，整个生产任务完成. p30−p34表示机械臂处于某个加工站位置; p35−p42表示机械臂在加工站之间的空载移动，每次空载时间消耗为2 s，这些库所中的托肯表示机械臂; p43−p46为加工站资源库所，其中的托肯表示加工站可加工资源数量.
借助库所赋时Petri网模型，通过观察变迁激发，就能清晰地了解机械臂的移动路径和加工站的任务执行次序. 因此，机器人柔性流水车间的调度优化可以抽象为一个可达图的搜索问题，即找到一条从初始状态到达目标状态耗时最短的变迁激发序列.
4 库所赋时Petri网启发式学习模型的设计方法
为了获取神经网络启发式学习模型所需的行为数据，给出了库所赋时Petri网启发式数据集的生成算法.
定义 1 给定一个库所赋时Petri网Gd =（N，d，m0）和一个目标标识mg，它从初识标识开始任意激发k ∈ N个变迁后到达状态 Xk，Xk =（mk，vk，gk，）是一个四元组，其中: mk表示库所赋时Petri网的标识; gk表示库所赋时Petri网从初识状态到达Xk的已经消耗时间; vk : P → {0} ∪ 是一个从库所集到非负实数集的映射，表示库所内托肯的已等待时间，vk（p）则表示一个托肯在库所p内的已等待时间，如果托肯在gi时刻流入到库所p，那么在Xk状态下，其已等待时间vk（p）= gk − gi; 表示库所赋时Petri网从Xk 到达目标状态实际需要的最小时间.
根据定义 1可知，库所赋时 Petri网从初识状态开始演化，其中不会影响该网的运行.表示库所赋时Petri网的k个激发变迁的发生时刻，第k个激发变迁表示为ek，它需要满足
定义 2 如果库所赋时Petri网处于第k个激发时刻的状态Xk，那么λk+1表示激发第k + 1个变迁还需等待的时间，即λk+1
综上所述，库所赋时Petri网从初识状态X0开始演化，符合库所赋时Petri网的变迁激发规则，因此假设该网处于当前状态Xk，当前时刻为gk，那么经过时间间隔λk+1后，在gk+1 =gk+ λk+1时刻，可以激发变迁 ek+1，库所赋时 Petri网到达下一个状态 Xk+1 =其中各状态分量满足
(1)
(2)
(3)
(4)
(5)
定义 3 给定库所赋时Petri网的任意个状态Xk，如果mk与目标标识mg相同，则Xk为目标状态; 如果 Xk下无可激发的变迁，则Xk称为死锁状态.
根据定义1–3，算法1给出了库所赋时Petri网启发式数据集Dh的生成算法（见表2）.
通过算法1可以获取库所赋时Petri网的可达图中每个结点的数据信息，每个结点数据包含了一个Petri网状态Xk的mk，vk，gk和，所有结点的m，v和h ∗ 组成了启发式数据集Dh.
表2算法1: 库所赋时Petri网启发式数据集Dh的生成算法
Table2Algorithm 1: Generation algorithm of heuristic data set Dh in Petri net
步骤1–13负责扩展Petri网的从初识状态到目标状态的可达图. 步骤1初始化初始标识m0下的每个库所内托肯已等待的时间v0、初始状态到当前状态已经消耗的时间g0、两状态间的时间间隔λ0以及到达目标状态需要消耗的时间 . 步骤2–5将初始状态作为可达图的根结点，开始正向扩展，并将待扩展的结点标记为new，将其放入OPEN表中，已扩展的结点放入CLOSED表，如果初始标识和目标标识一样，直接将该结点作为goal结点，并输出Dh. 步骤6–8选取OPEN表中待扩展的结点进行扩展，将已扩展的结点标记为old，将其放入CLOSED表，计算所有使能的变迁. 步骤9– 16依次激发一个状态下所有的使能变迁，每激发一个变迁，在对应可达图上生成一个相应结点，同时计算结点的数据信息，将goal结点的h ∗赋值为零，直到OPEN表中没有待扩展的new结点，可达图正向扩展完成. 此时，除了goal结点的h ∗为零，其余结点的h∗都为无穷大. 步骤17–19从目标结点反向遍历可达图，将所有的goal结点作为反向扩展的根结点，逐次用公式6 计算每个状态结点的，本文将死锁或者必将达到死锁的状态结点的h∗赋值为初始结点h ∗的1.5倍，让这类结点的h ∗远大于其它结点的h ∗，以便启发式数据集训练出来的启发式函数在进行启发式搜索时避免死锁的产生，因为在后续的A∗或者集束算法中，在对评价函数进行排序时，h∗大的状态结点就不会考虑扩展了. 当所有结点都反向更新完成，便可输出Dh.
在机器人柔性流水车间库所赋时Petri网模型中，每种零件的加工过程都是开环的路径子网结构，表示零件的托肯从开始加工库所到达结束加工库所的流动方向都是单向的，而且，尽管机械臂移动子网属于环状结构，通过新旧结点判断，能够避免将已经扩展过的状态结点放入到OPEN表中，因此，OPEN表的大小会收敛到0，也就是说算法1是可以收敛的.
算法1的时间复杂性可以由可达图的规模来分析，可达图内状态结点个数是托肯在库所内的排列组合，是随着库所个数n指数增长的，因此算法1的时间复杂性是O（q n ），其中q是库所能够获得的最大托肯数.
在获得了库所赋时Petri网的启发式数据集Dh之后，本文给出了一个全连接神经网络学习模型的设计方法，用于拟合从库所赋时Petri网标识到最小估计消耗时间之间的函数关系，从而获得高精度的神经网络形式的启发式函数.
基于库所赋时Petri网的结构信息，本文给出了其启发式全连接神经网络的设计方法:
1）在输入层，为库所赋时Petri网的每个库所设计两个神经元，分别表示该库所的托肯数和托肯已等待时间;
2）在输出层，设计唯一一个神经元，表示库所赋时Petri网每个状态的最小估计消耗时间;
3）在隐藏层，神经元个数逐层减少，每层与上一层的神经元个数的差值公式为
(6)
其中: nd为相邻两层神经元个数的差值，n为前一层神经元个数，no为输出层神经元个数，α为[1，10]区间内的经验常数.
根据上述方法，可以设计一个全连接神经网络，将库所赋时Petri网每个状态对应的标识mk和已等待时间vk作为输入，输出的是从Xk到达目标标识的估计消耗时间，于是便可以得到神经网络形式的启发式函数
以图2所示库所赋时Petri网为例，根据算法1，本文设计了名为 Net2Heuristic的C++ 程序，输入库所赋时Petri网的关联矩阵、初始状态和目标标识，就可以计算出启发式数据集Dh，并以 txt 文件的形式输出.3类零件各加工2个，Net2Heuristic生成了一个数据集，该数据集Dh是一个11801431行57列的矩阵.
根据本文神经网络的设计方法，为图2所示库所赋时Petri网设计了表示启发式函数的全连接神经网络，它的输入层包含56个神经元，具有6个隐藏层，各隐藏层神经元个数为: 48，38，30，23，15和8，输出层的神经元个数为1.
在Python3.7的计算机编程环境下，使用Tensorflow框架进行神经网络的搭建，将3类零件各加工2个的数据集作为数据样本，随机划分为训练集和测试集，对神经网络进行训练.
训练完成后，将数据集对应的全部Petri网状态，用神经网络来计算它们的估计任务加工时间，并与数据集中的实际值进行了比较，比较结果见表3. 从平均误差和平均相对误差结果来看，全连接神经网络对加工时间的估计达到了较高精度，训练集上平均相对误差不高于 0.04%，测试集上的平均相对误差不高于 0.05%，这也反映出本文的神经网络模型具有较好的泛化能力.
表3神经网络的训练效果
Table3Training effectiveness of neural network
5 库所赋时Petri网神经网络启发式搜索算法的设计
在获取全连接神经网络的启发式函数后，基于库所赋时Petri网的运行规则和全连接神经网络的启发式函数，给出了库所赋时Petri网启发式搜索算法（见表4）.
算法2中，步骤1–3初始化m0，v0，g0，λ0，和f0. OPEN表用来存放待扩展状态结点，开始时只包含一个初始状态X0; CLOSED表用来存放已扩展结点，最初时为空. 步骤4–5从X0开始扩展，并将其放入CLOSED表，计算所有使能的变迁. 步骤7–13计算每个变迁激发后状态结点的相关信息. 每个结点通过调用全连接神经网络的启发式函数和已经消耗的时间，来计算评价函数f值. 如果找到了目标标识，直接输出初始标识到该标识的变迁激发序列，即调度策略; 否则，将新产生的结点放入OPEN表中，如果OPEN表中结点数超出了B个，就删掉f值最大的结点. 步骤13–14判断OPEN表是否为空，如果为空，表示没有找到调度策略; 否则，在OPEN表中选取f值最小的进行扩展，并计算各状态结点的相关信息.
表4算法2: 库所赋时Petri网神经网络启发式搜索算法
Table4Algorithm 2: Library timed neural network heuristic search algorithm Petri net
当集束宽度B无穷大时，算法2为A∗算法，当B为一个有限值时，算法2为集束算法. 两种算法都是根据库所赋时Petri 网的运行规则和神经网络启发式函数来扩展状态结点. 当加工任务较大时，A∗ 搜索会面临搜索效率不足的问题，这时可采用集束算法来降低空间和时间复杂度. 集束算法对待扩展结点个数进行了限制，从而剪掉一些质量较差的结点，能以较快的速度搜索到一条可行的调度策略.
算法2在搜索过程中引入了新旧结点的判断，避免了状态结点的重复扩展，因此其收敛性与算法1相似，同时引入了启发式搜索策略，能够避免很多远离最优路径的状态结点的扩展，因此，算法2是可以收敛的.
A∗算法的时间复杂度通常由3个量表达: 从初始状态到目标状态的动作执行步数d、状态结点的最大后继状态个数b和启发式的最大相对误差ϵ，其时间复杂度指数增长，记为O（bϵd）[32] . 算法2本质上是一个 A∗算法，其中d对应该算法中从初始标识到目标标识的激发变迁个数，b为最大使能变迁个数. 本文的启发式采用神经网络模型，无法给出具体计算公式，但在示例实验中，启发式平均相对误差降低到了0.05%，因其位于时间复杂度的指数项，因此本文方法可以有效提高启发式搜索效率.
6 数值实验
根据算法 2，本文设计了名为 Heuristic-search的 C++程序，输入库所赋时Petri网的关联矩阵、初始状态、目标标识、启发式函数模型和集束宽度B，借助神经网络模型作为启发式引导搜索，通过设定B为无穷大或有限值选择A∗和集束模式，最终输出最短完工时间对应的那条变迁激发序列，从变迁激发序列中能清楚地了解到系统中机械臂的移动路径以及零件的加工次序. 为了考察算法2的性能，本文也设计了Dijkstra算法的C++程序.
以图1所示机器人柔性流水车间为实验对象，在 2.90 GHz CPU和16.0 GB RAM的64位操作系统上，对其分别进行了Dijkstra，A∗和集束搜索的系列仿真实验. 在A∗算法实验中，将文献 [17] 中搜索效率最高的启发式hexp和本文神经网络启发式hdnn进行了多组对比实验. 需要说明的是，文献 [17] 中的启发式并不适用于存在机械臂动作时间消耗的优化调度. 因此，本文对hexp进行了扩展，使其可以兼顾机械臂路径规划，即适用于机械臂空载移动的环状Petri网结构. 启发式神经网络模型是在Tensorflow框架下采用加工任务为（3，3，3）的数据集训练得到的，加工任务（i，j，k）表示加工i个I型零件、j个II型零件和k个 III型零件.
6.1 A∗算法实验分析
如表5所示，本文对训练集内的加工任务进行了 14组Dijkstra和A∗算法的数值实验. A∗（hdnn）表示采用本文神经网络启发式A∗算法，A∗（hexp）表示采用文献 [17] 中启发式的A∗算法. 在实验1–8中，A∗ （hdnn）得到的加工路径与Dijkstra算法相一致，都是最优解. A∗ （hexp）得到的加工路径并不都是最优路径，且每个实验中其搜索的状态数均多于A∗ （hdnn）. 以实验8为例，Dijkstra 搜索的状态数为 31 858，A∗ （hexp）搜索得到的状态数为6474，而A∗ （hdnn）仅需搜索1015个状态，这也意味着A∗ （hdnn）搜索时间远少于Dijkstra和 A∗ （hexp）. 在实验9–14中A∗（hdnn）得到的加工路径是近似最优解. 经统计，实验1–14中A∗ （hdnn）的平均搜索效率约是 Dijkstra算法的37倍，是A∗ （hexp）的13倍. 以实验 14为例，Dijkstra 搜索的状态数为 126 490，A∗ （hexp）搜索得到的状态数为46 210，而A∗ （hdnn）仅需搜索6474个状态，其搜索状态数远小于前两者的.
表5训练集内加工任务的数值实验
Table5Numerical experiments on machining tasks in training sets
随着加工零件的增多，加工任务逐渐偏离训练集，如表6所示的 11组Dijkstra、A∗和集束算法的数值实验. 在实验 15–25中，Dijkstra 平均搜索状态数是310 543，A∗ （hexp）平均搜索状态数是96 808，A∗ （hdnn）平均搜索状态数是7961. A∗ （hdnn）搜索效率比 Dijkstra平均提高了约38倍，比A∗ （hexp）平均提高了约11倍.
综合以上分析，对于训练集内的加工任务，A∗ （hdnn）在搜索效率和最优性上普遍优于启发式A∗ （hexp）; 对于训练集外的加工任务，A∗ （hexp）在最优性上优于A∗ （hdnn），但其搜索效率远低于 A∗ （hdnn）.
表6训练集外加工任务的数值实验
Table6Numerical experiments on machining tasks out-of training sets
6.2 集束算法实验分析
随着加工任务数量增加，特别是系统状态远离训练集时，神经网络启发式A∗算法需要扩展的状态数快速增加，计算效率明显降低. 为了保证此类加工任务调度计算效率，本文给出了算法2中集束搜索方法，并开展了系列数值实验，实验结果汇总在表6中，其与最优解的平均相对误差为 7.388%，平均搜索效率约是 A∗算法的6倍. 以实验25为例，A∗需要搜索59 883个状态，而集束只需要搜索3341个状态. 综合以上分析，对于计算效率要求严格、规模较大的实际工程问题，神经网络启发式集束搜索算法具有一定优势.
7 结论
针对柔性制造系统的启发式调度优化问题，本文提出了一种基于库所赋时Petri网和监督学习的启发式优化方法，该方法可以获得高精度的启发式，并且能够利用A∗或集束算法快速找到最优或近似最优解. 在加工任务较大的情况下，运用集束算法，在保证其求解性能的基础上，仍能进一步提高搜索效率，为实际制造系统提供高效、柔性的调度优化解决方案.
在后续的研究中，笔者将着重开展库所赋时Petri 网可达图理论研究，给出状态新旧的严格判据，以删减启发式训练数据集，有效缓解大加工任务制造系统数据集指数增长问题.