An OPT + 1 Algorithm for the Cutting Stock Problem with Constant Number of Object Lengths

摘要

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.