带剪刃长度限制的圆形片有约束多段剪冲排样算法
|
摘要
讨论带剪刃长度限制的圆形片有约束剪冲排样问题,即采用先剪切后冲压的工艺将一张板材剪冲出若干种圆形片,对每种圆形片在板材上允许出现的次数有上界约束,且剪切机剪刃长度有限制,优化目标是使得板材剪冲出的圆形片总价值最大。提出一种多段排样方式的生成算法:第1阶段将板材剪切成多个段,其中每个段的长度不大于剪刃长度;第2阶段将段剪切成一组具有相同方向和长度的条料;第3阶段将条料冲压出圆形片。采用递归算法分别生成条料在段上的布局和段在板材上的布局。使用文献例题和实际生产实例,将本文算法与文献算法进行比较,结果表明,本文算法排样价值高于3种文献算法。
The nesting problem of constrained shearing and punching of circular pieces limited by blade length was discussed,namely,several types of circular pieces were conducted on a plate by first shearing and then punching process,and the number of times each circular piece allowed to appear on the plate was set an upper bound constraint. Then,the blade length of shearing machine was limited,and the optimization objective was to make the total value of circular pieces divided from the plate reach the maximum. A generation algorithm of multi-segment nesting pattern was proposed. In the first stage,the plate was cut into multiple segments,in which the length of each segment was not greater than the length of blade. In the second stage,the segments were cut into a group of strips with the same direction and length. In the third stage,the strips were punched into circular pieces. Furthermore,the nesting of strips on the segment and segments on the plate were generated by the recursive algorithm,respectively. The comparison between the algorithm in this paper and the literature algorithm was made by the literature instances and the actual production example. The results show that the nesting value of the algorithm in this paper is higher than that of the three literature algorithms.
The nesting problem of constrained shearing and punching of circular pieces limited by blade length was discussed,namely,several types of circular pieces were conducted on a plate by first shearing and then punching process,and the number of times each circular piece allowed to appear on the plate was set an upper bound constraint. Then,the blade length of shearing machine was limited,and the optimization objective was to make the total value of circular pieces divided from the plate reach the maximum. A generation algorithm of multi-segment nesting pattern was proposed. In the first stage,the plate was cut into multiple segments,in which the length of each segment was not greater than the length of blade. In the second stage,the segments were cut into a group of strips with the same direction and length. In the third stage,the strips were punched into circular pieces. Furthermore,the nesting of strips on the segment and segments on the plate were generated by the recursive algorithm,respectively. The comparison between the algorithm in this paper and the literature algorithm was made by the literature instances and the actual production example. The results show that the nesting value of the algorithm in this paper is higher than that of the three literature algorithms.
引文
[1] Stoyan Y,Yaskov G. Packing unequal circles into a strip of minimal length with a jump algorithm[J]. Optimization Letters,2014,8(3):949-970.
[2] He K,Huang M,Yang C. An action-space-based global optimization algorithm for packing circles into a square container[J].Computers&Operations Research,2015,58:67-74.
[3] Zeng Z Z,Yu X G,He K,et al. Adaptive tabu search and variable neighborhood descent for packing unequal circles into a square[J]. Applied Soft Computing,2018,65:196-213.
[4]胡钢,杨瑞,潘立武.基于价值修正的圆片下料顺序启发式算法[J].图学学报,2016,37(3):337-341.Hu G,Yang R,Pan L W. Sequential value correction heuristic algorithm for the circle cutting stock problem[J]. Journal of Graphics,2016,37(3):337-341.
[5] 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.
[6] Cui Y,Cui Y P,Yang L. Heuristic for the two-dimensional arbitrary stock-size cutting stock problem[J]. Computers&Industrial Engineering,2014,78:195-204.
[7] Chen Q,Cui Y,Chen Y. Sequential value correction heuristic for the two-dimensional cutting stock problem with three-staged homogenous patterns[J]. Optimization Methods and Software,2016,31(1):68-87.
[8] Cui Y,Yang Y. An algorithm for generating optimal constrained one-stage homogenous strip cutting patterns[J]. Engineering Optimization,2010,42(10):943-957.
[9] Cui Y,Huang B. A heuristic for constrained T-shape cutting patterns of circular items[J]. Engineering Optimization,2011,43(8):867-877.
[10]曾兆敏,张春利.基于两段方式的圆形片约束排样算法[J].锻压技术,2017,42(8):180-184.Zeng Z M,Zhang C L. A constrained nesting algorithm of circular pieces based on two-segment patterns[J]. Forging&Stamping Technology,2017,42(8):180-184.
[11] Dusberger F,Raidl G R. Solving the 3-staged 2-dimensional cutting stock problem by dynamic programming and variable neighborhood search[J]. Electronic Notes in Discrete Mathematics,2015,47:133-140.
[12]姜永亮.基于最优同质块的分段式矩形优化排样[J].锻压技术,2017,42(7):182-186.Jiang Y L. Rectangular optimal layout based on segments filled with optimal homogeneous blocks[J]. Forging&Stamping Technology,2017,42(7):182-186.
[2] He K,Huang M,Yang C. An action-space-based global optimization algorithm for packing circles into a square container[J].Computers&Operations Research,2015,58:67-74.
[3] Zeng Z Z,Yu X G,He K,et al. Adaptive tabu search and variable neighborhood descent for packing unequal circles into a square[J]. Applied Soft Computing,2018,65:196-213.
[4]胡钢,杨瑞,潘立武.基于价值修正的圆片下料顺序启发式算法[J].图学学报,2016,37(3):337-341.Hu G,Yang R,Pan L W. Sequential value correction heuristic algorithm for the circle cutting stock problem[J]. Journal of Graphics,2016,37(3):337-341.
[5] 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.
[6] Cui Y,Cui Y P,Yang L. Heuristic for the two-dimensional arbitrary stock-size cutting stock problem[J]. Computers&Industrial Engineering,2014,78:195-204.
[7] Chen Q,Cui Y,Chen Y. Sequential value correction heuristic for the two-dimensional cutting stock problem with three-staged homogenous patterns[J]. Optimization Methods and Software,2016,31(1):68-87.
[8] Cui Y,Yang Y. An algorithm for generating optimal constrained one-stage homogenous strip cutting patterns[J]. Engineering Optimization,2010,42(10):943-957.
[9] Cui Y,Huang B. A heuristic for constrained T-shape cutting patterns of circular items[J]. Engineering Optimization,2011,43(8):867-877.
[10]曾兆敏,张春利.基于两段方式的圆形片约束排样算法[J].锻压技术,2017,42(8):180-184.Zeng Z M,Zhang C L. A constrained nesting algorithm of circular pieces based on two-segment patterns[J]. Forging&Stamping Technology,2017,42(8):180-184.
[11] Dusberger F,Raidl G R. Solving the 3-staged 2-dimensional cutting stock problem by dynamic programming and variable neighborhood search[J]. Electronic Notes in Discrete Mathematics,2015,47:133-140.
[12]姜永亮.基于最优同质块的分段式矩形优化排样[J].锻压技术,2017,42(7):182-186.Jiang Y L. Rectangular optimal layout based on segments filled with optimal homogeneous blocks[J]. Forging&Stamping Technology,2017,42(7):182-186.