×

Average-weight-controlled bin-oriented heuristics for the one-dimensional bin-packing problem. (English) Zbl 1219.90140

Summary: Bin-oriented heuristics for one-dimensional bin-packing problem construct solutions by packing one bin at a time. Several such heuristics consider two or more subsets for each bin and pack the one with the largest total weight. These heuristics sometimes generate poor solutions, due to a tendency to use many small items early in the process. To address this problem, we propose a method of controlling the average weight of items packed by bin-oriented heuristics. Constructive heuristics and an improvement heuristic based on this approach are introduced. Additionally, reduction methods for bin-oriented heuristics are presented. The results of an extensive computational study show that: (1) controlling average weight significantly improves solutions and reduces computation time of bin-oriented heuristics; (2) reduction methods improve solutions and processing times of some bin-oriented heuristics; and (3) the new improvement heuristic outperforms all other known complex heuristics, in terms of both average solution quality and computation time.

MSC:

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

Software:

Bison
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alvim, A. C.F.; Ribeiro, C. C.; Glover, F.; Aloise, D. J., A hybrid improvement heuristic for the one-dimensional bin packing problem, Journal of Heuristics, 10, 2, 205-229 (2004)
[2] Belov, G.; Scheithauer, G., A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting, European Journal of Operational Research, 171, 1, 85-106 (2006) · Zbl 1091.90080
[3] Bhatia, A. K.; Basu, S. K., Packing bins using multi-chromosomal genetic representation and better fit heuristic, Lecture Notes in Computer Science, 3316, 181-186 (2004)
[4] Caprara, A.; Pferschy, U., Worst-case analysis of the subset sum algorithm for bin packing, Operations Research Letters, 32, 2, 159-166 (2004) · Zbl 1060.90061
[5] Caprara, A.; Pferschy, U., Modified subset sum heuristics for bin packing, Information Processing Letters, 96, 1, 18-23 (2005) · Zbl 1184.68661
[6] Coffman, E. G.; Garey, M. R.; Johnson, D. S., Approximation algorithm for bin packing: A survey, (Hochbaum, D., Approximation Algorithm for NP-hard Problems (1997), PWS Publishing), 46-93
[7] Crainic, T.; Perboli, G.; Pezzuto, M.; Tadei, R., Computing the asymptotic worst-case of bin packing lower bounds, European Journal of Operational Research, 183, 3, 1295-1303 (2007) · Zbl 1135.90027
[8] Crainic, T.; Perboli, G.; Pezzuto, M.; Tadei, R., New bin packing fast lower bounds, Computers and Operations Research, 34, 11, 3439-3457 (2007) · Zbl 1127.90055
[9] Falkenauer, E., A hybrid grouping genetic algorithm for bin packing, Journal of Heuristics, 2, 1, 5-30 (1996)
[10] Fekete, S.; Schepers, J., New classes of fast lower bounds for bin packing problems, Mathematical Programming, 91, 1, 11-31 (2001) · Zbl 1051.90020
[11] Fleszar, K.; Hindi, K. S., New heuristics for one-dimensional bin-packing, Computers and Operations Research, 29, 7, 821-839 (2002) · Zbl 0994.90134
[12] Friesen, D.; Langston, M., Analysis of a compound bin packing algorithm, SIAM Journal on Discrete Mathematics, 4, 61 (1991) · Zbl 0714.68033
[13] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman · Zbl 0411.68039
[14] Gupta, J. N.D.; Ho, J. C., A new heuristic algorithm for the one-dimensional bin-packing problem, Production Planning and Control, 10, 6, 598-603 (1999)
[15] Johnson, D.; Demers, A.; Ullman, J.; Garey, M.; Graham, R., Worst-case performance bounds for simple one-dimensional packing algorithms, SIAM Journal on Computing, 3, 4, 299-325 (1974) · Zbl 0297.68028
[16] Loh, K.-H.; Golden, B.; Wasil, E., Solving the one-dimensional bin packing problem with a weight annealing heuristic, Computers and Operations Research, 35, 7, 2283-2291 (2008) · Zbl 1177.90347
[17] Martello, S., Toth, P., 1990. Knapsack Problems. Wiley, available online on <http://www.or.deis.unibo.it/knapsack.html>; Martello, S., Toth, P., 1990. Knapsack Problems. Wiley, available online on <http://www.or.deis.unibo.it/knapsack.html>
[18] Poli, R., Woodward, J., Burke, E.K., 2007. A histogram-matching approach to the evolution of bin-packing strategies. In: IEEE Congress on Evolutionary Computation 2007 (CEC 2007), pp. 3500-3507.; Poli, R., Woodward, J., Burke, E.K., 2007. A histogram-matching approach to the evolution of bin-packing strategies. In: IEEE Congress on Evolutionary Computation 2007 (CEC 2007), pp. 3500-3507.
[19] Rohlfshagen, P.; Bullinaria, J., A genetic algorithm with exon shuffling crossover for hard bin packing problems, Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation, 1365-1371 (2007)
[20] Scholl, A.; Klein, R.; Jürgens, C., BISON: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem, Computers and Operations Research, 24, 7, 627-645 (1997) · Zbl 0882.90113
[21] Schwerin, P.; Wäscher, G., The bin-packing problem: A problem generator and some numerical experiments with FFD packing and MTP, International Transactions in Operational Research, 4, 5/6, 377-389 (1997) · Zbl 0906.90151
[22] Singh, A.; Gupta, A. K., Two heuristics for the one-dimensional bin-packing problem, OR Spectrum, 29, 4, 765-781 (2007) · Zbl 1168.90598
[23] Valério de Carvalho, J. M., Exact solution of bin-packing problems using column generation and branch-and-bound, Annals of Operations Research, 86, 629-659 (1999) · Zbl 0922.90113
[24] Valério de Carvalho, J. M., LP models for bin packing and cutting stock problems, European Journal of Operational Research, 141, 2, 253-273 (2002) · Zbl 1059.90095
[25] Vanderbeck, F., Computational study of a column generation algorithm for bin packing and cutting stock problems, Mathematical Programming, 86, 3, 565-594 (1999) · Zbl 0949.90066
[26] Wäscher, G.; Gau, T., Heuristics for the integer one-dimensional cutting stock problem: A computational study, OR Spectrum, 18, 3, 131-144 (1996) · Zbl 0853.90099
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.