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

论文编号:TX042        论文字数:17736,页数:37

摘要

    排课问题是涉及班级、教师、教室等因素的决策优化问题，也是组合规划中的典型问题。在自动排课系统中，处理排课问题所用的算法处于核心地位，由于排课问题本身的复杂性，寻找这样一个有效算法还是有相当的难度。本文课题来源于自动排课问题的求解算法研究。
    本文借鉴以往的成功经验并结合本学校的实际情况，提出了一种基于禁忌搜索算法的排课问题解决方案。首先，使用网络最大流算法预处理，把授课任务分成若干组，同组的任务可以同时进行而不发生冲突，而且保证教室需求量不大于供应量。然后，使用禁忌搜索寻求任务组与时间的最优组合方式。最后，给任务分配教室输出课表。本文先给出了算法的总体框架，然后对如何建立网络流模型以及禁忌搜索的各个要素进行了详细的说明，最后使用真实数据进行了仿真测试。
    这种方案结合了经典的网络流算法与禁忌搜索算法，使两种算法优势互补，带来了较好的处理问题能力。经实际数据的仿真验证，该算法具有一定可行性和适用性。

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

Abstract
  Course-timetabling problem, an optimization decision-making problem involving factors such as classes, teachers and classrooms etc, is a typical problem of combinatorial planning. In an automated-course-timetabling system, the algorithm of course timetabling enjoys the core status, but it is rather difficult for us to find an effective processing algorithm due to the complexity of the course-timetabling problem itself. The subject studied in this paper originates from the research on the algorithm of automatic course-timetabling problem.
  This paper introduced a method to solve the course-timetabling problem based on taboo search. First, uses the network max-flow algorithm in preprocessing to divide the teaching tasks into several groups, in which the tasks can be carried on simultaneously without collisions and the number of the required classrooms not lager than the number of the supplied ones. Second, seeks a best combination between task groups and time slots using taboo search. Last, assigns a classroom to every teaching task and outputs the course timetable.This paper proposes an outline of the algorithm at first. Then, a detailed explanation is given on how to establish the network-flow model as well as how to use the essential factors in taboo search. Finally, uses the real data to carry out the simulation test.
  The implementation of the plan, which unifies the classical network flows algorithm and the modern heuristic taboo search algorithm, causes the superiorities of two algorithms supplementing each other, and improves the ability of processing problems. After confirmed through the real data simulation, the algorithm which this paper proposed is of certain feasibility and the serviceability.
Keywords: Course-Timetabling Problem,Combinatorial Optimization
Network Flow,Taboo Search

目    录
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