序号

论文名称

作者和年份

主要思想

1

Simulated annealing and Boltzmann

machines.

Aarts, E. H. L., & Korst, J.

1989

The natural annealing process.

自然退火过程

2

Simulated annealing

Aarts, E. H. L., Korst, J., & Michiels, W.

E. K. Burke & G. Kendall (Eds.)

2005

The idea is to search a wider area of the search space at the beginning of the process by accepting worse moves with a higher probability. A temperature is used within a cooling schedule to control the probability of the acceptance of worse moves in the search. Many parameters need to be tuned in Simulated Annealing including the initial and final temperatures, and the cooling factor in the cooling schedule.

主要思想是通过以更高的概率接受不好的解扩大搜索的范围。冷却过程中温度将会被用来控制搜索过程中接受不好的解的概率。模拟算法中还会用到很多参数包括初始和最后温度，以及冷却过程中的冷却因素。

3

Variants of simulated annealing for the examination timetabling problem.

Thompson, J., & Dowsland, K. (1996).

They concluded that the most important factors in Simulated Annealing were the cooling schedule and the way neighbourhoods were defined and sampled.

他们认为模拟退火最重要的因素是冷却时间和对相邻的定义和取样方式。他们的考试排时间系统已经从1993年开始成功应用。

4

A robust simulated annealing based examination timetabling system.

Thompson, J., & Dowsland, K. (1998).

A two-stage approach where feasible solutions from the first stage are fed into a Simulated Annealing process in the second stage to improve soft constraint satisfaction.

这种模拟退火算法分两个阶段，第一阶段找到的合适的解代入第二阶段来改善软约束条件的满意度，由于第一阶段求得的解不是最佳的，两个阶段的过程中还用到了回溯算法

the Kempe chain neighbourhood

相邻的肯普链

5

An examination scheduling model to maximise

students study time.

Bullnheimer, B. (1998).

discussed how a model for Quadratic

Assignment Problems was adapted to formulate a small scale practical exam timetabling problem .The models enabled the university administrators to control how much the conflicting exams needed to be spaced out.

讨论一种采用二次分配问题表述小规模的实际考试排时间问题，这种模型可以使学校的教务员控制有多少时间上有冲突的考试需要错开来。

6

A hybrid algorithm for the examination timetabling problem.

Merlot, L. T. G., Boland, N., Hughes, B. D., & Stuckey, P. J. (2003).

a Simulated Annealing approach initialised by constraint programming techniques

and followed by hill climbing to further improve the solution.A modified Kempe chain neighbourhood was employed.

这种模拟退火算法通过初始化约束条件编程技术，接着用登山算法进一步求最优解，用到了一种修改过的肯普链相邻关系。作者认为这种混合算法的方法将会主宰将来的考试排时间问题的研究。

7

In

Proceedings of the 2nd international conference in computer sciences,

research, innovation & vision for the future

Duong, T. A., & Lam, K. H. (2004).

Duong and Lam (2004) employed Simulated Annealing

on the initial solutions generated by constraint programming

for the exam timetabling problem at HMCM University of

Technology. A Kempe Chain neighbourhood was employed

in the Simulated Annealing, whose cooling schedule was experimentally set using mechanisms and algorithms. The authors noted that when limited time is given, it is crucial to tune the components in Simulated Annealing to the specific

problems to be solved.

Duong and Lam 通过约束规划产生的初始解，把模拟退火应用到考试时间表问题。一个肯普链邻里（Kempe Chain neighbourhood），其冷却时间表用机制和算法通过实验给出，也应用到模拟退火之中。值得注意的是，当给出有限时间时，调整部分模拟退火的具体要解决的问题是非常关键的。

8

The state of the art of nurse rostering. Journal

of Scheduling

Burke, E. K., De Causmaecker, P., Vanden Berghe, G., & Van Landeghem,

H.

(2004b).

Burke et al. (2004a) studied a variant of Simulated Annealing,

called the Great Deluge algorithm (Dueck 1993). The search accepts worse moves as long as the decrease in the quality is below a certain level, which is originally set as the quality of the initial solution and gradually lowered by a decay factor. The decay factor and an estimate of desired quality represent the parameters in this approach. The authors noted that such parameters can be set by users, who are usually not experts on meta-heuristics. The initial solutions,

however, need to be feasible to calculate the decay factor so  a Saturation Degree was run a number of times, from which

the best solutions were employed as the starting points.

此研究主要用到了大洪水算法（Great Deluge algorithm），此研究接受一个更坏的结果，只要质量衰减小于一定的水平，这个水平是由初始结果产生的且会随着衰减因子减小。这种方法有两个参数：衰减因子(decay factor)和估计理想质量(estimate of desired quality)，且这两个参数可以由用户设定。初始结果需要足够灵活来计算衰减因子，这样就可以较快得出饱和度，然后把这个饱和度(Saturation Degree) 作为最好的初始解。在多伦多和诺丁汉数据方面的应用结果表明，大洪水方法更优于模拟退火。