Article ID: | iaor201111571 |
Volume: | 36 |
Issue: | 4 |
Start Page Number: | 743 |
End Page Number: | 753 |
Publication Date: | Nov 2011 |
Journal: | Mathematics of Operations Research |
Authors: | Jansen Klaus, Solis-Oba Roberto |
Keywords: | bin packing |
In the cutting stock problem, we are given a set of objects of different types, and the goal is to pack them all in the minimum possible number of identical bins. All objects have integer lengths, and objects of different types have different sizes. The total length of the objects packed in a bin cannot exceed the capacity of the bin. In this paper, we consider the version of the problem in which the number of different object types is constant, and we present a polynomial‐time algorithm that computes a solution using at most one more bin than an optimum solution.