The one-dimensional multi-period cutting stock problem with setup cost
| dc.contributor.advisor | Araujo, Silvio Alexandre de [UNESP] | |
| dc.contributor.author | Silva, Eduardo Machado | |
| dc.contributor.institution | Universidade Estadual Paulista (Unesp) | |
| dc.date.accessioned | 2023-03-06T19:47:08Z | |
| dc.date.available | 2023-03-06T19:47:08Z | |
| dc.date.issued | 2023-01-26 | |
| dc.description.abstract | Nesta tese o problema de corte de estoque unidimensional multiperíodo com minimização dos custos de preparação nos padrões de corte é estudado. Primeiro propomos um extenso conjunto de formulações pseudo-polinomiais e baseadas em padrões de corte, principalmente adaptando formulações conhecidas para problemas de corte de estoque da literatura. Reformulações baseadas no problema de localização de facilidades são discutidas para melhorar os limitantes inferiores dos modelos propostos. Em seguida, apresentamos uma análise teórica comparando as várias formulações propostas em relação ao seu limitante inferior. Apresentamos uma análise computacional a fim de complementar a análise teórica e apresentar mais insights com relação à complexidade e qualidade das formulações na prática. Os experimentos computacionais foram realizados em dois conjuntos de instâncias sendo o segundo mais difícil de ser resolvido. Ambos os conjuntos de instâncias mostraram que as reformulações baseadas no problema de localização de facilidade propostas melhoram a qualidade dos limitantes inferiores. Contudo, testes adicionais mostram que a melhoria do limitante é afetada quando maiores custos do objeto em estoque são considerados. Em uma abordagem diferente, um algoritmo genético de chaves aleatórias viciadas em que o controle dos parâmetros é adaptativo é proposto para resolver o problema. Para a inicialização da metaheurística, um procedimento de decodificação das chaves aleatórias em termos da solução decoder do problema é necessário. Dois decoders são propostos e avaliados com base nos resultados de uma heurística de geração de colunas integrada a um software de solução. Uma combinação da metaheurística e da heurística de geração de colunas também é apresentada. Os resultados computacionais mostram que ambos os processos de decodificação obtém um melhor desempenho que a heurística de geração de colunas para instâncias com itens pequenos cujo custo de preparação nos padrões de corte é maior em relação ao custo do objeto em estoque. Por fim, são discutidas as conclusões finais e propostas de pesquisa futura. | pt |
| dc.description.abstract | In this thesis, we study the multi-period one dimensional cutting stock problem min imizing setup costs on cutting patterns. We first propose an extensive range of pattern based and pseudo-polynomial formulations for the problem, primarily adapting known formulations for cutting stock problems from the literature. Facility location based refor mulations are also discussed to improve the lower bounds of the proposed models. We then present a thorough theoretical analysis to establish the strength of the various pro posed formulations in comparison to each other. A computational analysis is presented to complement the theoretical analysis and present further insights with respect to the complexity and strength of the formulations in practice. The computational experiments were performed over two sets of instances where the second set is more difficult to solve. Both sets of instances have shown that the proposed facility location reformulations signif icantly improve the quality of the lower bounds. However, additional computational tests show that the lower bound improvement is directly affected by the object cost. Then, a random key genetic algorithm with adaptive parameter control is proposed to solve the problem. The metaheuristic initialization requires a decoder process which maps the random keys to feasible solutions of the problem. Two different decoder processes are proposed and evaluated according to the performance of a column generation heuristic solved by an optimization software. An experiment combining both the metaheuristic and the column generation is also presented. Computational experiments show that both decoders outperform the column generation based heuristic for instances with small items length and setup cost greater than the object cost. Finally, some final conclusions and future research are discussed. | en |
| dc.description.sponsorship | Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) | |
| dc.identifier.capes | 33004153071P0 | |
| dc.identifier.uri | http://hdl.handle.net/11449/242337 | |
| dc.language.iso | eng | |
| dc.publisher | Universidade Estadual Paulista (Unesp) | |
| dc.rights.accessRights | Acesso restrito | |
| dc.subject | Problema de corte de estoque multiperíodo | pt |
| dc.subject | Setup nos padrões de corte | pt |
| dc.subject | Formulações fortes | pt |
| dc.subject | Algoritmo Genético Adaptativo com Chaves Aleatórias Viciadas (ABRKGA) | pt |
| dc.subject | Multi-period cutting stock problem | en |
| dc.subject | Cutting pattern setup | en |
| dc.subject | Strong formulations | en |
| dc.subject | Adaptive Biased Random Keys Genetic Algorithm (ABRKGA) | en |
| dc.title | The one-dimensional multi-period cutting stock problem with setup cost | en |
| dc.title.alternative | O Problema de Corte de Estoque Unidimensional Multiperíodo com Custos de Setup | pt |
| dc.type | Tese de doutorado | |
| unesp.campus | Universidade Estadual Paulista (Unesp), Instituto de Biociências Letras e Ciências Exatas, São José do Rio Preto | pt |
| unesp.embargo | 12 meses após a data da defesa | pt |
| unesp.examinationboard.type | Banca pública | pt |
| unesp.graduateProgram | Matemática - IBILCE | pt |
| unesp.knowledgeArea | Matemática aplicada | pt |
| unesp.researchArea | Otimização e Teoria do Controle | pt |
Arquivos
Licença do Pacote
1 - 1 de 1
Nenhuma Miniatura disponível
- Nome:
- license.txt
- Tamanho:
- 2.96 KB
- Formato:
- Item-specific license agreed upon to submission
- Descrição: