图论在高校排课问题中的应用.doc

图论在高校排课问题中的应用

摘要：本文主要是通过对普通高校排课特点和难点进行研究，设计了一种基于图论的排课方法。文章首先根据教学要求构造出排课模型图，然后用图论的边着色理论对课时进行分配，针对教室不够用的情况，根据图论中的相关定理，对排课模型图中的一些边赋了权值，然后选出权值最大的加权图作为最优的排课方法。通过对高校的实际排课数据进行测试，表明该模型可行且能够有效地提高排课效率。
关键字：排课、图论、边着色、匹配、加权图
1问题的提出
排课问题是典型的多类资源组合优化问题，它是针对有限的教师、教学场地及教学时间资源，为达到最佳教学目标而进行的综合有效规划，其实质就是为学校所设置的课程安排一组适当的教学时间与空间，从而使整个教学活动能够有计划有秩序地进行。
在排课问题中，其主要任务是将具有多种属性的各种资源，如教室、班级、教师、学生、课程、时间等，以一个周期的方式进行合理的匹配，使其不发生冲突。事实上，在排课问题中，每节课可抽象为教师和学生在时间和空间上的统一。因此，课表是协调教师和上课班级在上课时间、上课教室两个要素的总调度。一般而言，在教师讲授课程、班级及各部门课程的课时数量确定的前提下，排课必须满足下述基本要求：
（1）教学场地要满足教学任务的条件需求；
（2）同一教学班级、教学场地及教师，在同一时间均只能进行一次教学安排。
2 图论在排课中的应用
基于图论的排课模型
两点约定
在建立数学模型时，为了简化问题，这里假设：1)学校从周一到周五上课，每天上8节课，上午4节，下午4节，每两节课为一个授课单元，所以每周共有2O个授课单元。这里每个授课单元从周一上午(1，2)节到周五下午(3，4)节，分别由课时1，2，⋯ ，2O来表示，例如：课时1O表示周三上午(3，4)节。2)不考虑教室和教学设备的因素，即认为教室和教学设备总是可以使用的。
构造教学要求关联矩阵
排课表时首先需要明确教学要求。要求要表达一些主要的关联关系，即教师、课程、班级以及授课时间之间的关联关系，这一关联关系可以通过一个关联矩阵加以量化，并用计算机存贮和处理。假设有四位老师和五个班级，教学要求所对应的关联矩阵可用图1表示，其中,X表示教师,Y表示班级，P 表示教师X需要给班级Y上课的次数。
将关距联阵表示成图
图1的关联距阵可表示成一个图G。如图2所示，
由图2可知：图G是一个以为顶点集，以授课关系为边集的偶图。

图1 关联矩阵

用边着色理论分配课时
根据图论的边着色理论，k边着色是指k种颜色1,2,…,k对于图中各边的一种分配方案，着色时若没有相邻的两条边颜色相同，则称着色是正常的如果图G可以用k种颜色实现正常边着色，就说明，从每一个顶点发出的相邻边颜色不同。
本文把一种颜色对应一个课时，也即把图G的k边着色方案对应成k个课时的分配方案，为每一次授课分配时间段的过程就是边着色过程，这样可以既保证在一张有是个课时的课表内，某个教师所代的各班的课不在同一个课时，同时也可以保证每个班级所上的不同教师的课也不在同一个课时。那么，在假定教室足够多的情况下，就可以保证教师、班级和课程等要素不会发生冲突。下图3是图2的优化方案。[1]

图3中细实线代表第一种颜色对应课时1，点线代表第二种颜色对应课时2，点划线代表第三种颜色对应课时3，粗实线代表第四种种颜色对应课时4从图3中可以看出(以教师为例)，教师在课时l和课时2要给班级上课，在课时3要给班级上课，在课时4要给班级上课。其余教师的授课情况也可以从图中看出。[2]

应用
课表的编排包括教师和上课班级在上课时间(节次)和上课地点(教室)上的编排，这其中的组合可能性太多，为此可将模型简化为两个子模型：教师和上课班级在时间(节次)上的编排；教师和上课班级在地点(教室)上的编排，而这两个优化过程都可以转化为图论问题来解决。[1]
1、 排课问题的时间安排 ：
排课问题在时间上的安排实际上就是安排每一个教师在具体的时间段到某个具体的班级去上课。这个安排要求满足下面的条件：同一时间每位教师只能到一个班级去上课；一个班级在同一个时间也只能由一位教师来上课。用图论的知识可以来表示这个问题。例如：有n位教师，用来表示，有m个班，用来表示，教师要给班级上课就将与相连，如果一周内教师要给班级上2次课，则连2条线，以此类推。可以先作一个二部图G，使G=(X，Y，E)，其中X=()代表n个教师，Y=()，
代表m个班级，E代表与之间连接的边，如图4表示：

图4
有相同顶点的边称为相邻边。对每一条边进行着色，一种颜色代表一个时间段，通常在大学中2个课时为1节课，每天4节，一周5天，故而在排课问题中边色数是2O，代表的是20个时间段，同种颜色的边代表同一个时间段。因为在同一时间每位教师只能到一个班级去上课，而一个班级也只能由一位教师来上课，相邻的边代表有共同的教师或学生。不可以安排在同一个时间段同时上课，因此相邻的边不能着相同的颜色。时间表的安排就变成了对所有的边进行着色，有相同顶点的边着不同的颜色，而所有颜色能超过2O种的种类不。[2]
2 排课问题的地点安排：
课表在地点安排上则是安排某个班级在某个时间段在一个具体的教室上课的问题，它必须要满足的条件是：班级人数小于教室的容量，也就是容量大于班级人数的教室都可用，这样班级与教室之间就形成了一个多对多的关系。而事实上，一个班级在同一时间内只能到一个教室去上课．一个教室在同一时间内也只能有一个班级在上课。这就要将一个多对多的关系转换成为一个一一对应的关系，这实际上是一个匹配问题。同时考虑到，如果班级人数比较少而教室太大的话将会影响上课质量．因此．可对每个可用的教室进行赋权．这就形成了一个加权图的匹配问题。
例如：在某一时间段，有5个班级,需要安排教室上课，同时有5个教室可用，班级与教室之间的关系如图5表示：

图5
针对各个教师的适用情况进行赋值，设置权值如下：
矩阵中的每个元素分别代表第i个班级安排在第j个教室上课的合适度的权数，权数越高的教室表示越合适，那么就越优先考虑，最终要使得每个班级都能够安排到相对合适的教室，这就要求找到一个权数最高的分配方案。该问题即抽象为在赋权二部图中找一个权最大的匹配。这个问题可以利用Kuhn—Munkres算法求出最终结果。
将上面两个方面结合起来就是一个完整的排课问题，在边色数为20的情况下进行着色表示在2O个可用时间段内进行课程安排，而同种颜色互不相邻表示一个教师不能在同一个时间上两门课．同一个班级不能在同一个时间上两门课。在某个时间段上课教室的安排则可看为是一个一一对应的匹配问题。将这两部分结合起来就可以得到在每个时间段内课程的安排和每门课程具体在哪个教室授课的地点安排。从而得到一张完整的课程表。[2]
3 结束语
本文阐述了在排课问题中图论的具体应用，包括在安排时间上的应用本和安排地点上的应用。通过分析问题必须满足的约束条件。利用图论的边着色和匹配的知识加以讨论，使之能够成为解决排课问题的一个有效的方法。

参考文献：
[1] 蒋政.基于图论的排课问题研究[J].江南大学学报，2007.12
[2] 唐勇、唐雪飞.基于遗传算法的排课系统[J].计算机应用，2002.2
[3] 殷建红、吴开亚.图论及其算法[M].中国科学技术大学出版社，2005.6

图论及其算法

学 号

姓 名

年 级

专 业

20年 月 日