锻压技术

匀质条带五块布局方式及其生成算法

英文标题：An algorithm of generating five block layout on uniform strip

作者：青巧李静管卫利

分类号：TP391

出版年,卷(期):页码：2016,41(12):37-41

摘要：

针对矩形毛坯无约束二维布局问题，提出一种匀质条带五块布局方式。这种布局方式将板材划分为5个矩形块，每个块由包含同种毛坯的匀质条带组成。构造五块布局方式的生成算法：首先采用动态规划方法生成所有可能尺寸的块中匀质条带的最优布局；然后采用隐式枚举和分支定界技术考察板材所有可能的五块划分方式，按照板材布局价值最大原则确定板材的最优五块划分，得到最终的五块布局方式图。数值实验结果表明，这种算法能有效地提高板材布局价值。

For the problem of two-dimensional layout without constraint on the rectangular blank, the five block layout on the uniform strip was put forward, and the blank was divided into five rectangular blocks, which were composed of uniform strips containing the same blanks respectively. Next, generation algorithm of this layout was constructed. Firstly, the optimal layouts of uniform strips on all possible size blocks were generated by dynamic programming method. Then, all possible five block layouts were investigated by implicit enumeration and branch and bound techniques. Furthermore, the optimal five block layout was confirmed and obtained based on the maximum principle of the blank layout value. Numerical experiment results show that this algorithm can effectively improve the value of the blank layout.

基金项目：

广西科学研究与技术开发计划(桂科攻11107006-13；桂科攻12118017-10A)

作者简介：青巧（1972-），女，硕士，高级工程师 E-mail：qqiaosc@163.com 通讯作者：管卫利（1979-），男，硕士，副教授 E-mail:gwlnn2001@126.com

参考文献：

［1］季君. 基于同形块的剪切下料布局算法研究
［D］. 北京：北京交通大学, 2012.

Ji J. Research on Guillotine Cutting Stock Packing Algorithm Based on Same-shape Block
［D］. Beijing：Beijing Jiaotong University, 2012.

［2］易向阳, 仝青山, 潘卫平. 矩形件二维下料问题的一种求解方法
［J］. 锻压技术, 2015, 40(6):150-153.

Yi X Y, Tong Q S, Pan W P. A solving method of two-dimensional cutting for the rectangular blanks
［J］.Forging & Stamping Technology, 2015, 40(6):150-153.

［3］Wscher G, Hauner H, Schumann H. An improved typology of cutting and packing problems
［J］. European Journal of Operational Research, 2007, 183(3):1109-1130.

［4］Andrade R, Birgin E G, Morabito R. Two-stage two-dimensional guillotine cutting stock problems with usable leftover
［J］. International Transactions in Operational Research, 2014, 23(1):121-145.

［5］Hadjiconstantinou E, Christofides N. An exact algorithm for general, orthogonal, two-dimensional knapsack problems
［J］. European Journal of Operational Research, 1995, 83(1):39-56.

［6］Chen C S, Lee S M, Shen Q S. An analytical model for the container loading problem
［J］. European Journal of Operational Research, 1995, 80(1):68-76.

［7］Cui Y. A new dynamic programming procedure for three-staged cutting patterns
［J］. Journal of Global Optimization, 2013, 55(2):349-357.

［8］潘卫平, 陈秋莲, 崔耀东, 等. 基于匀质条带的毛坯最优三块布局算法
［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.

［9］扈少华, 黄于欣, 管卫利. 矩形毛坯五块切割排样方式的生成算法
［J］. 锻压技术, 2016，41(7)：157-160.

Hu S H, Huang Y X, Guan W L. Generating algorithm of five block cutting nesting for rectangular blanks
［J］.Forging & Stamping Technology, 2016，41(7)：157-160.

［10］Kellerer H, Pferschy U, Pisinger D. Knapsack Problems
［M］.Berlin: Springer, 2004.

［11］Gun Y 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.

服务与反馈：

【文章下载】【加入收藏】