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

龙图腾网获悉温州大学申请的专利面向动态等效并行机调度问题的快速非支配排序遗传算法获国家发明授权专利权，本发明授权专利权由国家知识产权局授予，授权公告号为：CN114565290B 。

龙图腾网通过国家知识产权局官网在2025-06-27发布的发明授权授权公告中获悉：该发明授权的专利申请号/专利号为：202210202320.X，技术领域涉及：G06Q10/0631；该发明授权面向动态等效并行机调度问题的快速非支配排序遗传算法是由陈亚绒;王陈;黄沈权;沈纯纯;朱立夏;周富得设计研发完成，并于2022-03-03向国家知识产权局提交的专利申请。

本面向动态等效并行机调度问题的快速非支配排序遗传算法在说明书摘要公布了：本发明公开了一种面向动态等效并行机调度问题的快速非支配排序遗传算法，按下述步骤进行：S1：混合启发式规则MODD，ATC，X‑RM与随机方法生成种群；S2：基于动态规划的解码方法对种群个体进行目标值计算；S3：判断是否满足终止条件；若是，结束；否则，对种群中的个体进行快速非支配排序；S4：通过遗传算子产生子代种群；S5：将父代种群和子代种群合并而成规模为2N的种群；S6：对种群中个体进行快速非支配排序，结合拥挤度计算确定种群；S7：对种群个体进行邻域搜索产生新解替换原冗余解。本发明具有提高车间机器利用率和满足客户交期的特点。

本发明授权面向动态等效并行机调度问题的快速非支配排序遗传算法在权利要求书中公布了：1.面向动态等效并行机调度问题的快速非支配排序遗传算法，其特征在于，按下述步骤进行： S1：通过混合启发式规则和随机规则，生成规模为N的初始种群Pt，混合启发式规则包括MODD、ATC和X-RM； S2：利用基于动态规划的解码方法，计算每个个体的最大完工时间Cmax与总拖期时间和∑Tj； S3：判断是否满足终止条件；若是，结束；否则，对种群Pt中的个体进行快速非支配排序； S4：通过自适应概率交叉与变异、精英选择策略的遗传算子产生子代种群Qt； S5：将父代种群Pt和子代种群Qt合并而成规模为2N的种群Rt； S6：对Rt进行基于动态规划的解码和快速非支配排序，从第一层r1开始逐层选择非支配解个体放入新父代种群Pt+1，直到种群规模为N；若选择层级rk的个体无法全部放入，则对rk层个体进行拥挤度计算，选择拥挤度大的个体放入； S7：对种群Pt+1中的个体进行邻域搜索产生新解替换冗余解；令t＝t+1，返回步骤S3； 所述步骤S1中的初始种群Pt生成方法按下述步骤进行： 步骤2.1：问题描述与目标界定；动态等效并行机调度问题可以描述为将J＝{J1，J2，…，Jj…，Jn}中的n个工件安排到M＝{M1，M2，…，Mi…，Mm}台等效的并行机上，工件Jj的到达时间为rj，交期时间为dj，处理时间为pj，完工时间为Cj，拖期时间为Tj＝max{0，Cj-dj}，工件Jj的加工过程不可中断；机器在生产过程中需要进行弹性预防维护PM，即机器的连续加工时间或役龄不能超过界限值UT，每次维护的时长为t，优化目标为同时最小化最大完工时间Cmax＝max{Cj}与工件拖期时间和∑Tj；决策内容是确定工件在机器上的分配与加工顺序； 步骤2.2：根据初始种群中MODD、ATC、X-RM以及随机规则比例确定的数量，即N＝nMODD+nATC+nX-RM+nRandom； 步骤2.3：初始化每台机器的完工时间C1＝C2＝…＝Cm＝0，最早开工时间t1＝t2＝…＝tm＝0，役龄Age1＝Age2＝…＝Agem＝0，拖期时间和∑Tj＝0，已调度工件集合SJ1＝SJ2＝…＝SJm＝φ，未调度工件集合USJ＝{J1，J2，…，Jn}，工件数量n，维护界限值UT，维护时长t，种群规模N，工件指标j＝1，机器指标k＝1： 步骤2.4：利用MODD规则生成数量为nMODD的初始解集，包括以下步骤； 步骤2.4.1：判断USJ＝{φ}吗，若是，结束；否则，转步骤2.4.2； 步骤2.4.2：选择Jj∈USJ，转步骤2.4.3； 步骤2.4.3：当机器数量k≤m时，转步骤2.4.4；否则，转步骤2.4.5 步骤2.4.4：计算机器的役龄Agek＝Agek+pj；如果Agek＞UT，则tk＝tk+t，Agek＝pj，d′jk＝max{dj，max{rj，tk}+pj}；否则，Agek＝Agek+pj，d′jk＝max{dj，max{rj，tk}+pj}；令k＝k+1，返回步骤2.4.3； 步骤2.4.5：工件Jj的d′j＝min{d′jk}； 步骤2.4.6：令j＝j+1，返回步骤2.4.2； 步骤2.4.7：按照USJ中工件Jj的d′j值对工件进行排序，d′j值越小的排序越靠前；当d′j值相同，则交期早的排前面；如果交期相同，则序号小的工件排前面，得到排序结果π＝{J[1]，J[2]，…，J[|USJ|]}； 步骤2.4.8：当k≤m时，转步骤2.4.9，否则，转步骤2.4.11； 步骤2.4.9：当j≤|USJ|时，转步骤2.4.10； 步骤2.4.10：判断r[j]≤tk是否成立；若成立，则Agek＝Agek+p[j]，如果Agek＞UT，则tk＝tk+t，Agek＝p[j]，C[j]k＝max{rj，tk}+p[j]；否则，Agek＝Agek+p[j]，C[j]k＝max{rj，tk}+p[j]； 步骤2.4.11：C[j]h＝min{C[j]k}，将集合π中第一个当前已经到达的工件J[j]安排到机器h上，并更新Ch＝C[j]h，Ageh，th，SJh＝SJh∪J[j]，USJ＝USJJ[j]以及∑Tj；返回步骤2.4.1； 步骤2.4.12：循环步骤2.4.1-步骤2.4.11，生成数量为nMODD的初始解集； 步骤2.5：利用ATC规则生成数量为nATC的初始解集； 步骤2.6：利用X-RM规则生成数量为nX-RM的初始解集； 步骤2.7：随机将n个工件分派到m台机器上，生成数量为nRandom的初始解集； 步骤2.8：将MODD、ATC、X-RM以及随机规则四种规则生成的初始解集合并在一起，构成初始种群Pt； 所述S2和S6中的动态规划的解码方法，按下述步骤进行： 步骤3.1：初始化，将种群中的每个个体分为m段，即m台机器，每台机器上有ni个工件，对于机器Mi上的工件排序解码时，设定机器i上k个工件排序的集合为Δk＝{J[1]，J[2]，…，J[k]}，Δk中后g个工件构成的集合为分别使用Z0Δk和Z1Δk表示k个工件排序的Cmax值和∑Tj值，则Z0Δ0＝0，Z1Δ0＝0，k个工件排序的Cmax值和∑Tj值用第k阶段的状态函数表示，如公式1所示，Cmax值和∑Tj值的计算方法如公式2和3所示； 步骤3.2：基于动态规划的解码和目标值计算，包括如下步骤： 步骤3.2.1：初始化参数；机器Mi的完工时间集合 Z0Δ0＝0，Z1Δ0＝0，为UT和t参数赋值，设置种群中的染色体指标h＝1，每个染色体中的机器指标i＝1，机器上工件位置指标k＝1； 步骤3.2.2：判断种群数量hN是否成立；若是，则结束，否则到下一步骤； 步骤3.2.3：确定每台机器前k个工件的集合Δk＝{J[1]，J[2]，..，J[k]}； 步骤3.2.4：从工件位置g＝1开始，按照下面的方法计算工件集中工件排序的Ci值和Ti值； 如果g＝1，存在以下两种情形： 若k＝g，则 若kg，则 如果g＞1，存在以下两种情形： 当则： 当则： 步骤3.2.5：令g＝g+1；判断g是否小于k，若是，则返回步骤3.2.4；否则到下一步骤。 步骤3.2.6：令k＝k+1，判断k大于ni是否成立；若是，令Ci＝Z0Δk，MC＝MC∪{Ci}，Ti＝Z1Δk；否则，返回步骤3.2.3。 步骤3.2.7：令i＝i+1，到下一步骤； 步骤3.2.8：判断机器数量im是否成立，若是，到下一步骤；否则，返回步骤3.2.3； 步骤3.2.9：计算Cmax＝max{Ci，Ci∈MC}，令h＝h+1，返回步骤3.2.2； 所述步骤S4中的选择、交叉和变异方法，按下述步骤进行： 步骤4.1：根据快速非支配排序的分层结果，运用IC1和IC2两种选择规则进行个体复制；规则IC1从每一层级随机选择一半的染色体；规则IC2使用锦标赛方法选择个体；规则IC2每次随机选择三个个体进行两两比较，选择较优的两个个体；循环操作IC1和IC2直到取满N个个体为止；规则IC1可以增加种群的多样性，防止算法收敛过快；规则IC2的操作能减少有效基因的损失，较好的保留最佳个体； 步骤4.2：采用动态自适应交叉概率，利用两点交叉方法进行交叉；自适应交叉概率的计算方法为其中g表示目前迭代的次数，G表示总共要迭代的次数，pc为基本交叉概率；根据确定的自适应交叉概率，采用两点交叉的方式进行交叉；从种群N中随机选择非支配排序第一层的一条染色体px与其他层的一条染色体py作为父代；在每个父代中随机选择[1，n+m-1]中的一段基因进行交换，其余基因通过映射的方式确定；若产生的子代比父代py好，则予以保留；否则，保留原来的两条父代染色体； 步骤4.3：采用动态自适应变异概率，利用两种变异方法进行个体变异；自适应变异概率的计算方法为其中g表示目前迭代的次数，G表示总共要迭代的次数，pm为基本变异概率；根据自适应变异概率，采取MO1和MO2两种变异方式，分别用于前50％代种群和后50％代种群的变异操作； MO1算子任选一个个体且随机选择一段基因，基因段长度为将基因段内的工件顺序进行倒序；MO2算子任选一个个体并随机选择两个基因进行交换；若随机选择的基因为0，需重新进行选择。

如需购买、转让、实施、许可或投资类似专利技术，可联系本专利的申请人或专利权人温州大学，其通讯地址为：325006 浙江省温州市瓯海区瓯海经济开发区东方南路38号温州市国家大学科技园孵化器；或者联系龙图腾网官方客服，联系龙图腾网可拨打电话0551-65771310或微信搜索“龙图腾网”。