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

Optimized binary tree packing of guillotine problem

作　　者：戈鹏[1] 邱厌庆[1] 刘柱胜[1] 任佩瑜[1] 

机构地区：[1]四川大学工商管理学院,四川成都610064

出　　处：《计算机集成制造系统》2011年第2期329-337,共9页Computer Integrated Manufacturing Systems

基　　金：国家863计划资助项目(2008AA04A07)~~

摘　　要：为了在提高板材利用率的同时提高全料的二次利用率,以二维一刀切下料问题为研究对象,根据现实约束提出了优化二叉树的启发式算法。该算法基于最小空穴插入最大零件、零件靠左靠下放置、整除求余确定零件转向以及板材的整点切割等规则,给出兼容多板料的一刀切排样动态寻优算法流程;提出余料的动态拆分和合并思想,根据相邻关系将余料分为一类空穴和二类空穴两种类型,设计分裂、合并、Strip、Shake等算子,实现了一刀切下料的动态快速优化求解。基于本算法开发的系统在企业中的实际应用表明,所提算法能够在提高板材利用率的同时,有效避免余料的碎化,提高余料的二次利用率。To improve the use rate of plates,meanwhile improve the reuse rate of remainders,two-dimensional guillotine cutting stock problem was studied.An optimized binary tree heuristic algorithm based on realistic constraints was proposed.Based on rules such as largest parts into the smallest hole,parts placed on the lower left,determine the direction of parts by modulus operation,and cutting plate on integer coordinate,the dynamic optimization algorithm process which was compatible for multi-sheet was presented.To get a fast solution by dynamic optimization for guillotine problem,an idea of remainders＇ dynamic split and merge was put forward,as well as a series of operators like Division,Merging,Strip,Shake,etc.The remainders were divided into two types of cavities I and II according to neighborhood relationship between them.The practical application of the computational system in the enterprise which was developed based on this algorithm showed that the algorithm could not only improve the utilization of blanks but also contribute to the improvement of the reuse rate of remainders by preventing the fragmentation of remainders.

关 键 词：一刀切 二叉树 矩形件排样 动态寻优 启发式算法 

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