VB自动排课系统论文

摘要 本文建立了自动排课系统的数学模型，并利用遗传算法对问题进行求解。在演化过程中采用一种新的遗传策略，加速了群体的收敛速度。若对本系统做适当的修改，可适用于其他的时间表问题。 关键词 自动排课系统，遗传算法

一、引言

自动排课系统实际上是时间表的优化问题，从而是一类NP完全问题。如何根据班级的课程设置、课程的周内次数、现有教室资源、以及现有教师资源进行科学的合理安排，提供给学校的教务部门一个自动排课系统，在实际工作中具有一定的应用价值。

在排课过程中，我们考虑了三类资源：一类是教师资源，一类是教室资源，一类是时间资源。教师资源包括在编教师和每个教师历年所上过的课程、以及所上过课程的评价值。同一课程可能有多名教师能开课，在资源分配允许的情况下，自然选择评价值高的教师上这门课。多数情况下，在进行教学任务安排时，已经人为考虑了教师和课程之间的固定联系。教室资源是指现有可用教室。时间资源是指允许可用的时间段。此外，按每学期教学大纲，本学期每个班(专业)所上课程和每门课的周学时数(次数)是预定的。同时，我们还需要考虑不同时间段的上课效果。排课问题是根据现有教师资源、教室资源和时间资源，如何使排课结果最佳。适当定义相应的一些评价系数后，排课问题变成了一个时间表的优化问题。

本文考虑排课问题中的一些约束条件，定义了相关的评价系数，建立了排课问题的数学模型，利用遗传算法对问题进行求解。然后生成各类时间表。

遗传算法(简称GA)是1975年美国Michigan大学J.Holland教授等首次提出的，近年来，遗传算法在求解优化问题中得到了成功的运用。GA是一种抽象于生物进化过程的、基于自然选择和生物遗传机制的优化技术，它是一种全局优化策略，能避免陷入局部最优。按照“优胜劣汰，适者生存”的原则，通过快速随机搜索力求找到最优解或次优解。

二、自动排课系统的数学模型设计 1、集合定义

（1）课程集合:subject1,„„,subjectn2

其属性包括课程名称、课程号、周次数、每次学时数等。 （2）教师集合:teacher1,„„,teachern1

其属性包括姓名、教工号、年龄、已上过课程、所上课程的评价值等。 （3）班级集合：class1,„„,classn3

1

其属性包括班级名称（系名、年级、专业、班级号）、学生人数等。 （4）教室集合:classroom1,„„,classroomn4

其属性包括教室名称、容量、类别（一般、多媒体）等。 基本数据库如图所示：

教师资源库： 课程库：

（课程名称，周次数，每次（姓名，职称，年龄，已

上过课程） 学时数，已上过课程）

时间表： （星期，时间段）

班级库： 教室库：

（班级名称[系名，年级，专（教室名称，容量，类别[一

业，班级号]， 学生人数） 般，多媒体]）

而结果数据库则由教师时间表、教室时间表、班级时间表构成。 2、变量定义

（1）时间变量：T＝（tij）

每周按7天计，每天按6个时间段计。用一个7×6矩阵T表示。 tij：星期i第j时间段。 第1时段：上午1、2节；

第2时段：上午3、4节； 第3时段：下午1、2节；

第4时段：下午3、4节； 第5时段：晚上1、2节；

第6时段：晚上3、4节。

2

（2）时间段效率变量：α＝（ai）

用一个长为6的数组表a表示。ai：第i时段上课效果值。比如，我们可以规定每天各个时间段的效果值如下表所示：

1 2 3 4 5 6 时段号 ai 1 0.9 0.8 0.7 0.8 0.7 （3）教室利用率变量：rij＝classi.value/classroomj.value

其中，classi.value表示i班的学生人数，classroomj.value表示j教室的容量。 （4）时间表初始约束变量：C＝（cij）

cij＝1：表示星期i第j时间段可排课；cij＝0：表示星期i第j时间段不能排课。 （5）时间间距约束变量：B＝（bij）（一个42×42时间段关联矩阵） i＝6w＋d，j＝6w´＋d´。0≤w，w´≤6;0≤d，d´≤5。 i,j表示两个时间段，w为星期号，d为时间段号。 bi,j00.30.61ww',dd'ww',dd' |ww'|1o.w. 时间间距约束考虑的是一个班级某门课的周次数超过一次的情况，若同一班级同一门课程安排在同一天、或相邻近的两天属于低效率。 3、关联关系的局部描述

关联关系的局部描述如图所示： 教师

班级

教室 课程

时间1 时间2

在模型中，我们需要建立如下关系：

3

(1) 教师-课程：

布尔变量：xij （手工定义变量初值， i教师本学期上j课程）。

(2) 班级-课程：

布尔变量：yij （手工定义变量初值， i班级本学期上j课程）

(3) 课程-教室：

布尔变量：zij （i课程被安排在j教室）

(4) 课程-时间：

布尔变量：pij （i课程被安排j6wd时间段，课程结点度数表示重复

次数）

(5) 教室-时间：

4

布尔变量：qij （i教室被时间段j6wd时间段占用）

4、可行解的检验条件

（1） 同一个教师不能在同一时间段上两门课程。

（2） 同一个教室不能在同一时间段被两门课程占用。 （3） 同一个班级不能在同一时间段安排两门课程。 （4） 教室容量大于拟安排的班级的学生人数。

三、具体实现

㈠ 准备工作

选定教师集合、课程集合及每周课程重复次数、班级集合。 1．建立教师集合、课程集合、班级集合的关联关系。 (初始关联关系，由各系教学任务计划书可以确定)

2. 预留每周可排课时间段。

（可以取超过取班级课程量最大值作为周可排课时间段。 如：星期一至五，上午和下午1、2作为周排课时间段表） 3.总时间段空间：班级集合×周时间段可用空间。 4. 利用课程与班级的关联关系，限制课程选择时间段的范围。即，一个班级对应一张课程表，一对一。

5. 随机产生解空间。解的形式为：班级课程表序列为一个解。 6.检验每个解的协调条件，选出可行解集合。

7.计算每一个可行解的评价值；取最大值对应的解为一个满意解。 8.上述过程可以重复进行。 9.保存最终解。

10.根据教师、课程、班级、教室的关联关系。由最终解生成分类课程表： a. 教师时间表, b. 教室时间表, c. 班级时间表

(当无解时，逐步放大时间约束条件)（如： 允许下午1、2排课）。

（二）、系统结构

排课系统主要包括课表设置、添加/删除—课程、添加/删除—教师、添加/删除—班级、添加/删除—教室、课表查询、新建课程、排课等功能（如下图）。

5 排课系统 设 置 新建课程 排 课 查 询 教课教选选选设随协约班教 师 表 室 择择择定机调束级师 教教班学课检检课课 师 室 级 时 表 验 验 表 表 课 班程 级

（三）、自动排课系统模块：

1、 课表设置模块

2、 添加/删除—课程模块； 3、 添加/删除—教师模块； 4、 添加/删除—班级模块； 5、 添加/删除—教室模块； 6、 课表查询模块； 7、 新建课程模块； 8、 排课模块。

（四）、系统功能及部分代码 1、 排课系统的“设置”中有课表设置、添加/删除—课程、添加/删除—教师、添加/

删除—班级、添加/删除—教室四项。 a、 点击“课表设置”按钮进入课表样式设置（如图1） 每周上课天数的下拉框中可选值为0~7；

每天上午上课节数的下拉框中可选值为0~4； 每天下午上课节数的下拉框中可选值为0~4； 每天晚上上课节数的下拉框中可选值为0~4；

选定各项的值后，按确定按钮，系统将自动保存和生成课表样式。

6

教室课表

图1 课表样式设置模块代码：

private void button1_Click(object sender, System.EventArgs e) { long day,morning,afternoon,night; day=Int64.Parse(comboBox1.SelectedValue.ToString()); morning=Int64.Parse(comboBox2.SelectedValue.ToString()); afternoon=Int64.Parse(comboBox3.SelectedValue.ToString()); night=Int64.Parse(comboBox4.SelectedValue.ToString()); WindowsApplication5.Form2.ActiveForm.Close(); }

b、点击“添加/删除—教师”按钮进入教师设置（如图3）

在输入框中录入教师名，按添加按钮，教师名被录入教师库；删除教师，可以先选中要删除的教师名，按删除按钮即可，此处不支持复选，如要重新录入教师可按全部全部清空按钮即可；设置该教师的时间表，选定教师的时间，〉〉（添加）或〈〈（删除），设置并保存这个教师的时间表。

7

private void button2_Click(object sender, System.EventArgs e) { listBox1.Items.RemoveAt(listBox1.SelectedIndex); teacher[n]=null; n=n-1; } private void button3_Click(object sender, System.EventArgs e) {

listBox1.Items.Clear();

}

c、点击“添加/删除—课程”按钮进入课程设置（如图2）

在输入框中录入课程名，按添加按钮，课程名被录入课程库；删除课程，可以先选中要删除的课程名，按删除按钮即可，此处不支持复选，如要重新录入课程可按全部全部清空按钮即可。

图3 添加/删除—教师模块代码：

private void button1_Click(object sender, System.EventArgs e) { listBox1.Items.Add(textBox1.Text); teacher[n]=listBox1.Text; n=n+1; }

图2

添加/删除—课程模块代码：

private void button1_Click(object sender, System.EventArgs e)

8

{ listBox1.Items.Add(textBox1.Text); subject[n]=listBox1.Text; n=n+1; } private void button2_Click(object sender, System.EventArgs e) { listBox1.Items.RemoveAt(listBox1.SelectedIndex); subject[n]=null; n=n-1; } private void button3_Click(object sender, System.EventArgs e) { listBox1.Items.Clear();

}

d、点击“添加/删除—教室”按钮进入教室设置（如图4）

在输入框中录入教室名，按添加按钮，教室名被录入教室库；如教室可同时容纳多个班级上课，将教室的容量选定；删除班级，可以先选中要删除的教室名，按删除按钮即可，此处不支持复选，如要重新录入教室可按全部全部清空按钮即可；设置该教室的时间表，选定教室的时间，〉〉（添加）或〈〈（删除），设置并保存这个班级的时间表。

图 5

9

添加/删除—教室模块代码：

private void button1_Click(object sender, System.EventArgs e) { listBox1.Items.Add(textBox1.Text); classroom[n]=listBox1.Text; n=n+1; }

private void button2_Click(object sender, System.EventArgs e) { listBox1.Items.RemoveAt(listBox1.SelectedIndex); classroom[n]=null; n=n-1; }

private void button3_Click(object sender, System.EventArgs e) { listBox1.Items.Clear(); }

e、点击“添加/删除—班级”按钮进入班级设置（如图4）

在输入框中录入班级名，按添加按钮，班级名被录入班级库；删除班级，可以先选中要删除的班级名，按删除按钮即可，此处不支持复选，如要重新录入班级可按全部全部清空按钮即可；设置该班级的时间表，选定班级的时间，〉〉（添加）或〈〈（删除），设置并保存这个班级的时间表。

图4

添加/删除—班级模块代码：

10

private void button1_Click(object sender, System.EventArgs e) { listBox1.Items.Add(textBox1.Text); class[n]=listBox1.Text; n=n+1; }

private void button2_Click(object sender, System.EventArgs e) { listBox1.Items.RemoveAt(listBox1.SelectedIndex); class[n]=null; n=n-1; }

private void button3_Click(object sender, System.EventArgs e) { listBox1.Items.Clear(); } 2、 新建课程

新建课程模块包括选择教师、选择教室、选择班级和设定学时四项。 a、 选择教师

按下新建课程进入选择教师模块。从下拉框中选择一门课程（下拉框中的课程从课程库中读入），按下添加/删除老师按钮，为该门课制定授课教师；按下添加/删除教师按钮，为该门课添加可以使用的教室。

11

点击确定后回到选择老师界面，按下一步按钮进入XX课程，从下拉框中选择一个老师（从课程库中获取），设定学时数，选择所教班级，保存老师信息。

12

3、 排课

排课模块包括随机课表、协调检验、约束检验三项。

按下随机课表，此时系统根据数据库中的数据随机生成时间表，分别存于教师、教室、班级时间表中。方法：从数据库中得到〈班级、教师、课程〉固定关系，然后随机产生一个局限于最大时间段的时间点（最大时间段=每周上课天数*每天上课节数），这时就得到了〈班级、教师、课程、时间〉的固定关系，同样将能使用的教室加入固定关系中，得到随机课表。

协调检验是根据协调条件，将随机产生的时间表进行过滤，能满足协调条件的班级课程表形成可行解序列。

方法：用协调条件检验随机产生的课表序列。从教师时间库中得到每一个教师上课的时间段，检验是否重复，如重复则表示该教师在同一时间段上了两门课，此课表不能用，舍弃；从教室时间库中得到每一个教室使用的时间段，检验是否重复，如重复则表示该教室在同一时间段被两门课占用，此课表不能用，舍弃；从班级时间库中得到每一个班级上课的时间段，检验是否重复，如重复则表示该班级在同一时间段排了两门课程，此课表不能用，舍弃；再从生成的课程表中检验教室容纳的学生人数是否大于上课班级的人数。最后通过协调条件的课程表形成可行解序列。

约束检验是在可行解序列中，选出符合初始约束并且效率值最大的课程表。 方法：先对时间表的初始约束。约束时间表中某些时间段不能排课。

13

用一个与T同型的矩阵C定义。

cij1: 表示星期i第j时间段可排课，

cij0: 表示星期i第j时间段不能排课。

再从可行解序列中求出各自的效益值，取其最大值。效益值=上课效果值+教室利用率+课程时间间距。

上课效果值的计算：用一个长为6的数组表 a表示。ai：第i时段上课效果值 时段号 1 1 2 0.9 3 0.8 4 0.7 5 0.8 6 0.7 ai 教室利用率：学生人数/ 教室容量；

课程时间间距：

同一班级同一门课程安排在同一天、或相邻近的两天属于低效率。 定义一个4242时间段关联矩阵B=(bij) i6wd,j6w'd'。0w,w'6，0d,d'5

0ww',dd0.3ww',dd' bij

0.6|ww'|1o.w.1

4、查询

按下查询全部课表，弹出查询课表界面（如图6）。根据需要选择班级课程表、教室时间表、教师课程表。方法：根据所选的查询条件，分别从教师时间库、教室时间库、班级时间库中得到相应数据显示于指定区域，形成课程表。

14

㈤、遗传算法进行求解并优化

遗传算法的基本原理是：首先采用某种编码方式（如二进制编码）将解空间映射到编码空间，每个编码对应问题的一个解（称为染色体或个体）。一般通过随机方法确定初始的一群个体（称为种群），在种群中根据适应值或某种竞争机制选择个体，利用各种遗传操作算子产生下一代，如此进化下去，直到满足期望的终止条件。 1、 解的表示

表单元：一个班级的课程表为一个表单元。每周按7天计、每天按6个时间段计。如果周末和某些时间段不能排课，可以在初始约束时用一个布尔变量关闭。

时间段填充：单元中的时间段上用2元组（课程号，教室号）进行填充，当课程有重复次数时，固定课程号做重复填充。

原子码：班级码+课程码+星期码+时段码+教室码。 其中，班级码和课程码之间的关系是固定的。 表单元码：相同班级码的原子码集合。

个体码：假设有n个班，n个表单元码构成的序形成一个个体码。 可行解：满足协调条件的个体码。 2、 选择初始群体

(1) 根据给定的班级、该班级本学期所要上的课程集合、以及每门课的重复次数。随机产生星期码、时段码、教室码。与班级码和课程码构成一个原子码。 (2) 由原子码生成表单元码。 (3) 由表单元码生成个体码。

(4) 根据初始群体大小，生成由个体组成的初始群体。

15

3、 确定评价函数

评价函数在遗传过程中起着环境的作用，根据评价函数产生每个个体的适应值。这里，我们将时间段效率、时间间距约束、教室利用率等因素结合起来定义评价函数。时间段效率和时间间距约束涉及到上课的效果，教室利用率涉及到资源的利用问题。因此，应该优先考虑时间段效率和时间间距约束，在保证这两者的前提下，再考虑教室利用率。在评价函数中，前两者所占的比重相对较高。在每个个体中，每个三元组(星期码，时段码，教室码)对应着时间段效率和教室利用率。对于每个班的重复课程，对应着一个时间间距约束问题。将这三个因素按比例进行累加，就可以得到每个个体的适应值。 4、 遗传策略

通常，我们在遗传过程中采用三种算子：复制、杂交、变异，三者概率分别为Pr，Pc，Pm。

（1）复制算子(reproduction): 复制算子从群体中按照某一概率选择个体，某个体si被选择的概率Pi与其适应值成正比。通常，我们用轮盘赌(roulette wheel)方法进行实现。轮盘赌方法的实现如下：设群体S：s1,s2,……,sn,每个个体的适应值分别为f(s1),f(s2),……,f(sn),令sum＝f(s1)+f(s2)+……+f(sn),某个体所si被选择的概率Pi＝f(si)/sum (i=1,2,……,n),在0与sum之间产生一个随机数A，令B＝0，依概率p1,p2,……,pn在1到n之间随机产生一个个体编号m，将f(sm)累加进B中，直到B>A,将此sm作为被选个体。 （2）杂交算子(Crossover): 杂交算子将被选中的两个个体的基因链按概率Pc进行杂交，即在某一确定段上，对等交换代码，生成两个新的个体，杂交位置是随机的。 （3）变异算子(Mutation): 变异算子将新个体的基因链的各位按概率Pm进行变异，对二进制基因链来说就是对某些随机选取的位置取反。

在本系统中，对每一代群体，我们首先用协调条件进行一次筛选，剔除不满足协调条件的个体。然后才对个体进行演化计算产生下一代，从而加快了进化速度。

我们结合上述三种算子，采取了一种新的遗传策略。在得到群体中每个个体的适应值后，首先用轮盘赌方法将群体选择到交配池中，然后从交配池中每次取两个个体依概率进行杂交或变异产生临时新群体，此时，临时新群体数目与父代群体数目相同。接着，再将临时新群体中每个个体依概率选择或直接复制到下一代，或与上一代对应个体进行竞争(即若其适应值比上一代对应个体差，则将上一代个体保留下来，否则将其保留至下一代)。另外，将每一代中最优个体进行保存，每次产生新群体后，判断新群体中是否有比现有最优个体的适应值更好的，若有，则用其替换当前最优个体。通过父代和子代竞争，可以提高解的收敛速度。 5、 停机准则

我们可以采用多种方法来结束算法的执行，这里，我们采用两种方式相结合对停机加以控制：

（1） 设定最大遗传代数M，当遗传进行到第M代时，让其停机。

（2） 预先定义评价函数的一个指标数，当某一代最优个体的适应值达到或超过该指标数时，让其停机。

16

6、 输出结果

遗传算法结束后，可以得到适应值（即综合效率函数值）最好的个体。根据这个结果，我们将对个体码进行如下分解：

(1) 分解个体码成为表单元码。

(2) 分解每一个表单元码成为：班级码、课程码、星期码、时段码、教室码。 由分解后的班级码、课程码、星期码、时段码、教室码分别生成如下表格： (1) 班级课程表。

(2) 根据教师与课程的固定关系，生成教师工作表。 (3) 每个教室的时间占用表。 (4) 教学单位的课程总表。

四、结束语

本系统建立了一个自动排课的数学模型，是一个时间任务表的优化问题。利用遗传算法研究了对问题的求解。实验表明：系统运行的结果能得到较满意的课程安排方案。

参考文献：

1、 刘勇，康立山，陈毓屏.非数值并行算法（第二册）－遗传算法.北京：科学出版社，1998.

2、 王小平，曹立明.遗传算法－理论、应用与软件实现.西安：西安交通大学出版社，2002.

3、 Michalewicz Z. Genetic Algorithms+Data Structure=Evolution Programs.New York:Springer-Verlag,1996. 4、 张宗华，张伟，赵霖.利用遗传算法实现交通信号灯的控制.计算机科学，2002.29(9. 增刊): 178—181.

5、 田奕,刘涛,李国杰.求解可满足性问题的一种高效遗传算法.模式识别与人工智能,1996.9:209-212.

6、 Peter Brucker.Scheduling Algorithm. Berlin etc: Springer, 1998. 7、程序员杂志2002年合订本 电子工业出版社

17