

Chair of Business Administration and Decision Analysis FriedrichSchillerUniversity Jena  Chair of Operations Research Darmstadt University of Technology 
Problem description
Packing of items into boxes or bins is a recurring task in
distribution and production. Concerning the size and shape of items as well
as the form and capacity of bins a large variety of different packing problems
can be distinguished. Similar problems concern cutting of pieces into
particular smaller ones so as to minimize the wastage
of material and scheduling of identical parallel processors so as to
minimize the total completion time. We consider a basic packing problem
which is known as the onedimensional bin packing problem (BPP1,
cf. Martello and Toth, 1990). It is to pack a given set of items having
different sizes into a minimum number of equalsized bins. Even though
this problem seems to be rather simple it is NPhard, i.e., no
procedure is able to solve each problem instance in polynomial time.
In order to solve more general (and more complex) realistic problems
within reasonable computation time it is important to have on hand
effective procedures for the basic problem.
Solution procedures
We propose an exact hybrid solution procedure for BPP1 (called BISON) which
combines the successful heuristic meta strategy tabu search and a
branch and bound procedure. The tabu search procedure utilizes the relationship
of BPP1 to BPP2 (minimize the size of the bins given their number) through
the socalled dual strategy. The branch and bound procedure is based on a
clever branching scheme called local lower bound method.
Computational results indicate that BISON is very effective and outperforms
the wellknown procedure MTP of Martello and Toth (1990).
Test data
We present benchmark data sets for BPP1 which may be used to test and compare
solution procedures. The first data set (720 instances) is constructed similar to that used by
Martello and Toth (1990) for testing their procedure MTP. The second data set
(480 instances) contains parameter settings not covered by the first set, while the third set
contains 10 hard instances.
You may find information on the data sets and download the data of all
problem instances (defined through the number of items, the bin capacity,
and the weights of all items (in decreasing order) by choosing the
following links:
References:
 S. Martello and P. Toth, Knapsack problems. Wiley, Chichester (1990).
 A. Scholl, R. Klein, and C. Jürgens: BISON: a fast hybrid
procedure for exactly solving the onedimensional bin packing problem. Computers & Operations Research 24 (1997) 627645.
