ILP models for the skiving stock problem

Abstract

We consider the one-dimensional skiving stock problem which is also known as the dual bin packing problem: find the maximum number of items with minimum length $L$ that can be constructed by connecting a given supply of $m \in N$ smaller item lengths $l_1,\ldots,l_m$ with availabilities $b_1,\ldots, b_m$. For this optimization problem, we present three new models and investigate their relationships, especially regarding their respective continuous relaxations. To this end, numerical computations are provided. As a main result, we prove the equivalence between two of these approaches and the existing pattern-oriented standard model. In particular, this equivalence is shown to hold for the corresponding continuous relaxations, too.

PDF, (Preprint MATH-NM-05-2014, TU Dresden, December 2014)

Back