基于遗传算法的高校排课

《基于遗传算法的高校排课》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于遗传算法的高校排课ScheduleArrangementinUniversityBasedonGeneticAlgorithmWanYuanyuan；ChenFuzan(天津大学管理与经济学部，天津300072)(SchoolofManagement,TianjinUniversity,Tianjin300072,China)摘要：课表问题又称为时间表问题(TimetableProblem),是一个多因素的优化决策问题，也是组合规划中的典型问题。本文从排课系统研发和运行中存在的问题出发，从遗传算法的基本理论入手，研究如何利用遗传算法，解决时

2、间安排过程中的资源冲突(主要是教师资源和时间资源)、课表时间段组合优化等问题。Abstract:Timetableproblemisamulti-factoroptimizeddecisionproblemandisatypicalprobleminconstitutionandplanning,andsoitoccupiesacentralpositioninschoolteaching.Beginningwiththeproblemsinresearchanddevelopmentofschedulearrangingsystem,thet

3、hesisintroducesthebasictheoryofgeneticalgorithm,thenthefocusishowtousegeneticalgorithmtosolvetheconflictproblemthatarousedinschedulearrangingsystemandimproveschedulearrangement・关键词：高校排课遗传算法Keywords:schedulearrangementinuniversity；GeneticAlgorithm中图分类号：G47文献标识码：A文章编号：1006-431

4、1(2011)32-0258-020引言课表问题又称为时间表问题(TimetableProblem),是一个多因素的优化决策问题，也是组合规划中的典型问题。S.Even等人在1975年的研究中证明了排课问题是一个NP-Complete问题，即若是用“穷举法”之外的算法找出最佳解是不可能的［1］。早在上个世纪50年代末，国外就有人开始研究课表编排问题。1962年，Gotlieb曾提出一个课表问题的数学模型［2］。进入九十年代以后，国外对课表问题的研究十分活跃，比较有代表性的有印度的Vastapur大学管理学院的ArabindaTripathy、加

5、拿大Montreal大学的JeanAubin和JacquesFerland等。国内对课表问题的研究开始于20世纪80年代初期，具有代表性的有：南京工学院的UTSS(AUniversityTimetableSchedulingSystem)[3],清华大学的系统TISER(TimetableSchedulER)⑷等。这些系统大都是模拟手工排课过程，以“班”为单位，运用启发式函数来进行编排的。1高校排课方案研究1.1排课问题的描述课表的编排问题涉及到班级、时间、课程、教师、教室等五个相互制约的因素[5]。课表问题的编制过程就是为每个班的每门课寻找一

6、个老师在合适的时间和教室，在安排时不能发生冲突，也就是说必须满足以下必要条件：①任一时间，一个老师至多安排一次授课。②任一时间，一个班至多安排一次上课。③任一时间，一个教室至多安排一次授课。除上述条件外，排课过程中还应满足以下经验条件：①周课时多于两个课时的课程的安排应当尽量分散，方便教师备课和学生复习，而且同一门课程应尽量安排在一个教室。②尽量将课程安排在好的教学时段(如一二节比五六节好)。③为确保上课质量，提高教学效率，应尽量配合教师个人的生理时钟，尽量将课程安排到教师个人合适时段，而不应当安排在不合适时段。一个好的课表就是在满足所有必要条

7、件的基础上更多地去满足经验条件的安排。1.2时间安排算法的设计与实现1.2.1编码及其染色体表示假设每周可用时间段有n个，全院有m个班级，则周课表即为以n个时间段为行，每个班级为列所形成的一个二维表。对于每个班级而言，可以将课程和教师当作同一变量考虑。把某个班固定要上的这组课看作是基因，该基因由课程编号（或授课教师代码）和时间段状态码S（S=0时表示这个时间段没被任何课程使用，SJ时表示这个时间段已被某门课程使用）组成，而一个染色体就是由所考虑的m个班级和n个时间段所组成的二维表。1.2.2初始种群对每一个班级而言，首先产生随机数（l~n）,如

8、果该位置所对应的时间段的状态码S=0,则将优先级高的课程编号填入二维表中对应的相应位置，并将时间段状态S设为1；如果该位置所对应的状态码SJ,则重新产