Texto completo
| |
| Autor(es): |
Vinícius Loti de Lima
Número total de Autores: 1
|
| Tipo de documento: | Tese de Doutorado |
| Imprenta: | Campinas, SP. |
| Instituição: | Universidade Estadual de Campinas (UNICAMP). Instituto de Computação |
| Data de defesa: | 2021-12-14 |
| Membros da banca: |
Flávio Keidi Miyazawa;
Eduardo Uchoa Barboza;
Luciana Salete Buriol;
Marco Lübbecke;
Stefan Irnich
|
| Orientador: | Flávio Keidi Miyazawa; Thiago Alves de Queiroz |
| Resumo | |
Esta tese foca em otimização combinatória, um dos grandes campos em otimização. Esse campo consiste de problemas de decisão, nos quais é dado um conjunto discreto potencialmente enorme de soluções possíveis e deve-se encontrar uma única solução que otimize uma dada função objetivo. Esses problemas têm um grande número de aplicações no mundo real, principalmente em logística industrial e em cadeia de suprimentos. Primeiro, estudamos formulações de fluxo em redes que podem ser aplicadas a problemas gerais de otimização combinatória. Apresentamos um survey discutindo as fundamentações teóricas e as principais aplicações bem-sucedidas dos chamados modelos de fluxo em arcos pseudo-polinomiais. Em seguida, propomos novos métodos exatos para resolver tais modelos, envolvendo geração de colunas, regras de branching especializadas e estratégias de fixação de variáveis. Aplicamos os métodos de solução propostos a problemas bem estudados da literatura de corte, empacotamento e escalonamento, incluindo, por exemplo, os clássicos bin packing problem e cutting stock problem. Nossos experimentos computacionais mostram a eficácia dos métodos propostos, resolvendo na otimalidade um grande número de instâncias benchmark em aberto, de vários problemas. A segunda parte desta tese dá atenção especial à área de corte e empacotamento bidimensional, que está entre as áreas mais estudadas em otimização combinatória. Apresentamos uma revisão das referências mais relevantes que surgiram nas últimas duas décadas e propomos uma biblioteca online para organizar sistematicamente os materiais mais relevantes sobre tais problemas. Essas contribuições podem facilitar pesquisas futuras na área ativa de corte e empacotamento bidimensional. Nossa última contribuição diz respeito a um problema do mundo real surgido de uma empresa italiana de produção de carne. O problema é composto por um grande conjunto de decisões complexas, envolvendo a alocação diária de mão de obra e o escalonamento de pedidos na empresa. Para resolver esse problema, propomos uma heurística construtiva de três fases, implementada em um framework multi-start. Nosso algoritmo supera em média as decisões tomadas pela estratégia anterior da empresa (AU) | |
| Processo FAPESP: | 17/11831-1 - Algoritmos e modelos para problemas de corte e empacotamento |
| Beneficiário: | Vinícius Loti de Lima |
| Modalidade de apoio: | Bolsas no Brasil - Doutorado Direto |