A column generation-based algorithm for two-stage,two-dimensional bin packing problem with a variant variable sized constraint

详细信息    查看官网全文

• 英文论文题名：A column generation-based algorithm for two-stage,two-dimensional bin packing problem with a variant variable sized constraint
• 论文作者：Qi Zhang ; Shixin Liu ; Shujin Qin ; Yarong Shi
• 英文论文作者：Qi Zhang ; Shixin Liu ; Shujin Qin ; Yarong Shi ; College of Information Science and Engineering ; Northeastern University
• 年：2017
• 作者机构：College of Information Science and Engineering,Northeastern University;
• 英文论文关键词：two-dimensional bin packing ; variable size ; two stage packing ; column generation
• 会议召开时间：2017-07-26
• 会议录名称：第36届中国控制会议论文集（B）
• 英文会议录名称：Proceedings of the 36th Chinese Control Conference（B）
• 语种：英文
• 分类号：TP301.6
• 学会代码：KZLL
• 会议名称：第36届中国控制会议
• 会议地点：中国辽宁大连
• 主办单位：中国自动化学会控制理论专业委员会
• 学会名称：中国自动化学会控制理论专业委员会
• 页数：5
• 文件大小：340k
• 原文格式：D
• 会议级别：全国

摘要

In this paper, we consider two-dimensional bin packing problem with a variant variable sized constraint, where the width of the bin is continuously changed and the height of the bin is discretely changed, with the further restrictions that packing can be rotated and done in two stages. A column generation-based algorithm is proposed when the first cutting stage is the vertical direction. The problem is decomposed into a level packing problem and a level combining problem. Afterwards, a column generation(CG) algorithm and a cutting rule(CR) scheme are proposed respectively. Computational results for the practical instances show the effectiveness of the proposed method. Using the column generation-based algorithm above mentioned we solved the instances found at the OR-LIBRARY.
In this paper, we consider two-dimensional bin packing problem with a variant variable sized constraint, where the width of the bin is continuously changed and the height of the bin is discretely changed, with the further restrictions that packing can be rotated and done in two stages. A column generation-based algorithm is proposed when the first cutting stage is the vertical direction. The problem is decomposed into a level packing problem and a level combining problem. Afterwards, a column generation(CG) algorithm and a cutting rule(CR) scheme are proposed respectively. Computational results for the practical instances show the effectiveness of the proposed method. Using the column generation-based algorithm above mentioned we solved the instances found at the OR-LIBRARY.

引文

[1]A.Lodi,S.Martello,D.Vigo,Models and bounds for two-dimensional level packing problems,Journal of Combinatorial Optimization,8(3):363-379,2004.
    [2]A.Lodi,M.Monaci,E.Pietrobuoni,Partial enumeration algorithms for Two-Dimensional Bin Packing Problem with guillotine constraints,Discrete Applied Mathematics,217(1):40-47,2017.
    [3]J.Wy,B.Kim.Two-staged guillotine cut,two-dimensional bin packing optimization with flexible bin size for steel mother plate design,International Journal of Production Research,48(22):6799-6820,2010.
    [4]R.Morabito,V.Pureza,A heuristic approach based on dynamic programming and and/or-graph search for the constrained two-dimensional guillotine cutting problem,Annals of Operations Research,179(1):297-315,2010.
    [5]S.Hong,D.Zhang,H.Lau,A hybrid heuristic algorithm for the 2D variable-sized bin packing problem,European Journal of Operational Research,238(1):95-103,2014.
    [6]D.Pisinger,M.Sigurd,The two-dimensional bin packing problem with variable bin sizes and costs,Discrete Optimization,2(2):154-167,2005.
    [7]G.Cintra,F.Miyazawa,Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation,European Journal of Operational Research 191(1):61-85,2008.