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

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

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

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

3、ackingofguillotineproblemGEPeng,QIUYan2qing,LIUZhu2sheng,RENPei2yu(SchoolofBusinessAdministration,SichuanUniversity,Chengdu610064,China)Abstract:Toimprovetheuserateofplates,meanwhileimprovethereuserateofremainders,two2dimensionalguil2lotinecuttingstock

4、problemwasstudied.Anoptimizedbinarytreeheuristicalgorithmbasedonrealisticconstraintswasproposed.Basedonrulessuchaslargestpartsintothesmallesthole,partsplacedonthelowerleft,determinethedirectionofpartsbymodulusoperation,andcuttingplateonintegercoordinat

5、e,thedynamicoptimizationalgo2rithmprocesswhichwascompatibleformulti2sheetwaspresented.Togetafastsolutionbydynamicoptimizationforguillotineproblem,anideaofremaindersπdynamicsplitandmergewasputforward,aswellasaseriesofopera2torslikeDivision,Merging,Strip

6、,Shake,etc.TheremaindersweredividedintotwotypesofcavitiesIandIIac2cordingtoneighborhoodrelationshipbetweenthem.Thepracticalapplicationofthecomputationalsystemintheen2terprisewhichwasdevelopedbasedonthisalgorithmshowedthatthealgorithmcouldnotonlyimprove

7、theutiliza2tionofblanksbutalsocontributetotheimprovementofthereuserateofremaindersbypreventingthefragmentationofremainders.Keywords:guillotine;binarytree;rectangularpacking;dynamicoptimization;heuristicalgorithms生产中,材料的利用率即使提高1%,所创造的经济1问题的提出效益也相当可观。据调查

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