中文摘要：

为解决圆形片无约束剪冲排样问题,提出一个生成圆形片最优四块排样方式的确定性算法。四块排样方式首先用一条父分界线将板材分为两块,然后用两条与父分界线垂直的子分界线将两块分为四块;每个块里面只包含方向和长度均相同的圆形片条带。该算法首先求解一维背包问题生成块里面的条带最优布局;然后隐式枚举三条分界线位置得到所有可能的四块组合,选择排样价值最大的四块组合生成最优的四块排样方式。实验结果表明,该算法在计算时间和板材利用率两方面都有效。

英文摘要：

In order to solve the unconstrained circle cutting problem, it presents an optimal algorithm for generating fourblock cutting patterns of circle. It uses three cutting line to divide the sheet into four blocks, each of which contains circle strips of the same direction and length. The algorithm first solves one-dimensional knapsack problem to generates strip layout in this block, and finally four different block combinations obtained by implicit enumeration three cutting line position, choose the four composite which can make the sheet have a maximum value to generate the optimal four block layout. The experimental results show that, the algorithm is efficient in both the computation time and the material utilization rate.