基于约束满足的学分制排课算法应用与研究

摘要

排课是高校教学管理中的一个重点和难点问题。由于在排课过程中需要涉及到教师、学生、教室及时间等多重因素，因此，是一个典型的组合优化和不确定性调度问题并被证明是一个NP完全类问题，其算法的实现具有相当的难度。而在学分制条件下，由于学生自由选课因素的引入，如何对冲突进行有效检测也成为一个新的问题。
　　本文针对目前已有算法在排课模型表述和冲突检测效率等方面存在的问题，通过引入一个约束松弛条件而将原来相对复杂的排课过程转化为两个相互独立的时间分配过程和教室分配过程，从而大大简化了排课过程。在此基础上，本文提出了一种以课次模式选择和冲突向量检测为基础以约束目标函数最大化为目标的对大学课表约束的简洁统一表述机制。然后，进一步提出了一种以冲突向量迭加和课次模式满意度调整为约束传播手段、通过最小冲突截断回溯算法来消解冲突的基于约束满足的高效排课算法。
　　该算法对各种排课需求，特别是对具有大规模多约束特征的应用具有极强适应性，具有很好的实用价值。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 排课问题简述

1.2 国内外研究现状

1.3 约束满足技术简介

1.4 本文主要工作

1.5 论文结构安排

第二章 排课及其基本要求

2.1 排课管理的一般流程

2.2 对排课结果的要求

2.3 对排课结果的评价

2.4 本章小结

第三章 约束满足理论基础

3.1 约束的概念

3.2 约束满足问题

3.3 约束满足求解

3.4 约束传播

3.5 约束满足优化

3.6 本章小结

第四章 基于约束满足的排课建模

4.1 几个排课过程中的基本概念

4.2 约束松弛与两阶段排课

4.3 变量、值域及课次模式

4.4冲突检测

4.5 目标函数

4.6 形式化表述

4.7 本章小结

第五章 排课系统的实现

5.1 系统及其初始化

5.2 预处理过程

5.3 排课过程

5.4 变量选择与值域选择

5.5 约束传播

5.6局部冲突消解

5.7 程序运行实例

5.8 本章小结

第六章 总结与展望

6.1 本文所做研究工作及意义

6.2 对下一步工作的展望

致谢

参考文献

攻硕期间的研究成果