资源描述：
《多规格一维下料问题基于满意度模拟退火算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第49卷第6期大连理工大学学报Vol.49,No.62009年11月JournalofDalianUniversityofTechnologyNov.2009文章编号:100028608(2009)0620865207多规格一维下料问题基于满意度模拟退火算法1231,2郑晓军,杨光辉,滕弘飞(1.大连理工大学计算机科学与工程系,辽宁大连116024;2.大连理工大学机械工程学院,辽宁大连116024)摘要:为了对较大规模的一维下料问题更有效地进行计算,根据坯料的长度和数量将多规格一维下料问题分类为普通下料和批量下料,分别进行求解.对于普通下料问题,将满意度原理引入模拟退火算
2、法,给出了一种基于满意度的模拟退火算法(SDSA)进行求解;对于批量下料问题,由于各坯料的数量较多,采用该算法与序列启发方法相结合的混合算法(SHP&SDSA)进行求解,以进一步提高算法的搜索性能.对普通下料和批量下料的数值仿真结果表明,该算法可提高求解速度和质量,并可获得稳定的工程满意解.关键词:模拟退火;满意度;一维下料;批量下料中图分类号:TP391.72文献标志码:A0引言在经济组织的决策研究中提出的“令人满意准则”,[11]即用“令人满意解”代替传统意义的最优解.在工程实际中经常会遇到型材切割、木材加工本文根据坯料的数量和种类将下料问题分为等一维下料问题,即从某一
3、长度的原材料中,切割普通下料和批量下料两类.对于前者,给出一种基出各种不同种类长度的坯料,要求切割过程中最大于满意度的模拟退火算法(SDSA)进行求解;对限度地节约原材料,提高原材料的利用率.一维下于后者,由于每种坯料的数量很多,采用SDSA料问题与背包问题有相同的计算复杂度,同属NP2[12]与序列启发方法(SHP)相结合的混合算法hard问题,当问题规模较大时,很难求得全局最优(SHP&SDSA)进行求解.解,通常使用近似算法求解,使得能够在一个合理[1]1问题描述时间内得到所需要的工程满意解或优化解.目前下料问题的求解方法主要是各种近似算多规格一维下料问题描述如下:已
4、知M种规法和智能计算方法.近似算法主要有线性规划、动格原材料的长度分别为Lq(q=1,2,⋯,M),数量[2]态规划、NF(nextfit)、BF(bestfit)、序列启发不限,现有m种待切割的坯料,其长度和需求数[3、4]方法.但近似算法的求解结果与坯料的种类量分别为lj和nj(j=1,2,⋯,m).确定最优下料和数量有较大关系,在所需坯料的数量较大、种类方案,使所需要原材料浪费最少(原材料利用率最较多的情况下,很难得到理想的下料方案,因而很高),且末根原材料(即余料最长的一根原材料)多学者研究采用智能计算方法来求解此类问题.[13](以便下次下料时继续使用).其数的余
5、料最长[5、6]常用的智能计算方法有遗传算法、禁忌搜索学模型为[7][8][9]算法、进化策略、模拟退火算法等.智能算目标函数:法的优点是具有通用性、鲁棒性和全局收敛能力,N但也存在早熟、运行时间长、收敛速度慢等缺minF=∑ti-tmax(1)i=1[10]点.s.t.L(i)∈Lq满意度原理是1947年由诺贝尔奖获得者Simon(i=1,2,⋯,N;q=1,2,⋯,M)收稿日期:2007203213;修回日期:2009209217.基金项目:国家自然科学基金资助项目(50575031);“八六三”国家高技术研究发展计划资助项目(2006AA04Z109).作者简介:郑晓
6、军(19822),男,博士生;滕弘飞3(19362),男,教授,博士生导师,E2mail:tenghf@dlut.edu.cn.866大连理工大学学报第49卷m客户或专家对系统各项指标的综合评价.在优化ti=L(i)-∑ljaij≥0(i=1,2,⋯,N)j=1领域,将满意度原理与最优化理论相结合便产生N了满意优化,其核心思想是在最优化问题中,不刻nj=∑aij(j=1,2,⋯,m)i=1意强调获取最优解,而是根据具体情况寻求问题tmax=max{ti
7、i=1,2,⋯,N}[15]的满意解.所谓满意解是指在一定的满意标准其中N为原材料的使用数量,L(i)为下料结果中(水平)
8、下,如果一个解的满意度具有或超过满意第i根原材料的长度,aij为第i根原材料上第j件[16]水平,则称之为此满意水平下的满意解,在工坯料的数量,ti为第i根原材料的余料,tmax为所有程上则称之为工程满意解.目前满意优化已经用原材料上余料的最大值.于路径规划、生产调度等优化问题.本文引入满意式(1)综合考虑了所需原材料浪费最少和末度原理,确定了影响一维下料问题求解的两种满根原材料的余料最长.意水平(初始满意水平和用户满意水平),目的是定义1下料方式:在某一根原材料上的所提高该问题的求解效率.有坯料的组合称为该原材料
