一种基于拓扑邻域结构的柔性车间混排可变批调度方法及设备

本发明属于车间集成调度相关，更具体地，涉及一种基于拓扑邻域结构的柔性车间混排可变批调度方法及设备。

背景技术：

1、精密装备制造是现代科技的核心，是制造业的主要组成部分之一。这些装备包括了一系列复杂的系统，每一个系统都由众多精密的部件和子系统组成。由于使用环境的特殊性，如真空、极端温度、强辐射等，精密装备必须具备高度的可靠性、稳定性和适应性。因此，深入研究精密装备的制造过程优化调度方法，对提高精密装备的生产效率具有重要意义，进而促进制造业水平的进一步发展。

2、虽然精密装备的结构复杂、种类繁多，但其制造过程却需要经历一系列相似的工艺流程，如材料准备、精密加工、组装测试、环境适应性试验等。这些工艺流程中，每一步都需要严格的质量控制和技术保障，以确保最终产品的可靠性和稳定性。同时，由于装备的特殊性，其制造过程中的每一个环节都需要经过严格的测试和验证，以确保装备能够在极端的环境下正常工作。并且，由于不同的部件生产、装配和测试流程不尽相同，且具备一定的生产柔性，属于典型的离散型制造行业。

3、现有的离散制造调度的研究中或调度方法，常常将同类产品的同道工序视作为一个整体进行加工，待所有产品全部加工完成之后，再整体转运至下道工序的加工设备上。显然，这显然无法充分利用柔性作业车间中设备的加工能力，会导致过长的设备等待闲置时间，减小设备利用率，进而降低生产制造效率。分批生产调度作为车间生产效率提升的有效策略之一，可以将工序划分为若干个大小不等的批次，在其中部分子批加工完成后就提前运输至下道工序的加工设备之上，让后续设备提前进入生产状态，进而降低设备闲置时间。而分批生产调度往往由于需要额外考虑一个新的问题维度，导致求解的复杂性进一步攀升，解空间过于庞大和复杂，求解效率低且输出解质量不稳定，现有的调度方法难以满足企业的实际生产需求。因此，针对现有的精密装备的加工车间，研究柔性作业车间混排可变批调度方法具有重要的工程价值。

技术实现思路

1、针对现有技术的以上缺陷或改进需求，本发明提供了一种基于拓扑邻域结构的柔性车间混排可变批调度方法及设备，其旨在解决现有车间调度方案的效率及质量较低的问题。

2、为实现上述目的，按照本发明的一个方面，提供了一种基于拓扑邻域结构的柔性车间混排可变批调度方法，该方法包括以下步骤：

3、步骤一，构建精密装备制造过程中的柔性作业车间混排可变批调度模型，所述可变批调度模型同时考虑车间中的批量划分、子批排序和设备分配三个子问题，优化目标为最小化最大完工时间；

4、步骤二，采用混合元启发式算法对所述可变批调度模型进行优化求解，以得到精密装备的最佳加工调度方案；其中，所述混合元启发式算法的局部搜索是采用基于拓扑邻域结构的变邻域算法进行操作的。

5、进一步地，可变批调度模型中的首工序、非首工序、首任务、非首任务情况下各子批的完工时间cj,o,s,m需要满足以下公式的约束条件：

6、

7、

8、式中，j为产品的下标，其变化范围为j＝1，2，…，j；o为产品j对应工序的下标，其变化范围为o＝1，2，…，oj；s为子批的下标，变化范围为s＝0，1，…，snj,o，其中snj,o代表工序oj,o所划分的子批数量；m为设备的下标，变化范围为m＝0，1，…，m；cj,o,s,m代表工序oj,o对应的第s个子批slj,o,s在设备m上的完工时间，代表工序oj,o第s个子批slj,o,s对应的第w个部件的完工时间；tj,o,m代表工序oj,o在设备m上的单位加工时间，sto,j,o',j',m代表如果设备m上前后紧邻加工任务不一致时存在的设备切换时间；xj,o,s,m,r代表工序oj,o的第s个子批slj,o,s是否为设备m上的第r个任务的二进制变量；yj,o,s,w,m代表工序oj,o第s个子批slj,o,s的第w个部件是否在设备m上加工的二进制变量；σj,o,s,w代表部件w是否为工序oj,o第s个子批slj,o,s的第一个部件的二进制变量。

9、进一步地，可变批调度模型中的最大完工时间需满足的约束条件为：

10、o∈{1,2,...,oj}；s∈{1,2,...,njo}；m∈{1,2,...,m}

11、优化目标为确定j种精密装备的分批方案，以及各工序的各子批在m台设备上的加工顺序，使得柔性作业车间混排可变批调度模型中的最大完工时间cmax最小。

12、进一步地，步骤二具体包括以下子步骤：

13、step1，采用三层编码的形式来表示可变批调度模型的一个可行解，并依次确定各个工序各个子批的完工时间以最终得到优化目标；

14、step2，混合算法参数设置；

15、step3，个体初始化以及种群初始化；

16、step4，进化学习算子；

17、step5，变邻域操作算子；

18、step6，精英个体重分批操作；

19、step7，如果混合算法满足当前迭代次数等于gmax，则输出种群的最优个体及其对应的完工时间数值；否则跳转至步骤step4，反复迭代更新，直至满足终止条件为止。

20、进一步地，step1中，采用三层编码的形式来表示可变批度模型的一个可行解，第一层为分批编码层，即代表工序的分批数量；第二层为工序顺序编码层，代表各种产品各道工序的加工顺序；第三层为设备选择编码层，代表每个工序选择对应的加工设备。

21、进一步地，依次选取工序层的工序oj,o为待排序工序；其次，根据分批编码层，确定该工序对应的子批数目snj,o以及各子批的具体批量；根据设备选择编码层来确定该工序对应加工任务的所在设备；然后，采用主动解码的策略，将工序oj,o对应的各个子批，在所选设备的空闲时段内依次进行插入判定，寻找对应设备的最早可用时间；寻找前序工序oj,(o-1)中能够满足批量约束的子批slj,(o-1),s’，得到其完工时间作为当前子批slj,o,s的最早开工时间，并与设备最早可用时间比较，取其中的较大值作为子批的开工时间；根据该子批的批量ssj,o,s以及单位加工时长计算该子批slj,o,s的完工时间；最后，判定选定工序oj,o对应的所有子批的完工时间中的最大值，作为该工序的完工时间，继而依次确定各工序的完工时间并最终得到优化目标cmax。

22、进一步地，学习操作算子有5种，分别为：操作算子1：选定种群中的最优个体sbest和待操作个体s，对三层编码进行pox交叉操作；操作算子2：对编码中的分批编码层进行变异操作；操作算子3：对编码中的工序编码层进行操作；操作算子4：对编码中的设备选择层进行操作；操作算子5：对待操作个体s的三层编码均进行操作。

23、进一步地，在对种群中的质量靠前比例为eliterate的精英个体解转化为三维析取图及拓扑排序，并识别关键路径之后，执行变邻域操作；候选邻域结构包括3种，邻域结构1：对关键路径中节点在拓扑链表中执行拓扑k-insertion操作，将关键节点插入至另一可选设备的任务队列之中；邻域结构2：对关键块内的节点，在拓扑链表中寻找对应加工设备上的前序节点和后序节点，并对节点位置进行交换以实现块内移动操作；邻域结构3：对种群及其中个体进行随机重置更新操作。

24、本发明还提供了一种基于拓扑邻域结构的柔性车间混排可变批调度系统，所述系统包括存储器及处理器，所述存储器储存有计算机程序，所述处理器执行所述计算机程序时执行如上所述的基于拓扑邻域结构的柔性车间混排可变批调度方法。

25、本发明还提供了一种计算机可读存储介质，所述计算机可读存储介质存储有机器可执行指令，所述机器可执行指令在被处理器调用和执行时，所述机器可执行指令促使所述处理器实现如上所述的基于拓扑邻域结构的柔性车间混排可变批调度方法。

26、总体而言，通过本发明所构思的以上技术方案与现有技术相比，本发明提供的基于拓扑邻域结构的柔性车间混排可变批调度方法及设备主要具有以下有益效果：

27、1.采用混合元启发式算法对可变批调度模型进行优化求解，该混合元启发式算法的局部搜索是采用基于拓扑领域结构的变邻域算法进行操作的，可以将高维复杂的柔性作业车间混排可变批调度问题转化为线性的表达形式，能够快速、有效地在较短时间内进行邻域扰动并避免不可行解的产生，进而高效稳定地获得问题的近似最优解，具有高效的搜索性能。

28、2.根据精密装备的工艺流程和生产特点，建立精密装备生产车间的柔性作业车间混排可变批调度模型，采用不一致分配策略，充分适量地对解空间进行扩张，提升获得更短完工时间的调度方案的可能性，有效地提升设备利用率和生产效率。

29、3.采用混合元启发式算法对精密装备制造过程的分批调度模型进行优化，调度结果更加贴合生产实际，能够直接应用于车间的生产，大幅地提高精密装备生产车间的生产效率。

30、4.在对种群中质量靠前的比例为eliterate的精英个体解转化为三维析取图及拓扑链表编码，并识别关键路径之后，继而得到3种候选邻域结构，够在快速、有效地在较短时间内进行邻域的高质量扰动，并避免不可行解的产生，进而减少了后续可行性判定的计算资源消耗，提升求解算法的搜索性能。

技术特征：

1.一种基于拓扑邻域结构的柔性车间混排可变批调度方法，其特征在于：该方法包括以下步骤：

2.如权利要求1所述的基于拓扑邻域结构的柔性车间混排可变批调度方法，其特征在于：可变批调度模型中的首工序、非首工序、首任务、非首任务情况下各子批的完工时间cj,o,s,m需要满足以下公式的约束条件：

3.如权利要求2所述的基于拓扑邻域结构的柔性车间混排可变批调度方法，其特征在于：可变批调度模型中的最大完工时间需满足的约束条件为：

4.如权利要求1所述的基于拓扑邻域结构的柔性车间混排可变批调度方法，其特征在于：步骤二具体包括以下子步骤：

5.如权利要求4所述的基于拓扑邻域结构的柔性车间混排可变批调度方法，其特征在于：step1中，采用三层编码的形式来表示可变批度模型的一个可行解，第一层为分批编码层，即代表工序的分批数量；第二层为工序顺序编码层，代表各种产品各道工序的加工顺序；第三层为设备选择编码层，代表每个工序选择对应的加工设备。

6.如权利要求5所述的基于拓扑邻域结构的柔性车间混排可变批调度方法，其特征在于：依次选取工序层的工序oj,o为待排序工序；其次，根据分批编码层，确定该工序对应的子批数目snj,o以及各子批的具体批量；根据设备选择编码层来确定该工序对应加工任务的所在设备；然后，采用主动解码的策略，将工序oj,o对应的各个子批，在所选设备的空闲时段内依次进行插入判定，寻找对应设备的最早可用时间；寻找前序工序oj,(o-1)中能够满足批量约束的子批slj,(o-1),s’，得到其完工时间作为当前子批slj,o,s的最早开工时间，并与设备最早可用时间比较，取其中的较大值作为子批的开工时间；根据该子批的批量ssj,o,s以及单位加工时长计算该子批slj,o,s的完工时间；最后，判定选定工序oj,o对应的所有子批的完工时间中的最大值，作为该工序的完工时间，继而依次确定各工序的完工时间并最终得到优化目标cmax。

7.如权利要求4所述的基于拓扑邻域结构的柔性车间混排可变批调度方法，其特征在于：学习操作算子有5种，分别为：操作算子1：选定种群中的最优个体sbest和待操作个体s，对三层编码进行pox交叉操作；操作算子2：对编码中的分批编码层进行变异操作；操作算子3：对编码中的工序编码层进行操作；操作算子4：对编码中的设备选择层进行操作；操作算子5：对待操作个体s的三层编码均进行操作。

8.如权利要求1所述的基于拓扑邻域结构的柔性车间混排可变批调度方法，其特征在于：在对种群中的质量靠前比例为eliterate的精英个体解转化为三维析取图及拓扑排序，并识别关键路径之后，执行变邻域操作；候选邻域结构包括3种，邻域结构1：对关键路径中节点在拓扑链表中执行拓扑k-insertion操作，将关键节点插入至另一可选设备的任务队列之中；邻域结构2：对关键块内的节点，在拓扑链表中寻找对应加工设备上的前序节点和后序节点，并对节点位置进行交换以实现块内移动操作；邻域结构3：对种群及其中个体进行随机重置更新操作。

9.一种基于拓扑邻域结构的柔性车间混排可变批调度系统，其特征在于：所述系统包括存储器及处理器，所述存储器储存有计算机程序，所述处理器执行所述计算机程序时执行权利要求1-8任一项所述的基于拓扑邻域结构的柔性车间混排可变批调度方法。

10.一种计算机可读存储介质，其特征在于：所述计算机可读存储介质存储有机器可执行指令，所述机器可执行指令在被处理器调用和执行时，所述机器可执行指令促使所述处理器实现权利要求1-8任一项所述的基于拓扑邻域结构的柔性车间混排可变批调度方法。

技术总结
本发明属于车间集成调度相关技术领域，其公开了一种基于拓扑邻域结构的柔性车间混排可变批调度方法及设备，该方法包括以下步骤：步骤一，构建精密装备制造过程中的柔性作业车间混排可变批调度模型，所述可变批调度模型同时考虑车间中的批量划分、子批排序和设备分配三个子问题，优化目标为最小化最大完工时间；步骤二，采用混合元启发式算法对所述可变批调度模型进行优化求解，以得到精密装备的最佳加工调度方案；其中，所述混合元启发式算法的局部搜索是采用基于拓扑邻域结构的变邻域算法进行操作的。本发明能够快速、有效地在较短时间内进行邻域扰动并避免不可行解的产生，进而高效稳定地获得问题的近似最优解，具有高效的搜索性能。

技术研发人员：李新宇,杨梓芃,李育鑫,刘齐浩,崔航浩,周金龙,高亮,王喆,白静,张苗苗
受保护的技术使用者：华中科技大学
技术研发日：
技术公布日：2024/12/5