Banca de DEFESA: VÍTOR ALVES BARBOSA

Uma banca de DEFESA de MESTRADO foi cadastrada pelo programa.
DISCENTE : VÍTOR ALVES BARBOSA
DATA : 21/07/2025
HORA: 17:00
LOCAL: Virtual
TÍTULO:

Formulações e Heurísticas para Problemas de Roteamento e Escalonamento

PALAVRAS-CHAVES:

Roteamento, Escalonamento de tarefas acopladas, Programação inteira mista, Programação linear, Busca local, Programação por restrições, BRKGA

PÁGINAS: 104
RESUMO:

Neste trabalho, são estudados dois problemas de otimização relacionados ao roteamento e escalonamento. O primeiro estudo envolve o problema de coleta e entrega com janelas de tempo e escalonamento nas arestas (pickup and delivery problem with time windows and scheduling on the edges — PDPTW-SE). O desafio consiste em determinar rotas para uma frota heterogênea de veículos, a fim de transportar pedidos com locais específicos de coleta e entrega, considerando que algumas travessias exigem uma atuação sincronizada com máquinas. Como o número de máquinas é limitado, seu uso deve ser devidamente escalonado. O objetivo é minimizar o tempo total de conclusão, respeitando restrições de capacidade, janelas de tempo e precedência. Para esse fim, são desenvolvidas uma formulação de programação inteira mista (mixed integer programming — MIP) e uma heurística multistart com um procedimento de melhoria baseado em programação linear. Também é proposto um conjunto de instâncias de teste composto por duas famílias de instâncias, representando diferentes aplicações do problema. Nos experimentos computacionais, a formulação MIP resolve instâncias com até doze pedidos e encontra soluções viáveis para 93.40% das instâncias. A heurística, por sua vez, obtém soluções viáveis para todas as instâncias, com qualidade equivalente ou superior à da formulação MIP. O segundo estudo envolve o problema de escalonamento de tarefas acopladas em uma única máquina (single-machine coupled-task scheduling problem — SMCTSP). Esse é um problema de escalonamento de trabalhos, no qual cada trabalho é composto por duas tarefas acopladas, não preemptivas, e separadas por um atraso exato. O objetivo é minimizar o tempo de conclusão da última tarefa escalonada. Para tal, o problema é modelado utilizando programação por restrições (constraint programming — CP). Adicionalmente, um algoritmo genético de chaves aleatórias enviesadas (biased random-key genetic algorithm — BRKGA) é desenvolvido incorporando um gerador de soluções iniciais (warm-start), reinicializações periódicas com diferentes intensidades, e um algoritmo de busca local. Os experimentos computacionais indicam que o BRKGA proposto fornece soluções de alta qualidade com tempos computacionais reduzidos em comparação ao modelo CP. Por outro lado, o modelo CP supera significativamente as soluções obtidas pelo BRKGA quando executado por uma hora e com execução paralela em múltiplos núcleos. Por fim, as abordagens propostas em conjunto obtém novas soluções melhores para 93.33% das instâncias ainda não resolvidas até a otimalidade pelas abordagens anteriores na literatura.

MEMBROS DA BANCA:
Presidente - 2115562 - RAFAEL AUGUSTO DE MELO
Externo à Instituição - THIAGO FERREIRA DE NORONHA - UFMG
Externo à Instituição - CELSO DA CRUZ CARNEIRO RIBEIRO - UFF