BISON - A FAST HYBRID PROCEDURE FOR EXACTLY SOLVING THE ONE-DIMENSIONAL BIN PACKING PROBLEM

In this paper, we consider the well-known one-dimensional bin packing problem (BPP-1), which is to pack a given set of items having differen t sizes into a minimum number of equal-sized bins. For solving BPP-1, an exact hybrid solution procedure, called BISON, is proposed. It favo urably combines the well-known meta-strategy tabu search and a branch and bound procedure based on known and new bound arguments and a new b ranching scheme. Computational results indicate that BISON is very eff ective and outperforms existing approaches. (C) 1997 Elsevier Science Ltd.