单机调度问题一直是调度领域的研究热点，是生产调度问题的基础及核心问题之一。大多数单机调度问题已经被证明是NP难度的，因此，单机调度问题的研究不论是在当今国际学术界还是在实际生产领域都是一项具有挑战性的重要课题。求解NP难度的问题一般有三种方法：精确算法、近似算法和启发式算法。精确算法在求解规模较大的问题时，时间复杂度呈指数级增长，计算时间让人无法忍受；近似算法虽然能在较短的时间内找到解，但是，解的质量跟实际需求相差较远；启发式算法在解决大规模复杂问题时，有可能在合理的时间范围内给出一个满意的解。启发式算法在各个领域已经受到越来越多的关注，逐渐成为求解NP难度问题的有力工具。本文的研究重点是设计求解单机调度问题的高效启发式算法，并通过实验对算法进行了分析和评价。　　本研究主要内容包括：⑴提出了一种新的“块移动”的邻域结构（NBlock Move），该邻域结构扩大了邻域的搜索空间，并且通过限制相关参数的取值范围来提高搜索的有效性。⑵针对块移动的邻域结构，提出了一种高效的快速增量评估技术，提高了搜索效率。⑶在块移动邻域结构以及对块移动邻域结构的快速增量评估技术基础上，提出了一种新的迭代局部搜索算法BILS来求解单机调度问题。⑷提出了一种基于“公共块”概念的交叉算子BOX（Block Order Crossover Operator）。⑸提出了一种新的基于相似性和质量的优度函数的种群更新策略。⑹对比了不同的交叉算子和种群更新策略的组合在混合进化算法中处理单机调度问题时的表现，提出了一种高效的求解单机调度问题的混合进化算法LOX⊕B。⑺用带准备时间的单机加权延迟调度问题的120个公共算例对BILS进行了测试，BILS找到了所有120个算例的最优解。对于算例18和24，BILS找到最优解分别需要8586.6秒（≈2.4小时）和150169.22秒（≈41.7小时），而Tanaka和Araki的精确算法找到最优解则分别需要两个星期和30天。与其它几种优秀的启发式算法组成的当前最好解比，BILS改进了34个算例的当前最好解，82个算例的解与当前最好解持平。⑻用带准备时间的单机加权延迟调度问题的120个公共算例对LOX⊕B进行测试，结果与当前文献中最优秀的启发式算法的最好解OBK、ACO AP、DPSO、DDE、GVNS相比，改进最好解的个数分别为94、84、66、52、44。与本文新提出的BILS算法比，在平均值的优度和找到最好解的平均时间上都有较大的提高，表明了LOX⊕B相对于BILS更加稳定和高效。⑼用带准备时间不带权的单机延迟调度问题的64个公共算例对LOX⊕B进行测试。LOX⊕B算法用6037.93秒（≈1.7小时）找到算例prob855的最好解“256”，改进了由Tanaka和Araki的精确算法用超过30天时间找到的当前最好解“258”，并找到了其余63个算例的最优解或当前最好解。其中，对于算例prob751和prob851，LOX⊕B找到最优解或当前最好解的时间分别为33678.64秒（≈9.4小时）和84405.88秒（≈23.4小时），而Tanaka和Araki的精确算法却分别需要34天和超过30天的CPU时间。LOX⊕B算法对这64个算例的计算结果与当前最好的几种启发式算法相比也有很大的改进。