(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211071572.X (22)申请日 2022.09.02 (71)申请人 合肥工业大 学 地址 230009 安徽省合肥市包河区屯溪路 193号 (72)发明人 李凯　尹诗　张晗　陈健福　肖巍　 周陶　张丽敏　夏露露　谢福龙　 许莉萍　 (74)专利代理 机构 北京久诚知识产权代理事务 所(特殊普通 合伙) 11542 专利代理师 郭子辰 (51)Int.Cl. G06Q 10/06(2012.01) G06Q 10/08(2012.01) G06N 3/12(2006.01)G06N 3/00(2006.01) (54)发明名称 异址机器的生产配送 协同调度方法和系统 (57)摘要 本发明提供了一种异址机器的生产配送协 同调度方法和系统， 涉及协同调度技术领域。 本 发明考虑了机器处于不同地理位置和加工性能 的情形下， 工件的加工及配送的协同调度问题， 通过对该问题进行建模及求解， 可以得到最终的 调度方案， 且该调度方案更加符合实际生产情 形。 且采用的改进 多种群遗传算法的效率更高。 权利要求书4页 说明书13页 附图2页 CN 115545406 A 2022.12.30 CN 115545406 A 1.一种异址 机器的生产配送 协同调度方法， 其特 征在于， 该 方法包括： 获取工件信息、 机器信息以及调度模型， 其中， 所述工件信息包括： 每 个工件的加工所需时长、 每 个工件的权 重； 所述机器信息包括： 每 个机器的加工 速度、 每个机器对应的配送时长； 所述调度模型以最小化所有工件的加权服务完成时刻 之和为目标； 工件的服务完成时 刻为工件在机器上的完 工时刻与配送时长之和； 求解所述调度模型， 得到最优解； 基于最优解输出调度方案 。 2.如权利要求1所述的一种异址机器的生产配送协同调度方法， 其特征在于， 所述求解 调度模型， 得到最优解， 包括： S2.1、 设置算法参数： 种群数量Np， 种群规模N0， 最大进化代数Gmax， 移民间隔代数MN， 交 叉概率pc， 变异概率pm； S2.2、 初始化种群； S2.3、 令进化代数计数器gen ＝1； S2.4、 当gen≤Gmax时， 执行S2.5； 否则转S2.13； S2.5、 令k ＝1； S2.6、 当k≤Np时， 转S2.7； 否则转S2.10； S2.7、 计算种群k中各个染色体的适应度； 且所述适应度值由调度模型的目标函数值映 射得到； S2.8、 对种群k执 行选择、 交叉、 变异进化操作； S2.9、 k＝k+1， 转S2.6； S2.10、 若达 到移民间隔代数， 转S2.1 1； 否则， 转S2.12； S2.11、 对种群执 行移民操作； S2.12、 令gen ＝gen+1， 转S2.4； S2.13、 输出多种群遗传算法的最优解。 3.如权利要求2所述的一种异址机器的生产配送协同调度方法， 其特征在于， 种群 中每 条染色体的基因长度为工件的数量n， 且染色体上 的每个基因取值为该工件所分配的机器 序号； 且染色体对应的工件按wj/pj非增的顺序排列； 其中pj表示排列后的第j个工件 的加工 所需时长， wj表示排列后的第j个工件的权 重。 4.如权利要求3所述的一种异址机器的生产配送协同调度方法， 其特征在于， 在初始化 种群时， 每个初始种群中的一条染色体按照S2.2.1～S2.2.9的步骤构建， 且其余染色体随 机生成； S2.2.1、 获取工件集合J＝{J1,J2,…Jn}； 其中， 工件集合J中的所有工件按wj/pj非增的 顺序排列； S2.2.2、 令所有机器的Ci＝0， 其中， Ci表示第i个机器完成该机器上已分配的所有工件 的时刻； S2.2.3、 令j＝1； S2.2.4、 当j≤n时， 转S2.2.5； 否则， 转S2.2.8；权　利　要　求　书 1/4 页 2 CN 115545406 A 2S2.2.5、 将第j个工件预分配给每台机器， 指定使得第j个工件的服务完成时间最小 的 机器i*加工第j个工件； S2.2.6、 更新机器i*的最早可用时刻 S2.2.7、 令j＝j+1， 转至S2.2.4； S2.2.8、 输出调度 序列。 5.如权利要求2所述的一种异址机器的生产配送协同调度方法， 其特征在于， 所述移民 操作包括： 达到预定数量的进化代数时， 选取所有种群中前Z个最优个体， 获取Z个个体之间的共 同特征； 所述共同特 征为第j个工件在所有染色体中对应的机器序号相同； 基于染色体的编码规则将具有共同特 征的工件及其对应的机器序号存 储到序列W1中； 选择Z个个体中的最优个体W0， 从中删除序列W1， 得到不具有共同特征的工件及其对应 的机器序号组成的序列W2； 对序列W2进行局部 搜索操作， 得到序列W3， 将序列W1和序列W3进行合并， 得到序列W4； 比较调度 序列W4和W0对应的目标函数值， 保留目标函数值小的序列， 并进行移民操作。 6.如权利要求5所述的一种异址机器的生产配送协同调度方法， 其特征在于， 所述局部 搜索操作包括： Step1： 将序列W2作为初始解 π， 计算初始解中所有工件的加权服 务完成时刻之和f( π )； Step2： 令算法的运行时长t＝0； Step3： 当算法的运行时长t≤最大运行时间Tmax， 转Step4； 否则转Step10； Step4： 令k ＝1； Step5： 当k≤4时， 转Step6； 否则转Step9； Step6： 生成π 的邻域Nk， 寻找邻域Nk中π 的局部最优解π ′， 并计算所有工件的加权服务完 成时刻之和f( π ′)； Step7： 如果f( π ′)<f( π )， 更新调度方案， 令π＝π ′， f( π )＝f( π ′)， k＝1， 转Step5； 否则转 Step8； Step8： 令k ＝k+1， 转Step5； Step9： 更新 算法的运行时长t， 转Step3； Step10： 输出序列W3＝ π 以及所有工件的加权服 务完成时刻之和f( π )。 7.如权利要求6所述的一种异址机器的生产配送协同调度方法， 其特征在于， 所述邻域 Nk， k＝1,2,3,4， 包括： 邻域N1： 从序列中随机选取一个工件a， 随机生成一个[1,m]的整数替换工件a对应的机 器编号； 邻域N2： 从序列中随机 选取两个不同的工件b和c， 交换工件b和c对应的机器编号； 邻域N3： 从序列中随机选取一个工件d， 随机生成一个[1,m]的整数替换工件d对应的机 器编号， 再从编码排序中随机 选取两个不同的工件e和f， 交换工件e和f对应的机器编号； 邻域N4： 从序列中随机选 取三个不同的工件a、 b、 c， 交换工件a和b对应的机器编号， 然后 交换工件b和c对应的机器编号。 8.如权利要求2所述的一种异址机器的生产配送协同调度方法， 其特征在于， 所述交叉 操作包括：权　利　要　求　书 2/4 页 3 CN 115545406 A 3