摘要： 实验预约系统的核心任务是生成实验教学课表，课表的生成是一个典型的组合优化问题，模拟退火算法是解决此类问题的优秀算法之一。本文主要研究了模拟退火算法的原理与特性，并将其应用于实验教学预约系统的排课模块中，更好地提高排课效率，改善排课效果。
Abstract： The core task of the experimental reservation system is creating schedule， which a typical combinatorial optimization problem， simulated annealing algorithm is one of the best algorithm to solve the problem. This paper mainly studied the principle and characteristics of the simulated annealing algorithm， and then used it to course scheduling. It can improve the efficiency of scheduling.
关键词： 实验预约；模拟退火算法；排课
Key words： experimental reservation；simulated annealing algorithm；course scheduling
中图分类号：TP18 文献标识码：A 文章编号：1006-4311（2014）32-0253-03
0 引言
排课问题是一个典型的多参数的组合优化问题[1]。目前，排课算法有很多，其中模拟退火算法是一个研究热点。该算法简单、灵活，适应性强。本文对其进行了分析研究，并将其应用于实验预约系统的排课逻辑中。
1 算法介绍
1.1 基本原理 模拟退火算法（Simulated Annealing Algorithm，SA）源于冶金技术中的固体退火原理。固体被加热的过程温度不断升高，内能增大，固体内的粒子变得无序；而温度下降时内能减小，固体内部粒子逐渐趋于有序，到常温时达到最平衡态的基态[2]。1.3 应用分析 “实验预约系统”的核心业务逻辑是利用排课算法给出合理的课表，此类问题已被定义为NP完全问题[6]，由于无法获取足够的约束条件，因此也无法搜索到全局最优解[7]。而模拟退火算法对于排课问题有着很好的解决方案，可以在可接受的时间内得到近似最优解。
1.3.1 应用系统的功能
实验室预约系统功能模块如图1所示。
1.3.2 问题分析
实际的排课过程涉及的因素非常多，包括学生、教师、实验室、课程等等。学生信息是系统处理的基本信息之一，把一次实验课的上课单位看作一个学生集，这个集合受实际情况的多条件约束而产生。例如，在某个学生集中，可能包含来自不同班级，甚至不同专业的学生，他们的现有课表是系统的重要约束条件，并且由于班级不同、专业不同，导致这一约束条件变得错综复杂。
对于教师来说，其某些属性也是系统的约束条件，例如，教师现有课表，对于教师课表来说不仅要考虑其时间安排不能冲突，还要考虑实验内容与理论内容的逻辑关系，以符合学生的学习规律。除此之外，还要考虑教师的一些特别要求，例如，不要安排晚上上课、不要安排在第1节课、要连续为两个学生集上课等等。
实验室是系统可利用的目标资源，其属性包括实验容量、实验类型等。实验容量是一次实验最多可容纳的最大学生数量，实验类型是实验室可进行的实验内容的分类。
由以上分析可知，排课实际上就是根据以上所述因素产生的一组约束条件，将学生集安排到合适的实验室的过程。在约束条件中，有的是“必须”满足的，例如，同一个学生集不能同时在两个实验室上课。有的则是“尽可能”满足的，例如，教师要求每周的实验课程尽量早安排等。因此，为把约束条件分为两类，分别赋予两类权重值。对于“必须”的约束条件，将其权重值设置为1；对于“尽可能”的约束条件，按照实际情况其权重值从（0，1）的开区间中选择，若找不出最优课表，则可以逐步调整这类约束条件的权重值，以便得到优质解。同时满足这两类约束条件，是排课系统的设计目标。
1.3.3 排课模型
实际应用中分别采用了标准邻域和Kempe链邻域两种邻域方式，它们的最小代价函数比较结果如图3所示。
3 结论与展望
分析了排课问题的组成要素、约束条件和系统目标，建立了排课问题模型，利用模拟退火算法搜索最优解。通过多次实验和数据分析，证明了系统有较好的实用价值。模拟退火算法的各类参数错综复杂，对算法性能的影响很大，因此参数的组合优化问题值得进一步研究和探索。
参考文献：
[1]杨小兵.基于遗传算法的学分制下多校区排课系统的研究与实现[D].昆明理工大学，2010.
[2]康立山.非数值并行算法.第一册：模拟退火算法[M].北京：科学出版社，1994.
[3]S. Kirkpatrik. & C. D. Gelatt. & M. P. Vecchi. Optimization by Simulated Annealing[J]. Science， 1983， vol.220： 671-680.
[4]姚明海，王娜.基于改进模拟退火算法求解TSP问题[J].渤海大学学报（自然科学版），2013，34（1）.
[5]庞峰.模拟退火算法的原理及算法在优化问题上的应用
[D].吉林大学，2007.
[6]朱洁.基于J2EE的山西医科大学高校排课系统研究与设计[D].电子科技大学，2012.
[7]王庆荣，袁占亭，张秋余.基于改进遗传—模拟退火算法的公交排班优化研究[J].计算机应用研究，2012，29（7）.