买专利卖专利找龙图腾，真高效！ 查专利查商标用IPTOP,全免费！专利年费监控用IP管家,真方便！

龙图腾网恭喜聊城大学申请的专利混合流水车间必经工序有效位置插入的快速局部搜索方法获国家发明授权专利权，本发明授权专利权由国家知识产权局授予，授权公告号为：CN118710026B 。

龙图腾网通过国家知识产权局官网在2025-04-04发布的发明授权授权公告中获悉：该发明授权的专利申请号/专利号为：202411194605.9，技术领域涉及：G06Q10/0631；该发明授权混合流水车间必经工序有效位置插入的快速局部搜索方法是由韩玉艳;王宇航;王玉亭;李寰;张彪;贾保宪设计研发完成，并于2024-08-29向国家知识产权局提交的专利申请。

本混合流水车间必经工序有效位置插入的快速局部搜索方法在说明书摘要公布了：本发明公开了一种混合流水车间必经工序有效位置插入的快速局部搜索方法，通过调度方案的解空间表示，初始化过程，使用局部搜索方法，整个搜索过程中仅考虑必经工序的插入方法。本发明一方面通过减少移动工序的个数和插入位置的次数，有效避免了工序的无效移动，另一方面通过快速评价方法计算移动工序后的最大完工时间，节约了计算成本，提高了优化调度效率。

本发明授权混合流水车间必经工序有效位置插入的快速局部搜索方法在权利要求书中公布了：1.一种混合流水车间必经工序有效位置插入的快速局部搜索方法，其特征在于，包括以下步骤：步骤1：获取调度方案在解空间中的表示；步骤2：初始化过程，令局部搜索之后的最大完工时间等于局部搜索之前的最大完工时间，改进的标记参数等于；步骤3：如果等于，则局部搜索方法结束并输出，否则，执行步骤4；步骤4：将设置为，然后从调度方案中获取必经工序集；步骤5：依次删除其中一个必经工序，为该工序寻找有效插入位置，在插入过程中，采用快速评价方法计算从第一个工序到最后一个工序经过该必经工序的最长路径，记录使最小的位置；步骤6：如果小于，将该必经工序插入到使最小的位置，更新所有工序的完工时间和逆向完工时间，重新计算，并更新为，再执行步骤3；步骤7：如果大于等于，将该必经工序插入到原位置，执行步骤3；所述步骤1中的解空间的表示为：混合流水车间中个工件的处理过程按照相同的顺序依次经过相同的个工序的处理，每个阶段都有个并行机器处理工序；混合流水车间其中一个调度方案定义为：对每一个工序，在阶段确定唯一的机器（）处理该工序，并确定每个机器上的工序的处理顺序，其中，为工件的数量，为阶段的数量，为工件的索引,，为阶段的索引,，为阶段中并行机器的集合,，为阶段中的第台并行机器，=，为工件在阶段的工序；在解空间中，每个节点对应一个工序，每个节点的权重等于该节点对应工序的加工时间，每个阶段引入两个虚拟工序和，分别代表每个阶段所有机器加工的开始和结束，所有虚拟工序的加工时间为，此外，引入两个虚拟阶段，分别为阶段0和阶段，所有工件必须先经过阶段0的处理，然后经过正常阶段的处理，最后经过阶段的处理，每个工件在两个虚拟阶段的虚拟工序分别为和，加工时间均为0；对于同一非虚拟阶段上的操作和；如果且是的直接后继，则和之间存在两条弧线；如果是机器上的第一个操作，则和之间存在两条弧线；如果是机器上的最后一个操作，则和之间存在两条弧线；在解空间中完成正向完工时间和逆向完工时间的方法为：对于非虚拟阶段所有虚拟工序，令=0，，对于虚拟阶段的所有虚拟工序，令，，在解空间中，每一个非虚拟工序有四条入弧、、和，根据和得到工序的正向完工时间，根据和得到工序的逆向完工时间；在完成正向完工时间和逆向完工时间的计算后，确定调度方案的最大完工时间，记为；所述步骤4中的从调度方案中获取必经工序集的方法为：确定调度方案的解空间子集：基于解空间子集获得必经工序集；对于非虚拟工序，如果，工序为解空间的关键工序，在解空间中，由节点、和解空间的关键工序节点，以及和以上节点相关的弧构成的子集为解空间子集，记为，所有工序的连续操作之间没有间隙；所述基于解空间子集获得必经工序集，执行为：步骤4.1：令必经工序集合为空，设置时间戳为1；步骤4.2：对解空间子集中的每个操作，设置和为0，对解空间子集中的每条边，设置访问标记为0，构造一个栈，存储当前节点和其父节点的节点对；步骤4.3：从工序进行深度优先搜索，对于工序，设置和为当前的时间戳，将时间戳加1，将节点对进栈，表示没有父节点；步骤4.4：如果栈不为空，执行步骤5，否则执行步骤9；步骤4.5：从栈顶取出一对节点，为当前节点，为父节点；步骤4.6：寻找一条以当前节点为起点不以父节点为终点的访问标记为0的边；步骤4.7：若找到步骤4.6中的边，记该边为，设置其访问标记为1，如果discovery[]等于0，则设置和为当前的时间戳，将时间戳加1，并将节点对进栈，否则设置等于，执行步骤4.4；步骤4.8：若没有找到步骤4.6中的边，则出栈，如果栈不为空、和不是同一个节点和小于等于三个条件同时满足，则为一个必经工序，将其并入必经工序集，设置等于，执行步骤4.4；步骤4.9：基于关键子图获得必经工序集方法结束，输出必经工序集输出必经工序集；所述步骤5中的删除其中一个必经工序，将其重新插入其他位置后判断最大完工时间是否变小的快速评价方法，执行为：记为要删除并重新插入的必经工序，的原加工机器为，删除必经工序之后的最大完工时间记为，，重新插入工序后的最大完工时间记为，则；该为重新插入工序后，调度方案图中从到经过的所有路径中最长路径的长度；已知，则，进而判断删除某个必经工序将其重新插入其他位置后最大完工时间变优；在删除后，在机器上，原位置之后的工序的正向完工时间和原位置之前的工序的逆向完工时间发生变化并进行更新；在中除之外的机器上，工序的完工时间和逆向完工时间不会发生变化；完成所述更新后在每个位置插入时，记插入位置前后的工序分别为和，则等于；所述步骤5中删除其中一个必经工序，将其重新插入时有效位置的策略，执行为：记为要删除并重新插入的必经工序，的原加工机器为，在机器上，更新原位置之后的工序的正向完工时间和原位置之前的工序的逆向完工时间；往调度方案图中中重新插入时，以插入的机器为，记机器上加工的工序数为，则在机器共有位置插入，每一个位置的编号用表示，；机器上，位置前后工序记为和，位置前后工序对应的工件编号分别记为和，如果，则，表示为虚拟工序，如果，则，表示为虚拟工序，机器上从右往左第一个满足的位置记为，即，机器上从左往右第一个满足的位置记为，即。

如需购买、转让、实施、许可或投资类似专利技术，可联系本专利的申请人或专利权人聊城大学，其通讯地址为：252000 山东省聊城市东昌府区湖南路1号；或者联系龙图腾网官方客服，联系龙图腾网可拨打电话0551-65771310或微信搜索“龙图腾网”。