Desenvolvimento de um algoritmo genético multinível híbrido para problemas de sequenciamento da produção em job shop de médio e grande porte

Resumo

O problema de sequenciamento da produção (scheduling) tem sido exaustivamente estudado nos últimos anos devido a sua importância prática e complexidade computacional. Em geral, problemas de scheduling são resolvidos com uso de técnicas metaheurísticas de otimização. Entretanto, apesar de existirem abordagens relativamente eficientes para problemas considerados pequenos (até 100 operações), há problemas de médio ou grande porte para os quais ainda não foram encontradas soluções ótimas, ou mesmo sub-ótimas, ou o foram em um tempo computacional muito elevado. Por outro lado, problemas com características estocásticas e dinâmicas também carecem de uma melhor investigação. Este projeto propõe, portanto, o desenvolvimento de uma versão híbrida multinível da metaheurística Algoritmo Genético baseada na criação de subespaços do espaço de busca original. O objetivo é pesquisar técnicas para projetar o problema em um subespaço apropriado, que aproxime o espaço original e idealmente contenha uma boa aproximação da solução procurada, reduzindo o tamanho do problema e, consequentemente, o esforço computacional para resolvê-lo. Técnicas estatísticas e de inteligência artificial e transformada discreta wavelet serão investigadas. Especificamente, os dois seguintes tipos de problemas serão abordados: 1) scheduling em um ambiente de produção job shop clássico, com n tarefas e m máquinas em que cada tarefa é processada nas m máquinas, de acordo com um roteiro preestabelecido e tempos de processamento determinísticos; 2) scheduling em um ambiente job shop estocástico e dinâmico, no qual os tempos de produção das tarefas e o intervalo de tempo entre as chegadas das tarefas no sistema são aleatórios e descritos por distribuições de probabilidades. Em ambos os casos, o objetivo é determinar a sequência de produção nas máquinas de forma a minimizar o instante de término de processamento de todas as tarefa no sistema de produção (makespan). (AU)