矩形件无约束二维板材剪切的4块排样算法

针对矩形件无约束二维板材剪切排样问题,提出一种新的4块排样方式及其生成算法.该排样方式将板材划分成4个块,对每个块,按照递归方式进行排样.选择一行同种矩形件放置在块的左下角,沿着这行矩形件的上边界和右边界将该块剩余部分划分成两个更小的子块以待进一步递归考察.首先,构造动态规划算法一次性生成所有可能尺寸的块中矩形件的递归排样方式;然后,采用隐式枚举算法确定板材的最优4块划分,得到矩形件在板材上的最优4块排样方式.采用文献基准例题和符合实际情况的随机例题,将所提出算法与几种典型的文献算法进行对比,实验结果表明所提出算法时间复杂度在低于或等于文献算法的前提下,排样方式价值比文献算法高.

A four-block layout algorithm for unconstrained two dimensional plate guillotine cutting problem of rectangular items

A four-block layout and its generation algorithm are proposed for the unconstrained two-dimensional plate guillotine cutting problem of rectangular items, in which the plate is divided into four blocks, and each block is arranged recursively. A row of the same kind of rectangular items is selected and placed in the left lower corner of the block. Along the upper and right boundaries of this row of rectangular items, the rest of the block is divided into two smaller sub blocks for further recursive investigation. Firstly, the recursive layout of rectangular items in all possible size blocks is generated using the dynamic programming algorithm at one time. Then the optimal four-block layout of rectangular items on the plate is determined using the implicit enumeration algorithm. The algorithm is compared with several typical literature algorithms using literature benchmark examples and random examples in accordance with the actual situation. The experimental results show that the time complexity of this algorithm is lower than or equal to the literature algorithm, and the value of layout is higher than that of the literature algorithm.