×

Efficient algorithms for the offline variable sized bin-packing problem. (English) Zbl 1286.90132

Summary: We addresses a variant of the classical one-dimensional bin-packing problem where several types of bins with unequal sizes and costs are presented. Each bin-type includes limited and/or unlimited identical bins. The goal is to minimize the total cost of bins needed to store a given set of items, each item with some space requirements. Four new heuristics to solve this problem are proposed, developed and compared. The experiments results show that higher quality solutions can be obtained using the proposed algorithms.

MSC:

90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming

Software:

Bison
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Basnet C., Wilson J.: Heuristics for determining the number of warehouses for storing non-compatible products. Int. Trans. Oper. Res. 12, 527-538 (2005) · Zbl 1202.90005 · doi:10.1111/j.1475-3995.2005.00523.x
[2] Belov G., Scheithauer G.: A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths. Eur. J. Oper. Res. 141, 274-294 (2002) · Zbl 1081.90590 · doi:10.1016/S0377-2217(02)00125-X
[3] Blum C., Hemmelmayr V., Hernndez H., Schmid V.: Hybrid algorithms for the variable sized bin packing problem. Lect. Notes Comput. Sci. 30, 2069-2083 (2001). doi:10.1007/978-3-642-16054-7_2 · Zbl 0980.68056 · doi:10.1007/978-3-642-16054-7_2
[4] Chu C., La R.: Variable-sized bin packing: tight absolute worst-case performance ratios for four approximation algorithms. SIAM J. Comput. 30, 2069-2083 (2001) · Zbl 0980.68056 · doi:10.1137/S009753979834669X
[5] Coffmann J.E.G., Garey M.R., Johnson D.S.: Approximation Algorithms for NP-hard Problems: Approximation Algorithms for Bin-packing—A Survey, pp. 46-93. PWS Publishing, Boston (1997)
[6] Correia I., Gouveia L., Saldanha-Da-Gama F.: Solving the variable size bin-packing problem with discretized formulations. Comput. Oper. Res. 35, 2103-2113 (2008) · Zbl 1139.90025 · doi:10.1016/j.cor.2006.10.014
[7] Crainic T.G., Perboli G., Rei W., Tadei R.: Efficient lower bounds and heuristics for the variable cost and size bin packing problem. Comput. Oper. Res. 38(11), 1474-1482 (2011) · doi:10.1016/j.cor.2011.01.001
[8] Eilon S., Christofides N.: The loading problem. Manag. Sci. 17, 259-268 (1971) · Zbl 0224.90028 · doi:10.1287/mnsc.17.5.259
[9] Epstein, L., Favrholdt, L.M.: On-line maximizing the number of items packed in variable-sized bins. In: Ibarra, O.H., Zhang, L. (eds.) Lecture Notes in Computer Science vol. 2387, pp. 467-475. COCOON 2002, Springer, Berlin (2002) · Zbl 1077.68825
[10] Falkenauer E.: A hybrid grouping genetic algorithm. J. Heuristics 2, 5-30 (1996) · doi:10.1007/BF00226291
[11] Fleszar K., Hindi K.S.: New heuristics for one-dimensional bin-packing. Comput. Oper. Res. 29, 821-839 (2002) · Zbl 0994.90134 · doi:10.1016/S0305-0548(00)00082-4
[12] Friesen D.K., Langston M.A.: Variable sized bin-packing. SIAM J. Comput. 15, 222-230 (1986) · Zbl 0589.68036 · doi:10.1137/0215016
[13] Garey M.R., Johnson D.S.: Computers and Intratability: A Guide to the Theory of NP-completeness. Freeman, San Francisco (1979) · Zbl 0411.68039
[14] Gupta J.N.D., Ho J.C.: A new heuristic algorithm for the one-dimensional bin-packing problem. Prod. Plan. Control 10(6), 598-603 (1999) · doi:10.1080/095372899232894
[15] Haouari M., Serairi M.: Heuristics for the variable sized bin-packing problem. Comput. Oper. Res. 36(10), 2877-2884 (2009) · Zbl 1160.90634 · doi:10.1016/j.cor.2008.12.016
[16] Haouari M., Serairi M.: Relaxations and exact solution of the variable sized bin packing problem. Comput. Optim. Appl. 48, 345-368 (2011) · Zbl 1219.90141 · doi:10.1007/s10589-009-9276-z
[17] Hifi M., MHallah R., Saadi T.: Algorithms for constrained two-staged two-dimensional cutting problems. INFORMS J. Comput. 20, 212-221 (2008) · Zbl 1243.90137 · doi:10.1287/ijoc.1070.0233
[18] Johnson D.S., Demers A., Ullman J.D., Garey M.R., Graham R.L.: Worst-case performance bound for simple one dimensional packing algorithms. SIAM J. comput. 3(4), 299-325 (1974) · Zbl 0297.68028 · doi:10.1137/0203025
[19] Kang J., Park S.: Algorithms for the variable sized bin-packing problem. Eur. J. Oper. Res. 147, 365-372 (2003) · Zbl 1031.90027 · doi:10.1016/S0377-2217(02)00247-3
[20] Monaci, M.: Algorithms for packing and scheduling problems. Phd thesis or/02/4, Universit di Bologna (2002) · Zbl 1041.90529
[21] Murgolo F.D.: An efficient approximation scheme for variable-sized bin-packing. SIAM J. Comput. 16(1), 149-161 (1987) · Zbl 0618.90081 · doi:10.1137/0216012
[22] Ow P.S., Morton T.E.: Filtered beam search in scheduling. Int. J. Prod. Res. 26, 35-62 (1988) · doi:10.1080/00207548808947840
[23] Righini G., Bettinelli A., Ceselli A.: A branch-and-price algorithm for the variable size bin-packing problem with minimum filling constraint. Ann. Oper. Res. 179(1), 221-241 (2010) · Zbl 1201.90168 · doi:10.1007/s10479-008-0452-9
[24] Scholl A., Klein R., Bison J.C.: A fast hybrid procedure for exactly solving the one-dimensional bin-packing problem. Comput. Oper. Res. 24(7), 627-645 (1997) · Zbl 0882.90113 · doi:10.1016/S0305-0548(96)00082-2
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.