Heuristics for the variable sized bin-packing problem. (English) Zbl 1160.90634
Summary: We investigate the one-dimensional variable-sized bin-packing problem. This problem requires packing a set of items into a minimum-cost set of bins of unequal sizes and costs. Six optimization-based heuristics for this problem are presented and compared. We analyze their empirical performance on a large set of randomly generated test instances with up to 2000 items and seven bin types. The first contribution of this paper is to provide evidence that a set covering heuristic proves to be highly effective and capable of delivering very-high quality solutions within short CPU times. In addition, we found that a simple subset-sum problem-based heuristic consistently outperforms heuristics from the literature while requiring extremely short CPU times.
MSC:
| 90C27 | Combinatorial optimization |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Software:
KnapsackReferences:
| [1] | Friesen, D. K.; Langston, M. A., Variable sized bin packing, SIAM Journal on Computing, 15, 222-230 (1986) · Zbl 0589.68036 |
| [2] | Murgolo, F. D., An efficient approximation scheme for variable-sized bin packing, SIAM Journal on Computing, 16, 149-161 (1987) · Zbl 0618.90081 |
| [3] | Coffman, E. G.; Garey, M. R.; Johnson, D. S., Bin packing with divisible item sizes, Journal of Complexity, 3, 406-428 (1987) · Zbl 0641.68097 |
| [4] | Kang, J.; Park, J., Algorithms for the variable sized bin packing problem, European Journal of Operational Research, 147, 365-372 (2003) · Zbl 1031.90027 |
| [5] | Chu, C.; La, R., Variable-sized bin packing: tight absolute worst-case performance ratios for four approximation algorithms, SIAM Journal on Computing, 30, 2069-2083 (2001) · Zbl 0980.68056 |
| [6] | Monaci M. Algorithms for packing and scheduling problems, PhD thesis, University of Bologna, 2002.; Monaci M. Algorithms for packing and scheduling problems, PhD thesis, University of Bologna, 2002. · Zbl 1041.90529 |
| [7] | Belov, G.; Scheithauer, G., A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths, European Journal of Operational Research, 141, 274-294 (2002) · Zbl 1081.90590 |
| [8] | Alves, C.; Valério de Carvalho, J. M., Accelerating column generation for variable sized bin packing problems, European Journal of Operational Research, 183, 1333-1352 (2007) · Zbl 1135.90024 |
| [9] | Haouari M, Serairi M. Relaxations and exact solution of the variable sized bin packing problem. Computational Optimization and Applications, 2009, accepted.; Haouari M, Serairi M. Relaxations and exact solution of the variable sized bin packing problem. Computational Optimization and Applications, 2009, accepted. · Zbl 1160.90634 |
| [10] | Caprara, A.; Pferschy, U., Worst-case analysis of the subset sum algorithm for bin packing, Operations Research Letters, 32, 159-166 (2004) · Zbl 1060.90061 |
| [11] | Kellerer, H.; Pferschy, U.; Pisinger, D., Knapsack problems (2004), Springer: Springer Berlin · Zbl 1103.90003 |
| [12] | Caprara, A.; Pferschy, U., Modified subset sum heuristics for bin packing, Information Processing Letters, 96, 18-23 (2005) · Zbl 1184.68661 |
| [13] | Cullen, F.; Jarvis, J.; Ratliff, D., Set partitioning based heuristics for interactive routing, Networks, 11, 125-144 (1981) |
| [14] | Kelly, J. P.; Xu, J., A set-partitioning-based heuristic for the vehicle routing problem, INFORMS Journal on Computing, 11, 161-172 (1999) · Zbl 1092.90503 |
| [15] | Marsten, R.; Shepardson, F., Exact solution of crew scheduling problems using the set partitioning model: recent successful applications, Networks, 112, 167-177 (1981) |
| [16] | Wedelin, D., An algorithm for large scale 0-1 integer programming with application to airline crew scheduling, Annals of Operations Research, 57, 283-301 (1995) · Zbl 0831.90087 |
| [17] | Caprara, A.; Fischetti, M.; Toth, P.; Vigo, D.; Guida, P. L., Algorithms for railway crew management, Mathematical Programming, 79, 125-141 (1997) · Zbl 0887.90056 |
| [18] | Monaci, M.; Toth, P., A set-covering-based heuristic approach for bin packing Problems, INFORMS Journal on Computing, 18, 71-85 (2006) · Zbl 1241.90191 |
| [19] | Beasley, J. E.; Chu, P. C., A genetic algorithm for the set covering problem, European Journal of Operational Research, 94, 392-404 (1996) · Zbl 0953.90565 |
| [20] | Ceria, S.; Nobili, P.; Sassano, A., A Lagrangian-based heuristic for large-scale set covering problems, Mathematical Programming, 81, 215-228 (1998) · Zbl 0919.90085 |
| [21] | Caprara, A.; Fischetti, M.; Toth, P., A heuristic method for the set covering problem, Operations Research, 47, 730-743 (1999) · Zbl 0976.90086 |
| [22] | Haouari, M.; Chaouachi, J., A probabilistic greedy search algorithm for combinatorial optimisation with application to the set covering problem, Journal of Operational Research Society, 53, 792-799 (2002) · Zbl 1130.90389 |
| [23] | Jakobs, S., On genetic algorithms for the packing of polygons, European Journal of Operational Research, 88, 165-181 (1996) · Zbl 0913.90229 |
| [24] | Hopper, E.; Turton, B., A genetic algorithm for a 2D industrial packing problem, Computers and Industrial Engineering, 37, 375-378 (1999) |
| [25] | Zhang, D. F.; Chen, S. D.; Liu, Y. J., An improved heuristic recursive strategy based on genetic algorithm for the strip rectangular packing problem, Acta Automatica Sinica, 33, 911-916 (2007) · Zbl 1164.90430 |
| [26] | Falkenauer, E., A hybrid grouping genetic algorithm for bin packing, Journal of Heuristics, 2, 5-30 (1996) |
| [27] | Lima H, Yakawa T. A new design of genetic algorithm for bin packing, In: Evolutionary computation, 2003. CEC ’03. The 2003 Congress on Evolutionary Computation, vol. 2, pp. 1044-9.; Lima H, Yakawa T. A new design of genetic algorithm for bin packing, In: Evolutionary computation, 2003. CEC ’03. The 2003 Congress on Evolutionary Computation, vol. 2, pp. 1044-9. |
| [28] | Ruiz, R.; Maroto, C.; Alcaraz, J., Two new robust genetic algorithms for the flowshop scheduling problem, Omega, 34, 461-476 (2006) |
| [29] | Pisinger, D.; Sigurd, M., The two-dimensional bin packing problem with variable bin sizes and costs, Discrete Optimization, 2, 154-167 (2005) · Zbl 1077.90057 |
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.
