面向高校统一教学资源排课问题的一种人机协同方法

摘要

高校课程表的编排是教务系统中最重要、最复杂的工作。伴随着我国高等院校研究生招生规模的不断扩大和教育改革的不断深入，在校学生人数迅速增加，班级和课程的数量也大幅增长，在统一教学资源的情况下排课变的越来越复杂。人工排课费时费力，极易造成排课结果混乱，而机器排课又缺乏灵活性。因此，人机协同排课成为解决排课问题的当务之急。
　　排课问题研究早在1976年由美国人S.Even等提出并且证明是一个NP完全问题。排课的本质就是要求将学校开设的所有课程，在满足一定的约束条件下，合理地安排到有限的课时和教学资源上。尽管目前有很多关于排课的研究，但是仍然没有一个很好的解决方案。
　　贪心算法是一种简化问题复杂度的算法。贪心算法在求解排课过程中，采用置顶向下迭代选择的方法，根据贪心策略求解局部最优解。每做一次贪心选择后，将现问题简化为规模更小的类似子问题。通过多次的贪心选择后，得到整个问题的整体最优解。
　　本文首先对排课问题进行了概述，介绍了国内外对这一问题的研究现状和发展趋势，并且提出人机协同排课的必要性和重要性。同时面向高校整体教学资源环境下的复杂多约束排课问题，提出了一种面向高校统一教学资源的人机协同排课方法。基于实际教学过程中涉及学生、任课教师、上课教室，以及各自的可行时间段等教学资源下的复杂多约束条件建立了约束函数，构建了以学生每周上课节次的均匀度、教师对任课时间满意度与学生课间行走距离倒数之和最大化为目标函数的优化模型。在求解过程中，将各约束条件转化为关系代数的关系运算，在缩小解空间的基础上进而采用启发式策略进行优选。最后，以一个实际高校的排课算例验证本文方法的有效性。

目录

声明

摘要

第1章 绪论

1．1 研究背景及意义

1．2 排课问题的研究现状

1．3 现存问题与研究内容

1．4 论文结构安排

第2章 排课问题算法综述

2．1 排课问题描述

2．2 排课问题算法综述

2．2．1 遗传算法

2．2．2 模拟退火算法

2．2．3 蚁群算法

2．2．4 回溯算法

2．3 排课问题的评价标准

2．3．1 可行解

2．3．2 最优解

2．4 本章小结

第3章 高校排课问题的模型构建

3．1 排课问题分析

3．1．1 基本概念

3．1．2 排课问题的冲突分析

3．2 排课问题建模

3．2．1 排课问题的概要模型

3．2．2 排课问题的约束条件

3．2．3 排课问题符号定义

3．2．4 排课问题数学模型

3．2．5 排课问题目标函数

3．3 模型求解

3．3．1 问题规模

3．3．2 约束的关系代数转换

3．4 本章小结

第4章 人机协同排课实现

4．1 贪心算法

4．1．1 贪心算法求解步骤

4．1．2 贪心算法的性质

4．2 人机协同思想

4．2．1 人机协同思想

4．2．2 人机协同解决排课问题的实现策略

4．3 数据结构设计

4．4 计算机排课过程

4．5 人工辅助排课过程

4．6 本章小结

第5章 实验结果分析

5．1 实验环境的搭建

5．2 实验结果及分析

5．3 算法合理性分析

5．4 本章小结

第6章 总结与展望

6．1 总结

6．2 展望

参考文献

攻读学位期间公开发表论文

致谢