Um estudo sobre métodos de solução para o problema de corte de estoque biobjetivo

Imagem de Miniatura

Data

2021-08-20

Autores

Borges, Jennifer Cristina

Título da Revista

ISSN da Revista

Título de Volume

Editor

Universidade Estadual Paulista (Unesp)

Resumo

Nessa tese é feita uma breve revisão sobre as principais características do Problema de Corte de Estoque (PCE) Unidimensional e Bidimensional. Apresentam-se modelos de otimização matemática utilizados para gerar os padrões de corte unidimensionais e bidimensionais e diferentes critérios de otimização. Os critérios considerados são: minimizar o número total de objetos cortados, setups e ciclos da serra que são conflitantes entre si, e utiliza-se a abordagem multiobjetivo para resolver o PCE Unidimensional e Bidimensional. Na revisão de literatura verificou-se que o Problema de Corte de Estoque Bidimensional Multiobjetivo (PCEM-2D) é pouco abordado na literatura. Os artigos que tratam o caso unidimensional (PCEM-1D) usando métodos de escalarização desconsideram a geração dinâmica de colunas para a matriz de restrições do problema. Assim, a partir da revisão da literatura sobre métodos de escalarização para problemas de otimização inteira multiobjetivo são selecionados os métodos ϵ-Restrito Lexicográfico, Tchebycheff Ponderado Aumentado e Particionamento da Fronteira para resolver o PCEM-1D e o PCEM-2D, considerando que os padrões de corte são gerados dinamicamente. Através de simulações computacionais foi possível concluir que a geração de padrões de corte dinâmica resulta em uma melhor aproximação da fronteira de Pareto do que a geração de colunas a priori, e que o método que usa a estratégia branch and cut obteve o melhor desempenho quando comparado a outros dois métodos para os casos unidimensional e bidimensional. Outra contribuição dessa tese é a utilização de conceitos de invexidade para provar resultados de otimalidade parcial para o problema de corte de estoque biobjetivo. Dessa forma reitera-se conexões entre a otimização discreta e a otimização contínua multiobjetivo.
In this thesis, a review of the main features of the one dimensional and the two dimensional Cutting Stock Problem (CSP) is presented. Mathematical optimization models to generate one-dimensional and two-dimensional cutting patterns as well as different optimization criteria are discussed. The criteria considered are: minimize the total number of objects cut, of setups and of saw cycles that conflict with each other, therefore a multiobjective approach is proposed to solve the One-dimensional and Two-dimensional CSP. In the literature few papers address the Two-Dimensional Multiobjective Cutting Stock Problem (MCSP-2D). The papers that propose scalarization methods for the one-dimensional case (MCSP-1D) do not consider a dynamic generation of columns for the problem constraint matrix. Thus, from the literature review about scalarization methods, the ϵ-Lexicographical Restricted, Augmented Weighted Tchebycheff and Frontier Partitioning methods were selected to solve the MCSP-1D and the MCSP-2D considering that the cutting patterns are dynamically generated. Through the computer simulations it was possible to conclude that the dynamic generation of cutting patterns results in a better approximation of the Pareto frontier. The method based on a branch and cut strategy had the best performance compared to the other two methods for both problems. Another contribution of this thesis is the use of invexity concepts to prove partial optimality results for the biobjective cutting stock problem. Thus reiterating connections between discrete optimization and multiobjective continuous optimization.

Descrição

Palavras-chave

Problema de corte de estoque, Otimização multiobjetivo, Métodos de escalarização, Invexidade, Cutting stock problem, Multiobjective optimization, Scalarization methods, Invexity

Como citar