无等待流水车间调度问题是一类应用广泛的组合优化问题。在常用优化目标函数下，无等待流水车间调度都是NP难问题，最优化算法由于具有指数时间复杂度，从而只适用于中小规模实例；对大规模实例，常采用启发式方法以在合理时间求得次优解。邻域搜索算法是一类最为常用的启发式方法。　　 本文针对最大误工时间、总完工时间以及最大完工时间三个目标函数，研究无等待流水车间调度问题的邻域搜索算法，主要工作有：(1)基于任务块分解的分析方法。通过将当前解分解为任务块，给出了四个常用基本操作在最大误工时间目标函数下的加速性质，并设计了一个对偶倒置邻域。借助这些性质，搜索插入、交换、倒置以及对偶倒置邻域的时间复杂度以及NEH构造算法的时间复杂度均从O(n3)降至O(n2)。(2)邻域扩展及其加速性质。通过将任务块分解方法推广到邻域设计，给出了三个新的较大规模邻域：D(n4)规模的不相邻任务块交换邻域以及O(n3)规模的相邻任务块对换邻域和扩展单任务交换邻域，分析了三个邻域基本操作在最大误工时间和总完工时间目标函数下的加速性质。这些邻域亦可作为通用邻域派生出新的O(n2)规模的邻域。(3)基于最短路径的邻域搜索算法。针对最大完工时间目标函数，为指数规模的动态规划邻域，设计了一个O(n2)时间复杂度的动态规划搜索算法；为O(n4)规模的不相邻任务块交换邻域，通过重用中间计算结果，设计了一个O(n2)时间复杂度的搜索算法。两个算法均等价于搜索对应有向无环图中的一条最短路径。(4)有效的元启发方法。通过选取合适的禁忌属性及邻域基本操作禁忌状态的条件，给出了一个有效的禁忌搜索算法：选取相邻任务对作为禁忌属性，邻域基本操作的禁忌状态是该基本操作试图添加到当前解的相邻任务对的禁忌状态的合取；采用二维矩阵作为禁忌表的数据结构，使得该禁忌表可以容纳多种邻域并可在常量时间内判邻域基本操作的禁忌状态。通过在迭代局部搜索中使用变换邻域下降，提出了一个迭代变换邻域搜索算法，并比较了不同邻域组合用于迭代变换邻域搜索算法求解总完工时间以及最大完工时间目标函数时的相对性能。　　 模拟实验得出如下结论：(1)插入类型的邻域比相同渐进规模的交换类型的邻域更有效；(2)相对于并集，变换邻域是更有效的多邻域搜索方式；(3)若相邻解的评估时间复杂度为常量，则采用邻域搜索好于进化算法；(4)目标函数是影响邻域设计和评估的重要因素之一。