ScholarMate
English简体中文繁體中文
客服热线:400-1616-289
登录注册
期刊论文

An Effective Corner Increment-Based Algorithm for the Two-Dimensional Strip Packing Problem

Chen, Zhen; Chen, Jianli*福州大学
IEEE Access2018DOI: 10.1109/ACCESS.2018.2882823
9被引3阅读
引用收藏
分享

摘要

The 2-D strip packing problem is an NP-hard combinatorial optimization problem. Given a strip with fixed width and infinite height, the aim of strip packing is to pack a set of rectangles with known widths and heights into the strip such that the used height of the strip is minimized. In this paper, we address the 2-D strip packing problem without guillotine constraint and present an effective corner increment-based algorithm. First, a corner increment-based rectangle selection strategy is adopted in a constructive heuristic way. Second, by using the AVL tree and the segment tree, the constructive heuristic is efficiently implemented. Finally, a multi-start random local search is combined to improve the solution. Experimental results on a wide range of benchmark instances show that the proposed algorithm is effective, especially for large instances.

学科与关键词

关键词
Two dimension strip packingcorner incrementAVL treesegment tree
相关
加载中…
  • A simple randomized algorithm for two-dimensional strip packing
    Yang, Shuangyuan*; Han, Shuihua; Ye, WeiguoCOMPUTERS & OPERATIONS RESEARCH, 2013, 40(1): 1-8.被引 23
  • A two-stage intelligent search algorithm for the two-dimensional strip packing problem
    Leung, Stephen C. H.; Zhang, Defu*; Sim, Kwang MongEUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2011, 215(1): 57-69.被引 68
  • A quasi-human algorithm for the two dimensional rectangular strip packing problem: in memory of Prof. Wenqi Huang
    Wang, Lei*; Yin, AihuaJOURNAL OF COMBINATORIAL OPTIMIZATION, 2016, 32(2): 416-444.被引 4
查看全部 →

发表信息

论文状态
公开发表
期刊
IEEE Access
发表日期
2018
卷期
第 6 卷
页码
72906-72924
DOI
10.1109/ACCESS.2018.2882823
语言
ENGLISH
期刊等级
Q1
成果收录
SCIE
资助标注
National Natural Science Foundation of China [11501115, 61672005]

作者

  • C

    Chen, Zhen (第一作者)

    fuzhou univ

  • C

    Chen, Jianli (通讯)

    fuzhou univ

登录解锁更多功能

  • 收藏这篇,随时在“我的 · 收藏”找回
  • 认领你的成果,生成推广素材
  • 关注作者获取最新成果
  • 加入项目组、协同写作
注册 / 登录

产品服务

  • 科研之友
  • 创新城
  • 科创云

服务支持

  • 帮助中心
  • 隐私政策
  • 服务条款

联系方式

在线客服:【】
客服热线:400-1616-289
电子邮箱:support@scholarmate.com

关注或下载科研之友

微信二维码
微信公众号
客户端下载二维码
下载客户端
科研成果科研人员科研机构科研动态爱瑞思软件

©2026 深圳市科研之友网络服务有限公司

公安备案图标粤公网安备 44030502000213
粤ICP备 16046710 号粤B2-20110417