|
|
Chair of Business Administration and Decision Analysis Friedrich-Schiller-University 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 one-dimensional bin packing problem (BPP-1,
cf. Martello and Toth, 1990). It is to pack a given set of items having
different sizes into a minimum number of equal-sized bins. Even though
this problem seems to be rather simple it is NP-hard, 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 BPP-1 (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 BPP-1 to BPP-2 (minimize the size of the bins given their number) through
the so-called 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 well-known procedure MTP of Martello and Toth (1990).
Test data
We present benchmark data sets for BPP-1 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 one-dimensional bin packing problem. Computers & Operations Research 24 (1997) 627-645.
|