锻压技术

基于同质条带的两段式有约束矩形优化排样

英文标题：Optimal layout of constrained rectangle based on two-segment homogeneous strips

作者：姜永亮张亚敏

分类号：TP391.7

出版年,卷(期):页码：2016,41(2):138-143

摘要：

为了有效解决企业生产中的有约束矩形优化排样问题，对矩形优化排样算法进行研究，在综合考虑原材料利用率及切割工艺复杂度的情况下，给出基于同质条带的两段式有约束矩形优化排样算法。算法首先通过问题转换，将有约束矩形优化排样问题转化成多重背包问题，然后再基于动态规划算法对其进行求解，最后基于动态规划算法开发了一应用系统，有效地解决了企业实际生产中的有约束矩形优化排样问题。实例应用表明，该算法在求解有约束矩形优化排样问题方面优于其他算法。

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.

基金项目：

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

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

参考文献：

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

服务与反馈：

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