基于分布式势博弈算法的排课方法研究

郑加石+廉政

摘要：排课问题已被证明是NP完全问题，排课问题的难度随课表规模的增大而增加。通过对排课问题建立图形着色模型，采用分布式勢博弈算法求解。分布式势博弈算法从局部最优入手，最终形成全局最优，适用于排课问题求解；同时势博弈算法对排课问题中课表微调问题的响应是高效的。实践表明，相较于遗传算法、模拟退火算法，分布式势博弈算法对解决排课系统问题具有独特优势。

关键词：NP完全问题；势博弈；分布式势博弈算法；图形着色

DOIDOI：10.11907/rjdk.171696

中图分类号：TP319

文献标识码：A 文章编号：1672-7800（2017）012-0152-03

Abstract：Scheduling Problem has been proved to be an NP-complete problem， the difficulty of scheduling problem increases with increasing size of the curriculum. Through establishing graphics rendering model and applying to scheduling problem， a distributed potential algorithm is introduced. Distributed potential game algorithm starts to solve the problem from local optimum， which eventually forms the global optimum for the Scheduling Problem. At the same time the potential game algorithm is efficient in response to the course arrangement where there is a micro change in timetable. Practice shows that compared to genetic algorithms， simulated annealing algorithm， distributed game algorithm is unique and effective to solve the Scheduling Problem.

Key Words：scheduling problem； distributed； potential game； graphics rendering

0 引言

早在20世纪70年代，排课问题就被证明是NP完全问题[1]。排课问题的复杂度随问题规模的增大而剧烈增加。目前，对于NP完全问题求解主要是通过寻找一些降低计算复杂度的近似算法，没有通用算法，因而诸如动态规划[2]、遗传算法[3]、模拟退火算法[4]等用于近似求解NP完全问题的算法都可以用于解决排课问题。这类算法的共同特征是集中式处理，如果已排好的课表出现了某些变动而需要重排，则算法对这种动态变化响应并不及时。针对上述问题，建立排课问题的图论模型，提出使用多代理系统的分布式博弈算法[5]对课表进行编排。使用多代理系统的分布式博弈学习算法对课表进行编排的优点是：对于已经编排好的课表，如果某一部分课表发生变动，只需进行局部调整便可生成新的课表，效率得到极大提高。

1 问题描述

影响排课的因素是多方面的，主要是由教师、教室、课程、班级和时间组成的五元组，排课目标是实现这5个元素配置的最优化，使得教学资源得到合理分配及利用。这是一个多约束的组合优化问题，此类问题一般不存在唯一最优解，找到其中一种近似最优解即可。排课问题有两种类型约束。

1.1 基本约束条件

排课的实质是资源分配，解决排课问题的基本要求是基础教学资源分配在时间、空间上无冲突。将教学资源的

分配原则称为约束，对基础教学资源分配的原则称为基础约束。通常情况下，这些基础约束条件是固定的。例如：同一时间，同一教师不能讲授一门以上的课程；同一时间，同一班级不能开展一门以上的课程；同一时间，同一教室不能开展一门以上的课程等。

1.2 扩展约束条件

排课问题要求基本约束条件必须得到满足，但并非所有约束条件都需要得到满足，称此类约束为扩展约束。扩展约束一般用于保证课程质量，使得课程安排合理、科学。属于扩展约束的条件如下：某课程一周内有几次课应不在一天进行；英语、语文等记忆性课程应放在上午；同一教师的同一课程应尽量安排在同一地点等。

2 模型设计

2.1 基本假设

按照上述步骤，对于一个具有实际意义的真实课表安排问题，可以将课表排布问题转化为图的顶点着色问题，其中每周拥有的课时总数P作为颜色数，要求与同一个边相邻的顶点具有不同的颜色，对图的顶点进行着色，最后必然会得到一个结果，将不同班级课程按照颜色由小到大的顺序进行排序，便可以得到课程的最终排布。

2.3 排课模型完善

上述模型中，有许多实际约束条件没有考虑。对于一个实际排课问题，并非每一门课程都拥有同样的地位，某些课程比如英语，根据遗忘规律，需要将其放在上午，最理想的情况是放在上午第一节课，同时如果一门课在一天内进行两次，就可能导致学生一时接受不了大量知识，使得学习效率下降。解决第1个问题的方式是增加课程对偏好时间段的权重。还是以英语课程为例，这里设计一个权值W（W>1），在计算时将偏好时段乘以W，这就无形中增加了选取最适时段的概率。对于第2个问题，同课不适宜放在同一天进行，也同样可以通过设计权值W的方法解决，只不过权值小于1（w<1），这就减少了该值被选取的概率。endprint

高校课程表编排有别于中学课表，主要体现在高校教学活动中，为了节约资源，往往教室并不固定，同一门课程在一周内不同时刻上课，可能不在同一个教室。因此，在课程表安排好以后，还要为课程安排教室。但需要指出的是，在各班级课程表安排好以后，以各班级同一时间段课程为输入，以该时段可支配教室为输出，x为同一时段各班级的课程，y为该时段可支配教室，可以构成函数：

4 实验数据及结果分析

通过如下两点衡量排课算法优劣：①算法收敛速度，即算法能否快速解决课表排布问题。文中算法收敛速度和图的总冲突数成正比，冲突数为0时，算法收敛，算法收敛时间与循环次数成正比；②随着问题规模的增加，算法性能表现。对于NP完全问题，随着问题复杂度的增加，问题求解难度也相应增加，巧妙的算法在收敛性上要优于收敛性差的算法。测试结果（见表1）显示，随着问题规模的增加，冲突数增加，算法运算复杂度也相应提高。

5 结语

排課问题作为NP完全问题，其问题难度随课表规模的增大而提高。分布式势博弈算法从局部最优入手，最终形成全局最优，适用于排课问题求解；并且，势博弈算法对排课问题中课表微调问题的响应是高效的。本文通过对排课问题建立图形着色模型，采用分布式势博弈算法进行求解，对解决排课问题优势明显。

参考文献：

[1] EVEN S，ITAI A，SHAMIR A.On the complexity of time table andmulti-commodity flow problems[J].SIAM Journal on Computing，1976，5（4）：691-703.

[2] 程学先，祝苏薇.一种基于动态规划的课程调度算法的研究与实现[J].武汉理工大学学报：交通科学与工程版，2006，30（3）：485-488.

[3] 车明，秦存秀，刘凯.基于改进回溯算法的计算机排课系统[J].沈阳工业大学学报，2006，28（6）：667-670.

[4] 刘继清，陈传波.模拟退火算法在排课中的应用[J].武汉船舶技术学院学报，2003（3）：22-24.

[5] 杨光，蔚承建，王开，等.图形着色问题的分布式势博弈算法[J].计算机工程，2012（23）：181-184.

[6] 胡顺仁，邓毅，王铮.基于高校排课系统中的图论问题研究[J].计算机工程与应用，2002（4）：221-256.

（责任编辑：孙 娟）endprint