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.


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


OR-Library; Bison
Full Text: DOI


[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)
[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
[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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.