第23卷,第 深圳大学学报理工版 Vol 23 2006年7月 JOURNAL OF SHENZHEN UN NERSITY SC IENCE AND ENGNEER NG July 文章编号:1000-2618(2006)03-0272-06 非量产模式下车间调度的改进遗传算法 吴序一,伍晓宇 深圳大学工程技术学院,深圳518060) 摘要:将遗传算法用于求解模具制造的车间调度问题.通过改进基于工序的编码方法,采用实际工 序和虚拟工序的概念,降低了遗传算法的编码难度.遗传运算中进行了基于位置交叉和互换代码变异.为 降低统计误差,分别执行了随杋选择和个体最佳选择操作.实验表明,改进后的遗传算法能够在较少的迭 代次数下,以小规模种群获得满意解 关键词:遗传算法;车间调度;模具制造 中图分类号:TP391.72 文献标识码:A 非量产模式是指按订单、小批量或单件的生产次,从而约束子层工件的工序先于父层工序加工 形式,对其研究在理论上归纳为车间调度问题.由1.2设备分类及影响 于模具制造业正在朝着精益生产和敏捷制造的方向 通常,在非量产制造过程中设备资源对加工所 发展,因此人们日益关注这种模式下的车间调度问产生的约束是最大的.一个制造系统的生产能力主 题.文献[1构建了 Prams系统,采用关键路要指设备的加工能力,因此在进行非量产模式车间 径法和工时自动安排算法等进行生产作业调度.本调度时,是以工序为基础,针对加工设备进行.根 文在 Eproms系统的基础上,提出一种改进的遗传据制造系统内协作设备资源分工的不同,即主要工 算法.该算法釆用基于工序的编码方法( operaton-种的不同,可将设备资源分类为诸如加工中心类、 based encod ings,提出实基因座和虚基因座概普通铣床类和平面磨床类等.不同工序必须在提供 念,即实际工序和虚拟工序概念,使编码方法大为对应工种的机器上进行加工.这样根据各类设备的 简化,并对该编码基因进行特定的交叉和变异操作,数量便可确定制造系统该工种加工能力的强弱,而 可在较少的迭代次数下以小规模种群获得满意解.根据总设备的数量可确定总的加工能力 在制造过程中还有一些加工由人工进行.例如 1非量产制造系统 模具制造中的组装及部分钳工加工,须建立虚拟钳 工设备.按照这个分法,将制造系统中的设备资源 1.1物料结构 分为实际设备和虚拟设备.实际设备包括CNC加工 以模具工业为代表的非量产制造,其制造产品中心和EM电火花加工机等实际存在的设备;虚拟 的物料结构有类似之处.在Epms系统中一般将设备按照工厂中从事该工作的分组资源进行定义 产品的物料结构分为两层:一为顶级产品;二为各 在生产过程中,还存在设备需要维修和定时保 种加工工件及现成标准零件、但不排除有部分较复养、工人需要下班休息等情况.因此,需要对设备 杂的产品具有多层物料结构.对于这种物料结构,资源分别设定维护时段和停工时段.根据设备加工 工艺上要求优先完成子层工件的加工后,才能进行特点的差异及其受停工时段影响的不同,可将系统 父层工件加工.系统通过建造BOM表来实现:对设备资源分为:中断类和不中断可切入类.中断类 于不同模具制品的每一个物料均有对应的D号,设备指操作过程需要人工操控、可随时中断正在进 子D号是在其父D号后加上流水号进行标识的.行的加工,且中断后的加工可在设备再次启动后继 因此,根据D号长度可判断物料在BOM表中的层续进行的一类设备,如普通的铣床和车床等均属于 收稿日期:2005-11-09,修回日期:2006-03-21 通讯作者:伍晓字(1963,男以族),深圳大学教授、博士 Email wuxy@ salco ik wu xuyi163.cm (1981-) 汉族),广东省潮州市人,深圳大学硕士研究生.Emai 201994-2009ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.http:/wwwcnki.net© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 第 23卷 , 第 3期 深圳大学学报理工版 Vol123, No13 2006年 7月 JOURNAL OF SHENZHEN UN IVERSITY SCIENCE AND ENGINEER ING July 2006 文章编号 : 100022618 (2006) 0320272206 收稿日期 : 2005211209; 修回日期 : 2006203221 作者简介 : 吴序一 (19812) , 男 (汉族 ) , 广东省潮州市人 , 深圳大学硕士研究生. E2mail: wu1xuyi@1631com 通讯作者 : 伍晓宇 (19632) , 男 (汉族 ) , 深圳大学教授、博士. E2mail: wuxy@ szu1edu1cn 非量产模式下车间调度的改进遗传算法 吴序一 , 伍晓宇 (深圳大学工程技术学院 , 深圳 518060) 摘 要 : 将遗传算法用于求解模具制造的车间调度问题. 通过改进基于工序的编码方法 , 采用实际工 序和虚拟工序的概念 , 降低了遗传算法的编码难度. 遗传运算中进行了基于位置交叉和互换代码变异. 为 降低统计误差 , 分别执行了随机选择和个体最佳选择操作. 实验表明 , 改进后的遗传算法能够在较少的迭 代次数下 , 以小规模种群获得满意解. 关键词 : 遗传算法 ; 车间调度 ; 模具制造 中图分类号 : TP 391172 文献标识码 : A 非量产模式是指按订单、小批量或单件的生产 形式 , 对其研究在理论上归纳为车间调度问题. 由 于模具制造业正在朝着精益生产和敏捷制造的方向 发展 , 因此人们日益关注这种模式下的车间调度问 题 [ 124 ] . 文献 [ 1 ]构建了 E2p rom s系统 , 采用关键路 径法和工时自动安排算法等进行生产作业调度. 本 文在 E2p rom s系统的基础上 , 提出一种改进的遗传 算法. 该算法采用基于工序的编码方法 (operation2 based encodings) [ 3 ] , 提出实基因座和虚基因座概 念 , 即实际工序和虚拟工序概念 , 使编码方法大为 简化 ,并对该编码基因进行特定的交叉和变异操作 , 可在较少的迭代次数下以小规模种群获得满意解. 1 非量产制造系统 111 物料结构 以模具工业为代表的非量产制造 , 其制造产品 的物料结构有类似之处. 在 E2p rom s系统中一般将 产品的物料结构分为两层 : 一为顶级产品 ; 二为各 种加工工件及现成标准零件. 但不排除有部分较复 杂的产品具有多层物料结构. 对于这种物料结构 , 工艺上要求优先完成子层工件的加工后 , 才能进行 父层工件加工. 系统通过建造 BOM 表来实现 : 对 于不同模具制品的每一个物料均有对应的 ID 号 , 子 ID号是在其父 ID 号后加上流水号进行标识的. 因此 , 根据 ID号长度可判断物料在 BOM表中的层 次 , 从而约束子层工件的工序先于父层工序加工. 112 设备分类及影响 通常 , 在非量产制造过程中设备资源对加工所 产生的约束是最大的. 一个制造系统的生产能力主 要指设备的加工能力 , 因此在进行非量产模式车间 调度时 , 是以工序为基础 , 针对加工设备进行. 根 据制造系统内协作设备资源分工的不同 , 即主要工 种的不同 , 可将设备资源分类为诸如加工中心类、 普通铣床类和平面磨床类等. 不同工序必须在提供 对应工种的机器上进行加工. 这样根据各类设备的 数量便可确定制造系统该工种加工能力的强弱 , 而 根据总设备的数量可确定总的加工能力. 在制造过程中还有一些加工由人工进行. 例如 模具制造中的组装及部分钳工加工 , 须建立虚拟钳 工设备. 按照这个分法 , 将制造系统中的设备资源 分为实际设备和虚拟设备. 实际设备包括 CNC加工 中心和 EDM电火花加工机等实际存在的设备 ; 虚拟 设备按照工厂中从事该工作的分组资源进行定义. 在生产过程中 , 还存在设备需要维修和定时保 养、工人需要下班休息等情况. 因此 , 需要对设备 资源分别设定维护时段和停工时段. 根据设备加工 特点的差异及其受停工时段影响的不同 , 可将系统 设备资源分为 : 中断类和不中断可切入类. 中断类 设备指操作过程需要人工操控、可随时中断正在进 行的加工 , 且中断后的加工可在设备再次启动后继 续进行的一类设备 , 如普通的铣床和车床等均属于