Fast Pattern-based Algorithms for Cutting Stock

Brandão, F. and Pedroso, J. P. (2014). Fast pattern-based algorithms for cutting stock. Computers & Operations Research, 48(0):69–80.

Technical Report (PDF) (the final publication is available at http://dx.doi.org/10.1016/j.cor.2014.03.003)

Abstract

The conventional assignment-based first/best fit decreasing algorithms (FFD/BFD) are not polynomial in the 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.

BibTeX

@article{CSPHeuristics,
author = {Brand\~ao, Filipe and Pedroso, J. P.},
title = "Fast pattern-based algorithms for cutting stock",
journal = "Computers \& Operations Research",
volume = "48",
number = "0",
pages = "69 - 80",
year = "2014",
note = "",
issn = "0305-0548",
doi = "http://dx.doi.org/10.1016/j.cor.2014.03.003",
url = "http://www.sciencedirect.com/science/article/pii/S0305054814000525",
keywords = "Cutting stock",
keywords = "First fit decreasing",
keywords = "Best fit decreasing",
}