约束二维排样问题的一种求解算法

讨论有约束二维切割排样问题,即将板材切割成若干种矩形毛坯,其中每种毛坯的数量有上界约束,优化目标以使板材所切割的毛坯总价值(排样价值)最大。采用五块排样方式简化切割工艺,将板材切割成五块,每块切割成所需毛坯。构造一种基于隐式枚举和分支定界思想的算法生成五块排样方式:(1)计算所有可能尺寸的块的排样价值;(2)选择排样价值最大的五块组合生成五块排样方式;(3)采用文献中的基准测题,验证文中的有约束五块排样算法。研究结果表明,文中算法平均排样价值比文献中的3种算法分别高出12.85%,4.52%和1.89%,且算法计算时间较短。

An algorithm of the constrained two-dimensional nesting

The constrained two-dimensional nesting problem was discussed, and the total value of the blank was in the maximum when one blank was cut to meet upper bound and optimization objective. The cutting process was simplified by five-block pattern. The blank was cut into five-blocks, and then each block was cut into the required blanks. An algorithm based on implicit enumeration and branch bound al-gorithm was constructed to generate five-block pattern. Firstly, the nesting values of all possible size blocks were calculated, and then the five-block combination which had the maximal value was chosen to generate five-block pattern. Finally, the five-block pattern algorithm with constrain was tested by the benchmark problems of the literature. The research results show that the average value of the proposed al-gorithm is higher than those of the literature about 12. 85%, 4. 52%, 1. 89% respectively, and the computation time is shorter.