现代设计与先进制造技术·伍晓宇王志勇吴序一基于实虚基因座的车间调……39 要设定较小的变异概率。注意到本文的变异操作数和设备类别,其中由于模具零件的抛光工种一般 与变异基因率紧密相关,假如变异基因率为0,则均由钳工人工完成,所以表中为虚拟设备,实际为 变异操作将不进行,即此时变异概率为0,因此可从事抛光工种的钳工人数。关于设备停工时段的 以通过控制变异基因率来调整变异概率,从而实现设置,试验中定为周日24h停工,周一至周六早晨 变异概率的合理自适应性。在本算法中一般设定8:00至晚上18:00为工作时间。图4所示的是某 交叉基因率在0.10以下,然后通过生成小范围内模具加工企业生产排程后钻床设备加工工序与停 的随机数来控制变异概率。 工时段甘特图。 实验中使用从某企业获取的实际生产数据,包 4算法实验 括50套模具及其相关物料资料,500余道不同的 以上提出的改进遗传算法方案通过实验收到加工工序信息包括田优先权值表示的加工工艺路 满意的效果。表1所示的是算法实验中的设备数线、加工物料·加工工种、加工工时,通过排程选择 据包括参加实验的加工设备的工种、对应设备台加工设备、加工时段最终以总体排程长度(天)最 应军日 排程工序 停工时段 P工时键 图4加工工序与停工时段 短为寻优目标 按上述参数取值,如图5所示,其中个体序号 表1算例设备工种及类型 为1的记录为每代最短排程长度,初始化个体中最 设备数 设备类型 短排程长度14.37天,经过10代迭代运算,如图6 Milling铣削 可中断类 所示,最后排程长度优化结果为11.62天 按上述参数的基础上,改变初始群体中的个体 Drilling钴削 可中断类 数为20,进化代数为20,再次进行实验,初始化个 rinding磨削 可中断类 体中最短排程长度为12.65天,经过11代进化运 CNC数控加工 6不可中断,可切入类 算,排程长度缩短到优化结果为11.48天。当最后 13不可中断,可切入类迭代到20代时,最后的排程长度仍为11.48天 wire.cut线切割 10不可中断,可切入类 通过大量实验发现当车间各工种设备数量足 polishing抛光 可中断类 够大,而彼此相互竞争资源的工序相对少到一定程 注: polishing抛光用的设备为虚拟设备 度时,遗传算法每次迭代运算得到的适应度和排程 经过多次实验,该算法在较少遗传代数下即可长度完全相同,即任何情况下均可获得最优解,遗 快速收敛,效果明显优于一般遗传算法。发现在设传算法实际无优化作用 定遗传参数时,取初始种群个体数为12,进化群体 实际上,绝对多数模具企业平时工作量相当 个体数为10,交叉基因率P=0.42,变异基因率大,一般500人以上的模具厂每天新增的操作工序 Pm=0.09,10代内即可得到比较理想的结果,而往往接近甚至超过1000条,而每天需要调度的工 且遗传算法排程花费的时间也较少,20代内可逼序往往达到数千条(因为包含前几个工作日的工 近最优解,但花费的运算时间较大。 序),导致车间至少某些工种设备相对缺乏,这时遗 c1994-2008ChinaAcademicounalElectronicPublishingHouseallrightsreservedhttp://nwww.cnki.ner要设定较小的变异概率。注意到本文的变异操作 与变异基因率紧密相关 ,假如变异基因率为 0 ,则 变异操作将不进行 ,即此时变异概率为 0 ,因此可 以通过控制变异基因率来调整变异概率 ,从而实现 变异概率的合理自适应性。在本算法中一般设定 交叉基因率在 0. 10 以下 ,然后通过生成小范围内 的随机数来控制变异概率。 4 算法实验 以上提出的改进遗传算法方案 ,通过实验收到 满意的效果。表 1 所示的是算法实验中的设备数 据 ,包括参加实验的加工设备的工种、对应设备台 数和设备类别 ,其中由于模具零件的抛光工种一般 均由钳工人工完成 ,所以表中为虚拟设备 ,实际为 从事抛光工种的钳工人数。关于设备停工时段的 设置 ,试验中定为周日 24h 停工 ,周一至周六早晨 8 :00 至晚上 18 :00 为工作时间。图 4 所示的是某 模具加工企业生产排程后钻床设备加工工序与停 工时段甘特图。 实验中使用从某企业获取的实际生产数据 ,包 括 50 套模具及其相关物料资料 ,500 余道不同的 加工工序信息 ,包括由优先权值表示的加工工艺路 线、加工物料、加工工种、加工工时 ,通过排程选择 加工设备、加工时段 ,最终以总体排程长度(天) 最 图 4 加工工序与停工时段 短为寻优目标。 表 1 算例设备工种及类型 工种 设备数 设备类型 Milling 铣削 21 可中断类 Lathe 车削 3 可中断类 Drilling 钻削 4 可中断类 Grinding 磨削 16 可中断类 CNC 数控加工 6 不可中断 ,可切入类 EDM 电火花 13 不可中断 ,可切入类 Wire - cut 线切割 10 不可中断 ,可切入类 Polishing 抛光 13 可中断类 注 : Polishing 抛光用的设备为虚拟设备。 经过多次实验 ,该算法在较少遗传代数下即可 快速收敛 ,效果明显优于一般遗传算法。发现在设 定遗传参数时 ,取初始种群个体数为 12 ,进化群体 个体数为 10 ,交叉基因率 P ′ c = 0. 42 ,变异基因率 P ′ m = 0. 09 ,10 代内即可得到比较理想的结果 ,而 且遗传算法排程花费的时间也较少 ,20 代内可逼 近最优解 ,但花费的运算时间较大。 按上述参数取值 ,如图 5 所示 ,其中个体序号 为 1 的记录为每代最短排程长度 ,初始化个体中最 短排程长度 14. 37 天 ,经过 10 代迭代运算 ,如图 6 所示 ,最后排程长度优化结果为 11. 62 天。 按上述参数的基础上 ,改变初始群体中的个体 数为 20 ,进化代数为 20 ,再次进行实验 ,初始化个 体中最短排程长度为 12. 65 天 ,经过 11 代进化运 算 ,排程长度缩短到优化结果为 11. 48 天。当最后 迭代到 20 代时 ,最后的排程长度仍为 11. 48 天。 通过大量实验发现当车间各工种设备数量足 够大 ,而彼此相互竞争资源的工序相对少到一定程 度时 ,遗传算法每次迭代运算得到的适应度和排程 长度完全相同 ,即任何情况下均可获得最优解 ,遗 传算法实际无优化作用。 实际上 ,绝对多数模具企业平时工作量相当 大 ,一般 500 人以上的模具厂每天新增的操作工序 往往接近甚至超过 1 000 条 ,而每天需要调度的工 序往往达到数千条 (因为包含前几个工作日的工 序) ,导致车间至少某些工种设备相对缺乏 ,这时遗 ·现代设计与先进制造技术· 伍晓宇 王志勇 吴序一 基于实虚基因座的车间调 …… 93 © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net