复合匀质块排样方式及其生成算法

Algorithm for generating patterns of complex uniform blocks

为解决大规模矩形件无约束二维剪切排样问题,提出一种复合匀质块排样方式及其生成算法。用一条水平分界线将板材划分为上下两段,每段包括若干个由左到右水平排列的匀质块。采用文献算法生成匀质块,采用动态规划算法将匀质块组合成段,通过枚举法确定最优水平分界线的位置。采用3组基准例题对算法进行测试,实验结果表明,该算法能够有效提高材料利用率。

With the purpose of solving the large scale unconstrained two-dimensional guillotine-cutting problem of rectangular items,an algorithm for generating the patterns of complex uniform blocks was proposed.The plate was divided into up and down two segments with a single horizontal line,each of which contained several uniform blocks arranged from left to right horizontally.The homogeneous block was generated using a literature algorithm.A dynamic programming algorithm was introduced to combine the homogeneous blocks into segments.The optimal position of the horizontal line was determined using the enumeration method.The algorithm was tested through three group benchmark problems.The computational results indicate that the algorithm is highly efficient on improving material usage.