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

The Orthogonal Packing and Scheduling Problem: Model, Heuristic, and Benchmark

He, Kun; Yang, Huan; Jin, Yan*; Hu, Qian; Ji, Pengli华中科技大学; 南京大学
IEEE Transactions on Systems Man Cybernetics-Systems2020-4DOI: 10.1109/TSMC.2017.2768072
3阅读
引用收藏
分享

摘要

This paper addresses a new orthogonal packing and time scheduling problem-3D space-time optimization problem (3D-STO). Given a rectangular sheet and a set of rectangular items, each item needs to be continuously processed with a time length on the sheet, the 3D-STO consists in arranging each item's loading time, location, and orientation for a certain period such that the total utilization time of the sheet, i.e., the makespan of the schedule, is minimized. The 3D-STO involves a series of 2D rectangular packing problem (2D-RPP) for the whole scheduling period. If the processing time of each item is simply regarded as a space dimension for the packing, then the 3D-STO can be reduced to an NP-hard packing problem-3D strip packing problem (3D-SPP). The 3D-STO differs from the 3D-SPP in that the position and orientation of items can be changed over the processing time (the third dimension) such that the 3D-STO has a much larger search space compared with the 3D-SPP. Hereby, the optimal solution of the 3D-STO is better than or equal to the optimal solution of the 3D-SPP, and a possibly better solution could be found for the 3D-STO model. As a new model, there is no algorithm or benchmark in the literature. Moreover, the 2D-RPP and 3D-SPP algorithms are not suitable for solving the 3D-STO which considers the packing and scheduling simultaneously. Hereby, we propose a caving-degree-based scheduling algorithm (CDS) for the 3D-STO. This is the first proposed 3D-STO algorithm. We also formalize the problem as a mixed integer programming model and solve it by ILOG CPLEX. For evaluation, we provide a synthesized method to generate a total of 195 various benchmark instances with guillotine and nonguillotine cut constraints. The comparative results show that CDS is more effective than the CPLEX solver for the 3D-STO. Also, when comparing CDS for the 3D-STO and the adapted CDS for the 3D-SPP, we see that the new 3D-STO model can enhance the flexibility of the item arrangement and make maximum utilization of the sheet and time.

学科与关键词

关键词
SchedulesJob shop schedulingSiliconBenchmark testingOptimal schedulingLinear programmingCaving degreedeterministicNP-hardpackingscheduling
相关
加载中…
  • A reference length approach for the 3D strip packing problem
    Wei, Lijun; Oon, Wee-Chong; Zhu, Wenbin*; Lim, AndrewEUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2012, 220(1): 37-47.被引 14
  • Solving a 3D bin packing problem with stacking constraints
    Zhu, Weiwang; Chen, Sheng; Dai, Min; Tao, Jiping*COMPUTERS & INDUSTRIAL ENGINEERING, 2024, 188: 109814.被引 6
  • A tree search algorithm for solving the multi-dimensional strip packing problem with guillotine cutting constraint
    Bortfeldt, Andreas*; Jungmann, SabineAnnals of Operations Research, 2012, 196(1): 53-71.被引 11
查看全部 →

发表信息

论文状态
公开发表
期刊
IEEE Transactions on Systems Man Cybernetics-Systems
发表日期
2020-04
卷期
第 50 卷, 第 4 期
页码
1372-1383
DOI
10.1109/TSMC.2017.2768072
语言
ENGLISH
期刊收录
NSL.SCIE
期刊等级
1区
成果收录
SCIE
资助标注
National Natural Science Foundation of China [61173180, 61472147, 61602196, 61373016, 71501092]; Shenzhen Science and Technology Planning Project [JCYJ20170307154749425]

作者

  • H

    He, Kun (第一作者)

    huazhong univ sci & technol, shenzhen res inst · huazhong univ sci & technol

  • Y

    Yang, Huan

    huazhong univ sci & technol, shenzhen res inst · huazhong univ sci & technol

查看全部 5 位作者收起作者
  • J

    Jin, Yan (通讯)

    huazhong univ sci & technol, shenzhen res inst · huazhong univ sci & technol

  • H

    Hu, Qian

    nanjing univ

  • J

    Ji, Pengli

    huazhong univ sci & technol, shenzhen res inst · huazhong univ sci & technol

登录解锁更多功能

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

产品服务

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

服务支持

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

联系方式

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

关注或下载科研之友

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

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

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