Orientador: Pedro Sergio de Souza

Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação

Resumo: Times Assíncronos consistem numa nova técnica para solução aproximada de problemas que tem sido aplicada com sucesso a problemas de Otimização Combinatória. Esta técnica faz uso de diversos algoritmos heurísticos que cooperam entre si e conseguem encontrar soluções que não seriam encontradas...

Resumo: Times Assíncronos consistem numa nova técnica para solução aproximada de problemas que tem sido aplicada com sucesso a problemas de Otimização Combinatória. Esta técnica faz uso de diversos algoritmos heurísticos que cooperam entre si e conseguem encontrar soluções que não seriam encontradas pelos mesmos algoritmos quando executados isoladamente. Este trabalho tem como objetivo averiguar a adequabilidade de Tunes Assíncronos como metodolqgia para solução do problema de escalonamento de tarefas conhecido por Job Shop Scheduling Problem (JSP). Este problema é considerado um dos mais complexos dentro da Otimização Combinatória e tem recebido crescente atenção nas últimas décadas devido, principalmante, à sua aplicabilidade a processos industriais.
Especificamente, o cerne do presente trabalho foi a elaboração de TImes A"síncronos centrados fundamentalmente em heurísticas de construção para oJob Shop Scheduling Problem. Foram concebidas e testadas novas heurísticas para o ISP e novos fluxos de dados que podem ser facilmente acoplados à arquitetura de um Time Assíncrono. Os Times Assíncronos desenvolvidos foram submetidos a diversas instâncias do JSP. Os bons resultados obtidos, não somente atestaram a viabilidade da nova técnica como ferramenta para solução do ISP, como revelaram a competitividade destes resultados com aqueles produzidos por outros métodos aproximados para o problema.

Abstract: Asynchronous Teams (or A-Teams) are a new problem resolution technique that has been succesfully applied to Combinatorial Optimization problems. This technique uses several heurisJic algorithms that cooperate simultaneously with each other and find solutions that would not be found through...

Abstract: Asynchronous Teams (or A-Teams) are a new problem resolution technique that has been succesfully applied to Combinatorial Optimization problems. This technique uses several heurisJic algorithms that cooperate simultaneously with each other and find solutions that would not be found through isolated algorithms. The objective of this work is to verify the suitability of Asynchronous Teams methodology solving the combinatorial problem known by Job Shop Scheduling Problem (JSP). This problem has been appointed as one of the most complex problem of Combinatorial Optimization and has been received special attention due to your industrial applicability. Specifically, the kemel of this work was the implementation of A-Teams based on construction heuristics for the Job Shop Scheduling Problem. New heurisncs for the JSP were developed and new data flows that can be easily incorporated in an A-Team architecture were elaborated. Several JSP instances were used to test the A-Teams developed.. The good results obtained by these A-Teams not onIy showed the feasibility of such technique solving the JSP, but also revealed that this results are competitive with others one obtained by good aproximated approachs for the JSP.