基于排样矩形的直角边零件下料算法
作者:
基金项目:

国家自然科学基金青年基金(41706198); 山东省高等学校科技计划(J17KA056)


Rectilinear Parts Cutting Algorithm Based on Layout Rectangle
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [16]
  • |
  • 相似文献
  • |
  • 引证文献
  • | |
  • 文章评论
    摘要:

    针对实际操作中直角边零件下料利用率不高的问题, 导入排样矩形的概念, 将直角边零件下料问题分解为若干优化子问题, 在此基础上, 基于动态规划思想通过求解子问题构建全局最优解. 实验表明, 与传统的直角边零件板材切割相比, 使用本文算法能够使板材的利用率提高30%–50%; 与其他几种典型算法相比, 本算法板材利用率提高显著, 并且排样方案简单, 更适用于实际操作.

    Abstract:

    For the rectilinear parts cutting problem of low sheet utilization rate in practice, the concept of layout rectangle is introduced. The rectilinear parts cutting problem is decomposed into several optimization sub-problems. On this basis, the global optimal solution is constructed by solving the sub-problems based on dynamic programming. Experiment shows that compared with the traditional method of rectilinear parts cutting, the sheet utilization rate can be increased by 30%–50%. Compared with other typical algorithms, the sheet utilization rate is significantly improved and the scheme is more practical to layout.

    参考文献
    [1] 贾志欣. 排样问题的研究现状与趋势. 计算机辅助设计与图形学学报, 2004, 16(7): 890–897. [doi: 10.3321/j.issn:1003-9775.2004.07.003
    [2] 张燕玲, 陆一平, 吴九蕊, 等. 二维直角边不规则零件下料问题研究. 计算机工程与设计, 2014, 35(6): 2197–2201. [doi: 10.3969/j.issn.1000-7024.2014.06.061
    [3] Moretti AC, de Salles Neto LL. Nonlinear cutting stock problem model to minimize the number of different patterns and objects. Computational & Applied Mathematics, 2008, 27(1): 61–78
    [4] Afsharian M, Niknejad A, Wäscher G. A heuristic, dynamic programming-based approach for a two-dimensional cutting problem with defects. OR Spectrum, 2014, 36(4): 971–999. [doi: 10.1007/s00291-014-0363-x
    [5] 戚得众, 饶运清, 余天. 板类零件分组下料优化研究. 机械设计与制造, 2015, (6): 129–133
    [6] Furini F, Malaguti E, Thomopulos D. Modeling two-dimensional guillotine cutting problems via integer programming. INFORMS Journal on Computing, 2016, 28(4): 736–751. [doi: 10.1287/ijoc.2016.0710
    [7] 葛志辉, 王阳, 潘海鸿, 等. 工艺约束策略下的二维不规则零件排样算法. 广西大学学报(自然科学版), 2018, 43(2): 580–588
    [8] 张旭, 王莉莉, 杨博韬. 带有一刀切约束的二维非规则装箱算法. 计算机科学, 2020, 47(5): 212–216. [doi: 10.11896/jsjkx.190400078
    [9] Hartmanis J. Computers and intractability: A guide to the theory of NP-completeness (Michael R. Garey and David S. Johnson). SIAM Review, 1982, 24(1): 90–91
    [10] Belov G, Kartak V M, Rohling H, et al. Conservative scales in packing problems. OR Spectrum, 2013, 35(2): 505–542. [doi: 10.1007/s00291-011-0277-9
    [11] 卢蓉, 范勇, 陈念年, 等. 一种提取目标图像最小外接矩形的快速算法. 计算机工程, 2010, 36(21): 178–180. [doi: 10.3969/j.issn.1000-3428.2010.21.064
    [12] 邓国斌, 沈萍, 潘立武. 基于多段排样方式的卷材二维剪切下料算法. 锻压技术, 2019, 44(9): 46–50
    [13] Cui YD, Huang BX. Reducing the number of cuts in generating three-staged cutting patterns. European Journal of Operational Research, 2012, 218(2): 358–365. [doi: 10.1016/j.ejor.2011.10.047
    [14] Korte B, Vygen J. The knapsack problem. In: Korte B, Vygen J, eds. Combinatorial Optimization: Theory and Algorithms. Berlin Heidelberg: Springer, 2012. 459–470.
    [15] 裘瀚照. 二维不规则下料问题的几何干涉检查及模型简化研究[硕士学位论文]. 北京: 北京交通大学, 2015.40–70.
    [16] 周俊鹏. 不规则钣金零件的下料优化系统研究[硕士学位论文]. 北京: 北京交通大学, 2016.29–40.
    相似文献
    引证文献
引用本文

郭百海,隋毅.基于排样矩形的直角边零件下料算法.计算机系统应用,2021,30(1):162-167

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2020-05-30
  • 最后修改日期:2020-06-23
  • 在线发布日期: 2020-12-31
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京海淀区中关村南四街4号 中科院软件园区 7号楼305房间,邮政编码:100190
电话:010-62661041 传真: Email:csa (a) iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号