Qualificação de FRANCISCO REGIS ABREU GOMES

Uma Nova Formulação e Geração de Colunas para o Problema de Sequenciamento de Máquinas Paralelas Não-Relacionadas com Tempos de Preparação Dependentes da Máquina e da Sequência para Um e Dois Estágios

 

Essa proposta tem o objetivo de desenvolver métodos exatos para resolver problemas de sequenciamento de máquinas paralelas com um e dois estágios. Nessa proposta serão apresentados os resultados obtidos para um estágio, o que já foi desenvolvido para dois estágios e as próximas atividades. Para o problema com um estágio foi desenvolvida uma nova formulação para o problema de sequenciamento em máquinas paralelas que usa variáveis de posição e uma tarefa fictícia, sendo capaz de eliminar a necessidade de usar o parâmetro big-M para linearização das restrições de precedência. Assim esse modelo é mais eficiente de ser resolvido que os modelos não-lineares que usam esse parâmetro. Para resolver instâncias de maior porte é aplicada a decomposição de Dantzig-Wolfe no modelo proposto que é decomposto em um problema mestre usando uma formulação de particionamento de conjuntos. A relaxação linear do problema mestre restrito é resolvida através de geração de colunas. Para acelerar o processo de geração de colunas são usadas heurísticas para gerar a solução inicial e colunas com custo reduzido negativo. Os resultados preliminares indicam que o método é capaz de resolver instâncias com até 50 tarefas e 6 máquinas em tempo computacional aceitável, encontrando a solução ótima em 25 entre as 30 instâncias testadas e com gap máximo de 0,64%. O modelo foi estendido para o caso com dois estágios, mas não foi possível eliminar a necessidade de usar o parâmetro big-M, por isso, os resultados não foram interessantes. Algumas das próximas atividades serão concluir os trabalhos com o problema de um estágio, desenvolver uma decomposição de Dantzig-Wolfe e um método de geração de colunas para o problema de sequenciamento com dois estágios.

 

06/11/2015

14:00