混合遗传NEH算法在流水车间调度中应用

盛立纲，顾幸生

华东理工大学自动化研究所 上海

摘      要： 针对流水车间调度问题提出一种混合遗传NEH算法，以提高求解效率。NEH算法是一种高效的构造性算法具有很强的邻域搜索能力，而遗传算法则能有效的提供全局搜索。据此，新算法首先通过选择、交叉和变异操作，经过迭代获得一个较好解，然后在这个解所在的特定邻域内进行改进的NEH搜索，以获得更好解，经过NEH搜索后求得的较好解作为一个新个体加入下一代种群中，继续进行遗传操作。通过对流水车间调度的较小化较大完成时间问题的仿真实验结果表明，新算法有明显改进。

关  键  词：流水车间调度；遗传算法；NEH；较大完成时间

1 引言
流水车间调度问题可简述为：一些工件按照同一顺序在几台机器上进行加工；每个工件在每台机器上只加工一次，而且加工过程不能中断。迄今为止，人们提出了各种各样的优化方法以求解流水车间调度问题。这些优化方法可以分成三大类：精确计算法、构造法和智能计算法[1]。精确计算法主要包括规划法[2]，一般只适用于中小规模问题。构造法，是一种从局部较优中寻找全局较优的方法，适用于进行局部搜索。其中NEH是公认的较好的构造法[3]。由于流水车间调度问题是NP难问题，用智能优化方法得到满意解便成为近期研究关注的重点。它们包括：模拟退火算法，遗传算法[4]，粒子群算法，蚁群算法，文化算法[5]等等。遗传算法也许是被较为广泛应用的算法之一。遗传算法可以为大规模问题给出一个合理满意的解，但是有时候计算效率不高，并且合适的适应度函数并不容易找到。与之相对的，NEH算法能为车间调度问题更快的提供一个稳定可靠的解。近年来，出现了不少算法与NEH相结合取得了较好的结果[6]。本文将遗传算法和NEH算法相结合，用来更好的解决流水车间调度问题。首先，用遗传算法来缩小搜索范围，当这个范围达到一定程度时再用NEH的方法进行搜索，以求得到一个更好的解，并把这个解返回给遗传算法以改善染色体，再继续进行搜索。此外，改进了遗传算法和NEH算法。

登录网站后可下载文件

相关阅读:

• ...2012/04/10 11:40·开放式车辆路线问题的改进混合遗传算法
• ...2012/03/21 10:20·两步式混合遗传算法及其在常减压装置的应用
• ...2012/03/15 15:33·基于混合遗传算法的时间较优控制问题求解