Fast pattern-based algorithms for cutting stock

• Type: Article in International Scientific Journal
• Date: 2014

Authors

Filipe Brandao (Author) Other; Joao Pedro Pedroso (Author) FCUP

Journal

The Journal is awaiting validation by the Administrative Services.

Title: COMPUTERS & OPERATIONS RESEARCH

Vol. 48

Pages: 69-80

ISSN: 0305-0548

Indexing

ISI Web of Knowledge - 5 Citations

Scopus - 6 Citations

Scientific classification

FOS: Engineering and technology > Civil engineering

Other information

Authenticus ID: P-009-BXK

DOI: 10.1016/j.cor.2014.03.003

Abstract (EN): 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 12