基于启发式动态分解算法的矩形件优化排样  

Optimum packing of rectangles based on heuristic dynamic decomposition algorithm

作　　者：李波[1] 王石[2] 施松新[3] 胡俊勇[1] 

机构地区：[1]湖北文理学院机械与汽车工程学院,湖北襄阳441053 [2]东莞华中科技大学制造工程研究院信息技术部,广东东莞523808 [3]华中科技大学机械科学与工程学院,武汉430074

出　　处：《计算机应用》2013年第7期1908-1911,共4页journal of Computer Applications

基　　金：国家863计划项目(2011A0405);湖北文理学院博士科研基金资助项目

摘　　要：针对二维矩形件优化排样问题,提出了一种启发式动态分解算法,其可扩展用于三维及多容器全局排样求解。根据排放矩形件对容器进行正交动态分解,计算放置耦合度选择最佳子容器,通过干涉关系实现所有容器状态更新,实现大规模复杂排样问题的快速高效求解。对国际上公认Bench-mark多个问题例的计算结果表明,所提算法与同类算法相比优势明显,布局利用率提高达9.4%,计算效率提升达95.7%,并且已在商业化排样软件AutoCUT中应用,应用前景良好。To solve the optimum packing of two-dimensional rectangle layout problem, a heuristic dynamic decomposition algorithm was proposed, which can be used in the three-dimensional rectangule layout and global optimization problems. The container was orthogonally decomposed according to the emission rectangles, and the best sub-container was selected according to the degree of place coupling, then the state of all containers was updated by the interference relationship, so the large-scale and complex problem can be solved quickly and efficiently. The experimental results of the Bench-mark cases internationally recognized show that the proposed algorithm has better performance compared with similar algorithms, in which the layout utilization efficiency is increased by 9.4% and the calculating efficiency is improved up to 95.7%. Finally the algorithm has been applied to the commercialized packing software AutoCUT, and it has good application prospects.

关 键 词：矩形件排样 启发式 动态分解 优化 

分 类 号：TH301.06[机械工程—机械制造及自动化]