 ISEP | H211
3 de junho de 2014 | 12:00
Nesta apresentação é abordado o Problema de Posicionamento que consiste em minimizar a área da envolvente retangular que contém um conjunto de itens ortogonais.
Este problema surge em vários contextos reais: tais como no posicionamento de módulos em circuitos VLSI, que tem como objetivo encontrar o melhor posicionamento dos módulos para obter circuitos compactos, e no projeto físico de instalações, no qual um dos objetivos passa por encontrar o arranjo mais eficiente de departamentos dentro de uma instalação. Por exemplo, no posicionamento de itens, em circuitos VLSI, módulos com formas ortogonais surgiram para facilitar a utilização da área do circuito e melhorar a ligação entre os itens, contribuindo para o aumento do desempenho do circuito.
As instâncias que surgem nos problemas reais, principalmente nos circuitos integrados, apresentam um elevado número de itens que podem mesmo chegar aos milhares, sendo um grande desafio lidar com instâncias desta dimensão.
Enquanto problemas de otimização combinatória podem ser resolvidos usando qualquer uma das abordagens e técnicas disponíveis: programação matemática, heurísticas, meta-heurísticas, algoritmos de pesquisa, programação por restrições, etc. Apesar de serem facilmente representados através de modelos matemáticos são difíceis de serem solucionados dado o grande número de variáveis envolvidas e, consequentemente, obter soluções exatas, principalmente quando aplicados a instâncias de grande dimensão. Desta forma, são muitas vezes usados métodos heurísticos para os solucionar. Apesar destes métodos não garantirem a obtenção da solução ótima do problema, podem obter boas aproximações, com um baixo esforço computacional, quando comparados com a utilização de métodos exatos.
ORADORA-CONVIDADA
Marisa Oliveira (ISEP)
+INFO
www.lema.isep.ipp.pt |
Instituto Superior de Engenharia do Porto