禁忌搜索求解排课问题的应用研究

摘要

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

目录

文摘

英文文摘

声明

第一章绪论

1.1排课问题简述

1.2国内外研究现状

1.2.1排课问题的历史

1.2.2排课问题的求解方法

1.2.3当前研究趋势及存在的问题

1.3本文的研究意义及所做工作

1.4论文结构

第二章排课模型的建立与分析

2.1西电教务流程及排课特点简介

2.1.1教务流程简介

2.1.2教学教务信息系统简介

2.2课表的制定原则

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

2.4排课问题模型

2.4.1符号约定

2.4.2建立组合优化模型

2.5本章小结

第三章禁忌搜索算法理论研究

3.1组合优化问题的求解

3.1.1组合最优化概念

3.1.2邻域及邻域搜索

3.1.3启发式算法

3.2禁忌搜索算法

3.2.1禁忌搜索原理

3.2.2禁忌搜索算法流程

3.2.3禁忌搜索示例

3.2.4禁忌搜索的收敛性

3.3基于禁忌搜索的组合优化

3.4本章小结

第四章基于禁忌搜索的排课问题求解

4.1算法总体思想

4.2符号定义

4.2.1基本信息定义

4.2.2基本函数定义

4.2.3组合信息定义

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

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

4.5后续操作

4.6算法运行实例分析

4.6.1输入数据

4.6.2预处理步骤分析

4.6.3禁忌搜索过程分析

4.6.4输出周课表

4.7本章小结

第五章总结与展望

5.1对本文工作的总结

5.2对进一步研究的展望

致谢

参考文献

读研期间研究成果