Projeto financiado pelo CNPq com recursos do Edital Universal - MCT/CNPq - Nº 15/2007
Resumo:
Desenvolver algoritmos heurísticos eficientes para resolver problemas de otimização tem sido um desafio constante para os pesquisadores. A programação matemática tem a vantagem de fornecer a solução ótima para um problema, mas seu uso é muitas vezes desestimulado pelo consumo excessivo de tempo de processamento ou até mesmo pela dificuldade de se modelar determinados problemas. Por outro lado, os algoritmos heurísticos normalmente não garantem alcançar a solução ótima. Neste projeto são propostos alguns algoritmo híbridos baseados em programação matemática e heurísticas com o objetivo de explorar as vantagens de ambos na tentativa de solucionar alguns problemas de otimização combinatória. A presente investigação será fomentada a partir de três tipos de problemas de otimização combinatória: planarização de grafos, escalonamento e alocação. Estes serão os problemas fomentadores da investigação de algoritmos eficientes, com o objetivo de desenvolver novas técnicas/algoritmos que proporcionem avanços no projeto de algoritmos aplicados, também, para outros fins. Particularmente, os problemas de planarização de grafos são extremamente complexos de serem modelados por programação matemática. Nesse caso, será realizada uma investigação de algoritmos heurísticos baseados em st-numeração e árvores-PQ com o objetivo de encontrar subgrafos planares máximo, usando a invariante de apagamento de vértice. Além disso, investigar o uso da st-numeração na obtenção de grafos planares com o mínimo de cruzamentos em desenho linear. Dentro da linha de problemas de escalonamento, serão desenvolvidos e investigados alguns algoritmos heurísticos para solucionar problemas de emparelhamento em grafo multipartido com gargalo que surge em alguns problemas de escalonamento de pessoal. Nesta linha, será explorada a programação paralela/distribuída sobre um cluster de computadores através do uso de algoritmos populacionais. Além disso, investigar um problema ainda não explorado pela literatura que integra a programação de produção e escalonamento de pessoal de forma simultânea, envolvendo transporte de carga viva. Na linha de problemas de alocação serão investigados alguns algoritmos heurísticos, combinados com programação matemática, para um problema real de alocação de espaço físico em instituição de ensino. Para esse problema está sendo idealizado um novo modelo, denominado de Modelo Gravitacional, que também fará uso da resolução de emparelhamento num grafo multipartido com gargalo. Em suma, este projeto explorará algumas técnicas dentre as quais destacamos o uso de algoritmos bio-inspirados, algoritmo heurístico baseado em st-numeração e árvore PQ, algoritmos paralelos para cluster, além da modelagem por meio de grafos e programação matemática. A equipe que compõe este projeto é formada por três pesquisadores com experiência na área, sendo que os pesquisadores possuem dedicação exclusiva em suas instituições de origem, sendo elas, UEM, USP e UNESP. Além disso, estão envolvidos quatro alunos de mestrado, além de um aluno de iniciação científica e outros alunos de conclusão de curso. A meta central deste grupo de pesquisa é a produção científica de técnicas algorítmicas para problemas de otimização e em grafos. Como resultado final, esperamos contribuir para o conhecimento científico por meio de publicações em veículos de divulgação de impacto nacional e internacional. Os resultados preliminares e as experiências do grupo são indicadores para a conclusão do projeto.