论文导读:高职院校必须结合高职教育特点和本校实际情况开发合适的教学管理系统。而排课系统是教学管理系统中的一项重要内容。同时也是遗传算法中的适应度函数值和多目标优化中的目标函数值。排课系统,高职院校教学管理系统中的排课算法的实现。
关键词:高职院校,排课系统,数学模型,遗传算法
1.引言
近年来,高等职业教育己成为我国高等教育的一个重要组成部分。随着高等职业教育办学规模的不断扩大,市场需求的专业设置也更加灵活,职业技能培养的教学模式也体现出多样性,再加校企合作得愈加频繁,教学资源日益紧张。高职院校必须结合高职教育特点和本校实际情况开发合适的教学管理系统,而排课系统是教学管理系统中的一项重要内容,排课结果的优劣会直接影响学校的正常教学秩序,甚至影响教学质量。
2.基于遗传算法的课表问题分析
2.1课表问题的重要因素
班级、教师、教室、课程和时间是高职院校课程表问题的五个重要因素。
(1)班级:每个班级都有自己的编号和自己班级的名称。每个班级同一时间和同一地点不能同时上两门课程。
(2)教师:每个教师都有自己的编号和姓名。每个教师都有自己期望上课时间和期望上课方式。每个教师在同一时间和同一教室不能同时上两门课程。
(3)教室:每个教室都有编号和名称。每间教室同一时间只能接受一门课程的讲授,上课人数应该小于教室最大容量,但上课人数远小于教室最大容量也是不合适的。这可作为课程问题的一个优化目标。
(4)课程:每门课程都有编号和课程名称。一门课程通常由一位教师来讲授,具有相同课程的班级理论课可以合班上课,实训课再分班上课。
(5)时间:时间分为学期,周,天,时间段。通常一学期进行一次排课,每门课程要持续数周。论文格式,排课系统。通常高职院校中每天会有5个时段可以上课,上午2个,下午2个,晚上1个,而且每门课总是一次上2小节课。
2.2课表问题的多目标分析
高职院校课程表问题是一个多目标的组合规划问题。对于课程表问题来说,有时候无法获得足够多的约束,这样根据Pareto的最优解理论最后获得不可避免的只能是一个解集。我们期望从解集中获得能够令我们满意的相对最优解,它首先要满足不能发生任何冲突,不能发生诸如一个教室或一个教师或一个班级需要同时上两门课程的情况;其次它需要有较高的质量,符合科学,具有人性化。下面将具体分析怎样通过多目标优化来衡量一个排课方案的优劣。
(1)节次优度
节次优度表示的是一节课所占用的时间段中,教师和学生的工作、学习效率的高低或者说是一节课所占用的时间段的受欢迎程度。表1中给出了一个节次优度的实例。
表1 节次优度
|
周一 |
周二 |
周三 |
周四 |
周五 |
上午 |
1 |
0.92 |
0.95 |
0.94 |
0.93 |
0.9 |
2 |
0.85 |
0.9 |
0.88 |
0.84 |
0.8 |
下午 |
3 |
0.65 |
0.7 |
0.68 |
0.6 |
0.55 |
4 |
0.55 |
0.6 |
0.58 |
0.5 |
0.3 |
晚上 |
5 |
0.3 |
0.35 |
0.32 |
0.25 |
0.15 |
定义某个班级的节次优度Us为所有课程节次优度的平均值。

(2)班级时间安排均匀度
对于一个班级来说,较好的课程安排是各门课程的课次应该分布均匀,不应该出现一天课程安排得很满而另一天却没有课的情况。

其中,j2为授课班级总数,li为班级课次数量,σi为班级的课时分布日方差。
(3)课次间隔优度
对于同一门课程来说,两个课次之间最好有合适的间隔时间,这样既方便学生复习预习功课,也方便教师备课。表2就是一张课次间隔优度表,它对两个课次间隔天数进行评价。
表2 课次间隔优度表
间隔天数 |
当天 |
第二天 |
间隔1天 |
间隔2天 |
间隔3天以上 |
课次优度 |
0 |
0.25 |
0.75 |
1 |
0.5 |

其中,f是一个函数,记录间隔天数。Vki表示第k个班级第i门课程具有的课次数。
对于这三个主要目标的优化解决办法首先选择加权法,分别赋予0.3,0.3,0.4的权重,最后加权得到的总优度,同时也是遗传算法中的适应度函数值和多目标优化中的目标函数值。

3.课表问题的数学模型
假设学校有n1位教师,n2个授课班,n3门课程,n4间教室,p个时间段,k个自然班。
(1)教师集合: 。
(2)授课班集合: 。每个授课班包含一到多个自然班;自然班集合 ,每个自然班包含学生(M1,M2,…,Mn)人。
(3)课程集合: 。
(4)教室集合: 。每间教室可分别容纳学生(X1,X2,…,Xn)。
(5)时间集合: ,设定一周5天课,每天分为5个时间单元,每个单元为2个学时,即上午2个、下午2个、晚上1个时间单元,共25个时间段。论文格式,排课系统。
课表问题有m个目标函数,n个决策变量和c个约束条件,目标函数、约束条件和决策变量之间是函数关系。排课最优化目标可以表示为:

其中, 。x表示排课问题的决策向量,主要由时间和教室两方面因素决定。e(x)用来表示排课问题中的编排规则。y表示排课方案的目标向量,Y表示目标向量形成的目标空间。
4.排课系统的数据库设计
排课系统需要选择一个高效的存储系统以存储基础数据,以及存储排课结果。其中高效指的是有效数据和实际存放的数据之间的比率要高,冗余率不能超过20%。结合数字校园系统每年所产生的1G以上的数据,那几年后整个存储系统就会变得相当庞大,从而影响用户的访问速度。因此,选择一个高效的、冗余率低的存储系统,是该系统能否实现的一个关键技术指标。本系统采用SQL Server2005数据库,在ADO.NET中本身就对SQL Server数据库的连接、查询、更新、删除等操作进行了优化,在访问和执行的效率上都更高,而且,在安全性、稳定性等方面SQL Server也好得多。
本系统的主要数据表有:教学计划表、课程表、教师表、班级表、教室表、教室类型表等。
5.排课系统的实现
5.1 功能设计
高职院校教学管理系统中的排课系统功能的主要功能包括:开课计划管理、课程设置、自动排课、课表查询、课表打印、系统维护等。整个排课系统的功能结构如图1所示。
 
图1 排课系统功能图
5.2 实现方法
对教学进程表按预定的优先级排序,其优先级如下:
首先,将有特殊要求且安排在固定时间段的课程的优先级设为最高。
其次,按照周课时数由大到小的顺序设置优先级的高低。
最后,在相同的优先级条件下要先排要求有3节连排的课程,公选课的优先级要高于专业课的优先级。
系统在自动排课时除了遵循上述方式进行优先级外,还应按照如下规则进行课程设置:考虑课表问题的多目标分析结果,以及排课问题的基本约束条件。
本系统采用ASP.NET实现简单易用的动态Web页,其中脚本语言采用C#,后台数据库采用SQL Server 2005,通过ADO.NET连接数据库,并对数据库中的数据进行操作。主要步骤如下:
1)从数据库中检索将要编排的课程,并按照上述优先级的先后进行排序。
2)对将要编排的课程进行循环排课。
3)根据不同的要求调用不同的排课函数。
课程编排结束后,通过页面菜单选择查询界面,即可分别查询班级、教师及教室的课程表。为了实现课程安排的主观能动性,系统提供了手动调停课功能。论文格式,排课系统。论文格式,排课系统。在调整课程后,可以点击“冲突检测”来查看是否有课程或教室冲突。
5.3 测试与分析
迭代200次与300次的最终排课结果近似一致,仔细观测测试给出的排课数据,发现其优化速度存在一定的差别,这种差别是由遗传算法的“随机”特性所决定的。反复多次的测试表明,迭代到200代时,课表的最高适应度值将等于或超过1600。如图2所示。

图2 300次迭代的适应度值变化图
如图中所示,在0~100代的时候,遗传算法对系统适应度的提升是明显的,从200开始收敛于1600。这正是遗传算法的特点,它能够很快收敛于近优解。同时,排课数据测试显示,无冲突;合理安排特殊课程,如体育课和自习课;课程的离散度高。
6.结束语
高职学院教学资源紧张,突出表现在教师、实训室、机房这些硬件资源的紧缺。这样就造成了外聘教师多、固定时段上课多,教学时间集中,实训课程安排难等问题。论文格式,排课系统。这些问题都让每学期的排课任务变成了繁重而又困难的一项任务。论文格式,排课系统。针对高等职业教育的这些特点和现状,借鉴已有的排课系统的开发经验,本文对高职院校排课系统做了详细的研究,以重庆电子工程职业学院教务排课系统为背景,研究排课问题中的复杂因素和约束条件,给出了较合理的排课方案,并且在系统中加以实现和应用。
参考文献
[1]肖俊.遗传算法的工程应用[J].计算机科学,2005,11(32):247-250.
[2]王瑞峰.高职院校教学管理系统中智能排课算法的研究与实现[D].内蒙古:内蒙古大学,2009.
[3]陈谊等.基于优先级自动排课算法PCSA的设计与实现方案[J].北京工商大学学报(自然科学版),2002,20(2).
[4]王小平,曹立明.遗传算法一理论、应用与软件实现[M].西安:西安交通大学出版社,2002.
[5]苏仰娜.基于遗传算法的优化排课系统[J].河南大学学报(自然科学版),2005,35(1):77-78.
[6]李全安等.成人高等学历教育排课管理系统的设计与实现[J].高等函授学报(哲学社会科学版),2009,22(5):21-22.
|