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

BII

Zitieren

Zitierform:
Zitierform konnte nicht geladen werden.

Rechte

Nutzung und Vervielfältigung:Keine Creative-Commons-Lizenz - Es gelten die Bestimmungen des deutschen Urheberrechts (UrhG)Bitte beachten Sie, dass einzelne Bestandteile der Publikation anderweitigen Lizenz- bzw. urheberrechtlichen Bedingungen unterliegen können.