×

Triple-solution approach for the strip packing problem with two-staged patterns. (English) Zbl 1381.90070

Summary: 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.

MSC:

90C27 Combinatorial optimization
Full Text: DOI

References:

[1] Alvarez-Valdes R, Parreño F, Tamarit JM (2008) Reactive GRASP for the strip-packing problem. Comput Oper Res 35:1065-1083 · Zbl 1179.90269 · doi:10.1016/j.cor.2006.07.004
[2] Alvarez-Valdes R, Parreño F, Tamarit JM (2009) A branch and bound algorithm for the strip packing problem. OR Spectr 31:431-459 · Zbl 1160.90696 · doi:10.1007/s00291-008-0128-5
[3] 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 · Zbl 1168.90577 · doi:10.1007/s10288-007-0051-7
[4] Bortfeldt A (2006) A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces. Eur J Oper Res 172:814-837 · Zbl 1111.90094 · doi:10.1016/j.ejor.2004.11.016
[5] 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 · Zbl 1146.90499
[6] Coffman EG, Garey MR, Johnson DS, Tarjan RE (1980) Performance bounds for level-oriented two-dimensional packing algorithms. SIAM J Comput 9:808-826 · Zbl 0447.68079 · doi:10.1137/0209062
[7] Coffman EG, Shor PW (1990) Average-case analysis of cutting and packing in two dimensions. Eur J Oper Res 44:134-144 · Zbl 0689.90059 · doi:10.1016/0377-2217(90)90349-G
[8] Côté J-F, Dell’Amico M, Iori M (2014) Combinatorial benders’ cuts for the strip packing problem. Oper Res 62:643-661 · Zbl 1302.90173 · doi:10.1287/opre.2013.1248
[9] 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 · Zbl 1317.90326 · doi:10.1016/j.ejor.2013.05.042
[10] Cui Y-P, Cui Y, Tang T (2015) Sequential heuristic for the two-dimensional bin-packing problem. Eur J Oper Res 240:43-53 · Zbl 1339.90278 · doi:10.1016/j.ejor.2014.06.032
[11] He K, Jin Y, Huang W (2013) Heuristics for two-dimensional strip packing problem with 90 degrees rotations. Expert Syst Appl 40:5542-5550 · doi:10.1016/j.eswa.2013.04.005
[12] 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 · Zbl 1034.90500 · doi:10.1287/ijoc.11.4.345
[13] Lodi A, Martello S, Vigo D (2004) Models and bounds for two-dimensional level packing problems. J Comb Optim 8:363-379 · Zbl 1084.90031 · doi:10.1023/B:JOCO.0000038915.62826.79
[14] Mrad M (2015) An arc flow-based optimization approach for the two-stage guillotine strip packing problem. J Oper Res Soc 66:1850-1859 · doi:10.1057/jors.2015.8
[15] 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 · Zbl 1159.90527 · doi:10.1016/j.disopt.2008.11.002
[16] 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 · Zbl 1188.90181 · doi:10.1016/j.ejor.2010.01.039
[17] 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 · Zbl 1292.90174 · doi:10.1016/j.ejor.2012.08.005
[18] 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 · Zbl 1338.90357 · doi:10.1111/itor.12138
[19] Wäscher G, Haussner H, Schumann H (2007) An improved typology of cutting and packing problems. Eur J Oper Res 183:1109-1130 · Zbl 1278.90347
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.