高校排课系统的设计与实现

摘要：高校排课系统要求十分严格的可靠性和合理性，各高校一般都是根据自身的特点来定制排课系统，很难推广到所有高校使用。为此，该文根据高校排课的特点，对高校排课系统的需求进行了深入的分析，主要对系统中数据库的设计，并对遗传算法这个高校排课系统中的核心算法的实现进行了研究。

关键词：高校排课系统；遗传算法

中图分类号：TP302.1文献标识码：A文章编号：1009-3044(2011)18-4347-02

高校规模的不断扩大导致了高校教学资源紧张，这给高校教学管理工作带来了更大的困难，使得传统的高校教学管理模式已经难以适应目前现代教学管理的要求。利用现代信息技术来进行高校排课的自动化，不仅可以有效的降低排课的人力和时间成本，而且可以提高排课的质量和效率。因此，对于高校自动化排课系统的开发已经成为了高校进行数字化教学改革以及实现现代化教学管理的重要课题。

1 高校排课系统需求分析

排课系统的主要目的就是使用先进的信息技术来实现高校课表相关基础数据的处理、课表的自动编排以及课表的查询等功能，高校排课系统主要包括如下的需求：

1.1 高校排课相关基础数据处理

高校排课过程设计教学、时间、课程、教师、学生、教师、班级、院系等许多相关的基础数据，高校排课系统应该对这些基础数据进行有效的管理，能够灵活有效的对这些基础数据进行增删改以及查询操作。

1.2 约束条件的输入

由于实际的一些因素限制，某些课程、班级或者教师会对课程安排的时间有一些较为特殊的要求，在排课之前，必须要将这些课程安排的约束条件输入系统。

1.3 排课处理

排课处理是高校排课系统的重点，从排课实现的流程来看可以分成如下的三个步骤：

第一个步骤：预处理

对于一些关键或者特殊的课程，可以在自动排课之前，进行手动确定该课程的上课地点和上课时间，从而提高排课质量，这些预先排课的课程也必须参与到高校排课系统的冲突检测中。

第二个步骤：自动排课

在进行将特殊的课程进行预先排课之后，将剩下的未进行排课的课程按照某一种特定的规则以及算法安排这些课程的上课地点和上课时间，并在排课之后进行冲突检测。

第三个步骤：手动排课

在自动排课之后，根据班级、课程或者教师某些特殊的要求，对自动排课的结果通过人工进行局部的完善，比如，更给上课的时间或者上课的地点，并且保证手动排课的结果能够通过冲突检测。

课程表的编排是由一个教室、时间、班级以及教师四个因素所组成的组合规划问题，为了能够取得最好的教学效果，在高校的课程编排过程中，必须要考虑如下的几个要求：

1）对同一课程、或同一教师、或同一班级应该选择较为固定的上课地点；

2）如果课程在一周内有多次课，那么每堂课之间要有一定的间隔；

3）有特殊要求的课程、班级和教师要根据具体情况特殊处理。

第四个步骤：排课结果的查询和打印

高校排课系统应该提供良好的查询和打印接口，包括教室课程表查询、班级课程表查询、学院课程表查询、教师课程表查询以及临时课程表查询，以供学生和教师对排课结果进行查询，并将结果以表格的形式打印出来。

2 高校排课系统设计与实现

2.1 数据库设计

数据库结构的数据是在前面高校排课系统需求分析的基础上进行的，能够充分体现排课系统中教师、学生、教室以及时间等主体，以及这些主体之间的关系，从而为这些主体的逻辑模型转换提供方便。高校排课系统数据库设计的ER图如图1所示。

其中系统中几个较为重要数据表的物理结构如下所示：

1）班级信息表。高校中每一个班都会有唯一的代号来表明，一般情况下一个班级的代号由六位数字表示，其中前面两位表示入学的年代，而中间两位数字代表学院的编号，最后两位代表班级编号。班级信息表能够为排课信息表提供班级方面的信息，如表1所示。

2）教室信息表。对学校中的每个用于教学用的教室进行编号，为高校排课系统提供学校教室方面的基本信息，如表2所示。

3）教师信息表。教师信息表是对高校中教师信息进行管理的数据表，教师信息表为高校排课系统提供教师方面的基本信息，如表3所示。

4）排课记录表。排课记录表是高校排课系统中最为重要的一个数据表，存储了排课系统处理之后的结果，提供课程方面的相关信息，如表4所示。

2.2 遗传算法设计与实现

遗传算法是模拟生物进化，根据生物界的优胜劣汰和遗传机制所演化出来的一种智能算法。首先，选择问题可行解结合中的自己作为整个算法的初始种群，然后根据生物界优胜劣汰和适者生存的原理来挑选整个可行解子集中的个体，然后通过个体之间的基因交叉以及变异来生成新的种群，并逐代进行进化，在最后种群中的最优秀的个体就是问题的近似解。遗传算法使用了群体搜索的技术，通过对染色体（种群中的可行解）中的基因进行作用，以及对染色体（种群中的可行解）进行评价，可以通过对已经掌握的信息进行分析来指导最优解的搜索。

交叉和变异是遗传算法的核心，在高校排课系统的实现中，主要使用了单点变异以及单点较差的简单遗传算法。

2.2.1 复制操作

在高校排课系统中OpCopy(GMS *gms,int index,int value,int pValue)函数实现了遗传算法中的复制。在复制过程中使用了优势群体优先的策略，及将群集中较为优秀的染色体直接传递给下一代，并且当出现染色体不足的情况时，使用群体中最优秀的染色体来替代。

void OpCopy(GMS *gms,int index,int value,int pValue)

{

GMS oldgms;

oldgms.swap(*gms);

gims->clear();

//复制最优秀的染色体

for(int i=0;i

{

int num=pValue[i]/value;

if(num==0) continue;

for(;num>0;num--)

{

int* generate=new int[generatteLen];

memcpy(generate,oldgms[i],sizeof(int)*generateLen);

gms->insert(gms->end(),generate);

}}

当染色体出现不足时，用群体中最为优秀的染色体来替代。

for(int gms->size();i

{

int* generate=new int[generateLen]；

memcpy(generate,oldgms[index],sizeof(generateLen);

gms->insert)gms->end(),generate);

}}

2.2.2 变异操作

在高校排课系统遗传算法中的变异使用OpChange(GMS *gms,KY *class,Room room)函数，其操作的主要步骤如下：

从教室集合中随机的抽选一个教室，并且生成两个随机的时间段，然后将这两个时间段进行交换，并检测排课的冲突，如果变化之后出现冲突，那么证明此次变异失败，只能回到集群原始的位置。

2.2.3 可行解的求解和遗传

在系统中使用valueCaculate(GMS *gms,KY class,Room room,int **result)来实现遗传算法中可行解的求解以及可行解的遗传操作。在这个函数中首先计算出染色体的特征值，然后根据这个特征值，对染色体进行复制、变异以及交叉操作，并将最后的记过通过result结构传递出来。

3 结束语

排课系统是大学教务管理系统中一个非常重要，同时也是非常复杂的一个工作，良好的排课系统能够充分发挥大学的各种教学资源优势，并且保证教学计划的顺利进行。但是排课系统通常受到课程、时间、校区、教室、班级以及教师等因素的影响，情况非常复杂。本文采用遗传算法作为高校排课系统的核心算法，对排课问题做出了一些有益的尝试，也希望能够为排课系统的研究做出自己微薄的贡献。

参考文献：

[1] 张春梅,行飞.用自适应的遗传算法求解大学课表问题[J].内蒙古大学学报:自然科学版,2010,33(4):459-464.

[2] 崔雪梅.自动排课算法设计[J].延边大学学报,2010,26(3):214-217.

[3] 林漳希,林尧瑞.人工智能技术在课表编排中的应用[J].清华大学学报,2007,24(2):1-9.

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文