摘要
排课问题是一个有约束的、多目标的组合优化问题，并且已经被证明为一个NP完全问题。运用计算机进行自动排课既是高校教务管理的迫切需要，同时也有重要的理论意义。但由于排课问题复杂多变，几十年来一直没有很好解决。本文的目的就是要找到一种解决这种复杂问题的方法。 遗传算法是一种借鉴于生物界自然选择和进化机制发展起来的高度并行、自适应的随机搜索算法，是一种非常有效的解决NP完全的组合问题的方法。本文将遗传算法应用于排课问题的求解，进行了以下几个方面研究工作： 1.系统完整地讨论了排课问题中的影响因素、主要约束条件、求解目标和难点，用数学模型完整地描述了排课问题，并提出了排课问题求解方法的总体框架和技术路线。 2.给出了排课问题的ERD和类图，设计了排课系统的数据结构，并以此对课表安排过程的各个子算法进行了研究。 3.针对排课问题研究了染色体编码方式以及遗传操作算子的设计，并引入多目标决策协调模型，提出了一种基于多目标决策协调模型的适应度计算方法，并改进了遗传算法一般结构，形成了一套多目标协同优化的排课算法。 4.以VC++为基本开发工具，MSSQLSERVER2000为后台数据库，设计和实现基于GA算法的排课测试系统。通过一个实例分析了遗传算法的各个参数的设置对排课效率以及排课质量的影响，分析显示遗传算法的应用使所得结果令人满意，大大提高了工作人员的排课效率。
NETL