课程表空间模型及排课算法
2星 需积分: 10 170 浏览量
2011-05-05
20:36:29
上传
评论 2
收藏 92KB DOC 举报 
摘要本文在课程表问题分析的基础上，建立了课程表的空间数学模型，并据此模
型推出排课算法，建立了排课系统的 E-R 图，描述了采用软件实现排课的计算过程。
关键字排课算法数学模型E-R 图
1 引言
随着计算机的普及，如何利用软件系统来进行课程编排，是各个高校面临的问题。目前已经
有一些比较成熟的排课软件，其大部分作为教务管理系统的一个子系统存在，其排课算法和数
据采集效率及排课效率都各不相同，各有特点。高校课程表排课设计因素多和结构复杂被归结
为 NPC(Nondeterministic Poly-nominal Complexity)问题。本文在文献
[2]
提出的课程表的
矢量空间的概念基础上，进一步完善设计及算法，并实现一个更具体可行的排课过程。
2 排课问题描述
课程表的问题，是解决教师、课程、班级、教室、时间的组合问题，这个问题的数学描述是
给定一组学生 S(S1，S2
，
……Si)
，
一组课程 C (C1，C2，……Cj)，一组教师 T (T1，T2，
……Tk)，一组教室 R (R1，R2，……Rm)，一个时间序列 N(N1，N2，……Nn)，问题的求
解目的是找出这些序列的每个元素之间的一一对应关系，其中这些元素的组合要满足一定的对
应关系。诸如：① S-C 之间的对应关系；② T-C 之间的对应关系；③ R-C 之间的对应关系；
④ T-N 之间的对应关系；⑤ S-N 之间的对应关系；这些对应关系是主要考虑的限制条件，还有
一些次要的限制条件。这是一个复杂的 NPC 问题，它的求解是一个完整类的求解问题。
在文献
[2]
中使用代数的矢量空间的概念，将 S，C，T，N，R 中每个组中的每一个元素的组
合用 5 维空间的点来表示，合并 S 和 C 为一个维度，合并 N 和 R 为一个纬度，可得 3 维空间
点阵。本文引入教学任务概念，如图 1 所示，本文进一步将空间点阵细化，明确具体开课点在
空间上的交点来源及含义。在 T，C，S 对应的平面上的点定义为教学任务
1（C1，S1，W1，T1），C，S 坐标上对应的点是班级排课序列，空间点 P1，P2 即为求的开
课的时间和地点。
3 排课问题求解方法
资源评论
linhucong1102013-04-23这个文档对我的帮助也不大- donar2012-09-21写得太简单，也没涉及具体的算法，这个文档对我的帮助不大，没什么参考价值，建议别下载。
