基于遗传算法的高校排课ScheduleArrangementinUniversityBasedonGeneticAlgorithmWanYuanyuan；ChenFuzan(天津大学管理与经济学部，天津300072)(SchoolofManagement,Tian激nUniversity,Tian激n300072,China)摘要：课表问题又称为时间表问题(TimetableProblem),是一个多因素的优化决策问题，也是组合规划中的典型问题。本文从排课系统研发和运行中存在的问题出发，从遗传算法的基本理论入手，研究如何利用遗传算法，解决时间安排过程中的资源冲突(主要是教师资源和时间资源)、课表时间段组合优化等问题。Abstract:Timetableproblemisamulti-factoroptimizeddecisionproblemandisatypicalprobleminconstitutionandplanning,andsoitoccupiesacentralpositioninschoolteaching.Beginningwiththeproblemsinresearchanddevel之外的算法找出最佳解是不可能的⑴。Siopmentofschedulearrangingsystem,thethesisintroducesthebasictheoryofgeneticalgorithm,thenthefocusishowtousegeneticalgorithmtosolvetheconflictproblemthatarousedinschedulearrangingsystemandimproveschedulearrangement.关键词：高校排课遗传算法Keywords:schedulearrangementinuniversity；GeneticAlgorithm：G47文献标识码：A:1006-4311(2011)32-0258-020引言课表问题又称为时间表问题(TimetableProblem),是一个多因素的优化决策问题，也是组合规划中的典型问题。S.Even等人在1975年的研究中证明了排课问题是一个NP-Complete问题，即若是用“穷举法”早在上个世纪50年代末，国外就有人开始研究课表编排问题。1962年,Gotlieb曾提出一个课表问题的数学模型［2］。进入九十年代以后，国外对课表问题的研究十分活跃，比较有代表性的有印度的Vastapur大学管理学院的ArabindaTripathy＞加拿大Montreal大学的JeanAubin和JacquesFerland等。国内对课表问题的研究开始于20世纪80年代初期，具有代表性的有：南京工学院的UTSS(AUniversityTimetableSchedulingSystem)[3],清华大学的系统TISER(TimetableSchedulER)[4]等。这些系统大都是模拟手工排课过程，以“班”为单位，运用启发式函数来进行编排的。1高校排课方案研究1.1排课问题的描述课表的编排问题涉及到班级、时间、课程、教师、教室等五个相互制约的因素[5]。课表问题的编制过程就是为每个班的每门课寻找一个老师在合适的时间和教室，在安排时不能发生冲突，也就是说必须满足以下必要条件：①任一时间，一个老师至多安排一次授课。②任一时间，一个班至多安排一次上课。③任一时间，一个教室至多安排一次授课。除上述条件外，排课过程中还应满足以下经验条件：①周课时多于两个课时的课程的安排应当尽量分散，方便教师备课和学生复习，而且同一门课程应尽量安排在一个教室。②尽量将课程安排在好的教学时段(如一二节比五六节好)。③为确保上课质量，提高教学效率，应尽量配合教师个人的生理时钟，尽量将课程安排到教师个人合适时段，而不应当安排在不合适时段。一个好的课表就是在满足所有必要条件的基础上更多地去满足经验条件的安排。1.2时间安排算法的设计与实现1.2.1编码及其染色体表示假设每周可用时间段有n个，全院有m个班级，则周课表即为以n个时间段为行，每个班级为列所形成的一个二维表。对于每个班级而言，可以将课程和教师当作同一变量考虑。把某个班固定要上的这组课看作是基因，该基因由课程编号（或授课教师代码）和时间段状态码S（S=0时表示这个时间段没被任何课程使用，S=1时表示这个时间段已被某门课程使用）组成，而一个染色体就是由所考虑的m个班级和n个时间段所组成的二维表。1.2.2初始种群对每一个班级而言，首先产生随机数（:Tn）,如果该位置所对应的时间段的状态码S=0,则将优先级高的课程编号填入二维表中对应的相应位%并将时间段状态S设为1；如果该位置所对应的状态码S=L则重新产生随机数。如果该课程一周的课时总数超过2,则继续产生随机数在空闲的相应位置填入课程编号，直到这门课程的周课时达到要求，那么就可以接着安排下一门课程了。重复上述过程，直到所有优先级的课程完成安排，然后安排优先级低的课程。有m个班级，则上述过程进行m...