Algoritmos enumerativos para geração de padrões tabuleiros

• Ano de defesa: 2006
• Autor(a) principal: Daniel Massaru Katsurayama
• Orientador(a): Horácio Hideki Yanasse
• Banca de defesa: José Carlos Becceneri, Reinaldo Morábito Neto, Nei Yoshihiro Soma, Marcos Nereu Arenales
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Instituto Nacional de Pesquisas Espaciais (INPE)
• Programa de Pós-Graduação: Programa de Pós-Graduação do INPE em Computação Aplicada
• País: BR
• Resumo em Inglês: We focus on the problem of determining special cutting patterns known as checkerboard patterns or 1-group patterns. We propose new exact methods and heuristics for determining constrained and unconstrained checkerboard patterns. A new heuristic for determining unconstrained checkerboard pattern is presented. The new heuristic combines more than one strip to compose the best pattern, generating a larger variety of patterns than the heuristics proposed previously in the literature. Three exact methods for determining constrained exact checkerboard patterns are proposed. The first one is based on an enumerative algorithm proposed by Yanasse, Soma and Maculan (2000) for determining the K-best solutions of the one-dimensional knapsack problem. The second one is based on a Gilmore and Gomorys (1963) implicit enumeration scheme for solving the one-dimensional unconstrained knapsack problem. The third one is an improved version of second method. The results obtained from the computational tests indicate that the third method outperforms previous methods of the literature in terms of execution times.
• Link de acesso: http://urlib.net/sid.inpe.br/MTC-m13@80/2006/08.10.18.26

Nesta tese de doutorado focaliza-se o problema da determinação de padrões de corte simples, conhecidos como padrões tabuleiros, ou padrões 1-grupo. São propostos novos métodos exatos e heurísticas para a determinação de padrões tabuleiros restritos e irrestritos. Uma nova heurística para determinação de padrões tabuleiros irrestritos é apresentada. A nova heurística combina mais de uma faixa para compor o melhor padrão, gerando uma maior variedade de padrões do que uma heurística proposta anteriormente na literatura. Propõem-se três métodos exatos para determinação de padrões tabuleiros exatos e restritos. O primeiro método baseia-se no algoritmo enumerativo de Yanasse, Soma e Maculan (2000) para determinação das K-melhores soluções para o problema da mochila unidimensional. O segundo método baseia-se no método da enumeração implícita de Gilmore e Gomory (1963) para resolução do problema da mochila unidimensional irrestrito. O terceiro método é uma versão melhorada do segundo método exato proposto. Os resultados dos testes computacionais realizados indicam que o terceiro método é mais eficiente do que os demais da literatura, em termos de tempos computacionais.