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

关键词：流水车间调度；遗传算法；neh；****完成时间

中图分类号：tp 27    文献标识码：a

    流水车间调度问题可简述为：一些工件按照同一顺序在几台机器上进行加工；每个工件在每台机器上只加工一次，而且加工过程不能中断。

    迄今为止，人们提出了各种各样的优化方法用来求解流水车间调度问题。这些优化方法可以分成三大类：精确计算法、构造法和智能计算法。精确计算法主要包括规划法，一般只适用于中小规模问题。构造法，是一种从局部****中寻找全局****的方法，适用于进行局部搜索。其中，neh是公认的****的构造法。由于流水车问调度问题是np难问题，用智能优化方法得到满意解便成为近期研究关注的重点。它们包括模拟退火算法，遗传算法，粒子群算法．蚁群算法，文化算法-1等。遗传算法也许是被最为广泛应用的算法之一。遗传算法可以为大规模问题给出一个合理满意的解，但是有时候计算效率不高，并且合适的适应度函数并不容易找到。与之相对的，neh算法能为车间调度问题更快地提供一个稳定可靠的解。因此近年来，出现了不少算法与neh相结合取得了较好的结果。

  本文将遗传算法和neh算法相结合，用来更好地解决流水车间调度问题。首先，用遗传算法来缩小搜索范围，当这个范围达到一定程度时再用neh的方法进行搜索，以求得到一个更好的解，并把这个解返回给遗传算法以改善染色体，再继续进行搜索。此外，改进了遗传算法和neh算法。

    1)流水车间调度问题的具体定义有n个工件需要在m台机器上加工，第j个工件在第i台机器上的加工时间与加工的顺序无关，是一个固定的常数，为pij于是加工时间矩阵p就可以记为

    并且，在同一时刻，每个工件最多只在一台机器上加工而且每台机器最多只加工一个工件。问题的优化目标便是找到一种所有工件加工顺序使得从第一个工件在第一台机器上加工开始到最后一个工件在最后一台机器上加工完成所消耗的时间最短。若{ π1，π1，... ，πn-1，πn}表示一种工件加工顺序，则依据reeves所述，完工时间c（i，πj）可以按照如下公式计算：

    由此，生产周期可以如下定义：

    记ⅱ是所有可能的加工顺序集合，若π是****加工顺序，则有：

    

    显然，能很方便地用图形来表达这个问题。对于rr eⅱ，对应的图形记为g（π）=(n，e)，如图l所示。

   

    其中，n={l，2，…，m}．{l，2，…，n}是每个节点，(i，j)∈n权重为对应处理时间p的节点。g（∈ⅱ）可看作一个m×n的矩形，且每个节点的权重由一决定。按照上述计算完成时间cmax的方法，可以对应的在图上找出相应的一条从(1，1)到(m，n)的最长路径，使之等于cmax(π)，称为关键路径。关键路径中一定有(m—