|
Abstract：
|
|
For the problem of unconstrained two-dimensional cutting pattern problem for rectangular part, a four-ordinary-block cutting pattern and its generation algorithm were proposed. Firstly, the sheet was divided into four ordinary blocks, then the ordinary blocks were cut into strips, and finally the strips were cut into the required rectangular parts. However, the ordinary block was consisted of strips, and only one strip was cut from the ordinary block each time. Therefore, the directions of two strips cut continuously were parallel or perpendicular to each other. Furthermore, firstly, the optimal layout of rectangular parts on strips was determined by the knapsack algorithm, then the optimal layout of strips on ordinary blocks was confirmed by the recursive algorithm, and finally the optimal four-block partition of sheet was obtained by the implicit enumeration method. Compared the proposed algorithm with the literature algorithms for two sets of literature instances, the experimental results show that the value of the proposed algorithm is higher than that of four literature algorithms.
|
|
Funds：
|
|
河南省科技厅科技攻关项目 (172102210298 )
|
|
AuthorIntro：
|
|
刘小可（1981-），男，硕士，工程师，E-mail：lxkhnxx@163.com；通讯作者：邓国斌（1976-），男，硕士，副教授，E-mail：jsgxdgb@163.com
|
|
Reference：
|
[1]Savi Aleksandar,ukilovi Tijana, Filipovi Vladimir. Solving the two-dimensional packing problem with m-M calculus[J]. Yugoslav Journal of Operations Research, 2011, 21(1): 93-102.
[2]Furini F, Malaguti E, Thomopulos D. Modeling two-dimensional guillotine cutting problems via integer programming[J]. Informs Journal on Computing, 2016, 28(4): 736-751.
[3]Lodi A, Monaci M. Integer linear programming models for 2-staged two-dimensional knapsack problems[J]. Mathematical Programming, 2003, 94(2-3): 257-278.
[4]崔耀东. 生成矩形毛坯最优T形排样方式的递归算法[J]. 计算机辅助设计与图形学学报, 2006, 18(1): 125- 127.
Cui Y D. Recursive algorithm for generating optimal T-shape cutting patterns of rectangular blanks[J]. Journal of Computer-aided Design & Computer Graphics, 2006, 18(1):125-127.
[5]Cui Y. A new dynamic programming procedure for three-staged cutting patterns[J]. Journal of Global Optimization, 2013, 55(2): 349-357.
[6]扈少华，潘立武，管卫利. 复合条带三阶段排样方式的生成算法[J].锻压技术，2016，41（11）：149-152.
Hu S H，Pan L W，Guan W L. A generating algorithm of three-stage nesting patterns for composite strip[J]. Forging & Stamping Technology，2016，41（11）：149-152.
[7]Young G G, Seong Y J, Kang M K. A best-first branch and bound algorithm for unconstrained two-dimensional cutting problems[J]. Operations Research Letters, 2003, 31(4): 301-307.
[8]沈萍, 邓国斌. 应用递归划分策略解决矩形件剪切排样问题[J]. 锻压技术, 2018, 43(3): 181-185.
Shen P, Deng G B. Application of recursive partitioning strategy in solving guillotine cutting problem of rectangular piece[J]. Forging & Stamping Technology, 2018, 43(3): 181-185.
[9]杨传民, 王树人, 王心宇. 基于 4 块结构的斩断切割布局启发性算法[J]. 机械设计, 2007, 24(2): 25-26.
Yang C M, Wang S R, Wang X Y. Heuristic algorithm on layout of chopped cutting based on 4 pieces of structure[J]. Journal of Machine Design, 2007, 24(2): 25-26.
[10]潘卫平, 陈秋莲, 崔耀东,等. 基于匀质条带的矩形件最优三块布局算法[J]. 图学学报, 2015, 36(1):7-11.
Pan W P, Chen Q L, Cui Y D, et al. An algorithm for generating optimal homogeneous strips three block patterns of rectangular blanks[J]. Journal of Graphics, 2015, 36(1): 7-11.
[11]蓝雯飞, 吴子莹, 杨波. 背包问题的动态规划改进算法[J]. 中南民族大学学报：自然科学版, 2016, 35(4): 101-105.
Lan W F, Wu Z Y, Yang B. Improved dynamic programming algorithms for the knapsack problem[J]. Journal of South-central University for Nationalities: Natural Science Edition, 2016, 35 (4):101-105.
[12]Kellerer H, Pferschy U, Pisinger D. Knapsack Problems [M]. Berlin: Springer, 2004.
[13]罗运贞，潘立武. 约束剪切问题的三块排样方式及其生成算法[J].锻压技术，2018,43(10):185-189.
Luo Y Z，Pan L W. Three-block layout pattern and its generation algorithm of constrained cutting problem [J]. Forging & Stamping Technology，2018, 43(10): 185-189.
|
|
Service：
|
|
【This site has not yet opened Download Service】【Add
Favorite】
|
|
|
|
Copyright Forging & Stamping Technology.All rights reserved