2010 | OriginalPaper | Chapter
An OPT + 1 Algorithm for the Cutting Stock Problem with Constant Number of Object Lengths
Authors : Klaus Jansen, Roberto Solis-Oba
Published in: Integer Programming and Combinatorial Optimization
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.