Setup and Open Stacks Minimization
in One-Dimensional Stock Cutting
Authors: G. Belov, G. Scheithauer
INFORMS J. on Computing 19/1 (2007) 27-35
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. Probably the most complex auxiliary criteria of a
solution are the number of different cutting patterns (setups) and
the maximum number of open stacks during the cutting process.
There are applications where the number of stacks is restricted to
two. We design a sequential heuristic to minimize material input
while restricting the number of open stacks to any given limit.
Then, the heuristic is simplified and integrated into a setup
minimization approach in order to combine setup and open stacks
minimization. To get a smaller number of open stacks, we may split
up the problem into several parts of smaller dimension. Different
solutions are evaluated in relation to the multiple objectives
using the Pareto criterion. Finally we extend some known
models by boolean variables that account for the states of stacks
in the cutting sequence.
(Preprint MATH-NM-16-2003, TU Dresden, Oct. 2003)