2008年4月中国制造业信息化第37卷第7期 基于实虚基因座的车间调度遗传算法 伍晓宇1,王志勇2,吴序一2 (1,.深圳大学机电与控制工程学院广东深圳518060 (2.深圳市标准技术研究院,广东深圳518033) 摘要:提出了实基因座和前、后虚基因座的概念,能够很好地表达生产排程时制品之间的优先级 别以及加工工艺路线,并由此构建了面向车间生产的实用遗传算法。该算法具有编码简单、小群 体进化、快速收敛代数少、全局搜索能力强等优点,可以有效解决生产车间的排程问题。 关键词:车间调度;生产排程;遗传算法;优化 中图分类号:TP391.72文献标识码:A文章编号:1672-1616(2008)07-0036-05 1问题描述 2实、虚基因座与算法构建 目前将遗传算法应冂于Job-Shop类车间调2.1编码方案 度的研究已取得了很多进展,但实用的排程调度算 编码问题是实际遗传算法的首要和关键问题, 法或系统仍然比较少见。主要是因为这类问题模遗传算法的编码技术必须考虑“染色体″的合法性 型繁多,而且计算复杂性理论表明多数的排程问题可行性、有效性以及对问题解空间表征的完全性 都属于NP难问题,搜索目标的解涉及解空间的 本文采用一种字符串编码与基于工序的编码 组合爆炸,尤其对于实际问题更加难以解决 相结合的方法,就是将不同的制品按整数进行编 遗传算法在计算过程中用适应度值评估来代码然后利用这些编码表示不同的工序组成编码串 替目标函数的计算,适应度值可以理解为生物个体来代表一个染色体,即一个可行的调度方案。要求 对环境的适应程度,用来评估生物群体中每个个体编码之前要按照工艺路线指定制品内各工序的优 适应环境所表现出的不同生命力,从而决定其遗传先级,以及指定工序所作用的制品、物料和操作的 机会的大小 设备工种类型 制造系统按主要工种分为W类机器,每类有 以下为2个可行调度个体的基因编码: h台,在一段时间范围T内要求加工N个制品位产 品,第i制品含有S个物料工件,用M表示第i P2=22103013302123012110302002133123 制品的第j物料工件,完成该物料工件的加工需要 图1所示的是染色体基因编码p1的生成示 安排o道工序,令O表示制品的工序集,OP=例。为了更好地表达作者提出了遗传编码方案,本 文提出了实、虚基因座的概念。实基因座表示制品 2为任务集的总工序数,不同的物料工件顺序调度工序集中的实际工序所占用的实位置,虚 加工工艺路线和加工工时各不相同但在排程前已基因座表示为了简化染色体编码而加入的虚位置 确定21,排程任务是安排所有制品的加工工序的解码操作过程中仅实基因座基因会被解码为原工 调度顺序,在满足各种约束条件的前提下求解目标序进入调度。 函数 虚基因座可以出现在染色体编码前后2部分 f(x)=min( ∈(1,2,…,w),n∈(1,2,… Cmni) 让我们分别称其为前虚基因座和后虚基因座。所 式中:x表示一个完整的可行调度:C。表示第m以染色体编码的构成为前虚基因座+实基因座 类机器、第n台的完工时间 后虚基因座。 它们在染色体编码中的作用分别如下 a.前虚基因座。它是为了反映制品之间的优 收稿日期:2007-12-24 作者简介:伍晓宇(1963-),男,四川仁寿人,深圳大学教授,博士,主要研究方向为 CADI CAM、网络协同制造 21994-2008ChinaaCademicJournalElectronicpUblishingHouseAllrightsreservedhttp://nn:.cnkiner
基于实虚基因座的车间调度遗传算法 伍晓宇1 ,王志勇2 ,吴序一2 (11 深圳大学 机电与控制工程学院 ,广东 深圳 518060) (21 深圳市标准技术研究院 ,广东 深圳 518033) 摘要 :提出了实基因座和前、后虚基因座的概念 ,能够很好地表达生产排程时制品之间的优先级 别以及加工工艺路线 ,并由此构建了面向车间生产的实用遗传算法。该算法具有编码简单、小群 体进化、快速收敛代数少、全局搜索能力强等优点 ,可以有效解决生产车间的排程问题。 关键词 :车间调度 ;生产排程 ;遗传算法 ;优化 中图分类号 :TP391. 72 文献标识码 :A 文章编号 :1672 - 1616( 2008) 07 - 0036 - 05 1 问题描述 目前将遗传算法应用于 Job - Shop 类车间调 度的研究已取得了很多进展 ,但实用的排程调度算 法或系统仍然比较少见。主要是因为这类问题模 型繁多 ,而且计算复杂性理论表明多数的排程问题 都属于 NP 难问题[1 ] ,搜索目标的解涉及解空间的 组合爆炸 ,尤其对于实际问题更加难以解决。 遗传算法在计算过程中用适应度值评估来代 替目标函数的计算 ,适应度值可以理解为生物个体 对环境的适应程度 ,用来评估生物群体中每个个体 适应环境所表现出的不同生命力 ,从而决定其遗传 机会的大小。 制造系统按主要工种分为 W 类机器 ,每类有 hw 台 ,在一段时间范围 T 内要求加工N 个制品(产 品) ,第 i 制品含有 S i 个物料工件 ,用 M ij 表示第 i 制品的第 j 物料工件 ,完成该物料工件的加工需要 安排 oij 道工序 ,令 Oi 表示制品 i 的工序集 , O P = ∑ N i = 0 ∑ S i j = 0 oij 为任务集的总工序数 ,不同的物料工件 加工工艺路线和加工工时各不相同但在排程前已 确定[2 ] ,排程任务是安排所有制品的加工工序的 调度顺序 ,在满足各种约束条件的前提下求解目标 函数 : f ( x) = min ( max m ∈(1 ,2 , …, w) , n ∈(1 ,2 , …, h w ) { Cm n}) 式中 : x 表示一个完整的可行调度; Cm n 表示第 m 类机器、第 n 台的完工时间。 2 实、虚基因座与算法构建 2. 1 编码方案 编码问题是实际遗传算法的首要和关键问题 , 遗传算法的编码技术必须考虑“染色体”的合法性、 可行性、有效性以及对问题解空间表征的完全性。 本文采用一种字符串编码与基于工序的编码 相结合的方法 ,就是将不同的制品按整数进行编 码 ,然后利用这些编码表示不同的工序组成编码串 来代表一个染色体 ,即一个可行的调度方案。要求 编码之前要按照工艺路线指定制品内各工序的优 先级 ,以及指定工序所作用的制品、物料和操作的 设备工种类型。 以下为 2 个可行调度个体的基因编码 : p1 = 21103032122302310232031100012133 p2 = 22103013302123012110302002133123 图 1 所示的是染色体基因编码 p1 的生成示 例。为了更好地表达作者提出了遗传编码方案 ,本 文提出了实、虚基因座的概念。实基因座表示制品 顺序调度工序集中的实际工序所占用的实位置 ,虚 基因座表示为了简化染色体编码而加入的虚位置。 解码操作过程中仅实基因座基因会被解码为原工 序进入调度。 虚基因座可以出现在染色体编码前后 2 部分 , 让我们分别称其为前虚基因座和后虚基因座。所 以染色体编码的构成为 :前虚基因座 + 实基因座 + 后虚基因座。 它们在染色体编码中的作用分别如下 : a . 前虚基因座 。它是为了反映制品之间的优 收稿日期 :2007 - 12 - 24 作者简介 :伍晓宇(1963 - ) ,男 ,四川仁寿人 ,深圳大学教授 ,博士 ,主要研究方向为 CAD/ CAM、网络协同制造。 63 2008 年 4 月 中国制造业信息化 第 37 卷 第 7 期 © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
现代设计与先进制造技术·伍晓宇王志勇吴序一基于实虚基因座的车间调…… 制品0顺序调度工序集(基因0)包含4 染色体编码P=21103032122302310232031100012 制品2顺序调度工序集(基因2)包含5工序 制品3顺序调度工序集(基因3)包含8工序 实基因座 ·前虚基因座 后虚基因座 图1遗传编码 先级别而加入的虚位置节点,是制品排程时的延迟论上可以得到最优解。 长度。最紧急的制品其延迟长度为零,不存在前虚2.2遗传操作 基因座节点,它有权优先竞争加工资源。而前虚基 本文采用一种改进的基于位置交叉的方法来 因座节点越多,表示制品起始排程延迟长度越大,进行编码交叉。具体做法如下 由于其他制品的实基因座节点可以插入其间,这样 步骤1,通过上述个体选择办法选中2个交叉 相对这些制品前虚基因座节点所对应的制品越靠个体 后参与加工资源的竞争。所以,前虚基因座可以反 步骤2,根据预先设定的交叉基因率P和染 映制品之间的竞争资源的优先级别 色体编码基因数n确定发生交叉基因的范围大小 b实基因座。实基因座节点表示各制品的实为n×P(取整) 际加工工序以及这些加工工序构成的加工工艺链 步骤3,根据发生交叉基因范围大小随机确定 实基因座节点数就是制品的工序数目。在构建统交叉基因 的染色体编码时,各制品实基因座和虚基因座节 步骤4,保证除了交叉基因外的其他基因位置 点相互穿插形成一条单行队列这一队列也反映了不变遗传到下一代,对2个个体中的交叉基因进 制品内和制品之间工序的排程顺序,即抢占加工资行交叉变换,从而得到2个子代新个体 源的前后顺序。需要指出的是,这一顺序并不是排 例如选中交叉的个体为前面编码例子所产生 程完成后工序的前后顺序,也就是说先进入排程的2个个体p1和p2,P=0.42,n=4,取整后交 的不一定获得较早的开工时间 叉基因范围大小为2个,随机确定交叉基因为1,3, c后虚基因座。它是为了染色体编码而加入则保持基因0,2的位置不变,对p1和p2中的1,3 基因所占的虚位置。由于各制品存在不同长度的进行交叉变换,产生新个体如图2所示,其中0,2 前虚基因座和实基因座为保证总的染色体编码长加下划线表示位置从父代遗传维持不变。这种交 度一致取各制品中前虚基因座+实基因座长度最叉方法保证子代个体从父代中遗传了部分特性同 大值为统一长度其他制品编码尾部的不足部分用时又发生了一定的变化,且由于编码的优势交叉后 后虚基因座节点补足 产生的子代染色体完全符合制造系统的各种约束 染色体编码步骤如下 关系,保证了子代个体的合法性与可行性 步骤1,给不同的制品指定整数编码基因,如 父代个体 0,12等,基因数为n,表示有n个制品参加排程 P2221030133212301211030200213323 步骤2,根据不同制品的优先权值,生成数目 位置遗传基因0.2 不等的前虚基因座节点 子代个体4=2130103232210231021201310002313 42221910331923230123301020021123 步骤3,找到参加排程的制品的前虚基因座+ 实基因座长度(工序长度)最大值m,例如参加排 图2交叉操作 程的制品有4个,它们的前虚基因座和实基因座长 变异操作是模仿生物进化过程中染色体上基因 度分别为2和4.0和6.0和5及0和8,那么m就发生的突变现象,从而使染色体的结构和某些性状 等于8 发生相应的突变。在遗传算法中引入变异操作可以 步骤4,随机加入编码基因组成编码长度为使算法具有局部的随机搜索能力加强算法的搜索 m的编码串表示一个染色体 能力避免陷入局部最优,同时维持群体的多样性 经过分析该编码方法就可行性而言编码空间本文采用一种互换操作变异方法,具体做法如下 仅包含可行解的空间,而且表征整个调度空间,理 步骤1:根据设定的遗传变异基因率P和染 c1994-2008ChinaAcademicJounalElectronicPublishingHouseallrightsreseredhttp://nn.cnki.ner
图 1 遗传编码 先级别而加入的虚位置节点 ,是制品排程时的延迟 长度。最紧急的制品其延迟长度为零 ,不存在前虚 基因座节点 ,它有权优先竞争加工资源。而前虚基 因座节点越多 ,表示制品起始排程延迟长度越大 , 由于其他制品的实基因座节点可以插入其间 ,这样 相对这些制品前虚基因座节点所对应的制品越靠 后参与加工资源的竞争。所以 ,前虚基因座可以反 映制品之间的竞争资源的优先级别。 b. 实基因座。实基因座节点表示各制品的实 际加工工序以及这些加工工序构成的加工工艺链 , 实基因座节点数就是制品的工序数目。在构建统 一的染色体编码时 ,各制品实基因座和虚基因座节 点相互穿插形成一条单行队列 ,这一队列也反映了 制品内和制品之间工序的排程顺序 ,即抢占加工资 源的前后顺序。需要指出的是 ,这一顺序并不是排 程完成后工序的前后顺序 ,也就是说 ,先进入排程 的不一定获得较早的开工时间。 c. 后虚基因座。它是为了染色体编码而加入 基因所占的虚位置。由于各制品存在不同长度的 前虚基因座和实基因座 ,为保证总的染色体编码长 度一致 ,取各制品中前虚基因座 + 实基因座长度最 大值为统一长度 ,其他制品编码尾部的不足部分用 后虚基因座节点补足。 染色体编码步骤如下 : 步骤 1 ,给不同的制品指定整数编码基因 ,如 0 ,1 ,2 等 ,基因数为 n ,表示有 n 个制品参加排程 ; 步骤 2 ,根据不同制品的优先权值 ,生成数目 不等的前虚基因座节点 ; 步骤 3 ,找到参加排程的制品的前虚基因座 + 实基因座长度 (工序长度) 最大值 m , 例如参加排 程的制品有 4 个 ,它们的前虚基因座和实基因座长 度分别为 2 和 4 ,0 和 6 ,0 和 5 及 0 和 8 ,那么 m 就 等于 8 ; 步骤 4 ,随机加入编码基因组成编码长度为 L = n ×m 的编码串表示一个染色体。 经过分析 ,该编码方法就可行性而言编码空间 仅包含可行解的空间 ,而且表征整个调度空间 ,理 论上可以得到最优解。 2. 2 遗传操作 本文采用一种改进的基于位置交叉的方法来 进行编码交叉。具体做法如下 : 步骤 1 ,通过上述个体选择办法选中 2 个交叉 个体 ; 步骤 2 ,根据预先设定的交叉基因率 P ′ c 和染 色体编码基因数 n 确定发生交叉基因的范围大小 为 n ×P ′ c (取整) ; 步骤 3 ,根据发生交叉基因范围大小随机确定 交叉基因 ; 步骤 4 ,保证除了交叉基因外的其他基因位置 不变 ,遗传到下一代 ,对 2 个个体中的交叉基因进 行交叉变换 ,从而得到 2 个子代新个体。 例如选中交叉的个体为前面编码例子所产生 的 2 个个体 p1 和 p2 , P ′ c = 0. 42 , n = 4 ,取整后交 叉基因范围大小为2 个 ,随机确定交叉基因为1 ,3 , 则保持基因 0 ,2 的位置不变 ,对 p1 和 p2 中的 1 ,3 进行交叉变换 ,产生新个体如图 2 所示 ,其中 0 ,2 加下划线表示位置从父代遗传维持不变。这种交 叉方法保证子代个体从父代中遗传了部分特性 ,同 时又发生了一定的变化 ,且由于编码的优势交叉后 产生的子代染色体完全符合制造系统的各种约束 关系 ,保证了子代个体的合法性与可行性。 图 2 交叉操作 变异操作是模仿生物进化过程中染色体上基因 发生的突变现象 ,从而使染色体的结构和某些性状 发生相应的突变。在遗传算法中引入变异操作可以 使算法具有局部的随机搜索能力 ,加强算法的搜索 能力避免陷入局部最优 ,同时维持群体的多样性。 本文采用一种互换操作变异方法 ,具体做法如下: 步骤 1 :根据设定的遗传变异基因率 P ′ m 和染 ·现代设计与先进制造技术· 伍晓宇 王志勇 吴序一 基于实虚基因座的车间调 …… 73 © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
2008年4月中国制造业信息化第37卷第7期 色体编码长度L计算变异基因次数为L×P 操作之后的染色体为q 步骤2:随机选取染色体内不同位置2个基因21321032322102310012013100032313。通过采用 进行互换操作 互换变异,在一定程度上避免了“早熟”,有可能尽 步骤3:重复步骤2直到完成步骤1所计算的快地找到最优解 变异基因次数 2.3解码 例如,对如图2所示的子代个体q1进行变异, 解码的过程其实就是编码的逆过程图3所示 取变异基因率Pm=0.04,变异基因操作次数为为染色体编码q1的解码过程,图中的双下划线表 32×0.04≈1,随机选取互换位置为3,17,则变异示虚基因座,它不进行解码。具体步骤如下 染色体编码q1 1032322102310012013100032313 圆吸圆吸 甘特图 图3解码 步骤1,将所有制品顺序调度工序集O(=3遗传参数选取 0,1,…N-1)对应的位置标记Mark复位到0 由于这里研究的算法与系统主要针对车间生 步骤2,从左到右按顺序取编码基因i 产实践,因此强调的是优化与效率的平衡提升。在 步骤3根据取得的编码基因找到对应制品遗传参数选取上算法以能取得一定优化值且计算 的顺序调度工序集O4 速度能够接受为准则,同时在算法流程设计上也充 步骤4,若对应位置标记Mrk等于O的大小分考虑了这一点。当然,对于不同的问题,参数的 则返回步骤2,否则转到步骤5 选取是不同的。 步骤5,根据O4和Mark获取对应工序信息 a.进化群体的规模。一般取10~20,而对于 包括设备工种类型、计划加工工时和加工物料信息初始群体规模则可稍微加大,一般取12~30,主要 等,同时该位置标记Mark加1 是为了加大初始的全局搜索范围,但这个规模同样 步骤6,根据加工物料信息获取物料到达时是属于较小的 间 b.进化代数。一般选取20代以内。优化过程 步骤7根据设备工种类型到对应设备集中随必须兼顾效率,本算法在小进化代数下能够得到相 机寻找可加工时间晚于物料到达时间的最早开始 设备 对满意的优化值。因此,在进化代数的选取上以小 步骤8在该设备的调度上按该工序的计划加进化代数为主 工工时加入工序,当遭遇到设备计划的停工时段或 c.交叉概率与交叉基因率。交叉操作是在选 维护时段时按照普通排程方法处理 择操作后将得到的个体进行两两交叉,因为选择操 步骤9,重复步骤2~8直到选取完编码所有作由个体适应度决定,所以个体参与交叉的概率是 基因,从而产生一个完整的活动调度。 变化的、自适应的。个体参与交叉的概率直接与其 通过以上的解码过程最终就在数据库中形成适应度值对应的遗传概率挂钧因此优良个体参与 了一个完整的具体时间调度计划,包括设备的加工交又的概率就大,而劣质个体则相反,从而具有自 开始时间和加工结束时间等信息。根据这些信息适应性能。关于遗传参数的交叉基因率,通过实验 检索调度计划的开始时间和结束时间,两者之差便 般选取在0.2~0.5之间 是目标函数f(x)的结果。由于我们的目标是使 d.变异概率与变异基因率。与交叉概率相似 f(x)越小越好,而计算中的适应度值F是越大越由于变异操作在交叉操作后直接进行因此个体进 行变异的概率亦是变化的、自适应的。与交叉操作 好,因此取遗传适应度值函数F(x f(x)° 不同的是,由于变异操作属辅助操作,因此一般需 c1994-2008ChinaAcademicounalElectronicPublishingHouseallrightsreservedhttp://nwww.cnki.ner
色体编码长度 L 计算变异基因次数为 L ×P ′ m ; 步骤 2 :随机选取染色体内不同位置 2 个基因 进行互换操作 ; 步骤 3 :重复步骤 2 直到完成步骤 1 所计算的 变异基因次数。 例如 ,对如图 2 所示的子代个体 q1 进行变异 , 取变异基因率 P ′ m = 0. 04 , 变异基因操作次数为 32 ×0. 04 ≈1 ,随机选取互换位置为 3 ,17 ,则变异 操 作 之 后 的 染 色 体 为 q ′ 1 = 21321032322102310012013100032313。通过采用 互换变异 ,在一定程度上避免了“早熟”,有可能尽 快地找到最优解。 2. 3 解码 解码的过程其实就是编码的逆过程 ,图 3 所示 为染色体编码 q ′ 1 的解码过程 ,图中的双下划线表 示虚基因座 ,它不进行解码。具体步骤如下 : 图 3 解码 步骤 1 ,将所有制品顺序调度工序集 Oi ( i = 0 ,1 , …, N - 1) 对应的位置标记 Marki复位到 0 ; 步骤 2 ,从左到右按顺序取编码基因 i ; 步骤 3 ,根据取得的编码基因 i 找到对应制品 的顺序调度工序集 Oi ; 步骤 4 ,若对应位置标记 Marki等于 Oi 的大小 则返回步骤 2 ,否则转到步骤 5 ; 步骤 5 ,根据 Oi 和 Mark i获取对应工序信息 , 包括设备工种类型、计划加工工时和加工物料信息 等 ,同时该位置标记 Marki加 1 ; 步骤 6 ,根据加工物料信息获取物料到达时 间 ; 步骤 7 ,根据设备工种类型到对应设备集中随 机寻找可加工时间晚于物料到达时间的最早开始 设备 ; 步骤 8 ,在该设备的调度上按该工序的计划加 工工时加入工序 ,当遭遇到设备计划的停工时段或 维护时段时按照普通排程方法处理 ; 步骤 9 ,重复步骤 2～8 直到选取完编码所有 基因 ,从而产生一个完整的活动调度。 通过以上的解码过程最终就在数据库中形成 了一个完整的具体时间调度计划 ,包括设备的加工 开始时间和加工结束时间等信息。根据这些信息 检索调度计划的开始时间和结束时间 ,两者之差便 是目标函数 f ( x ) 的结果。由于我们的目标是使 f ( x) 越小越好 ,而计算中的适应度值 F 是越大越 好 ,因此取遗传适应度值函数 F( x ) = 1 f ( x) 。 3 遗传参数选取 由于这里研究的算法与系统主要针对车间生 产实践 ,因此强调的是优化与效率的平衡提升。在 遗传参数选取上算法以能取得一定优化值且计算 速度能够接受为准则 ,同时在算法流程设计上也充 分考虑了这一点。当然 ,对于不同的问题 ,参数的 选取是不同的。 a. 进化群体的规模。一般取 10～20 ,而对于 初始群体规模则可稍微加大 ,一般取 12～30 ,主要 是为了加大初始的全局搜索范围 ,但这个规模同样 是属于较小的。 b. 进化代数。一般选取 20 代以内。优化过程 必须兼顾效率 ,本算法在小进化代数下能够得到相 对满意的优化值。因此 ,在进化代数的选取上以小 进化代数为主。 c. 交叉概率与交叉基因率。交叉操作是在选 择操作后将得到的个体进行两两交叉 ,因为选择操 作由个体适应度决定 ,所以个体参与交叉的概率是 变化的、自适应的。个体参与交叉的概率直接与其 适应度值对应的遗传概率挂钩 ,因此优良个体参与 交叉的概率就大 ,而劣质个体则相反 ,从而具有自 适应性能。关于遗传参数的交叉基因率 ,通过实验 一般选取在 0. 2～0. 5 之间。 d. 变异概率与变异基因率。与交叉概率相似 , 由于变异操作在交叉操作后直接进行 ,因此个体进 行变异的概率亦是变化的、自适应的。与交叉操作 不同的是 ,由于变异操作属辅助操作 ,因此一般需 83 2008 年 4 月 中国制造业信息化 第 37 卷 第 7 期 © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
现代设计与先进制造技术·伍晓宇王志勇吴序一基于实虚基因座的车间调……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
2008年4月中国制造业信息化第37卷第7期 传算法优化作用十分明显,有时发现个体之间的排程长度计算结果相差一倍左右。 年1止应年1月1日一]程:orHm日 自动维程 图5初始群体个体数12进化10代的初始阶段数据 FAA NY 色儿_工进备名 工作型工列廿特图工11产n传法 算法」 图6初始群体个体数12进化10代的最后数据 实验证明,遗传算法的实现方法对于运行性能大的前提下,虚基因座的存在造成了大量冗余码 有很大的影响,随着计算代数的增加,计算时间也然而,经过实验发现并没有造成运行性能明显降 显著增加。虽然通过引入数据库索引技术及其他低。因此可以肯定虚基因座的存在对系统性能的 数据库优化技术可使工作性能得到一定的提升,但影响并不大。 仍然可以肯定至少80%以上的运算耗费大部分为 数据库存取操作的磁盘ⅣO上 结束语 因此,运算过程中应尽量减少磁盘ⅣO操作 本文提出的实基因座和前、后虚基因座的概 磁盘O操作过程中存在大量机械动作比内存念,能够很好地表达生产排程时制品之间的优先级 中的电操作慢得多,系统构建时,可先将所需全部别以及加工工艺路线,从而可确保获得符合生产要 信息,例如设备、制品、物料和工序信息等事先从数求的排程结果。构建了面向车间调度的实用遗传 据库中读入内存随后的操作全部放在内存中执算法经过使用某模具制造厂实际生产数据多次实 行,可使运行性能大大提高 验取初始种群个体数为12,进化群体个体数为 实验中虽然选代过程中无任何磁盘vO动10,交叉基因率为0.42,变异基因率为0.09,可得 作全部在内存中进行,且如果内存(B将足以到比较理想的结果效果明显。 满足需要,而CPU的负载自始自终为100%变成 系统运行瓶颈。 参考文献 另一方面通过对编码结果的分析发现,对于1王凌车间调度及其遗传算法M北京:清华大学 大规模问题,尤其是在各个制品包含工序数差别巨 社,2003:1-100 (下转第44页) 201994-2008ChinaaCademicJournalElectronicpUblishingHouseallrightsreservedhttp://www.cnki.ner
传算法优化作用十分明显 ,有时发现个体之间的排 程长度计算结果相差一倍左右。 图 5 初始群体个体数 12、进化 10 代的初始阶段数据 图 6 初始群体个体数 12、进化 10 代的最后数据 实验证明 ,遗传算法的实现方法对于运行性能 有很大的影响 ,随着计算代数的增加 ,计算时间也 显著增加。虽然通过引入数据库索引技术及其他 数据库优化技术可使工作性能得到一定的提升 ,但 仍然可以肯定至少 80 %以上的运算耗费大部分为 数据库存取操作的磁盘 I/ O 上。 因此 ,运算过程中应尽量减少磁盘 I/ O 操作 , 磁盘 I/ O 操作过程中存在大量机械动作 ,比内存 中的电操作慢得多 ,系统构建时 ,可先将所需全部 信息 ,例如设备、制品、物料和工序信息等事先从数 据库中读入内存 ,随后的操作全部放在内存中执 行 ,可使运行性能大大提高。 实验中虽然迭代过程中无任何磁盘 I/ O 动 作 ,全部在内存中进行 ,且如果内存 ≥1 GB ,将足以 满足需要 ,而 CPU 的负载自始自终为 100 % ,变成 系统运行瓶颈。 另一方面 ,通过对编码结果的分析发现 ,对于 大规模问题 ,尤其是在各个制品包含工序数差别巨 大的前提下 ,虚基因座的存在造成了大量冗余码。 然而 ,经过实验发现并没有造成运行性能明显降 低。因此可以肯定虚基因座的存在对系统性能的 影响并不大。 5 结束语 本文提出的实基因座和前、后虚基因座的概 念 ,能够很好地表达生产排程时制品之间的优先级 别以及加工工艺路线 ,从而可确保获得符合生产要 求的排程结果。构建了面向车间调度的实用遗传 算法 ,经过使用某模具制造厂实际生产数据多次实 验 ,取初始种群个体数为 12 ,进化群体个体数为 10 ,交叉基因率为 0. 42 ,变异基因率为 0. 09 ,可得 到比较理想的结果 ,效果明显。 参考文献 : [ 1 ] 王 凌. 车间调度及其遗传算法[ M ] . 北京 :清华大学出版 社 ,2003 :1 - 100. (下转第 44 页) 04 2008 年 4 月 中国制造业信息化 第 37 卷 第 7 期 © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
2008年4月中国制造业信息化第37卷第7期 表6负判断矩阵中元素向量出现正值符合要求,从而可以实现对产品外型的评价和筛 选,对产品外型设计具有一定的实用价值。如果把 NURBS的数据点看作参数,这种改进思想对其他 100090)∞0.0参数化的几何表达方法也具有一定的参考价值。 2(-10410,0)(-104100)(244100(24,4100) ,0)(95,0,1)65500)(560,0) 参考文献 Apllications, 1991, 11(1): 55-71 3结束语 12]方顾李季军,陆亚文.一种用于模具设计的 NURBS曲面 由以上的理论分析和实验结果可知,本文提出 造型系统设计方案[].模具工业,200632(2):18-21 的改进 NURBS表达方法可以判断产品外型设计3】陈军,崔汉国刘建军复杂船体曲面NURS造型技术的 研究与实现].计算机工程,2005,31(1):201-202 的合理性,只要能对产品外型的取值范围进行恰当(4]许平,田红旗,姚曙光流线型列车头部结构设计方法门 的限定,就可以获得比较好的判断效果,而且,由于 中国铁道科学,2006,27(1):78-82. 取值范围也可以是函数,所以它具有相当的灵活5]韩宝玲罗庆生,黎臻荣采用 NURBS进行汽车壳体计算机 性,为进一步精确表达设计要求提供了可能。 拟实外型的方法[J]机械设计与制造,2007,7(7):69-70 6]施法中计算机辅助几何设计与非均匀有理B样条[M].北 这种方法可以方便地判断改变后的曲面是否 京:高等教育出版社,2000 A Surface Re presentation Based on NURBS and Its Application An Yan fei-. QIU Ho (1. Xi'an Qixin Software Ltd. Co., Shaanxi Xi'an, 710076, China) (2. Dalian University, Liaoning Dalian, 116622, China) (3. Shantou University, Guangdong Shantou, 515063, China) Abstract It proposes a surface representation based on NURBS, which can test the validity of product design result. This method reorganizes the disorderly data of points in original NURBS, uses a differ- matrix and a criterion- matrix to represent geometric constraint, judges the requirement of design with the judgment-mar trix. It int roduces the common steps for representing and judging existed NUrBs surfaces, shows the shape car design of its front engine crust Key words NURBS; Differ- matrix; Criterion- matrix, J udgment-matrix (上接第40页) 2]伍晓宇,陈锦盛,王志勇,等.一个面向制造业的生产作业计 划调度系统[U]中国机械工程,2002,13(16):1423-1426 The Genetic Algorithm for Job- Shop Based on Real and Virtual Gene Stands WU Xiao- yu, WANG Zhi- yong, WU Xu-yi (1. Shenzhen University, Guangdong Shenzhen, 518060, China) 2. Shenzhen Institute of Standard Technology, Guangdong Shenzhen, 518033, China) Abstract It presents an improved genetic al gorithm using the idea of real and virtual gene stands for job hop. This met hod is self-adaptable in crossover and mutation, simple in encoding, evolving in small group converging in low generation and strong global searching. The example proves that the algorithm can solve the practical scheduling problems for job- shop and shorten the lead -time Key words: Shop Cont rol Scheduling; Genetic Algorithm; Optimization 201994-2008cHinaAcademicJournalElectronicPUblishingHouseaLlrightsreservedhttp:/hnnv.cnkiner
表 6 负判断矩阵中元素向量出现正值 i j 1 2 3 4 1 (0 ,0 ,0 ,0) (0 ,0 ,0 ,0) (30 ,0 ,0 ,0) (30 ,0 ,0 ,0) 2 ( - 10 ,41 ,0 ,0) ( - 10 ,41 ,0 ,0) (24 ,41 ,0 ,0) (24 ,41 ,0 ,0) 3 (9 ,6 ,0 ,0) (9 ,6 ,0 ,1) (5 ,6 ,0 ,0) (5 ,6 ,0 ,0) 4 (0 ,0 ,0 ,0) (0 ,0 ,0 ,0) (15 ,0 ,0 ,0) (15 ,0 ,0 ,0) 3 结束语 由以上的理论分析和实验结果可知 ,本文提出 的改进 NURBS 表达方法可以判断产品外型设计 的合理性 ,只要能对产品外型的取值范围进行恰当 的限定 ,就可以获得比较好的判断效果 ;而且 ,由于 取值范围也可以是函数 ,所以它具有相当的灵活 性 ,为进一步精确表达设计要求提供了可能。 这种方法可以方便地判断改变后的曲面是否 符合要求 ,从而可以实现对产品外型的评价和筛 选 ,对产品外型设计具有一定的实用价值。如果把 NURBS 的数据点看作参数 ,这种改进思想对其他 参数化的几何表达方法也具有一定的参考价值。 参考文献 : [ 1 ] Piegl L . On NURBS :a survey[J ] . IEEE Computer Graphics & Apllications , 1991 ,11 (1) :55 - 71. [2 ] 方 顾 ,李季军 ,陆亚文. 一种用于模具设计的 NURBS 曲面 造型系统设计方案[J ] . 模具工业 ,2006 ,32 (2) :18 - 21. [ 3 ] 陈 军 ,崔汉国 ,刘建军. 复杂船体曲面 NURBS 造型技术的 研究与实现[J ] . 计算机工程 ,2005 ,31 (1) :201 - 202. [ 4 ] 许 平 ,田红旗 ,姚曙光. 流线型列车头部结构设计方法[J ] . 中国铁道科学 ,2006 ,27 (1) :78 - 82. [ 5 ] 韩宝玲 ,罗庆生 ,黎臻荣. 采用 NURBS 进行汽车壳体计算机 拟实外型的方法[J ] . 机械设计与制造 , 2007 ,7 (7) : 69 - 70. [ 6 ] 施法中. 计算机辅助几何设计与非均匀有理 B 样条[ M ] . 北 京 :高等教育出版社 ,2000. A Surface Representation Based on NURBS and Its Application AN Yan - ping 1 , YI Peng - fei2 , Q IU Hong - jun3 (1. Xi’an Qixin Software Ltd. Co. , Shaanxi Xi’an , 710076 , China) (2. Dalian University , Liaoning Dalian , 116622 , China) (3. Shantou University , Guangdong Shantou , 515063 , China) Abstract :It proposes a surface representation based on NURBS , which can test the validity of product design result . This method reorganizes the disorderly data of points in original NURBS , uses a differ - matrix and a criterion - matrix to represent geometric constraint , judges the requirement of design with the judgment - ma2 trix. It introduces the common steps for representing and judging existed NURBS surfaces , shows the shape car design of its front engine crust . Key words :NURBS ; Differ - matrix ; Criterion - matrix ; J udgment - matrix (上接第 40 页) [2 ] 伍晓宇 ,陈锦盛 ,王志勇 ,等. 一个面向制造业的生产作业计 划调度系统[J ] . 中国机械工程 ,2002 ,13 (16) :1 423 - 1 426. The Genetic Algorithm for Job - Shop Based on Real and Virtual Gene Stands WU Xiao - yu 1 , WAN G Zhi - yong 2 , WU Xu - yi2 (1. Shenzhen University , Guangdong Shenzhen , 518060 , China) (2. Shenzhen Institute of Standard Technology , Guangdong Shenzhen , 518033 , China) Abstract :It presents an improved genetic algorithm using the idea of real and virtual gene stands for job - shop . This method is self - adaptable in crossover and mutation , simple in encoding , evolving in small group , converging in low generation and strong global searching. The example proves that the algorithm can solve the practical scheduling problems for job - shop and shorten the lead - time. Key words :Shop Control ; Scheduling ; Genetic Algorithm ; Optimization 44 2008 年 4 月 中国制造业信息化 第 37 卷 第 7 期 © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
