网站首页期刊简介编委会过刊目录投稿指南广告合作征订与发行联系我们English
基于同质条带的两段式有约束矩形优化排样
英文标题: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.
服务与反馈:
本网站尚未开通全文下载服务】【加入收藏
《锻压技术》编辑部版权所有

中国机械工业联合会主管 北京机电研究所有限公司 中国机械工程学会塑性工程分会主办
联系地址:北京市海淀区学清路18号 邮编:100083
电话:+86-010-82415085 传真:+86-010-62920652
E-mail: fst@263.net(稿件) dyjsjournal@163.com(广告)
京ICP备07007000号-9