基于局部状态计算的模拟退火算法求解排课问题

马超

摘要：编排课程表是教学工作开展的基础，因此排课问题的解决有着重大的现实意义。作为典型的组合优化问题，随着课程规模的增加以及约束条件的多样化、复杂化，人工求解排课问题显得不现实。在分析排课问题需要满足的约束条件上建立课程表模型，使用基于局部状态计算的模拟退火算法来减小计算范围对模型求解。（近似）最优的求解结果证明了模型的有效性和求解方法的可行性。

关键词：排课系统 模拟退火 局部状态计算

中图分类号：TP311.52 文献标识码：A 文章编号：1007-9416（2016）08-0149-02

1 引言

排课工作是教学管理的一项重要内容，其实质是为每个班级安排合理的课程、时间、教室和教师，制定课程表以保证教学工作能按时有序进行。课程表编排的合理化和人性化直接影响着后续教学工作的效率。S.Even于1975年证明了排课问题在本质上属于NP完全问题[1]。随着班级、课程量的增加以及约束条件的复杂化，传统的人工排课方法耗时耗力，甚至难以排出合理的课程表。不少文献对遗传算法解决排课问题进行了研究[2][3][4]，遗传算法在求解该问题时搜索效率较低，容易陷入局部极值。事实上，遗传算法更适用于无约束的优化问题求解。由于遗传算法的解和软色体基因编码间有着对应规则，因此适应度较高的两个个体经杂交后可能产生较差的子代，甚至子代会成为非法软色体（不满足基因编码规则）。文献[5]使用蚁群算法对排课问题进行了研究，蚁群算法的缺点是计算耗时较长，蚂蚁运动的随机性致使收敛速度较慢， 算法容易停滞不前。鉴于以上，本文使用基于局部状态计算的模拟退火算法对排课问题进行求解。

2 问题描述和建立模型

2.1 问题描述

作为典型的组合优化问题，排课问题涉及班级、课程、教师、时间和教室五个因素，其实质是给定资源在一系列约束条件下的分配，因此排课问题属于约束满足问题[6]。一方面，课程表必须满足硬约束以保证不发生时空冲突，另一方面，课程表要尽量满足软约束去考虑某些课程或者教师的特殊要求。教学的最小单位定义为基本时间段BTD（Basic Time Duration），一个BTD可以认为是一节课或者一个课时。

课程表必须满足硬约束，从教学资源分配的观点看，硬约束有下面三点：

（1）班级约束：一个班级在一个课时内只能上一门课。

（2）教师约束：一个教师在一个课时内只能上一门课。

（3）教室约束：一个教室在一个课时内只能上一门课。

软约束随具体情况而变，综合看来有下面几点：

（1）教师A的课程只能安排在上午。

（2）教师B的课程需要有连课（比如1、2节都为英语课）。

（3）教师C的课只能安排在周一和周三。

（4）某些课只能安排在特定教室（实验课等）。

（5）考虑到备课负担和教学效果，课程编排要尽量均匀。

2.2 模型建立

如前所述，排课问题中所涉及的因素有班级、课程、教师、教室、时间。我们对教学资源的假定如下：有m间教室，每周上n天课，每天有p个课时，（比如上午四节，下午三节，那么一天的课时数为7），则每周共有m*n*p个时空单元（课时单元）。我们把所有的时空单元划分为一个行数为m、列数为p*n的二维数组TimeTable[m][p*n]。如果有8间教室，每周上课5天（星期一至星期五），每天7节课，那么该二维数组就为TimeTable[7×5]。二维数组的每个元素TimeTable[i][j]（0≤i≥7，0≤j≥34）与哪一天（date）、哪一节（order）的对应关系为：

date=j/7（取整）

order=j%7（取余）。

3 基于局部状态计算的模拟退火排课算法

模拟退火算法[4]（Simulated annealing，SA）的基本原理是模拟固体在退火过程中总是从能量高的状态向能量最低的平衡态转换的思想寻找最优解，通过冷却温度的不断降低来控制退火过程。SA在每个温度下设计解的随机变化，并以一定的概率接受差的解。随着能量的降低，接受差的解的概率也显著降低。因此，SA在高能状态下具有逃离局部最优解的能力，在低能状态下可以收敛得到全局最优解。

模拟退火算法的关键是要找到一个目标函数，排课问题中的各种约束是建立目标函数的依据，这些约束分为硬约束和软约束。我们对不同的约束赋予不同的影响因子（权重），硬约束决定了排课方案是否可行，软约束决定排课方案是否够好。

3.1 算法流程

为了算法流程的描述简洁，T0表示退火的初始温度，Tmin表示退火的结束温度，降温方式使用指数衰减。INNER_TIMES为每个温度下的课程表随机变化次数。算法流程如图1所示。

3.2 模型求解的算法关键

3.2.1 新课程表的随机产生

Step1：随机产生一个数i（i∈[0， m-1]），选出教室TimeTable[i]。

Step2：随机产生两个数j，k（j，k∈[0， n*p-1]），选出step1中教室的两个课时TimeTable[i][j]和TimeTable[i][k]，确保TimeTable[i][j]≠TimeTable[i][j]，即两个课时所代表的课程不同。

Step3：对step2中两个课时的课程进行交换，产生新的课程表。新课程表是否被接受取决于其和当前课程表的目标函数差及概率。

3.2.2 目标函数设计

（1）基于局部状态计算的目标函数。新课程表相比当前课程表只有一个教室的两个课时顺序发生了变化，参与变化的课程只有两门课。在计算课程表的目标函数值时，不变的那些课时无需参与计算，因为这部分是一个定值，我们只需要计算发生变化的部分，然后得到目标函数差即可。假设课程表不变部分的目标函数是value_constant，当前课程表由课程TimeTable[i][j]和TimeTable[i][k]决定的目标函数值部分是value_variation1，新课程表由课程TimeTable[i][j]和TimeTable[i][k]决定的目标函数值部分是vale_variation2， 目标函数差值是value_diff.value_variation1和value_variation2都取决于TimeTable[i][j]和TimeTable[i][k]，确切地说是取决于课时TimeTable[i][j]和TimeTable[i][k]对应课程上面的约束（硬约束和软约束）。基于局部计算的原理公式如下：

value_diff=（value_constant + value_variation2）

-（value_constant+value_variation1）

=value_variation2-value_variation1

这样目标函数在计算时不用考虑整张课程表，只需考虑发生交换的两个课时，计算范围得以大大缩小。

（2）约束的完备性：目标函数要计算到排课要求的所有约束。

（3）约束的影响因子：硬约束的影响因子要高于软约束；软约束的影响因子确定原则，越重要的软约束（根据排课面临的现实情况权衡），其影响因子越高（不应高过硬约束），确保算法优先满足。

3.2.3 SA参数设置

T0=1000，Tmin=0.001，退火速率设置为0.98，INNER_TIME = 1000。

4 结果与结论

本文用C语言实现了对某年级课程表的建模和算法求解，基于局部状态计算的模拟退火算法大大减少了计算量，求解出的课程表如图2所示，经验证完全满足约束条件。由于每个学校的开课情况和约束条件存在差别，所以设计出通用的排课程序不是很实际，但本文对排课问题的建模方法和基于局部状态计算的模拟退火算法求解有着一定的启发和借鉴意义。

参考文献

[1]Garey M R， Johnson D S. Compute and Intractability： A Guide to the theory of NP completeness [M]. San Francisco： W H， Freeman &Co Ltd. ，1979.

[2]崔玉连，杨先锋.改进遗传算法在排课问题中的应用研究[J].微型电脑应用，2013，29（10）：48-51.

[3]王园园.遗传算法在高校排课系统中的应用[J].淮北职业技术学院学报，2015，14（3）：134-135.

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

[5]张 林.基于蚁群算法的排课系统研究与设计[D].合肥： 安徽大学硕士学位论文， 2005.

[6]Bartak R， Salido MA， Rossi F. Constraint satisfaction techniques in planning and scheduling [J]. Journal of Intelligent Manufacturing， 2010，21： 5-15.