An Opt + 1 algorithm for the cutting stock problem with a constant number of object lengths

In the cutting stock problem we are given a set $T=T_1,T_2, \ldots, T_d$ of object types, where objects of type $T_i$ have integer length $p_i > 0$. Given a set $\mathcal{O}$ of $n$ objects containing $n_i$ objects of type $T_i$, for each $i = 1, \ldots, d$, the problem is to pack $\mathcal{O}$ into the minimum number of bins of capacity $\beta$. 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.

Logo BII


Use and reproduction:

No license. The provisions of the German Copyright Act (UrhG) apply.

Please note that individual components of the publication may be subject to other licensing or copyright conditions.


Citation style:
Could not load citation form.