课表安排问题实质上就是要求将学校开设的所有课程,在满足一定的约束条件下,合理地安排到有限的课时和教室资源上。课表安排工作是教学活动中必不可少的一个重要环节,对提高教学质量和节约教学资源起着非常关键的作用。该问题还是一个NP完全问题,用传统的精确算法求解容易导致算法复杂度的指数组合爆炸,因此设计出高效的启发式算法成为当前学者研究课表安排问题的热点之一。因此,无论是从实际应用还是从理论意义的角度考虑,课表安排问题都具有很大的研究价值。本文主要研究高中和大学的课表安排问题,目标在于设计简单、实用和高效的启发式算法。课表安排问题的困难在于,必须把大量的课程安排到紧缺的资源上,同时不能违反各种苛刻的客观约束和主观约束。这些约束通常分为硬约束和软约束,并定义满足所有硬约束的课表为可行解,而违反最少软约束的可行解为最优解。本文利用贪心和禁忌搜索的思想,提出了遍历搜索和定向搜索这两种邻域搜索策略,并在其基础上结合模拟退火,设计出了一个较为通用的二阶段课表安排算法。此算法在第一阶段构造一个可行解,而其第二阶段则在保持课表可行性的同时进行优化,尝试最大程度地去减少软约束违反的数量。高中的排课问题规模较小,难度较低,具有静态性。针对这些特征,本文提出了基于遍历搜索策略的模拟退火算法对其进行求解。为了证明算法的高效性,本文选用了HDTT和GPTT这两个高中课表安排的实例进行测试,并和当前高效的遗传算法、约束规划等算法比较。实验结果的对比分析体现了我们算法的优越性。在大学课表安排问题这个研究领域,最具代表性和影响力的是UCTP国际课表安排算法设计竞赛。针对这个竞赛提出的问题,本文设计了一个定向搜索策略,用于构造可行解。而在第二阶段,本文改进了前面提到的遍历搜索策略,使得算法能够更充分地提高可行解的质量。本文对竞赛提供的标准实例进行了测试,并采用了与竞赛一致的评价方式。评价结果表明,我们的算法优于大部分参赛的高效算法,是一个简单、实用、可拓展的算法。