矩形件无约束二维板材剪切的4块排样算法
CSTR:
作者:
作者单位:

1. 东北大学 工商管理学院,沈阳 110169;2. 东北大学 信息科学与工程学院,沈阳 110004;3. 东北大学 流程工业综合自动化国家重点实验室,沈阳 110004

作者简介:

通讯作者:

E-mail: weiping209@126.com.

中图分类号:

TH164

基金项目:

国家自然科学基金项目(71871049);国家自然科学基金重点国际合作研究项目(71620107003);辽宁省兴辽英才计划项目(XLYC1802115);流程工业综合自动化国家重点实验室基础科研业务费基金项目(2013ZCX11);东北大学博士后基金项目(20200311);中央高校基本科研业务费专项基金项目(N2106008).


A four-block layout algorithm for unconstrained two dimensional plate guillotine cutting problem of rectangular items
Author:
Affiliation:

1. School of Business Administration,Northeast University,Shenyang 110169,China;2. College of Information Science and Engineering,Northeastern University,Shenyang 110004,China;3. State Key Laboratory of Synthetical Automation for Process Industries,Northeastern University,Shenyang 110004,China

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    针对矩形件无约束二维板材剪切排样问题,提出一种新的4块排样方式及其生成算法.该排样方式将板材划分成4个块,对每个块,按照递归方式进行排样.选择一行同种矩形件放置在块的左下角,沿着这行矩形件的上边界和右边界将该块剩余部分划分成两个更小的子块以待进一步递归考察.首先,构造动态规划算法一次性生成所有可能尺寸的块中矩形件的递归排样方式;然后,采用隐式枚举算法确定板材的最优4块划分,得到矩形件在板材上的最优4块排样方式.采用文献基准例题和符合实际情况的随机例题,将所提出算法与几种典型的文献算法进行对比,实验结果表明所提出算法时间复杂度在低于或等于文献算法的前提下,排样方式价值比文献算法高.

    Abstract:

    A four-block layout and its generation algorithm are proposed for the unconstrained two-dimensional plate guillotine cutting problem of rectangular items, in which the plate is divided into four blocks, and each block is arranged recursively. A row of the same kind of rectangular items is selected and placed in the left lower corner of the block. Along the upper and right boundaries of this row of rectangular items, the rest of the block is divided into two smaller sub blocks for further recursive investigation. Firstly, the recursive layout of rectangular items in all possible size blocks is generated using the dynamic programming algorithm at one time. Then the optimal four-block layout of rectangular items on the plate is determined using the implicit enumeration algorithm. The algorithm is compared with several typical literature algorithms using literature benchmark examples and random examples in accordance with the actual situation. The experimental results show that the time complexity of this algorithm is lower than or equal to the literature algorithm, and the value of layout is higher than that of the literature algorithm.

    参考文献
    相似文献
    引证文献
引用本文

潘卫平,樊治平,黄敏.矩形件无约束二维板材剪切的4块排样算法[J].控制与决策,2022,37(5):1211-1219

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:
  • 最后修改日期:
  • 录用日期:
  • 在线发布日期: 2022-03-30
  • 出版日期: 2022-05-20
文章二维码