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

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

2、算法和数据采集效率及排课效率都各不相同，各有特点。高校课程表排课设计因素多和结构复杂被归结为NPC(Nondeterministic Poly-nominal Complexity)问题。本文在文献提出的课程表的矢量空间的概念基础上，进一步完善设计及算法，并实现一个更具体可行的排课过程。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问题，它的求解是一个完整类的求解问题。   在文献中使用代数的矢量空间的概念，将S，C，T，N，R 中每个组中的每一个元素的组合用5 维空间的点来表示，合并S和C为一个维度，合并N和R为一个纬度，可得3维空间点阵。本文引入教学任务概念，如图1所示，本文进一步将空间点阵细化，明确具体

4、开课点在空间上的交点来源及含义。在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轴上的点：此过程为列出所有可用

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

6、在一个交点。   (2) 一个教师在某一节课时只能在一个地点上课；如得到P1前，必须检查T1在N1时刻是否已经存在一个交点。   (3) 一个地点在某一节课时只能有一个教学任务；如得到P1前，必须检查N1R1是否已经存在交点，合班教学除外。   (4) 一个地点的座位数是否大于上课学生总数；如得到P1前，必须检查R1座位数是否大于S1。4  数据库建模            务对于合班上课的处理可以虚拟为一条教学任务，这样可在

7、排课过程中保持教学任务与教室、时间的一一对应关系。5  排课过程   排课遵循排课问题求解方法所描述过程，首先是教学任务数据的采集，采用Web模式，各教学部门首先对于班级排课，然后对于教师排课，然后选择上课场地类型，并且选择对应的周学时，从而生成教学任务。采用此方式，降低教务部门的压力，各系的教学任务由个系自己提交完成，然后教务处审核，通过后即可进行排课任务。   排课程序采用VC程序实现，排课过程采用自动排课和手动调课结合的方式，自动排课具体方法就是将教学任务安排到时间与地点构成的点上，并同时检查是否同时满足约束4个约束条件，如果满足，则教学

8、任务安排上课完毕，并对于教学任务做已安排标记；否则，继续下一个时间与地点构成的点并检查约束。手动排课对于自动排课不完或者不合理的地方进行手动调整，使课程表更加合理。排课过程需要按照一定的顺序进行，即对于教学任务中要求的资源相对短缺的先进行计算排课，对于一般要求或者资源相对充裕的后排课，这就要求排课前必须先对于全部资源和教学任务进行计算，由程序来统计出上课需求资源和实际资源，从而进行优先级别排序，依顺序进行排课。   排课过程中需要考虑的特殊问题的处理：   (1) 上大课（合班上课）的处理，合班上课会违反第(3)个约束，因此对于合班上课首先将其教学任务合

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