| Resumo: |
O objectivo deste projecto é o estudo e desenvolvimento de abordagens e algoritmos para a resolução de problemas de Cortes e Empacotamento (C&E), considerando objectivos múltiplos para além do clássico: a minimização do desperdício. Será a primeira vez que diferentes objectivos serão sistematicamente considerados na resolução de problemas de C&E.
Enquanto problemas de optimização combinatória, os problemas de C&E podem ser resolvidos usando qualquer uma das abordagens e técnicas disponíveis: programação linear, heurísticas, meta-heurísticas, algoritmos de pesquisa, programação em lógica por restrições, etc. Infelizmente, dada a sua natureza combinatória, as técnicas exactas não são capazes de lidar eficientemente com estes problemas para instâncias de grande dimensão, pelo que a utilização de heurísticas se torna indispensável.
Neste projecto será desenvolvida uma estratégia para a resolução de problemas de C&E, considerando simultaneamente a minimização de desperdícios e outros objectivos. Serão utilizadas, como ferramenta genérica de optimização, meta-heurísticas multi-objectivo. Casos industriais, de diferentes dimensionalidades, serão utilizados: problemas 1D retirados da indústria do papel, onde a minimização do desperdício surge a par de objectivos relacionados com o futuro balanceamento de linhas de produção; problemas 2D irregulares ("nesting problems"), onde algoritmos construtivos atenderão simultaneamente à minimização do desperdício e à compactação dos padrões; problemas 3D em que o carregamento de veículos terá em linha de conta não só a eficiente utilização do espaço mas também que em seguida problemas de determinação de rotas para os veículos terão que ser resolvidos. |