图论在高校排课中的应用

[摘 要]课程表的编制是高校教务管理中非常重要与关键的一个工作。排课问题需要在满足一定的约束情况下，制定出相应的课程的时间安排及地点安排，是一种非常典型的组合优化问题。本文从某职业技术学院实际情况出发，提出了一种比较适合高校教学实际课程的比较通用的模型，并且针对这个模型给出一种实用的算法流程，并将这种算法应用到某职业技术学院，通过排课的相关实验验证了算法的有效性。

[关键词]排课 组合优化 图论

中图分类号：G423.07 文献标识码：A 文章编号：1009-914X（2016）10-0205-01

1 概述

随着计算机相关技术及网络技术的不断发展，职业技术学院的网络办公越来越受到重视[1]。学校开展了大量的校园网信息化建设，但是目前学校的排课系统相对比较落后，主要的原因在于由于学校的规模大小、约束的复杂程度不同，而且学校发展过程中存在很多的其他因素等的影响导致[2-3]。在排课的过程中，一方面要保证学校学生、教师与教室之间不能够产生相应的矛盾，同时还需要满足学校目前的各种资源的实际使用情况的相关约束。

本文主要是从图论的角度针对某职业技术学院的排课进行研究与分析。

2 问题提出

近些来年，由于某职业技术学院的招生规模在不断的扩大，学生的人数是在不断的增加。在学生人数不断增加的情况下，学校的教师、教室、实验室的机房等相关硬件资源增加相对来说比较的落后。一些专业的课程不但没有减少而且还在不断增加，一些专业课程还在不断的发生变化。这些不确定因素一定程度上增加了教务排课方面的负担。对于传统的手工排课来说，过去的学生人数比较少、课程的变化情况比较小，针对这种情况还会出现一些问题。

通过采用自动化的计算机排课系统能够从根本上解决人力、物力等方面的资源合理利用，还能够根据实际的数据变化情况动态产生变化。通过采用图论算法能够解决一些排课方面的问题，但是基于图论算法的排课系统也会存在一些不足之处。例如一些图论算法中将教师和班级作为二部图来进行计算，这种模型在实际的应用过程中忽略了高校教学中班级可能不固定的情况，还有一些模型没有考虑到学生的实际情况，将一门课程的两次课安排在同一天内，直接会增加学生的负担。

3 模型建立

在高校的教学管理过程中有两个比较明显的特点，第一个是教学的班级是不固定的，第二是学校每学期会开设一些公共课或者必修课，学生能够根据自己的兴趣爱好来选择一些课程，基于这两个特点，我们能够把高校的排课转换成图论理论模型进行计算。

在高校的教学过程中，大学的课程是以周为计算，将高校排课问题抽象成基本的图论模型G（V，E）：

（1）其中顶点集用来表示教师与课程两部分组成，集合T={T1，T2，T3，…，Tn}用来表示不同的教师集合，集合C={ C1，C 2，C 3，…，C n }表示课程的集合。

（2）在图G（V，E）的相关边集主要是由上面的两个顶点之间的连线组成。比如集合T={T1，T2，T3，…，Tn}中的一位老师教授集合C={ C1，C 2，C 3，…，C n }中的一节课，那么就将这两个顶点用实线连接起来。基于这个流程，高校排课问题就能够转变成一种偶图。

利用软色理论中的相关边着色理论来进行时间段的分配：在图G（V，E）中可以用例K中不同的颜色来进行边的软色处理，一种颜色就对应一个上课时间段。基于这个流程，就可以得到一张具有K个授课时间段的课表信息。在这个课表信息中，教师、课程不会发生相关的冲突问题。比如在图1中，教师T1每周有三次课C1，C2，C3，教师T2每周有一次课C4，教师T3每周有两次课C5，C6。

4 算法设计

在图论排课算法中，采用边软色的相关理论，通过构造相应的方法，对满足相关冲突与约束的边进行软色处理，在所有能够染色的颜色中寻找一种与所有实线课程的顶点之间的权重最接近的颜色进行软色即可。最终根据权重的颜色集合进行排序处理，对于权重大的进行优先排列，最后得到一张课表。

根据职业技术学院的教学大纲，画出相应的图G（V，E）。假设在图G（V，E）中目前已经有了n条实线边，根据课程的重要程度将其权重值设置为；图中的顶点的最大度设置为；教室的总的数量信息设置为L个。按照下面的算法进行计算与排课：

（1）作相应的图G=（C，E），用来表示相应的软色的实线边数的集合，用E里表示没有软色的实线边的集合。取相应的整数m（），构造数据来表示m中不同的颜色，另外用来表示颜色中边的个数。其中在初始化的时候设置为0。用表示这些颜色的相应的实线边的集合，初始化的值还是设置为。根据实际所需要的课程的情况及教室的实际的数量信息来选择适当的参数L（）信息。

（2）设置相应的构造方法为布尔型，主要是用来表示软色为k的所有实线的边中是否含有与实线边e进行连接的。如果有边e那么就不能继续进行软色为k，返回false值；如果没有那么需要进行相应的软色处理k，返回true值。这种方法需要进行相应的遍历处理E，时间复杂度为。

（3）对于在E中实线的相应的实线边e，如果发生，那么就需要遍历相应的颜色值，调用方法，找出其中返回值为true的所有的颜色集合K，在所有的能够软色颜色中找到一种与实线的边e的所有课程的顶点的权重最为接近的颜色，将这条实线边e软色为。同时，在这个算法过程中运行，，，，。通过这个步骤来遍历所有的集合E中的实线边，并且对这些实线边的遍历的颜色值，时间上的复杂度为。如果在遍历的过程中没有找到合适的颜色来进行软色，那么就不会有合适的返回值true，就表示没有找到合适的颜色值对这条边进行软色，那么就需要选取另外的整数m，重新返回到（1）。如果在选取一定的数目信息之后，仍然没有合适的颜色，那么就需要退出这个程序。

（4）如果发生，那么需要计算返回软色的结果E，，。否则就需要返回到步骤（3）中继续进行计算。

5 系统实现

采用目前留下的编程技术JSP语言实现某职业学院的高校排课系统的相关开发。用户操作起来比较方便，界面比较友好，功能完善性比较好，对系统的支持性要求很低。根据输入或者采集的初始数据信息使用上面的图论排序算法进行高校排课，排课生成的课程表可以按照班级、教师、教室、时间等多种关键字进行查询。

根据开发的这个系统，能够将职业技术学院2015、2016级的四个学期的课程进行重新的排列，生成新的课表。通过将新生成的课表与原来已经排好的课表之间进行比较。比较的对象包括同一种课程上课之间的间隔信息、学生主要课程每周上课的天数、学生平均每天的上课的节数安排以及相关的课程之间的冲突等。通过相应的测试能够发现，在这个系统中同一种课程上课之间的间隔信息、学生主要课程每周上课的天数、学生平均每天的上课的节数安排以及相关的课程之间的冲突能够得到很大的改变，相比于以前的系统具有很大的优化。

6 结论

综合来讲，利用先进的计算机技术进行排课是未来发展的趋势，本文主要是针对高校的排课中出现的主要问题进行深入的分析与研究，提出了一种比较适合高校教学实际课程的比较通用的模型，并且针对这个模型给出一种实用的算法流程，并将这种算法应用到某职业技术学院。

参考文献

[1] 于宙.基于遗传与模拟退火算法相结合的排课系统研究[D].大连理工大学，2014.

[2] 江萧，弋改珍，袁岚清.遗传算法在排课系统中的应用与设计研究[J].电脑知识与技术，2014（5）：1032-1035.