Defesa de Tese de THIAGO HENRIQUE NOGUEIRA

SINGLE MACHINE SCHEDULING PROBLEMS WITH SEQUENCE-DEPENDENT SETUP TIMES (PROBLEMAS DE SEQUENCIAMENTO DE UMA MÁQUINA COM TEMPOS DE PREPARAÇÃO DEPENDENTES DA SEQUÊNCIA)

 

Problemas de otimização do tipo NP-Difícil aparecem nas mais distintas aplicações do mundo real, tais como planejamento da produção, sequenciamento de projetos, design de redes, roteamento de veículos, sequenciamento de máquinas e vários outros campos de importância econômica, industrial e científica. Dentre eles, destacam-se os problemas de sequenciamento de máquinas, os quais consistem em alocar recursos escassos em atividades ao longo do tempo, desejando minimizar um ou mais objetivos. Neste trabalho, um conjunto de jobs deve ser processado uma única vez, em uma máquina, sem preemption. Cada job pode possuir release date, due date, weight, processing time e sequence-dependent setup time. Ao longo deste trabalho, as funções objetivo consideradas minimizam total weighted tardiness, total weighted completion time e total tardiness. Inicialmente são propostas e analisadas seis mixed integer programming (MIP) formulações para o problema de sequenciamento de uma máquina com sequence-dependent setup times e release dates. Em seguida, apresenta-se um panorama histórico de uma variedade de formulações para esta família de problemas. Extensivos experimentos computacionais são realizados, considerando-se uma variedade de características das instâncias para capturar vários aspectos das situações práticas. Para exemplificar uma aplicação real, os problemas de sequenciamento de uma máquina propostos são utilizados para o sequenciamento
de trens em uma rede ferroviária de via única com intercâmbio entre ferrovias. Uma parte da rede ferroviária é pertencente à Companhia VALE e a outra parte à Centro-Atlântica ferroviário (FCA). Nesta linha férrea compartilhada, os comboios circulam em ambos os sentidos e o gargalo é devido ao denso fluxo entre as ferrovias. O objetivo dos modelos matemáticos é minimizar o atraso total ponderado pela prioridade atribuida a cada trem ou total weighted tardiness no ambiente de sequenciamento de máquinas. Finalmente, para atingir o máximo de desempenho e economia de memória, de forma a resolver grandes instâncias, propõe-se uma metaheurística Lagrangeana híbrida que não depende de solvers comerciais. A metaheurística híbrida proposta é uma relaxação Lagrangeana integrada com metaheurísticas. Considerando-se as informações sobre os multiplicadores de Lagrange, esta metaheurística proposta utiliza as informações destes multiplicadores para construir e perturbar soluções viáveis. Boas soluções viáveis para instâncias da literatura com até 45 jobs foram obtidos num tempo razoável. A metaheurística híbrida proposta é comparada com metaheurísticas da literatura. Os limites superiores obtidos foram particularmente bons para as instâncias estudadas, a otimalidade foi provada para várias instâncias e gaps apertados para as demais. Além disso, a metaheurística proposta apresentou geralmente melhores resultados do que as metaheurísticas consultadas na literatura.

 

22/08/2014

14:00

sala 1014, Escola de Engenharia