Job Shop Scheduling问题是指：有一组机器加工一组工件，每个工件有若干个工序，把这些工序按照一定次序加工，在加工的过程中要满足问题特定的约束条件，并使所有工序完成后形成的最终调度的时间跨度尽可能短。该问题是一个典型的NP完全问题。NP完全问题的精确求解算法计算时间会随着问题规模的增大而呈现指数增加，因此，用精确算法求解Job ShopScheduling问题是不实际的，而近似算法则能在较短的时间求出问题的满意解。由于Job Shop Scheduling问题是一个很重要的实际问题，因此，寻求该问题的近似算法有重要的理论价值和实际意义。本文采用优先指派规则来确定工序的调度顺序。借鉴工人在调度工作中的实际经验，研究并设计了多规则的优先指派算法SP(Simple Priority)，验证结果表明，算法SP能在较短的时间内得到问题实例的近似解。为了得到算例的最优解，本文在优先指派规则的基础上引入枚举策略和局部搜索策略，对算法SP进行了改进和完善，并设计了基于优先指派规则的枚举算法ESP(Enumeratebased on Simple Priority rule)和基于优先指派规则的局部搜索算法LS(LocalSearch)。对算例的测试结果表明，算法ESP和算法LS都能得到部分算例的最优解。禁忌搜索算法TS(Tabu Search)的计算结果与初始解的优度、邻域的好坏以及禁忌表长度的选取都有很大的关系。为了进一步求解问题实例的最优解，经过对经典禁忌搜索算法的研究，设计了一种改进的禁忌搜索算法ITS(ImprovedTabu Search)。通过问题实例对算法ITS测试表明，算法ITS能得到大部分算例的最优解，是一个可行且有效的Job Shop Scheduling问题的求解算法。