一种具有拓扑邻域结构的柔性作业车间批量流调度方法

本发明属于车间制造过程中的调度理论相关，更具体地，涉及一种具有拓扑邻域结构的柔性作业车间批量流调度方法。

背景技术：

1、邻域结构在作业车间调度领域中起着关键作用，作为优化算法的重要组成部分，邻域结构能够通过高效探索解空间的不同区域来寻找更优的调度方案。在作业车间调度问题中，合理设计和应用邻域结构可以有效提高算法的搜索效率和解决问题的能力。通过邻域结构的引导，优化算法能够快速跳出局部最优，寻找全局最优解，从而提高调度效率和生产效益。

2、现有的邻域结构大多针对于柔性作业车间调度问题，存在以下问题：首先，现有的邻域结构在对关键路径上节点进行扰动时需要严格考虑节点之间的工艺顺序约束，并且通过头时间和尾时间的计算来判定可插入位置，在这些步骤中，算法需要消耗大量资源进行计算和判断，以确保生成的解满足所有约束；其次，现有的邻域结构在优化过程中有一定的概率产生不可行解，可行性判定也将会消耗大量的计算资源，并且不可行解的产生也会导致算法陷入无效搜索。

3、与传统的柔性作业车间调度问题不同，柔性作业车间批量流调度问题是在柔性作业车间中，存在多种批量制造任务，这些任务需要在多台机器上完成加工。柔性作业车间批量流调度问题还需考虑批量流的特性。现有的邻域结构大多基于二维析取图编码，将工序作为节点进行位置的移动以产生邻域解。然而在柔性作业批量流调度问题中，是以子批作为析取图中的节点，并且每个节点会具有产品号、工序号和子批号三种属性。这种高维复杂的约束进一步提升节点移动的难度，并提升了移动后不可行解的产生概率，导致求解的复杂性进一步攀升，解空间过于庞大和复杂，求解效率低且输出解质量不稳定。现有的邻域结构将不再适用。

4、因此，考虑到柔性作业车间批量流调度问题的特点，亟需设计一种具有拓扑邻域结构的柔性作业车间批量流调度方法，以在降低计算复杂度的同时，保证邻域解的质量和可行性，从而提升调度优化的效果。

技术实现思路

1、针对现有技术的以上缺陷或改进需求，本发明提供了一种具有拓扑邻域结构的柔性作业车间批量流调度方法，以解决求解效率低、计算资源消耗大的技术问题，其能够避免产生非法邻域解，稳定高效地获得柔性作业车间批量流调度问题的优良邻域解。

2、为实现上述目的，按照本发明的一个方面，提供了一种具有拓扑邻域结构的柔性作业车间批量流调度方法，包括以下步骤：

3、s1：种群初始化，将待优化的柔性作业车间批量流调度解作为初始解；

4、s2：建立柔性作业车间批量流调度问题的三维析取图编码模型，s1中的初始解通过三维析取图进行表达，优化目标为最小化最大完工时间；

5、s3：基于s2中的三维析取图编码模型，进行拓扑排序解码，得到一维的拓扑链表；

6、s4：利用浮动时间法进行关键路径的识别，基于步骤s3中的拓扑链表，按照线性顺序依次遍历线性拓扑链表中的各子批节点，将浮动时间为0的节点插入集合，组成关键路径；

7、s5：对关键路径上的每个关键节点，使用拓扑邻域结构以得到邻域解；所述拓扑邻域结构包含两种邻域扰动操作：邻域扰动操作tns-1设置为同机器的关键节点移动，邻域扰动操作tns-2设置为跨机器的关键节点移动；

8、s6：计算最大完工时间，从邻域解中选择最大完工时间最小的作为新的最优解，当最优解的最大完工时间优于初始解时，将最优解替换初始解以进行种群的更新，判断是否满足终止条件，如满足，则输出最优解，不满足终止条件则转至步骤s1。

9、进一步地，步骤s2中，三维析取图编码模型将柔性作业批量流调度中各子批对应的产品号、工序号和子批号，分别映射至产品轴、工序轴和子批轴；三维析取图编码模型中每个坐标位置均代表着一个子批节点，子批节点之间通过产品弧、子批弧和机器弧进行指向连接，产品弧为前后工序之间的工艺顺序约束弧，子批弧为同工序的子批节点之间的虚弧，机器弧为同机器上前后任务之间的连接弧。

10、进一步地，步骤s3中，拓扑排序解码的具体步骤为：新建一个空的拓扑链表，从起始节点开始，计算所有节点的入度，将所有入度为0的节点中的一个节点v放入拓扑链表之中，并将所有与其邻接的节点的入度减1，如此循环，只要判定存在入度为0的节点，即将其放置于拓扑链表之中，直至所有的节点都已完成放置，此时拓扑链表的顺序即为拓扑排序后的节点顺序，拓扑链表中任两个节点之间都不会出现索引大的节点指向索引小的节点的情况。

11、进一步地，步骤s4中浮动时间的计算过程为：

12、依据拓扑链表中各节点之间连接弧的指向关系，从起始节点开始，递归计算各个子批节点的最早开工时间esj,o,s,m，在递归至终止节点之后，反向递归计算各个子批节点的最晚开工时间lsj,o,s,m，最早开工时间和最晚开工时间的计算公式分别如下：

13、

14、

15、其中，表示子批节点slj,o,s,m的前序节点的最早开工时间，表示子批节点slj,o,s,m的后序节点的最晚开工时间，表示子批节点slj,o,s,m的前序节点的加工时长，tcj,o,s,m表示子批节点slj,o,s,m的加工时长；

16、基于各子批节点的最早开工时间esj,o,s,m和最晚开工时间lsj,o,s,m，计算浮动时间tfj,o,s,m，计算公式如下：

17、tfj,o,s,m＝lsj,o,s,m-esj,o,s,m。

18、进一步地，步骤s5具体包括如下步骤：

19、s51：邻域扰动操作的选择，通过随机生成的一个概率数值p，取值范围为[0，1]，判定在当前解的基础上，执行何种邻域扰动操作生成新解，如果p>0.5，则选择邻域扰动操作tns-1，否则就选择邻域扰动操作tns-2；

20、s52：邻域扰动操作的可行性判定，基于s51选择的邻域扰动操作，依据判定定理，进行可行性判定，其中，判定定理设置如下：

21、邻域扰动操作tns-1对应的判定定理1：子批s与为关键块内的两个节点，只有当满足约束条件时，将节点移动至节点s后能够产生无环的可行解；其中，index表示节点在拓扑链表的索引位置，sjp和sjs分别表示节点s在工艺约束上的紧前节点和紧后节点，smp和sms分别表示节点s在机器任务顺序约束上的紧前节点和紧后节点，和分别表示节点在工艺约束上的紧前节点和紧后节点，和分别表示节点在机器任务顺序约束上的紧前节点和紧后节点；

22、邻域扰动操作tns-2对应的判定定理2：若要将节点s移动至机器m’上，则需要找到同为机器m’上的紧前节点sm’p和紧后节点sm’s，并保证拓扑链表中的位置索引满足index(sm’p)<index(s),index(s)<index(sm’s)，则将节点s移动至机器m’并插入至节点sm’p和sm’s之中不会产生有环的不可行解；

23、s53：邻域扰动操作的执行，当不满足判定定理时，保留关键节点的位置不变，当满足判定定理时，执行邻域扰动操作，关键节点的位置进行交换，生成新的邻域解；

24、其中，邻域扰动操作具体执行过程为：

25、邻域扰动操作tns-1：确定待移动关键节点si及其所属关键块{s1,s2,…,si,…,sn}，在此基础上，找到与关键节点si同机器加工的关键块首节点sf和块尾节点sl，将其在拓扑链表上的序列索引分别标注为index(sf)，index(si)，index(sl)，依据一定的随机概率判定与之互换位置的是块首节点sf还是块尾节点sl，将待交换两节点在拓扑链表中的索引位置利用判定定理1进行判定，在满足约束条件的前提下进行互换，生成邻域解；

26、邻域扰动操作tns-2：确定待移动关键节点si及其所属加工机器m，并确定需要移动到的新加工机器m’，在此基础上，找到属于加工机器m’，且在拓扑链表上与关键节点si最接近的紧前节点sm’p和紧后节点sm’s，断开原始拓扑链表中与关键节点si相关的机器弧，原始为smp→si→sms，断开后为smp→sms，将独立出来的关键节点si在新加工机器m’上进行断弧重连，组成新的完整的拓扑链表，新加工机器m’上原始为sm'p→sm's，重连后为sm'p→si→sm's，其能在保证扰动充分性的前提下，生成可行的新邻域解。

27、进一步地，最大完工时间cmax计算公式如下：

28、cmax＝max(cj,o,s,m)o∈{1,2,...,oj}；s∈{1,2,...,njo}；m∈{1,2,...,m}

29、式中，j为产品的下标，其变化范围为j＝1，2，…，j，j为产品总数；o为产品j对应工序的下标，其变化范围为o＝1，2，…，oj，oj为产品的工序总数；s为子批的下标，变化范围为s＝0，1，…，snj,o，其中snj,o代表工序oj,o所划分的子批数量；m为机器的下标，变化范围为m＝0，1，…，m，m为机器总数；cj,o,s,m代表工序oj,o对应的第s个子批slj,o,s在机器m上的完工时间。

30、进一步地，步骤s6中，终止条件为迭代次数达到预定值。

31、本发明还提供一种计算机可读存储介质，所述计算机可读存储介质中存储有计算机程序，当所述计算机程序在计算机上运行时，使得所述计算机执行所述的一种具有拓扑邻域结构的柔性作业车间批量流调度方法。

32、本发明还提供一种电子设备，所述电子设备包括处理器和存储器，所述存储器中存储有计算机程序，所述处理器通过调用所述存储器中存储的所述计算机程序，用于执行所述的一种具有拓扑邻域结构的柔性作业车间批量流调度方法。

33、总体而言，通过本发明所构思的以上技术方案与现有技术相比，本发明提供的一种具有拓扑邻域结构的柔性作业车间批量流调度方法主要具有以下有益效果：

34、1.基于拓扑链表和识别得出的关键路径，设计包含两种邻域扰动操作的拓扑邻域结构，能够在快速、有效地在较短时间内进行邻域的高质量扰动，并避免不可行解的产生，进而减少了后续可行性判定的计算资源消耗，提升求解算法的搜索性能。

35、2.针对柔性作业车间批量流调度问题的特点，建立三维析取图编码模型，结合节点、连接弧、非连接弧的特征，完整充分地对调度方案进行表征，清晰直观地反映所有子批节点的加工顺序和工艺顺序，为高质量邻域扰动提供技术基础。

36、3.根据三维析取图的高维复杂特征，设计基于拓扑排序的快速解码方法，将高维复杂的柔性作业车间批量流调度的空间图转化为线性拓扑链表的表达形式，并结合浮动时间法设计关键路径判定方法，减少解码耗时。

技术特征：

1.一种具有拓扑邻域结构的柔性作业车间批量流调度方法，其特征在于，包括以下步骤：

2.如权利要求1所述的一种具有拓扑邻域结构的柔性作业车间批量流调度方法，其特征在于，步骤s2中，所述三维析取图编码模型将柔性作业批量流调度中各子批对应的产品号、工序号和子批号，分别映射至产品轴、工序轴和子批轴；三维析取图编码模型中每个坐标位置均代表着一个子批节点，子批节点之间通过产品弧、子批弧和机器弧进行指向连接，产品弧为前后工序之间的工艺顺序约束弧，子批弧为同工序的子批节点之间的虚弧，机器弧为同机器上前后任务之间的连接弧。

3.如权利要求1所述的一种具有拓扑邻域结构的柔性作业车间批量流调度方法，其特征在于，步骤s3中，拓扑排序解码的具体步骤为：新建一个空的拓扑链表，从起始节点开始，计算所有节点的入度，将所有入度为0的节点中的一个节点v放入拓扑链表之中，并将所有与其邻接的节点的入度减1，如此循环，只要判定存在入度为0的节点，即将其放置于拓扑链表之中，直至所有的节点都已完成放置，此时拓扑链表的顺序即为拓扑排序后的节点顺序。

4.如权利要求1所述的一种具有拓扑邻域结构的柔性作业车间批量流调度方法，其特征在于，步骤s4中浮动时间的计算过程为：

5.如权利要求1所述的一种具有拓扑邻域结构的柔性作业车间批量流调度方法，其特征在于，步骤s5具体包括如下步骤：

6.如权利要求1所述的一种具有拓扑邻域结构的柔性作业车间批量流调度方法，其特征在于，最大完工时间cmax计算公式如下：o∈{1,2,...,oj}；s∈{1,2,...,njo}；m∈{1,2,...,m}式中，j为产品的下标，其变化范围为j＝1，2，…，j，j为产品总数；o为产品j对应工序的下标，其变化范围为o＝1，2，…，oj，oj为产品的工序总数；s为子批的下标，变化范围为s＝0，1，…，snj,o，其中snj,o代表工序oj,o所划分的子批数量；m为机器的下标，变化范围为m＝0，1，…，m，m为机器总数；cj,o,s,m代表工序oj,o对应的第s个子批slj,o,s在机器m上的完工时间。

7.如权利要求1所述的一种具有拓扑邻域结构的柔性作业车间批量流调度方法，其特征在于，步骤s6中，终止条件为迭代次数达到预定值。

8.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质中存储有计算机程序，当所述计算机程序在计算机上运行时，使得所述计算机执行权利要求1至7任一项所述的方法。

9.一种电子设备，其特征在于，所述电子设备包括处理器和存储器，所述存储器中存储有计算机程序，所述处理器通过调用所述存储器中存储的所述计算机程序，用于执行权利要求1至7任一项所述的方法。

技术总结
本发明属于车间制造过程中的调度理论相关技术领域，其公开了一种具有拓扑邻域结构的柔性作业车间批量流调度方法，该方法建立了柔性作业车间批量流调度问题的三维析取图编码模型，根据三维析取图的高维复杂特征，设计基于拓扑排序的快速解码方法，将高维复杂的柔性作业车间批量流调度的空间图转化为线性拓扑链表的表达形式，并结合浮动时间法设计关键路径判定方法，减少解码耗时，对于关键路径上的关键节点，利用设计好的拓扑邻域结构中的两种邻域扰动操作，高效稳定地输出可行的邻域解，有效地在较短时间内进行邻域的高质量扰动，并避免不可行解的产生，进而减少了后续可行性判定的计算资源消耗，提升求解算法的搜索性能。

技术研发人员：李新宇,杨梓芃,崔航浩,刘齐浩,李育鑫,柳再为,高亮,裴冲,张巨君,田博文
受保护的技术使用者：华中科技大学
技术研发日：
技术公布日：2024/12/5