Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

A bottom-up packing approach for modeling the constrained two-dimensional guillotine placement problem

Texto completo
Autor(es):
Martin, Mateus [1] ; Morabito, Reinaldo [1] ; Munari, Pedro [1]
Número total de Autores: 3
Afiliação do(s) autor(es):
[1] Univ Fed Sao Carlos, Dept Prod Engn, Via Washington Luiz Km 235, BR-13565905 Sao Carlos, SP - Brazil
Número total de Afiliações: 1
Tipo de documento: Artigo Científico
Fonte: Computers & Operations Research; v. 115, MAR 2020.
Citações Web of Science: 0
Resumo

In this paper, we address the Constrained Two-dimensional Guillotine Placement Problem (C2GPP). This problem considers a rectangular large object and a set of rectangular small item types of given sizes and values. The objective is to select and cut the most valuable subset of small items from the large object using orthogonal guillotine cuts and constrained patterns. To completely model the problem, we present pseudo-polynomial and compact integer non-linear formulations. Then, we obtain an equivalent Mixed Integer Linear Programming (MILP) formulation from each non-linear model. These novel formulations are related to a bottom-up packing approach of successive horizontal and vertical builds of the small items. Additionally, we develop a set of constraints for each model which allows us to strictly consider d-staged guillotine cutting patterns, for a given positive integer d. To evaluate the MILP models and compare their performance to the state-of-the-art formulation of the C2GPP, we run computational experiments using three sets of benchmark instances, two of them from the literature. The results show that the proposed models, based on a bottom-up packing approach, lead to optimal or near-optimal solutions in reasonable processing times, even for scenarios that are intractable for the benchmark model. (C) 2019 Elsevier Ltd. All rights reserved. (AU)

Processo FAPESP: 13/07375-0 - CeMEAI - Centro de Ciências Matemáticas Aplicadas à Indústria
Beneficiário:José Alberto Cuminato
Linha de fomento: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs
Processo FAPESP: 16/08039-1 - Problemas de corte bidimensional guilhotinado e restrito: formulações matemáticas e métodos de solução
Beneficiário:Mateus Pereira Martin
Linha de fomento: Bolsas no Brasil - Doutorado
Processo FAPESP: 16/01860-1 - Problemas de corte, empacotamento, dimensionamento de lotes, programação da produção, roteamento, localização e suas integrações em contextos industriais e logísticos
Beneficiário:Reinaldo Morabito Neto
Linha de fomento: Auxílio à Pesquisa - Temático