Aplicação de algoritmos evolucionários ao problema de job-shop scheduling

Resumo

No campo da automação de processos o problema de job-shop scheduling tem sido um dos principais assuntos de pesquisa devido a sua relevância econômica. Tal problema se encaixa na categoria dos problemas de otimização de processos discretos, combinatórias NP-completos, não podendo ser abordado por meio de técnicas tradicionais de otimização fundamentadas no uso do gradiente descendente. Por esta razão os métodos para sua resolução, isto é para encontrar soluções quase ótimas, têm se concentrado no uso de heurísticas. Entre esses métodos encontra-sé a utilização de sistemas multi-agentes, tais como os A-Teams (Asynchronous Teams). Neste caso, diversas heurísticas fazem parte de agentes que trabalham cooperativamente sobre o problema de modo a encontrar uma solução adequada. A composição dessas heurísticas por meio de algoritmos de natureza evolucionária, isto é, processos iterativos que rastreiam soluções através da simulação de operações encontradas nos processos de seleção natural, tem se demonstrado promissora, uma vez que o corpo teórico dos algoritmos evolutivos encontra-se em um estágio de razoável coerência e solidez, em contraste com a dispersão de técnicas encontradas em sua origem histórica. Sendo assim, uma pesquisa envolvendo o estudo dos algoritmos evolucionários seguido de um trabalho de inserção destes sob a forma de heurísticas em sistemas multi-agentes tem potencial para fornecer boas soluções para o problema de job-shop scheduling. (AU)