基于五块模式的单一矩形件排样算法  

Algorithm for Generating Five Block Mode Cutting Patterns of Single Rectangular Items

作　　者：易向阳[1] 潘卫平[1] 张俊晖[2] 

机构地区：[1]广西大学计算机与电子信息学院 [2]四川信息职业技术学院

出　　处：《图学学报》2015年第4期521-525,共5页Journal of Graphics

基　　金：国家自然科学基金资助项目(61363026;71371058);广西高等教育教学改革工程重点资助项目(2013JGZ110)

摘　　要：如何在一个大矩形里排入尽可能多的单一规格小矩形件是广泛出现在制造业领域的板材分割、物流业领域的集装箱装载中的问题。采用五块模式将大矩形划分为五个块,求解每个块里面矩形件的排样方式。首先,采用动态规划算法一次性生成所有块中矩形件排样方式,然后,采用隐式枚举法考虑所有可能的五块组合,选择包含矩形件个数最多的五块组合作为最终的排样方案。使用算例对算法进行了测试,并与另外4种单一排样算法进行了比较。实验结果表明,该算法在排样利用率和切割工艺两方面都有效,而且计算时间合理。It is widely appears in manufacturing fieldfield of pallet loading that how to finding a maximalof plate segmentation and the logistics industrylayout for identical small rectangles on a largerrectangle. The large rectangle is divided into five blocks using five-block mode, then the problem issolved to arrange the identical small rectangular into each blocks. Firstly, the dynamic programmingmethod is used to generate the entire layout of rectangular in blocks in once. Then, the enumerationmethod is used to consider all of five blocks combination. The combination is selected to generate thefinal pattern which have the maximal number of rectangular. Several examples are used to test theproposed algorithm, and comparing the algorithm with other 4 kinds of single layout algorithm. Theexperimental results show that the algorithm is efficient in both the layout utilization rate and thecutting process with a reasonable computing time.

关 键 词：矩形排样问题 动态规划算法 隐枚举 五块模式 

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