车间作业调度问题jobshop的一种改进遗传算法

《车间作业调度问题jobshop的一种改进遗传算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、万方数据第24卷第2期(尊第107期)V01．24No．2(SUMNo．107)机械管理开发MECHANICALMANAGEMENTANDDEVELOPMENT2009年04月Apr．2009车间作业调度问题(job—shop)的一种改进遗传算法冯伟东，刘伟，徐连香(长春工业大学机电工程学院，吉林长春130012)【摘要】搜索空间适应性的遗传算法(GSA)具有这样的能力，即使在不通过修改遗传算法的某些参数(例如交叉率和变异率)的情况下，就可适应解空间的结构、并调节全局搜索和局部搜索的相互平衡。但是这种遗传算法(GSA)需有对个体特征继承率控制能力的

2、交叉操作。文章阐述了一种改进的搜索空间适应性的遗传算法(mGSA)用于解决车间作业调度问题(JSP)：这种方法不同于GSA不需要带特征继承率调节能力的交叉操作。最后通过两个benchmark问题的数字实验．展示了这种方法的的有效性；并通过与现存的遗传算法相比较，展示了这种方法有更好的结果。【关键词】车间作业调度问题；遗传算法；搜索区域适应【中图分类号】THl88【文献标识码】A【文章编号】1003—773X(2009)02-0137-031概述调度问题存在于现实社会的各个领域，特别是工业工程领域。许多制造工业中的复杂调度问题往往都是NP—hard问

3、题【lJ，通过传统的优化方法是很难解决的。通常这样难解决的调度问题，被看成为具有高约束条件的组合优化问题【lI。随机的优化方法。像遗传算法已被用到许多困难的组合优化问题当中，这些方法要配备有出色的表现全局和局部搜索的能力。因为该方法要考虑全局和局部优化之间的目标，所以往往难以同时满足两者的要求。虽然一些现有方法，由调整几个参数克服了一些困难。但要调整妥善合适，也不那么简单。遗传算法就其全局搜索，呈现出良好的能力。在整个空间中它开始多点搜寻；具有交叉和变异遗传算子，从而能搜寻广泛的地区。对于适当的折中平衡，调整参数(如交叉率和突变率)是遗传算法中必不

4、可少的。Someya和Yamamura最早提出了带有搜索区域适应性的遗传算法(GSA)t21，它是通过考虑遗传操作的具体角色而被发展起来的。GSA有适应解空间和动态调整全局和局部搜索平衡的能力。通过几个展位设计问题的实例设计，GSA已经显示了良好的性能。但是GSA需要一个具有特色继承比例调节的能力的交叉算子。本文阐述了对于解决作业车间调度问题的一类改进的带有搜索空间适应性的遗传算法。它显示了比现存遗传算法更优的性能。本文主要有下列内容：作业车间调度模型，适应性遗传算法，改进的适应性遗传算法。本文算法与其他算法的比较。2作业车间调度模型一般来说。作业

5、车间调度模型通常描述如下(Gen&Cheng，1997)：加工系统中有几个工件^，五，⋯Z和m台机床肘。，鸭，⋯⋯，眠，每个工件均需不重复地经历所有机床加工。工件的工艺路线和加工时间事先已知。同时假设：1)一个工件同一时间只能加工一个工序：2)一台机床同一时刻只能加工一个工件；3)工序一旦开始就不能中断；4)任何工件没有抢先加工的特权。调度问题的解决目标是如何安排生产，使生产周期最短【”。3搜索区域适应性的遗传算法(GSA)GSA是在解空间中自适应搜索最优解，在图1示出了一个GSA过程的伪代码[21。一个周期被分为两个阶段：交叉和变异。交叉由三部分

6、组成：交叉选择(RC)、交叉、交叉存活(SC)。变异也由三部分组成：变异选择(RM)、变异、变异存活(SM)。本文中，我们采用‘个体’这个术语作为给定问题的候选解；同时也用如下术语：子代(通过交叉产生的一代个体)。父代(通过RC选择的个体)。长女(通过sC选择的个体)。变异个体(通过RM或者变异产生的个体)。后代(通过SM选择的个体)。选择初始种群并置数器为零(counter=O)：While(counter

7、o和PI；lelseif(2ndrepeat){2个父代个体为Pl和P2；lelseif(3rdrepeat){2个父代个体为P2和P0；】do(通过交叉操作产生新个体并选择最优个体；1while(目前选择的最优个体劣于种群中的最差个体)；counter+=生成新个体的数目：)Repeat3times{repeatR_mtimes／／R_m是终止条件参数：f通过变异生成新的变异个体；l从变异生成的个体中选择生成的后代；counter=-+生成变异个体的数目：1用3个后代个体取代之前的3个父代个体；)．图1GSA算法的伪代码收稿日期：2008—10-

8、07作者简介：冯伟自-,(1968一)，男，吉林长春人，副教授，硕士研究生导师，硕士，研究方向：计算机集成制造。·137·