带瓶颈移动法的混合遗传算法求解柔性作业车间调度.pdf

( ) 第25卷第9期 总第165期 　　　　　　　系　统　工　程 V ol. 25, N o. 9 2007年9月　　　　　　　　　 　　　　 System s Engineering Sep t. , 2007 文章编号:(2007) 带瓶颈移动法的混合遗传算法求解柔性作业车间调度 陈　钢, 高　杰, 孙林岩 (西安交通大学 管理学院, 陕西 西安　710049) 摘　要: 柔性作业车间调度问题是对传统车间调度问题的扩充, 它更接近于现实的生产调度问题。针对柔性作 ( ) 业车间调度问题, 提出了带局域有哪些信誉好的足球投注网站 瓶颈移动法 的混合遗传算法。区别于传统的遗传算法, 本文算法用两个 向量来表达解, 并采用了适应问题特征和染色体结构的交叉和变异算子。基于关键路径的思想, 瓶颈移动法使 用两种有效的邻域结构: 改变关键路径上相邻两工序的加工顺序和为关键路径上的工序分配新设备。为了提 高有哪些信誉好的足球投注网站能力, 邻域结构可以动态调整。我们在3个代表性标准测试问题上检验了该算法的求解性能。 关键词: 柔性作业车间调度; 遗传算法; 瓶颈移动法; 邻域结构 中图分类号: T P 18　　　文献标识码: A 每个工序分配合理的机器, 然后才是工序调度问题。 fJSP 1　引言 问题是对JSP 问题的扩展。由于已经证明JSP 问题是N P [1 ] 在作业车间中, n 个工件在m 台设备上进行加工。每 难题 , fJSP 问题也是N P 难题。 个工件 都包含了 个顺序化的工序 ( , , …, ) 。工 一旦为工序分配好了设备, fJSP 问题也就转化成了 i m oi1 oi2 oim ( ) 传统的JSP 问题。为降低问题的复杂性, 早期的研究多采 序 工件 的第 个工序 所指定的设备为 , 作业时 oik i k M ik 间为p ik , 每个工序在加工过程中不能被打断。同一工件上 用层次化的求解策略: 将设备分配和工序调度独立起来研 究[2- 5 ]。 开始 同时考虑设备分配和工序调度 决 的工序 oi1, oi2 , …, oim 必须按照顺序执行, 每台设备同时只 Jurisch