约束剪切问题的三块排样方式及其生成算法

Three-block layout pattern and its generation algorithm of constrained cutting problem

讨论了矩形件有约束剪切排样问题,即在一张板材上剪切下若干种已知尺寸和价值的矩形件,约束每种矩形件允许剪切的数量不能超过其需求量,优化目标为使板材剪切出的矩形件总价值最大。提出了一种三块排样方式及其生成算法。这种算法用两条互相垂直的剪切线将板材分成3个块;对于每个块,排放一个矩形件在其左下角,将其剩余部分划分为2个子块;将子块看作块继续递归排样,直到其无法再容纳矩形件为止。采用基准例题将本文算法与文献算法进行实验对比,结果表明本文算法排样价值比4种文献算法分别高0.35%,0.31%,0.19%和0.37%,且计算时间可满足实际应用需要。

The constrained guillotine cutting problem of rectangular part was discussed,namely,a number of rectangular parts known size and value were cut down from a sheet,and each rectangular part was contained to allow the number of cutting parts not to exceed its demand. Therefore,the optimization objective was to maximize the total value of the parts cut from the sheet,and a three-block layout pattern and its generation algorithm were proposed. This algorithm divided the sheet into three blocks with two mutually perpendicular shear lines,and a rectangular part was placed in the lower left corner for each block. Then,the remainder was divided into two sub-blocks,and the sub-block was regarded as a block to recursive layout until no rectangular part was accommodated. The experimental comparison between the proposed algorithm and the literature algorithm was conducted by the benchmark examples. The results show that the proposed algorithm is 0. 35%,0. 31%,0. 19% and 0. 37% higher than four kinds of literature algorithms respectively,and the calculation time can meet the needs of practical application.