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