锻压技术

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

英文标题：A constrained nesting algorithm of circular pieces based on two-segment patterns

作者：曾兆敏张春利

分类号：TP391

出版年,卷(期):页码：2017,42(8):180-184

摘要：

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

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.

基金项目：

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

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

参考文献：

［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.

服务与反馈：

【本网站尚未开通全文下载服务】【加入收藏】