Transactions of Materials and Heat Treatment

Title：Optimal layout of constrained rectangle based on two-segment homogeneous strips

Authors： Jiang Yongliang Zhang Yamin

Unit： Hainan Normal University Luohe Medical College

KeyWords： homogeneous strip two-segment layout dynamic programming algorithm multiple knapsack problems

ClassificationCode：TP391.7

year,vol(issue):pagenumber：2016,41(2):138-143

Abstract：

To effectively solve the optimal layout problem of constrained rectangle in the actual production, the rectangular optimal layout algorithms were studied. A constrained rectangle layout algorithm was put forward based on two-segment homogeneous strips and under the consideration of the utilization rate of raw materials and the cutting process complexity. Firstly, the algorithm was transferred from the constrained rectangular optimal layout problem into the multiple knapsack problems. Then it was solved by dynamic programming algorithm, and a set of application system was developed finally. Therefore, the problem of constrained rectangle layout was solved in the actual production effectively. The application examples show that the algorithm is superior to other algorithms in solving the problem of constrained rectangle optimal layout.

Funds：

国家自然科学基金资助项目(71361008)；海南省重点科技基金资助项目（ZDXM20130080）；海南省自然科学基金资助项目（612136）；河南省基础与前沿技术研究计划资助项目(142300410105)

姜永亮（1980-），男，硕士，副教授

Reference：

[1]Hochbaum D S, Wolfgang M. Approximation schemes for covering and packing problems in image processing and VLSI[J]. Journal of the Association for Computing Machinery,1985,32(1): 130-136.

[2]Leung J, Tam T, Wong C S, et al. Packing squares into square[J]. Journal of Parallel and Distributed Computing, 1990, 10(3): 271-275.

[3]王晓庆,李尚芳,崔耀东.矩形毛坯最优层排样方式的动态规划算法[J].计算机应用研究,2010,27(6):2064-2067.Wang X Q, Li S F, Cui Y D. Dynamic programming algorithm for generating optimal layer patterns of rectangular blanks [J]. Application Research of Computers, 2010, 27(6):2064-2067.

[4]季君，陆一平，查建中，等.生成矩形毛坯最优两段排样方式的确定型算法[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.

[5]曹大勇,杨梅,科托夫·弗拉基米尔·米哈伊拉维奇,等.二维一刀切装箱问题的两阶段启发式算法[J].计算机集成制造系统,2012,18(9):1954-1963.Cao D Y, Yang M, Kotov V M, et al. Two-stage heuristic algorithm for two-dimensional guillotine bin packing problem[J]. Computer Integrated Manufacturing Systems, 2012,18(9):1954-1963.

[6]苏兰.冲裁条带三块排样方式的动态规划算法[J].河南师范大学学报:自然科学版,2014,42(6):148-153.Su L. Dynamic programming algorithm for three-block cutting patterns of punched strip [J]. Journal of Henan Normal University: Natural Science Edition, 2014, 42(6):148-153.

[7]季君，邢斐斐，杜钧，等.生成最优同形块两阶段布局方式的确定型算法[J].计算机应用,2014,34(5):1511-1515.Ji J, Xing F F, Du J, et al. Deterministic algorithm for optimal two-stage cutting layouts with same shape block[J].Journal of Computer Applications, 2014,34(5):1511-1515.

[8]何霖，刘强，王晶，等.满足“一刀切” 约束的矩形件交互式排样系统[J].现代制造工程,2015,(4):81-88.He L, Liu Q, Wang J, et al. An interactive acking system based on guillotine constraint [J].Modern Manufacturing Engineering,2015,(4):81-88.

[9]梁秋月,崔耀东,游凌伟.应用三块排样方式求解二维下料问题[J].广西师范大学学报:自然科学版,2014,32(3):41-45.Liang Q Y, Cui Y D, You L W. Solving two-dimensional cutting stock problem with three-block patterns [J]. Journal of Guangxi Normal University: Natural Science Edition, 2014, 32(3):41-45.

[10]彭文.一种快速的有约束矩形件优化排样模型[J].计算机工程与应用，2010,46(27）:214-216.Peng W. A quick model for guillotine rectangle cutting problem [J].Computer Engineering and Applications, 2010,46(27):214-216.

[11]罗丹,崔耀东,李秋蓉.生成匀质块排样方式的递推算法[J].计算机工程与设计，2013,34(3):1112-1115.Luo D, Cui Y D, Li Q R. Recursive algorithm for uniform block patterns[J].Computer Engineering and Design, 2013,34(3):1112-1115.

[12]Hand Hifi, Catherine Roucairol. Approximate and exact algorithms for constrained(Un) weighted two-dimensional two-staged cutting stock problems[J]. Journal of Combinatorial Optimization, 2001,5(1):465-494.

[13]Yao D C. Fast heuristic for constrained homogenous T-shape cutting patterns[J].Applied Mathematical Modelling, 2012,36(1):3696-3711.

Service：

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