多规格一维下料问题基于满意度模拟退火算法  

Simulated annealing algorithm based on satisfaction degree for one-dimensional cutting-stock problems with multiple stock lengths

作　　者：郑晓军[1] 杨光辉[2] 滕弘飞[1,2] 

机构地区：[1]大连理工大学计算机科学与工程系,辽宁大连116024 [2]大连理工大学机械工程学院,辽宁大连116024

出　　处：《大连理工大学学报》2009年第6期865-871,共7页Journal of Dalian University of Technology

基　　金：国家自然科学基金资助项目(50575031);"八六三"国家高技术研究发展计划资助项目(2006AA04Z109)

摘　　要：为了对较大规模的一维下料问题更有效地进行计算,根据坯料的长度和数量将多规格一维下料问题分类为普通下料和批量下料,分别进行求解.对于普通下料问题,将满意度原理引入模拟退火算法,给出了一种基于满意度的模拟退火算法(SDSA)进行求解;对于批量下料问题,由于各坯料的数量较多,采用该算法与序列启发方法相结合的混合算法(SHP&SDSA)进行求解,以进一步提高算法的搜索性能.对普通下料和批量下料的数值仿真结果表明,该算法可提高求解速度和质量,并可获得稳定的工程满意解.In order to solve the large scale one-dimensional cutting stock problems（1D-CSP） more efficiently, the 1D-CSP with multiple stock lengths is firstly classified into general 1D-CSP and batch 1D-CSP according to the length and number of the billets. For general 1D-CSP, a simulated annealing algorithm based on satisfaction degree （SDSA） is presented, which is inspired by the satisfaction degree theory. For batch 1D-CSP, since the number of billets is large, it will be solved by SDSA combined with sequential heuristic procedure, which is called SHP＆ SDSA for short. The proposed SHP＆SDSA will further improve the search ability of SDSA for batch 1D-CSP. The numerical experimental results show that the proposed approaches achieve the better quality and the higher efficiency, and obtain the stable satisfactory project solution.

关 键 词：模拟退火 满意度 一维下料 批量下料 

分 类 号：TP391.72[自动化与计算机技术—计算机应用技术]