锻压技术

约束二维排样问题的一种求解算法

英文标题：An algorithm of the constrained two-dimensional nesting

作者：朱强薛峰郑仕勇管卫利

单位：中原工学院贺州学院南宁学院

关键词：有约束排样问题排样算法隐式枚举矩形毛坯五块排样方式

分类号：TP391

出版年,卷(期):页码：2016,41(9):148-151

摘要：

讨论有约束二维切割排样问题，即将板材切割成若干种矩形毛坯，其中每种毛坯的数量有上界约束，优化目

标以使板材所切割的毛坯总价值（排样价值）最大。采用五块排样方式简化切割工艺，将板材切割成五块，

每块切割成所需毛坯。构造一种基于隐式枚举和分支定界思想的算法生成五块排样方式：（1）计算所有可

能尺寸的块的排样价值；（2）选择排样价值最大的五块组合生成五块排样方式；（3）采用文献中的基准测

题，验证文中的有约束五块排样算法。研究结果表明，文中算法平均排样价值比文献中的3种算法分别高出

12.85%，4.52%和1.89%，且算法计算时间较短。

The constrained two-dimensional nesting problem was discussed, and the total value of the

blank was in the maximum when one blank was cut to meet upper bound and optimization

objective. The cutting process was simplified by five-block pattern. The blank was cut into

five-blocks, and then each block was cut into the required blanks. An algorithm based on

implicit enumeration and branch bound algorithm was constructed to generate five-block

pattern. Firstly, the nesting values of all possible size blocks were calculated, and then the

five-block combination which had the maximal value was chosen to generate five-block pattern.

Finally, the five-block pattern algorithm with constrain was tested by the benchmark problems

of the literature. The research results show that the average value of the proposed algorithm

is higher than those of the literature about 12.85%, 4.52%, 1.89% respectively, and the

computation time is shorter.

基金项目：

广西自然科学基金资助项目（2015GXNFBA139264）；贺州市科技开发项目（贺科能1506006）

朱强（1985-），男，硕士，讲师郑仕勇（1983-），男，硕士，高级工程师

参考文献：

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

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

150-154.

Yi X Y, Tong Q S, Pan W P. A solving method of two-dimensional cutting for the rectangular
［J

］.Forging & Stamping Technology, 2015, 40(6): 150-154.

［3］王晓新，陈磊. 基于高斯过程的萤火虫算法及其在板料成形优化设计中的应用[J].锻压技术,

2015, 40(12): 26-34.

Wang X X, Chen L. Firefly algorithm and application in sheet metal forming optimization based

on Gaussian process[J].Forging & Stamping Technology, 2015, 40(12): 26-34.

［4］ Hifi M, Roucairol C. Approximate and exact algorithms for constrained (un) weighted

two-dimensional two-staged cutting stock problems[J]. Journal of Combinatorial Optimization,

2001, 5(4): 465-494.

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

［6］ Lodi A, Monaci M. Integer linear programming models for 2-staged two-dimensional

knapsack problems[J]. Mathematical Programming, 2003, 94(2-3): 257-278.

［7］ Belov G, Scheithauer G. A branch-and-cut-and-price algorithm for one-dimensional stock

cutting and two-dimensional two-stage cutting[J]. European Journal of Operational Research,

2006, 171(1): 85-106.

［8］ Hifi M, M′ Hallah R. Strip generation algorithms for constrained two-dimensional two

-staged cutting problems[J]. European Journal of Operational Research, 2006, 172(2): 515-

527.

［9］ Hifi M, M′ Hallah R, Saadi T. Algorithms for the constrained two-staged two-

dimensional cutting problem[J]. Informs Journal on Computing, 2008, 20(2): 212-221.

［10］Hifi M, Negre S, Ouafi R, et al. A parallel algorithm for constrained two-staged two-

dimensional cutting problems[J]. Computers & Industrial Engineering, 2012, 62(1): 177-189.

［11］季君, 陆一平, 查建中, 等. 生成矩形毛坯最优两段排样方式的确定型算法[J]. 计算机学报,

2012,35(1):183-191.

Ji J, Lu Y P, Zha J Z, et al.A deterministic algorithm for optimal two-segment cutting

patterns of rectangular blanks[J].Chinese Journal of Computers，2012,35(1):183-191.

［12］Cui Y, Yang Y. A recursive branch-and-bound algorithm for constrained homogenous T-shape

cutting patterns[J]. Mathematical and Computer Modelling, 2011, 54(5): 1320-1333.

服务与反馈：

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