Algoritmos híbridos para o problema de corte bidimensional

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorBarboza, Eduardo Uchoa-
Autor(es): dc.contributorPessoa, Artur Alves-
Autor(es): dc.contributorOchi, Luiz Satoru-
Autor(es): dc.contributorPaula Junior, Geraldo Galdino de-
Autor(es): dc.contributorMorabito Neto, Reinaldo-
Autor(es): dc.creatorVelasco, André Soares-
Data de aceite: dc.date.accessioned2024-07-11T18:08:45Z-
Data de disponibilização: dc.date.available2024-07-11T18:08:45Z-
Data de envio: dc.date.issued2018-09-24-
Data de envio: dc.date.issued2018-09-24-
Data de envio: dc.date.issued2017-03-
Fonte completa do material: dc.identifierhttps://app.uff.br/riuff/handle/1/7644-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/764456-
Descrição: dc.descriptionO presente trabalho tem como objetos de estudo dois tipos de Problemas de Corte e Empacotamento, conhecidos na literatura como Problema de Corte Bidimensional Guilhotinado Restrito (PCBGR) e Problema de Corte de Estoque Bidimensional Guilhotinado (PCEBG), ambos pertencendo à classe NP-difícil, nos casos com e sem rotação de itens. Esses problemas possuem grande aplicabilidade em diversos setores produtivos que consideram as ações de corte na transformação de materiais em produtos semiacabados ou finais, tais como: metal mecânico, moveleiro, rochas ornamentais, entre outros. Primeiramente, são apresentadas as contribuições para o PCBGR: o algoritmo RG2D, fundamentado no Reactive Greedy Randomized Adaptive Search Procedure (GRASP Reativo) e implementado a partir de melhorias feitas no algoritmo GRASP-2D (G2D), para tratar o problema em destaque; o algoritmo X, baseado em Programação Inteira e capaz de provadamente obter os pesos ótimos para a relaxação de espaço de estados da Programação Dinâmica proposta em (CHRISTOFIDES; HADJICONSTANTINOU, 1995); o algoritmo X2, proposto como uma generalização de X que usa pesos bidimensionais para obter limites ainda mais fortes; o algoritmo X2H que consiste na adaptação de X2 para transformá-lo em uma heurística primal; o método X2D, resultante da combinação desses quatro elementos, foi testado em um grande conjunto de instâncias e mostrou ser capaz de encontrar soluções com garantias de qualidade ou mesmo certificado de otimalidade nas variantes com e sem rotação dos itens. A seguir, tendo como objeto de estudo o PCEBG, as contribuições são: a proposta de um algoritmo híbrido que combina a técnica de Geração de Colunas com Programação Dinâmica e o novo algoritmo RG2D. Os resultados computacionais obtidos até o momento foram bastante positivos. Em todas as instâncias testadas as soluções encontradas nunca ficaram mais do que 1 unidade além do limite inferior dado pela Geração de Colunas-
Descrição: dc.descriptionThe present work addresses two types of Cutting and Packing Problems, known in the literature as Two-dimensional Guillotine Restricted Cutting Problem (TGRCP) and Twodimensional Guillotine Cutting Stock Problem (TGCSP), both in the NP-hard class, with and without item rotation. Those problems have applications in industry, where cutting operations are performed for transforming raw stocks into final or semi-final products, in sectors like metallurgy, furniture, glass, ornamental stones, among others. Firstly, the following contributions are presented: the RG2D algorithm based on the Reactive Greedy Randomized Adaptive Search Procedure (GRASP Reactive) and implemented from improvements made in the GRASP-2D (G2D) algorithm, to address the highlighted problem; the Algorithm X, based on Integer Programming and capable of provably to obtain the optimal weights for the Dynamic Programming state space relaxation proposed in (CHRISTOFIDES; HADJICONSTANTINOU, 1995); the X2 algorithm proposed as a generalization of X that uses two-dimensional weights in order to obtain even stronger upper bounds; the X2H algorithm that consists in the adaptation of X2 to transform it into a primal heuristic; the method X2D that results from the combination of those four elements was tested in a large set of instances and showed to be able to find solutions with quality guarantees or even certificate of optimality. Next, in order to handle TGCSP, the contributions are: hybrid algorithms that combine in different ways Column Generation with Dynamic Programming and the new RG2D algorithms are proposed. The computational results obtained so far were very positive. In all tested instances, the final solutions were never more than 1 unit above the lower bound given by the Column Generation-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Direitos: dc.rightsopenAccess-
Direitos: dc.rightsCC-BY-SA-
Palavras-chave: dc.subjectCorte bidimensional-
Palavras-chave: dc.subjectGrasp-
Palavras-chave: dc.subjectProgramação dinâmica-
Palavras-chave: dc.subjectProgramação inteira-
Palavras-chave: dc.subjectGeração de colunas-
Palavras-chave: dc.subjectPesquisa operacional-
Palavras-chave: dc.subjectMetaheurística-
Palavras-chave: dc.subjectProgramação inteira-
Palavras-chave: dc.subjectProgramação dinâmica-
Palavras-chave: dc.subjectTwo-dimensional cutting-
Palavras-chave: dc.subjectInteger programming-
Palavras-chave: dc.subjectDynamic programming-
Palavras-chave: dc.subjectColumn generation-
Título: dc.titleAlgoritmos híbridos para o problema de corte bidimensional-
Título: dc.titleHybrid algorithms for the two-dimensional cut-off problem-
Tipo de arquivo: dc.typeTese-
Aparece nas coleções:Repositório Institucional da Universidade Federal Fluminense - RiUFF

Não existem arquivos associados a este item.