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"
}