The two-dimensional cutting problem with usable leftovers and uncertainty in demand
| Autor: | Nascimento, Douglas Nogueira do |
|---|---|
| Přispěvatelé: | Universidade Estadual Paulista (Unesp), Cherri, Adriana Cristina [UNESP], Oliveira, José Fernando |
| Jazyk: | portugalština |
| Rok vydání: | 2022 |
| Předmět: | |
| Zdroj: | Repositório Institucional da UNESP Universidade Estadual Paulista (UNESP) instacron:UNESP |
| Popis: | Submitted by Douglas Nogueira do Nascimento (douglas.nogueira@unesp.br) on 2022-09-06T02:58:37Z No. of bitstreams: 1 Tese - Douglas Nogueira do Nascimento - Versão Final.pdf: 1680670 bytes, checksum: 207877f0bb2b87f5f826c792a2476702 (MD5) Approved for entry into archive by Lucilene Cordeiro da Silva Messias null (lubiblio@bauru.unesp.br) on 2022-09-06T11:39:31Z (GMT) No. of bitstreams: 1 nascimento_dn_dr_bauru.pdf: 1680670 bytes, checksum: 207877f0bb2b87f5f826c792a2476702 (MD5) Made available in DSpace on 2022-09-06T11:39:31Z (GMT). No. of bitstreams: 1 nascimento_dn_dr_bauru.pdf: 1680670 bytes, checksum: 207877f0bb2b87f5f826c792a2476702 (MD5) Previous issue date: 2022-09-01 Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) O problema de corte de estoque é um problema clássico da área de pesquisa operacional que foi tema de centenas de estudos publicados na literatura científica. Na primeira parte desta tese, é abordada uma variação desse problema, conhecida como problema de corte de estoque bidimensional com sobras aproveitáveis, que consiste em cortar placas retangulares disponíveis em estoque para produzir itens retangulares menores com dimensões e quantidades específicas, de modo a minimizar a perda de material. O planejamento dessa produção é realizado considerando a possibilidade de gerar sobras não demandadas que, caso atendam a critérios predefinidos, retornam ao estoque para serem utilizadas em futuros processos de corte. O aproveitamento de sobras é uma técnica de grande importância prática para muitas empresas, com forte impacto econômico e ambiental, devido à redução no desperdício de matéria-prima. Para resolver este problema, foi proposto um modelo matemático que, simultaneamente, cria padrões de corte e determina suas frequências. Os padrões de corte são criados a partir de uma estratégia que divide a placa cortada em faixas horizontais, nas quais os itens são alocados. Novos tipos de itens também são considerados a partir da combinação dos tipos de itens originais. Esse modelo foi resolvido a partir de um solver exato. Entretanto, devido ao seu alto número de variáveis e restrições, pode se tornar inviável sua resolução para instâncias de médio e grande porte em um tempo computacional aceitável. Nesse contexto, foi desenvolvido um procedimento heurístico que utiliza duas adaptações do modelo para resolver separadamente as tarefas de criar padrões de corte e definir suas frequências. Testes computacionais foram realizados com instâncias da literatura e instâncias geradas aleatoriamente para comparar o desempenho do modelo e da heurística com outros modelos propostos na literatura. Na segunda parte da tese, com o objetivo de aproximar esta pesquisa de aplicações práticas reais, o problema de corte de estoque bidimensional com sobras aproveitáveis foi estudado considerando a incerteza na demanda dos itens. A produção de sobras aproveitáveis e itens visando atender uma demanda variável e aleatória é um problema recorrente nas empresas por conta da imprevisibilidade na ocorrência dos pedidos dos clientes. A resolução desse problema envolve um planejamento complexo, motivando a busca por métodos de solução que auxiliem no processo de tomada de decisão. Para a formulação desse problema, as demandas incertas podem ser aproximadas por um conjunto finito de possíveis cenários. Esta tese contribui com a literatura científica propondo uma matheurística que resolve o problema a partir de três etapas consecutivas e dependentes entre si. Na primeira etapa, um conjunto de padrões de corte, com e sem sobras aproveitáveis, é criado para todos os tipos de placas em estoque e todas as possíveis combinações de itens. Esses padrões de corte são usados na segunda etapa por um framework baseado em algoritmos genéticos que gera um conjunto de cenários de demanda. Na terceira etapa, tanto os padrões quanto os cenários são utilizados por um modelo estocástico que determina a frequência de cada padrão de corte em cada cenário de demanda. Esse modelo estocástico foi resolvido por duas abordagens, um solver exato e uma heurística baseada no método L-shaped, avaliadas utilizando experimentos computacionais com instâncias geradas aleatoriamente. A partir dos resultados obtidos e de uma análise dos efeitos da incerteza na qualidade das soluções, foi possível verificar que a matheurística resolve satisfatoriamente o problema abordado, demonstrando que pode ser uma ferramenta eficiente se aplicada a situações reais. The cutting stock problem is a classic problem in the operational research area that has been the subject of hundreds of studies published in the scientific literature. In the first part of this thesis, a variation of this problem, known as the two-dimensional cutting stock problem with usable leftovers, is addressed, which consists of cutting rectangular plates available in stock to produce smaller rectangular items with specific dimensions and quantities while minimizing the material loss. The planning of this production is carried out considering the possibility of generating unordered leftovers that, if meeting predefined criteria, return to stock to be used in future cutting processes. Usable leftovers is a strategy of great practical importance for many companies, with strong economic and environmental impact, due to the reduction in raw material waste. To solve this problem, a mathematical model that simultaneously creates cutting patterns and determines their frequencies was proposed. The cutting patterns are created by a strategy that divides the cut plate into horizontal strips, in which the items are allocated. New items are also considered from the combination of the original types of items. This model was solved by an exact solver. However, due to its high number of variables and constraints, its resolution for medium and large-sized instances may become impracticable in an acceptable computational time. In this context, a heuristic procedure was developed using two adaptations of the model to solve separately the tasks of creating cutting patterns and defining their frequencies. Computational tests were performed with instances from the literature and randomly generated instances to compare the performance of the model and the heuristic with other models proposed in the literature. In the second part of the thesis, aiming to bring this research closer to real practical applications, the two-dimensional cutting stock problem with usable leftovers was studied considering uncertain items' demand. The production of usable leftovers and items to meet a variable and random demand is a recurring problem in companies due to the unpredictability occurrence of customer orders. Solving this problem involves complex planning, which motivates the search for solution methods that help in the decision-making process. For the formulation of this problem, the uncertain demands can be approximated by a finite set of possible scenarios. This thesis contributes to the scientific literature by proposing a matheuristic that solves the problem in three consecutive and dependent steps. In the first step, a set of cutting patterns, with and without usable leftovers, is created for all types of plates in stock and all possible item combinations. These cutting patterns are used in the second step by a framework based on genetic algorithms that generate a set of demand scenarios. In the third step, both patterns and scenarios are used by a stochastic model that determines the frequency of each cutting pattern in each demand scenario. This stochastic model was solved by two approaches, an exact solver and a heuristic based on the L-shaped method, tested in computational experiments with randomly generated instances. From the obtained results and an analysis of the effects of uncertainty on the quality of solutions, it was possible to verify that the matheuristic satisfactorily solves the addressed problem, demonstrating that it can be an efficient tool if applied to real situations. FAPESP: 2018/16600-0 FAPESP: 2019/25041-8 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|