Utilize este identificador para referenciar este registo:
https://hdl.handle.net/1822/10760
Título: | Modelos e algoritmos para o problema de minimização de padrões |
Autor(es): | Peixoto, Carlos Miguel Marques |
Orientador(es): | Alves, Cláudio Manuel Martins |
Data: | 28-Mai-2009 |
Resumo(s): | Nesta dissertação, estudamos um problema de optimização combinatória designado por
Problema de Minimização de Padrões. O problema é um problema de corte no qual se
consideram custos de setup. Existe um número muito reduzido de métodos para a resolução
exacta do Problema de Minimização de Padrões. Aqueles que são descritos na literatura
apenas permitem resolver algumas instâncias de pequena dimensão. Com esta dissertação,
pretendemos contribuir para a resolução exacta do problema explorando um modelo que foi
proposto recentemente na literatura.
Os modelos de Programação Inteira propostos na literatura são descritos na primeira parte
do texto. Descrevemos também os algoritmos exactos que foram definidos com base nesses
modelos e apresentamos algumas das melhores heurísticas de resolução que foram
desenvolvidas para este problema.
Na segunda parte da dissertação, analisamos em detalhe um modelo proposto recentemente
na literatura para o Problema de Minimização de Padrões. Esse modelo é um modelo de
Programação Inteira, obtido com base numa nova decomposição de um modelo não-linear.
Exploramos formas de reforçar esse modelo, e analisamos algoritmos que permitam obter
soluções óptimas inteiras a partir do método de partição e avaliação e do método de geração
de colunas.
A diferença entre os algoritmos reside nas regras de partição que foram usadas. É sabido
que combinar o método de partição e avaliação com o método de geração de colunas não é
trivial. A partição feita com base nas variáveis do modelo de geração de colunas provoca a
regeneração das colunas presentes no problema mestre. A forma de evitar esse problema
passa por aumentar a complexidade do subproblema. Nesta dissertação, as regras de partição
são baseadas em variáveis originais, e como tal não alteram significativamente a dificuldade
dos subproblemas de geração de colunas.
Foram conduzidos experiências computacionais para avaliar a qualidade dos esquemas de
partição propostos. Essas experiências foram realizadas usando instâncias da literatura, e sem
recorrer a qualquer heurística. Os resultados das experiências são apresentados no final da
dissertação. In this dissertation, we study a combinatorial optimization problem called the Pattern Minimization Problem. The problem is a cutting stock problem in which setup costs are considered. The number of exact algorithms that were proposed in the literature for this problem is very small. Those that were proposed can only solve a limited number of small and medium instances. With this dissertation, our aim is to contribute to the exact resolution of this problem by exploring a model that was proposed recently in the literature. The Integer Programming models proposed in the literature are described in the first part of this text. We also describe the exact algorithms that were defined based on these models and we present the best heuristics that were developed to solve this problem. In the second part of this dissertation, we analyse in detail a model proposed recently in the literature for the Pattern Minimization Problem. This model is an Integer Programming model that is obtained by applying a new decomposition to a non-linear model. We explore ways of strengthening the model, and we analyse algorithms for computing integer solution using the branch-and-bound method and the column generation method. The difference among our algorithms is in the branching scheme that is used. It is well known that combinig branch-and-bound with column generation is not trivial. When the partition is done on the variables of the column generation model, regeneration occurs. To avoid this regeneration, we have to increase the complexity of the pricing subproblem. In this dissertation, the branching rules are based on original variables and hence the complexity of the subproblem is almost unchanged. Computational experiments were conducted to evaluate the quality of the branching schemes proposed. These experiences were conducted on instances from the literature, and without using any heuristic. The results of these experiments are presented at the end of this dissertation. |
Tipo: | Dissertação de mestrado |
Descrição: | Dissertação de mestrado em Engenharia Industrial |
URI: | https://hdl.handle.net/1822/10760 |
Acesso: | Acesso aberto |
Aparece nas coleções: | BUM - Dissertações de Mestrado DPS - Dissertações de Mestrado |