大学自动排课算法设计与实现

摘要

    排课问题是涉及班级、教师、教室等因素的决策优化问题，也是组合规划中的典型问题。在自动排课系统中，处理排课问题所用的算法处于核心地位，由于排课问题本身的复杂性，寻找这样一个有效算法还是有相当的难度。本文课题来源于自动排课问题的求解算法研究。

    本文借鉴以往的成功经验并结合本学校的实际情况，提出了一种基于禁忌搜索算法的排课问题解决方案。首先，使用网络最大流算法预处理，把授课任务分成若干组，同组的任务可以同时进行而不发生冲突，而且保证教室需求量不大于供应量。然后，使用禁忌搜索寻求任务组与时间的最优组合方式。最后，给任务分配教室输出课表。本文先给出了算法的总体框架，然后对如何建立网络流模型以及禁忌搜索的各个要素进行了详细的说明，最后使用真实数据进行了仿真测试。

    这种方案结合了经典的网络流算法与禁忌搜索算法，使两种算法优势互补，带来了较好的处理问题能力。经实际数据的仿真验证，该算法具有一定可行性和适用性。

关键词：排课问题，组合优化，网络流，禁忌搜索

目    录

1 绪论 1

1.1 课题背景及其目的 1

1.2 国内外研究状况 2

1.3 课题研究方法 3

1.4 论文构成及研究内容 3

2 排课模型的建立与分析 5

2.1 教务流程简介 5

2.2 课表的制定原则 6

2.3 排课系统的基本需求分析 8

2.4 排课问题模型 9

2.4.1 符号约定 9

2.4.2 建立组合优化模型 10

2.4.2.1约束条件定义 10

2.4.2.2 目标函数定义 11

2.4.2.3 模型描述 11

3 禁忌搜索算法理论研究 12

3.1 禁忌搜索简介 12

3.2 禁忌搜索原理 12

3.3 禁忌搜索示例 12

3.4禁忌搜索算法流程 14

4 基于禁忌搜索的排课问题求解 16

4.1 算法总体思想 16

4.2 符号定义 16

4.2.1 基本信息定义 16

4.2.2 基本函数定义 17

4.2.3 组合信息定义 17

4.3 基于网络流的预处理算法 17

4.4 基于禁忌搜索的时间分配算法 20

4.4.1定义域 20

4.4.2目标函数 20

4.4.3禁忌搜索的主要参数描述 21

4.4.4 禁忌搜索算法步骤 22

4.5 后续操作 24

4.6 算法运行实例分析 24

4.6.1 输入数据 24

4.6.2 预处理步骤分析 25

4.6.3 禁忌搜索过程分析 26

4.6.4 输出周课表 27

5 结论 29

5.1 对本文工作的总结 29

5.2 对进一步研究的展望 30

致谢 32

参考资料 33