(19)国家知识产权局 (12)发明 专利 (10)授权公告 号 (45)授权公告日 (21)申请 号 202210995672.5 (22)申请日 2022.08.19 (65)同一申请的已公布的文献号 申请公布号 CN 115081755 A (43)申请公布日 2022.09.20 (73)专利权人 合肥工业大 学 地址 230009 安徽省合肥市包河区屯溪路 193号 (72)发明人 胡朝明　钱晓飞　刘心报　郑锐　 陆少军　汪鹏　程浩　周志平　 (74)专利代理 机构 北京久诚知识产权代理事务 所(特殊普通 合伙) 11542 专利代理师 余罡 (51)Int.Cl. G06Q 10/04(2012.01)G06N 20/00(2019.01) G06Q 10/06(2012.01) G06Q 10/00(2012.01) (56)对比文件 CN 113128839 A,2021.07.16 CN 10723 0023 A,2017.10.0 3 CN 109255484 A,2019.01.2 2 US 201908024 4 A1,2019.0 3.14 US 2021398157 A1,2021.12.23 苏生等.并行机间歇过程 生产调度的遗传局 部搜索算法. 《软件学报》 .20 06,(第12期), 牟健慧等.基 于遗传变邻域混合 算法的带交 货期的单机车间逆调度方法. 《机 械工程学报》 .2018,(第0 3期), 审查员 陈安安 (54)发明名称 基于变邻域搜索算法的生产与维修协同调 度方法和系统 (57)摘要 本发明提供一种基于变邻域搜索算法的生 产与维修协同调度方法和系统， 涉及生产与维修 协同调度技术领域。 本发明通过初始化算法的输 入参数； 根据所述输入参数随机生成一个一维向 量作为初始解； 构造变邻域搜索算法的邻域结 构， 将所述初始解输入邻域结构中进行搜索， 获 取考虑能源消耗成本线性增加的生产与维修协 同调度问题的全局最优解。 本发明在调度过程 中， 输入参数包括边际能耗成本的增长率， 考虑 能源消耗成本的增加对生产与维修进行协同调 度， 实现精准的协同调度。 同时， 采用变邻域搜索 算法来求解， 原理简单且易实现， 提高了问题求 解的精度， 进一 步实现更为精准的协同调度。 权利要求书4页 说明书10页 附图2页 CN 115081755 B 2022.12.09 CN 115081755 B 1.一种基于变邻域搜索算法的生产与维修协同调度方法， 其特 征在于， 所述方法包括： S1、 初始化算法的输入参数， 所述输入参数包括： 工件的数量 n， 机器的数量 m， 工厂单位 时间的固定成本 c0， 一次维修活动所 需的时间 tp和成本cp； 作业总的处理时间 T， 机器Mj每单 位时间的正常能耗成本 aj， 机器Mj边际能耗成本的增长率 bj； S2、 随机生成一个一维向量作 为算法的初始解， 每个所述一维向量代表一个解， 记为 X= (x1,x2,…,xn)， 其中， 每个元素的值在[0, m]内， 通过相应元素的舍入操作一个作业的分 配； ； S3、 构造变邻域搜索算法的邻域结构， 将所述初始解输入邻域结构中进行搜索， 获取考 虑能源消耗成本线性增加的生产与维修协同调 度问题的全局最优解； 所述全局最优解对应 工件加工顺序和维修活动的次数， 用于对生产与维修进行协同调度， 包括： S302a、 设定算法的执 行参数， 所述执 行参数包括当前迭代次数 t=1， 最大迭代次数 tmax； S302b、 初始化 k=1， 最大邻域结构个数 kmax=4； S302c、 判断 k≤kmax是否成立， 若成立， 用初 始解X通过邻域结构 Nk(X)进行扰动操作得到 解X′， 然后在邻域结构 Nk(X′)中进行邻域搜索得到解 X″， 进入步骤S302d； 若不成立， 进入步 骤S302e； S302d、 计算个体的适应度值， 判断最优解， 若 X″优于X， 则令X= X″， 且k=k+1， 返回步骤 S302c， 否则令 k=1， 返回步骤S3 02c； S302e、 令 t=t+1， 判断t≤tmax是否成立， 若不成立， 则进入步骤S302f， 否则返回步骤 S302b； S302f、 输出全局最优解 X及其适应度值， 以及生产和维修协同调度方案； 其中， 个体的适应度值计算方法具体包括： 按如下公式计算个 体适应度值； TC= 其中，TC表示并行机的总成本， 即个体的适应度值， Cj表示机器 Mj的成本，Zj*表示机器 Mj 上维修活动的最佳数量， Pj， k表示机器 Mj上各批次的加工时间， 其中， k=1，…，Zj*+1，c0表示 工厂单位时间的固定成本， tp和cp表示一次维修活动所 需的时间和成本， Tj表示机器 Mj上作 业总的处理时间， aj是机器Mj每单位时间的正常 能耗成本， bj是机器Mj边际能耗成本的增长 率。 2.如权利要求1所述的基于变邻域搜索算法的生产与维修协同调度方法， 其特征在于， 所述邻域结构包括： 交换邻域结构， 每个元素向下舍入进行分组， 数值相同则分为一组， 分组完成后， 随机 选择两个组， 从这两个组中分别选择一个元 素交换其在整个数组中的位置； 变异邻域结构， 随机获得一个数组 R=(r1，r2，…，ri，…，rn)， 如果ri大于变异概率 pm， 然 后让元素xi的值在[0, m]内随机生成；权　利　要　求　书 1/4 页 2 CN 115081755 B 2插入邻域结构， 选择三个不相邻的位置A、 B和C， 在数组的第一个元素之前插入A和B之 间的元素， 在数组的最后一个元 素之后插 入B和C之间的元 素； 反向邻域结构， 一次选择多个元 素， 将所选元 素按相反顺序重新 排列。 3.如权利要求1所述的基于变邻域搜索算法的生产与维修协同调度方法， 其特征在于， 所述S302d包括： d1、 输入解向量 X=(x1,x2,…,xn)； d2、 按解码规则将工件分配到相应的机器上； d3、 应用单机的启发式算法， 确定每台机器生产与维修方案； d4、 根据每台机器生产与维修方案计算每台机器的成本； d5、 根据每台机器的成本计算个 体适应度值， 适应度值 最小的个 体即为最优解。 4.如权利要求3所述的基于变邻域搜索算法的生产与维修协同调度方法， 其特征在于， 所述d3包括： 步骤1： 计算每台单机 Mj上的维修活动次数， 按以下公式计算每台单机 Mj上维修次数的 近似最佳 数量zj； 式中，c0表示工厂单位时间的固定成本， tp和cp表示一次维修活动所需的时间和成本， Tj 表示机器 Mj上作业总的处 理时间，bj是机器边际能耗成本的增长率； 式中，Zj*表示机器 Mj维修活动的最佳 数量，round( )表示取整， n表示工件数量； 步骤2： 将机器 Mj上的工件分成 Zj*+1个批； 步骤3： 按任意 顺序安排批次； 步骤4： 在相邻批次之间插 入维修活动。 5.如权利要求4所述的基于变邻域搜索算法的生产与维修协同调度方法， 其特征在于， 所述将机器 Mj上的工件分成 Zj*+1个批， 包括： 步骤2.1： 输入作业的处理时间和维修活动的次数 Zj*， 令i=1， 并且令 B1=B2=…=BZ+1=0， 表 示初始每批次的加工时间都为0; 步骤2.2： 将工件加工时间按降序排列， 获得 数组(p1,p2,…,pn)并且p1≥p2≥…≥pn； 步骤2.3： 如果 i< Zj*， 计算剩余批的平均值， 平均值=数组中剩余元素之和/空批的个 数， 进入步骤2.4， 否则进入步骤2.8； 步骤2.4： 如果数组中的首个数字大于或等于平均值， 则将首个数字作为第 i批， 从数组 中删除该 数字并更新数组， 然后令 i=i+1， 返回步骤2.3， 否则进入步骤2.5； 步骤2.5： 将数组中首个数字放入第 i批， 令Bi=Bi+首个数字， Ri=平均值‑Bi， 从数组中删 除该数字并更新 数组， 重复此操作直到 Ri小于数组中的首个数字停止， 其中 Bi表示已放入第权　利　要　求　书 2/4 页 3 CN 115081755 B 3