A+A-Acessibilidade
EnglishPortuguese
Buscar
14 Dez
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