|
摘要：
|
|
针对矩形件无约束二维剪切排样问题，提出普通块四块排样方式及其生成算法。这种排样方式首先将板材划分成4个普通块，然后将普通块切成条带，最后将条带切成所需要的矩形件。普通块由条带组成，每刀在普通块上仅切下一根条带，连续被切下的两根条带的方向互相平行或垂直。首先采用背包算法确定条带中矩形件的最优布局，然后采用递推算法确定普通块中条带的最优布局，最后采用隐式枚举法确定板材的最优四块划分。采用2组文献例题将本文算法与文献算法进行比较，实验结果表明，本文算法排样价值高于4种文献算法。
|
|
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.
|
|
基金项目：
|
|
河南省科技厅科技攻关项目 (172102210298 )
|
|
作者简介：
|
|
刘小可（1981-），男，硕士，工程师，E-mail：lxkhnxx@163.com；通讯作者：邓国斌（1976-），男，硕士，副教授，E-mail：jsgxdgb@163.com
|
|
参考文献：
|
[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.
|
|
服务与反馈：
|
|
【文章下载】【加入收藏】
|
|
|
|
