调度通过将系统中有限的资源在给定的时间内分配给若干任务,以达到降低库存、缩短工期和提高设备利用率等目的。随着柔性制造系统的引入,柔性作业车间调度问题(Flexible Job-shop Scheduling Problem,FJSP)已成为实际生产中亟待解决的一类问题,受到越来越广泛的关注。FJSP问题是NP-hard问题,精确方法难以在合理时间内求得问题的最优解。近年来,元启发式方法的出现和发展,为求解FJSP问题提供了新的有效手段。由于单一算法难以同时满足搜索的探索性和勘探性,混合算法得到了广泛应用。其中,遗传算法和禁忌搜索算法的混合应用取得了较好结果。遗传算法应用于FJSP问题的首要问题是染色体表示问题。本研究通过对现有FJSP问题染色体表示形式进行总结和分析,认为现有染色体表示形式造成了遗传操作的多样性不足。因此本研究提出了一种新的染色体表示,即MSOS-III,不仅保证了染色体的可行性,还增加了遗传操作的多样性。而禁忌搜索算法应用于FJSP问题的首要问题是邻域结构和移动评价策略。本研究提出了一种改进邻域结构可以将邻域构造过程与移动评价策略相融合,解决了以往基于邻域结构的局部搜索算法需要在移动评价上耗费大量时间的问题。同时,为保证局部搜索的连通性,提出了两级邻域搜索策略,提高了禁忌搜索算法的求解质量。最后,基于本研究提出的染色体表示、邻域结构和两级邻域搜索策略设计了混合遗传算法,并选择了四组具有不同规模和柔性的FJSP实例进行了对比实验。实验表明:本研究设计的混合遗传算法能获得大部分实例的历史最优解,且更新了8个实例的历史最优解,其结果优于其他先进算法,具有良好的性能。