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

东北大学

作者简介:

通讯作者:

中图分类号:

TH164

基金项目:

国家自然科学基金项目(面上项目,重点项目,重大项目)


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;2.College of Information Science and Engineering, Northeastern University

Fund Project:

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

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

    Abstract:

    A four-block layout and its generation algorithm were proposed for unconstrained two-dimensional plate guillotine cutting problem of rectangular items.With this layout the plate was divided into four blocks, and each block was arranged recursively. A row of the same kind of rectangular items was selected and placed them 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 was divided into two smaller sub blocks for further recursive investigation. Firstly, the recursive layout of rectangular items in all possible size blocks was generated by dynamic programming algorithm at one time; then the optimal four-block layout of rectangular items on the plate was determined by implicit enumeration algorithm.The algorithm was compared with several typical literature algorithms by 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 literature algorithm.

    参考文献
    相似文献
    引证文献
引用本文
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2020-11-10
  • 最后修改日期:2021-02-22
  • 录用日期:2021-03-03
  • 在线发布日期: 2021-04-01
  • 出版日期: