课程表的空间模型及排课算法分析的教育论文

　　摘 要 本文在课程表问题分析的基础上，建立了课程表的空间数学模型，并据此模型推出排课算法，建立了排课系统的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 排课问题求解方法
　　根据图1描述空间点情况，排课问题的解就是空间中对应的交点P1，P2等。求解过程如下：
　　(1)确定CS轴上的点：此过程就是给班级排课，某班（S）上某门课程（C），在什么类型的教室上课（O），每周几课时（V），开课时间（开课周数，如单周开课、双周开课、5~10周开课等）（Y）。
　　(2)确定NR轴上的点：此过程为列出所有可用教室。此轴上应该列出每节（N）所有可用的教室资源（R），此外，每个教室对应有教室类型（O）。
　　(3)确定T轴上的点：此轴上列出所有的教师资源（T）。
　　(4)确定TCS平面上的点：此过程就是安排教学任务，也就是教师任课选择。
　　(5)寻找TCSNR空间上的点：此过程就是排课，根据教学任务列出的教室类型，查找符合条件的`NR上的点，从而完成排课。
　　在排课求解过程中，潜在几个约束必须要满足：
　　(1) 一个班级在某一节课时只能在一个地点上课；如得到P1前，必须检查S1在N1时刻是否已经存在一个交点。
　　(2) 一个教师在某一节课时只能在一个地点上课；如得到P1前，必须检查T1在N1时刻是否已经存在一个交点。
　　(3) 一个地点在某一节课时只能有一个教学任务；如得到P1前，必须检查N1R1是否已经存在交点，合班教学除外。
　　(4) 一个地点的座位数是否大于上课学生总数；如得到P1前，必须检查R1座位数是否大于S1。
　　4 数据库建模
　　根据对排课问题的求解方法，定义数据库E-R图，如图2所示。在此E-R模型中，教学任务的定义十分重要，在此将教学任务的主要属性都列出，教学任务主要属性有班级、课程、教师、开课周、周课时、上课所需教室类型等。在设计中，开课周用20个字符来表示是否安排教学计划（前提为学期教学周定义为20周，若学期教学周为18周，则用18个字符），若某周安排上课，则对应字符为1，否则为0，如：某课程在一学期每周都安排上课，则字符串为＂11111 11111 11111 11111＂，某课程在一学期只有单周安排上课，则字符串为＂10101010101010101010＂，某课程在一学期只有双周安排上课，则字符串为＂01010101010101010101＂，某课程在一学期第5到10周安排上课，则字符串为＂00001111110000000000＂，依此类推。此外，教学任务对于合班上课的处理可以虚拟为一条教学任务，这样可在排课过程中保持教学任务与教室、时间的一一对应关系。
　　5 排课过程
　　排课遵循排课问题求解方法所描述过程，首先是教学任务数据的采集，采用Web模式，各教学部门首先对于班级排课，然后对于教师排课，然后选择上课场地类型，并且选择对应的周学时，从而生成教学任务。采用此方式，降低教务部门的压力，各系的教学任务由个系自己提交完成，然后教务处审核，通过后即可进行排课任务。 排课程序采用VC程序实现，排课过程采用自动排课和手动调课结合的方式，自动排课具体方法就是将教学任务安排到时间与地点构成的点上，并同时检查是否同时满足约束4个约束条件，如果满足，则教学任务安排上课完毕，并对于教学任务做已安排标记；否则，继续下一个时间与地点构成的点并检查约束。手动排课对于自动排课不完或者不合理的地方进行手动调整，使课程表更加合理。排课过程需要按照一定的顺序进行，即对于教学任务中要求的资源相对短缺的先进行计算排课，对于一般要求或者资源相对充裕的后排课，这就要求排课前必须先对于全部资源和教学任务进行计算，由程序来统计出上课需求资源和实际资源，从而进行优先级别排序，依顺序进行排课。 排课过程中需要考虑的特殊问题的处理：
　　(1) 上大课（合班上课）的处理，合班上课会违反第(3)个约束，因此对于合班上课首先将其教学任务合并。
　　(2) 公共选修课的处理：全校范围内选修某门课程，根据学生选修情况分班，该分班结果为虚拟班级，然后对虚拟班级排课，此外，控制选修课程在固定的时间范围开设，以免违反第(2)个约束。
　　(3) 双肩挑教师上课时间的处理：对于双肩挑教师，设定某一时间段统一不排课。
　　(4) 双职工教师上课时间的处理：处于人性化考虑，属于此类教师，3、4节不能同时排课。
　　6 结束语
　　本文描述了课程表的空间点阵模型及排课算法，另外给出了课程表的E-R图，可以据此顺利实现一个排课系统，具有较高的实用价值。本文所描述的算法已经对于1500条实际教学任务的学校进行了2个学期的排课，结果比较理想，因此具有一定的实用性，此外对于课程表排好后，采用Web方式发布，随时随地可以查询和打印，方便快捷。
　　参考文献
　　[1]潘以锋.高校智能排课系统的算法[J].上海师范大学学报(自然科学版)，2006，(10)
　　[2]花鹏飞.课程表问题的数学分析[J].中国科技论文在线
　　[3]李增智等.课程表问题的一种混合型模拟退火算法[J].西安交通大学学报，Vo.l37，No 4（2003）
　　[4]郭方铭等.采用增强学习算法的排课模型[J].计算机工程与设计，Vol.24，No11（2003）
　　[5]陶滔等.多维冲突在排课算法中的应用[J].华东地质学院学报，Vol.24，No 3 (2001)