Abstract: A recursive multi-block pattern and its dynamic programming generation algorithm were proposed for two-dimensional plate cutting of rectangular pieces.With this pattern,the plate was divided into multiple blocks,then each block was recursively divided into multiple blocks until an optimal rectangular piece was arranged in each newly generated block.To balance the calculation complexity of layout method and the pattern value of the plate,for the guillotine cutting problem,the number of blocks for multi-block division was set as two,for the non-guillotine cutting problem,the number of blocks for multi-block division was set as five.The dynamic programming algorithm first calculated the maximum value of the first level multi-block pattern obtained when each of the five blocks discharged a rectangular piece,then calculated the value of the second level multi-block pattern obtained when each of the five blocks discharged a first level multi-block pattern,and then recursively obtained the maximum value of the multi-block pattern of any number of level.By comparing the upper and lower bounds of the block pattern value,unnecessary multi-block division was eliminated.The computation time of the algorithm was controlled by discretizing the location of the dividing line.Using typical instances in the literature and actual production instance,the proposed algorithm was compared with the guillotine cutting algorithm and non-guillotine cutting algorithm.The results showed that the algorithm had higher pattern value and the calculation time could meet the needs of practical application.

Key words: two-dimensional plate cutting, recursive multi-block pattern, dynamic programming, pattern value, rectangular pieces

摘要： 针对矩形件二维板材排样问题,提出递归多块排样方式及其动态规划生成算法。递归多块排样方式将板材划分成多个块,然后递归地对每个块进行多块划分,直到每个新产生的块中排放一种最优矩形件为止。为了均衡考虑排样方式的计算复杂度和板材排样价值,对于一刀切排样问题将多块划分的块数定为两块,对于非一刀切排样问题将多块划分的块数定为5块。动态规划算法首先计算每个块中分别排放一种矩形件所得到的1阶多块排样方式的最大价值,然后计算每个块中分别排放一个1阶多块排样方式得到的2阶多块排样方式的最大价值,以此递推,得到任意阶数的多块排样方式的最大价值。通过比较块的排样价值的上界和下界来剔除不必要的多块划分,通过离散化划分线位置来控制算法的时间复杂度。采用文献典型例题和实际生产实例,将所提算法与一刀切排样算法和非一刀切排样算法进行对比,表明了所提算法的优越性。

关键词: 二维板材排样, 递归多块排样方式, 动态规划, 排样价值, 矩形件