基于遗传算法的排课系统
一、介绍
随着近几年各个高校的合并与扩招，我国的综合性大学和各个高校中在校的学生数量的大大增加，对于高校教务部门来说，排课工作是非常令人头痛的事，经常会出现课程排列冲突，比如：一个教师在同一时间上两门课，有两个教师同时去一个教室上不同的课程，有些教师在特定时间不可以上课。如果没有很好地解决这些冲突，必将产生教学混乱等现象。可见，排课算法的正确性、高效性是非常关键的。[1]
20世纪70年代中期，就有人论证了课表问题是NP完全问题。当课表所涉及的任何信息量稍有变化将会导致课表编排选择方案的剧增。课表问题存在固定的数学模型，能找到相应的解，且是一组解集。为此，现提出一些关于高校教学管理系统排课的算法。
二、排课问题的数学模型
学校排课问题本质上是时间表问题的一类典型应用实例，是为了解决课程安排对时间和空间资源的有效利用并避免相互冲突。在排课过程中，需要考虑课程教学效果、满足教师特殊要求等多项优化指标，将各门课程安排到相应的时间和教室需要付出一定的“成本”(Cost)。[2]
符号与约束条件
设课程集合：L={l1，l2，.，lp，.，lP}；班级集合：C = {c1，c2，.，cm，.，cM} ；教室集合：R = {r1，r2，.，rn，.，rN} ；教师集合：S={s1，s2，.，sk，.，sK} ；时间集合：T={t1，t2，.，td，.，tD}；时间与教室对的笛卡尔积为：G=T·R=(t1，r1)，(t1，r2)，.，(tD，rN)；G中的元素称为时间教室对；课表问题的求解过程就转化成为每一门课程寻找一个合适的时间教室对。
排课过程中必须满足各种约束条件，可以将各种约束条件归纳成两类以简化分析过程。
（1）硬约束条件
硬约束条件是在排课过程中由于各类资源的有限，因此必须满足而无法变更的约束条件，通常只要满足下面三类硬约束条件就能够保证在排课的过程中不发生此类冲突。
①同一时间，一个教师不能同时有一门以上的课程，记为R1：
R1 为： ≤1
其中：k=1，.，K； d=1，.，D。
=1 教师sk 在时间td 和教室rn 上课程lp；0 否则。
②同一时间，一个班级不能同时有一门以上的课程，记为R2：
R2 为： ≤1
其中：m=1，.，M； d=1，.，D。
=1 班级cm 在时间td 上教师sk 的课程lp；0 否则。
③同一时间，一个教室不能同时有一门以上的课，记为R3 ：
R3 为： ≤1
其中： n = 1 ， .， N ； d = 1 ， .， D。
=1教室rn在时间td由教师sk上课程lp；0否则。
（2）软约束条件
软约束条件是在排课过程中可以满足但又可以不完全满足的约束条件，是排课过程中在满足硬约束条件的基础上能尽量要求满足的约束条件，软约束条件会因不同的教学情况而有所差异。通常也可以通过调节软约束条件的满足程度而改变排课的效果，可以将一定要满足的软约束条件转换为“硬约束条件”。
以下是排课过程中常用的软约束条件，也是本文中所考虑的软约束条件。
(1) 课程尽量安排在教学效果较好的节次。课程上课的效果与上课的节次有密切的关系，在排课的过程中我们应该尽量将课程安排在教学效果较好的节次中，用ph表示第h节次的教学效果系数：
(2) 多学时课程的周次安排要错开。在实际的排课过程中，一般对于每周多学时( ≥4) 的课程，应该能够尽量将其隔天安排，才能保证有较好的教学效果，用qt(t=1，2，3，4，5)表示一门课程安排隔天天数t的教学效果系数：
(3) 满足教师所提出的上课时间和地点的要求。课程的主讲教师和课程有着对应的关系，我们将教师提出的上课要求固化在其对应的课程上，用hj表示满足课程上课要求的系数：
(4) 当一个班的周总课时数需在某个数值范围内的要求。
三、排课问题的算法
1.算法分析
排课的冲突异常复杂，对于这些冲突的复杂度我们进行分析。以下给出分析的过程。
过程1：将模型中的五个集合降维为一个给定四维空间V(S，T，R，C)，称之为：课表。
四维分别代表了：
S（教师）：全校所有课程的任课教师；
T（时间）：上课的时间段，每天分为1-2、3-4、5-6、7-8、9-10，总共五个时间段，每学期20周，每周五天，合计每学期有500个上课时间段；
R（教室）：全校所有的可用教室，包括不同的教室属性，如：教室大小、是否为多媒体或语音教室等等；
C（班级）Class：当前学期的所有教学班级，包括班级属性，如：班级人数、是否合班。
过程2 ：在课表V中求解存在着子空间L，且L
过程3 ：在课表V中求解存在着四维向量l (Sr，Tm，R，C)，且l∈L，那么称l为：课。
过程4 ：在课表编排过程中，对于P( li∈VΛlj∈L，i，j∈N)，li (Tr，Tm，R，C)与lj (Tr，Tm，R，C)，没有冲突，认为V是：有效课表。[3] [4]
通过对四维向量li ( Sr，Tm，R，C)与lj (Sr，Tm，R，C)的简化。在排课过程中的所有关系情况TmR + Tm RC。
那么：由过程1、过程2 可以推导出，在课表空间中，恒有f (Tr，Tm，R，C)，那么V就是有效的课表。
最后为了简化，再给出过程5：
过程5 ：在课表V中，对于li ( Sr，Tm，R，C)与lj (Sr，Tm，R，C)，i、j∈N，没有冲突，记为：liΨlj ；对于Li、Lj没有冲突，记为：LiΨLj。
这样有对于P( li∈VΛlj∈L)，li (Sr，Tm，R，C)与lj (Sr，Tm，R，C)，i、j∈N，没有冲突，就可以得到VΨL。
四、结束语
该模型与求解方法已在实际中得到应用，取得了较好的效果。在使用遗传算法优化后排课算法的实际效率有极大的提高。因此用遗传算法实现类似排课问题的最优解也是一种比较简单实用的方法，收敛速度很快，时间段分配均匀。[5]
但是在实际应用中也可能没有终止条件，目的是可以依次提供不同的可行解以供使用者选择直到所有解给完或者使用者终止。如果只考虑最优解的问题，可以使用迭代的适应度几乎不变作为终止条件或者规定迭代次数。值得一提的是，有些实际问题的可行解可能是唯一的，比如教学场地或教师资源紧缺的情况，更严重的是如果约束条件太苛刻，甚至可能没有可行解，在此类情况下人工干预还是有必要的。
参考文献
[1] 陶滔，李赫男，熊正为．多维冲突在排课算法中的应用[J]．华东地质学院学报．2001，(4):256～259．
[2] 吴志斌，陈淑珍，孙晓安．回溯算法与计算机智能排课[J]．计算机工程．1999,(3):792801．
[3] 高喜玛，张萍．大学自动排课系统内核算法设计[J]．南阳师范学院学报．2003 ，(12)．
[4] 张亚东，叶克江．高校计算机排课系统的设计与实现[J]．郑州轻工业学院学报．2003 ，(12)．
[5] 董艳云，钱晓群，张宇舒．基于课元相关运算的高校排课算法[J]．西南交通大学学报．1998,(12):67026731．
随着近几年各个高校的合并与扩招，我国的综合性大学和各个高校中在校的学生数量的大大增加，对于高校教务部门来说，排课工作是非常令人头痛的事，经常会出现课程排列冲突，比如：一个教师在同一时间上两门课，有两个教师同时去一个教室上不同的课程，有些教师在特定时间不可以上课。如果没有很好地解决这些冲突，必将产生教学混乱等现象。可见，排课算法的正确性、高效性是非常关键的。[1]
20世纪70年代中期，就有人论证了课表问题是NP完全问题。当课表所涉及的任何信息量稍有变化将会导致课表编排选择方案的剧增。课表问题存在固定的数学模型，能找到相应的解，且是一组解集。为此，现提出一些关于高校教学管理系统排课的算法。
二、排课问题的数学模型
学校排课问题本质上是时间表问题的一类典型应用实例，是为了解决课程安排对时间和空间资源的有效利用并避免相互冲突。在排课过程中，需要考虑课程教学效果、满足教师特殊要求等多项优化指标，将各门课程安排到相应的时间和教室需要付出一定的“成本”(Cost)。[2]
符号与约束条件
设课程集合：L={l1，l2，.，lp，.，lP}；班级集合：C = {c1，c2，.，cm，.，cM} ；教室集合：R = {r1，r2，.，rn，.，rN} ；教师集合：S={s1，s2，.，sk，.，sK} ；时间集合：T={t1，t2，.，td，.，tD}；时间与教室对的笛卡尔积为：G=T·R=(t1，r1)，(t1，r2)，.，(tD，rN)；G中的元素称为时间教室对；课表问题的求解过程就转化成为每一门课程寻找一个合适的时间教室对。
排课过程中必须满足各种约束条件，可以将各种约束条件归纳成两类以简化分析过程。
（1）硬约束条件
硬约束条件是在排课过程中由于各类资源的有限，因此必须满足而无法变更的约束条件，通常只要满足下面三类硬约束条件就能够保证在排课的过程中不发生此类冲突。
①同一时间，一个教师不能同时有一门以上的课程，记为R1：
R1 为： ≤1
其中：k=1，.，K； d=1，.，D。
=1 教师sk 在时间td 和教室rn 上课程lp；0 否则。
②同一时间，一个班级不能同时有一门以上的课程，记为R2：
R2 为： ≤1
其中：m=1，.，M； d=1，.，D。
=1 班级cm 在时间td 上教师sk 的课程lp；0 否则。
③同一时间，一个教室不能同时有一门以上的课，记为R3 ：
R3 为： ≤1
其中： n = 1 ， .， N ； d = 1 ， .， D。
=1教室rn在时间td由教师sk上课程lp；0否则。
（2）软约束条件
软约束条件是在排课过程中可以满足但又可以不完全满足的约束条件，是排课过程中在满足硬约束条件的基础上能尽量要求满足的约束条件，软约束条件会因不同的教学情况而有所差异。通常也可以通过调节软约束条件的满足程度而改变排课的效果，可以将一定要满足的软约束条件转换为“硬约束条件”。
以下是排课过程中常用的软约束条件，也是本文中所考虑的软约束条件。
(1) 课程尽量安排在教学效果较好的节次。课程上课的效果与上课的节次有密切的关系，在排课的过程中我们应该尽量将课程安排在教学效果较好的节次中，用ph表示第h节次的教学效果系数：
(2) 多学时课程的周次安排要错开。在实际的排课过程中，一般对于每周多学时( ≥4) 的课程，应该能够尽量将其隔天安排，才能保证有较好的教学效果，用qt(t=1，2，3，4，5)表示一门课程安排隔天天数t的教学效果系数：
(3) 满足教师所提出的上课时间和地点的要求。课程的主讲教师和课程有着对应的关系，我们将教师提出的上课要求固化在其对应的课程上，用hj表示满足课程上课要求的系数：
(4) 当一个班的周总课时数需在某个数值范围内的要求。
三、排课问题的算法
1.算法分析
排课的冲突异常复杂，对于这些冲突的复杂度我们进行分析。以下给出分析的过程。
过程1：将模型中的五个集合降维为一个给定四维空间V(S，T，R，C)，称之为：课表。
四维分别代表了：
S（教师）：全校所有课程的任课教师；
T（时间）：上课的时间段，每天分为1-2、3-4、5-6、7-8、9-10，总共五个时间段，每学期20周，每周五天，合计每学期有500个上课时间段；
R（教室）：全校所有的可用教室，包括不同的教室属性，如：教室大小、是否为多媒体或语音教室等等；
C（班级）Class：当前学期的所有教学班级，包括班级属性，如：班级人数、是否合班。
过程2 ：在课表V中求解存在着子空间L，且L
过程3 ：在课表V中求解存在着四维向量l (Sr，Tm，R，C)，且l∈L，那么称l为：课。
过程4 ：在课表编排过程中，对于P( li∈VΛlj∈L，i，j∈N)，li (Tr，Tm，R，C)与lj (Tr，Tm，R，C)，没有冲突，认为V是：有效课表。[3] [4]
通过对四维向量li ( Sr，Tm，R，C)与lj (Sr，Tm，R，C)的简化。在排课过程中的所有关系情况TmR + Tm RC。
那么：由过程1、过程2 可以推导出，在课表空间中，恒有f (Tr，Tm，R，C)，那么V就是有效的课表。
最后为了简化，再给出过程5：
过程5 ：在课表V中，对于li ( Sr，Tm，R，C)与lj (Sr，Tm，R，C)，i、j∈N，没有冲突，记为：liΨlj ；对于Li、Lj没有冲突，记为：LiΨLj。
这样有对于P( li∈VΛlj∈L)，li (Sr，Tm，R，C)与lj (Sr，Tm，R，C)，i、j∈N，没有冲突，就可以得到VΨL。
四、结束语
该模型与求解方法已在实际中得到应用，取得了较好的效果。在使用遗传算法优化后排课算法的实际效率有极大的提高。因此用遗传算法实现类似排课问题的最优解也是一种比较简单实用的方法，收敛速度很快，时间段分配均匀。[5]
但是在实际应用中也可能没有终止条件，目的是可以依次提供不同的可行解以供使用者选择直到所有解给完或者使用者终止。如果只考虑最优解的问题，可以使用迭代的适应度几乎不变作为终止条件或者规定迭代次数。值得一提的是，有些实际问题的可行解可能是唯一的，比如教学场地或教师资源紧缺的情况，更严重的是如果约束条件太苛刻，甚至可能没有可行解，在此类情况下人工干预还是有必要的。
参考文献
[1] 陶滔，李赫男，熊正为．多维冲突在排课算法中的应用[J]．华东地质学院学报．2001，(4):256～259．
[2] 吴志斌，陈淑珍，孙晓安．回溯算法与计算机智能排课[J]．计算机工程．1999,(3):792801．
[3] 高喜玛，张萍．大学自动排课系统内核算法设计[J]．南阳师范学院学报．2003 ，(12)．
[4] 张亚东，叶克江．高校计算机排课系统的设计与实现[J]．郑州轻工业学院学报．2003 ，(12)．
[5] 董艳云，钱晓群，张宇舒．基于课元相关运算的高校排课算法[J]．西南交通大学学报．1998,(12):67026731．
java 文章被收录于专栏
java学习总结，技术积累
查看4道真题和解析
