调度问题是指将有限的资源,在给定时间内分配给若干任务,从而优化一个或多个调度性能指标,如最大完工时间、总加权拖期等。作业车间调度问题（Job-shop Scheduling Problem,JSP）是生产调度问题的重要分支,受到了众多研究学者的广泛关注。在JSP问题的研究基础上进行拓展,可以为其他生产调度问题的研究提供理论指导。JSP问题作为最简单的调度问题,是许多复杂生产调度问题的基础与简化。同时JSP问题是NP-hard问题,也是最难的组合优化问题之一。精确算法虽然可以求得JSP问题的最优解,但却牺牲了求解的效率,难以在较短时间内求解大规模问题。近似算法可以在合理时间内获得JSP问题的全局最优解或近似最优解,因此得到了广泛的应用。其中,局部搜索算法性能优越,目前已经成为求解JSP问题最受欢迎的方法之一,而邻域结构则是影响局部搜索算法求解JSP问题的关键因素。本研究基于对现有邻域结构的分析,提出判断工序执行前向插入移动和后向插入移动后邻域解可行性的充分条件,并提出一种在保证邻域解可行性的前提下,可以探索更大解空间的通用型邻域结构,打破了经典邻域结构之间的界限。通过引入工序头时间和尾时间变化量的概念,在通用型邻域结构的基础上,限制产生非改进解的邻域移动,从而进一步缩小邻域规模,优化通用型邻域结构。最后,本研究以最小化最大完工时间为优化目标,建立作业车间调度问题模型。采用具有非改进解接受机制和历史精英解追踪回溯机制的禁忌搜索算法,应用通用型邻域结构,从而改进禁忌搜索算法的性能,提升算法的求解质量。本文选择了四组规模不同的JSP问题实例进行对比实验。实验结果表明:本研究设计的基于通用型邻域结构的禁忌搜索算法能获得大多数问题实例的历史最优解,结果优于其他先进算法,具有良好的性能。