Algoritmos enumerativos para geração de padrões tabuleiros / Enumerative algorithms to generate checkerboard patterns
AUTOR(ES)
Daniel Massaru Katsurayama
DATA DE PUBLICAÇÃO
2006
RESUMO
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.
ASSUNTO(S)
computaÇÃo aplicada corte produtividade algoritmo métodos heurísticos pesquisa operacional otimização custo de operação custo de produção computer science cutting productivity algorithms heuristic methods operation research optimiation operating costs productio costs
