Advanced search
Start date
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

A general heuristic for two-dimensional nesting problems with limited-size containers

Full text
Mundim, Leandro R. [1] ; Andretta, Marina [1] ; Carravilla, Maria Antonia [2] ; Oliveira, Jose Fernando [2]
Total Authors: 4
[1] Univ Sao Paulo, Inst Ciencias Matemat & Comp, Sao Carlos, SP - Brazil
[2] Univ Porto, INESC TEC, Fac Engn, Porto - Portugal
Total Affiliations: 2
Document type: Journal article
Source: INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH; v. 56, n. 1-2, SI, p. 709-732, 2018.
Web of Science Citations: 3

Cutting raw-material into smaller parts is a fundamental phase of many production processes. These operations originate raw-material waste that can be minimised. These problems have a strong economic and ecological impact and their proper solving is essential to many sectors of the economy, such as the textile, footwear, automotive and shipbuilding industries, to mention only a few. Two-dimensional (2D) nesting problems, in particular, deal with the cutting of irregularly shaped pieces from a set of larger containers, so that either the waste is minimised or the value of the pieces actually cut from the containers is maximised. Despite the real-world practical relevance of these problems, very few approaches have been proposed capable of dealing with concrete characteristics that arise in practice. In this paper, we propose a new general heuristic (H4NP) for all 2D nesting problems with limited-size containers: the Placement problem, the Knapsack problem, the Cutting Stock problem, and the Bin Packing problem. Extensive computational experiments were run on a total of 1100 instances. H4NP obtained equal or better solutions for 73% of the instances for which there were previous results against which to compare, and new benchmarks are proposed. (AU)

FAPESP's process: 13/07375-0 - CeMEAI - Center for Mathematical Sciences Applied to Industry
Grantee:José Alberto Cuminato
Support type: Research Grants - Research, Innovation and Dissemination Centers - RIDC
FAPESP's process: 16/01860-1 - Cutting, packing, lot-sizing, scheduling, routing and location problems and their integration in industrial and logistics settings
Grantee:Reinaldo Morabito Neto
Support type: Research Projects - Thematic Grants