A constructive heuristic for the two-dimensional bin packing problem based on value correction strategy

被引：0

作者：

Yao, Yi ^{[1
,2
]}

Lai, Chaoan ^{[1
]}

机构：

[1] School of Business Administration, South China University of Technology, Guangzhou

[2] College of Computer and Electronics Information, Guangxi University, Nanning

来源：

Journal of Information and Computational Science | 2015年 / 12卷 / 12期

关键词：

Bin packing; Guillotine cut; Insertion; Replacement; Value correction;

D O I：

10.12733/jics20106371

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

This paper researches on 2D bins packing problems with guillotine-cut constraints. Four successful ideas are combined into a single coherent heuristic: (1) combining narrow items into a block and then packing it as a single item, (2) slicing the bin space into shelves and packing items shelf-by-shelf, (3) adopting value correction strategies of replacement and insertion, and (4) adopting shelf partitioning based on random numbers to guarantee the adversity of packing schemes. Computational experiments by benchmark test sets suggest that this approach rivals existing approaches in performance and owns the potential ability for application in the both patterns of RG and OG. Copyright © 2015 Binary Information Press.

引用

页码：4799 / 4809

页数：10

共 14 条

[1]

Wescher G., Haussner H., Schumann H., An improved typology of cutting and packing problems, European Journal of Operational Research, 183, pp. 1109-1130, (2007)

[2]

Lodi A., Martello S., Vigo D., Recent advances on two-dimensional bin packing problems, Discrete Applied Mathematics, 123, pp. 296-379, (2002)

[3]

Lodi A., Martello S., Vigo D., Two-dimensional packing problems: A survey, European Journal of Operational Research, 141, pp. 241-252, (2002)

[4]

He Y., Wu Y., de Souza R.D., A global search framework for practical three-dimensional packing with variable carton orientations, Computers & Operations Research, 39, pp. 2395-2414, (2012)

[5]

Egeblad J., Pisinger D., Heuristic approaches for the two- and three-dimensional knapsack packing problem, Computers & Operations Research, 36, pp. 1026-1049, (2009)

[6]

Ortmann F.G., Ntene N., van Vuuren J.H., New and improved level heuristics for the rectangular strip packing and variable-sized bin packing problems, European Journal of Operational Research, 203, pp. 306-315, (2010)

[7]

Zhu W., Zhang Z., Oon W.-C., Lim A., Space defragmentation for packing problems, European Journal of Operational Research, 222, pp. 452-463, (2012)

[8]

Crainic T.G., Perboli G., Tadei R., TS2 PACK: A two-level tabu search for the three-dimensional bin packing problem, European Journal of Operational Research, 195, pp. 744-760, (2009)

[9]

Chu C.B., Antonio J., Approximation algorithms to solve real-life multi-criteria cutting stock Problems, Operations Research, 47, 4, pp. 495-508, (1999)

[10]

Wei L., Tian T., Zhu W., Et al., A block-based layer building approach for the 2D guillotine strip packing problem, European Journal of Operational Research, 239, pp. 58-69, (2014)

← 1 2 →