基于改进的NSGA-Ⅱ的采煤机械车间调度问题研究.pdf

基于改进的的采煤机械车间调度问题研究李思远(黑龙江工业学院黑龙江 鸡西)摘 要:采煤机械零件生产过程中存在种类繁多、配套效率低的问题研究者以最小化提前组件数量、延迟组件数量和组件齐套时间为目标提出改进 算法进行求解 传统的 算法存在交叉不充分、容易陷入局部最优解等问题研究者设计分段线性次序交叉采用双层基因的编码方式确保每个基因带有求解问题的全部信息改进非支配排序的序值计算方法有效减少序值计算量关键词:多目标优化车间调度分段线性次序交叉改进的 算法组件齐套中图分类号:文献标识码:文章编号:()多目标问题车间调度是影响采煤机械车间零部件生产的重要因素采煤机械零件的加工任务繁重涉及的零件种类多 采煤机械零件的调度问题不仅需要确定零件的加工顺序还要确定零件在哪台机器上加工是复杂的 问题利用智能算法优化调度问题指导车间的生产逐渐成为研究热点对企业降低生产成本提高生产效率起着重要作用 传统的车间调度主要求解单个目标最常见的优化目标是最小化最大的完工时间但实际的生产调度要考虑多个目标车间的多目标优化问题通常以完工时间、机器负载、能耗和加工成本等为主要生产指标一般情况下多目标优化问题更符合实际情况 目前经典车间调度理论的研究趋于成熟研究热点逐渐从理论转向实际制造大多数车间调度问题需要优化的多个目标是相互矛盾的一个目标的优化可能会降低其他目标的性能这种车间调度问题称为多目标优化问题 解决多目标优化问题的方法主要有两种:加权系数法与基于 的优化方法 加权系数法的系数大多数是人为给出的该方法的主观性强导致评价结果与实际不符基于 的优化方法的最大优点就是让决策者在解集中选择问题最优解因此多目标优化问题多采用基于 的优化方法 是目前最流行的基于 的优化算法之一降低了非劣前端分级遗传算法的复杂度具有收敛性好、求解速度快等优点使 成为多目标优化算法的标杆 问题描述采煤机械零件生产车间调度问题的描述如下:零件加工过程中有 道工序每道工序有数量不等的并行机 个零件按顺序加工先加工第一道工序最后加工第 道工序加工每道工序时零件可以在这道工序的任意一台并行机上加工 采煤机械零件生产车间调度拟解决的问题确定零件的加工顺序使三个目标同时达到最优 三个优化目标分别是:最大组件的齐套时间 零件在加工过程中以组件的形式齐套运输到下一道工序可有效减少产品的完工时间提前组件数量 组件提前运送到下一道工序会扩大储存区的占地面积造成资源浪费 延迟组件数量组件延迟运送下一道工序会延长产品的完工时间不能按时交货加大违约成本对于采煤机械零件的生产车间调度问题一般假设:零件在加工过程中不会受到扰动事件影响零件必须按照顺序进行加工 在任意一道工序中零件可以在任意一台机器上加工 任意一台机器在任意时刻只能加工一个零件 如果两个零件优先级相同则加工第一个零件优先级不同则优先加工等级高的零件 算法设计算法是 在 的基础上提出的主要改进了三个方面:采用快速非支配排序一方面保留了种群中最优秀的个体另一方面降低了计算的复杂程度 提出序值和拥挤度距离概念使获得的解均匀分布在整个 空间中 采用精英保留策略使获得的最优解在交叉、变异过程中得以保留提高最优解质量.基因编码为解决采煤机械零件的调度问题设计了改进的的求解算法 以延迟组件数量、组件齐套时间和提前组件数量为三个目标 编码时除了零件编号外还要考虑了零件所属的组件编号为表达零件的全部信息研究者设计了一种双层编码方式每条染色体有两层信息第一层是组件编号第二层是零件编号 算法的流程如下:首先随机产生双层基因编码的初始化种群计算每个个体的多个目标函数值计算个体的序值和拥挤距离对所有个体进行非支配排序产生第一代父代种群 父代种群通过分段交叉、变异后与子代种群合并计算合并后种群中个体的序值和拥挤距离采用精英保留策略选出子种群循环操作此步骤直到迭代次数与设定值相等时结束程序运行 改进的 算法流程图如图 所示图 改进的 算法流程图.分段变异与交叉由于编码时染色体长度与采煤机械零件生产车间加工的零件数量相等染色体的长度 过长传统的变异与交叉方法存在不充分问题因此提出了分段变异与分段交叉的方法 分段交叉方式为:将父代染色体 和 分成 段分段的长度为/在父代的每一段中选取两个点位 和 将 和 之间的数值遗传给 最后将父代 与子代 不同的数值遗传给子代 用同样的方法得到子代 分段线性次序交叉的过程如图 所示 本文中变异原理与交叉原理相同 分段变异方式为:将父代染色体 和 分段分成 段分段的长度为/在父代的每段染色体内随机选择两个点位 和 交换 和 位置数值在进化初期交叉概率与变异概率应选择较大数值防止出现未成熟就收敛的情况 在进化后期需要防止破坏最优解加快向最优解收敛交叉概率与变异概率应选择较小数值因此本文采用自适应交叉与变异图 分段线性次序交叉示意图.快速非支配排序在多目标优化问题中通常采用非支配排序的序值和拥挤距离对个体进行排序 如果个体 至少有一个目标比个体 的好且所有目标不比个体 的差则个体 支配个体 非支配排序的步骤是根据非支配关系计算每一个个体的序值序值等于 的个体是最优的再通过拥挤距离比较序值相同的个体优劣直到所有个体被排序.序值计算为保证目标空间中的解均匀分布在整个 空间需要计算每个个体的序值和拥挤距离 在 算法中设有 个目标函数 序值计算过程如下:令个体 比较个体 和其他个体的每一个目标函数值将最优个体放入支配集合 如果 中没有任何元素则定义个体 的序值为 令 利用 循环找出所有序值为 的非支配个体 删除非支配个体和支配集合 中序值为 的个体若 中没有任何元素则个体 的序值为 循环第 步直到所有个体被排序.拥挤距离计算种群中同一序值的个体通过拥挤距离计算过程如下:将序值相同的个体放在矩阵 中 比较矩阵 中个体的第 个目标函数值并按照降序排列令矩阵 中的第一个和最后一个个体的拥挤距离为无穷大 计算所有个体的拥挤距离 令 计算每个目标函数的拥挤距离 比较个体 和 所有目标的函数值得到最优解集.精英保留策略算法采用精英保留策略计算父代种群和子代种群合并后的序值和拥挤距离使获得的最优解在交叉、变异过程中保留精英保留策略的过程为:将父代种群和子代种群合并为获得更好的后代采用了双人竞赛的策略 交配池的大小设定为种群大小的一半随机选取两个选手分别计算序值和拥挤距离序值高的选手作为父代种群当两个选手具有相同的序值时选择拥挤距离大的选手当两个选手序值与拥挤距离都相同时则随机选择一个选手 采用有放回的选择方式直至选出数量与父代的大小相等 实验运行环境是在 、主频、操作系统下使用 编程实现的本文以 台机器 个零件为例包括 个组件和 种原材料 零件的加工时间是随机产生的加工时间为 改进的 算法设置为:种群大小最大迭代次数 运行程序得到的零件调度甘特图如图 所示组件调度甘特图如图 所示一样颜色的零件可组成一个组件运行改进的 算法得到 个组件的齐套时间分别为、由图 可知构成 号组件的、号零件分别在机器、上加工因此图 中 号组件中的零件加工时间重合图 零件调度甘特图 图 组件调度甘特图分别运行标准 算法和本文改进的 算法 次每个优化目标的平均值演化曲线如图和图 所示 从图 和图 中可以看出改进 算法计算的最大组件齐套时间为、提前组件个数为、延迟组件个数为 优于标准 算法计算的最大组件齐套时间、提前组件个数为、延迟组件个数为 证明改进 算法具有较强的局部搜索能力改进 算法最优解集在 代左右能搜索到远小于标准 的 代证明改进算法具有较强的全局搜索能力 图 标准迭代曲线 图 改进迭代曲线 总结传统的 算法存在交叉不充分、搜索效率低、容易陷入局部最优解等问题为解决上述问题本文提出一种基于改进 的多目标车间调度方法为表达零件的全部信息设计双层编码方式设计分段线性次序变异与交叉的方式保证充分变异与交叉改进了非支配排序的序值计算方法有效减少了序值计算的计算量采用自适应变异与交叉概率防止早熟现象加快收敛速度精英保留策略用于获得最优解集实现三个优化目标的最优组合本文旨在建立一个基于改进 的多目标车间调度模型优化三个目标 实验结果证明本文设计的算法效率和求解精度均有显著提高参考文献:陈辅斌李忠学杨喜娟.基于改进 算法的多目标柔性作业车间调度.工业工程():.姜天华.混合灰狼优化算法求解柔性作业车间调度问题.控制与决策():.程强高元杰初红艳等.基于多目标差分进化算法的机加工柔性作业车间调度.北京工业大学学报():.李颖俐李新宇高亮.混合流水车间调度问题研究综述.中国机械工程():.彭建刚刘明周张玺等.基于 优化的离散自由搜索算法求解多目标柔性作业车间调度问题.中国机械工程():.杜百岗谢永健郭钧.基于 的流水车间多品种柔性分批调度.数字制造科学():.基金项目:年度黑龙江省省属高等学校基本科研业务费项目采煤机械零件生产车间调度方法研究()作者简介:李思远()男 黑龙江鸡西人 硕士研究生助教 研究方向:智能车间调度