论文部分内容阅读
课表的编排是高校教务活动中非常重要的工作之一,是保证教学秩序正常进行的前提和基础。目前大多数院校的排课主要采用手工编排方法,但是随着高校招生规模的扩大,教学资源变得严重不足,教学资源的利用率也日益被重视起来,同时办学形式的多样化及排课涉及面广、约束条件多等各类复杂要求使得手工排课已经无法完成,因此借助计算机辅助排课成为一种解决手段。如何利用计算机快速、有效地编排出合理、满意的课表,是一项值得研究的工作,也吸引了国内外一大批研究人员对其进行深入研究。然而,在实际应用中,由于排课问题是一个NP完全问题,开发出符合要求的排课系统是一件难事,迄今为止,国内尚没有用户普遍反映良好的计算机自动排课系统。本文通过分析课表制定的原则和要求,依据我校排课的实际需求,建立了排课问题的多目标组合规划模型,提出了基于贪心思想的智能排课算法。模型通过将无冲突的硬性条件作为约束条件,将一些合理性、适应性原则作为优化目标,采用多目标优化的理论进行求解。本文提出的智能排课算法通过分析历史排课数据,利用全概率计算公式,将得到的排课规律应用到自动排课过程中,使得到的排课结果更加合理。在自动排课过程采用了优先级的思想,根据用户定义的或依照一定规则计算出的优先级顺序进行课程安排,算法分成教室选择和时间选择两个阶段,按照贪心算法的思想,针对每次选定的教室和时间计算其目标函数,根据多目标优化的理论选择当前最优解进行课程安排。针对排课过程中出现的“甩课”问题,本文提出了一个无回溯的简单调整算法,通过搜索出要安排“甩课”任务可能需要取消的任务集合,结合用户决策,取消某些任务安排即降低其安排的优先级,然后重新利用自动排课算法进行“甩课”任务安排。用户的参与避免了产生不合理的调整结果,该算法可以在无回溯的情况下有效的解决“甩课”问题。最后,本文通过实验详细介绍了智能排课算法过程,证明了通过该算法产生的排课结果是正确的,并且可以较好的满足课程、教师等约束条件,有效的利用教室资源。在此基础上,本文设计实现了一个排课系统,对系统的数据库结构、功能结构等进行了详细的分析和设计。本文提出的智能排课算法及在此基础上设计实现的排课系统,具有较高的理论和应用价值,系统提供了良好的交互方式,产生的课表在一定程度上可以满足合理性及用户的满意度要求。目前,本文提出的排课算法已在考试编排和课程编排中开始试用,并取得了较好的结果。