The number of Setups (Different Patterns)
in One-Dimensional Stock Cutting
Authors: G. Belov, G. Scheithauer
Preprint MATH-NM-15-2003, TU Dresden, October 2003.
The primary objective in cutting and packing problems is
trim loss or material input minimization (in stock cutting) or
value maximization (when packing into a knapsack). However, in
real-life production we usually have many other objectives (costs)
and constraints, for example, the number of different patterns. We
propose a new simple model for setup minimization (in fact, an
extension of the Gilmore-Gomory model for trim loss minimization)
and develop a branch-and-price algorithm on its basis. The
algorithm is tested on problems with industrially relevant sizes
of up to 150 product types. The behavior is investigated on a
broad range of problem classes and significant differences between
instances of a class are found. Allowing even 0.2 percent more material
input than the minimum significantly improves the results, this
tradeoff has not been investigated in the earlier literature.
Comparison to a state-of-the art heuristic KOMBI shows mostly
better results; to a previous exact approach of Vanderbeck,
slightly worse solutions and much worse LP bound, which is a
consequence of the simplicity of the model.