课程表的空间模型及排课算法分析

1、.课程表的空间模型及排课算法分析摘  要 本文在课程表问题分析的基础上，建立了课程表的空间数学模型，并据此模型推出排课算法，建立了排课系统的E-R图，描述了采用软件实现排课的计算过程。     关键字 排课算法 数学模型 E-R图 1  引言    随着计算机的普及，如何利用软件系统来进行课程编排，是各个高校面临的问题。目前已经有一些比较成熟的排课软件，其大部分作为教务管理系统的一个子系统存在，其排课算法和数据采集效率及排课效率都各不相同，各有特点。高校课程表排课设计因素多和结构复杂被归结为NPC(Non

2、deterministic 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)，问题的求解目的是找出这些序列的每个元素之间的一一对应关系，其中这些元素的组合要满足一定的对应关系

3、。诸如：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（

4、C1，S1，W1，T1），C，S坐标上对应的点是班级排课序列，空间点P1，P2即为求的开课的时间和地点。3  排课问题求解方法    根据图1描述空间点情况，排课问题的解就是空间中对应的交点P1，P2等。求解过程如下：    (1)确定CS轴上的点：此过程就是给班级排课，某班（S）上某门课程（C），在什么类型的教室上课（O），每周几课时（V），开课时间（开课周数，如单周开课、双周开课、510周开课等）（Y）。    (2)确定NR轴上的点：此过程为列出所有可用教室。此轴上应该列出每节（N）所有可

5、用的教室资源（R），此外，每个教室对应有教室类型（O）。    (3)确定T轴上的点：此轴上列出所有的教师资源（T）。    (4)确定TCS平面上的点：此过程就是安排教学任务，也就是教师任课选择。    (5)寻找TCSNR空间上的点：此过程就是排课，根据教学任务列出的教室类型，查找符合条件的NR上的点，从而完成排课。    在排课求解过程中，潜在几个约束必须要满足：    (1) 一个班级在某一节课时只能在一个地点上课；如得到P1前，必须检查

6、S1在N1时刻是否已经存在一个交点。    (2) 一个教师在某一节课时只能在一个地点上课；如得到P1前，必须检查T1在N1时刻是否已经存在一个交点。    (3) 一个地点在某一节课时只能有一个教学任务；如得到P1前，必须检查N1R1是否已经存在交点，合班教学除外。    (4) 一个地点的座位数是否大于上课学生总数；如得到P1前，必须检查R1座位数是否大于S1。4  数据库建模    根据对排课问题的求解方法，定义数据库E-R图，如图2所示。在此E-R模型中，教

7、学任务的定义十分重要，在此将教学任务的主要属性都列出，教学任务主要属性有班级、课程、教师、开课周、周课时、上课所需教室类型等。在设计中，开课周用20个字符来表示是否安排教学计划（前提为学期教学周定义为20周，若学期教学周为18周，则用18个字符），若某周安排上课，则对应字符为1，否则为0，如：某课程在一学期每周都安排上课，则字符串为“11111 11111 11111 11111”，某课程在一学期只有单周安排上课，则字符串为“10101010101010101010”，某课程在一学期只有双周安排上课，则字符串为“01010101010101010101”，某课程在一学期第5到10周安排上课，则

8、字符串为“00001111110000000000”，依此类推。此外，教学任务对于合班上课的处理可以虚拟为一条教学任务，这样可在排课过程中保持教学任务与教室、时间的一一对应关系。 5  排课过程    排课遵循排课问题求解方法所描述过程，首先是教学任务数据的采集，采用Web模式，各教学部门首先对于班级排课，然后对于教师排课，然后选择上课场地类型，并且选择对应的周学时，从而生成教学任务。采用此方式，降低教务部门的压力，各系的教学任务由个系自己提交完成，然后教务处审核，通过后即可进行排课任务。    排课程序采用VC程序实现，排

9、课过程采用自动排课和手动调课结合的方式，自动排课具体方法就是将教学任务安排到时间与地点构成的点上，并同时检查是否同时满足约束4个约束条件，如果满足，则教学任务安排上课完毕，并对于教学任务做已安排标记；否则，继续下一个时间与地点构成的点并检查约束。手动排课对于自动排课不完或者不合理的地方进行手动调整，使课程表更加合理。排课过程需要按照一定的顺序进行，即对于教学任务中要求的资源相对短缺的先进行计算排课，对于一般要求或者资源相对充裕的后排课，这就要求排课前必须先对于全部资源和教学任务进行计算，由程序来统计出上课需求资源和实际资源，从而进行优先级别排序，依顺序进行排课。  

10、0; 排课过程中需要考虑的特殊问题的处理：    (1) 上大课（合班上课）的处理，合班上课会违反第(3)个约束，因此对于合班上课首先将其教学任务合并。    (2) 公共选修课的处理：全校范围内选修某门课程，根据学生选修情况分班，该分班结果为虚拟班级，然后对虚拟班级排课，此外，控制选修课程在固定的时间范围开设，以免违反第(2)个约束。    (3) 双肩挑教师上课时间的处理：对于双肩挑教师，设定某一时间段统一不排课。    (4) 双职工教师上课时间的处理：处于人性化考虑，属于此类教师，3、4节不能同时排课。6  结束语    本文描述了课程表的空间点阵模型及排课算法，另外给出了课程表的E-R图，可以据此顺利实现一个排课系统，具有较高的实用价值。本文所描述的算法已经对于1500条实际教学任务的学校进行了2个学期的排课，结果比较理想，因此具有一定的实用性，此外对于课程表排好后，采用Web方式发布，随时随地可以查询和打印，方便快捷。参考文献1潘以锋.高校智能排课系统的算法J.上海师范大学学报(自然科学版)，2006，(10)2花鹏飞.课程表问题的数学分析J.