用图论方法解决排课冲突问题 陶华亭!，郭 玲" （ 郑州经济管理干部学院 计算机系，河南 郑州 !# $%&&%" ； "# 郑州工业贸易学校，河南 郑州 ） $%&&&’ 摘要：排课模型是教务管理系统的核心。排课可能造成的冲突有多种情况，包括实验室争用冲突、教室争用冲 突和时间上的冲突等。利用图论中边着色理论可彻底避免这种冲突发生的可能性，并在此基础上能够保证顺利调 课，达到排课的最佳效果。 关键词：排课模型；偶图；对集；边着色；可扩路；调课；优化 中图分类号： ,!%’#% 文献标识码： - 文章编号： （ !)’!($*.* "&&$ ） &/(&&.’(&$ 一、排课模型的基本要求 法。目前大多数算法是模仿手工排课的做法和经 排课表的基本要求是避免各种冲突，以免造成 验，通过计算机反复对比来避免冲突的发生，排课的 教学事故，但由于没有好的算法，在手工排课时，需 过程是直接按照排课的习惯进行时间和教室的分 要付出艰巨的劳动，尽管如此，也没有从理论上保证 配，遇到冲突了再设法调整，而每次调整都有可能造 不会冲突。因此，随着教学资源、师资力量和招生规 成新的冲突，不能保证最优解收敛的速度，因此，效 模的变化，每次需要多大的工作量、多长时间能排出 率很低。另外，这种算法不能保证最终方案较优。 来以及能不能正常安排教学过程都是一个未知数， 三、利用图论中边着色理论设计排课模型 这是教务管理人员最为头痛的事情。在排课表时， 图论中边着色理论可以从根本上避免手工排课 需要考虑的约束和资源限制太多，有时即便排出的 的不确定性，它可以在保证不冲突的前提下，分配授 课表能够运用，也不能保证这一排课方案是效果较 课时段，也可以对方案进行优化。下面结合一个简 好的。 单的例子，讨论该算法的原理和应用。 冲突限制主要表现在同一时段既不能一个老师 给两个班上课（合班除外），也不能有两个老师给同 假设一天内，有 个老师给 % ) 个班级分别代了 不同的课，一般在排课表前，首先填写教师定位表， 一个班上课；合班课不能跟小班课冲突，即某个班的 为了直观反映定位情况，可用如下关联矩阵表示： （ 01 12! ， " ， / …）表示教师， （ 34 ， " ， 42! / 的授课次 对班级 01 34 …）表示班级， 表示教师 514 小班课不能跟它与其他班的合班课排在同一时段 其中 内。资源约束是指实验室和合班教室一般都属紧缺 资源，排课时应该针对每个时间段平均分配使用的 数。 班级。除冲突限制及资源约束外，排课时还应考虑 相邻的两次课不能排得太近，排在一天或相邻的两 天都不符合要求。比如每周 $ 个学时的课程，排在 星期一、三或星期二、四或星期三、五都可以，每周 ) 个学时的课，排在星期一、三、五则是比较理想的。 为满足这方面的要求，需要在模型中设计效果优化 算法。 二、一般排课模型算法缺陷 排课模型中的关键是避免排课冲突的排课算 图 ! 教师定位表 用图论的方法表示这一授课定位关系 !# 收稿日期： "&&$(&)(&* 作者简介：陶华亭（ !*)$+ 万方数据 ），男，山西襄汾人，郑州经济管理干部学院计算机系讲师。 · ’. · 

这张定位表中的授课关系可以表示成一个图： 在三个时间段内。如果教室不够，可以考虑用较多 的颜色着色，如上例中用四种颜色着色，则需要占用 ’ 周有 个教室。在实际应用中，每天安排 个时间段，一 & 个时间段，就可以考虑使用 种颜色着色， $( $( 即把所有授课分为 $( 类，分别进入不同的时段。 下面按四个时间段对本例给出排课算法： 第一步：在图 % 中寻找不超过 ’ 个边的对集，用 一种线型（代表一种颜色）标注，得到如图 所示的 & 结果。所谓对集是指被选中的每一条边与它的邻接 边必须是不同的颜色，每条边的两个顶点必须分别 在两个顶点集中。如图 中 & *$#$*&#&*+#(*’#’ 形成 了一条由两种颜色着色的叉错通路。这一步可以得 到边集 ｛ 3$" #$*$ ， #&*& ， #’*’ ， #(*+ ｝，这个集合中的 边所代表的授课关系就被安排在第一个时间段。 这个图是一个以 ｛ ， ， ， ， !" ， #% #$ ｝为顶点集，以授课关系 #’ #& #( ｝ ! )" ｛ *$ ｛ ， ， ， ， *% ， *& *’ ， *( *+ ， #$*$ ， #$*& ， #$*( ， #(*% #%*% ， ， #%*’ ， ， #(*+ ,-." ， ， ， #&*& #%*+ ｝为 边 集 的 偶 图。 #&*+ #’*’ #’*$ 所谓偶图是指图中的所有顶点可以分为两个集合， #’*( #(*’ 即 ! 顶点集和 ) 顶点集，而每一条边的两个顶点分 别在两个顶点集中，如图 所示。 % 图 % 教师与班级、课程关联图 找到第 $ 个对集的关联图 5$ 中从边集 5$ 得到一张新的关联图 5$ （ 6 ）中去掉 中的 3$ ，如图 所 5% 中，再寻找不 ’ " 3%!3&!3’ 5% 个边的对集，得到 。在图 ’ 中的个边， ｛ ， 3%" #%*% 3% 图 & 第二步：在 ） 5$ 73$ ） 边， （ 6 示。 （ 6 超过 ’ ， #(*’ ｝。 #&*+ 用边着色方法分配授课时间段 %/ 该图共有 个顶点、 $’ $$ 条边，如果使用 种颜 0 色，经过着色后，能满足从每一个顶点发出的相邻边 有不同的颜色，就认为该图可以 正常着色。一个 0 图的 0 边着色，可以看做是对所有边的一个 分类 0 方案。如果用 0 种颜色能够正常着色，一种颜色对 应一个授课时间段，就可以保证在一张有 个时间 0 段的课表内，每个老师代的各班的课不在一个时间 段，同样，每个班级上的不同老师的课也在不同的时 间段。 我们考虑一天内可以安 排 的 时 间 段 一 般 为 & 个，多则 ’ 个，即上午 节。四个时间段用 $% ｛ 节、 &’ ， 4% 节和下午 节、 12 (+ ， 4& ， 4’ ｝来表示。 条边，显然，要在三个时间段 3" 4$ 该定位表共有 $’ 内安排全部课程，则每个时间段需要安排 个课头， ( ；如果占用 ’ 即需要占用最少 ( 个教室， &"("$(#$’ 个时间段，则每个时间段平均要排 个课头， 。可以看出，少于 "$+#$’ 的，因为该图中所有顶点的最大度为 & & 种颜色才能正常着色，换句话说，一个老师有三个课 & ，至少需要 ’ ’"’ 个时间段是无法安排 头，少于三个时间段是无法安排的。 理论上，如果教室足够，我们可以用不少于最小 边色数的颜色着色，如上例中，可以把所有课程安排 · 万方数据 · 22 图 ’ 简化过程中的关联图 第三步：在 中去掉 得图 。在 5& （ 6 5& " 3&!3’ 5% ） 5% 中的边， （ 6 3% ） 73% 中寻找对集，得到 5% 

!"# ｛ $%&" ， $’&( 最后，在 *" ｝。 ， $(&) 中去掉 !" 后剩下的就是第四个时 "-. 边着色的实际意义 $%&% 表示老师 $% 给班级 &% 的一次授课。边着色的 间段的授课关系， ｛ !(# $%&) ， $’&+ ， $(&% ， $)&’ ｝，如图 所示。 + 基本规则是：从同一顶点发出的边称为相邻边，无论是从 顶点集发出的边还是从 顶点集发出的相邻边之间 / 不能有相同的颜色，当我们按照颜色安排时段时，不同的 0 颜色就被安排在不同的时段，保证了一个老师不会同时 上两个班的课，一个班级不会同时听两个老师讲课。 经过着色以后，如果不考虑教室资源，只考虑时间 不冲突的限制，一个时段安排一种颜色代表授课关系，那 么在 个时段内就可以安排完所有授课任务，保证不会 " 发生冲突。这一结果可以用图 直观表示。 1 图 ) 简化过程中的关联图 *" 图 + 简化过程中的关联图 通过上面寻找对集的过程，我们就可以得到一 张 ( 个课时的课表，如图 所示。 !%# !’# !"# !(# ｛ $%&% ｛ $’&’ ｛ $%&" ｛ $%&) ， $"&" ， $"&+ ， $’&( ， $’&+ ， $(&( ， $)&( ， $(&) ， $(&% ｝ , ｝， ， $)&+ ｝， ， $)&’ ｝。 图 , 一张 ( 个时段的课表 图 1 一张 个时段的课表 " 可以验证，上例使用超过 种的颜色都可以正常着 " 色，但少于 种颜色是不可能的，因为该关联图的顶点最 种颜色是该图进行正常着色的最小 " ，即 大度为 " !#" ， " 边色数。换句话说，这个排课任务不可能在小于 个时 " 间段的课表内排下。 个课时是最少的课时了，但要求有足够多的教室 " 是 ( 放在 ( 或实验室资源。如果用 种颜色着色，就表示这个课表 个时段的课表，这时，在 个时间段可以排下的课表 个时间段里，每个时间段就可以占用较少的教室 ( " 数，把所有的授课关系尽量平均分布在 个时间段内，就 得到了一张占用教室数最少的课表。大学里一般每天安 ( 排三个时段，一周有 个时段，用 种颜色着色，就是 %) %) 一张周课表。 四、实现调课的算法 图 是一张 个时间段的课表，以此为例，如果由于 , ( 老师的原因或是实验室的原因，需要调换某个班的上课 时间，往往需要多个班级和教师连动。这在手工调课时， 比较困难，下面介绍图论中的方法。 如图 所示，假设只有三个实验室，第一个时段内 2 ( 的 个班都要上实验课，而第 个时段内的实验室有剩 " 余，教师 代的 这个班不上实验课，我们试图把 和 /( 0) 两个时段的 !" 0( 这个时段要上教师 !" 的调课过程。 /’ 和 对调，但发现 0) 的课，这样就形成了一种连动 0( !% 这个班在 万方数据 · 21 · 

图 ! 需要调课的课表 调课过程的算法：在 "#!"$ 的图中寻找“可扩 路”，如图 所示。 #% 按周课表执行，每周可以设计 个时间段。 图 #) 调课后的新的课表 个或 #+ )% 每门课一般每周有两次或三次课，各次授课之 间，需要有一定的时间间隔，这需要在分配时间段或 调课时，设计一种效果评价函数，根据该函数优先分 配效果较好的时间段。比如教师 对班级 的两 .# &# 次授课，第一次排在周一的一二节这个时段以后，第 二次排在周一的任何时段和周二的任何时段，其效果 评价函数值都很小，而周三的某个时间段效果系数就 比较理想。对每周 个时段的课表，如果第一次课 #+ 分配在 ，第二次根据效果函数就可能被分配在 "/ "# 或 。 "! "0 对于合班课，应该考虑小班课与大班课的冲突问 在寻找对集分配时段时，应考虑优先系数，对合 班课、周学时多的课以及实验室紧张的课，应优先分 配。 六、结束语 该排课模型从理论上避免了排课中的时间冲突 问题，并给出了调课算法。对于排课效果、合班课冲 突以及实验室和教室资源冲突等问题，需要在排课 过程中，增加效果评价函数和资源冲突检测算法。 由于实际应用中排课任务量非常大，手工实现很困 难，所以作者设计了计算机实现的相关模型。由于 篇幅所限，本文对此不再讨论。 ［ ］吴文虎，王建德 # ［参 考 文 献］ 图论的算法与程序设计［ 1 ］ 北京：清华 " 1 大学出版社， #!!/1 图论［ ］ 北京：北京理工大学出版社， ［ ］王朝瑞 ) ［ ］徐俊明 $ 1 " 1 图论及其应用［ 1 ］ 合肥：中国科学技术大学出 " 1 #!!/1 调课算法———寻找可扩路 或 的 有 一 条 交 错 路 题。 图 #% 在 图 #% 中，经 过 &’ ，可以把其中的颜色对调，这样得到了新的时 ()*’(’*+ 间分配， ｝，如图 "#, ## (’*’ .+&- 时间分配为： ， ()*’ ｛ (#*# 所示。由于 ， ($*$(’*+ ｝， ， (+*- ｛ (#*$ 时间段的课太多，而 "$, ， "# 可以直接调色，因此将其调到 时段。最终的 "$ "#, ｛ (#*# ， ()*’ ， ($*$ ， (’*+ ｝， "$, ｛ (#*$ ， (’*’ ｝。 ， (+*- 五、更多的考虑 在高校实际排课中，一般要考虑如下因素： 图 ## 调课后的新的关联图 版社， #!!01 · 万方数据 · %! 

用图论方法解决排课冲突问题 作者： 陶华亭， 郭玲 作者单位： 陶华亭(郑州经济管理干部学院,计算机系,河南,郑州,450052)， 郭玲(郑州工业贸易学校 刊名： 英文刊名： 年，卷(期)： ,河南,郑州,450007) 郑州经济管理干部学院学报 JOURNAL OF ZHENGZHOU ECONOMIC MANAGEMENT INSTITUTE 2004,19(3) 1次 被引用次数： 参考文献(3条) 1.吴文虎;王建德 图论的算法与程序设计 1997 2.王朝瑞 图论 1997 3.徐俊明 图论及其应用 1998 本文读者也读过(10条) 1. 陶华亭.张桃改.Tao,Huating.Zhang,Tagai 基于图论方法的自动优化排课模型研究[期刊论文]-微计算机信息 2005(27) 2. 蒋政.JIANG Zheng 基于图论的排课问题[期刊论文]-科技信息2010(15) 3. 王仲华.卢娇丽.Wang Zhonghua.Lu Jiaoli 图论在高校排课问题中的应用研究[期刊论文]-太原师范学院学报 （自然科学版）2010,9(1) 4. 胡顺仁.邓毅.王铮 基于高校排课系统中的图论问题研究[期刊论文]-计算机工程与应用2002,38(4) 5. 李雷孝.冯永祥.LI Lei-xiao.FENG Yong-xiang 高校计算机自动排课系统的研究与实现[期刊论文]-内蒙古工业 大学学报（自然科学版）2007,26(1) 6. 张健.ZHANG Jian 基于图论的高校排课系统实现[期刊论文]-重庆师范大学学报（自然科学版）2005,22(1) 7. 洪文.朱广斌 排课问题及其数学模型[期刊论文]-安徽电力职工大学学报2002,7(3) 8. 何永太 二部图在排课系统设计中的应用[期刊论文]-安徽水利水电职业技术学院学报2003,3(2) 9. 陈兆斗.CHEN Zhao-dou 优化的合班问题[期刊论文]-数学的实践与认识2007,37(7) 10. 章小莉.王文杰.赵耿 基于模糊聚类分班的排课表系统设计与实现[期刊论文]-计算机系统应用2009,18(10) 引证文献(1条) 1.陶华亭.张桃改 基于图论方法的自动优化排课模型研究[期刊论文]-微计算机信息 2005(27) 本文链接：http://d.g.wanfangdata.com.cn/Periodical_zzjjglgbxyxb200403031.aspx