0I:10.13374/j.issn1001-053x.2002.01.054 第24卷第1期 北京科技大学学报 Vol.24 No.1 2002年2月 Journal of University of Science and Technology Beijing Fcb.2002 模糊遗传算法在机器调动问题运用 郑大伟玄光男 日本足利工业大学经营工学科智能系统工学研究室 摘要单机器调度问题是研究工件在多道工序进行加工的加工活动排序的组合最优化问 题.由于调度问题中绝大多数属于NP一难类问题，不存在有效的最优求解算法，针对用智能优 化算法一遗传算法求解单机器调度问题中交叉率和变异率难以确定的问题，设计了一种模糊 算法以便自动确定交叉率和变异率，通过数值实验，嵌入模糊规则的遗传算法比简单的遗传算 法要好，说明在实际生产中，此算法具有强大的发展前途 关键词机器调度问题；遗传算法：模糊逻辑 分类号TP2734TP206.1 单机器调度问题是研究工件在多道工序进 罚.根据Rinnooy Kan的定义)，本问题被定义为 行加工排序的组合最优化问题.本文把各个工 /I/IET,或被简称为ET.用TIMETABLER方法 作的提前和滞后惩罚的总和作为目标.该问题 来对染色体进行编码以便减少全惩罚. 是NP-难类问题，不存在有效的最优求解算法. 遗传算法(GAs)是一种具有“鲁棒性”(Robust-- 2子代和父代之间的相关性 ness)的方法，它可以适应不同的问题环境，在大 对于有20个单机调度的问题，随机生成200 多数情况下都能得到比较有效的满意解四.很 个调度方案，然后进行染色体交叉操作.一点顺 多研究者都在这方面作了工作.本文提出了一 序法如图1所示.交叉实施后，子代和父代的相 种改进的遗传算法来求解调度问题.设计了一 任选一个位置 按染色体2的顺序重新排工件 种模糊算法用以自动确定交叉率和变异率从而 可以省略用以确定交叉率和遗传率初始计算. 53741826 53741826 1 机器调度问题 图1一点顺序法 单机器调度问题中有个工件，每个工作的 Fig.1 One-point order method 就绪时间为0，即在开始加工时，所有工件都具 关系数如图2所示.横轴表示父代的平均目标 备加工条件.每个工件都具有下面的属性：() 值，纵轴表示子代的平均目标值.用同样的方 为加工时间：d()为完工时间：()为提前完工时 法，计算变异操作的相关性.变异方法如图3所 的单位惩罚；()为滞后完工时的单位惩罚. 示.变异实施后，子代和父代的相关系数如图4 假设n个工件分别以其自然数编号1,2，n 所示.横轴表示父代的平均目标值，纵轴表示子 标识，则工件标识的任意一个排列可以表示一 代的平均目标值.由图2和图4父代和子代之 个调度方案s=S2,小，S是第i个工件.目标 间具有正相关性，因此优良的父代能够产生优 是求解全惩罚，目标函数如下定义： 良的子代 minZ(s)=E[e(s)max(d(s)-c(s),0;+ 为确定交叉率，定义规则：(1)为了防止遗 (s)max(c(s)-d(s,),0)] (1) 传搜索停留在局部最优解，当各个染色体的目 式中，c(s)是工件的完成时刻.等式右边第1项 标值之间的差很小时应该加大交叉率.(2)如果 是提前完成的惩罚，第2项是滞后完工时的惩 任选的染色体的目标值和当前世代中的最大目 标值相差很小时应该减小交叉率，可以省略逻 收稿日期2001-02-12 郑大伟男，32岁，博士DOI: 10. 13374 /j . issn1001 -053x. 2002. 01. 054