论文部分内容阅读
高校课表编排是一件很复杂但又很重要的工作,因为它包含了对很多信息数据的管理。根据调查得知,随着高校改革的深入,扩招的增长速度远远超过教学资源增长的速度,排课难度年复一年的增加,因此迫切需要开发出适用的智能排课系统。目前,虽然已经有部分高校和公司成功开发出了学校自动排课软件并投入使用,他们采用的算法大多集中在目前比较流行的基于图论的算法、利用人工智能的遗传算法、专家系统等。但由于这些算法均存在着思路复杂、开发难度大、优化不确切等问题,因而,软件除具有各自的一些优点外,都不同程度地存在一些问题,例如,排出的课程不够合理、排课效率低下、通用性差、缺乏完整性、且受多种条件的限制等。造成这些问题的另一个主要原因就是他们大多使用了单一的算法,所以基于多策略的排课算法的研究将有可能成为解决以上问题的一个有效方法。文中分析了分治策略、贪心算法、回溯算法、遗传算法和禁忌算法等在排课系统中的应用。几种算法各有利弊,为了取长补短,本文提出了一种新的思路即多策略算法,该算法的基本思想是:首先根据分治算法的思想把整个排课过程分成教室分配和时间分配两个部分。然后,依据贪心算法的思想,在教室分配时,总是在尚未分配的教室中选择教室容量最接近并且教室类型合适的教室;在时间分配时,总是在某种条件下尚未分配的时间单元中选择上课效果最好的单元。而在时间分配发生死锁时,会向上回溯搜索到发生冲突的最近一个记录,然后对它进行重排以解决冲突。将教室和时间组合,遍历完整个排课课元之后就生成了初始的排课结果,这种结果只能说是可能达到了局部最优,基本上符合了排课的硬约束条件。为了使课表更加人性化,资源使用更加合理,研究中借鉴了遗传算法和禁忌算法的思想对初始结果进行优化,进而得到最终解。基于多策略算法排课系统研究,使用Microsoft Visual Studio 2008系统开发工具、C#语言和SQL Sever 2005数据库开发平台进行了系统的设计开发。本着人性化的设计思想,为了更好的管理课表信息、将教务管理人员从繁琐的排课工作中解脱出来,本系统实现了手动预排课、自动排课、手动调整、冲突检测和查询等功能,达到了合理分配时间、充分利用教学资源、减轻排课人员工作强度、优化学生的学习进程的目的,基本上满足了一个智能排课系统的需求。