Abstract
A triple-solution approach for the rectangular level strip packing problem is presented, where m item types with specified demands are packed in levels into a strip with definite width and infinite height to minimize the occupied height, with the constraint that the items in the same level cannot be placed one on top of the other. The approach contains two phases and considers three types of solutions. In phase one, two types of solutions, obtained respectively from solving residual problems using column generation and from looking ahead, are considered and the best is selected as phase-one solution. In phase two, an integer programming model is solved over the levels generated in phase-one to obtain phase-two solution. Finally the better one of the phase-one and phase-two solutions are selected. Computational results indicate that the approach is effective for both the instances with strongly heterogeneous items and those with weakly heterogeneous items.
Similar content being viewed by others
References
Alvarez-Valdes R, Parreño F, Tamarit JM (2008) Reactive GRASP for the strip-packing problem. Comput Oper Res 35:1065–1083
Alvarez-Valdes R, Parreño F, Tamarit JM (2009) A branch and bound algorithm for the strip packing problem. OR Spectr 31:431–459
Bettinelli A, Ceselli A, Righini G (2008) A branch-and-price algorithm for the two-dimensional level strip packing problem. 4OR-Q J Oper Res 6(4):361–374
Bortfeldt A (2006) A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces. Eur J Oper Res 172:814–837
Cintra GF, Miyazawa FK, Wakabayashi Y, Xavier EC (2008) Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation. Eur J Oper Res 191:61–85
Coffman EG, Garey MR, Johnson DS, Tarjan RE (1980) Performance bounds for level-oriented two-dimensional packing algorithms. SIAM J Comput 9:808–826
Coffman EG, Shor PW (1990) Average-case analysis of cutting and packing in two dimensions. Eur J Oper Res 44:134–144
Côté J-F, Dell’Amico M, Iori M (2014) Combinatorial benders’ cuts for the strip packing problem. Oper Res 62:643–661
Cui Y, Zhao Z (2013) Heuristic for the rectangular two-dimensional single stock size cutting stock problem with two-staged patterns. Eur J Oper Res 231:288–298
Cui Y-P, Cui Y, Tang T (2015) Sequential heuristic for the two-dimensional bin-packing problem. Eur J Oper Res 240:43–53
He K, Jin Y, Huang W (2013) Heuristics for two-dimensional strip packing problem with 90 degrees rotations. Expert Syst Appl 40:5542–5550
Lodi A, Martello S, Vigo D (1999) Heuristics and meta-heuristic approaches for a class of two-dimensional bin packing problems. INFORMS J Comput 11:345–357
Lodi A, Martello S, Vigo D (2004) Models and bounds for two-dimensional level packing problems. J Comb Optim 8:363–379
Mrad M (2015) An arc flow-based optimization approach for the two-stage guillotine strip packing problem. J Oper Res Soc 66:1850–1859
Ntene N, van Vuuren JH (2009) A survey and comparison of guillotine heuristics for the 2D oriented offline strip packing problem. Discret Optim 6:174–188
Silva E, Alvelos F, Valério de Carvalho JM (2010) An integer programming model for two- and three-stage two-dimensional cutting stock problems. Eur J Oper Res 205:699–708
Wei L, Oon W-C, Zhu W, Lim A (2013) A goal-driven approach to the 2D bin packing and variable-sized bin packing problems. Eur J Oper Res 224:110–121
Wei L, Qin Hu, Cheang B, Xu X (2016) An efficient intelligent search algorithm for the two-dimensional rectangular strip packing problem. Int Trans Oper Res 23:65–92
Wäscher G, Haussner H, Schumann H (2007) An improved typology of cutting and packing problems. Eur J Oper Res 183:1109–1130
Acknowledgments
This research is part of Projects 71371058 and 61363026 supported by National Natural Science Foundation of China.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Cui, YP., Zhou, Y. & Cui, Y. Triple-solution approach for the strip packing problem with two-staged patterns. J Comb Optim 34, 588–604 (2017). https://doi.org/10.1007/s10878-016-0088-7
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-016-0088-7