Transactions of Materials and Heat Treatment

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

Authors： Zeng Zhaomin Zhang Chunli

Unit： Sichuan Institute of Information Technology Hebei Finance University

KeyWords： constrained nesting algorithm two-segment nesting patterns knapsack algorithm circular pieces strip

ClassificationCode：TP391

year,vol(issue):pagenumber：2017,42(8):180-184

Abstract：

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.

Funds：

四川省教育厅科研项目（GZY15C45）

曾兆敏（1974-），女，学士，副教授

Reference：

［1］侯桂玉. 圆形件下料启发式算法[D]. 桂林：广西师范大学, 2010.Hou G Y. An Efficient Heuristic Algorithm for the Circle-cutting Problem [D]. Guilin: Guangxi Normal University, 2010.
［2］秦旭辉. 圆形件剪切下料的排样研究[D].长春：吉林大学，2014.Qin X H. Layout Research of Circular Piece under the Way of Blanking [D]. Changchun: Jilin University, 2014.
［3］Cui Y, Yang Y. An algorithm for generating optimal constrained one-stage homogenous strip cutting patterns [J]. Engineering Optimization, 2010, 42(10): 943-957.
［4］Akeb H，Hifi M，Lazure D. A heuristic based algorithm for the 2D circular strip packing problem [J].Springer International Publishing, 2013, 470:73-92.
［5］Akeb H, Hifi M. Solving the circular open dimension problem by using separate beams and look-ahead strategies[J]. Computers & Operations Research, 2013, 40(5):1243-1255.
［6］Cui Y P, Cui Y, Tang T. Sequential heuristic for the two-dimensional bin-packing problem[J]. European Journal of Operational Research, 2015, 240(1): 43-53.
［7］朱强, 薛峰, 郑仕勇, 等. 约束二维排样问题的一种求解算法[J]. 锻压技术, 2016, 41(9): 148-152.Zhu Q, Xue F, Zheng S Y,et al. An algorithm of the constrained two-dimensional nesting [J]. Forging & Stamping Technology, 2016, 41(9): 148-152.
［8］Hifi M, M′Hallah R, et al. An exact algorithm for constrained two-dimensional two-staged cutting problems [J]. Operations Research, 2005, 53(1): 140-150.
［9］Cui Y. An exact algorithm for generating homogenous T-shape cutting patterns [J]. Computers & Operations Research, 2007, 34(4): 1107-1120.
［10］Cui Y, Huang B. Heuristic for constrained T-shape cutting patterns of rectangular pieces [J]. Computers & Operations Research, 2012, 39(12): 3031-3039.
［11］Cui Y P, Cui Y, Tang T, et al. Heuristic for constrained two-dimensional three-staged patterns[J]. Journal of the Operational Research Society, 2015, 66(4): 647-656.
［12］潘卫平, 陈秋莲, 崔耀东. 考虑切割刀数的最优两段排样算法研究[J]. 广西大学学报: 自然科学版, 2014, 39(3): 687-692.Pan W P, Chen Q L, Cui Y D. Research on the algorithm for generating optimal two segment cutting patterns with cuts number consideration[J]. Journal of Guangxi University：Natural Science Edition, 2014,39(3)：687-692.
［13］Kellerer H，Pferschy U，Pisinger D. Knapsack Problems[M]. Berlin: Springer,2004.

Service：

【This site has not yet opened Download Service】【Add Favorite】