改进GSO算法的成套订单调度和维修联合优化.pdf

第 卷 第 期太原科技大学学报.年 月 .文章编号:()收稿日期:基金项目:国家自然科学基金()山西省自然科学基金()太原科技大学博士启动资金项目()作者简介:杨晓梅()女教授主要研究方向为复杂系统智能运维和健康管理改进 算法的成套订单调度和维修联合优化杨晓梅张宇琼李文汇官 开(.山西省人文社科重点基地:装备制造业创新发展研究中心太原.太原科技大学 经济与管理学院太原)摘 要:基于对生产调度和设备维修间相关关系的分析设计了成套订单调度和设备维修的联合策略 该策略根据故障率的大小来判定对应的设备维修活动或后续的调度任务根据该策略以加工作业顺序和预防性维修阈值为决策变量加权成套订单数最大为优化目标构建了联合决策模型 利用对调度问题特点和设备故障机理的分析设计了一个改进的萤火虫算法将其运用于求解所提出的联合决策模型并通过数值实验和灵敏度分析验证了改进算法的可行性和模型的有效性关键词:成套订单调度预防性维修萤火虫优化算法()中图分类号:文献标识码:./.随着市场竞争的激烈化和客户需求的个性化如何有效匹配客户的不同需求和生产资源成为大多数企业所关注的问题 为了提高客户满意度企业需要针对不同客户的订单需求合理安排调度方案以期按产品交货期要求进行交货 作为一个典型的生产调度问题成套订单调度问题是针对客户的不同需求研究如何充分利用有限的生产资源安排客户订单的生产任务从而制定出一个满足不同客户需求的调度方案 在实际生产过程中随着运行时间的增加设备会逐渐劣化直至故障一旦故障会带来昂贵的故障维修费用和停机损失虽然对设备进行预防性维修可以提高其可靠性但维修期间会占用原调度方案的生产时长这就会直接影响到正常的生产 因此有必要设计成套订单调度和设备维修的联合优化方法从而指导企业制定合理的调度方案和维修决策与传统调度问题相比成套订单调度问题增加了对不同客户订单交货期的约束条件其求解难度更为复杂 针对这一问题学者们从调度模型的构建、求解方法的设计等方面展开了研究 如周水银提出针对单机的成套订单调度问题以加权成套订单数最大为目标函数建立了 整数规划模型利用遗传算法对该模型进行了求解 等考虑到对于单台设备而言加工不同类型的工件时机器需要进行调整构建了基于调整时间的成套订单调度模型并设计了混合萤火虫算法对该模型进行了求解 徐震浩以加权成套订单数最大为目标研究柔性作业车间的成套订单调度问题 贾叶玲针对混合流水车间的成套订单调度问题提出启发式遗传算法进行求解这些研究虽然丰富了生产调度的理论研究成果但是并没有考虑到设备的维修活动对调度方案的影响 近年来部分学者考虑到生产调度和维修间的相关性展开了生产调度与设备维修的集成研究如 提出单机生产环境下生产调度和维修计划的联合优化模型 针对单机系统进行预测维修和生产调度的集成研究 针对劣化的生产系统建立预防性维修与生产调度集成优化模型 但是上述研究中大多针对的是单机调度环境下的维修策略并没有考虑到客户订单的需求 作为一个智能优化算法萤火虫算法因其计算速度快、易于实现近年来开始被学者们应用于生产调度领域 如夏俊红提出一种改进的 算法求解柔性作业车间/调度问题 张丽红提出一种 算法求解置换流水线调度问题 本文拟针对单机生产系统构建成套订单调度和设备维修的联合优化模型并结合成套订单调度的特点和设备的故障机理设计一个改进的萤火虫算法对该模型进行求解 成套订单调度和设备维修的集成策略.问题描述 个工件在一台机器上加工加工任务来自于 个客户的订单每个订单包含多个工件 按工艺类别可将所有工件分为 个工艺组属于不同工艺组的两个工件在加工时机器需要调整 已知所有工件的加工时间和交货期所有工件在 时刻均已到达如果某一工件的完工时间不晚于交货期那么该工件按期完成如果该订单内所有工件均在各自交货期内完工该订单成套完成为了降低设备的故障率需要对设备进行维修来改善其性能确保生产活动连续进行 在对设备进行调整时根据设备故障率的大小来判定是否对设备进行维修如果设备故障率超过预防性维修阈值则停机进行预防性维修设备维修后恢复如新进行下一道工序生产如果设备故障率没有达到预防性维修阈值无需采取维修活动系统继续生产以 个客户订单对应的 个工件的加工任务为例这 个工件按工艺类别分为 个工艺组 已知各工件的相关加工信息(如表 所示)、每个工艺组对应的机器调整时间(如表 所示)和每个订单的权重(如表 所示)假设调度序列为 当第三次调整时机器的故障率达到预防性维修阈值需要进行预防性维修活动维修时间为 对应的成套订单调度和设备维修的集成策略的甘特图如图 所示其中工件、均按时完工由于一个订单中所有工件都在其交货期内完工意味着该订单任务已经完成根据表 中的工件数据可知工件、仅仅对应订单、中一个工件的加工任务只有工件、对应订单 的全部加工任务这就说明订单 已成套完成能够满足该订单对应客户的需求 此时只有订单 成套完成且订单 的权重为.则加权成套订单数为.表 工件数据.工件号订单号工艺组加工时间交货期表 工艺组对应调整时间数据.工艺组机器调整时间.表 订单权重数据.订单号权重.4441.图 成套订单调度和设备维修集成的甘特图.假设条件()机器每次只能加工一个工件且一个工件只需在机器上加工一次工件加工过程不可中断()假设设备发生一般故障的时间服从形状参数 的 分布故障率函数().()设备进行预防性维修需要停机预防性维修后设备恢复如新()忽略维修活动后机器的准备时间()设备的性能在初始时刻处于全新状态在使用过程中其性能会发生连续退化 联合决策模型的构建.符号定义构建模型所对应的符号定义如下所示:太原科技大学学报 年 工件总数 订单总数 预防性维修阈值 预防性维修时间 工件 是否被安排在第 个位置加工 工件 的加工时间 工件 的交货期 订单 中所有工件的加工位置构成的集合 订单 的权重 订单 包含工件个数 排在第 位进行加工的工件的加工时间 排在第 位进行加工的工件的完工时间 排在第 位被加工的工件加工前机器需要的调整时间安排在第 位进行加工的工件所属的工艺组()工艺组 对应的机器调整时间 排在第 位进行加工的工件的交货期 排在第 位进行加工的工件是否按时完工 订单 是否成套完成 排在第 位进行加工的工件加工前设备是否进行了 排在第 位进行加工的工件加工前设备的故障率排在第 位进行加工的工件加工后设备的役龄排在第 位进行加工的工件加工前设备的役龄.联合决策模型根据所设计的集成策略本文以加权成套订单数最大为目标构建如下模型:.().()()()否则()()()()()()()()()()排在第 位进行加工的工件按时完工 反之()()()为目标函数即加权成套订单数最大()代表每个加工位置只能安排一个工件加工()代表每个工件对应一个加工位置()代表预防性维修阈值的取值范围()表示加工第 位工件之前是否进行.()代表相邻两个工件分属于不同工艺组时机器需要调整时间否则不需要()()分别表示排在第 位进行加工的工件的加工时间和交货期()表示排在第一个加工工件的完工时间就是它的加工时间()表示排在第二个及以后位置被加工工件的完工时间()代表第 位被加工工件在加工前设备的役龄()代表第 位被加工工件在加工后的设备役龄()表示如果排在第 位进行加工的工件按时完工取值为 否则 为.()表示如果订单 中所有工件都按时完工则该订单成套完成取值为 否则 取值为.算法描述.算法数学描述 算法是受到萤火虫通过发光完成觅食、寻偶等行为的启发而形成的基于群体搜索的一种智能优化算法 其原理为:每一只萤火虫都携带一定量的荧光素来反映自身亮度荧光素值的高低与目标函数值相关荧光素越大代表萤火虫所处位置越好好反之亦然 每只萤火虫都有自己的决策域决策域的大小决定它们邻域内个体数量萤火虫在其邻域内选择更优个体向其移动算法通过不第 卷第 期 杨晓梅等:改进 算法的成套订单调度和维修联合优化断迭代萤火虫不断移动直到所有萤火虫聚集到最亮萤火虫所在位置以实现寻优目的.求解本文模型的 算法()编码规则采用随机键的编码方法每个个体表示为一串 间随机数该个体中第 个数的相对大小对应工件 在调度序列中的相对位置 例如随机生成一串 间随机数序列.经排序后得到.对应安排加工的工件顺序为.这种编码方式能够避免后期算法操作中产生不可行个体的情况()个体邻域为空处理传统 算法中萤火虫在动态决策域内寻找较优个体组成自己的邻域集合并向其移动但是如果个体分布不均时就可能会出现个体邻域为空的情况这将导致算法收敛缓慢陷入局部最优为了防止此类现象的发生当个体邻域为空时将该个体向当前全局最优个体的方向进行移动移动步长为 之间的随机数()步长的确定步长的取值会直接影响求解的效率传统 算法中采用的步长是固定的当步长取值过大虽然全局搜索能力较强但可能导致迭代后期萤火虫位置更新跳过最优值或在最优值附近震荡的情况反之步长取值过小会使算法过早收敛不能准确得到最优值 为了快速搜索到全局最优解本文提出一种动态调整步长的改进策略:在算法迭代初期步长取值较大随着迭代次数的增加步长的取值逐渐减小 步长的具体计算公式为:()()()()其中为最大步长由初始设定 为当前迭代次数 为最大迭代次数 为固定值设.()个体间距离的确定传统 算法利用欧氏距离来判定萤火虫间的距离而成套订单调度对应需确定各工件加工位置根据编码方法可知这种距离计算方法已不再适用于本问题的求解 由于编码后所得到调度序列的位数等于其工件数则利用对个体排序后得到的调度序列间的差异来表示两个萤火虫之间的距离 假设有 个工件对其中两个个体各基因值转换后得到两个可行调度序列()().两者间的距离可由下式来确定:.()/()由于 间距离满足对称性所以 为常数本文设定 .假设现有 个待加工工件其中两个个体对应的调度序列为()和().根据公式()计算得:()/.()即得到两个个体间的距离为.所设计的 算法的流程图如图 所示图 算法流程图.太原科技大学学报 年 数值仿真为了验证本文提出的 算法的有效性以 个客户的订单需求为例进行数值仿真假设企业收到 个订单对应 个工件的加工任务这 个工件按工艺类别分为 个工艺组已知各工件的相关加工信息(如表 所示)、每个工艺组对应的机器调整时间(如表 所示)和每个订单的权重(如表 所示)将 与 两种算法进行性能对比参数设定为:.算法中步长 算法中.两种算法分别运行十次对应的仿真结果如表 所示表 工件数据.工件号订单号工艺组加工时间交货期工件号订单号工艺组加工时间交货期表 工艺组对应调整时间数据.工艺组机器调整时间.表 订单权重数据.订单号权重.表 结果对比.十次 的最优值十次 的最差值十次 的平均值十次 的方差.从表 可以看出 算法得到的最优值最差值平均值的结果均好于 算法且方差小这就说明 算法稳定性较强 图 列示了算法的迭代过程从中可以看出改进后的算法基本在 代左右收敛收敛速度较快 算法运行十次求出最优值为.预防性维修阈值 为.运行时间.此时对应的调度序列为:需要一次.对应的甘特图如图 所示其中订单、成套完成(FO J U OFT T(40(40图 算法迭代过程.44 44444441.44 图 最优解对应的甘特图.由此可知本文提出的 算法在求解不同规模问题时均能得到较好的结果而且算法收敛较快随着订单数和工件数的增多成套率有明显下降的趋势算法运行时间也明显增加为了获知不同参数的取值对优化结果的影响对参数、进行灵敏度分析观察对十次 的平均值的影响 每次只改变其中一个参数值其它参数保持不变变化范围为 、分析结果如图 所示:根据图 得到以下结论:()随着预防性维修时间 的增加平均值有减小的趋势 维修时间的增加会造成维修后加工工件的完成时间大于交货期使其不能按时完工导致其所在订单不能完成成套率降低第 卷第 期 杨晓梅等:改进 算法的成套订单调度和维修联合优化U图 参数变化对十次 的平均值的影响.()随着威布尔分布的形状参数 的增加平均值有减小的趋势 故障率达到预防性维修阈值的速度会变快所以预防性维修次数增加导致在调度序列靠后位置加工的工件的完工时间大于交货期使其不能按时完工导致该工件所在订单不能完成成套率降低()随着尺度参数 的增大平均值有变大的趋势 故障率达到预防性维修阈值的速度会变慢所以预防性维修次数减少在调度序列靠后位置加工的工件按时完工其所在订单可以成套完成成套率增加 结论本文针对成套订单调度问题考虑到设备维修活动对生产的影响以加权成套订单数最大为优化目标建立了成套订单调度和设备维修的联合决策模型并结合生产特点和设备的故障机理设计了一个改进萤火虫算法()对模型进行求解通过仿真实验验证了该模型的有效性及算法的适用性在生产过程中订单数和工件数的增加会降低企业实际的订单成套率 通过本研究有助于企业提高设备可靠性、提高客户满意度可为指导企业制定合理的调度方案和维修计划提供借鉴参考文献:.:.周水银陈荣秋.单机加权成套订单数遗传算法研究.系统工程():.():.徐震浩周畅张凌波等.柔性作业车间的成套订单调度问题.华东理工大学学报:自然科学版():.贾叶玲董绍华.基于启发式遗传算法的混合流水车间成套订单问题.计算机应用():.:.:.:.:.夏俊红郑建国.基于改进 算法的柔性作业车间/调度问题.计算机系统应用():.张丽红余世明.求解置换流水线调度问题的改进萤火虫优化算法.计算机科学():.():.太原科技大学学报 年 (.:.):.:(上接第 页)武文琪王建芳张朋飞等.一种巴氏系数改进相似度的协同过滤算法.计算机应用与软件():.喻金平刘娟巫光福等.一种改进的协同过滤算法在中小企业服务平台的研究与应用.计算机应用与软件():.():.:第 卷第 期 杨晓梅等:改进 算法的成套订单调度和维修联合优化