一刀切问题的优化二叉树排样

《一刀切问题的优化二叉树排样》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、计算机集成制造系统ComputerIntegratedManufacturingSystems第17卷第2期2011年2月Vol.17No.2Feb.2011文章编号:1006-5911(2011)02-0329-09一刀切问题的优化二叉树排样戈鹏,邱厌庆,刘柱胜,任佩瑜(四川大学工商管理学院,四川成都610064)摘要:为了在提高板材利用率的同时提高全料的二次利用率,以二维一刀切下料问题为研究对象,根据现实约束提出了优化二叉树的启发式算法。该算法基于最小空穴插入最大零件、零件靠左靠下放置、整除求余确定零件转向

2、以及板材的整点切割等规则,给出兼容多板料的一刀切排样动态寻优算法流程;提出余料的动态拆分和合并思想,根据相邻关系将余料分为一类空穴和二类空穴两种类型,设计分裂、合并、Strip、Shake等算子,实现了一刀切下料的动态快速优化求解。基于本算法开发的系统在企业中的实际应用表明,所提算法能够在提高板材利用率的同时,有效避免余料的碎化,提高余料的二次利用率。关键词:一刀切;二叉树;矩形件排样;动态寻优;启发式算法中图分类号:TP391.72文献标志码:AOptimizedbinarytreepackingofguil

3、lotineproblemGEPeng,QIUYan2qing,LIUZhu2sheng,RENPei2yu(SchoolofBusinessAdministration,SichuanUniversity,Chengdu610064,China)Abstract:Toimprovetheuserateofplates,meanwhileimprovethereuserateofremainders,two2dimensionalguil2lotinecuttingstockproblemwasstudied.

4、Anoptimizedbinarytreeheuristicalgorithmbasedonrealisticconstraintswasproposed.Basedonrulessuchaslargestpartsintothesmallesthole,partsplacedonthelowerleft,determinethedirectionofpartsbymodulusoperation,andcuttingplateonintegercoordinate,thedynamicoptimization

5、algo2rithmprocesswhichwascompatibleformulti2sheetwaspresented.Togetafastsolutionbydynamicoptimizationforguillotineproblem,anideaofremaindersπdynamicsplitandmergewasputforward,aswellasaseriesofopera2torslikeDivision,Merging,Strip,Shake,etc.Theremaindersweredi

6、videdintotwotypesofcavitiesIandIIac2cordingtoneighborhoodrelationshipbetweenthem.Thepracticalapplicationofthecomputationalsystemintheen2terprisewhichwasdevelopedbasedonthisalgorithmshowedthatthealgorithmcouldnotonlyimprovetheutiliza2tionofblanksbutalsocontri

7、butetotheimprovementofthereuserateofremaindersbypreventingthefragmentationofremainders.Keywords:guillotine;binarytree;rectangularpacking;dynamicoptimization;heuristicalgorithms生产中,材料的利用率即使提高1%,所创造的经济效益也相当可观。据调查,采用计算机优化下料后,制造企业材料利用率可平均提高5%～10%。111矩形件排样理论基础下料问

8、题又称为排样问题或者切割问题,最早由苏联人Knaortovihc[1]于1939年提出。许多工业问题的提出在当今激烈的市场竞争中,降低生产成本、提高生产效率和增强对市场的应变能力,是企业保持竞争力的主要实现手段。材料费用是制造企业主要的生产成本,一般占总成本的60%～80%,在大批量1收稿日期:2010201220;修订日期:2010205218。Received20Jan.2010;