14 dez 2021
14:00 Defesa de Doutorado Integralmente a distância
Tema
Métodos Baseados em Programação Inteira Aplicados em Corte, Empacotamento e Escalonamento
Aluno
Vinícius Loti de Lima
Orientador / Docente
Orientador: Flávio Keidi Miyazawa/ Coorientador: Thiago Alves de Queiroz
Breve 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.
Banca examinadora
Titulares:
| Flávio Keidi Miyazawa | IC/UNICAMP |
| Eduardo Uchoa Barboza | TEP/UFF |
| Luciana Salete Buriol | INF/UFRGS |
| Marco Lübbecke | RWTH AACHEN UNIVERSITY |
| Stefan Irnich | JGU - Johannes Gutenberg-Universität Mainz |
Suplentes:
| Yoshiko Wakabayashi | IME/USP |
| Pedro Augusto Munari Junior | DEP/UFSCar |
| Jean François Côté | FSA/Ulaval |