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.)

Robust mixed-integer linear programming models for the irregular strip packing problem

Texto completo
Autor(es):
Cherri, Luiz H. [1] ; Mundim, Leandro R. [1] ; Andretta, Marina [1] ; Toledo, Franklina M. B. [1] ; Oliveira, Jose F. [2] ; Carravilla, Maria Antonia [2]
Número total de Autores: 6
Afiliação do(s) autor(es):
[1] Univ Sao Paulo, Ave Trabalhador Sao Carlense 400, BR-13566590 Sao Carlos, SP - Brazil
[2] Univ Porto, Fac Ingn, INESC TEC, Rua Dr Roberto Frias, P-4200465 Oporto - Portugal
Número total de Afiliações: 2
Tipo de documento: Artigo Científico
Fonte: European Journal of Operational Research; v. 253, n. 3, p. 570-583, SEP 16 2016.
Citações Web of Science: 14
Resumo

Two-dimensional irregular strip packing problems are cutting and packing problems where small pieces have to be cut from a larger object, involving a non-trivial handling of geometry. Increasingly sophisticated and complex heuristic approaches have been developed to address these problems but, despite the apparently good quality of the solutions, there is no guarantee of optimality. Therefore, mixed-integer linear programming (MIP) models started to be developed. However, these models are heavily limited by the complexity of the geometry handling algorithms needed for the piece non-overlapping constraints. This led to pieces simplifications to specialize the developed mathematical models. In this paper, to overcome these limitations, two robust MIP models are proposed. In the first model (DTM) the non-overlapping constraints are stated based on direct trigonometry, while in the second model (NFP - CM) pieces are first decomposed into convex parts and then the non-overlapping constraints are written based on nofit polygons of the convex parts. Both approaches are robust in terms of the type of geometries they can address, considering any kind of non-convex polygon with or without holes. They are also simpler to implement than previous models. This simplicity allowed to consider, for the first time, a variant of the models that deals with piece rotations. Computational experiments with benchmark instances show that NFP CM outperforms both DTM and the best exact model published in the literature. New real-world based instances with more complex geometries are proposed and used to verify the robustness of the new models. (C) 2016 Elsevier B.V. All rights reserved. (AU)

Processo FAPESP: 10/10133-0 - Problemas de corte, empacotamento, dimensionamento de lotes e programação da produção, e suas integrações em contextos industriais e logísticos
Beneficiário:Reinaldo Morabito Neto
Linha de fomento: Auxílio à Pesquisa - Temático
Processo FAPESP: 12/18653-8 - O problema de corte de peças irregulares
Beneficiário:Luiz Henrique Cherri
Linha de fomento: Bolsas no Brasil - Doutorado
Processo FAPESP: 14/10740-4 - O problema de corte de peças irregulares
Beneficiário:Luiz Henrique Cherri
Linha de fomento: Bolsas no Exterior - Estágio de Pesquisa - Doutorado
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