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

时间:2021-08-31

  摘 要 本文在课程表问题分析的基础上,建立了课程表的空间数学模型,并据此模型推出排课算法,建立了排课系统的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)

【课程表的空间模型及排课算法分析的教育论文】相关文章:

1.算法设计与分析课程论文

2.关于描述CRP模型中的聚类算法的论文

3.信息技术课程教学分析的优秀论文

4.体育场馆经营管理模型建立研究与分析的论文

5.职业教育项目课程探究论文

6.活动课程的心理教育价值论文

7.学前教育专业课程论文

8.教育技课程教学设计论文