Metaheurísticas híbridas baseadas em programação por restrições para um problema de corte bidimensional guilhotinado com defeitos e restrições de precedência

• Ano de defesa: 2020
• Autor(a) principal: Santos Neto, Junot Freire dos
• Orientador(a): Melo, Rafael Augusto de
• Banca de defesa: Januario, Tiago de Oliveira, Prata, Bruno de Athayde
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal da Bahia; Instituto de Matemática e Estatística; Departamento de Ciência da Computação
• Programa de Pós-Graduação: em Ciência da Computação
• País: Brasil
• Palavras-chave em Português: Problema de corte bidimensional; Metaheurísticas; Programação lógica por restrição; Otimização combinatória; Algoritmo; Heurística (computação)
• Área do conhecimento CNPq: Ciências Exatas e da Terra; Ciência da Computação
• Link de acesso: http://repositorio.ufba.br/ri/handle/ri/33606

Problemas de corte bidimensional (2BP, do inglês \textit{Two-Dimensional bin packing problem}) são problemas clássicos de otimização combinatória pertencentes à classe NP-Difícil e tem aplicações em diversos setores como a indústria têxtil, metalúrgica e de vidro. Estes problemas consistem em alocar um conjunto de itens retangulares em placas retangulares maiores com tamanho padronizado, a fim de minimizar o desperdício de matéria-prima. Nesta dissertação é estudado um problema restrito de corte bidimensional guilhotinado associado à produção de vidro considerado no \textit{\citeA{challenge2018}}, no qual existe a possibilidade de rotacionar itens em 90° e possuem ordem de precedência para serem produzidos, e as placas retangulares de matéria-prima podem possuir defeitos como rachaduras e trincos. São propostas como técnicas para este problema duas heurísticas gulosas randomizadas e um método de aprimoramento de soluções baseado em uma modelagem de programação lógica por restrições combinada com uma heurística gulosa randomizada. As técnicas foram combinadas em metaheurísticas \textit{Multistart} e \textit{GRASP} (do inglês, \textit{Greedy Randomized Adaptive Search Procedure}) a fim de se obterem melhores soluções. Os experimentos realizados mostram que o uso do método de aprimoramento de soluções é vantajoso, e que algumas combinações de técnicas se mostram mais eficazes para determinados tipos de instâncias. Uma versão preliminar deste trabalho foi qualificada para a etapa final do \textit{\citeA{challenge2018}}.