多群体并行遗传算法在动态车间调度中应用.docVIP

多群体并行遗传算法在动态车间调度中应用 　　［摘 要］ 生产调度对企业的生产作业过程具有重要的作用。有效的调度方法和优化技术是实现先进制造和提高生产效益的基础和关键。本文论述利用多群体并行遗传算法可满足动态车间调度的应用，采用一种特殊构造遗传编码方法来改进遗传算法，提供有效的最优化查询。利用MATLAB工具以实例证明该算法的有效性。该算法特别适合于job-shop调度问题。 　　［关键词］ 指派规则；遗传算法； job-shop调度；多代遗传算法 　　 　　1 引 言 　　 　　生产调度是对企业生产作业过程进行计划#65380;安排以及组织执行,有效的调度方法和优化技术是实现先进制造和提高生产效益的基础和关键#65377;job-shop调度问题是许多生产调度问题的简化模型,是生产调度领域研究的重要内容,job-shop调度问题研究具有重要的理论意义和工程价值#65377; 　　当前,job-shop调度方法大多采用指派规则和知识库系统#65377;指派规则的缺陷是实用性差,局限于特定生产环境,同时需要人工选择和更新#65377;知识库系统利用有调度经验的专家知识来解决问题,它需要建立一个庞大知识库收集各种专家经验,这种方法具有工作量巨大#65380;速度慢#65380;效果不明显等缺陷#65377;本文提出一种并行多代遗传算法(GA),该算法应用迁移模型和一些改进的交叉和变异算子,处理动态job-shop调度问题,同时能够克服简单GA 的一些弱点,如计算时间长#65380;容易陷入局部最优等#65377; 　　 　　2 job-shop调度线性模型建立 　　 　　job-shop研究i个工件在k台机器上的加工,已知各操作的加工时间和i个工件在各机器上的加工次序约束,要求确定与工艺约束条件相容的各机器上所有工件的加工开始时间或完成时间或加工次序,使加工性能指标达到最优#65377;该问题的形式化如下: 　　设Cik表示工件i在机器k上的完成时间,tijk表示操作(k, j,i)的处理时间,Cik是基本决策变量#65377;每个job-shop操作都可以用(i, j,k)三变量描述为工件i操作j在机器k上执行#65377;假设操作(i, j-1,h)需要机器h,操作(i, j,k)需要机器k,那么Cik在可行的值域内描述优先级的约束条件的不等式如下: 　　 　　3 并行多代遗传算法 　　 　　job-shop调度问题属于一类资源组合优化问题,可以采用不同的优化策略来进行最优解的有哪些信誉好的足球投注网站#65377;本文提出一种并行多代有哪些信誉好的足球投注网站策略解决job-shop调度优化问题#65377; 　　3. 1初始化 　　初始化要为并行多代遗传算法产生一些可行的初代群体,本文通过算法随机产生初始代群体#65377; 　　3. 2编码和目标函数 　　3. 3交叉和变异 　　遗传算法产生新个体的一个基本运算是交叉,新个体具有父母某些遗传属性#65377;交叉的最简单运算是单点交叉#65377; 　　job-shop调度问题是一个极其复杂的过程,普通交叉和变异运算是无效的#65377;本文采用顺序交叉和多点交叉有效结合构造子代,在串的前半部分采用顺序交叉,后半部分采用多点交叉#65377; 　　顺序交叉首先随机确定两个交叉切点,然后把在这两个切点之间的部分传递给两子女#65377;接着运算器开始构建左边和右边的剩下部分#65377;第一代子女的构建是越过第2个父母,消除与第一代父母的传送部分相同的数值,并根据第2个父母出现的顺序装满空缺的左边和右边#65377;过程如图1所示#65377; 　　子串后半部分采用多点交叉,使用户能够选择交叉点的数值#65377;与单点交叉比较,采用多点交叉的优点在于:它支持有哪些信誉好的足球投注网站空间的探测,而不是对有哪些信誉好的足球投注网站过程中最早适合个体的支持,因此能使搜寻具有很好的鲁棒性#65377; 　　图2显示基于工件顺序交叉的例子是如何逐步执行这些操作的#65377; 　　当交叉操作的后代适应性不再进化,达到最优时,就需要对编码串进行变异运算#65377;变异运算将个体染色体编码串中基因座的某些基因值用该基因座的其他位来替换,形成新个体#65377;其目的是探索新的环境或者从再生控制器中追回损失的基因结构,通过随机改变基因位使发现的新基因结构完成最优化#65377; 　　变异运算有位置变异和顺序变异#65377;位置变异是将两个基因位随机交换;顺序变异是将一个随机选择的基因挪到另一个随机选择基因的前面#65377;如图3#65380;图4所示,每个变异操作都可能是在编码串的前半部分或者后半部分,这取决于最优化搜寻如何进行#65377; 　　3. 4替换 　　种群替换有整体替换和部分替换两种策略,整体替