改进的模拟退火算法在板式家具工业优化下料问题中-计算机应用研究.pdf

2·26 · 计算机应用研究 2005 年 改进的模拟退火算法在板式家具工业 优化下料问题中的应用 * 岳 琪, 曹 军 ( 东北林业大学, 黑龙江 哈尔滨 150040) 摘 要: 讨论了如何利用改进的模拟退火算法即单调升温的模拟退火算法求解板式家具生产中的优化下料问 题。在对问题进行数学描述的基础上, 给出了算法求解的关键步骤和方法; 讨论了单调升温模拟退火算法中如 何跳出局部最优解, 以及升温幅值的确定方法。实例表明该算法优化速度快, 效率高, 能有效解决大规模矩形件 优化下料问题。 关键词: 板式家具; 下料问题 ; 单调升温的模拟退火算法; 全局优化 中图法分类号: TP301. 6 文献标识码: A 文章编号 : 1001- 3695( 2005) 10- 0226- 03 Application of Improved Simulated Annealing Algorithm in Large-scale Rectangular Packing Problem in Furniture Industry YUE Qi, CAO Jun ( Northeast Forestry University, Harbin Heilongjiang 150040, China) Abstract: In this paper the packing problem in furniture manufacture industry is solved by applying the rising temperature controlled simulated annealing algorithm. The important steps and method of the algorithm are given. And how to distinguish the local optimization in the rising temperature controlled simulated annealing algorithm is discussed. The method of rising the temperature value is given. An experiment example showed that this algorithm could get the optimal result quickly and effi- ciently. It is an effective way to solve the large-scale rectangular packing problem. Key words: Board Furniture; Packing Problem; Rising Temperature Controlled Simulated Annealing; Global Optimization 的数, 由客户对板式家具的产品订单数量决定。零件在板材上 1 板式家具下料问题及其数学描述 既可被横放也可被竖放。板材在纵向方向每一行只能排放一 种零件, 假设