Abstract: The machine layout problem is an NP-complete problem, it is very difficult, even impossible to find the optimum solution in a reasonable amount of time, so it can only be solved by use of the heuristic algorithms. The efficiency of the traditional simulated annealing algorithm is low and its solution is not good because of its repeated searching during the process of searching the new solution. The traditional simulated annealing algorithm is improved through adding memory function in the searching process. The improved simulated annealing algorithm can effectively avoid repeated searching, so the solution is better and the efficiency is higher, which is proved true through an example.

Key words: Machine layout, Simulated annealing algorithm, Improved simulated annealing algorithm

摘要： 由于设备布局问题是NP完全问题，它在有限合理的时间内难以求得最优解，因此问题的求解只能依赖于各种启发式方法。文章针对传统的模拟退火算法经常出现迂回搜索，导致搜索效率低，解的质量差这一现象，通过在传统模拟退火算法搜索过程中增加记忆功能，来避免迂回搜索，将改进的模拟退火算法应用于设备布局的研究中，通过实例证明改进的模拟退火算法解的质量有了很大提高。

关键词: 设备布局, 模拟退火算法, 改进型模拟退火算法