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

Fleszar, Krzysztof; Hindi, Khalil S.

Comput. Oper. Res. 29, No. 7, 821-839 (2002).

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

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)
[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)