×

New heuristics for one-dimensional bin-packing. (English) Zbl 0994.90134

Summary: Several new heuristics for solving the one-dimensional bin packing problem are presented. Some of these are based on the minimal bin slack heuristic of Gupta and Ho. A different algorithm is one based on the variable neighbourhood search metaheuristic. The most effective algorithm turned out to be one based on running one of the former to provide an initial solution for the latter. When tested on 1370 benchmark test problem instances from two sources, this last hybrid algorithm proved capable of achieving the optimal solution for 1329, and could find for 4 instances solutions better than the best known. This is remarkable performance when set against other methods, both heuristic and optimum seeking.

MSC:

90C35 Programming involving graphs or networks
90C59 Approximation methods and heuristics in mathematical programming

Software:

OR-Library; Bison
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Garey, M. R.; Johnson, D. S., Computers and intractability: a guide to the theory of NP-completeness (1979), W.H. Freeman: W.H. Freeman San Francisco · Zbl 0411.68039
[2] Scholl, A.; Klein, R.; Jürgens, C., BISON: a fast hybrid procedure for exactly solving the one-dimensional bin packing problem, Computers & Operations Research, 24, 7, 627-645 (1997) · Zbl 0882.90113
[3] 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
[4] Gupta, J. N.D.; Ho, J. C., A new heuristic algorithm for the one-dimensional bin-packing problem, Production Planning & Control, 10, 6, 598-603 (1999)
[5] Fekete SP, Schepers J. New classes of lower bounds for bin packing problems, Lecture Notes in Computer Science, vol. 1412. Berlin: Springer, 1998. p. 257-70.; Fekete SP, Schepers J. New classes of lower bounds for bin packing problems, Lecture Notes in Computer Science, vol. 1412. Berlin: Springer, 1998. p. 257-70. · Zbl 0910.90222
[6] Hoffmann, T. R., Assembly line balancing with a precedence matrix, Management Science, 9, 551-562 (1963)
[7] Martello, S.; Toth, P., Knapsack problems (1990), Wiley: Wiley New York · Zbl 0452.90047
[8] Kolisch R, Hartmann S. Heuristic algorithms for the resource-constrainted project scheduling problem: classification and computational analysis. In: Wȩglarz J editor. Project scheduling: recent models, algorithms and applications. Dordrecht: Kluwer, 1999.; Kolisch R, Hartmann S. Heuristic algorithms for the resource-constrainted project scheduling problem: classification and computational analysis. In: Wȩglarz J editor. Project scheduling: recent models, algorithms and applications. Dordrecht: Kluwer, 1999.
[9] Hansen P, Mladenović N. An introduction to variable neighbourhood search. In: S. Voss et al., editors. Metaheuristics, advances and trends in local search paradigms for optimization. Dordrecht: Kluwer, 1999. p. 433-58.; Hansen P, Mladenović N. An introduction to variable neighbourhood search. In: S. Voss et al., editors. Metaheuristics, advances and trends in local search paradigms for optimization. Dordrecht: Kluwer, 1999. p. 433-58.
[10] Mladenović, N.; Hansen, P., Variable neighbourhood search, Computers & Operations Research, 24, 11, 1097-1100 (1997) · Zbl 0889.90119
[11] Beasley, J. E., OR-library: distributing test problems by electronic mail, Journal of the Operational Research Society, 41, 11, 1069-1107 (1990)
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.