高校排课

高校排课（精选十篇）

高校排课 篇1

关键词：高校排课,遗传算法

0 引言

课表问题又称为时间表问题(Timetable Problem),是一个多因素的优化决策问题,也是组合规划中的典型问题。S.Even等人在1975年的研究中证明了排课问题是一个NP-Complete问题,即若是用“穷举法”之外的算法找出最佳解是不可能的[1]。

早在上个世纪50年代末,国外就有人开始研究课表编排问题。1962年,Gotlieb曾提出一个课表问题的数学模型[2]。进入九十年代以后,国外对课表问题的研究十分活跃,比较有代表性的有印度的Vastapur大学管理学院的Arabinda Tripathy、加拿大Montreal大学的Jean Aubin和Jacques Ferland等。国内对课表问题的研究开始于20世纪80年代初期,具有代表性的有:南京工学院的UTSS(A University Timetable Scheduling System)[3],清华大学的系统TISER(Timetable SchedulER)[4]等。这些系统大都是模拟手工排课过程,以“班”为单位,运用启发式函数来进行编排的。

1 高校排课方案研究

1.1 排课问题的描述

课表的编排问题涉及到班级、时间、课程、教师、教室等五个相互制约的因素[5]。课表问题的编制过程就是为每个班的每门课寻找一个老师在合适的时间和教室,在安排时不能发生冲突,也就是说必须满足以下必要条件:

(1)任一时间,一个老师至多安排一次授课。(2)任一时间,一个班至多安排一次上课。(3)任一时间,一个教室至多安排一次授课。

除上述条件外,排课过程中还应满足以下经验条件:

(1)周课时多于两个课时的课程的安排应当尽量分散,方便教师备课和学生复习,而且同一门课程应尽量安排在一个教室。(2)尽量将课程安排在好的教学时段(如一二节比五六节好)。(3)为确保上课质量,提高教学效率,应尽量配合教师个人的生理时钟,尽量将课程安排到教师个人合适时段,而不应当安排在不合适时段。

一个好的课表就是在满足所有必要条件的基础上更多地去满足经验条件的安排。

1.2 时间安排算法的设计与实现

1.2.1 编码及其染色体表示

假设每周可用时间段有n个,全院有m个班级,则周课表即为以n个时间段为行,每个班级为列所形成的一个二维表。对于每个班级而言,可以将课程和教师当作同一变量考虑。把某个班固定要上的这组课看作是基因,该基因由课程编号(或授课教师代码)和时间段状态码S(S=0时表示这个时间段没被任何课程使用,S=1时表示这个时间段已被某门课程使用)组成,而一个染色体就是由所考虑的m个班级和n个时间段所组成的二维表。

1.2.2 初始种群

对每一个班级而言,首先产生随机数(1~n),如果该位置所对应的时间段的状态码S=0,则将优先级高的课程编号填入二维表中对应的相应位置,并将时间段状态S设为1;如果该位置所对应的状态码S=1,则重新产生随机数。如果该课程一周的课时总数超过2,则继续产生随机数在空闲的相应位置填入课程编号,直到这门课程的周课时达到要求,那么就可以接着安排下一门课程了。重复上述过程,直到所有优先级的课程完成安排,然后安排优先级低的课程。

有m个班级,则上述过程进行m次,这样就产生了一个染色体。根据本文设计的编码及染色体表示,不会出现同一时间一个班级上多门课的情况,但是有可能出现同一教师在同一时间给不同班级上课的情况,在染色体中具体表现为同一行中有相同的教师编码。因此要采取修复操作,将冲突元素和随机元素进行交换,解决这个冲突,这样就可以产生可行的个体。

重复上述产生可行个体的过程,根据给定的种群规模的大小产生一定量的个体(即一点数量的初始课程表)组成可行初始种群。

1.2.3 适应度函数

适应度函数的设计是排课问题遗传算法设计的关键。在适应度函数中考虑三点:第一点是时间段优化(每门课程尽量安排好的时间段),第二点是时间段组合优化(时间段组合优化是针对周课时多于2个课时的课程,为了获得良好的教学效果,就应该保证有合适的上课时间间隔),第三点是同一时间段课程数目优化(为了在安排教室的过程中,不至于出现某个时间段课程过多而导致教室不足的情况,所以要限制每个时间段的课程数目)。

考虑上述各个因素之后,定义适应度函数为:

其中coursenum表示所有的课程数目,timenum表示所有的时间段数目,故表示课程ci占用时间段的期望值,表示课程ci时间段组合的期望值,为时间段tj内上课的班级比例的期望值,f是适应度函数。适应度值越大,表示课表的编排越合理和高效。

1.2.4 遗传操作

当创建好初始的可行种群后,就可以利用遗传算法从可行解出发寻求满意解。

(1)选择操作。本文采用轮盘赌选择[6]方法,具体实现时采用的步骤如下:

step1:将所有个体的适应度函数值相加得到fTotal;

step2:在0~fTotal范围产生一个随机数r;

step3:choice=0,cTotal=0,i=1,其中choice表示轮盘赌选择出来的个体,cTotal表示已经累加的适应度函数值,i表示适应度函数值即将被累加的个体,f(i)表示第i个个体的适应度函数值,i=0是为了让累加过程从第一个个体开始;

step5:如果cTotal>r,则令choice=i,结束选择过程;否则i=i+1,继续执行step4,直到i等于种群规模。

(2)自适应交叉概率和变异概率。交叉概率和变异概率的选取在相当大程度上影响遗传算法的收敛速度和近优解的质量,为加快遗传算法的搜索效率和有效地防止限于局部最优解,自适应地调整交叉概率Pc和变异概率Pm。

本文采用的自适应遗传算子为:

其中:fmax是群体的最大适应度函数值,favg是群体的平均适应度函数值,fc是进行交叉的两个染色体传中适应度函数值较大者,fm是变异串的适应度函数值。k1=0.7,k2=0.001,这两个数值都是经验值,也可以取其他的值,但由于交叉操作发生的可能性较大,而变异操作发生的可能性相对较小,所以在确定这两个参数的值时保证k1大于0.5,而k2应小于0.001。

用自适应的交叉概率和变异概率的定义可以看出,当前代的最优个体仍然保留,但较优的个体要多参加交叉和变异,以便搜索更多的区域,从而探查到更好的解。

(3)交叉、变异操作。从前面的介绍可知,初始种群均为可行解,但这些可行解经过交叉、变异操作后可能有新的冲突产生从而变为不可行解,所以要对交叉、变异后的个体及时检查冲突情况并进行修复,从而保证每代个体的可行性。由于父代的无冲突性,因此交叉后的冲突检查只需对两个子代交叉所在列进行,修复工作也只需在该列进行。

1.2.5 课表问题遗传算法的结束条件

如果不为遗传算法设置结束条件,那么遗传算法将无限执行下去,因为算法本身并不知道该怎样结束,所以,必须设置遗传算法的结束条件。

在本文中,算法的结束条件是达到了适应度的目标或者迭代了一定的次数,这样就可以让遗传算法以合适的条件结束了。

2 结束语

本文针对排课系统的特点,利用改进后的遗传算法对课程进行时间分配。因为排课问题是一个多学科交叉的难解问题,而时间和精力有限,所以在本文这个排课算法中还有很多实际没有考虑到的问题,例如如何更加合理的解决“甩课问题”、老师的不上某些时间段、只上某些时间段等特殊需求没有被考虑进来、遗传算法的结束条件的合理设置、交叉概率和变异概率如何设置的合理有效等,这些都是我们以后研究的方向,排课算法还需要我们去进一步完善。本文只限于理论研究,如何利用现有工具实现排课系统,也是我们以后的研究目标。

参考文献

[1]张春梅,行飞.用自适应的遗传算法求解大学课表安排问题[J].内蒙古大学学报(自然科学版).2002(7):459-462.

[2]玄光男,程润伟.遗传算法与工程设计[M].科学出版社.2000.

[3]汪力君.分治算法在排课系统中的分析与应用[J].安徽建筑工业学院学报(自然科学版).2007,15(6):60-62.

[4]詹芹,廖惠芬.高校排课系统的设计与实现[J].赤峰学院学报(自然科学版).2009,25(2):40-41.

[5]焦爱胜,谢娟文.基于遗传算法的排课系统的研究[J].兰州工业高等专科学校学报.2008,15(1):15-17.

高校排课 篇2

【摘要】高校课程表是高校教学运行的重要组成部分,统筹兼顾合理化和“以人为本”的课程表编排,不仅可以稳定教学运行,还能调动和激发教师和学生的积极性。通过对课表编排各个环节的控制,使“以人为本”的思想贯彻始终。

【关键词】高校课程 课程编排 以人为本

高校的课程表是教学运行的基础,课程表的合理化是教学稳定运行的前提。深入学习科学发展观使我们了解,课程表不仅应该具备合理性,更要体现“以人为本”的思想。课表的编排工作大体可分为准备、编排、征求意见、调整、实施、反馈情况几个环节[1],“以人为本”应贯穿于排课中的各个环节。

1“以人为本”的课表编排基础―合理化和人性化排课前准备工作

课表编排是一项既复杂又精细的系统性工作,既要遵循科学的原则,又要合情合理,保证无差错、无矛盾[2]。因此做好准备工作,是实现课表“以人为本”的前提。

1.1 严格执行教学计划,是排课“以人为本”的基础

课表的编排应以教学计划为依据,严格按照教学计划执行:包括学校校历,学年学期具体的教学任务,有关教学改革与教学组织管理的具体政策、法规、要求等,不得脱离总体目标。教学任务的落实应当以现行的教学计划为准,由各学院等教学单位按照学校的具体要求进行填报。各教学单位在填报教学任务时要根据本单位的实际情况尽可能安排最为合适的教师上课,对于需要合班的课程要进行合理的编班[3]。编排课程时严格保证课程的学时、性质与教学计划一致,不能任意更改,合理安排合班课程,实现最终培养目标。对于如因“国庆节”等假期公休、学生实践周、教师带实习,应该在排课前将此时段空出,避免调课,影响教学秩序稳定。

1.2 征求排课意见,实践课表“以人为本”

课表编排要做到以人为本,就要了解教师和学生的各种需要,并尽最大努力为学生和教师的各种需要改善外部条件,激发教师和学生的主动性、积极性和能动性[4]。因此,在课表编排前,向教师和学生征求排课要求,并对要求进行归类,对于一些有特殊困难的`教师和学生,统筹考虑课表编排。

2“以人为本”的课表编排

高校排课“以人为本”的“人”即指学生和教师。学生和教师是高校办学的主体,教师是教学和科研工作的主体,学生是学习过程的主体。课表编排作为教学管理的一项重要内容,其核心和动力是教师和学生,是教师和学生间的教与学,是教师和学生的创造性和能动性[3]。

2.1 把“以学生为根本”作为出发点

排课始终要本着“以学生为本”的原则,以“一切为了学生”为出发点。

(1)遵从学生的认知规律,合理安排课程时间

按照学生学习的注意力和大脑调节功能的生理及心理特点[5],在安排课程时注意课程的搭配,如难度大的课程和较容易的课程,理科和文科课程,基础课和专业课、理论课和实践课,要均衡疏密,合理分布。

(2)不同类别学生,采用侧重不同的课程编排

学生可以按照年级、学科等进行分类。按照类别编排课程,可以激发学生学习的主动性和积极性。不同年级的学生,编排的课程的侧重不同;不同学科的学生,应按照专业培养目标,调整课程的重心,编排课程。编排课表时,应将一天中最佳时段分给重点课程。

(3)课程编排应注意动静匹配,使学生能够减轻负担,劳逸结合,从而提高学习乐趣和学习效率[6]。

学科课程有理论课和实践课。理论课以理论学习为主,形式为“静”,实践类课程主要培养学生的实际操作能力和技能,形式为“动”。实践类的课程进度要与理论课应相互配合,因此在课程安排上,两类课程时间相互搭配,课程内容相互辅助,以此提高学生学习乐趣和学习效率。通常,实践类课程编排受到场地、实验室、教师资源的限制,因此在安排这些课程时,需要统筹考虑。

(4)服务学生,合理化课表空间安排

将“以学生为本”的思想落实编排课表的方方面面。在尽量保证每个班级上课教室相对稳定的前提下,可使班级数目少的课程流动,合班课程尽可能保持稳定,流动尽量保证在同一个楼层,避免因一天之内因频繁更换上课地点混淆教室,或下课时间换教室带来的教学楼内人多拥挤的现象。另外,单双周安排的课程,尽量保持在同一个教室里或同一楼层,避免学生因混淆单双周上课地点。

2.2 充分体现教师的教学主导地位

教师是教学行为的实施者,在“教”和“学”的过程中起着主导性的作用。

(1)保证教师在充沛的精神状态下完成教学任务

排课时应该考虑到教师的业务水平、教学特点、身体状况、所承担的教学任务和是否有特殊要求等。平均教师周工作量,避免因一天内课程过多超负荷工作,影响教师的教学效果和身体健康。教师是教学质量得以保证的关键,即使是老教师上课前也需要备课,从教师课表出发尽可能地给教师充分的备课时间[2]。

(2)统筹安排,兼顾合理化与人性化

课表的编排应当从实际出发,对部分教师的合理要求具体分析、区别对待。如对待怀孕、年长、路途较远、有社会兼职教师的合理要求,在不影响全局的情况下,应给予适当照顾。对局部合理而全局有困难的要求,应作好解释,排课时视具体情况而适当处理。排课期间或课表排定后部分教师确因教学需要调整的,在办理相关手续后也应给予调整[2]。

(3)调动教师积极性,提升教学水平

尽量保证同一教研室的任课教师有共同空闲时段,以方便任课教师集体备课、讨论、研究,进行教研室活动。尽量错开平行课程的上课时间,方便教师相互听课学习,汲取经验,提升教学水平。另外,对于有些教师因科研或进修学习需要而要求课时适当集中的,应酌情考虑解决。

3“以人为本”课表编排反馈机制

课表编排是为学校、教师、学生服务的,课表质量的高低必须由学校、教师、学生等方面给出的综合评价指标来反映。在制定综合评价指标时,要站在课表编排过程中所涉及的学校、教师,学生的角度思考和分析课表的诸多因素。如:采用学生问卷调查、计算教学场地利用率、教师的满意度[6]。针对反馈情况,进行分析,对于不合理之处予以及时调整。

4 结语

课表是学校一切教学活动的指挥棒,课表质量的高低决定了学校的教学质量水平;是学校教学管理实现“高标准,精细化”的基础[6]。以“以人为本”的思想指导课表编排,是时代和教育发展的要求,也是服务与管理相辅相成的体现。

参考文献

[1] 赵峰,等.课表编排初探.山东体育学院学报,1995,(26)77-79.

[2] 贺纹.浅析以人为本的高校课表编排.青年科学,,(3):87.

[3] 鲁井兰.高校课表编排的原则与要点探析.科学教育论坛,,(1):87-89.

[4] 陈榕坤.略谈高校课表编排的人本化.中国科技信息,,(5):138-142.

[5] 孔风琴.关于高职院校排课的若干思考科教纵横.2009,(4):236.

基于遗传算法的高校排课问题分析 篇3

【关键词】遗传算法排课问题分析

遗传算法是近些年发展起来的一种崭新的全局优化算法，它借助了生物遗传学的观点，基于进化过程中的信息遗传机制和优胜劣汰的自然选择原则的搜索算法。通过自然选择、交叉、变异等作用机制，实现各个个体的适应性的提高。高校课表编排工作的主要思想是：读取开课计划一落实教学任务一统计可用资源一课表的编排。具体来说就是教务处在每学期开始前读取各个专业的开课计划；并将读取的开课计划落实教师、教室类型等；统计全校在对应学期的可利用的教学资源(教师、教室等)；对确定开设的课程，根据不同的专业，以班级为单位编制下学期的班级、教师、教室以及课程的课表。

一、排课问题要素分析

(一)课程

每门课程都有自己的编号、名称以及承担单位。课程本身包含的属性会在很大程度上影响该门课程的排课结果。

学时数：根据教学计划，每门课程都有指定的学时数，可以用整个学期或者规定的时间段完成课程的总学时数，要为课程安排相应的时间片。

可拆性：上课时间的最小单位是学时，一般来说，每一个时间片对应两个学时(称为一个讲次)，但是多数课程的周学时数多于两个学时，这样就必须将课程拆成两个或者多个讲次。

时间要求：有些课程对时间有特殊的要求，例如体育课尽量不安排在1、2节课。有些课程不能安排到晚上等等。

地点要求：一般来说，上课地点分为很多类型，如多媒体教室、一般教室、语音室、机房、专用实训室等。

起止周数：根据课程的需要，很多高校把某些课程集中在某几周或者由于特殊原因不规则的安排到一个学期中。因此必须要为课程定义起止周数。只要满足周数不冲突的课程即可安排在一个时间段内。

(二)教师

教师是安排课程的必要资源之一。在排课的过程中。教师应该服从相应的时间安排。当然也可以根据实际情况对授课时间提出的要求。

所授课程：每个教师都可以讲授多门课程，但同一名教师在同一时间段内只能讲授一门课程。

时间要求：教师由于个人因素或者职务因素等对授课时间提出要求，例如，有些教师希望在一周的某个时间不能上课，有些教师希望在具体某天上课。还有教师希望课程安排尽量紧凑等等。

(三)班级

班级就是指行政班级。合班上课的情况我们称之为教学班，教学班不能认为是一个新的班级。

开设课程：在一个学期内每个班级都会开设多门课程，但同一个班级在同一时间段内只能上一门课程。

班級人数：在正常情况下，某个班级开设某门课程即是班级的全体学生都学习这门课程。在安排教室的时候必须考虑到教室容量数一定要大于或者等于班级人数。

时间要求：有时根据教学计划，某些班级对课程的编排时间也有着特殊要求，如可能在中间几周出去实习，这段时间就不能排课，还有些如体育课等后面最好不排课等等。

(四)教室

教室类型：包括普通教室、多媒体教室、机房、语音室和实训室等，一般来说，一个教室在同一时间内只能被一门课程所使用。对于一些特殊课程，例如体育课因为不需要固定的教室，可以同时安排多门课程。

教室容量：指一间教室所能容纳的最多人数，上课人数不能超过教室容量。

教室位置：包括校区、教学楼、楼层等，影响班级学生和教师在不同课程之间的移动距离。

(五)时间

上课时间在对应学年、学期一般是按周来计算的，按照学校规定从第1周至第N周。当然根据实际情况，也可以是学期中的任意连续或不连续周。

二、排课问题的约束分析

排课就是将教学任务在时间和地点上按照不同的约束条件进行的排列组合。从手工排课可以看出，排课需要考虑学校方方面面的约束条件。在排课过程中，主要任务就是将班级、教室、课程、教师等几部分资源进行最优化组合配置。

排课问题的约束条件很多，但大体上可以分为三种：

(一)基本硬约束(基本的约束条件)：

1、一个班级不能在同一时间内上两门不同的课程。

2、一个教师不能在同一时间内上两门不同的课程。

3、一个教室不能在同一时间内上两门不同的课程。

(二)硬约束(排课所必须遵循的原则)：

1、学校本身的规定产生相关的约束。

2、课程的学时在周和星期上分配有一定的规律。

3、上课按最小单位一节计算，课表周数、天数、节数可以自行定制。

4、教室容量必须大于上课班级人数。

5、某些课程、教师、班级、教室的属性可以提前设置。

6、每门课程都有相对应的教室类型。

(三)软约束(不影响结果的约束条件)：

1、每个上课时间段都具有一定的优度。

2、教师尽量不安排连续上课。

3、班级在一周内的课表尽量分布均匀。

4、教师对上课时间或地点具有一定的满意度。

5、职业院校实训课程比较多，根据需要进行上课时间和地点的约束。

浅谈高校的排课艺术 篇4

关键词：高校,课表编排,原则,人机交互

17世纪捷克教育家夸美纽斯认为,学校要达到预定的教学目的,就需要对学生的学习科目、时间、方法等进行巧妙的安排,使学校各方面的工作能够“用最巨大的技巧做成功,用最精细的工具巧妙地雕镂出的钟”那样有条不紊地运行。显然,课表就是学校这座“钟”有条不紊运行的重要组成部分。学校的课表在设计时,应像下一盘棋一样要通盘考虑各个棋子摆在什么地方,尽量做到科学。课表编排的优劣,可以反映出学校教务工作的水平,甚至影响到学校教学质量的提高。

课表既是学校执行教学计划,落实教学任务,顺利进行教学的依据,又是学校日常教学工作和其他各项活动的调度表,它把学校教师、学生和工作人员有机结合起来。笔者认为,要编排一张合理、高效的课表必然要求排课者全面熟悉教育教学规律、教学管理规律,掌握一切排课的信息资源,以现代化技术为依托,不断优化课表。

编排课表所要遵守的原则

高校的排课具有规模性、多样性、复杂性等特点,尤其是跨校区教学,更增加了课表编排的难度。在教学活动中经常出现不以行政班为单位的情况,学生可以在专业教学计划的指导下根据自己的兴趣和能力等选课。大学英语等公共基础课采取分层次教学,这些所谓“模块课”的排课模式与一般的课程也不同。这些都对高校排课工作提出了更高的要求。因此,为了处理好这些问题,首先要确立科学的排课原则。

排课过程必须遵循的总体原则

必须坚持全面正确地贯彻党的教育方针和教学计划,全面提高教学质量;坚持以人为本,要符合教育学、心理学的要求以及各学科的特点;坚持从大局出发,从全校着眼充分周密地考虑安排,确保教学过程的稳定性。

调动教与学两个方面的积极性

高等学校课程复杂多样,课表编排应保证学生在一天和一周中保持学习的高效率。人的神经系统的工作是有一定规律的。在一天里,早上的前两节课是教师和学生精力最旺盛的时段,应当安排难度较大的、较重要的基础课或专业课;在一周里,大脑的工作能力在星期二、三达到高峰,星期四、五又开始下降。因此,排课的时候把复杂的科目安排在星期二、三、四,在学生大脑功效最高的时候来完成。每天的课程不要编排得太多,要考虑给学生足够的自学时间,给教师留有足够的备课时间,同时还应考虑教师的一些实际情况。比如,对于进修的教师不宜排太多的课,以防教师过度疲劳。编排课表时还应考虑到教研室全体成员需要一定共同时间不排课,以便开展教研活动,还应保证教师有足够的时间来进行科学研究。

教学资源的充分合理利用

高等教育正逐步向大众教育转变,许多高校的学生快速增加,教学资源显得相对不足,这就要求在排课的时候要充分考虑场地、设备的周转率问题,减少闲置和浪费。要做到见缝插针,提高资源利用率,获得最大的投资效益。在遇到实验设备使用冲突时,要做到有意错开,这样不仅能解决设备不足的问题,而且还能为教师的相互听课提供时间保障。

课表编排的流程

编排课表是教务部门一项业务性很强的工作,编排者需要有丰富的实践经验,既要服从教学规律,又要兼顾一些特殊要求,最主要的是要高效地协调各类资源,发挥最大优势。一般来说,课表编排主要涉及下面四个流程:

全面掌握各类资源

要排出高质量的课表,必须充分掌握排课的一切信息资源。首先,按照教学计划向各系部下达教学任务,各系部填写教学任务后按时汇总到教务部门。一般来说,教学任务应包括以下信息:各系、各专业、各年级必须开设的课程,课程的总课时数,周课时数,班级和班级人数,任课教师姓名,对所上课程的场地要求。其次,掌握全校各类教室各种实验设备的数量、分布情况以及机房、画室、琴房等特殊场地的情况。

合理安排各门课程的编排顺序

排课时要以课表编排所要遵守的原则为依据,科学合理地编排课程。可以优先考虑对课表整体影响程度最大的课程(通常称为板块课),优先考虑板块课的编排,让其占据最佳的时间组合模块,以保证课表的整体优化。如一些分层次教学的外语类课程,因为这些课程往往不是按照行政班上课,所以需要优先考虑。还要突出解决主要问题,集中精力解决好一些重要的基础课和专业课的编排,往往这些课对所学专业起着决定性的作用。最后才是对一些非主要课程的编排,时间从属于主要课程。为了让学生更好地学习知识,还要尽量做到文、理、工课程的交叉安排,错落有致。

仔细检查课表编排结果

课表编排相当复杂,系统性相当强,排课者水平再高,也难以做到万无一失,因此必须对其进行反复检查。首先,根据教学任务检查是否有课程漏排、错排的情况;其次,检查课表安排是否符合课表编排的原则,发现不合理的地方应及时调整,调整后应特别注意局部调整对课表整体的影响。检查课表中各类资源的使用情况是否冲突,也是课表检查的重要环节,一般可以从教师、班级、教室、实验室等方面着手检查,这就需要在编排课表时做好对信息的及时、准确统计,以便更好地发现问题。

及时公布编排结果

排课结果在经过以上步骤以后,一般来说比较准确合理了,为了使课表更加合理,更加人性化,及时公布编排结果尤为重要。因为排课者本身的局限性,不可能对每门课的具体教学情况了如指掌,若教师认为课程安排不利于教学,严重影响教学效果,可由教研室将意见汇总后在一周内到教务部门调整,排课者将本着课表编排的原则进行微调。经过这样调整后的课表即成为正式课表。为保证教学的稳定性,任何部门、人员不能随意变动,教师和学生都必须严格按课表开展教学活动。

利用信息管理系统编排课表

随着高校规模的扩大和办学水平的提高,仅靠手工排课已经很难适应教学管理的需要,特别是一些规模较大的学校,存在着在校人数多、跨校区排课、分层次教学、选课等许多个性化的问题。如果再用人工编排方式,不但效率低,而且还很容易出错。因此,运用信息管理系统进行排课是提高教学管理水平的必经之路。

目前,大多数高校采用的教务信息管理系统是一个集Client/Server和Brosweser/Web Server技术于一体、涉及教务管理各环节、面向学校各个部门以及各层次用户的多模块综合信息管理系统,突破了许多局限性,实现了网上用户的访问。因此,可以在任何地域、任何时间、以各种不同身份访问信息管理系统中的数据,大大加强了数据的共享能力。

利用现代化手段进行排课,首先要做好排课数据的准备工作,主要包括教师信息、班级信息、教学场地信息、选课信息等,即将教学任务和各类教学资源在计算机中体现出来。其次,对一些数据进行设定,如可排课时间、排课时限以及课程、教师、教室的优先级设定。每一步工作都应为整体服务,前期准备工作的细致到位能为后面排课的顺利进行打下良好的基础。第三,开始智能排课,系统通常能自动排出大部分课程,对于少部分课程需通过人机交互的方式进行调整,比如一些较为重要的必修课,即使在排课时设置的优先级比较高,但仍会因教学资源有限而排在不合适的时间,还有一些班级课程松紧不一,分布不均匀,或者教师连续上课时间太紧,这些都不利于教学,都需要手工调整。第四,利用计算机可以对课表进行准确高效的检查,最后充分利用信息管理系统的查询功能,输出各类报表,主要包括全校总课表、班级课表、教师课表、场地课表等。

将科学合理的排课原则和现代化的管理手段相结合,虽然能大大提高排课效率,但任何软件都有其局限性,加上一些新情况不断出现,排课难的问题仍比较突出。因此,我们要不断学习新知识,适应新环境,在实践中不断研究和总结,积累排课经验,运用更加智能化的排课软件,排出一张高质量的课表。

参考文献

[1]职业院校教务工作管理创新实用手册[M].北京:中国教育出版社,2007.

[2]周国伟.高校课程表编排若干问题的思考[J].温州师范学院学报,2003,(92).

排课程序 篇5

第1章 系统需求......................................................................................................2 第2章 分析问题领域..............................................................................................2 2.1确定系统范围和边界..................................................................................2 2.2 确定活动者.................................................................................................2 2.3 定义UserCase.........................................................错误！未定义书签。2.4 用例图.........................................................................................................2.5 主要交互图(顺序图)..................................................................................8 第3章 静态结构模型............................................................................................10 3.1 建立对象类图...........................................................................................10 3.2 数据库表设计...........................................................................................11 3.3 建立包图...................................................................................................12 第4章 动态行为模型............................................................................................13 4.1 建立顺序图...............................................................................................13 4.2 建立状态图...............................................................................................13 4.3 建立活动图...............................................................................................14 第5章

总结............................................................................................................15

自动排课系统

第1章 系统需求

系统功能描述：

(1)课程规划人员必须在排课之前规划好本学期各专业的课程，并且要保证各个专业学生学期总学时不高于某个规定值。

(2)教师可以提前申请教授课程，可以根据自己的代课课程提出对媒体教室的需求。需要教师填写个人代课意向申请，教师意向将在系统排课时被优先考虑。

(3)系统根据教室的多媒体安装情况、座位数，专业课程设置情况，教师意向，选课学生数量等信息进行排课，使尽可能满足各种用户的要求；支持教师对课表更改进行申请，系统给予微调整。

(4)教室管理员根据对教室设备的更新情况修改教室配置的基本信息。

(5)系统管理员规定一确定时间进行系统自动排课，到这一时间时，系统将自动进行排课，生成课表。

(6)课表生成后，所有用户将有权对课表按班级、教师、教室等不同方式进行的查询。

第2章 分析问题领域

2.1确定系统范围和边界

经过对自动排课系统的的分析可知，自动排课管理系统的主要功能模块包括：

1.自动排课系统：对所有的课程进行自动安排，以达到所有的任课老师，学生的课程无冲突；

2.教室时间安排：对所有的教室的所有可用时间进行安排，以达到教室使用权的不突出； 3.申请更改课程：对有意外情况或临时状况的课程变更，进行更改，以达到正常的完成教学任务。2.2 确定活动者

使用者主要是：系统管理员、教师、课程规化人员 2.3 用例图

2.3 主要交互图(用例图)（1）自动排课操作顺序： 1.Main ： 主界面 2.land：登陆界面 3.register：注册界面

4.Requests：排课要求界面 5.Result ：自动排课生成结果 6.Remark ：备注

（1）自动排课操作顺序图

（2）教室时间安排操作顺序： 1.Main ： 主界面 2.land：登陆界面 3.register：注册界面

4.Requests：教室安排要求 5.Result ：自动排课生成结果 6.Remark ：备注

（2）教室时间安排操作顺序图

（3）申请更改课表： 1.Main ： 主界面 2.land：登陆界面

3.Apply：查看更改课表的申请 4.Change：对课表进行更改 5.Result ：确定申请，生成结果 6.Public：公布更改信息界面

（3）申请更改课表操作顺序图

2.5建立顺序图

2.7 建立状态图

(1)班级课程表状态图

（1）班级课程表状态图

(2)班级状态图

(3)班级状态图

(4)教室状态图

(5)教室状态图

2.6 建立活动图

(1)课表自动生成活动图

(2)课表自动生成活动图

(3)教师申请更改课表活动图

(4)教师申请更改课表活动图

总结

基于遗传算法的智能排课问题的探究 篇6

关键词：智能排课遗传算法排课变量

1.引言

近几年，随着高校教育走向大众化，学生人数急速上升，这无疑加大了排课工作的难度，而课表安排又是教务管理工作中最基础的部分。因此自动排课系统是高校教务管理系统的一个重要组成部分，自动排课系统的应用，使得管理人员可以及时掌握学生的排课情况，进一步优化指导学校的教学资源，在一定程度上提高了高校教学管理人员的工作效率及教学质量。

2.背景

随着计算机网络技术的发展和教育信息化的不断推进，信息技术和计算机网络技术对教学和管理的各个方面都产生了很深的影响。教学计划的实施是高校日常教学管理工作中最重要也是最基本的一个环节。而课程表的制定则是教学计划实施的一个根本条件，是整个教学管理工作实施的基础，对教学计划的实施与教学培养计划的落实起着至关重要的作用，在此基础上对教育教学进行科学统一的组织和管理，有助于充分整合及利用各种资源。一张好的课表不仅能给授课教师带来工作上面的便利，而且也能为学生创造好的学习环境，提高学习效率。编制课表目的在于使整个教学过程能够有计划有秩序地进行，这在高校的教务管理工作中是一项耗时巨大的工程。而这项排课工作的复杂程度与学校的规模有很大的关系，学校的规模越大，当然排课工作的复杂程度就会越高。近几年，随着高校教育走向大众化，学生人数急速上升，这无疑加大了排课工作的难度，而课表安排是又教务管理工作中最基础的部分，因此如何设计一个好的排课系统，如何把教务管理人员从复杂的排课工作中抽离出来，是每一位教务工作人员和软件开发者的希望，也是当前迫切需要解决的一个问题。

因此，自动化排课系统的广泛应用必然成为大势所趋。排课系统是高校教务管理系统的一个重要组成部分，自动排课系统的应用，使得管理人员可以及其掌握学生的排课情况，进一步优化指导学校的教学，操作方便、灵活高效。自动化排课系统实现了整个排课流程的自动化，同时还解决了多种角色以及各个部门之间的协作关系。因此自动化排课系统的应用，在一定程度上提高了高校教学管理人员的工作效率及教学质量。

3.遗传算法

1.原理

遗传算法（Genetic Algorithms，GA）通过模拟自然界的生物进化过程来寻求问题的最优解，它借鉴了生物界的自然选择机制。遗传算法被较多的用于解决排课问题，同时很多学者热衷于对它的改进与优化，从而出现了诸多基于遗传算法的排课算法。

2.遗传算法流程如下：

1）进行染色体编码；

2）随机产生初始种群，数量根据实际情况事先定义；

3）计算所有个体进行适应度函数值的计算，若某个个体适应度值已满足最优化的要求，则输出该个体及其优化解，并结束当前计算，否则转到第4）步；

4）依据适应度值的大小，从所有个体中选取出那些适应能力较强的个体成为再生个体；

5）依据预先定义的交叉概率及方法产生出新的个体；

6）依据预先定义的变异概率及方法产生出新的个体；

7）由以上两个步骤中的交叉、变异操作产生新一代种群，并返回到第3）步。

4.排课系统设计

4.1排课管理部分

包括智能排课和排课结果查询两个功能。确定专业和年级后，启动自动排课功能，即可完成自动排课功能。排课结果查询即是对前面已排好的课表，在指定了专业和年级以后进行查询。

4.2数据库设计

排课系统依赖的基本信息包括课程、教室、教师、班级等资源，求解目标即满足要求的课表安排。数据库是上述信息的载体。利用关系型数据库系统进行系统的开发，需要首先完成概念结构的设计。概念结构反映了现实世界中实体之间的联系。

4.3排课问题变量

1. 时间变量

排课时重点要注意的是时间段的划分，一般高校安排周一至周五

为课程工作日， 一天可以安排8节课（上午4节， 下午4节），上课方式一般为两节连上，一个课次为两个相邻的小节课。所以以一个课次为一个时间段，一天可以划分为4个时间段。按一周五天计算，一周可以划分为20个时间段。但是，并非20个时间段里面每一个时间段都适合排课，并且有的课程对时间可能还会有一定的要求，如：比较重要的课一般放在一二节；体育课尽量不要排在上午的时间；周五下午三四节一般不排课等等。

2. 教师变量

一个教师可能只带一门课，也可能带多门课，但是一个教师在某一个时间段，在某一个教学地点只能上一门课；另外，一个教师可能带一个班级的课程也可能带多个班级的课，如果一个教师在某一时间段内被安排在多个班级上课，同样会造成教学活动的混乱。

3. 课程变量

一门课程可以由一位教师任教也可以由多位教师任教，而且每位教师可能对应了个班级的学生。

4. 班级变量

同一时间段内一个班级只能在一个教室里面上课，并且只能是一门课程。

5. 教室变量

学校里通常有多个教学楼，每个教学楼又会有若干个教室可供选择，在某个时间段内只能有一名教师在此教室授课，可以有多名学生，但是学生的课程必须相同，所选教师必须相同。

4.4排课问题约束

排课问题涉及到两种约束，分别是基本约束和模糊约束。其中，基本约束又称硬约束，是指在排课过程中必须要遵循的原则。而模糊约束又称软约束，是要尽量满足的原则。

nlc202309011113

一个正确的课表要遵循的基本约束条件：

1. 同一时间段内不能给一位教师安排两门不同的课程上课；

2. 同一時间段内一个班级只能安排一门课程；

3. 同一时间段内一个教室只能安排一门课程；

4. 教室的最大容量应不小于上课的学生人数；

除上述的基本约束外，还有一些模糊约束，这些模糊约束可以使课表更加合理、更加人性化。

模糊约束条件有：

1.根据课程类型以及学生接受程度，来为这类课程安排最合适的时间段；如：专业课、必修课一般安排在早上，而文体类的课程通常安排在下午；

2.理论性课程尽量分散安排，即一门课尽量分散在一周的某几天，并且中间尽量隔开，以便教师能够有充足的时间备课，而学生也有足够的时间消化已学到的知识；理论与实践并重的课程最好将理论与实践课穿插安排，可以在学生学习完理论课程后及时通过动手操作加以巩固，有利于学生对知识的理解、掌握；

3.学生的上课时间不能过分集中，应尽量避免某一天课程安排的很满而另一天却没课的情况；

4.排课时，应尽量把知识性强的和趣味性强的、理论性的和理解性的课程交叉安排；

5.考虑教师的工作负荷，一天内上课一般不超过四节；

6. 同一教师，同一门课程可以尽量安排在相对固定的教学场所，不但方便记忆， 还有利于教师和学生的适应；

7.教师或学生接连两门课程地点尽量比较接近；

8.对于教师、学生可能提出的一些特殊要求，根据情况安排，如若合理，尽量满足。

另外，对于其它特殊情况，如分单、双周上的课程，不确定周次的课程等，也需要综合考虑，合理安排。此外对于计算机预排的结果，还可以根据实际情况，通过人工交互的方式进行修改。

4.5基于遗传算法的智能排课算法

1.连接数据库获得课程信息，班级信息，教室信息，公共课程信息，系别信息；

2.根据多媒体教室资源数据生成空白时间安排表；

3.按照群体中个体数量，随机地将课程序号数据装入到时间安排表中；

4.计算每个个体的适应度向量，即个体染色体适应度函数值；

5.若适应度达到事先设定的进化结束要求（无继续收敛），或进化代数达到最大代数，则跳转到9；

6.根据4所得适应度值，计算交叉、变异和选择概率，根据概率选择优秀的时间安排方案，并淘汰掉适应度值低的方案；

7.应用交叉、变异算子与染色体；

8.继续循环，跳到5；

9.从较优群体中选择一个最优方案，生成最优时间安排表。

5.结束语

本文中的自动排课算法实现了教师、教室、课程、时间等资源在教学活动中的合理配置与安排，把教学工作者从繁杂的手工排课工作中解脱出来。同时，也减少了排课过程中可能出现的冲突错误，保证了教学秩序的正常运行，大幅度的提高了教务教学管理水平以及教务人员的工作效率。虽然实现了自动排课功能，而在实际应用中，还应该考虑到因为一些特殊原因导致的需要手工调节课表安排的情况，所以在今后还需要改善这方面的功能。

参考文献：

[1]修磊， 杨社堂. 高校排课管理系统的设计与实现[J].太原理工大学学报，2006， 37（5）：75-77.

[2]张海涛， 刘万军. 高校计算机排调课算法研究[J].辽宁工程技术大学学报，2005，24（1）： 110-111.

[3]袁宏武， 薛模根， 姚翎. 基于规则的个性化课表生成算法[J].计算机工程，2006，32（4）， 194-224.

[4]苏仰娜. 基于遗传算法的优化排课系统[J].河南大学学报（自然科学版），2005， 35（1）， 75-78.

[5]魏敏.基于遗传算法电大排课系统的设计与实现[J].复旦大学，2011.

课题信息：课题名称：遗传算法在高等学校智能排课问题方面的研究，课题类别： 内蒙古自治区高等教育科学“十二五”规划课题课题，批准号：NGJGH2014083。

基于遗传算法的高校排课分析 篇7

1 研究思路与遗传算法

1.1 研究思路

笔者的研究思路如下:首先, 要列出高校排课的各个要素和制约条件、制定研究目标, 通过人工排课的逻辑思维来构造高校计算机排课的初步模型, 得出一个完全NP的、复杂非线性问题的组合模型。其次, 分析遗传算法, 理解它的特点、思想和模式, 进行优化后把遗传算法的模式套入排课算法。然后绘出排课系统的功能模块框图。最后, 运算得出最优解。

排课问题的重点和难点有:首先全面考虑排课要考虑的各项因素 (包括软约束和硬约束) 对遗传算法本身存在的一些缺点如收敛过早的问题要进行一些改进。接着是排课问题的整体建模, 包括建立基因编码, 选定初始种群, 规定进化规则, 适应度函数, 控制参数等。完成系列计算以后, 由于排课问题的解数量庞大, 还要对结果进行择优汰劣。

1.2 遗传算法

遗传算法 (Genetic Algorithm) 是仿照达尔文物种进化的规律来寻找最优解的算法[1], 它具有很强的全局搜索能力。笔者提出的排课算法建立在遗传算法的基础上, 从多方面改进和完善, 其目的是提高计算机排课优化的效率, 避免提前收敛和收敛速度慢等问题。在这之中“选择、交叉和变异”是遗传算法的三大主要步骤。

具体而言, 遗传算法是根据达尔文生物进化论和遗传学机理进化而来的具有高度并行性、随机性、自适性的计算模型, 是一种通过模拟自然进化过程搜索最优解的方法[2]。它的主要思想是在实际求解问题中引入生物进化的原理, 因而它适用于非线性的复杂的计算问题中。遗传算法是从一个随机的初始解开始计算的 (解的选择要相对的分散, 过于集中就要增大变异概率, 减小交叉概率) , 规定一个适应度然后开始计算, 当中通过交叉和变异 (每个周期突变一些数据, 然后再筛选一些数据进入下一轮计算) 寻找这组变量的最优解, 使得适应度最高。选择与交叉将使种群与天然进化相同, 后代生成种群将会比上一代更为顺应适应度规则, 如此循环往复, 逐步演变出越来越好的末代种群中的最优个体, 也就是要求的最优秀的解。通过解码 (decoding) , 能够产生类似最优解, 但并不一定能产生最优解。遗传算法也可以通过DSL的程序编程来进行优化。

2 排课分析

2.1 排课考虑的要素

笔者总结的排课要素主要有以下几个:同一时刻一个学生只能选择一门课程;同一时刻同一个教室只能上一门课程;同一时刻一个教师只能上一门课程;给班级安排的教室必须可以容纳所有上该课程的学生;必须要有特定的教室提供给特定课程使用 (如实验课) ;尽可能满足大多数人相邻两节课上课地点近;为了方便本地学生尽早回家周五下午尽量不排课;体育课后尽量不要安排课程;根据一些学校的特殊性 (如有的学校每周二下午为无课日专用于学生活动) 避开特殊时段不要安排课程。

2.2 评判排课优度的因素

以教育心理学为理论依据, 评判一张课表是否科学合理包括教师教学的心理特点、学生接受能力的层次、有效时间内人脑的记忆特点、设置的课程的特点等因素, 主要分析如下。

1) 时间间隔。人脑记得最牢固的是事物的开头和结尾, 可以使用这条规则来安排学习时间, 以此提高学习成效。1个课时大约为45分钟, 2个课时加中间休息为95分钟, 超过这个时间学生的注意力开始不集中。

2) 时间元。人体的神经系统经过一夜的睡眠调整后得到彻底的放松, 记忆能力也恢复到最高点, 然后在一天之间就逐步降低, 晚上最为疲乏。所以说早晨是一天中最适合学习的时间, 这段时间的思想最集中, 接受新知识的效率高。对于一周之内来说, 星期一、星期二就是学生学习精力最集中学习效果最好的时间段, 星期三人的神经达到最紧张的状态, 星期四、五临近周末大脑开始放松, 所以星期一、二应该安排难度系数较大的课程。

3) 时间元的顺序:如果有一门课每周要上两次, 那就从星期一到五中任意选择两天的两个时段来安排, 这存在多种排列组合方式, 但是各种方式的学习效率肯定有差别。

2.3 基于遗传算法的排课分析

基于遗传算法, 笔者对于排课问题进行编码如下[3]:用数据结构表示基因和染色体的方式表示排课变量空间;设计, 复制, 交叉和变异操作算子;适应度函数及成本函数的设计;解决排课冲突 (如连堂错误, 长连错误以及课时冲突等) 。

根据遗传算法的求解思路[4], 笔者将排课流程总结为五个步骤:第一, 将教学计划导入本学期的授课任务, 同时做好教学资源、教师信息、时间信息等基础数据的输入;第二, 把授课任务下发到各系部, 由各系部安排好教师及教师的各种要求, 比如班级的类型 (合堂或单班) , 教室的类型 (普通教室或多媒体, 合堂教室及语音室等) , 时间类型 (上午, 下午, 晚自习或周末) ;第三, 系统根据任务的反馈自动生成课表, 这个过程主要实现课时、地点的安排;第四, 自动排课完成后, 根据排课结果以及对课程、班级、教师、教室等各种因素可能出现的冲突, 对课表进行微调;最后, 调整完成后, 确认最终课表并输出存档。

3 总结

笔者从遗传算法出发, 分析了排课问题与遗传算法之间的联系。通过遗传算法, 排课问题可行解的适应度得到了显著提高, 并且在速度和质量上与人工排课相比也有很大的进步。课表不仅仅局限于计算机智能编排, 还能进行相应的手工调整, 使课表更加合理。同时也验证了遗传算法的可行性, 将它运用于排课系统是十分科学合理的, 排课效率有较大提升。

参考文献

[1]徐锦国.基于遗传算法的排课系统研究[D].西安:西安石油大学, 2010:58-59.

[2]陈春明.遗传算法在自动排课系统中的应用研究[D].苏州:苏州大学, 2009:47-49.

[3]朱良学.遗传算法在车间调度中的应用研究[D].兰州:兰州大学, 2007:54-57.

高校排课系统的设计与实现 篇8

1 系统分析

1.1 排课的约束条件

(1)硬约束[2]。排课工作中应遵守的规则:1)同一时间同一教师只能上一门课程;2)同一时间同一学生只能上一门课程;3)同一时间同一教室只能上一门课程;4)上课按最小的单位(节)进行;5)某一课程被安排的教室座位数应大于该门课程上课人数。

(2)软约束。对排课的合理性和满意性会产生影响的因素:1)一个班级的课程时间安排应尽量分布均匀。2)一周的课程表中的每个时间有一定的裕度。3)教师对上课时间存在的期望;4)班级相邻时间内的上课地点尽可能近。5)体育课应排在下午或上午3、4节,体育课后应避免安排讲授课。6)实验、实习课程有其自身的排课方式。7)可先行手工排定某些课程的时间和教室。

1.2 系统需求描述

(1)以单个学生作为上课对象;(2)可以自动排课;(3)可以手工排课;(4)可以生成任意班级、任课教师和上课教室的课表;(5)可以提供教师、学生和教室管理者等查询课表的接口;(6)可以设置不同操作者的系统使用权限;(7)可以形成报表,并以其他格式输出。

2 系统设计

2.1 工作流程

高校的排课工作由教务处根据各院系制定的教学计划,在每学期末生成下一学期的教学任务,并下发给各教学单位,审核上课的软硬件条件约束,然后根据教学单位返回的学期教学任务,制定全校各班级的课表[3]。基本流程如图1所示。

2.2 主要功能设计

排课系统的主要功能设计如下:

(1)教学资源管理。主要管理各类教室、实验室、教学场馆及场地的相关信息,对教学资源信息进行录入、增加、修改、删除等操作。

(2)课表框架设置。包括安排周学时、周数、学年、学期等上课的具体时间等。

(3)教学日历管理。根据指定学期开始日期和结束日期,由系统自动生成教学日历。

(4)排课相关条件设置。包括设置可排课时间、不可排课时间、课程性质与排课时间之间的关联。设置排课教室的类型与课程性质之间的关联。设置合班上课的时间、课程性质及上课教室之间等关联。

(5)特殊课程安排。对上课时间、地点有特殊要求的课程进行预先安排。

(6)智能排课。根据现有教学资源对所开设的课程自动合理的分配时间和教室等。

(7)手工排课。系统须具备手动处理排课结果的功能,即对系统己自动排好的课程或系统无法自动安排的课程,部门管理员在设定手动排课的时间内进行手动调整或安排。

(8)课程更改处理。在实际操作中,可能因为一些客观原因需对代课教师、上课的起止周或周学时等进行调整。

(9)停调补课处理。在实际教学过程中,停、调、补课现象时有发生,系统可对教师的停、调、补课进行实时安排。

(10)查询统计处理。按照模块中各种组合条件查询上课情况并生成各类表格。

2.3 数据库设计

(1)概念结构设计

(2)逻辑结构设计。根据概念结构设计得到的E-R模型,该排课系统主要涉及到以下数据库表:教师信息表、教室信息表、班级信息表、课程信息表、时间安排信息表和教学计划信息表。

2.4 遗传算法设计

文中采用的遗传算法设计,根据系统的具体情况,对算法的实际使用做了适当的修改,具体设计步骤如下。

(1)染色体编码:采用教师、班级、课程以及教室和教学时间段的组合作为染色体,即使用每个教师的课表作为染色体,尽可能地将课程表的各种类型冲突和各项常识表现在内。

(2)产生初始种群:多个染色体组成”个体”,也就是一种排课方式。多个”个体”组成种群。根据课程多少,动态安排种群大小。

(3)冲突检测和消除:对初始种群中的个体进行冲突检测,如存在各类冲突,例如“一师多班”冲突、“固定时段”冲突等,则确定冲突的行、列,然后在同一行找另一随机位置,将这两个位置的数值互换。直至无冲突存在。

(4)计算适应度值:按照适应度函数计算适应度值。

(5)选择操作:按照适应度值计算选择率和期望的选择数,进行选择产生下一代种群。从选择数的算式可知,具有较高适应度值的父代更有可能在下一代中产生一个或多个子代。

(6)交叉操作:根据选择操作的结果选取两个较好的排课结果作为父体,将两个染色体的上课教师和上课时间段进行交叉。

(7)变异操作:按概率决定变异的次数。对参与变异的个体随机选一行,在该行随机生成两个变异的位置,然后将这两个位置的教师编码互换。值得注意的是当这两个编码中至少有一个是固定教学时段码时,则取消本次交换,重新执行该步骤,直到交换完成。

(8)冲突检测和再消除:经过交叉和变异操作后,可能会产生冲突,因此要进行冲突再检测,并解决冲突。

经过一次遗传算法步骤,新一代种群的适应度值可能有所提高,问题的解便朝着最优解的方向前进,将这个过程进行下去,最终将逼近全局最优解,而每一步的操作较简单,且对问题的依赖性较小。

3 系统实现

通过智能排课功能模块可以实现排课数据条件设置、系统智能排课、人机交互式排课、考试安排、调停补课申请处理、其他上课时间地点安排、查询打印等功能。智能排课模块子菜单的实现界面如图3所示。

系统自动排课后,用户通过人机交互方式来调整教师上课时间地点,调整课程过程中系统将自动检测冲突。对满意的班级、教师或场地课表,用户可直接预览打印或输出Excel。人机交互式排课功能实现界面如图4所示。

课程、教师、教室、班级优先级设定,实现界面如图5所示。

4 结束语

通过该系统可以较大程度上减少教务人员的工作量,避免手工排课可能导致的冲突,提高办公效率。排课问题是一个多目标的组合优化问题,系统中还存在一些未能考虑到的实际问题,所有的约束条件也并未完全涉及,还需在实际应用中不断完善和改进。

参考文献

[1]李富星.自动排课系统的设计与实现[D].西安:西安电子科技大学,2010.

[2]张长庚.基于遗传算法的浙江水利水电专科学校排课系统设计与实现[D].成都:电子科技大学,2010.

[3]蒲静,陈华月,傅饶.通用排课系统的设计与实现[J].福建电脑,2010(6):170-171.

[4]萨师煊,王珊.数据库系统概论[M].3版.北京:高等教育出版社,2000.

[5]李玉吉,卢才武,刘冠.蚁群遗传算法在高校智能排课系统中的应用[J].现代电子技术,2010,33(14):129-131.

用演化算法求解高校排课的问题 篇9

近年来，由于学校扩招，学生和课程数量比以往大大增加，教室资源相对稀缺，使得高校课表的编排成了各高校教务处最棘手和最费时的工作之一，如何用计算机实现智能排课的问题越来越受关注。

2 排课问题的描述

课表的编排，简称排课，是每个学校在学期开学前都要面对的重要任务，简单地说就是给课程分配时间和教室。高校排课问题中课程安排最重要的是将时间、课程、教室的冲突减到最少，以使教学正常进行。排课过程中的约束条件可分为有效性约束和优化性约束两类。

2.1 有效性约束

有效性约束指一张可行有效的课程表上绝不可能发生的约束，主要包括：

1)一个都是或者一个班级或者一个教室在同一时间段内只能安排一门课程;

2)分配的教室可容纳人数应该大于学生数;

3)对于任一班级，某门课程一周内的授课时间数固定。

另外，由于各学校的不同情况，有可能还有以下有效性约束：

4)课程的学时在周和星期上分配有一定的规律。

5)每门课程都有自己的特定的教学资源。

6)分配的教室可容纳人数应该大于学生数。

7)某些课程可以先行手工排定时间和教室。

8)某些教师、班级、教室在某个时间可能不能利用。

2.2 优化性约束

优化性约束指排课过程为使课表更加合理、更加人性化而产生的约束，例如：

1)尽量在早上安排必修课，而下午安排选修课，晚上尽量不排课。

2)尽可能满足个别教师的特殊上课时间要求。

3)一门课尽量分散在一个星期中，即某天上完某一门课后，要隔一天以上再上这门课，以使教师有充足的时间备课和批改作业，而学生也有足够的时间复习消化。

4)一个教师的课不能排满一整天。

5)学生课表中的上课时间不能过分集中，应避免一天课程很满而另一天却一整天没课的情况。

2.3 排课问题的数学模型

排课问题实质就是经典的时间表问题(Timetabling Problem，简称TTP)，它可以一般化地描述为：设给定n个事件和m个资源，用cij表示将第i个事件分配给第j个资源的代价，所求问题为决定一个从事件到资源的最优分配，使得总的代价最小且满足k个附加条件[1]。

1975年艾温(S.Even)证明了TTP问题是NP完全的[2]，宣布了这一问题的学术地位和难度。

2.4 问题假设

因为课表问题的约束条件根据实际情况的不同而变化，因此在开始研究之前有必要进行假定，确定所研究问题的范围。

1)一周上五天课，每天5个教学单位时间，一个教学单位时间为2课时。

2)有的课程只在单周或双周上课，有的课程在单周双周都要上。

3)只考虑有效性约束，不考虑优化性约束。

2.5 常用算法

解决排课问题的主要方法有遗传算法、模拟退火法、分支限界法、贪婪算法等[3]，其中又以遗传算法最为常见。遗传算法重点在于基因的表达，因此产生了不同的若干算法[3,4,5]。

3 演化算法

演化算法与遗传算法相似，是借鉴生物界的进化规律深化而来的随机化搜索方法。其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定;具有内在的并行性;能自适应地调整搜索方向，不需要确定的规则。因此演化算法具有良好的智能性、鲁棒性[6]，特别适合用于处理传统的搜索算法难以解决的复杂的和非线性的问题。

应用演化算法求解问题的核心技术主要体现在编码、评价、交叉、变异、选择和淘汰六方面。

3.1 编码

根据问题的描述，设立以下几个集合：

1)教师集合T={Ti|i=1,2,…,t}。

2)班级集合S={Si│i=1,2,…,s}。

3)课程集合C={Ci│i=1,2,…,c}。

4)教室集合R={Ri│i=1,2,…,r}。教室为授课的地点，一般有类型和容量两种属性。类型属性反映教室的设备状况，会限制某些课程不能在此上课;容量属性会限制某些班级不能在此上课。

5)时间集合M={Mi│i=1,2,…,m}。时间集合根据学校的作息时间不同而不同。根据假设，共有50个可供分配的时间单元，其中单周25个，双周25个。

6)课元集K={(t,s,c)│t∈T,s∈S,c∈C}。课元是一个三元数，由教师、班级和课程组成，表示“教师给班级上的某课程”。课元集是所有要安排的课程的集合。

7)资源集Z={(r,m)│r∈R,m∈M}。资源集是一个二元数，由教室和时间组成，表示“某教室在某时间可上课”。课元集是所有可安排的资源的集合。

根据以上定义，原问题可转化为求映射集F:K→Z的问题。所以，个体的编码方式可表示为向量(z1,z2,…,zN)，其中N=|K|，表示课元的数量;zi∈Z(i=1,2,…N)，表示第i个课元安排在资源zi中上课。这样，一个个体就代表了一个排课方案。找到最合理的排课方案，就转化成搜索到最优秀的个体的问题。

3.2 评价

根据约束条件和问题假设，设置问题的最高评价值为1000，评价值越高表示个体越优秀。当个体满足所有条件时，它获得最高评价值1000;如果某些约束条件不能满足，则扣除相应的评价分。

根据个体的编码方式，有效性约束的8条法则可总结为以下6条可操作的扣分法则：

1)同一教师不能在同一时间上不同课课程。

2)同一班级不能在同一时间上不同课课程。

3)同一资源不能指派多个课元。

4)每个课元由于老师有其它安排或班级有其它安排等原因不能在某些时间上课。

5)每个课元由于学生人数过多或者教室硬件设备落后等原因不能在某些教室上课。

6)某些资源已经被指定使用，不能指派任何课元。

用T(x)表示课元x的任课教师，S(x)表示课元x的受课班级，C(x)表示课元x的课程;用R(x)表示资源x所占用的教室，用M(x)表示资源x所占用的时间。为了进行惩罚，须设立限制集。根据规则要求定义3个限制集：

a)R4={(k,r)│k∈K,r∈R}，对应法则4，表示课元k不能指派到所有教室为r的资源。数据应该反映真实的需求，是作为问题数据的一部分存在的。

b)R5={(k,m)│k∈K,m∈M}，对应法则5，表示课元k不能指派到所有时间为m的资源。数据应该反映真实的需求，是作为问题数据的一部分存在的。

c)R6={(r,m)│r∈R,m∈M}，对应法则6，表示教室r在时间m不能指派任何课元。数据应该反映真实的需求，是作为问题数据的一部分存在的。

则上述六条法则的具体的实现方式可表示为：

1)(i,j),i≠j，如果T(i)=T(j)∧M(zi)=M(zj)，则扣分d1。

2)(i,j),i≠j，如果S(i)=S(j)∧M(zi)=M(zj)，则扣分d2。

3)(i,j),i≠j，如果zi=zj，则扣分d3。

4)(i),i∈K，如果(i,R(zi))∈R4，则扣分d4。

5)(i),i∈K，如果(i,M(zi))∈R5，则扣分d5。

6)(i),i∈K，如果(R(zi),M(zi))∈R6，则扣分d6。

其中d1～d6表示相应项的扣分量，用以调节各法则的权重。因为这六项法则都是有效性法则，任何有一项不满足都无法构成一张可行的排课表，因此这里设置d1=d2=d3=d4=d5=d6=1。

3.3 选择、交叉、变异和淘汰策略

选择策略是“优胜劣汰”的自然法则的体现。本算法使用轮盘法则进行选择，也就是按照评价值线性地决定被选择的概率。

交叉是演化算法中实行大范围搜索的主要手段，好的交叉算子能够快速定位到最优解的附近，或者能够均匀地遍历解空间，从而能以较高的概率搜索到最优解。因此，交叉算子的设计对算法的整体运行效率有重要的影响。

经验表示，在大部分使用演化算法求解的问题中，使用模仿染色体分裂的交叉算子是具有较高性能的，所以大部分算法都沿用了这一办法，除非简单的交换会导致个体非法，例如用演化算法求解TSP问题[7]。

本算法采用单点交叉策略。容易证明交叉后两个新的个体仍然是合法的个体。

变异的方法也很直接。随机选择一个课元i，然后将i所对应的资源zi随机变为另一资源z'i。

淘汰策略采用μ+λ策略。这种策略能进行小规模淘汰，实现快速收敛，对于规模较小的问题比较合适。

4 实验与分析

以电子科技大学中山学院计算机工程系2009年上半年实验课排课数据为例，得到实验数据，数据中|T|=27，|S|=23，|C|=32，|R|=5，|M|=50，|K|=62，|Z|=250，|R4|=200，|R5|=1478，|R6|=28。这组数据的特点是教室相对少，冲突相对多，所以人工排课的难度很大，经验表明大约一个人日才可完成。而且实验室排课是二次排课，它必须在理论课程排完之后再排，因此理论课程的课程表稍有改动实验课的课程表就必须调整，因此给排课工作带来极大的麻烦和不便。

使用演化算法，问题就变得简单多了。设置种群大小为50，μ+λ中λ值为3，运行5000代，运行结果图如图1。

图1中，横坐标表示运行代数，纵坐标表示运行至每一代时得到的最大评价值。可以看出，最大评价值呈上升趋势而且最终能够达到1000，结果可以接受。

从结果可以看到，程序大约运行至4000代就出现最优解，运行完5000代需要0.755秒钟。

即使加上前期大约一小时的数据录入工作，很明显，用演化算法排课要比人工排课效率高得多。而且，大部分的数据录入是一次性的，即使部分限制条件经常在变，但对已经录入的数据进行少量修改的工作量不大，数据修改后马上又可运行程序产生一个新的课程表。

5 结论

结果表明，用演化算法解决排课问题是可行的。它能极大提高排课的工作效率与减少人工操作的失误，因此是值得推广的。

参考文献

[1]郑月锋,黄德才,刘端阳.遗传算法在求解时问表问题中的应用研究[J].浙江工业大学学报,2006,34(2):162-165.

[2]Sohaerf A.A survey of automated timetabling[J].Artificial Intelligence Review,1999,13:87-127.

[3]廖远,黄勤,曹培霞.基于三维编码的自适应遗传算法在排课系统中的应用[J].计算机与现代化,2008,12:23-28.

[4]郭芸俊.遗传算法在高校排课问题中的应用[J].电脑开发与应用,2009,22(2):75-77.

[5]谭保华,彭伟.基于蚁群遗传算法的高校排课系统[J].计算机仿真,2008,25(12):294-297.

[6]潘正君,康立山,陈毓屏.演化计算[M].北京:清华大学出版社,1998.

[7]李悦乔,康立山,李程俊.求解TSP问题的实数编码演化算法[J].计算机工程与设计,2007,28(19):4592-4594.

[8]黄海.基于遗传算法排课系统的设计与实现[J].大众科技,2005(9):81-83.

基于遗传算法的高校排课系统设计 篇10

高校排课问题, 它要求将课程、教师、班级安排在一个有限的时间和空间当中去, 要求避免冲突且尽量满足一些其它条件, 这实际上是5个相互制约的因素的组合优化问题。

如果说一张课表是有效的, 则它至少应该满足以下硬约束条件: (1) 不能在同一时间给同一位教师安排多个班级课程 (合班除外) 或同时讲授多门课程; (2) 不能在同一时间给同一个教室安排多个班级上课 (合班除外) 或多位教师授课; (3) 不能在同一时间给同一个班级安排多门课程或同时在不同的教室上课。

一张高质量的课表, 除了应该满足上述硬约束条件外, 还应该考虑一些软约束条件。硬约束条件是衡量排课方案是否可行的标准, 软约束条件则是衡量排课方案优劣的标准, 一般的软约束条件为: (1) 一门课程的几次课在一周之内应间隔排列; (2) 上课人数尽量接近教室容量; (3) 教师对上课时间存在一定的喜好; (4) 教师不推荐连续上课。

此外, 不同的学校还可以根据实际情况定义其他的软约束条件, 例如作者所在学校要求合班课尽量安排在下午。

2 遗传算法原理

遗传算法 (Genetic Algorithm, 简记GA) 是1975年美国Michigan大学J.Holland教授首次提出的, 并逐渐发展成为一种迭代自适应启发式概率性搜索算法。近年来, 遗传算法在求解优化问题中得到了成功的运用。GA是一种抽象于生物进化过程的、基于自然选择和生物遗传机制的优化技术, 它是一种全局优化策略, 其主要特点是直接对结构对象进行操作, 不存在求导和函数连续性的限定;具有内在的隐并行性和更好的全局寻优能力, 能避免陷入局部最优;采用概率化的寻优方法, 能自动获取和指导优化的搜索空间, 自适应地调整搜索方向, 不需要确定的规则。由于其良好的智能性、健壮性和内在并行性, 特别适合用于处理传统的搜索算法难以解决的复杂的和非线性问题。遗传算法演算过程如下: (1) 随机产生一定数目的初始种群; (2) 对个体适应度进行评估, 如果个体的适应度符合优化准则, 则输出最佳个体及其代表的最优解, 并结束计算, 否则转向第3步; (3) 依据适应度选择再生个体; (4) 按照一定的交叉概率和交叉方法生成新的个体; (5) 按照一定的变异概率和变异方法生成新的个体; (6) 由交叉和变异产生新一代的种群, 然后返回第2步。

工作过程如图1所示。

3 算法设计

3.1 班级课表的染色体编码

根据班级信息表以及本学期开课列表, 找到班级的所有排课元。假设每星期上5天课, 每天上午4节, 下午4节, 每次2节连上, 一天有4个时间段, 则每星期有20个上课时间段, 用t1, t2, t3, …t20表示。那么将这20个时间段随机地分配给上述某个班的所有排课元, 也就是排好了一个班的课表。一个班的“排课元”的数目一定是小于或等于20的。如果小于则有时段未排到, 即是自习时间。用0表示。一般来说, 每个班级有相对固定的教室, 因此可以把班级和教室作为一个变量来对待, 如考虑的班有W个, 则对应的教室编号为r1, r2, r3, …rw, 对于一个班级而言, 由于这学期开的课程和教师是相对固定的, 可以把课程和教师当作同一变量来对待。如在课表上有5位老师, 就给其编号1, 2, 3, 4, 5, 同一编号教师可以在一个或多个班级出现, 但只能在一个班级上一门课, 因此一名教师一周可以有多次上课, 他的编号出现次数为所有上课次数的总和。通过以上把班级与教室等同、课程与教师等同的处理后, 原课表五要素 (班级、课程、教室、时间、教师) 转化为三要素 (班级+教室、课程+教师、时间) 。把班级固定要上的课程看作是基因, 教师用代码表示已排课 (0表示自习课) 。而染色体在这里就是W个班级和20个时间段组成的二维表。班级数为5时, 染色体如表1所示。

3.2 建立初始种群

种群的初始化并不复杂, 只要随机产生一定数量的染色体即可。种群的规模推荐50-100, 规模过小, 染色体的多样性不够, 规模过大, 占用内存较多, 收敛时间延长。

3.3 适应度函数的确定

遗传算法在进化中是以每个个体的适应度值为依据来选取下一代种群的。适应度函数设定的好坏直接影响到遗传算法的收敛速度和能否找到最优解。在本系统中, 适应度函数的设计思想是对每条染色体中违反约束条件的情况进行加权求和, 其中权值Wi代表的是第i条约束条件的重要程度, 若某条染色体违反了某条约束条件i, 则将其值Pi置为1 (若没有违反约束条件i, 则Pi值为0) , 其受到的惩罚值为Wi×Pi, 对染色体中存在的冲突进行加权求和并加上1后, 再求其倒数, 如以下公式所示。染色体适应度函数值越大, 则表示其满足约束条件的情况越好, 其在下一代的演化中的生存概率就较大。

3.4 选择操作

选择操作我们采用随机联赛选择的方法, 联赛规模的取值为2, 即每次随机从种群中取2组染色体, 保留f值大的染色体, 淘汰f值小的染色体。除了选用随机联赛选择操作外, 为防止已经搜寻到的最优解丢失, 还采用了最优保存策略, 我们把上一次群体中适应度最大的10%个体不进行复制、交换、变异操作, 而直接进入下一代群体中, 平衡了交叉操作和变异操作的破坏作用。

3.5 交叉操作

交叉操作我们采用单点交叉, 对选择操作形成的种群中的个体随机配对并按预先设定的交换概率Pc来决定每对是否需要进行交换操作。一对要进行交换的个体, 随机选定一交换点, 该点即为染色体中的一列 (即一个班级) , 然后将父代中的这一部分分别交换。交换概率Pc≈0.9, 太小收敛过缓, 太大波动较大。

3.6 变异操作

变异操作的作用是防止丢失有用的可能解, 保证搜索到空间的重要点, 使算法具有全局收敛性。操作的方法是, 选择种群中的个体, 根据预先设定的变异概率Pm来决定是否需要进行变异操作。需要进行变异的个体, 随机选择染色体中某一列的两个位置进行交换。变异概率Pm≈0.01, 太小全局收敛较缓, 过大波动很大, 乃至波动无收敛趋势。

3.7 中止条件

满足以下两个条件中的一个时, 排课过程可以中止: (1) 该种群中最大适应值f大于或等于某个数值; (2) 当前种群中最大适应值与以前各代中最大适应值相差不大, 这时说明进化效果已不太显著, 再进化下去没有必要, 仍有冲突可以手工调整。

4 结束语

本文提出的利用遗传算法解决排课问题的方案, 很好地解决了多约束下的排课问题, 大大减少了人的工作量, 具有很大的现实意义。在实际的应用中, 最终排课结果的整体满意度达到85%-90%, 得到了学校师生的肯定。

参考文献

[1]李敏强, 等.遗传算法的基本理论与应用[M].北京:科学出版社, 2002.

[2]郭东伟.遗传算法运行机理的研究[D].长春:吉林大学, 2002.

[3]江齐, 兰竞.遗传算法在排课问题中的运用[J].重庆大学学报:自然科学版, 2005 (11) .