第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电火花加工机等实际存在的设备 ; 虚拟 设备按照工厂中从事该工作的分组资源进行定义. 在生产过程中 , 还存在设备需要维修和定时保 养、工人需要下班休息等情况. 因此 , 需要对设备 资源分别设定维护时段和停工时段. 根据设备加工 特点的差异及其受停工时段影响的不同 , 可将系统 设备资源分为 : 中断类和不中断可切入类. 中断类 设备指操作过程需要人工操控、可随时中断正在进 行的加工 , 且中断后的加工可在设备再次启动后继 续进行的一类设备 , 如普通的铣床和车床等均属于
吴序一 产模式下车间调度的改进遗传算法 此类;不中断可切入类设备主要针对数控设备,在在停工时段起始时刻暂停、在停工时段结束时刻继 完成工件装夹并输入加工程序后即可自动进行加续,计划工时不包括停工时段;若设备为不中断可 工,即使操作工下班也不影响工作完成,说明加工切入类,则该工序忽略停工时段作用,继续加工直 过程可以切入停工时段继续加工,数控加工中心和到工序完成;⑧设备维护时段内不排入任何工序 HM电火花加工机等属此类.需要注意的是,当设 备安排有维护时段时,不中断可切入类设备上的工2应用遗传算法的实现 序不可切入维护时段 1.3制造系统描述 2.1编码 一个实际的非量产模式制造系统可描述为:其 编码是遗传算法的关键,本文采用一般字符串 制造系统,按主要工种分为W类机器,每类有h编码( gene ral string encod ings)和基于工序的编码 台,在时间段内要求加工N个制品产品),第;方法,将不同的制品按整数进行编码,利用这些编 制品含有S个工件,用M表示第制品的第正件,码表示不同的工序,且组成编码串来代表一个染色 完成该工件的加工需安排ω道工序,令O,表示制体,即一个可行的调度方案.编码前要按照工艺路 线指定制品内各工序的优先级,以及指定工序所作 品的顺序调度工序集合,OP=写为任务集用的制品、工件和操作的设备工种类型编码步骤 的总工序数,不同工件加工工艺路线和时间在调度是:①给不同制品指定整数编码基因,如0,1, 前已确定.调度的任务是安排所有制品加工工序,2,…等,基因数为n表示n个制品参加调度 且满足各种约束条件,使目标函数为 ②找到参加调度制品的最大工序数m,例如,参加 f(x)=m in(m ax/ Cnni) (1)调度的制品有4个,分别有6、6、5和8道工序 其中,m∈(1,2,.…W);n∈(1.2.…);x表示那么,m=8,③随机生成编码基因,组成编码长 个完整的可行调度;C表示第m类机器第n台的度为L=nⅫm的编码串,表示一个染色体,其中 完工时间 包含m个0~(n-1).例如,按照②例产生的两个 根据工厂实际,需要考虑如下约東:①工序可行调度个体基因编码为 只能在提供对应工种的机器上完成;②对于同 B=21103032122302310232031100012133, 工件,必须按照指定的工艺路径进行加工,只有完 P=22103013302123012110302002133123 成前工序的加工才能开始后一工序;③某一时刻 图1是染色体基因编码p的生成示例图.其 台机器只能进行一个工序的加工;④工件在加中,实基因座表示制品顺序调度工序集中的实际工 工过程中从一台机器转移到另一台机器的转移时间序基因所占用的实位置,虚基因座表示为染色体编 计入加工时间;⑤各工件的加工工艺路径和每道码而加入基因所占的虚位置.它们的区别主要体现 工序的加工时间己知,且不随排序改变;⑥若工在解码时实基因座基因会被还原为原工序进入调 件还有子层物料结构,则要求先完成所有子层工件度,而虚基因座基因将被忽略.在生成染色体编 的加工后才能进行该工件的加工;⑦当计划工序的过程中无需考虑实或虚基因座,只要保证生成的 遭遇计划停工时段时,若设备为中断类,则该工序编码符合包含m个0~(n-1),从而降低编码难度 制品0顺序调度T序集(基因0}包含61序 制品1噸序调度T序集(基因)包含6T序 染色体编码P1=2110 310002 制品2顺序调度工序集(基因2)包含5工序 制M3顺序调度τ序集(基因3}包含8T序 实基因座 虚基因座 图1遗传编码示例图 Fig. I Genetic encoding 201994-2009ChinaAcademicJournalElectronicPublishingHouseAllrightsreservedhup:/www.cnki.net
© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 第 3期 吴序一 , 等 : 非量产模式下车间调度的改进遗传算法 273 此类 ; 不中断可切入类设备主要针对数控设备 , 在 完成工件装夹并输入加工程序后即可自动进行加 工 , 即使操作工下班也不影响工作完成 , 说明加工 过程可以切入停工时段继续加工 , 数控加工中心和 EDM电火花加工机等属此类. 需要注意的是 , 当设 备安排有维护时段时 , 不中断可切入类设备上的工 序不可切入维护时段. 113 制造系统描述 一个实际的非量产模式制造系统可描述为 : 其 制造系统 , 按主要工种分为 W 类机器 , 每类有 hw 台 , 在时间段 T内要求加工 N个制品 (产品 ) , 第 i 制品含有 Si个工件 , 用 M ij表示第 i制品的第 j工件 , 完成该工件的加工需安排 oij 道工序 , 令 Oi 表示制 品 i的顺序调度工序集合 , O P = ∑ N i =0 ∑ S i j =0 oij为任务集 的总工序数 , 不同工件加工工艺路线和时间在调度 前已确定. 调度的任务是安排所有制品加工工序 , 且满足各种约束条件 , 使目标函数为 f ( x) = m in (max{ Cm n } ). (1) 其中 , m ∈ (1, 2, …, W ) ; n ∈ (1, 2, …, hw ) ; x表示 一个完整的可行调度 ; Cm n表示第 m类机器第 n台的 完工时间. 根据工厂实际 , 需要考虑如下约束 : ①工序 只能在提供对应工种的机器上完成 ; ②对于同一 工件 , 必须按照指定的工艺路径进行加工 , 只有完 成前工序的加工才能开始后一工序 ; ③某一时刻 一台机器只能进行一个工序的加工 ; ④工件在加 工过程中从一台机器转移到另一台机器的转移时间 计入加工时间 ; ⑤各工件的加工工艺路径和每道 工序的加工时间已知 , 且不随排序改变 ; ⑥若工 件还有子层物料结构 , 则要求先完成所有子层工件 的加工后才能进行该工件的加工 ; ⑦当计划工序 遭遇计划停工时段时 , 若设备为中断类 , 则该工序 在停工时段起始时刻暂停、在停工时段结束时刻继 续 , 计划工时不包括停工时段 ; 若设备为不中断可 切入类 , 则该工序忽略停工时段作用 , 继续加工直 到工序完成 ; ⑧设备维护时段内不排入任何工序. 2 应用遗传算法的实现 211 编码 编码是遗传算法的关键 , 本文采用一般字符串 编码 ( general string encodings) 和基于工序的编码 方法 , 将不同的制品按整数进行编码 , 利用这些编 码表示不同的工序 , 且组成编码串来代表一个染色 体 , 即一个可行的调度方案. 编码前要按照工艺路 线指定制品内各工序的优先级 , 以及指定工序所作 用的制品、工件和操作的设备工种类型. 编码步骤 是 : ①给不同制品指定整数编码基因 , 如 0, 1, 2, …, 等 , 基因数为 n, 表示 n个制品参加调度 ; ②找到参加调度制品的最大工序数 m , 例如 , 参加 调度的制品有 4个 , 分别有 6、6、5和 8道工序 , 那么 , m = 8; ③随机生成编码基因 , 组成编码长 度为 L = n ×m 的编码串 , 表示一个染色体 , 其中 包含 m个 0 ～ ( n - 1). 例如 , 按照 ②例产生的两个 可行调度个体基因编码为 p1 = 21103032122302310232031100012133, p2 = 22103013302123012110302002133123. 图 1是染色体基因编码 p1 的生成示例图. 其 中 , 实基因座表示制品顺序调度工序集中的实际工 序基因所占用的实位置 , 虚基因座表示为染色体编 码而加入基因所占的虚位置. 它们的区别主要体现 在解码时实基因座基因会被还原为原工序进入调 度 , 而虚基因座基因将被忽略. 在生成染色体编码 的过程中无需考虑实或虚基因座 , 只要保证生成的 编码符合包含 m个 0～( n - 1) , 从而降低编码难度
深圳大学学报理工版 第23卷 2.2个体选择 传,维持不变.这种交叉方法保证子代个体从父代 个体选择运算操作以其适应度值评估为基础,中遗传了部分特性,同时又发生了一定的变化,且 理论上要求适应度值高的染色体具有较大的概率遗由于编码的优势交叉后产生的染色体完全符合非量 传到下一代.个体选择是保证遗传向着期望方向前产模式制造系统的各种约束关系,保证了子代个体 进的关键,本文进行的遗传运算包含两次选择:第的合理性与可行性 次选择进行遗传操作的个体;第二次选择遗传到2.4变异操作 下一代的个体.第一次选择采用最常见的适应度比 本文采用互换操作变异方法,具体步骤为:① 例选择法(称转轮赌或蒙特卡罗选择),第二次根据设定的遗传变异基因率P‘和染色体编码长度 选择采用最佳个体保留法,个体被选中的概率与其L,计算变异基因次数=L×n’(取整);②随机选 适应度值成正比.若设群体的大小为G.个体的适取染色体内不同位置两个基因进行互换操作;③ 应度值为F,则个体被选中的概率为 重复②直到完成①所计算的变异基因次数.例如将 q进行变异,取变异基因率Pn′=0.04.变异基因 P=F/∑Fn 1.2 (2)次数=32×0.04=1,随机选取互换位置为3和17 显然,个体的适应度值大,即选中概率P,高 则变异后的染色体为 但这种方法需要产生随机数进行选择,因此可能出 q′=21321032322102310012013100032313 现不正确的反映个体的选择,存在统计误差.本文 采取两次选择操作,在第一次选择中,群体进化的2.5解码与个体适应度值计算 每一代均随机选择多个个体进行交叉操作;第二次工的具体做法为:①将所有制品顺序调度 选择操作,采用最佳个体保留.因此,能有效克服 复位到0;②从左到右按顺序取编码基因t③根 统计误差引起劣质个体被选中的非理想结果 据取得的编码基因找到对应制品的顺序调度工序 2.3交叉操作 交叉操作是利用父代染色体通过交叉变换重新集O;④若对应位置标记Ma等于O,,则返回 组合制造出新个体,要求在尽量降低有效模式被破②,否则,继续⑤,⑤根据O,和Mak获取对应工 坏的基础上,对解空间进行改进有效的搜索以找到序信息,包括设备工种类型、计划加工工时和加工 物料信息等,同时该位置标记Mak加1;⑥根据 最优解.由于采用一般字符串编码,所以在交叉时 使用组合优化中的置换编码米进行本文采用一种根据设备工种类型到对应设备集中随机寻找可加工 操作.其步骤为:①选中两个交叉个体;②根据 时间晚于物料到达时间的最早开始设备;⑧在该 交叉基因率P。和染色体编码基因数n确定发生交设备的调度上按工序计划加工工时加入工序,当遇 叉基因的范围大小;③根据发生交叉基因范围大 到计划停工时段或维护时段时按照上文描述系统约 小随机确定交叉基因;④保证除了交又基因外的東⑦处理;⑨重复步骤②~③直到编码完所有基 其他基因位置不变,对两个个体中的交叉基因进行 因,从而产生一个完整的调度计划 交叉变换,从而得到两个新个体 通过以上解码过程,最终在数据库形成一个完 例如,选中交叉的个体为前面编码例子所产生整的调度计划,包括设备加工的开始与结束时间 的两个父代个体A和p2,选取P2=0.42.n=4等.需要注意的是,制品顺序调度工序集仅决定工 相乘取整得到交叉基因范围大小为2,随机确定交序进入调度的先后,因此后进入调度的工序,只要 叉基因为1和3,则保持基因0和2的位置不变 其约束许可,便有可能比先进入调度的工序先开始 对A和中的1和3进行交叉变换,产生新个体为加工,从而实现互相没有约束关系的同一制品子层 工件具有并行加工的可能.再通过检索调度计划的 qh=2130103232102310212013100032313 开始时间和结束时间,两者之差便是目标函数f(x) q=22101033102323013302002111323 的结果.由于调度目标是使∫(x)越小越好,而计 其中,o和2加下划线表示基因位置从父代个体遗算中的适应度值F是越大越好,遗传向着适应度值 2o1994-2009ChinacademicJournalElectronicPublishingHouse.Allrightsreserved.http:/wnwcnkiner
© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 274 深圳大学学报理工版 第 23卷 212 个体选择 个体选择运算操作以其适应度值评估为基础 , 理论上要求适应度值高的染色体具有较大的概率遗 传到下一代. 个体选择是保证遗传向着期望方向前 进的关键 , 本文进行的遗传运算包含两次选择 : 第 一次选择进行遗传操作的个体 ; 第二次选择遗传到 下一代的个体. 第一次选择采用最常见的适应度比 例选择法 (又称转轮赌或蒙特卡罗选择 ) , 第二次 选择采用最佳个体保留法. 个体被选中的概率与其 适应度值成正比. 若设群体的大小为 G, 个体 i的适 应度值为 Fi , 则个体 i被选中的概率为 Pi = Fi /∑ G n =1 Fn , n = 1, 2, …, G. (2) 显然 , 个体的适应度值大 , 即选中概率 Pi 高. 但这种方法需要产生随机数进行选择 , 因此可能出 现不正确的反映个体的选择 , 存在统计误差. 本文 采取两次选择操作 , 在第一次选择中 , 群体进化的 每一代均随机选择多个个体进行交叉操作 ; 第二次 选择操作 , 采用最佳个体保留. 因此 , 能有效克服 统计误差引起劣质个体被选中的非理想结果. 213 交叉操作 交叉操作是利用父代染色体通过交叉变换重新 组合制造出新个体 , 要求在尽量降低有效模式被破 坏的基础上 , 对解空间进行改进有效的搜索以找到 最优解. 由于采用一般字符串编码 , 所以在交叉时 使用组合优化中的置换编码来进行. 本文采用一种 改进的基于位置交叉 PX的交叉方法 [ 2 ]来进行交叉 操作. 其步骤为 : ①选中两个交叉个体 ; ②根据 交叉基因率 Pc ′和染色体编码基因数 n, 确定发生交 叉基因的范围大小 ; ③根据发生交叉基因范围大 小随机确定交叉基因 ; ④保证除了交叉基因外的 其他基因位置不变 , 对两个个体中的交叉基因进行 交叉变换 , 从而得到两个新个体. 例如 , 选中交叉的个体为前面编码例子所产生 的两个父代个体 p1 和 p2 , 选取 Pc ′= 0142, n = 4, 相乘取整得到交叉基因范围大小为 2, 随机确定交 叉基因为 1和 3, 则保持基因 0和 2的位置不变 , 对 p1和 p2中的 1和 3进行交叉变换 , 产生新个体为 q1 = 21301032322102310212013100032313, q2 = 22101033102323012330102002111323. 其中 , 0和 2加下划线表示基因位置从父代个体遗 传 , 维持不变. 这种交叉方法保证子代个体从父代 中遗传了部分特性 , 同时又发生了一定的变化 , 且 由于编码的优势交叉后产生的染色体完全符合非量 产模式制造系统的各种约束关系 , 保证了子代个体 的合理性与可行性. 214 变异操作 本文采用互换操作变异方法 , 具体步骤为 : ① 根据设定的遗传变异基因率 Pm ′和染色体编码长度 L, 计算变异基因次数 =L ×Pm ′(取整 ) ; ②随机选 取染色体内不同位置两个基因进行互换操作 ; ③ 重复 ②直到完成 ①所计算的变异基因次数. 例如将 q1 进行变异 , 取变异基因率 Pm ′= 0104, 变异基因 次数 = 32 ×0104∆ 1, 随机选取互换位置为 3和 17, 则变异后的染色体为 q1 ′= 213 2 103232210231 0 012013100032313. 215 解码与个体适应度值计算 解码的具体做法为 : ①将所有制品顺序调度 工序集 Oi ( i = 0, 1, …, N - 1) 对应的位置标记 Ma rki 复位到 0; ②从左到右按顺序取编码基因 i; ③根 据取得的编码基因 i找到对应制品的顺序调度工序 集 Oi; ④若对应位置标记 Marki 等于 Oi , 则返回 ②, 否则 , 继续 ⑤; ⑤根据 Oi和 Marki获取对应工 序信息 , 包括设备工种类型、计划加工工时和加工 物料信息等 , 同时该位置标记 Marki 加 1; ⑥根据 加工物料信息获取物料约束与物料到达时间 ; ⑦ 根据设备工种类型到对应设备集中随机寻找可加工 时间晚于物料到达时间的最早开始设备 ; ⑧在该 设备的调度上按工序计划加工工时加入工序 , 当遇 到计划停工时段或维护时段时按照上文描述系统约 束 ⑦处理 ; ⑨重复步骤 ②～⑧直到编码完所有基 因 , 从而产生一个完整的调度计划. 通过以上解码过程 , 最终在数据库形成一个完 整的调度计划 , 包括设备加工的开始与结束时间 等. 需要注意的是 , 制品顺序调度工序集仅决定工 序进入调度的先后 , 因此后进入调度的工序 , 只要 其约束许可 , 便有可能比先进入调度的工序先开始 加工 , 从而实现互相没有约束关系的同一制品子层 工件具有并行加工的可能. 再通过检索调度计划的 开始时间和结束时间 , 两者之差便是目标函数 f ( x) 的结果. 由于调度目标是使 f ( x) 越小越好 , 而计 算中的适应度值 F是越大越好 , 遗传向着适应度值
吴序一 非量产模式下车间调度的改进遗传算法 F高的方向移动 26算法流程 3算法实践分析 综合上述,本文提出的应用于非量产模式下车 间调度的改进遗传算法流程,如图2 在Epms系统中,将以上提出的算法嵌入到 系统的车间调度模块中,收到满意效果.下面以16 算法开始 台8类设备组成的制造系统和截取自生产实例数据 遗传编码 的3个制品部分工序包括6个物料46道工序), 来说明该方法的有效性 初始化:产生初始群体 表1是算例中非量产制造系统设备的主要工 选择个体进行遗传操作 种、设备类型和停工时段等信息,工种编号在系统 中不直接显示.表2表示参加调度的制品物料及其 交叉操作 对应的加工工艺和加工工时.括号外的加工顺序工 种编号对应表1的工种编号,以此决定该工序在哪 变异操作 类设备上进行加工 解码操作 图3是算例的计算结果界面及甘特图.经多次 实验,该算法在较少遗传代数下即可改进收敛.该 个体适应度值评估并从遗传 操作前后两个群体中选择最 系统还可用于典型调度问题的调度实验,通过对标 优个体组成下一代群 准pb-shop调度问题FI6进行20次随机调度实 验,发现在设定简单参数(初始种群个体数16, 满足中止条件 进化群体个体数12,交叉基因率P′=0.42.变异 基因率P′=0.09)10代内即可得到次优解57或 算法结束 58,20代内可得到最优解55在本算例中,设定 遗传参数:初始种群个体数20,进化群体个体数 图2流程示意图 12,交叉基因率P′=0.42.变异概率P。′=0.09 Fg. 2 Flow chart of the a lgor ithm 20次随机实验均在20代内得到最优解 表1算例使用的加工工序集 Table 1 O pera tin set in the exam ple 设备代号 主要工种 工种编 设备类型 CNC T. CNC T2 CNC 不中断可切入类 DR TI DR 12 Drilling钻削 中断类 EDM TI, EM 12 HM电火花 不中断可切入类 LA TI, LA T2 Late车削 中断类 Polishing抛光 中断类 SG TI SG TI Grind ing磨削 中断类 SM TI SM T Milling铣削 中断类 WC TI WC TI wie.cut慢走丝线切割8不中断可切入类 注:设置周一至周六80~18W为工作时间,其余时间为停工时段 201994-2009ChinaacademicJOurnalElectromicPublishingHousedllrightsreservedhp:/www.cnki.ner
© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 第 3期 吴序一 , 等 : 非量产模式下车间调度的改进遗传算法 275 F高的方向移动. 216 算法流程 综合上述 , 本文提出的应用于非量产模式下车 间调度的改进遗传算法流程 , 如图 2. 图 2 流程示意图 Fig12 Flow chart of the a lgor ithm 3 算法实践分析 在 E2p rom s系统中 , 将以上提出的算法嵌入到 系统的车间调度模块中 , 收到满意效果. 下面以 16 台 8类设备组成的制造系统和截取自生产实例数据 的 3个制品部分工序 (包括 6个物料 46道工序 ) , 来说明该方法的有效性. 表 1是算例中非量产制造系统设备的主要工 种、设备类型和停工时段等信息 , 工种编号在系统 中不直接显示. 表 2表示参加调度的制品物料及其 对应的加工工艺和加工工时. 括号外的加工顺序工 种编号对应表 1的工种编号 , 以此决定该工序在哪 类设备上进行加工. 图 3是算例的计算结果界面及甘特图. 经多次 实验 , 该算法在较少遗传代数下即可改进收敛. 该 系统还可用于典型调度问题的调度实验 , 通过对标 准 job2shop调度问题 FT06 [ 2 ]进行 20次随机调度实 验 , 发现在设定简单参数 (初始种群个体数 16, 进化群体个体数 12, 交叉基因率 Pc ′= 0142, 变异 基因率 Pm ′= 0109) 10代内即可得到次优解 57或 58, 20代内可得到最优解 55. 在本算例中 , 设定 遗传参数 : 初始种群个体数 20, 进化群体个体数 12, 交叉基因率 Pc ′= 0142, 变异概率 Pm ′= 0109. 20次随机实验均在 20代内得到最优解. 表 1 算例使用的加工工序集 Table 1 O pera tion set in the exam ple 设备代号 主要工种 工种编号 设备类型 CNC_T1 , CNC_T2 CNC 1 不中断可切入类 DR_T1 ,DR_T2 D rilling钻削 2 中断类 EDM_T1, EDM_T2 EDM电火花 3 不中断可切入类 LA_T1, LA_T2 Lathe车削 4 中断类 PL_T1, PL_T2 Polishing抛光 5 中断类 SG_T1, SG_T1 Grinding磨削 6 中断类 SM_T1, SM_T1 M illing铣削 7 中断类 WC_T1, WC_T1 W ire - cut慢走丝线切割 8 不中断可切入类 注 :设置周一至周六 8∶00～18∶00为工作时间 ,其余时间为停工时段
深圳大学学报理工版 第23卷 表2工件加工工艺顺序及工时 Ta ble 2 Processing sequence and work ig hours of workp eces 制品编号 物料工件 加工顺序及工序编号括号内为加工工时) CORE料1.001 7(55)4(43)1(44)3(65)6(56)2(4)5(6) SAT036605CORE占料1-0097(36)4(35)1(34)3(53)6(6)2(24)5(5) 7(56)4(46)1(42)8(62)3(62)6(52)2(26)5(6) 模料2-201 7(3.6)4(36)1(36)8(6)3(56)6(48)2(4)5(7) DCH006505 E61N09 7(4)4(34)6(48)1(43)3(48)8(48)2(2)5(6) E61NO8 7(43)4(32)6(46)1(46)3(6)8(5)2(3)5(73) 程工作算|信第工作解入世教费管理 起0年月日年月日)排.日 缺是工作 工序列表甘特停工列表 停工时段 E61N09 □C0RE料1-001 E61NOT CORE 1-101 CORE占料1-009 模料2-201 图3调度结果界面及甘特图 Fi. 3 Scheduling result and its gantt chart 参考文献 结语 [1]伍晓宇,陈锦盛.一个面向制造业的生产作业计划调 度系统[J]中国机械工程,2002,13(16):1423 本文提出的非量产模式下车间调度的改进遗传 1426 算法,具有编码简单,收敛迭代次数少,全局搜索2]王凌车间调度及其遗传算法M1北京:清华大 能力强等优点,实践表明,该算法可有效解决非量 学出版社 产模式下的实际调度问题,节省设备等待时间.因 [3] Cheng r,GenM, Tsumura Y.遗传算法求解作业车间 调度问题的研究[J]计算机与工业工程,199,30 遗传的过程适应度值函数只是遗传方向的一个标 (4):983-997(文版) 准,通过设计不同的优化目标函数,该算法可引进4]廖仁,陈庆新,毛宁。模具虚拟企业项目调度遗 实现其他目标,甚至多目标的优化调度 传算法研究[J]计算机集成制造系统,2004,10 o1994-2009 China Academic ournal Electronic Publishing House. All rights reserved. hutp: //nnw cnkiner
© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 276 深圳大学学报理工版 第 23卷 表 2 工件加工工艺顺序及工时 Table 2 Processing sequence and work ing hours of workp ieces 制品编号 物料工件 加工顺序及工序编号 (括号内为加工工时 ) SAT036605 CORE料 1 - 001 7 (5. 5) 4 (4. 3) 1 (4. 4) 3 (6. 5) 6 (5. 6) 2 (4) 5 (6) SAT036605 CORE占料 1 - 009 7 (3. 6) 4 (3. 5) 1 (3. 4) 3 (5. 3) 6 (6) 2 (2. 4) 5 (5) SAT036505 CORE 1 - 101 7 (5. 6) 4 (4. 6) 1 (4. 2) 8 (6. 2) 3 (6. 2) 6 (5. 2) 2 (2. 6) 5 (6) SAT036505 模料 2 - 201 7 (3. 6) 4 (3. 6) 1 (3. 6) 8 (6) 3 (5. 6) 6 (4. 8) 2 (4) 5 (7) DCH006505 E61N09 7 (4) 4 (3. 4) 6 (4. 8) 1 (4. 3) 3 (4. 8) 8 (4. 8) 2 (2) 5 (6) DCH006505 E61N08 7 (4. 3) 4 (3. 2) 6 (4. 6) 1 (4. 6) 3 (6) 8 (5) 2 (3) 5 (7. 3) 图 3 调度结果界面及甘特图 Fig13 Scheduling result and its gan tt chart 结 语 本文提出的非量产模式下车间调度的改进遗传 算法 , 具有编码简单 , 收敛迭代次数少 , 全局搜索 能力强等优点 , 实践表明 , 该算法可有效解决非量 产模式下的实际调度问题 , 节省设备等待时间. 因 遗传的过程适应度值函数只是遗传方向的一个标 准 , 通过设计不同的优化目标函数 , 该算法可引进 实现其他目标 , 甚至多目标的优化调度. 参考文献 : [ 1 ] 伍晓宇 , 陈锦盛. 一个面向制造业的生产作业计划调 度系统 [ J ]. 中国机械工程 , 2002, 13 ( 16 ) : 14232 1426. [ 2 ] 王 凌. 车间调度及其遗传算法 [M ]. 北京 : 清华大 学出版社 , 2003. [ 3 ] Cheng R, Gen M, Tsujimura Y. 遗传算法求解作业车间 调度问题的研究 [J ]. 计算机与工业工程 , 1996, 30 (4) : 9832997 (英文版 ). [ 4 ] 廖 仁 , 陈庆新 , 毛 宁. 模具虚拟企业项目调度遗 传算法研究 [ J ]. 计算机集成制造系统 , 2004, 10 (7) : 8152819
吴序一 非量产模式下车间调度的改进遗传算法 277 Abstract:1000-2618(2006)03-0277EA m proved genetic a gor ithm for job-shop scheduling wUXu-yiandwUXio-yu College of Engineering and Technobgy Shenzhen University pr China Abstract: An mp oved genetic algorithm for pb-shop scheduling in mould manfacture was p resented The camputa- ton comp lexity of operation-based encoding me thod was reduced by app lying the real and virtual operation Two dif- ferent se lec ton operations, i.e Roulette Wheel selection and best string selection, are used for reduc ing the statisti cal error The traditional positon exchange crossover and swap mutation are perfomed iteratively The expermental results have demonstrated that the perfomance is desirable with less iterations and maller populaton Key words: genetic algorithm; pb-shop scheduling, mould manfacture References [1 WU Xiao-yu, CHEN Jin-sheng Research on pnoduction shop scheduling problem s using genetic algorithms [J p lann ing controlling system based on manufacturing Computer Industrial Engineering, 1996, 30(4):983 J. China Mechanical Engineering, 3(16) 1423-1426( in Chinese) [4LAO Ren, CHEN Qing-xin, MAO N ing Genetic algo- [2] WANG Ling Job-shop Scheduling with Genetic Algorithms rithm for resource-constrained pmject scheduling [J] [M. Beijing Tsinghua University Press, 2003( in Chi- Camputer Itegrated Manufacturing Systems, 2004, 10 (7):815-819( in Chinese) [3 Cheng R, Gen M, Tsujmura Y A tutrial survey of pb- 中文责编:坪梓;英文责编:雨辰】 书讯 維子标签原理与应用》受到读者好评 电子标签因其体量小、超薄、柔韧性好、可植入多种材料内部的特性和其可读取的功能,广泛 应用于射频识别(RFD)领域.电子标签、读写器、天线和应用软件构成的RFD系统直接与相应 的管理信息系统相连。每一件物品都可以被准确地跟踪,这种全面的信息管理系统能为客户带来诸 多利益,电子标签基于低成本的设计和制造工艺,可广泛用于工业生产和日常生活的各个方面.为 此,电子标签的研究和使用受到社会各界关注.2006年初,我国第一部系统介绍电子标签原理、开 发、应用技术和解决方案的专著—子标签原理与应用》,由深圳大学信息工程学院纪震教授 等编著,西安电子科技大学出版社正式出版。该书一经问世,即受到读者好评.全书42万字,分9 个章节及若干附录.作者深入浅出地介绍了电子标签技术的基本原理和主要应用,翔实阐述了电子 标签的物理基础和允许使用的无线电规范,电子标签的信息处理技术以及安全性,国际标准ⅣO/ 正C15693和国际标准O/正C143,电子标签在物流、身份认证和智能交通系统等在多个领域的 应用.书中光盘附带大量电子标签的资料、标准和应用软件,适合高校、科研院所以及开发各种电 子标签应用系统的工程技术人员阅读 (小溪) o1994-2009ChinaAcademicJournalElectronicPublishingHouseAllrightsreservedhttp://nw.cnki.ner
© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 第 3期 吴序一 , 等 : 非量产模式下车间调度的改进遗传算法 277 Abstract: 100022618( 2006) 03202772EA Improved genetic a lgor ithm for job2shop scheduling W U Xu2y i and W U Xiao2yu College of Engineering and Technology Shenzhen University Shenzhen 518060 P. R. China Abstract: An imp roved genetic algorithm for job2shop scheduling in mould manfacture was p resented. The computa2 tion comp lexity of operation2based encoding method was reduced by app lying the real and virtual operation. Two dif2 ferent selection operations, i1e. RouletteWheel selection and best string selection, are used for reducing the statisti2 cal error. The traditional position exchange crossover and swap mutation are performed iteratively. The experimental results have demonstrated that the performance is desirable with less iterations and smaller population. Key words: genetic algorithm; job2shop scheduling; mould manfacture References: [ 1 ] WU Xiao2yu, CHEN Jin2sheng. Research on p roduction p lanning & controlling system based on manufacturing [J ]. China Mechanical Engineering, 2002, 13 ( 16 ) : 142321426 ( in Chinese). [ 2 ] WANG L ing. Job2shop Scheduling with Genetic A lgorithms [M ]. Beijing: Tsinghua University Press, 2003 ( in Chi2 nese). [ 3 ] Cheng R, Gen M, Tsujimura Y. A tutorial survey of job2 shop scheduling p roblems using genetic algorithms [ J ]. Computer & Industrial Engineering, 1996, 30 ( 4 ) : 9832 997. [ 4 ] L IAO Ren, CHEN Q ing2xin, MAO N ing. Genetic algo2 rithm for resource2constrained p roject scheduling [ J ]. Computer Integrated Manufacturing System s, 2004, 10 (7) : 8152819 ( in Chinese). 【中文责编 : 坪 梓 ; 英文责编 : 雨 辰 】 ·书 讯 · 《电子标签原理与应用 》受到读者好评 电子标签因其体量小、超薄、柔韧性好、可植入多种材料内部的特性和其可读取的功能 , 广泛 应用于射频识别 (RFID) 领域. 电子标签、读写器、天线和应用软件构成的 RFID系统直接与相应 的管理信息系统相连. 每一件物品都可以被准确地跟踪 , 这种全面的信息管理系统能为客户带来诸 多利益 , 电子标签基于低成本的设计和制造工艺 , 可广泛用于工业生产和日常生活的各个方面. 为 此 , 电子标签的研究和使用受到社会各界关注. 2006年初 , 我国第一部系统介绍电子标签原理、开 发、应用技术和解决方案的专著 ———《电子标签原理与应用 》, 由深圳大学信息工程学院纪震教授 等编著 , 西安电子科技大学出版社正式出版. 该书一经问世 , 即受到读者好评. 全书 42万字 , 分 9 个章节及若干附录. 作者深入浅出地介绍了电子标签技术的基本原理和主要应用 , 翔实阐述了电子 标签的物理基础和允许使用的无线电规范 , 电子标签的信息处理技术以及安全性 , 国际标准 ISO / IEC 15693和国际标准 ISO / IEC 14443, 电子标签在物流、身份认证和智能交通系统等在多个领域的 应用. 书中光盘附带大量电子标签的资料、标准和应用软件 , 适合高校、科研院所以及开发各种电 子标签应用系统的工程技术人员阅读. (小 溪 )
