Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
An OPT + 1 Algorithm for the Cutting Stock Problem with Constant Number of Object Lengths
verfasst von : Klaus Jansen, Roberto Solis-Oba
Erschienen in: Integer Programming and Combinatorial Optimization
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In the
cutting stock problem
we are given a set
T
of object types, where objects of type
T
i
∈
T
have integer length
p
i
> 0. Given a set
O
of
n
objects containing
n
i
objects of type
T
i
, for each
i
= 1, ...,
d
, the problem is to pack
O
into the minimum number of bins of capacity
β
. In this paper we consider the version of the problem in which the number
d
of different object types is constant and we present an algorithm that computes a solution using at most
OPT
+ 1 bins, where
OPT
is the value of an optimum solution.