Transactions of Materials and Heat Treatment

Title：An algorithm of the constrained two-dimensional nesting

Authors： Zhu Qiang Xue Feng Zheng Shiyong Guan Weili

Unit： Zhongyuan University of Technology Hezhou University Nanning University

KeyWords： two-dimensional nesting problem with constrain nesting algorithm implicit enumeration rectangular blanks five block nesting pattern

ClassificationCode：TP391

year,vol(issue):pagenumber：2016,41(9):148-151

Abstract：

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.

Funds：

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

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

Reference：

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

Service：

【This site has not yet opened Download Service】【Add Favorite】