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

　　摘要本文在课程表问题分析的基础上，建立了课程表的空间数学模型，并据此模型推出排课算法，建立了排课系统的ER图，描述了采用软件实现排课的计算过程。
　　关键字排课算法数学模型ER图
　　1引言
　　随着计算机的普及，如何利用软件系统来进行课程编排，是各个高校面临的问题。目前已经有一些比较成熟的排课软件，其大部分作为教务管理系统的一个子系统存在，其排课算法和数据采集效率及排课效率都各不相同，各有特点。高校课程表排课设计因素多和结构复杂被归结为NPC（NondeterministicPolynominalComplexity）问题。本文在文献〔2〕提出的课程表的矢量空间的概念基础上，进一步完善设计及算法，并实现一个更具体可行的排课过程。
　　2排课问题描述
　　课程表的问题，是解决教师、课程、班级、教室、时间的组合问题，这个问题的数学描述是给定一组学生S（S1，S2，Si），一组课程C（C1，C2，Cj），一组教师T（T1，T2，Tk），一组教室R（R1，R2，Rm），一个时间序列N（N1，N2，Nn），问题的求解目的是找出这些序列的每个元素之间的一一对应关系，其中这些元素的组合要满足一定的对应关系。诸如：SC之间的对应关系；TC之间的对应关系；RC之间的对应关系；TN之间的对应关系；SN之间的对应关系；这些对应关系是主要考虑的限制条件，还有一些次要的限制条件。这是一个复杂的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），开课时间（开课周数，如单周开课、双周开课、510周开课等）（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数据库建模
　　根据对排课问题的求解方法，定义数据库ER图，如图2所示。在此ER模型中，教学任务的定义十分重要，在此将教学任务的主要属性都列出，教学任务主要属性有班级、课程、教师、开课周、周课时、上课所需教室类型等。在设计中，开课周用20个字符来表示是否安排教学计划（前提为学期教学周定义为20周，若学期教学周为18周，则用18个字符），若某周安排上课，则对应字符为1，否则为0，如：某课程在一学期每周都安排上课，则字符串为11111111111111111111，某课程在一学期只有单周安排上课，则字符串为10101010101010101010，某课程在一学期只有双周安排上课，则字符串为01010101010101010101，某课程在一学期第5到10周安排上课，则字符串为00001111110000000000，依此类推。此外，教学任务对于合班上课的处理可以虚拟为一条教学任务，这样可在排课过程中保持教学任务与教室、时间的一一对应关系。
　　5排课过程
　　排课遵循排课问题求解方法所描述过程，首先是教学任务数据的采集，采用Web模式，各教学部门首先对于班级排课，然后对于教师排课，然后选择上课场地类型，并且选择对应的周学时，从而生成教学任务。采用此方式，降低教务部门的压力，各系的教学任务由个系自己提交完成，然后教务处审核，通过后即可进行排课任务。排课程序采用VC程序实现，排课过程采用自动排课和手动调课结合的方式，自动排课具体方法就是将教学任务安排到时间与地点构成的点上，并同时检查是否同时满足约束4个约束条件，如果满足，则教学任务安排上课完毕，并对于教学任务做已安排标记；否则，继续下一个时间与地点构成的点并检查约束。手动排课对于自动排课不完或者不合理的地方进行手动调整，使课程表更加合理。排课过程需要按照一定的顺序进行，即对于教学任务中要求的资源相对短缺的先进行计算排课，对于一般要求或者资源相对充裕的后排课，这就要求排课前必须先对于全部资源和教学任务进行计算，由程序来统计出上课需求资源和实际资源，从而进行优先级别排序，依顺序进行排课。排课过程中需要考虑的特殊问题的处理：
　　（1）上大课（合班上课）的处理，合班上课会违反第（3）个约束，因此对于合班上课首先将其教学任务合并。
　　（2）公共选修课的处理：全校范围内选修某门课程，根据学生选修情况分班，该分班结果为虚拟班级，然后对虚拟班级排课，此外，控制选修课程在固定的时间范围开设，以免违反第（2）个约束。
　　（3）双肩挑教师上课时间的处理：对于双肩挑教师，设定某一时间段统一不排课。
　　（4）双职工教师上课时间的处理：处于人性化考虑，属于此类教师，3、4节不能同时排课。
　　6结束语
　　本文描述了课程表的空间点阵模型及排课算法，另外给出了课程表的ER图，可以据此顺利实现一个排课系统，具有较高的实用价值。本文所描述的算法已经对于1500条实际教学任务的学校进行了2个学期的排课，结果比较理想，因此具有一定的实用性，此外对于课程表排好后，采用Web方式发布，随时随地可以查询和打印，方便快捷。
　　参考文献
　　〔1〕潘以锋。高校智能排课系统的算法〔J〕。上海师范大学学报（自然科学版），2006，（10）
　　〔2〕花鹏飞。课程表问题的数学分析〔J〕。中国科技论文在线
　　〔3〕李增智等。课程表问题的一种混合型模拟退火算法〔J〕。西安交通大学学报，Vo。l37，No4（2003）
　　〔4〕郭方铭等。采用增强学习算法的排课模型〔J〕。计算机工程与设计，Vol。24，No11（2003）
　　〔5〕陶滔等。多维冲突在排课算法中的应用〔J〕。华东地质学院学报，Vol。24，No3（2001）