课表安排问题的启发式算法研究

摘要

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

目录

文摘

英文文摘

声明

第一章绪论

1.1研究背景及意义

1.2国内外研究现状

1.3本文的内容安排

第二章课表安排问题概述

2.1课表安排问题的定义

2.2课表质量的评价标准

2.3课表安排算法综述

第三章启发式算法

3.1模拟退火算法

3.2禁忌搜索算法

第四章高中课表安排算法研究

4.1高中课表安排问题定义

4.1.1问题特征

4.1.2数学定义

4.2基于遍历搜索的模拟退火算法

4.2.1数据结构

4.2.2遍历搜索策略

4.2.3结合遍历搜索策略与模拟退火算法

4.3构造可行解算法

4.4优化可行解算法

4.5实验结果及其对比分析

4.5.1 HDTT实验结果及其对比分析

4.5.2 GPTT实验结果及其对比分析

4.6本章小结

第五章大学课表安排算法研究

5.1大学课表安排问题定义

5.1.1问题特征

5.1.2数学定义

5.2基于定向搜索的课表压缩算法

5.2.1数据结构

5.2.2定向搜索策略

5.2.3利用定向搜索策略压缩课表

5.3基于遍历搜索的模拟退火算法

5.3.1数据结构

5.3.2改进的遍历搜索策略

5.3.3结合改进的遍历搜索策略与模拟退火算法

5.4构造可行解算法

5.5优化可行解算法

5.6实验结果及其对比分析

5.6.1构造可行解实验结果及其对比分析

5.6.2优化可行解实验结果及其对比分析

5.7本章小结

第六章结论和进一步的工作

参考文献

攻读硕士学位期间发表的论文

致谢