Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
475152 | Computers & Operations Research | 2014 | 12 Pages |
•New data structures for the cutting stock problem.•Pattern-based versions of FFD/BFD heuristics.•Polynomial FFD/BFD on the cutting stock input size.
The conventional assignment-based first/best fit decreasing algorithms (FFD/BFD) are not polynomial in the one-dimensional cutting stock input size in its most common format. Therefore, even for small instances with large demands, it is difficult to compute FFD/BFD solutions. We present pattern-based methods that overcome the main problems of conventional heuristics in cutting stock problems by representing the solution in a much more compact format. Using our pattern-based heuristics, FFD/BFD solutions for extremely large cutting stock instances, with billions of items, can be found in a very short amount of time.