以总完工时间为目标的无等待流水车间调度问题是一个重要的制造加工系统,广泛应用于工业生产中。无等待问题是流水车间调度中的一种,是一类典型的NP完全问题,已被证明在多项式时间内得不到最优值。好的求解方法可以促进企业提高生产率,降低生产成本。因此,该研究无论从理论还是实际都有重要意义。目前对这些问题的研究主要可以分为两类方法:启发式方法和元启发式方法(包括遗传算法、模拟退火、人工神经网络、禁忌搜索和蚁群算法等)。这两类方法在评价算法性能的两个标准方面各有优缺点:在最优性(Efficiency)方面,元启发式算法在总体上优于启发式算法,但是由于不确定参数的存在其解的稳定性较差;在有效性(Effectiveness)方面,元启发式算法通常较差,其需要的CPU时间远远多于多项式复杂度的启发式算法,使得他们很难应用于工程实践,特别是对于大规模的调度问题。所以,本文研究有效的混合算法能在较短时间内找到较好的解对实际的工程应用具有重要意义。首先,针对以总完工时间为优化目标的无等待流水作业调度问题,提出一种遗传算法来构造所求问题的初始解,然后在DS算法的基础上采用多移动的思想提出基于局部搜索的启发式算法DSM用以对初始解进行改进。提出的混合算法与目前求解无等待流水调度问题最好的算法RC,DS,DSM在4000个实例上进行比较。试验结果表明:在最好调度的获取能力、所得调度的平均质量及所得调度的稳定性方面,混合算法均是最优的。因此,它能够更有效地解决以总完工时间最小为目标的无等待流水车间调度问题。