基于两段方式的圆形片约束排样算法

讨论圆形片约束排样问题,提出一种两段排样方式生成算法。两段排样方式用一条分界线将板材划分为两个段,每个段由相同长度和方向的条料组成,每根条料排放同种圆形片。首先确定所有可能尺寸的条料中圆形片的排样方式;然后采用背包算法,生成所有可能尺寸的段中条料的排样方式;最后依据板材排样价值最大原则,确定段的分界线位置,得到整张板材上圆形片的两段排样方式。将本文算法和文献算法进行比较,数值实验结果表明,本文算法排样价值高于文献算法。

A constrained nesting algorithm of circular pieces based on two-segment patterns

The circular pieces constrained nesting problem was discussed, and an algorithm generated by two-segment nesting patterns was proposed.The plate was divided into two segments using a line of demarcation by the two-segment patterns.Each segment consisted of strips with the same length and direction, and each strip consisted of identical circular pieces.Firstly, the nesting patterns of circular pieces on strip of all possible sizes were determined, then the knapsack algorithm was used to generate the nesting patterns of strips on segment of all possible sizes.Finally, the boundary position of the segments was determined by the principle of the maximum pattern value, and the two-segment nesting patterns of circular pieces on the whole plate were obtained.Compared the algorithm with the literature algorithm, the numerical results show that the pattern value of the proposed algorithm is higher than that of the literature algorithm.