项目调度问题是一类具有顺序约束和资源约束的组合优化问题,是典型的NP难问题。机器调度是特殊的项目调度问题。　　 本论文以最小化完工时间为优化目标,研究两类典型的机器调度问题和一类具有特殊约束的项目调度问题。在设计算法时,采用通用的算法框架,将问题划分为两个子问题分别设计方法求解:时间表方法和排列方法。时间表方法用于求解给定时间顺序约束的最优调度,排列方法用于搜索最优调度所对应的时间顺序约束。本论文主要工作有:　　 (1)双机无等待车间作业调度优化。通过研究两机无等待车间作业特点,提出分治法求解给定排列顺序下最优时间表问题;基于分治法所得的调度,采用著名的Gilmore& Gomory算法获得具有更高调度质量的排列;提出一个快速贪心算法搜索最优调度。　　 (2)机器数大于2的无等待车间作业调度优化。提出一个有限记忆的完全局部搜索算法(CLLM)及其改进版本(MCLM)。因为在机器数大于2的情况下,求解给定排列顺序的最优时间表是一个NP难问题。在CLLM中,分别设计了移动时间表方法和有限记忆的完全局部搜索解决时间表问题和排列问题。在MCLM中,首先研究无等待车间作业问题中两两任务之间可行开始时间的关系,提出基于可行时间差集的问题模型;根据该模型设计基于移动惩罚的时间表方法和改进的有限记忆的完全局部搜索,分别求解两个子问题。试验结果表明,高效的时间表方法对整个算法性能影响很大;　　 (3)阻塞车间作业调度优化。分析阻塞约束特点,设计冲突消除策略,并应用于时间表算法,消除任务之间的冲突以获得可行调度。采用有限记忆的完全局部搜索算法求解排列问题。　　 (4)可抢占有资源约束项目调度优化。研究不允许抢占情况下的经典有资源约束项目调度问题,提出一个完全局部搜索算法;分别研究在允许一次抢占和多次抢占对项目完工时间的影响,提出两个遗传算法。试验结果表明,允许抢占情况下,项目调度问题的完工时间可以大大减少;随着允许抢占的次数增加,项目调度问题的完工时间减少程度逐渐降低。